When More Objectives Make Identification Easier: The Role of Preferences and Feedback

• Multi-objective BAI is motivated by applications with potentially conflicting criteria, while its complexity reflects reward-vector geometry and the preference-defined identification task.Source: §1 · pp. 1–2
• A characteristic-time lower bound provides a unified basis for comparing multi-objective identification across preference orders, model structures, and feedback models.Source: §1 · p. 2
• Pareto and lexicographic examples show that identifying multiple optimal arms can be easier than identifying a unique optimum, or harder; neither answer-set size nor preference order alone determines difficulty.Source: §1 · p. 2
• The advantage of vector over coordinate feedback depends on preference order, and multi-objective identification can require fewer samples than the best corresponding single-objective problem.Source: §1 · p. 2
• OATS is fixed-confidence correct and asymptotically optimal, making the information-theoretic gains achievable by adaptive sampling.The algorithm is proposed alongside the paper’s comparisons of identification difficulty.Source: §1 · p. 2

• Information-theoretic BAI work uses answer-changing alternatives to derive lower bounds and optimal sampling rules, extending to multiple valid answers and general answer maps.Source: §2 · p. 3
• Multi-objective bandit research spans regret minimization and pure-exploration identification, with work covering Pareto, scalarized, cone-induced, hierarchical, and lexicographic preferences.Source: §2 · p. 3
• The paper’s distinguishing comparison places Pareto, linear, and lexicographic identification in one characteristic-time framework and examines when multi-objective feedback reduces exploration.Source: §2 · p. 3

• Each arm has an unknown mean reward vector, and sample complexity counts vector observations, or arm pulls, rather than scalar measurements.Source: §3 · pp. 3–4
• The framework considers Pareto, linear scalarization, and lexicographic preference relations to determine the identification target.Source: §3 · p. 4
• The prescribed answer is the complete set of maximal arms; Pareto dominance can yield multiple arms, while linear and lexicographic preferences typically yield a singleton.Source: §3 · p. 4
• A fixed-confidence algorithm stops at a data-dependent time, outputs a recommendation, and aims to minimize expected stopping time while remaining δ-correct.Source: §3 · p. 4
• Local stability requires the prescribed answer to remain unchanged under sufficiently small feasible perturbations of the true instance.Source: §3 · p. 4

• The characteristic information rate comes from optimizing the sampling allocation against the worst feasible alternative that changes the answer.Source: §4 · pp. 4–5
• Any δ-correct algorithm needs expected samples at least the characteristic time times kl(1 −δ, δ), yielding an asymptotic lower bound as δ decreases.The bound applies uniformly across preference relations because each order enters through its answer-changing alternatives and characteristic time.Source: §4 · p. 5
• For two arms, identification complexity is determined by the distance from the mean difference to the nearest answer-changing difference; perturbations across multiple objectives add in squared distance.Source: §4 · p. 5

5.1 Larger Optimal Sets Can Be Easier to Identify

• For d=(∆1M/2,−∆1M/2), the larger Pareto-optimal set is easier by a factor of M/2; for d=(1,...,1,ϵ), Tlex/TP=ϵ², so the ordering can reverse.The two constructions show that neither preference is uniformly easier and that optimal-set size alone does not determine difficulty.Source: §5.1 · p. 6

5.2 The Value of Feedback Depends on the Preference Order

• Vector feedback yields an M-fold reduction in characteristic time under Pareto preferences, but no gain under lexicographic preferences.Pareto identification can depend on every objective, while lexicographic identification can concentrate coordinate feedback on the first objective.Source: §5.2 · p. 7

5.3 When Multiple Objectives Outperform Single-Objective Benchmarks

• A gain greater than one means the multi-objective task has lower characteristic time than every single-objective task, even though their answers may differ.The benchmark compares tasks, not feedback models for the same task.Source: §5.3 · p. 7
• Under Pareto preferences, incomparable arms accelerate when both sign-group gap sums exceed the largest squared coordinate gap; balanced gaps can yield a gain of ⌊M/2⌋.The positive and negative gap groups must both be sufficiently large relative to ∆max(d)^2.Source: §5.3 · p. 7
• For linear scalarization, acceleration occurs when weighted gaps reinforce one another; cancellation across objectives can reduce or eliminate it.Aligned gaps promote acceleration, with a maximum gain of M.Source: §5.3 · pp. 7–8
• Under lexicographic preferences, a common-ranking constraint makes answer-changing alternatives reverse every objective’s ordering, yielding strict acceleration for M≥2 and a gain of M for equal-magnitude gaps.Without that constraint, reversing the first objective alone suffices and the acceleration disappears.Source: §5.3 · p. 8

6 Attaining the Characteristic Time

• At each round, OATS estimates the answer, targets its closest alternatives with an informative allocation, and stops when accumulated evidence exceeds the threshold.A vanishing uniform-exploration component ensures every arm is sampled, while deficit tracking keeps realized counts close to target allocations.Source: §6 · pp. 8–9
• The characteristic information rate for an allocation is the smallest rate it provides against instances with a different answer.OATS uses this answer-changing comparison to measure evidence against the closest alternative.Source: §6 · pp. 8–9
• The stopping threshold controls estimation error uniformly over time and across possible sample-count vectors.The statistic measures information accumulated against the closest instance with a different answer.Source: §6 · p. 9
• OATS is δ-correct and, for each fixed instance, its expected stopping time matches the characteristic-time lower bound to first order as δ decreases.The theorem assumes answer stability under sufficiently small feasible perturbations and a nonempty alternative set.Source: §6 · p. 9

7 Experiments

• The Pareto-to-lexicographic stopping-time ratio grew approximately linearly with M, tracking the prediction Tlex/TP = M/2.For larger M, the empirical ratio lay slightly above the prediction.Source: §7 · p. 10
• Under Pareto preferences, the coordinate-to-vector ratio grew approximately linearly with M; under lexicographic preferences, it stayed near one, as predicted.The predicted ratios were M and 1, respectively; observed trends had a modest finite-confidence gap.Source: §7 · p. 11
• The best-single-objective-to-vector stopping-time gain grew nearly linearly for linear and lexicographic orders, but more slowly for Pareto.Finite-confidence gains were below characteristic-time predictions, particularly at larger M, with scalar and vector thresholds using different dimensions.Source: §7 · p. 11
• As confidence increased, OATS’s normalized stopping time decreased toward 8/3 for Pareto and 4/3 for both linear and lexicographic identification.The linear and lexicographic curves nearly coincided, while the Pareto curve approached the higher limit.Source: §7 · p. 11
• Across the experiments, larger optimal sets could be easier to identify, vector-feedback gains depended on preference order, and multi-objective identification accelerated stopping; OATS approached characteristic-time limits.The experiments tested Propositions 1–3 and Theorem 2.Source: §7 · pp. 10–11

8 Conclusion and Future Work

• Pareto and lexicographic identification have no universal hardness ordering; vector-feedback gains range from none to an M-fold improvement, and multi-objective identification can beat the best corresponding single-objective problem.OATS asymptotically matches the lower bound, showing these gains are achievable.Source: §8 · p. 11
• Future work includes extending beyond Gaussian observations to heavy-tailed noise or partially observed objectives, and scaling optimal-allocation approximations to many arms or objectives.Source: §8 · p. 11

A Experimental Details and Additional Results

• For two-arm vector-feedback experiments, the closest-alternative calculation gives the balanced allocation (1/2, 1/2); general-K linear identification projects means onto v/∥v∥2.That projection reduces allocation to scalar Gaussian best-arm identification.Source: A Experimental Details and Additional… · p. 12
• For a singleton linear answer, the allocation parameter is found by bisection over a specified interval; after 45 iterations, the solution agrees with sequential quadratic programming to seven decimal places.The appendix also reports numerical checks of distance formulas, feedback endpoints, and predicted scaling laws.Source: A Experimental Details and Additional… · p. 12
• OATS, Uniform, and Oracle-Track share observations and stopping rules, differing only in target allocations; Oracle-Track uses true means and is not implementable in practice.In two-arm vector-feedback settings, all three target (1/2, 1/2), so differences reflect Monte Carlo variability.Source: A Experimental Details and Additional… · p. 12
• The prescribed thresholds use (K, KM) for vector feedback and (KM, KM) for coordinate feedback, except Figure 1(b), which equalizes thresholds to isolate feedback effects.Source: A Experimental Details and Additional… · pp. 12–13

A.1 HELM-Derived Model Evaluation

• Most HELM Pareto and linear theoretical gains fall below one, while common-ranking lexicographic gains shift right; observed stopping times increase with T⪯(µ) log(1/δ).The 48 instances use five objectives; stopping times lie above the reference line at δ = 0.05 because the finite-confidence threshold is conservative and lower-order terms matter.Source: §A.1 · p. 13, Figure 2 · p. 14
• OATS reduces mean stopping time by about 29.5% versus uniform allocation and is statistically indistinguishable from Oracle-Track; all methods answer correctly in every trial.The comparison uses one four-arm HELM-derived linear instance and 500 trials.Source: §A.1 · p. 14, Table 1 · p. 14

A.2 Additional Synthetic Experiments

• Doubling the gap scale divides characteristic time by four and lowers mean stopping time by about 4.7; more balanced Pareto sign groups also reduce stopping time.With unequal linear weights, adding objectives enlarges the projected gap and reduces both characteristic time and stopping time.Source: §A.2 · p. 14, Table 2 · p. 15
• For larger linear problems, OATS matches Oracle-Track and beats uniform allocation, with its advantage growing from roughly 1.3× at K = 5 to about 3.4× at K = 20.At fixed K, characteristic time is independent of M when projected gaps are held fixed; stopping time rises with M because the threshold dimension term D = KM grows.Source: §A.2 · p. 15, Table 3 · p. 15

B Proof of Theorem 1

• The lower-bound proof converts δ-correctness into divergence requirements against answer-changing alternatives, then uses expected sampling proportions to obtain an asymptotic lower bound.The change-of-measure argument uses Gaussian observation divergences and the monotonicity of binary relative entropy.Source: B Proof of Theorem 1 · p. 16

C Proof of Lemma 1

• When the model depends only on the two-arm mean difference, minimizing the alternative distance splits the mean shifts according to the sampling allocation, yielding Eq. (6).The common location of the two means is unrestricted in this model class.Source: C Proof of Lemma 1 · p. 16

D Auxiliary Results for the Two-Arm Comparisons

• For Pareto identification with mixed-sign gaps, the answer is both arms, and the squared distance to an answer-changing alternative is min{S+(d), S−(d)}.An answer changes when one arm dominates the other; the nearest alternatives are approached by coordinatewise projections.Source: D Auxiliary Results for the Two-Arm… · pp. 17–18
• Under linear scalarization, answer-changing differences form a halfspace determined by the scalarized gap, and its boundary gives the distance used in Eq. (21).Coordinate ties do not change the closure of this halfspace.Source: D Auxiliary Results for the Two-Arm… · p. 18
• With unrestricted lexicographic preferences, an answer change requires reversing the first coordinate; under common ranking, all coordinates share a sign and the feasible alternatives are restricted accordingly.The common-ranking restriction must apply to the entire feasible model, not merely describe the true gap vector.Source: D Auxiliary Results for the Two-Arm… · p. 18

E Proof of Proposition 1

• For a mixed-sign gap vector, Pareto returns both arms while lexicographic preference returns arm 1; other examples have both orders select arm 1.The section uses these examples to prove its characteristic-time comparisons in Eqs. (7) and (8).Source: E Proof of Proposition 1 · p. 19

F Proof of Proposition 2

• Across preferences, vector feedback has at least as much characteristic information as coordinate feedback, and the two endpoint examples attain the bounds in Eq. (9).Any vector allocation induces a coordinate allocation that gathers exactly a 1/M fraction of its information against every alternative.Source: F Proof of Proposition 2 · pp. 19–20
• For Pareto identification at equal positive gaps, coordinate feedback has characteristic time M times that of vector feedback, with uniform allocation attaining the coordinate-feedback bound.Reversing any single objective can change the answer, so coordinate sampling must cover all M objectives.Source: F Proof of Proposition 2 · p. 20
• For lexicographic identification, only the first coordinate needs to be reversed, so coordinate feedback can allocate half its samples to each arm on that objective.The resulting characteristic time matches vector feedback at the stated endpoint.Source: F Proof of Proposition 2 · p. 20

G Proof of Proposition 3

• The single-coordinate benchmark is Tbest(d) = 8/∆²max(d).Source: G Proof of Proposition 3 · p. 20
• Strict Pareto acceleration on the unrestricted comparison model requires M ≥ 4.Source: G Proof of Proposition 3 · p. 21
• For linear scalarization, equal positive weights attain a gain of M at d = ∆1M.Source: G Proof of Proposition 3 · p. 21
• For lexicographic preferences, the factor-M gain is attained when all coordinate gaps have equal magnitude, and the acceleration depends on the common-ranking constraint.Source: G Proof of Proposition 3 · p. 21

H Proof of Theorem 2

• OATS’s proof establishes δ-correctness, almost-sure stopping, and finite expected stopping time.Source: H Proof of Theorem 2 · pp. 23, 25
• OATS’s expected stopping time matches the characteristic-time lower bound to first order as δ ↓ 0.Source: H Proof of Theorem 2 · p. 25