Paper deep dive
When More Objectives Make Identification Easier: The Role of Preferences and Feedback
Bo Xue, Ji Cheng, Yuanyu Wan, Shuang Qiu
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Best-arm identification (BAI) aims to identify the optimal arm using as few samples as possible. While most existing work focuses on a single objective, many real-world applications involve multiple criteria, which motivates the study of BAI in multi-objective bandits. Intuitively, multi-objective identification seems harder, since the learner must identify optimal arms in a higher-dimensional reward space; however, the additional objectives also provide richer feedback that can reduce the required exploration. In this paper, we characterize when and why multiple objectives can make BAI easier. For Gaussian bandits, we establish a characteristic-time lower bound for fixed-confidence identification that holds uniformly across preference orders. Through explicit comparisons under Pareto, linear, and lexicographic preferences, we reveal three phenomena: (i) identifying a larger optimal set can require fewer samples than identifying a unique optimum; (ii) the advantage of vector feedback over coordinate feedback depends fundamentally on the preference order; and (iii) multi-objective identification can require fewer samples than even the easiest corresponding single-objective problem. Finally, we propose Order-Aware Track-and-Stop (OATS), an algorithm that is correct at any prescribed confidence level and asymptotically matches the lower bound.
Tags
Links
- Source: https://arxiv.org/abs/2610.18577v1
- Canonical: https://arxiv.org/abs/2610.18577v1
Trouble viewing inline? Open PDF directly →
Full Text
96,289 characters extracted from source content.
Expand or collapse full text
22footnotetext: Corresponding Author When More Objectives Make Identification Easier: The Role of Preferences and Feedback Bo XueJi ChengYuanyu Wan †thanks: City University of Hong Kong. Email: boxue4-c@my.cityu.edu.hk†thanks: City University of Hong Kong. Email: J.Cheng@my.cityu.edu.hk†thanks: Zhejiang University. Email: wanyy@zju.edu.hk Shuang Qiu †thanks: City University of Hong Kong. Email: shuanqiu@cityu.edu.hk October 13, 2026 Abstract Best-arm identification (BAI) aims to identify the optimal arm using as few samples as possible. While most existing work focuses on a single objective, many real-world applications involve multiple criteria, which motivates the study of BAI in multi-objective bandits. Intuitively, multi-objective identification seems harder, since the learner must identify optimal arms in a higher-dimensional reward space; however, the additional objectives also provide richer feedback that can reduce the required exploration. In this paper, we characterize when and why multiple objectives can make BAI easier. For Gaussian bandits, we establish a characteristic-time lower bound for fixed-confidence identification that holds uniformly across preference orders. Through explicit comparisons under Pareto, linear, and lexicographic preferences, we reveal three phenomena: (i) identifying a larger optimal set can require fewer samples than identifying a unique optimum; (i) the advantage of vector feedback over coordinate feedback depends fundamentally on the preference order; and (i) multi-objective identification can require fewer samples than even the easiest corresponding single-objective problem. Finally, we propose Order-Aware Track-and-Stop (OATS), an algorithm that is correct at any prescribed confidence level and asymptotically matches the lower bound. 1 Introduction Best-arm identification (BAI) is a fundamental pure-exploration problem that aims to identify the optimal arm using as few samples as possible (Even-Dar et al., 2006; Bubeck et al., 2009; Garivier and Kaufmann, 2016). Classical BAI considers scalar rewards and defines the optimal arm as the one with the largest mean reward (Audibert et al., 2010; Gabillon et al., 2012; Karnin et al., 2013; Kaufmann et al., 2016). However, many applications involve multiple and potentially conflicting criteria, such as accuracy, cost, and latency in LLM evaluation (Liang et al., 2023; Chang et al., 2024). This motivates multi-objective BAI, in which each arm yields a reward vector and optimality is determined by a preference relation (Roijers et al., 2013; Auer et al., 2016; Ararat and Tekin, 2023; Shukla and Basu, 2024). For example, linear scalarization compares weighted rewards (Drugan and Nowe, 2013), lexicographic preferences rank objectives by priority (Hüyük and Tekin, 2021), and Pareto dominance may admit multiple maximal arms (Auer et al., 2016). Multi-objective BAI therefore comprises distinct identification tasks whose complexity depends on the preference relation. Multi-objective identification may appear harder than its scalar counterpart, as its complexity depends not only on reward gaps but also on the geometry of the reward vectors (Karagözlü et al., 2024). Under Pareto preferences, the learner may even need to identify the entire set of nondominated arms (Kone et al., 2023). On the other hand, multiple objectives also provide richer feedback: each arm pull typically reveals all reward coordinates, and evidence accumulated across objectives can reduce the required exploration (Xue et al., 2026d). This tension motivates our central question: When do multiple objectives make best-arm identification harder, and when can they make it easier? Existing studies provide algorithms and complexity guarantees for Pareto identification (Auer et al., 2016), preference-cone identification (Das et al., 2025), cost-aware Pareto identification (Xue et al., 2026c), and lexicographic identification with cross-objective constraints (Xue et al., 2026d). However, these results are derived under different answer maps, model classes, and feedback models, which makes direct comparisons difficult. A unified analysis should therefore disentangle three factors: the preference order, which determines how arms are compared and hence what must be identified; the model structure, which specifies how rewards may vary across arms and objectives; and the feedback model, which determines what each sample reveals (Garivier and Kaufmann, 2016; Fiez et al., 2019; Degenne et al., 2020; Du et al., 2021). Their interaction, rather than the number of objectives alone, determines the sample complexity. To address this gap, we adopt the characteristic time as a common measure of identification difficulty (Garivier and Kaufmann, 2016; Degenne and Koolen, 2019). For Gaussian bandits, it is governed by the optimal rate at which sampling can distinguish the true instance from feasible alternatives with a different correct answer. We construct matched comparisons in which only one of the three factors (preference order, model structure, or feedback model) varies at a time. This allows us to isolate the effect of each factor on sample complexity and to quantify when, and by how much, multiple objectives facilitate identification. Our main contributions are as follows. • We establish a characteristic-time lower bound for fixed-confidence multi-objective BAI under general preference-induced answer maps. This provides a unified information-theoretic basis for comparing identification tasks across preference orders, model structures, and feedback models. • Through explicit comparisons under Pareto and lexicographic preferences, we construct instances in which identifying multiple optimal arms is easier than identifying a unique optimum, as well as instances in which the reverse holds. Hence, neither the preference order nor the number of returned arms alone determines identification difficulty. • We characterize the advantage of vector feedback over coordinate feedback and establish conditions under which multi-objective identification requires fewer samples than the best corresponding single-objective benchmark. These results clarify when observations of multiple objectives accumulate into useful evidence rather than being redundant. • We propose Order-Aware Track-and-Stop (OATS) and prove its fixed-confidence correctness and asymptotic optimality. Hence, the information-theoretic gains revealed by our comparisons are achievable by an adaptive sampling algorithm. 2 Related Work We review two closely related lines of research: best-arm identification and multi-objective bandits. Best-arm identification. BAI is a pure-exploration problem studied in both the fixed-budget and the fixed-confidence settings. Early work developed elimination- and confidence-based methods with gap-dependent guarantees for identifying the best arm (Even-Dar et al., 2006; Bubeck et al., 2009; Audibert et al., 2010; Kalyanakrishnan et al., 2012; Gabillon et al., 2012; Karnin et al., 2013; Jamieson et al., 2014). A complementary information-theoretic line characterizes instance difficulty through alternative models with different correct answers, which yields fundamental lower bounds and asymptotically optimal frequentist or Bayesian sampling rules (Kaufmann et al., 2016; Garivier and Kaufmann, 2016; Russo, 2020). This framework has been extended to problems with multiple valid answers and general answer maps, where the optimal allocation of samples can be formulated as a sequential game (Degenne and Koolen, 2019; Degenne et al., 2019). Work on combinatorial, linear, and transductive pure exploration further exploits structural dependencies and shared observations through optimization oracles and experimental-design principles (Chen et al., 2014; Soare et al., 2014; Fiez et al., 2019; Degenne et al., 2020). Multi-objective bandits. Multi-objective bandits associate each arm with a reward vector and define desirable decisions through a preference relation. Early regret-minimization studies considered Pareto dominance and scalarized utilities, and developed methods that learn nondominated arms or optimize aggregate objectives (Drugan and Nowe, 2013; Busa-Fekete et al., 2017). Subsequent work extended multi-objective regret analysis to contextual, adversarial, and structured linear settings, including dominant-objective and mixed Pareto–lexicographic preferences (Turğay et al., 2018; Tekin and Turğay, 2018; Xu and Klabjan, 2023; Cheng et al., 2024). Within lexicographic bandits, regret guarantees have been developed for Lipschitz, adversarially corrupted, and structured low-rank models (Xue et al., 2025a; Xue et al., 2025b; Xue et al., 2026a); hierarchical preferences have also been incorporated into safe multi-objective linear bandits (Xue et al., 2026b). A complementary pure-exploration line studies Pareto-set identification, with confidence-region, adaptive-sampling, and elimination methods for approximate, relaxed, fixed-budget, and exact fixed-confidence recovery (Auer et al., 2016; Kone et al., 2023; Kone et al., 2024; Crépon et al., 2024). Recent cost-aware formulations additionally study Pareto identification when vector observations have heterogeneous evaluation costs (Xue et al., 2026c). More general formulations replace coordinatewise dominance with cone-induced, hierarchical, or lexicographic orders, and characterize how preference geometry and structural relations shape identification complexity (Ararat and Tekin, 2023; Karagözlü et al., 2024; Shukla and Basu, 2024; Das et al., 2025; Xue et al., 2026d). Most existing studies analyze a single preference relation under a fixed feedback model. In contrast, we compare Pareto, linear, and lexicographic identification within a common characteristic-time framework and determine when multi-objective feedback reduces the required exploration. 3 Preliminaries Notation. For any integer K≥1K≥ 1, let [K]=1,2,…,K[K]=\1,2,…,K\ and ΔK=w∈ℝ+K:∑i=1Kwi=1 _K=\w _+^K: _i=1^Kw_i=1\ denote the probability simplex. For any matrix ∈ℝK×M x ^K× M with rows x1,…,xKx_1,…,x_K, its squared Frobenius norm is ‖F2=∑i=1K‖xi‖22\| x\|_F^2= _i=1^K\|x_i\|_2^2. For any set S⊆ℝMS ^M, the distance from x∈ℝMx ^M to S is dist(x,S)=infz∈S‖x−z‖2 (x,S)= _z∈ S\|x-z\|_2. We consider a stochastic multi-armed bandit with K≥2K≥ 2 arms and M≥1M≥ 1 objectives, where larger rewards are preferred. Each arm i∈[K]i∈[K] is associated with an unknown mean vector μi∈ℝM _i ^M, and the bandit instance is denoted by =(μ1,…,μK)∈ℝK×M μ=( _1,…, _K) ^K× M. At round t, the learner selects an arm ItI_t based on the observations collected so far and observes Xt=μIt+εt,εt∼(0,IM),X_t= _I_t+ _t, _t (0,I_M), where the noise vectors are independent across rounds. Accordingly, sample complexity counts vector observations (i.e., arm pulls) rather than individual scalar measurements. The identification target is determined by a known preference relation ⪯ on ℝMR^M, with strict part denoted by ≺ . We consider three representative orders: x≺Py x _Py ⇔xm≤ymfor every mand xm<ymfor some m, x_m≤ y_m\ for every m\ and x_m<y_m\ for some m, (Pareto), (Pareto), x≺vy x _vy ⇔v⊤x<v⊤y,v∈ℝ+M∖0, v x<v y, v _+^M \0\, (linear scalarization), (linear scalarization), x≺lexy x _lexy ⇔xr(x,y)<yr(x,y),r(x,y)=minm:xm≠ym, x_r(x,y)<y_r(x,y), r(x,y)= \m:x_m≠ y_m\, (lexicographic). (lexicographic). For an instance μ, the prescribed answer is the complete set of maximal arms: A⪯()=i∈[K]:∄j∈[K] such that μi≺μj.A_ ( μ)=\i∈[K]: j∈[K] such that _i _j\. (1) Under linear scalarization or lexicographic preferences, this set is typically a singleton, whereas Pareto dominance may admit multiple maximal arms. Importantly, A⪯()A_ ( μ) is a single set-valued answer: the learner must recover the entire set in Eq. (1), rather than return any one of several valid answers as in multiple-answer identification (Degenne and Koolen, 2019). More generally, our analysis applies to any prescribed answer map with a finite range. Fixed-confidence identification. For δ∈(0,1/2)δ∈(0,1/2), a fixed-confidence algorithm adaptively selects arms based on past observations, stops at a data-dependent time τδ _δ, and outputs a recommendation A^δ⊆[K] A_δ [K]. It is δ-correct on a model class Θ⊆ℝK×M ^K× M if, for every ∈Θ μ∈ , ℙ(τδ<∞)=1,ℙ(A^δ=A⪯())≥1−δ.P_ μ( _δ<∞)=1, _ μ\! ( A_δ=A_ ( μ) )≥ 1-δ. Performance is measured by the expected stopping time [τδ]E_ μ[ _δ], which we aim to minimize subject to δ-correctness. The difficulty of this problem depends on how close μ is to instances in Θ with a different answer: the closer these alternatives are, the more samples are needed to rule them out. In classical BAI, a standard assumption is that the best arm is unique (Kaufmann et al., 2016; Garivier and Kaufmann, 2016). With finitely many arms, this implies a strictly positive gap between the best and second-best arms, so the best arm is preserved under sufficiently small perturbations of the means. We impose the analogous condition on the general, possibly set-valued, answer map A⪯A_ . Assumption 1 (Local stability). The true instance ∈Θ μ∈ is locally stable with respect to the answer map: there exists r>0r_ μ>0 such that A⪯()=A⪯()for every ∈Θ satisfying ‖−‖F<r.A_ ( ν)=A_ ( μ) every ν∈ satisfying \| ν- μ\|_F<r_ μ. (2) Assumption 1 requires the answer A⪯()A_ ( μ) to remain unchanged under sufficiently small feasible perturbations. Equivalently, μ lies in the interior of the set of instances sharing its answer. 4 A Unified Lower Bound for Identification In this section, we derive a characteristic-time lower bound that holds uniformly across preference relations. We first describe the answer-changing alternatives that any algorithm must rule out. For an instance ∈Θ μ∈ , define its set of feasible alternatives as Alt⪯()=∈Θ:A⪯()≠A⪯(). _ ( μ)=\ ν∈ :A_ ( ν)≠ A_ ( μ)\. (3) A δ-correct algorithm must distinguish μ from every instance in Alt⪯() _ ( μ). Under the Gaussian observation model, each sample from arm i contributes a KL divergence of ‖μi−νi‖22/2\| _i- _i\|_2^2/2 between μ and ν. Hence, under an allocation w∈ΔKw∈ _K, the information rate against ν is ℐ(,,w)=12∑i=1Kwi‖μi−νi‖22.I( μ, ν;w)= 12 _i=1^Kw_i\| _i- _i\|_2^2. Optimizing the allocation against the worst-case feasible alternative yields the characteristic information rate, whose reciprocal is the characteristic time: ℐ⪯∗()=supw∈ΔKinf∈Alt⪯()ℐ(,,w),T⪯()=1ℐ⪯∗().I_ ^*( μ)= _w∈ _K _ ν∈ _ ( μ)I( μ, ν;w), T_ ( μ)= 1I_ ^*( μ). (4) We restrict attention to instances with nonempty alternative sets. Together with local stability (Assumption 1), this guarantees 0<ℐ⪯∗()<∞0<I_ ^*( μ)<∞. Theorem 1 (Unified characteristic-time lower bound). For any δ∈(0,1/2)δ∈(0,1/2), any algorithm that is δ-correct on Θ , and any ∈Θ μ∈ , [τδ]≥T⪯()kl(1−δ,δ)⇒lim infδ↓0[τδ]log(1/δ)≥T⪯(),E_ μ[ _δ]≥ T_ ( μ) (1-δ,δ) _δ 0 E_ μ[ _δ] (1/δ)≥ T_ ( μ), (5) where kl(p,q)=plog(p/q)+(1−p)log((1−p)/(1−q)) (p,q)=p (p/q)+(1-p) ((1-p)/(1-q)) is the binary relative entropy. Theorem 1 applies uniformly to all preference relations because the order enters only through the answer-changing set Alt⪯() _ ( μ) and the resulting characteristic time T⪯()T_ ( μ). By a standard change-of-measure argument, any δ-correct algorithm must accumulate an expected divergence of at least kl(1−δ,δ) (1-δ,δ) between μ and every answer-changing alternative (Kaufmann et al., 2016; Garivier and Kaufmann, 2016). Under any sampling allocation, the worst-case information gained per sample is at most ℐ⪯∗()I_ ^*( μ). Therefore, at least T⪯()kl(1−δ,δ)T_ ( μ) (1-δ,δ) samples are needed in expectation, which yields Eq. (5). The asymptotic statement follows from kl(1−δ,δ)∼log(1/δ) (1-δ,δ) (1/δ) as δ↓0δ 0. Two-arm geometry. For K=2K=2, suppose that both Θ and the answer depend only on the difference between the two arm means. Define the set of feasible differences as =μ1−μ2:=(μ1,μ2)∈Θ⊆ℝM.D=\ _1- _2: μ=( _1, _2)∈ \ ^M. For a fixed instance =(μ1,μ2)∈Θ μ=( _1, _2)∈ , let d=μ1−μ2∈d= _1- _2 . With a slight abuse of notation, define T⪯(d)=T⪯(),Alt⪯(d)=ν1−ν2:=(ν1,ν2)∈Alt⪯()⊆.T_ (d)=T_ ( μ), _ (d)=\ _1- _2: ν=( _1, _2)∈ _ ( μ)\ . Both quantities are well defined and invariant under a common translation of the two arm means. Lemma 1 (Two-arm distance formula). If d∈d and 0<dist(d,Alt⪯(d))<∞0< (d, _ (d))<∞, then T⪯(d)=8dist2(d,Alt⪯(d)).T_ (d)= 8 ^2(d, _ (d)). (6) Lemma 1 gives a geometric interpretation: identification complexity is determined by the distance from d to the nearest answer-changing difference. When several objectives must be perturbed to change the answer, their contributions add up in the squared distance, reducing the characteristic time. We next use this formula to compare preference relations. 5 Multi-Objective Identification Gains In this section, we use the characteristic time to determine when multiple objectives facilitate identification. Specifically, we address three questions: (i) Can a larger optimal set be easier to identify? (i) How much can vector feedback reduce the complexity of a fixed identification task? (i) When can a multi-objective task be easier than the best corresponding single-objective benchmark? 5.1 Larger Optimal Sets Can Be Easier to Identify We first compare Pareto and lexicographic identification on the same two-arm instances. The following result shows that identification difficulty is not determined by the size of the optimal set. Proposition 1 (A larger optimal set can be easier to identify). Consider the unrestricted two-arm model (Appendix D). Let M≥4M≥ 4 be even and Δ>0 >0. For d=(ΔM/2,−ΔM/2)d=( 1_M/2,- 1_M/2), the Pareto-optimal set is 1,2\1,2\ and the lexicographic optimum is 1\1\. Nevertheless, TP(d)=16MΔ2,Tlex(d)=8Δ2⇒Tlex(d)TP(d)=M2.T_P(d)= 16M ^2, T_lex(d)= 8 ^2 T_lex(d)T_P(d)= M2. (7) Conversely, for d=(1,…,1,ϵ)d=(1,…,1,ε) with 0<ϵ<10<ε<1, both preferences identify arm 11 as optimal, but TP(d)=8ϵ2,Tlex(d)=8⇒Tlex(d)TP(d)=ϵ2.T_P(d)= 8ε^2, T_lex(d)=8 T_lex(d)T_P(d)=ε^2. (8) In the first instance, Eq. (7), each arm outperforms the other on half of the objectives. Under Pareto dominance, changing the answer requires removing one arm from the Pareto-optimal set, which in turn requires closing all M/2M/2 coordinate gaps on which that arm is superior. Hence, the nearest Pareto alternative lies at squared distance MΔ2/2M ^2/2. By contrast, the lexicographic answer is determined solely by the first coordinate, so the nearest alternative lies at squared distance Δ2 ^2. Lemma 1 therefore yields the factor-M/2M/2 separation in Eq. (7). The second instance, Eq. (8), shows that this ordering does not hold uniformly. Although both preferences identify arm 11 as optimal, the Pareto answer changes as soon as the smallest coordinate gap ϵε is reversed, whereas the lexicographic answer depends only on the fixed gap in the first coordinate. Consequently, Tlex(d)/TP(d)=ϵ2T_lex(d)/T_P(d)=ε^2, which can be made arbitrarily small as ϵ↓0ε 0. Together, these two constructions show that neither preference relation is uniformly easier than the other, and that identification complexity cannot be inferred from the size of the optimal set alone. 5.2 The Value of Feedback Depends on the Preference Order We next compare vector and coordinate feedback for a fixed identification task. The following result shows that the gain from vector feedback can range from none to a factor of M. Under vector feedback, sampling an arm reveals all M objectives, whereas coordinate feedback reveals only one chosen objective of one chosen arm. For an allocation q∈ΔKMq∈ _KM over arm–objective pairs, define the coordinate-feedback information rate against an alternative ν as ℐco(,,q)=12∑i=1K∑m=1Mqi,m(μi,m−νi,m)2.I^co( μ, ν;q)= 12 _i=1^K _m=1^Mq_i,m( _i,m- _i,m)^2. The coordinate-feedback characteristic time T⪯coT_ ^co is defined analogously to (4), with q and ℐcoI^co replacing w and ℐI, respectively. Proposition 2 (The value of feedback depends on the preference order). Every instance μ with Alt⪯()≠∅ _ ( μ)≠ satisfies T⪯()≤T⪯co()≤MT⪯().T_ ( μ)≤ T_ ^co( μ)≤ MT_ ( μ). (9) In the unrestricted two-arm model with d=ΔMd= 1_M and Δ>0 >0, the lexicographic and Pareto orders attain the lower and upper endpoints, respectively: Tlex(d)=TP(d)=8Δ2,Tlexco(d)=8Δ2,TPco(d)=8MΔ2.T_lex(d)=T_P(d)= 8 ^2, T_lex^co(d)= 8 ^2, T_P^co(d)= 8M ^2. (10) Proposition 2 shows that the benefit of vector feedback depends fundamentally on the preference order, ranging from no gain to an M-fold reduction in characteristic time. Under Pareto dominance, every objective can change the optimal set, so coordinate feedback must spread samples across all M objectives, whereas vector feedback observes them simultaneously and achieves the full factor-M improvement. Under the lexicographic order, only the first objective matters, so coordinate feedback can concentrate entirely on that objective and match vector feedback. Hence, richer feedback helps only when the preference order makes multiple objectives informative for identification. 5.3 When Multiple Objectives Outperform Single-Objective Benchmarks We now compare multi-objective identification with the best single-objective benchmark. Each objective, considered alone, defines a scalar BAI problem, and we ask whether multi-objective identification can require fewer samples than even the easiest of these scalar problems. For the two-arm gap vector d=μ1−μ2∈ℝMd= _1- _2 ^M, assume that dm≠0d_m≠ 0 for all m. Objective m alone then has characteristic time 8/dm28/d_m^2. With Δmax(d)=maxm∈[M]|dm| _ (d)= _m∈[M]|d_m|, we define the best single-objective benchmark and the corresponding multi-objective gain as Tbest(d)=minm∈[M]8dm2=8Δmax2(d),⪯(d)=Tbest(d)T⪯(d). T_best(d)= _m∈[M] 8d_m^2= 8 _ ^2(d), Gain_ (d)= T_best(d)T_ (d). A gain greater than one means that the multi-objective task has a smaller characteristic time than every single-objective task. Since the multi-objective and single-objective tasks may have different answers, this is a comparison between tasks, not between feedback models for the same task. Proposition 3 (Acceleration under three preference orders). Let d∈ℝMd ^M have no zero coordinates, and define S+(d)=∑m:dm>0dm2S_+(d)= _m:d_m>0d_m^2 and S−(d)=∑m:dm<0dm2S_-(d)= _m:d_m<0d_m^2. Under vector feedback, strict improvement over the best single-objective benchmark occurs in the following regimes: P(d)=minS+(d),S−(d)Δmax2(d)>1, Gain_P(d)= \S_+(d),S_-(d)\ _ ^2(d)>1, if minS+(d),S−(d)>Δmax2(d), \S_+(d),S_-(d)\> _ ^2(d), (11) v(d)=(v⊤d)2‖v‖22Δmax2(d)>1, Gain_v(d)= (v d)^2\|v\|_2^2 _ ^2(d)>1, if |v⊤d|>‖v‖2Δmax(d), |v d|>\|v\|_2 _ (d), lex(d)=‖d‖22Δmax2(d)>1, Gain_lex(d)= \|d\|_2^2 _ ^2(d)>1, if d∈=ℝ++M∪(−ℝ++M),M≥2. d =R_++^M∪(-R_++^M),\ M≥ 2. Proposition 3 shows that multi-objective acceleration arises when changing the answer requires coordinated changes across several objectives, so that their information contributions accumulate under vector feedback. Under Pareto dominance, this occurs when the two arms are incomparable and both sign groups have sufficiently large aggregate gaps, i.e., minS+(d),S−(d)>Δmax2(d) \S_+(d),S_-(d)\> _ ^2(d). The gain is largest when the positive and negative gaps are well balanced across objectives, and it can reach ⌊M/2⌋ M/2 . Under linear scalarization, acceleration occurs when the weighted gaps reinforce one another, i.e., |v⊤d|>‖v‖2Δmax(d)|v d|>\|v\|_2 _ (d). Thus, aligned gaps promote acceleration, whereas cancellation across objectives reduces or eliminates it; the maximum gain is M. Under lexicographic preferences, acceleration stems from the common-ranking constraint =ℝ++M∪(−ℝ++M)D=R_++^M∪(-R_++^M). This constraint forces every answer-changing alternative to reverse the ordering on all objectives simultaneously, so the relevant separation scales with ‖d‖22\|d\|_2^2. Consequently, strict acceleration occurs for every M≥2M≥ 2, and the gain reaches M when all coordinate gaps have equal magnitude. Without this constraint, reversing the first objective alone suffices to change the lexicographic answer, and the multi-objective acceleration disappears (Appendix G). 6 Attaining the Characteristic Time In this section, we show that the characteristic-time lower bound in Theorem 1 can be attained asymptotically. Building on the Track-and-Stop framework (Garivier and Kaufmann, 2016; Degenne and Koolen, 2019), we propose OATS, an order-aware procedure that repeatedly estimates the current answer, allocates samples to distinguish it from its closest alternatives, and stops once sufficient evidence has been collected. The complete procedure is given in Algorithm 1. We first introduce some notation. Let =A⪯():∈ΘA=\A_ ( μ): μ∈ \ denote the set of possible answers, and let ΘA=∈Θ:A⪯()=A _A=\ ν∈ :A_ ( ν)=A\ denote the region of instances with answer A. For any estimate ^=(μ^1,…,μ^K)∈ℝK×M μ=( μ_1,…, μ_K) ^K× M and allocation w∈ΔKw∈ _K, define gA(^,w)=inf∈Θ∖ΘAℐ(^,,w)=inf∈Θ∖ΘA12∑i=1Kwi‖μ^i−νi‖22,g_A( μ,w)= _ ν∈ _AI( μ, ν;w)= _ ν∈ _A 12 _i=1^Kw_i\| μ_i- _i\|_2^2, which is the smallest information rate that w provides against instances with a different answer. Algorithm 1 OATS: Order-Aware Track-and-Stop 1: Preference relation ⪯ , model class Θ , confidence δ 2: Pull each arm once; set t←Kt← K and S←KS← 1_K 3: while true do 4: Compute the empirical mean matrix ^t μ_t 5: Fit the candidate answer A^t A_t using Eq. (12) 6: Evaluate the evidence ZtZ_t against competing answers using Eq. (13) 7: if Zt>β(t,δ)Z_t>β(t,δ) then 8: return A^t A_t 9: end if 10: Compute the most informative allocation: wt∈argmaxw∈ΔKgA^t(^t,w)w_t∈ _w∈ _Kg_ A_t( μ_t,w) 11: Mix with forced exploration: qt←(1−t−1/2)wt+t−1/2K/Kq_t←(1-t^-1/2)w_t+t^-1/2 1_K/K 12: Update the cumulative target: S←S+qtS← S+q_t 13: Select the arm with the largest deficit: It+1←argmaxi∈[K]Si−Ni(t)I_t+1← _i∈[K]\S_i-N_i(t)\ 14: Pull It+1I_t+1 and update the counts and empirical means 15: t←t+1t← t+1 16: end while Given a confidence level δ∈(0,1)δ∈(0,1), OATS first samples every arm once. At each round t, it computes the empirical mean matrix ^t μ_t and selects the answer whose region is closest to this estimate: A^t∈argminA∈inf∈ΘA∥^t−∥F2. A_t∈ _A _ ν∈ _A\| μ_t- ν\|_F^2. (12) Let Ni(t)=∑s=1tIs=iN_i(t)= _s=1^tI\I_s=i\ denote the number of pulls of arm i∈[K]i∈[K] up to round t, and let N(t)=(N1(t),…,NK(t))N(t)=(N_1(t),…,N_K(t)). OATS then evaluates the evidence in favor of A^t A_t through Zt=t×gA^t(^t,N(t)t)=inf∈Θ∖ΘA^t12∑i=1KNi(t)‖μ^i(t)−νi‖22.Z_t=t× g_ A_t ( μ_t, N(t)t )= _ ν∈ _ A_t 12 _i=1^KN_i(t)\| μ_i(t)- _i\|_2^2. (13) Thus, ZtZ_t measures the information accumulated against the closest instance with a different answer. We use the stopping threshold β(t,δ)=KM2+KMlog2(t+1)K+2δ+log2(t+1)K+2δ,β(t,δ)= KM2+ KM 2(t+1)^K+2δ+ 2(t+1)^K+2δ, (14) which controls the estimation error uniformly over time and over all possible sample-count vectors. If Zt>β(t,δ)Z_t>β(t,δ), the algorithm stops and returns A^t A_t. Otherwise, OATS computes the most informative allocation wt∈argmaxw∈ΔKgA^t(^t,w),w_t∈ _w∈ _Kg_ A_t( μ_t,w), (15) which maximizes the estimated information rate against alternatives to the current answer. To ensure sufficient exploration, it then sets qt=(1−t−1/2)wt+t−1/2K.q_t=(1-t^-1/2)w_t+t^-1/2 1_KK. The uniform component vanishes asymptotically but guarantees that every arm receives Ω(t) ( t) observations. Next, OATS updates the cumulative target and selects the arm with the largest deficit: S←S+qt,It+1∈argmaxi∈[K]Si−Ni(t).S← S+q_t, I_t+1∈ _i∈[K]\S_i-N_i(t)\. Since Si−Ni(t)S_i-N_i(t) is the sampling deficit of arm i relative to its cumulative target, this tracking rule keeps the realized sample counts within a bounded distance of their targets. Finally, OATS pulls arm It+1I_t+1 and updates the counts and empirical means. The following theorem establishes the correctness and asymptotic optimality of OATS. Theorem 2 (Asymptotic optimality of OATS). Suppose every instance in Θ satisfies Assumption 1 and has a nonempty alternative set. Then OATS is δ-correct, and for every ∈Θ μ∈ , limδ↓0[τδ]log(1/δ)=T⪯(). _δ 0 E_ μ[ _δ] (1/δ)=T_ ( μ). (16) Theorem 2 shows that OATS is not only δ-correct but also asymptotically instance-optimal: for any fixed instance, its expected stopping time matches the characteristic-time lower bound of Theorem 1 to first order as δ↓0δ 0. This extends classical Track-and-Stop for scalar BAI (Garivier and Kaufmann, 2016) to preference-induced, possibly set-valued identification problems. Whereas previous extensions have considered multiple valid answers (Degenne and Koolen, 2019) or specific multi-objective targets such as Pareto-front identification (Crépon et al., 2024), OATS handles different preference orders and model structures through a single answer-changing formulation. Consequently, the three phenomena of Section 5 are attained by an adaptive procedure and are not mere properties of the lower bound. In particular, whenever the preference relation or structural constraints enlarge the information distance to the nearest answer-changing alternative, OATS asymptotically exploits this additional information. Applying the same analysis to a single known coordinate also shows that the oracle single-objective benchmark is attainable. Figure 1: Synthetic results for Propositions 1–3 and Theorem 2. (a) The ratio [τlex]/[τP]E[ _lex]/E[ _P] grows with M: Pareto-set identification becomes increasingly easier than lexicographic identification. (b) The feedback gain [τcoord]/[τvec]E[ _coord]/E[ _vec] grows with M under the Pareto order but remains near one under the lexicographic order. (c) The gain [τbest]/[τvec]E[ _best]/E[ _vec] increases with M under all three orders and stays above one, confirming multi-objective acceleration. (d) The normalized stopping time [τδ]/log(1/δ)E_ μ[ _δ]/ (1/δ) decreases toward the corresponding characteristic time as δ decreases. Markers show empirical means with 95% confidence intervals, and dashed lines show theoretical predictions. 7 Experiments In this section, we run synthetic experiments to test whether OATS exhibits the identification phenomena of Propositions 1–3 and the asymptotic optimality of Theorem 2. Appendix A reports supplementary results on instances derived from the HELM Instruct ratings (Zhang et al., 2024). Experimental setup. All experiments use independent observations Xi,t∼(μi,IM)X_i,t ( _i,I_M). For two-arm instances, we set μ1=d/2 _1=d/2 and μ2=−d/2 _2=-d/2. Unless otherwise specified, we use Δ=1 =1 and δ=0.05δ=0.05. Each configuration is evaluated over 500 independent repetitions with deterministic seeds. Figure 1(a) evaluates Proposition 1 for even M∈4,6,8,10,12,16M∈\4,6,8,10,12,16\ under the mixed-sign gap d=(M/2,−M/2)d=(1_M/2,-1_M/2), for which the proposition predicts Tlex/TP=M/2T_lex/T_P=M/2. The empirical stopping-time ratio grows approximately linearly in M and closely tracks this prediction, lying slightly above it for larger M. These results confirm that the advantage of Pareto-set identification over lexicographic identification scales linearly with the number of objectives. Figure 1(b) validates Proposition 2 with d=Md=1_M and M∈2,4,6,8,10,12M∈\2,4,6,8,10,12\, comparing vector and coordinate feedback under the Pareto and lexicographic orders. The proposition predicts coordinate-to-vector characteristic-time ratios of M and 11, respectively. The observed Pareto ratio grows approximately linearly in M, whereas the lexicographic ratio stays close to one. Both trends closely follow the predictions, up to a modest finite-confidence gap. These results confirm that the benefit of vector feedback depends critically on the preference order. Figure 1(c) tests Proposition 3 for M∈2,3,4,5,6,8,10,12M∈\2,3,4,5,6,8,10,12\ by comparing vector-feedback identification with a scalar oracle that knows m∗∈argmaxm|dm|m^*∈ _m|d_m|. We use d=(M/2,−M/2)d=(1_M/2,-1_M/2) for the Pareto order and d=Md=1_M for the linear and common-ranking lexicographic orders, with v=M/Mv=1_M/ M for linear scalarization. The stopping-time gain [τbest]/[τvec]E[ _best]/E[ _vec] grows nearly linearly in M for the linear and lexicographic orders and more slowly for the Pareto order, consistent with the theory. At finite confidence, the empirical gains remain below the characteristic-time predictions, particularly for larger M, because the thresholds in Eq. (14) for the scalar and vector procedures use different dimensions, namely KM=2KM=2 and KM=2MKM=2M, respectively. Figure 1(d) evaluates the asymptotic optimality of OATS established in Theorem 2. We use M=6M=6, with d=(1,1,1,−1,−1,−1)d=(1,1,1,-1,-1,-1) for the Pareto order and d=6d=1_6 for the linear and lexicographic orders. We plot the normalized stopping time [τδ]/log(1/δ)E_ μ[ _δ]/ (1/δ) for confidence levels δ ranging from 0.20.2 down to 10−25010^-250. The theorem predicts that this quantity converges to T⪯()=8/3T_ ( μ)=8/3 for Pareto identification and to T⪯()=4/3T_ ( μ)=4/3 for both linear and lexicographic identification. Consistent with this prediction, all three curves decrease monotonically toward their respective limits as log(1/δ) (1/δ) grows. The linear and lexicographic curves nearly coincide and approach their common limit of 4/34/3, whereas the Pareto curve converges to the higher limit of 8/38/3. The empirical results thus agree with the asymptotic characterization in Theorem 2. Summary. Overall, the synthetic experiments confirm that larger optimal sets can be easier to identify, the benefit of vector feedback depends on the preference order, and multiple objectives can accelerate identification; moreover, the normalized stopping time of OATS approaches the characteristic time. Appendix A complements these synthetic results with implementation details, HELM-derived Gaussian instances, allocation baselines against uniform sampling and Oracle-Track, and additional robustness and scaling checks. 8 Conclusion and Future Work In this paper, we studied when multiple objectives make fixed-confidence identification easier rather than harder. By casting different preference orders in a common characteristic-time framework, we disentangled the effects of the preference relation, the feasible model class, and the feedback model on identification complexity. Our results show that identification difficulty is governed by the geometry of answer-changing alternatives rather than by the number of objectives or the size of the optimal set alone. In particular, Pareto and lexicographic identification admit no universal hardness ordering, the benefit of vector feedback ranges from no gain to an M-fold improvement, and multi-objective identification can be strictly easier than the best corresponding single-objective problem. We further proposed OATS, which asymptotically matches the lower bound and thereby shows that these gains are achievable. Future directions include extending the analysis beyond Gaussian observations to more general reward and feedback models, such as heavy-tailed noise or partially observed objectives, and developing scalable approximations of the optimal allocation for problems with many arms or objectives. Appendix Appendix A Experimental Details and Additional Results Implementation and numerical checks. We implement OATS following Algorithm 1, including the empirical answer, the stopping statistic, the forced-exploration mixture, and the cumulative-deficit tracking rule. For two-arm experiments under vector feedback, Lemma 1 and its proof reduce the closest-alternative problem to (18), which yields the balanced allocation w=(1/2,1/2)w=(1/2,1/2); the corresponding Pareto, linear, and lexicographic distances are derived in Proposition 4 and its proof. For coordinate feedback, we use the information formulas and optimal allocations derived in the proof of Proposition 2. For linear identification with general K, we project each mean vector onto v/‖v‖2v/\|v\|_2, which reduces the allocation problem to scalar Gaussian best-arm identification. For a candidate singleton answer A=iAA=\i_A\, let cj=(v⊤(μiA−μj))2/(2‖v‖22)c_j=(v ( _i_A- _j))^2/(2\|v\|_2^2) for j≠iAj≠ i_A, so that gA(,w)=minj≠iAcjwiAwjwiA+wj.g_A( μ,w)= _j≠ i_Ac_j w_i_Aw_jw_i_A+w_j. The maximizing weights satisfy wj=wiAλ/(cj−λ)w_j=w_i_Aλ/(c_j-λ) for j≠iAj≠ i_A, where λ∈(0,minj≠iAcj)λ∈(0, _j≠ i_Ac_j) is the unique solution of ∑j≠iA(λ/(cj−λ))2=1 _j≠ i_A(λ/(c_j-λ))^2=1, and wiAw_i_A is then determined by the normalization ∑kwk=1 _kw_k=1. Since the left-hand side is strictly increasing in λ, we solve this equation by bisection on (0,minj≠iAcj)(0, _j≠ i_Ac_j) (Boyd and Vandenberghe, 2004, Section 4.2.5); after 45 iterations, the bracketing interval has width at most 2−45minj≠iAcj2^-45 _j≠ i_Ac_j. We cross-check the resulting allocation and information value against a constrained epigraph formulation solved by sequential quadratic programming (Nocedal and Wright, 2006, Chapter 18), and the two solutions agree to seven decimal places on all test instances. We further verify numerically the two-arm distance formulas, the scalar-acceleration gains, the vector- and coordinate-feedback endpoints, and the predicted scaling laws, and we confirm that instances outside the common-ranking model are correctly rejected. Every simulated trial stopped before reaching the prescribed sample cap, so all reported stopping times are finite. Seeds, intervals, and baselines. For reproducibility, each experimental condition is assigned a fixed base seed, from which independent per-trial seeds are derived. We report 95% confidence intervals for mean stopping times as the sample mean ±1.96± 1.96 standard errors, intervals for ratios of mean stopping times via the delta method for independent samples, and intervals for error rates via the exact two-sided Clopper–Pearson method. The three allocation rules (OATS, Uniform, and Oracle-Track) differ only in their target allocations; they share the same observations, candidate answer, evidence statistic, and stopping threshold. Oracle-Track computes its target allocation from the true mean matrix; it is therefore not implementable in practice and serves only as a reference. In the two-arm vector-feedback setting, all three rules target the same allocation (1/2,1/2)(1/2,1/2), so any observed differences among them are due solely to Monte Carlo variability. Stopping threshold and coordinate-feedback ablation. All simulations stop as soon as ZtZ_t exceeds the threshold β(t,δ)=D2+Dlog(2(t+1)Kexp+2/δ)+log(2(t+1)Kexp+2/δ),β(t,δ)= D2+ D \! (2(t+1)^K_ exp+2/δ )+ \! (2(t+1)^K_ exp+2/δ ), where KexpK_ exp is the number of selectable experiments and D is the total dimension of their mean parameters. The values dictated by our proofs are (Kexp,D)=(K,KM)(K_ exp,D)=(K,KM) for vector feedback and (KM,KM)(KM,KM) for coordinate feedback, and we use them throughout, with one exception. In Figure 1(b), we also set Kexp=K_ exp=K for coordinate feedback, so that both feedback models use the same threshold and the comparison isolates the effect of the feedback model itself. A.1 HELM-Derived Model Evaluation Data and Gaussian construction. We use the publicly released GPT-4 evaluator ratings from CRFM HELM Instruct v1.0.0 (Zhang et al., 2024). In the HELM-derived Gaussian instances, each arm corresponds to a language model and each reward vector contains M=5M=5 objectives. Pairwise comparisons use K=2K=2 arms, and the linear experiments use all K=4K=4 models. HELM groups prompts into evaluation scenarios, each corresponding to a fixed prompt source or task family. For each scenario s, model i, and objective m, we let μ^i,m(s) μ_i,m^(s) denote the average released rating on objective m over the prompts shared by all four models in that scenario, and we collect these five averages into the mean vector μ^i(s)∈ℝ5 μ_i^(s) ^5. We also construct a pooled instance by averaging each model’s ratings over all 678 prompts retained across the seven scenarios. To place these means on the scale of the unit-covariance Gaussian model assumed in our theory, we compute all six model-pair Euclidean gaps within each of the seven scenarios and within the pooled instance, giving 48 gaps in total. Let dmedd_ med denote the median of the nonzero gaps. For the released ratings, dmed=medians,i<j:‖μ^i(s)−μ^j(s)‖2>0∥μ^i(s)−μ^j(s)∥2≈0.7561.d_ med=median_s,\,i<j:\,\| μ_i^(s)- μ_j^(s)\|_2>0\| μ_i^(s)- μ_j^(s)\|_2≈ 0.7561. We use the single global multiplier μ~i(s)=γμ^i(s),γ=dmed−1≈1.323, μ_i^(s)=γ\, μ_i^(s), γ=d_ med^-1≈ 1.323, so that the median model-pair separation is one after rescaling. This provides a representative signal scale relative to the identity-covariance Gaussian noise, while the median is less sensitive than the mean to unusually large or small model gaps. The simulations use the unrounded data-derived value of γ. We then generate fresh observations Xi,t∼(μ~i(s),I5)X_i,t ( μ_i^(s),I_5). Because γ>0γ>0 is applied uniformly to every model and objective, it preserves all Pareto, linear, and lexicographic comparisons; it changes only the absolute signal-to-noise ratio, and hence the difficulty of the Gaussian instances. Across the seven scenarios and the pooled instance, the six model pairs yield 48 two-arm instances with M=5M=5. Figure 2(a) shows the empirical distribution of the theoretical gain over the pairs to which each notion applies, namely Pareto, linear, and common-ranking lexicographic pairs. Most Pareto and linear gains fall below one, whereas the lexicographic distribution is shifted to the right. The large accelerations in our synthetic examples are therefore not typical of HELM mean gaps. Real model pairs rarely exhibit the balanced, mixed-sign gap structure that favors Pareto identification, while common-ranking lexicographic pairs can still aggregate evidence across objectives. Figure 2(b) examines whether the characteristic time predicts stopping times on HELM-derived instances. We fix δ=0.05δ=0.05 and consider the eligible two-arm Pareto instances and the four-arm linear instances. Observed stopping times increase with T⪯()log(1/δ)T_ ( μ) (1/δ), indicating that T⪯()T_ ( μ) remains a reliable indicator of relative instance difficulty. The points lie well above the y=xy=x reference line because, at this practical confidence level, the finite-confidence threshold is conservative and its lower-order terms are not negligible. Figure 2: HELM-derived Gaussian instances. (a) Empirical CDF of the theoretical gain across within-scenario model pairs; a gain above 11 indicates a multi-objective speedup over the best scalar benchmark. (b) Observed stopping time versus T⪯()log(1/δ)T_ ( μ) (1/δ) for eligible Pareto and linear instances, showing that T⪯()T_ ( μ) captures instance difficulty on HELM-derived geometries. Allocation baselines. We compare three allocation rules on a four-arm linear HELM instance. OATS estimates the answer and tracks the allocation returned by Eq. (15). Uniform samples all arms equally with the same stopping rule. Oracle-Track, an unattainable reference, computes the optimal allocation from the true mean matrix with the same observations and stopping rule. Table 1: A four-arm HELM-derived linear instance (Best ChatGPT Prompts scenario, δ=0.05δ=0.05). All methods share the same evidence statistic and stopping threshold. We report the mean stopping time, its 95% confidence interval, and the number of incorrect answers over 500 trials. Oracle-Track uses the true mean matrix and is not implementable. Allocation Mean τ 95% CI Errors OATS 61,797 61,797 [61,119,62,474][61,119,62,474] 0/5000/500 Uniform 87,60087,600 [86,663,88,538][86,663,88,538] 0/5000/500 Oracle-Track 61,93861,938 [61,289,62,588][61,289,62,588] 0/5000/500 As shown in Table 1, OATS reduces the mean stopping time by about 29.5%29.5\% relative to uniform allocation. Its performance is statistically indistinguishable from Oracle-Track, as the two 95% confidence intervals overlap. All three methods return the correct answer in every trial. A.2 Additional Synthetic Experiments This subsection reports two additional sets of synthetic experiments. The first varies the gap size, the scalarization weights, and the balance of Pareto coordinates. The second extends linear identification to more than two arms. Unless otherwise stated, all settings follow those of the main experiments. Table 2: Additional two-arm synthetic checks (δ=0.05δ=0.05, 500 repetitions). Check Setting T⪯()T_ ( μ) Mean τ Gap scaling Δ=0.5 =0.5 10.66710.667 631.2631.2 Gap scaling Δ=1 =1 2.6672.667 133.4133.4 Gap scaling Δ=2 =2 0.6670.667 28.328.3 Unequal linear weights M=4M=4 2.4002.400 94.594.5 Unequal linear weights M=8M=8 1.2591.259 58.358.3 Unequal linear weights M=12M=12 0.8550.855 45.345.3 Pareto imbalance p=1p=1 8.0008.000 447.1447.1 Pareto imbalance p=2p=2 4.0004.000 208.5208.5 Pareto imbalance p=3p=3 2.6672.667 131.0131.0 Pareto imbalance p=4p=4 2.0002.000 106.7106.7 Table 2 confirms that empirical stopping times respond to the instance geometry in the same direction as the characteristic time. First, each doubling of the gap scale Δ divides T⪯()T_ ( μ) by four, consistent with its inverse-square dependence on the gap. The mean stopping time decreases by a similar factor of about 4.74.7, with the difference attributable to lower-order terms in the threshold. Second, with unequal linear weights, increasing the number of objectives enlarges the projected gap and hence reduces both the characteristic time and the stopping time. Third, for Pareto identification with M=8M=8 objectives split into sign groups of sizes p and 8−p8-p, making the two groups more balanced increases the distance to the closest alternative. As a result, T⪯()T_ ( μ) scales as 1/minp,8−p1/ \p,8-p\ and the stopping time decreases accordingly. Table 3: Linear identification with larger K (δ=0.05δ=0.05, 500 repetitions). The last three columns report empirical mean stopping times. Oracle-Track uses the true instance and is not implementable. K M T⪯()T_ ( μ) OATS Uniform Oracle-Track 55 33 3.5683.568 302302 397397 312312 55 55 3.5683.568 354354 470470 367367 55 88 3.5683.568 420420 561561 438438 1010 33 4.7654.765 792792 15861586 813813 1010 55 4.7654.765 933933 18761876 958958 1010 88 4.7654.765 11181118 22502250 11271127 2020 33 5.7925.792 19411941 67266726 19671967 2020 55 5.7925.792 22832283 78017801 22982298 2020 88 5.7925.792 27122712 92879287 27362736 Table 3 extends linear identification beyond two arms. For K∈5,10,20K∈\5,10,20\ and M∈3,5,8M∈\3,5,8\, we generate instances with a unique best arm after projection and a fixed projected gap between the best arm and its closest competitor, which avoids near-ties. This comparison isolates the value of adaptive allocation. Uniform uses the same stopping rule but samples all arms equally, whereas Oracle-Track tracks the true optimal allocation and is not implementable. For fixed K, T⪯()T_ ( μ) does not depend on M because the projected gaps are held fixed. The increase in stopping time with M instead comes from the threshold, whose dimension term D=KMD=KM grows with M. OATS performs on par with Oracle-Track in every setting and is faster than uniform allocation. Its advantage grows with the number of arms, from roughly 1.3×1.3× at K=5K=5 to 2.0×2.0× at K=10K=10 and about 3.4×3.4× at K=20K=20. Appendix B Proof of Theorem 1 Proof. Fix ∈Θ μ∈ . The claim is trivial if [τδ]=∞E_ μ[ _δ]=∞, so assume that this expectation is finite. For any ∈Alt⪯() ν∈ _ ( μ), consider the event E=A^δ=A⪯().E=\ A_δ=A_ ( μ)\. Since the algorithm is δ-correct on the entire model class and A⪯()≠A⪯()A_ ( ν)≠ A_ ( μ), ℙ(E)≥1−δ,ℙ(E)≤δ.P_ μ(E)≥ 1-δ, _ ν(E)≤δ. Applying the change-of-measure inequality (Kaufmann et al., 2016, Lemma 1) to the stopped history gives ∑i=1K[Ni(τδ)]‖μi−νi‖222≥kl(ℙ(E),ℙ(E))≥kl(1−δ,δ). _i=1^KE_ μ[N_i( _δ)] \| _i- _i\|_2^22≥ (P_ μ(E),P_ ν(E) )≥ (1-δ,δ). (17) For completeness, the first inequality follows from the data-processing inequality applied to the indicator of E in the stopped history. The relative entropy of that history equals the left-hand side, because the sampling rule is the same under both instances and each observation from arm i contributes the Gaussian divergence ‖μi−νi‖22/2\| _i- _i\|_2^2/2. This identity is justified by first stopping at τδ∧n _δ n and then using the integrability of the stopped Gaussian log-likelihood increments when [τδ]<∞E_ μ[ _δ]<∞. The second inequality uses the monotonicity of the binary relative entropy kl(p,q) (p,q) for p≥1−δ>δ≥qp≥ 1-δ>δ≥ q. Define the expected sampling proportions as w¯i=[Ni(τδ)][τδ]. w_i= E_ μ[N_i( _δ)]E_ μ[ _δ]. The denominator is positive by Eq. (17), and ∑iNi(τδ)=τδ _iN_i( _δ)= _δ implies w¯∈ΔK w∈ _K. Taking the infimum of Eq. (17) over ∈Alt⪯() ν∈ _ ( μ) yields kl(1−δ,δ) (1-δ,δ) ≤[τδ]inf∈Alt⪯()ℐ(,,w¯) _ μ[ _δ] _ ν∈ _ ( μ)I( μ, ν; w) ≤[τδ]ℐ⪯∗(). _ μ[ _δ]\,I_ ^*( μ). Using T⪯()=1/ℐ⪯∗()T_ ( μ)=1/I_ ^*( μ) proves Eq. (5). Finally, kl(1−δ,δ)=(1−2δ)log1−δ,kl(1−δ,δ)log(1/δ)⟶1, (1-δ,δ)=(1-2δ) 1-δ, (1-δ,δ) (1/δ) 1, which proves the asymptotic lower bound. ∎ Appendix C Proof of Lemma 1 For a feasible-difference set ⊆ℝMD ^M, write Θ()=(μ1,μ2)∈ℝ2×M:μ1−μ2∈. (D)=\( _1, _2) ^2× M: _1- _2 \. The assumption of the lemma that the model depends only on the mean difference means precisely that Θ=Θ() = (D); in particular, the common location of the two means is unrestricted. Proof. Fix an allocation (α,1−α)∈Δ2(α,1-α)∈ _2 and an alternative difference z∈Alt⪯(d)z∈ _ (d). Since the model Θ() (D) leaves the common location of the means unrestricted, every pair with difference z is feasible. Writing a=μ1−ν1a= _1- _1 and b=μ2−ν2b= _2- _2, the constraint is a−b=d−za-b=d-z. The identity α‖a‖22+(1−α)‖b‖22=α(1−α)‖a−b‖22+‖αa+(1−α)b‖22α\|a\|_2^2+(1-α)\|b\|_2^2=α(1-α)\|a-b\|_2^2+\|α a+(1-α)b\|_2^2 therefore gives infν1−ν2=zℐ(,,(α,1−α))=α(1−α)2‖d−z‖22. _ _1- _2=zI( μ, ν;(α,1-α))= α(1-α)2\|d-z\|_2^2. (18) The infimum is attained at a=(1−α)(d−z)a=(1-α)(d-z) and b=−α(d−z)b=-α(d-z), including when α∈0,1α∈\0,1\. Consequently, ℐ⪯∗(d)=maxα∈[0,1]α(1−α)2dist2(d,Alt⪯(d))=18dist2(d,Alt⪯(d)).I_ ^*(d)= _α∈[0,1] α(1-α)2 ^2(d, _ (d))= 18 ^2(d, _ (d)). Taking reciprocals proves Eq. (6). ∎ Appendix D Auxiliary Results for the Two-Arm Comparisons We now specify the feasible-difference sets used in the two-arm comparisons. Define free _free =(ℝ∖0)M, =(R \0\)^M, (19) v _v =z∈free:v⊤z≠0, =\z _free:v z≠ 0\, cmp _cmp =ℝ++M∪(−ℝ++M). =R_++^M∪(-R_++^M). The unrestricted Pareto and lexicographic comparisons use Θ(free) (D_free), and linear scalarization uses Θ(v) (D_v). Excluding ties ensures local stability and does not change the distances to the decision boundaries computed below. In the common-ranking comparison in Proposition 3, the feasible-difference set D is cmpD_cmp and the model is Θ(cmp) (D_cmp). This restriction is known to the learner and applies to the entire model, i.e., to both the true instance and every feasible alternative in Eq. (3). Proposition 4 (Two-arm characteristic times). Let d∈freed _free, and define P(d)=m:dm>0,N(d)=m:dm<0,P(d)=\m:d_m>0\, N(d)=\m:d_m<0\, S+(d)=∑m∈P(d)dm2,S−(d)=∑m∈N(d)dm2.S_+(d)= _m∈ P(d)d_m^2, S_-(d)= _m∈ N(d)d_m^2. Under vector feedback, Pareto identification on Θ(free) (D_free) has characteristic time TP(d)=8minm∈[M]dm2,P(d)=∅ or N(d)=∅,8minS+(d),S−(d),P(d)≠∅ and N(d)≠∅.T_P(d)= cases 8 _m∈[M]d_m^2,&P(d)= or N(d)= ,\\[5.69054pt] 8 \S_+(d),S_-(d)\,&P(d)≠ and N(d)≠ . cases (20) For v∈ℝ+M∖0v _+^M \0\ and d∈vd _v, linear scalarization on Θ(v) (D_v) satisfies Tv(d)=8‖v‖22(v⊤d)2.T_v(d)= 8\|v\|_2^2(v d)^2. (21) For lexicographic identification, distinguish the two model classes by writing Tlexfree(d)=8d12(d∈free),Tlexcmp(d)=8‖d‖22(d∈cmp).T_lex^free(d)= 8d_1^2 (d _free), T_lex^cmp(d)= 8\|d\|_2^2 (d _cmp). (22) The superscripts in Eq. (22) indicate the model class, not the feedback model. Proof. By Lemma 1, it suffices to compute the squared distance from d to the corresponding set of feasible answer-changing differences. We use dist(d,S)=dist(d,S¯) (d,S)= (d, S), so boundary points need not belong to the model to determine this infimum. Pareto preferences. Suppose first that d∈ℝ++Md _++^M. The prescribed answer is 1\1\. Any alternative in freeD_free must have a negative coordinate, so its squared distance from d is at least minmdm2 _md_m^2. Conversely, choose j∈argminmdm2j∈ _md_m^2 and replace djd_j by −η-η, leaving the other coordinates unchanged. This yields a feasible answer-changing difference for every η>0η>0, and letting η↓0η 0 shows that the squared distance equals minmdm2 _md_m^2. The case d∈−ℝ++Md∈-R_++^M is symmetric. If P(d)P(d) and N(d)N(d) are both nonempty, neither arm dominates the other, and the answer is 1,2\1,2\. An alternative changes this answer if and only if one arm dominates the other. Since no coordinate is zero in freeD_free, this is equivalent to all coordinate differences having the same sign. Hence AltP(d)¯=ℝ+M∪(−ℝ+M). _P(d)=R_+^M∪(-R_+^M). Coordinatewise projection gives dist2(d,ℝ+M)=S−(d),dist2(d,−ℝ+M)=S+(d). ^2(d,R_+^M)=S_-(d), ^2(d,-R_+^M)=S_+(d). Both projections can be approached by strictly positive or strictly negative differences, respectively. Therefore, the squared distance to the alternative set is minS+(d),S−(d) \S_+(d),S_-(d)\, which proves Eq. (20). Linear scalarization. Write a=v⊤d≠0a=v d≠ 0. The closure of the answer-changing differences is the halfspace Ha=z∈ℝM:av⊤z≤0.H_a=\z ^M:a\,v z≤ 0\. Indeed, differences whose scalarized gap has the opposite sign are answer-changing, and excluding coordinate ties does not affect the closure of this open halfspace. For any z∈Haz∈ H_a, Cauchy–Schwarz implies ‖d−z‖2≥|v⊤(d−z)|‖v‖2≥|a|‖v‖2.\|d-z\|_2≥ |v (d-z)|\|v\|_2≥ |a|\|v\|_2. The projection z∗=d−a‖v‖22vz^*=d- a\|v\|_2^2v attains this distance to HaH_a. To approach z∗z^* by feasible alternatives, take z∗−ηsign(a)vz^*- (a)v with η>0η>0 and, if necessary, apply an additional perturbation of norm o(η)o(η) to avoid coordinate ties. Such perturbations preserve the strictly opposite sign of the scalarized gap. Thus, dist2(d,Altv(d))=(v⊤d)2‖v‖22, ^2(d, _v(d))= (v d)^2\|v\|_2^2, which proves Eq. (21). Unrestricted lexicographic preferences. Suppose d1>0d_1>0. Every answer-changing difference in freeD_free has a negative first coordinate, so its squared distance from d is at least d12d_1^2. Replacing only d1d_1 by −η-η gives feasible alternatives approaching this lower bound as η↓0η 0. Exchanging the arms covers d1<0d_1<0 and proves the first identity in Eq. (22). Lexicographic preferences under common ranking. Suppose d∈ℝ++Md _++^M. The answer is 1\1\, and the feasible answer-changing differences are exactly −ℝ++M-R_++^M. Consequently, infz∈−ℝ++M‖d−z‖22=∑m=1Mdm2. _z∈-R_++^M\|d-z\|_2^2= _m=1^Md_m^2. For the lower bound, each summand (dm−zm)2(d_m-z_m)^2 is at least dm2d_m^2. For the upper bound, set z=−ηMz=- 1_M and let η↓0η 0. The case d∈−ℝ++Md∈-R_++^M is symmetric. The second identity in Eq. (22) now follows from Lemma 1. ∎ The role of the feasible model. Both lexicographic identities can be evaluated at the same gap vector with strictly same-sign coordinates, but they refer to different sets of feasible alternatives. Merely observing that the true difference has a common sign does not justify Tlexcmp(d)T_lex^cmp(d): the learner must know that all feasible instances obey the common-ranking restriction. This distinction explains why the unrestricted lexicographic examples in Propositions 1 and 2 are consistent with the common-ranking acceleration in Proposition 3. Appendix E Proof of Proposition 1 Proof. Both orders are evaluated on Θ(free) (D_free). For d=(ΔM/2,−ΔM/2)d=( 1_M/2,- 1_M/2), the Pareto answer is 1,2\1,2\, whereas the lexicographic answer is 1\1\. Since S+(d)=S−(d)=M2Δ2,d12=Δ2,S_+(d)=S_-(d)= M2 ^2, d_1^2= ^2, Proposition 4 gives TP(d)=16MΔ2,Tlex(d)=8Δ2,Tlex(d)TP(d)=M2.T_P(d)= 16M ^2, T_lex(d)= 8 ^2, T_lex(d)T_P(d)= M2. This proves Eq. (7). For d=(1,…,1,ϵ)d=(1,…,1,ε) with 0<ϵ<10<ε<1, both orders identify arm 11. Now minmdm2=ϵ2 _md_m^2=ε^2 and d12=1d_1^2=1, so the same proposition yields TP(d)=8ϵ2,Tlex(d)=8,Tlex(d)TP(d)=ϵ2.T_P(d)= 8ε^2, T_lex(d)=8, T_lex(d)T_P(d)=ε^2. This proves Eq. (8). ∎ Appendix F Proof of Proposition 2 Proof. For coordinate feedback, write q=(qi,m)∈ΔKMq=(q_i,m)∈ _KM for the sampling proportions and define ℐ⪯∗,co()=supq∈ΔKMinf∈Alt⪯()12∑i=1K∑m=1Mqi,m(μi,m−νi,m)2.I_ ^*,co( μ)= _q∈ _KM _ ν∈ _ ( μ) 12 _i=1^K _m=1^Mq_i,m( _i,m- _i,m)^2. (23) Its reciprocal is T⪯co()T_ ^co( μ). General feedback bounds. For any q∈ΔKMq∈ _KM, define wi=∑mqi,mw_i= _mq_i,m. Then w∈ΔKw∈ _K and, against every feasible alternative, 12∑i,mwi(μi,m−νi,m)2≥12∑i,mqi,m(μi,m−νi,m)2. 12 _i,mw_i( _i,m- _i,m)^2≥ 12 _i,mq_i,m( _i,m- _i,m)^2. Taking infima over alternatives and optimizing over allocations shows that the characteristic information under vector feedback is at least that under coordinate feedback. Conversely, any vector allocation w induces the coordinate allocation qi,m=wi/Mq_i,m=w_i/M, which collects exactly a 1/M1/M fraction of its information against every alternative. Thus, 1Mℐ⪯∗()≤ℐ⪯∗,co()≤ℐ⪯∗(). 1MI_ ^*( μ) _ ^*,co( μ) _ ^*( μ). Local stability and a nonempty alternative set ensure that the vector-feedback characteristic information is positive and finite, so taking reciprocals proves Eq. (9). We next verify the two endpoint examples on Θ(free) (D_free). Information for one coordinate comparison. For two arms, let pm=q1,m+q2,mp_m=q_1,m+q_2,m. When dm>0d_m>0, the minimal information needed to reverse the comparison on coordinate m is cm(q)=infa≤bq1,m2(μ1,m−a)2+q2,m2(μ2,m−b)2=q1,mq2,m2pmdm2,c_m(q)= _a≤ b \ q_1,m2( _1,m-a)^2+ q_2,m2( _2,m-b)^2 \= q_1,mq_2,m2p_md_m^2, where the right-hand side is defined as zero if pm=0p_m=0. If both weights are positive, the minimizing values coincide at (q1,mμ1,m+q2,mμ2,m)/pm(q_1,m _1,m+q_2,m _2,m)/p_m. If a weight vanishes, the corresponding arm mean can be moved at no cost, which gives the same formula. Strict reversals approach this infimum. Since q1,mq2,m≤pm2/4q_1,mq_2,m≤ p_m^2/4, cm(q)≤pmdm28,c_m(q)≤ p_md_m^28, (24) with equality at q1,m=q2,m=pm/2q_1,m=q_2,m=p_m/2. Balancing the arms within each coordinate achieves these equalities simultaneously without changing p. Pareto identification. At d=ΔMd= 1_M, the answer is 1\1\. Every alternative reverses at least one coordinate (in the closure), and reversing a single coordinate suffices to change the answer. Hence, for fixed q, the information infimum is minmcm(q) _mc_m(q). Using Eq. (24), ℐP∗,co(d)=Δ28maxp∈ΔMminmpm=Δ28M.I_P^*,co(d)= ^28 _p∈ _M _mp_m= ^28M. The last equality follows from minmpm≤1/M _mp_m≤ 1/M, with equality at the uniform allocation. Thus, TPco(d)=8M/Δ2T_P^co(d)=8M/ ^2. Lexicographic identification. An answer-changing difference must have z1≤0z_1≤ 0, and a strict reversal of the first coordinate alone is feasible. The information infimum is therefore c1(q)c_1(q), giving ℐlex∗,co(d)=Δ28maxp∈ΔMp1=Δ28.I_lex^*,co(d)= ^28 _p∈ _Mp_1= ^28. This value is attained by assigning mass 1/21/2 to each of the two first-coordinate experiments. Hence, Tlexco(d)=8/Δ2T_lex^co(d)=8/ ^2. Vector feedback and endpoint attainment. At d=ΔMd= 1_M, Proposition 4 gives TP(d)=Tlex(d)=8/Δ2T_P(d)=T_lex(d)=8/ ^2 on Θ(free) (D_free). Combining these identities with the coordinate-feedback characteristic times proves Eq. (10) and shows that both bounds in Eq. (9) are attained. ∎ Appendix G Proof of Proposition 3 Proof. We use the model-specific characteristic times from Proposition 4. In particular, the third line of Eq. (11) uses the common-ranking model Θ(cmp) (D_cmp) specified in Eq. (19). The scalar benchmark is Tbest(d)=8Δmax2(d).T_best(d)= 8 _ ^2(d). Together with Lemma 1, this gives the identity ⪯(d)=dist2(d,Alt⪯(d))Δmax2(d), Gain_ (d)= ^2(d, _ (d)) _ ^2(d), where the alternative set is taken in the relevant model. Pareto preferences. The condition minS+(d),S−(d)>Δmax2(d) \S_+(d),S_-(d)\> _ ^2(d) implies that both P(d)P(d) and N(d)N(d) are nonempty. Equation (20) therefore yields P(d)=8/Δmax2(d)8/minS+(d),S−(d)=minS+(d),S−(d)Δmax2(d)>1. Gain_P(d)= 8/ _ ^2(d)8/ \S_+(d),S_-(d)\= \S_+(d),S_-(d)\ _ ^2(d)>1. This proves the first line of Eq. (11). For incomparable arms, dm2≤Δmax2(d)d_m^2≤ _ ^2(d) gives P(d)≤min|P(d)|,|N(d)|≤⌊M2⌋. Gain_P(d)≤ \|P(d)|,|N(d)|\≤ M2 . The upper bound is attained by d=Δ(⌊M/2⌋,−⌈M/2⌉)d= (1_ M/2 ,-1_ M/2 ) for any Δ>0 >0 and M≥2M≥ 2. For comparable arms, Eq. (20) instead gives P(d)=minmdm2Δmax2(d)≤1. Gain_P(d)= _md_m^2 _ ^2(d)≤ 1. Hence, the condition in the proposition characterizes strict Pareto acceleration on the unrestricted comparison model, and such acceleration requires M≥4M≥ 4. Linear scalarization. The condition |v⊤d|>‖v‖2Δmax(d)|v d|>\|v\|_2 _ (d) implies v⊤d≠0v d≠ 0. Equation (21) gives v(d)=8/Δmax2(d)8‖v‖22/(v⊤d)2=(v⊤d)2‖v‖22Δmax2(d)>1, Gain_v(d)= 8/ _ ^2(d)8\|v\|_2^2/(v d)^2= (v d)^2\|v\|_2^2 _ ^2(d)>1, proving the second line of Eq. (11). Moreover, since v≥0v≥ 0, |v⊤d|≤‖v‖1Δmax(d),v(d)≤‖v‖12‖v‖22≤M.|v d|≤\|v\|_1 _ (d), Gain_v(d)≤ \|v\|_1^2\|v\|_2^2≤ M. For a fixed v, the first bound is attained at d=ΔMd= 1_M; if, in addition, the weights are equal and positive, the gain equals M. Thus, the maximum gain for a fixed weight vector is ‖v‖12/‖v‖22\|v\|_1^2/\|v\|_2^2, and the global factor-M bound is attainable. Lexicographic preferences under common ranking. For d∈cmpd _cmp, the second identity in Eq. (22) yields lex(d)=8/Δmax2(d)8/‖d‖22=‖d‖22Δmax2(d). Gain_lex(d)= 8/ _ ^2(d)8/\|d\|_2^2= \|d\|_2^2 _ ^2(d). All coordinates are nonzero, so for M≥2M≥ 2, 1<‖d‖22Δmax2(d)≤M.1< \|d\|_2^2 _ ^2(d)≤ M. The upper bound is attained when all coordinate gaps have the same magnitude. This proves the third line of Eq. (11) and the stated factor-M gain. By contrast, the first identity in Eq. (22) gives lex(d)=d12/Δmax2(d)≤1 Gain_lex(d)=d_1^2/ _ ^2(d)≤ 1 on the unrestricted model. Thus, the lexicographic acceleration is a consequence of the common-ranking constraint on feasible alternatives, not merely of the signs of the true gaps. Finally, the common-ranking restriction does not change the single-coordinate benchmark: every two-arm scalar mean pair with a nonzero gap can be extended to an instance in Θ(cmp) (D_cmp). Hence, for each objective, the induced scalar model remains unrestricted apart from the exclusion of ties. The minimum in Tbest(d)T_best(d) is an instance-wise oracle benchmark; we do not claim that an unknown easiest coordinate can be selected without additional sampling. ∎ Appendix H Proof of Theorem 2 Proof. Fix ∈Θ μ∈ , and write A∗=A⪯()A^*=A_ ( μ), g=gA∗g=g_A^*, and Γ=ℐ⪯∗() =I_ ^*( μ). We analyze the sampling process continued indefinitely, ignoring the stopping rule; for each confidence level, the actual algorithm coincides with this process up to its first threshold crossing. We use the exact allocation maximizer in Algorithm 1 and resolve all ties by fixed measurable rules that do not depend on δ, so that the confidence level enters only through the stopping threshold. Local stability is used in the metric form of Eq. (2). Step 1: continuity and positivity of the information. Let S⊆ℝK×MS ^K× M be a fixed nonempty set, and define h(,w)=inf∈S12∑iwi‖xi−νi‖22,∈ℝK×M,w∈ΔK.h( x,w)= _ ν∈ S 12 _iw_i\|x_i- _i\|_2^2, x ^K× M, w∈ _K. This function is nonnegative and finite, since it is bounded above by the cost of any fixed 0∈S ν^0∈ S. It is concave in w, as an infimum of linear functions. For fixed x, it is upper semicontinuous in w, as an infimum of continuous linear functions. To prove lower semicontinuity, let w(n)→w^(n)→ w and set ηn=maxi:wi>0(1−wi(n)wi)+. _n= _i:w_i>0 (1- w_i^(n)w_i )_+. Then ηn→0 _n→ 0, and wi(n)≥(1−ηn)wiw_i^(n)≥(1- _n)w_i for all i, including those with wi=0w_i=0. Since each per-arm cost is nonnegative, h(,w(n))≥(1−ηn)h(,w).h( x,w^(n))≥(1- _n)h( x,w). Thus, h(,⋅)h( x,·) is continuous on the closed simplex. Moreover, the weighted seminorm ‖z‖w=(∑iwi‖zi‖22)1/2\|z\|_w=( _iw_i\|z_i\|_2^2)^1/2 and the triangle inequality give |2h(,w)−2h(,w)|≤‖−‖w≤‖−‖F. | 2h( x,w)- 2h( y,w) |≤\| x- y\|_w≤\| x- y\|_F. Combining this uniform bound with continuity in w yields joint continuity in (,w)( x,w). Note that no closedness, convexity, or boundedness of S is required. For any A∈A , take S=Θ∖ΘAS= _A and write the answer-specific information as gA(,w)=inf∈Θ∖ΘA12∑iwi‖xi−νi‖22.g_A( x,w)= _ ν∈ _A 12 _iw_i\|x_i- _i\|_2^2. At the empirical input =^t x= μ_t, its iith row is xi=μ^i(t)x_i= μ_i(t). The preceding argument establishes the required continuity and concavity of gAg_A, so its maximum over the compact simplex is attained. Each answer-region distance is also continuous in x, so the minimization over the finitely many answers is well defined. Consequently, fixed measurable selectors can be used for both optimization steps. Local stability and the nonempty alternative set give ρ=inf∈Θ∖ΘA∗‖−‖F∈(0,∞).ρ= _ ν∈ _A^*\| μ- ν\|_F∈(0,∞). Evaluating the information at the uniform allocation, and at any fixed alternative 0 ν^0, gives 0<ρ22K≤Γ≤12maxi‖μi−νi0‖22<∞.0< ρ^22K≤ ≤ 12 _i\| _i- _i^0\|_2^2<∞. Step 2: a confidence event valid under adaptive sampling. For each arm i, we represent its observations by an independent infinite sequence of potential observations, and let μ^i[n] μ_i[n] denote the mean of the first n of them. For any deterministic count vector n=(n1,…,nK)n=(n_1,…,n_K) with ni≥1n_i≥ 1, Q(n)=12∑ini‖μ^i[ni]−μi‖22∼12χD2,D=KM.Q(n)= 12 _in_i\| μ_i[n_i]- _i\|_2^2 12 _D^2, D=KM. For 0<λ<10<λ<1, logexpλ(Q(n)−D/2)=D2[−log(1−λ)−λ]≤Dλ24(1−λ). \λ(Q(n)-D/2)\= D2 [- (1-λ)-λ ]≤ Dλ^24(1-λ). Chernoff’s inequality with λ=2x/(D+2x)λ=2 x/( D+2 x) then gives ℙ(Q(n)>D2+Dx+x)≤e−x,x>0.P (Q(n)> D2+ Dx+x )≤ e^-x, x>0. (25) At time t, there are at most (t+1)K(t+1)^K possible count vectors. Applying Eq. (25) with x=log(2(t+1)K+2/δ)x= (2(t+1)^K+2/δ) to each of them, before the adaptive count vector is selected, and taking a union bound over count vectors and times gives ℙ(∃t≥K:12∑iNi(t)∥μ^i(t)−μi∥22>β(t,δ)) _ μ (∃ t≥ K: 12 _iN_i(t)\| μ_i(t)- _i\|_2^2>β(t,δ) ) ≤δ2∑t≥K(t+1)−2≤δ. ≤ δ2 _t≥ K(t+1)^-2≤δ. (26) This argument does not require the empirical means to remain Gaussian after conditioning on the adaptively chosen counts. If A^t≠A∗ A_t≠ A^*, the true instance belongs to Θ∖ΘA^t _ A_t, so Zt≤12∑iNi(t)‖μ^i(t)−μi‖22.Z_t≤ 12 _iN_i(t)\| μ_i(t)- _i\|_2^2. Therefore, an incorrect recommendation at a threshold crossing can occur only outside the confidence event in Eq. (26), so the probability of an incorrect stop is at most δ. Almost-sure stopping is established in Step 6. Step 3: bounded tracking discrepancy and forced exploration. Let Si(t)=1+∑s=Kt−1qs,i,bi(t)=Si(t)−Ni(t).S_i(t)=1+ _s=K^t-1q_s,i, b_i(t)=S_i(t)-N_i(t). We have bi(K)=0b_i(K)=0 and ∑ibi(t)=0 _ib_i(t)=0. Before the pull at time t+1t+1, the deficits are bi(t)+qt,ib_i(t)+q_t,i and sum to one, so the selected deficit is at least 1/K1/K before it is reduced by one, while every unselected deficit can only increase. By induction, bi(t)>−1b_i(t)>-1 for all i and t; since the deficits sum to zero, also bi(t)<K−1b_i(t)<K-1. Thus, |Ni(t)−Si(t)|≤K−1,‖N(t)t−S(t)t‖1≤K(K−1)t.|N_i(t)-S_i(t)|≤ K-1, \| N(t)t- S(t)t \|_1≤ K(K-1)t. (27) The exploration mixture satisfies qs,i≥s−1/2/Kq_s,i≥ s^-1/2/K, whence Ni(t)≥1+1K∑s=Kt−1s−1/2−(K−1).N_i(t)≥ 1+ 1K _s=K^t-1s^-1/2-(K-1). (28) Consequently, there exist deterministic constants c0>0c_0>0 and t0≥Kt_0≥ K, depending only on K, such that Ni(t)≥c0tN_i(t)≥ c_0 t for all i and all t≥t0t≥ t_0. Step 4: an integrable time after which the estimates remain accurate. Fix r>0r>0. If ‖^t−‖F>r\| μ_t- μ\|_F>r, then at least one scalar coordinate has error greater than r/KMr/ KM. For a deterministic sample size n, the Gaussian tail bound gives ℙ(|μ^i,m[n]−μi,m|>rKM)≤2exp(−nr22KM).P_ μ (| μ_i,m[n]- _i,m|> r KM )≤ 2 (- nr^22KM ). Using Eq. (28) and a union bound over all possible counts yields constants Cr,cr>0C_r,c_r>0 such that ℙ(‖^t−‖F>r) _ μ(\| μ_t- μ\|_F>r) ≤2KM∑n≥⌈c0t⌉exp(−nr22KM) ≤ 2KM _n≥ c_0 t (- nr^22KM ) ≤Cre−crt,t≥t0. ≤ C_re^-c_r t, t≥ t_0. Let LrL_r be one plus the last integer t≥t0t≥ t_0 at which this error exceeds r, with Lr=t0L_r=t_0 if no such time exists. Then ℙ(Lr>u)≤∑t≥uCre−crt(u≥t0),P_ μ(L_r>u)≤ _t≥ uC_re^-c_r t (u≥ t_0), and [Lr]≤t0+∑t≥t0(t+1)Cre−crt<∞.E_ μ[L_r]≤ t_0+ _t≥ t_0(t+1)C_re^-c_r t<∞. For r<ρ/3r<ρ/3, an estimate within distance r of μ is at distance at most r from ΘA∗ _A^* and at distance at least ρ−r>rρ-r>r from every other answer region. Hence, the exact answer-region fit in Eq. (12) selects A^t=A∗ A_t=A^* for all t≥Lrt≥ L_r. This argument also covers estimates outside Θ . Step 5: information accumulation after an integrable time. Fix ε∈(0,Γ) ∈(0, ). By joint continuity (Step 1) and compactness of the simplex, we can choose r∈(0,ρ/3)r∈(0,ρ/3) such that supw∈ΔK|g(,w)−g(,w)|≤ε8whenever ‖−‖F≤r. _w∈ _K|g( x,w)-g( μ,w)|≤ 8 \| x- μ\|_F≤ r. Choose a deterministic t1≥t0t_1≥ t_0 such that t−1/2Γ≤ε/8t^-1/2 ≤ /8 for all t≥t1t≥ t_1, and let L=maxLr,t1L= \L_r,t_1\. Then [L]<∞E_ μ[L]<∞. For t≥Lt≥ L, the candidate answer is A∗A^*, and the exact allocation rule gives g(,wt) g( μ,w_t) ≥g(^t,wt)−ε8 ≥ g( μ_t,w_t)- 8 =maxw∈ΔKg(^t,w)−ε8 = _w∈ _Kg( μ_t,w)- 8 ≥Γ−ε4. ≥ - 4. Let uK=K/Ku_K=1_K/K. By concavity and nonnegativity, g(,qt)≥(1−t−1/2)g(,wt)+t−1/2g(,uK)≥Γ−3ε8.g( μ,q_t)≥(1-t^-1/2)g( μ,w_t)+t^-1/2g( μ,u_K)≥ - 3 8. Since S(t)/t=(K/t)uK+t−1∑s=Kt−1qsS(t)/t=(K/t)u_K+t^-1 _s=K^t-1q_s, another application of concavity gives g(,S(t)t)≥1t∑s=Lt−1g(,qs)≥(1−Lt)(Γ−3ε8).g ( μ, S(t)t )≥ 1t _s=L^t-1g( μ,q_s)≥ (1- Lt ) ( - 3 8 ). For t≥8ΓL/εt≥ 8 L/ , this is at least Γ−ε/2 - /2. By Eq. (27) and the uniform continuity of g(,⋅)g( μ,·) on the simplex, there exists a deterministic t2≥t0t_2≥ t_0 such that |g(,N(t)t)−g(,S(t)t)|≤ε8(t≥t2). |g ( μ, N(t)t )-g ( μ, S(t)t ) |≤ 8 (t≥ t_2). Define Hε=maxt2,⌈8ΓLε⌉.H_ = \t_2, 8 L \. Then Hε≥LH_ ≥ L, [Hε]<∞E_ μ[H_ ]<∞, and for all t≥Hεt≥ H_ , Ztt=g(^t,N(t)t)≥Γ−ε2−ε8−ε8≥Γ−ε. Z_tt=g ( μ_t, N(t)t )≥ - 2- 8- 8≥ - . (29) The random time HεH_ does not depend on δ. This argument relies on the average information value of the allocations rather than on the convergence of individual maximizers, and therefore does not require a unique optimal allocation. Step 6: finite expectation and the asymptotic upper bound. For fixed δ, the threshold satisfies β(t,δ)/t→0β(t,δ)/t→ 0, so there exists a deterministic bδ≥Kb_δ≥ K such that β(t,δ)<(Γ−ε)tβ(t,δ)<( - )t for every integer t≥bδt≥ b_δ. Equation (29) gives τδ≤maxHε,bδ. _δ≤ \H_ ,b_δ\. This proves that the algorithm stops almost surely and has a finite expected stopping time. Together with Step 2, this establishes δ-correctness. To obtain the leading constant, set ℓδ=log(1/δ) _δ= (1/δ), fix ζ>0ζ>0, and define nδ=⌈(1+ζ)ℓδΓ−ε⌉.n_δ= (1+ζ) _δ - . For fixed K,MK,M, log2(nδ+1)K+2δ=ℓδ+O(logℓδ),β(nδ,δ)=ℓδ+o(ℓδ). 2(n_δ+1)^K+2δ= _δ+O( _δ), β(n_δ,δ)= _δ+o( _δ). Hence, β(nδ,δ)<(Γ−ε)nδβ(n_δ,δ)<( - )n_δ for sufficiently small δ, and this inequality continues to hold for every t≥nδt≥ n_δ. Indeed, extending the threshold to real t≥Kt≥ K, t∂tβ(t,δ) t\, _tβ(t,δ) ≤(K+2)(1+D2log2(t+1)K+2δ), ≤(K+2) (1+ D2 2(t+1)^K+2δ ), β(t,δ) β(t,δ) ≥log2(t+1)K+2δ≥ℓδ. ≥ 2(t+1)^K+2δ≥ _δ. For sufficiently small δ, the second quantity exceeds the first uniformly in t, so β(t,δ)/tβ(t,δ)/t is decreasing in t. Combining this with Eq. (29) gives τδ≤maxHε,nδ,[τδ]≤nδ+[Hε]. _δ≤ \H_ ,n_δ\, _ μ[ _δ]≤ n_δ+E_ μ[H_ ]. It follows that lim supδ↓0[τδ]log(1/δ)≤1+ζΓ−ε. _δ 0 E_ μ[ _δ] (1/δ)≤ 1+ζ - . Letting ζ↓0ζ 0 and then ε↓0 0 yields the upper bound 1/Γ=T⪯()1/ =T_ ( μ). Theorem 1 provides the matching lower bound, which establishes Eq. (16). ∎ References Ararat and Tekin (2023) Ç. Ararat and C. Tekin Vector optimization with stochastic bandit feedback. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, p. 2165–2190. Cited by: §1, §2. Audibert et al. (2010) J. Audibert, S. Bubeck, and R. Munos Best arm identification in multi-armed bandits. In Proceedings of the 23rd Conference on Learning Theory, p. 41–53. Cited by: §1, §2. Auer et al. (2016) P. Auer, C. Chiang, R. Ortner, and M. Drugan Pareto front identification from stochastic bandit feedback. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, p. 939–947. Cited by: §1, §1, §2. Boyd and Vandenberghe (2004) S. Boyd and L. Vandenberghe Convex optimization. Cambridge university press. Cited by: Appendix A. Bubeck et al. (2009) S. Bubeck, R. Munos, and G. Stoltz Pure exploration in multi-armed bandits problems. In Algorithmic Learning Theory, p. 23–37. Cited by: §1, §2. Busa-Fekete et al. (2017) R. Busa-Fekete, B. Szörényi, P. Weng, and S. Mannor Multi-objective bandits: optimizing the generalized Gini index. In Proceedings of the 34th International Conference on Machine Learning, p. 625–634. Cited by: §2. Chang et al. (2024) Y. Chang, X. Wang, J. Wang, Y. Wu, L. Yang, K. Zhu, H. Chen, X. Yi, C. Wang, Y. Wang, W. Ye, Y. Zhang, Y. Chang, P. S. Yu, Q. Yang, and X. Xie A survey on evaluation of large language models. ACM Transactions on Intelligent Systems and Technology 15 (3), p. 1–45. Cited by: §1. Chen et al. (2014) S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen Combinatorial pure exploration of multi-armed bandits. In Advances in Neural Information Processing Systems 27, p. 379–387. Cited by: §2. Cheng et al. (2024) J. Cheng, B. Xue, J. Yi, and Q. Zhang Hierarchize Pareto dominance in multi-objective stochastic linear bandits. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, p. 11489–11497. Cited by: §2. Crépon et al. (2024) E. Crépon, A. Garivier, and W. M. Koolen Sequential learning of the Pareto front for multi-objective bandits. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, p. 3583–3591. Cited by: §2, §6. Das et al. (2025) U. Das, A. Shukla, and D. Basu FraPPE: fast and efficient preference-based pure exploration. In Advances in Neural Information Processing Systems 38, p. 10190–10236. Cited by: §1, §2. Degenne et al. (2019) R. Degenne, W. M. Koolen, and P. Ménard Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems 32, p. 14465–14474. Cited by: §2. Degenne and Koolen (2019) R. Degenne and W. M. Koolen Pure exploration with multiple correct answers. In Advances in Neural Information Processing Systems 32, p. 14564–14573. Cited by: §1, §2, §3, §6, §6. Degenne et al. (2020) R. Degenne, P. Ménard, X. Shang, and M. Valko Gamification of pure exploration for linear bandits. In Proceedings of the 37th International Conference on Machine Learning, p. 2432–2442. Cited by: §1, §2. Drugan and Nowe (2013) M. Drugan and A. Nowe Designing multi-objective multi-armed bandits algorithms: a study. In The 2013 International Joint Conference on Neural Networks, p. 1–8. Cited by: §1, §2. Du et al. (2021) Y. Du, Y. Kuroki, and W. Chen Combinatorial pure exploration with full-bandit or partial linear feedback. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, p. 7262–7270. Cited by: §1. Even-Dar et al. (2006) E. Even-Dar, S. Mannor, and Y. Mansour Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research 7 (39), p. 1079–1105. Cited by: §1, §2. Fiez et al. (2019) T. Fiez, L. Jain, K. G. Jamieson, and L. Ratliff Sequential experimental design for transductive linear bandits. In Advances in Neural Information Processing Systems 32, p. 10666–10676. Cited by: §1, §2. Gabillon et al. (2012) V. Gabillon, M. Ghavamzadeh, and A. Lazaric Best arm identification: a unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems 25, p. 3212–3220. Cited by: §1, §2. Garivier and Kaufmann (2016) A. Garivier and E. Kaufmann Optimal best arm identification with fixed confidence. In Proceedings of the 29th Conference on Learning Theory, p. 998–1027. Cited by: §1, §1, §1, §2, §3, §4, §6, §6. Hüyük and Tekin (2021) A. Hüyük and C. Tekin Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning 110, p. 1233–1266. Cited by: §1. Jamieson et al. (2014) K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck lil’ UCB: an optimal exploration algorithm for multi-armed bandits. In Proceedings of the 27th Conference on Learning Theory, p. 423–439. Cited by: §2. Kalyanakrishnan et al. (2012) S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone PAC subset selection in stochastic multi-armed bandits. In Proceedings of the 29th International Conference on Machine Learning, p. 655–662. Cited by: §2. Karagözlü et al. (2024) E. M. Karagözlü, Y. C. Yıldırım, Ç. Ararat, and C. Tekin Learning the Pareto set under incomplete preferences: pure exploration in vector bandits. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, p. 3070–3078. Cited by: §1, §2. Karnin et al. (2013) Z. Karnin, T. Koren, and O. Somekh Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning, p. 1238–1246. Cited by: §1, §2. Kaufmann et al. (2016) E. Kaufmann, O. Cappé, and A. Garivier On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research 17 (1), p. 1–42. Cited by: Appendix B, §1, §2, §3, §4. Kone et al. (2023) C. Kone, E. Kaufmann, and L. Richert Adaptive algorithms for relaxed pareto set identification. In Advances in Neural Information Processing Systems 36, p. 35190–35201. Cited by: §1, §2. Kone et al. (2024) C. Kone, E. Kaufmann, and L. Richert Bandit Pareto set identification: the fixed-budget setting. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, p. 2548–2556. Cited by: §2. Liang et al. (2023) P. Liang, R. Bommasani, T. Lee, D. Tsipras, D. Soylu, M. Yasunaga, Y. Zhang, D. Narayanan, Y. Wu, A. Kumar, et al. Holistic evaluation of language models. Transactions on Machine Learning Research. Cited by: §1. Nocedal and Wright (2006) J. Nocedal and S. J. Wright Numerical optimization. 2 edition, Springer. Cited by: Appendix A. Roijers et al. (2013) D. M. Roijers, P. Vamplew, S. Whiteson, and R. Dazeley A survey of multi-objective sequential decision-making. Journal of Artificial Intelligence Research 48 (1), p. 67–113. Cited by: §1. Russo (2020) D. Russo Simple bayesian algorithms for best-arm identification. Operations Research 68 (6), p. 1625–1647. Cited by: §2. Shukla and Basu (2024) A. Shukla and D. Basu Preference-based pure exploration. In Advances in Neural Information Processing Systems 37, p. 17313–17347. Cited by: §1, §2. Soare et al. (2014) M. Soare, A. Lazaric, and R. Munos Best-arm identification in linear bandits. In Advances in Neural Information Processing Systems 27, p. 828–836. Cited by: §2. Tekin and Turğay (2018) C. Tekin and E. Turğay Multi-objective contextual multi-armed bandit with a dominant objective. IEEE Transactions on Signal Processing 66 (14), p. 3799–3813. Cited by: §2. Turğay et al. (2018) E. Turğay, D. Öner, and C. Tekin Multi-objective contextual bandit problem with similarity information. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, p. 1673–1681. Cited by: §2. Xu and Klabjan (2023) M. Xu and D. Klabjan Pareto regret analyses in multi-objective multi-armed bandit. In Proceedings of the 40th International Conference on Machine Learning, p. 38499–38517. Cited by: §2. Xue et al. (2026a) B. Xue, J. Cheng, H. Jing, H. Li, and S. Qiu Efficient online lexicographic generalized low-rank matrix bandits. arXiv preprint arXiv:2608.04324. Cited by: §2. Xue et al. (2025a) B. Xue, J. Cheng, F. Liu, Y. Wang, L. Zhang, and Q. Zhang Lexicographic lipschitz bandits: new algorithms and a lower bound. Journal of Machine Learning Research 26 (223), p. 1–56. Cited by: §2. Xue et al. (2026b) B. Xue, M. He, Y. Liu, J. Cheng, Z. Zhao, and Q. Zhang Safe multi-objective linear bandits with hierarchical preferences. In Proceedings of the 35th International Joint Conference on Artificial Intelligence, p. 2418–2426. Cited by: §2. Xue et al. (2026c) B. Xue, Z. Hong, J. Li, Y. Wan, J. Cheng, and S. Qiu Cost-aware multi-objective bandits: theory and application to budgeted llm configuration evaluation. arXiv preprint arXiv:2608.04333. Cited by: §1, §2. Xue et al. (2025b) B. Xue, X. Lin, Y. Wan, and Q. Zhang Problem-dependent regret for lexicographic multi-armed bandits with adversarial corruptions. In Proceedings of the 34th International Joint Conference on Artificial Intelligence, p. 6776–6784. Cited by: §2. Xue et al. (2026d) B. Xue, Y. Wan, Z. Lu, and Q. Zhang Beyond the lower bound: bridging regret minimization and best arm identification in lexicographic bandits. In Proceedings of the 40th AAAI Conference on Artificial Intelligence, p. 27414–27422. Cited by: §1, §1, §2. Zhang et al. (2024) Y. Zhang, Y. Mai, J. S. Roberts, R. Bommasani, Y. Dubois, and P. Liang HELM instruct: a multidimensional instruction following evaluation framework with absolute ratings. External Links: Link Cited by: §A.1, §7.