Pith. sign in

REVIEW 1 major objections 6 minor 1 cited by

Optimal Multi-Objective Best Arm Identification with Fixed Confidence

T0 review · 1 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Any correct policy needs at least $c^*(v)\log(1/\delta)$ pulls on average; the new MO-BAI algorithm matches this bound up to $(1+\eta)$ using surrogate proportions from a linear program.

desk verdict A genuinely clever surrogate-proportion LP trick for multi-objective BAI, with detailed proofs that are almost right—but Lemma F.14 has a real, fixable gap in the expectation bound. read the letter →

arxiv 2501.13607 v1 pith:A2DPGAMJ submitted 2025-01-23 cs.LG cs.AIcs.ITmath.ITstat.ML

Zhirui Chen , P.N. Karthik , Yeow Meng Chee , Vincent Y. F. Tan This is my paper · ORCID
classification cs.LGcs.AIcs.ITmath.ITstat.ML
keywords multi-objectivemulti-armedbanditsbestarmidentificationfixedconfidenceasymptoticoptimalitysurrogateproportionstrack-and-stoppureexploration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies pure exploration in a multi-armed bandit where each arm yields a vector of rewards, one per objective, and the task is to return the best arm of every objective with error probability at most $\delta$. The authors establish that any policy achieving this must pull arms at least $c^*(v)\log(1/\delta)$ times on average, where $c^*(v)$ is the value of a max-min optimization over pull proportions. They then design an algorithm, MO-BAI, that does not solve this max-min problem at each step; instead, it samples arms according to a surrogate proportion obtained from a linear program. The main theorem proves that MO-BAI's expected stopping time is bounded above by $(1+\eta)c^*(v)\log(1/\delta)$ asymptotically, for any $\eta>0$. Because $\eta$ can be chosen arbitrarily small, the algorithm is asymptotically optimal, filling the gap left by prior work that focused only on Pareto frontier identification.

What carries the argument

The mechanism that carries the argument is the surrogate proportion $s_t$, defined as the maximizer over the $\eta$-mixed simplex $\Gamma(\eta)$ of $h_{v}(\hat{\omega}_{t-1},s)$, where $h_v(\omega,z)=\min_{m,i}\{g_v^{(i,m)}(\omega)+\langle \nabla g_v^{(i,m)}(\omega),z-\omega\rangle\}$ is the lower envelope of first-order Taylor expansions of the pairwise complexity contributions $g_v^{(i,m)}(\omega)=\frac{\Delta_{i,m}^2}{2}\frac{\omega_i\omega_{i^*_m}}{\omega_i+\omega_{i^*_m}}$. Since $h_v$ is a minimum of affine functions of $s$, computing $s_t$ reduces to a linear program. A buffer-update rule $B_t=B_{t-1}-e_{A_t}+s_t$ keeps the empirical pull proportions inside $\Gamma(\eta)$ and steers them toward $s_t$; the proof controls the tracking error by a curvature constant $C(v,\eta)$ that is finite on $\Gamma(\eta)$, and Lemma F.13 converts the restricted optimum $\tilde{c}(v,\eta)^{-1}=\sup_{\omega\in\Gamma(\eta)}g_v(\omega)$ into $c^*(v)$ at a multiplicative cost of $1+\eta$.

What would settle it

Use the two-arm, three-objective instance from Remark 2 (with a small gap $\varepsilon$), compute $c^*(v)$ exactly from equation (5), then run MO-BAI with its theoretical threshold $\beta(t,\delta)$ for $\delta=10^{-2},10^{-3},\dots,10^{-8}$. If the empirical ratio $\mathbb{E}[\tau_\delta]/\log(1/\delta)$ does not converge to a value inside $[c^*(v),(1+\eta)c^*(v)]$ as $\delta$ shrinks, the claimed lower or upper bound is violated for that instance.

Watch

Extended reading notes

Core claim

The paper's central result is a pair of matching bounds for multi-objective best arm identification with independent, unit-variance Gaussian rewards. Proposition 3.1 shows that every $\delta$-PAC policy satisfies $\mathbb{E}[\tau_\delta] \ge c^*(v)\log(1/(4\delta))$, where $c^*(v)^{-1}=\sup_{\omega\in\Gamma}\min_{m\in[M]}\min_{i\neq i^*_m(v)} \frac{\omega_i\omega_{i^*_m}\Delta_{i,m}^2}{2(\omega_i+\omega_{i^*_m})}$. Theorem 4.2 then shows that the proposed MO-BAI algorithm, which samples arms using surrogate proportions rather than the oracle weight, achieves $\limsup_{\delta\downarrow0}\mathbb{E}[\tau_\delta]/\log(1/\delta)\le(1+\eta)c^*(v)$ for any fixed $\eta>0$, and the same holds almost surely for the stopping time itself. The algorithm also satisfies a non-asymptotic $\delta$-PAC guarantee (Proposition 4.1). Together these results establish that $c^*(v)$ is the correct complexity constant and that the surrogate-proportion scheme is asymptotically optimal up to an arbitrarily small multiplicative slack.

Load-bearing premise

The reward noise in every objective is an independent standard normal, and the objectives are mutually independent; if real rewards are correlated across objectives or non-Gaussian, the complexity constant $c^*(v)$ is no longer correct and the optimality guarantee in Theorem 4.2 does not apply.

Editorial extensions

If this is right

  • Any $\delta$-PAC policy for multi-objective BAI must spend at least $c^*(v)\log(1/\delta)$ pulls in expectation, so the lower-bound constant $c^*(v)$ is the right measure of instance difficulty.
  • MO-BAI attains this lower bound up to $(1+\eta)$ for any $\eta>0$ while solving only a linear program per step, so asymptotic optimality and computational tractability are compatible.
  • When $M=1$, both the lower bound and the algorithm reduce to the classical Gaussian BAI results, making single-objective BAI a special case of this framework.
  • The multi-objective problem has rank 2, so the empirically-friendly threshold $\log((1+\log t)/\delta)$ is valid and MO-BAI can use it in practice.
  • The $\delta$-PAC guarantee (Proposition 4.1) holds for every $\delta\in(0,1)$, not only asymptotically, so the algorithm's correctness is certified at any finite confidence level.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the surrogate-proportion step only requires the complexity function to be concave, the same linear-program trick may yield optimal algorithms for other structured fixed-confidence problems, such as linear bandits, where the oracle weight is also expensive.
  • If $\eta$ is allowed to shrink to zero at a carefully chosen rate instead of being fixed, MO-BAI might attain the exact constant $c^*(v)$ rather than $(1+\eta)c^*(v)$, although the current proof style requires $\eta$ fixed.
  • For correlated Gaussian or non-Gaussian objectives, the algorithm's mechanics remain plausible, but the complexity constant must be recomputed from the correct KL divergence; the independence assumption is thus the real boundary of the paper's optimality claim.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

Summary. The paper studies fixed-confidence best-arm identification in a multi-objective multi-armed bandit with K arms and M independent Gaussian objectives, where the goal is to identify the best arm for every objective. The main contributions are (i) a problem-dependent lower bound on the asymptotic expected stopping time, expressed through a max-min complexity constant c*(v), (ii) an algorithm called MO-BAI that replaces the per-step max-min oracle optimization by a linear-programming surrogate-proportion computation, and (iii) a proof that MO-BAI is delta-PAC and asymptotically optimal up to a multiplicative factor 1+eta for any eta>0. The appendix contains detailed proofs of the upper bound, and the paper reports numerical comparisons against a D-Tracking-style baseline and a successive-elimination baseline on synthetic and SNW datasets.

Significance. If the results hold, this is a substantial contribution: it gives the first fixed-confidence treatment of multi-objective best-arm identification (as opposed to Pareto-frontier identification), identifies the correct complexity constant, and provides a computationally tractable algorithm that matches the lower bound up to an arbitrarily small multiplicative slack. The surrogate-proportion idea is a genuine methodological novelty relative to track-and-stop algorithms that solve a convex program at every step. The assumptions are explicit: independent unit-variance Gaussian noise per objective, and a unique best arm per objective, which is reasonable for a first asymptotic-optimality result. The lower-bound proof follows a standard change-of-measure argument, and the upper-bound proof is detailed and self-contained except for a few imported lemmas. A strength of the manuscript is that the claimed asymptotic optimality is measured against an externally defined complexity constant c*(v), not against any fitted quantity.

major comments (1)
  1. [Appendix F, Lemma F.14 and Eq. (120)] The proof of E[T_gap(v,eta,epsilon)] < infinity is not complete as written. In the display leading to Eq. (120), the sequence d_s = 1{A_s=i}(X_{A_s,m}-mu_{i,m}) is called a 'bounded martingale difference sequence with finite variance', and de la Pena (1999, Theorem 1.2A) is invoked for an exponential tail. This description is inaccurate: conditionally on the history, d_s is a centered Gaussian random variable times an indicator, so |d_s| is unbounded. The cited theorem, as stated, does not justify the exponential tail in Eq. (120). Since E[T_gap] is the unique step that converts the almost-sure bound (20) into the expectation bound (19) in Theorem 4.2, the expectation statement of Theorem 4.2 is not fully proven as written. The gap appears fixable: conditionally on the history, d_s is sub-Gaussian with conditional variance at most 1, so a standard sub-Gaussian martingale concentration inequality should yield the same type of tail. The authors should supply this argument explicitly.
minor comments (6)
  1. [Section 5.1, Eq. (21)] The definition of C(v,eta) writes h_v(omega, z-omega), but h_v is defined in Eq. (9) with a second argument z and a linear term <nabla g, z-omega>. In Lemma F.5, Eq. (49), the quantity is correctly interpreted as h_v(omega, z). The notation in Eq. (21) should be corrected for consistency.
  2. [Appendix D, Lemma D.1] Lemma D.1 is a load-bearing ingredient of the lower bound, but its proof is omitted and it is only said to follow as in Kaufmann et al. (2016, Lemma 19). Given that the multi-objective setting involves M independent Gaussian dimensions, the authors should either include the derivation or state precisely the adaptation needed for vector rewards.
  3. [Appendix E, Lemma E.2] Lemma E.2 is cited from Chen et al. (2023, Lemma A.4) without proof. It is used in the delta-PAC argument for the stopping rule. A short proof or a precise reference statement would improve self-containedness.
  4. [Section 3, opening sentence] The sentence 'We present an lower bound' contains a grammatical error; it should read 'a lower bound'.
  5. [Appendix D, proof of Proposition 3.1] The proof text refers to 'Theorem 3.1' when the statement in the main text is Proposition 3.1. Please align the numbering.
  6. [Section 6 and Appendix A.4] The simulation study replaces the theoretical threshold beta(t,delta) with the empirical threshold log((1+log t)/delta). The paper acknowledges this difference, but it should be stated more prominently that the numerical stopping times therefore illustrate practical performance and do not directly validate the constants in Theorem 4.2.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity constant c*(v) is defined directly from sub-optimality gaps, and the algorithm's guarantee is measured against that externally defined constant without fitting.

full rationale

The paper's central claim, Theorem 4.2, is that the expected stopping time of MO-BAI satisfies limsup E[tau_delta]/log(1/delta) <= (1+eta) c*(v), where c*(v)^-1 is defined by the max-min expression in Equation (5) solely from the sub-optimality gaps of the instance. The lower bound in Proposition 3.1 is obtained by standard change-of-measure arguments (Lemma D.1 adapted from Kaufmann et al. 2016), and the lower-bound constant is not fitted to the algorithm. The upper bound is derived by showing that the empirical proportion converges to a surrogate-optimal weight in the restricted simplex Gamma(eta), and Lemma F.13 relates that limit to c*(v) via an explicit inequality c*(v) <= (1+eta) c_tilde(v,eta). No parameter is calibrated to make the upper bound match the lower bound; the factor (1+eta) is a slack from restricting arm weights to be at least eta/(K(1+eta)). The algorithm's stopping threshold and test statistic are based on concentration inequalities, not on knowing c*(v). The only self-cited results are Lemma E.2 and Lemma F.3, taken from the authors' prior federated BAI paper; these are general technical facts (a tail bound for sums of logarithms of sub-uniform random variables and the asymptotic inverse of f), not statements of the target theorem, and they are not used to define c*(v) or to impose the optimality conclusion by construction. The skeptic's concern about Lemma F.14, where a bounded-martingale inequality is applied to unbounded Gaussian increments, is a possible rigor gap in the proof of E[T_gap] < infinity, but it is not circularity: the conclusion does not assume the theorem being proved, and a correct proof of that step would still be independent of the lower-bound constant. Accordingly, no circular step can be exhibited, and the appropriate finding is no significant circularity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

No new physical entities, forces, particles, or dimensions are introduced. The surrogate proportion is a computational object defined inside the paper, with its properties proved rather than postulated.

free parameters (1)
  • eta (relaxation parameter) = 0.1 in experiments; arbitrary positive value in theory
    Chosen by the user, not fitted to data. It defines the minimum sampling mass eta/(K(1+eta)) on every arm and appears as the multiplicative slack (1+eta) in Theorem 4.2. Smaller eta makes the guarantee closer to the lower bound.
assumptions (5)
  • domain assumption Reward noise is independent standard normal in every objective, and objectives are mutually independent.
    Section 2 defines r_{t,m} = mu_{A_t,m} + eta_{t,m} with independent standard normal noise. The KL divergence in Lemma D.1 and the concentration in Lemma E.1 take this specific form, and c*(v) would change under correlations or non-Gaussian noise.
  • domain assumption Each objective has a unique best arm.
    Section 2 restricts the problem class P to instances with a unique best arm per objective. The lower-bound proof and the recommendation rule rely on this uniqueness to define I*(v) and Alt(v).
  • standard math Change-of-measure lemma from Kaufmann et al. (2016) extends to vector Gaussian rewards.
    Lemma D.1 is adapted from Kaufmann et al., Lemma 19; the proof is stated to follow the same lines and is omitted. It is the foundation of the lower bound.
  • standard math Time-uniform Gaussian concentration and Erlang tail inequalities hold as stated.
    Lemma E.1 is cited from Lattimore and Szepesvari (2020) and Lemma E.2 from Chen et al. (2023). These support the delta-PAC stopping proof in Appendix E.
  • standard math Martingale concentration bounds of de la Pena (1999) apply to the random pull-count processes.
    Lemma F.14 uses these bounds to show the finite gap time T_gap has finite expectation, a step needed for the expectation version of Theorem 4.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Multi-Objective Best Arm Identification with Fixed Confidence." pith.science (2026). https://pith.science/paper/A2DPGAMJ

@misc{pith2026250113607,
  author       = {Pith},
  title        = {Pith review of: Optimal Multi-Objective Best Arm Identification with Fixed Confidence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A2DPGAMJ}},
  note         = {Machine review of arXiv:2501.13607}
}
abstract

We consider a multi-armed bandit setting with finitely many arms, in which each arm yields an $M$-dimensional vector reward upon selection. We assume that the reward of each dimension (a.k.a. {\em objective}) is generated independently of the others. The best arm of any given objective is the arm with the largest component of mean corresponding to the objective. The end goal is to identify the best arm of {\em every} objective in the shortest (expected) time subject to an upper bound on the probability of error (i.e., fixed-confidence regime). We establish a problem-dependent lower bound on the limiting growth rate of the expected stopping time, in the limit of vanishing error probabilities. This lower bound, we show, is characterised by a max-min optimisation problem that is computationally expensive to solve at each time step. We propose an algorithm that uses the novel idea of {\em surrogate proportions} to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step. We demonstrate theoretically that our algorithm is asymptotically optimal. In addition, we provide extensive empirical studies to substantiate the efficiency of our algorithm. While existing works on pure exploration with multi-objective multi-armed bandits predominantly focus on {\em Pareto frontier identification}, our work fills the gap in the literature by conducting a formal investigation of the multi-objective best arm identification problem.

Figures

Figures reproduced from arXiv: 2501.13607 by the authors.

Figure 1
Figure 1. Plot of average stopping times of MO-BAI and BASELINE (with varying iteration numbers) for the synthetic dataset. 6 Numerical Study We run experiments to validate the effectiveness of MO-BAI through empirical assessments on the SNW dataset (Zulu￾aga et al., 2016) and a synthetic dataset, and their detailed descriptions are presented in Appendix A.2. Specifically, we compare our algorithm against BASELINE, a multi-ob… view at source ↗
Figure 2
Figure 2. We observe that the performance for η = 0.1 is superior to that for η > 0.1, This observation aligns with our theoretical findings. Indeed, because Ni,t/t ≈ ωbi,t for all large t (noting that |Bi,t| ≤ 1), and mini∈[K] ωbi,t ≥ η K(1+η) , it is evident that the fraction of times each arm is pulled in the long run increases with increase in η (as η 7→ η/(1 + η) is an increasing function), thereby leading to larger stop… view at source ↗
Figure 2
Figure 2. Comparison of the empirical stopping times with varying values of [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Best Group Identification in Multi-Objective Bandits

    cs.LG 2025-05 conditional novelty 6.0 of 10

    The authors formalize Best Group Identification in multi-objective bandits and give elimination algorithms with upper and lower sample-complexity bounds for Pareto and linear objectives.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages · cited by 1 Pith paper

  1. [1]

    and Tekin, C

    Ararat, C. and Tekin, C. (2023). Vector optimization with stochastic bandit feedback. In International Conference on Artificial Intelligence and Statistics, pages 2165–2190. PMLR. Auer, P., Chiang, C.-K., Ortner, R., and Drugan, M. (2016). Pareto front identification from stochastic bandit feedback. In Artificial Intelligence and Statistics, pages 939–947...

    work page 2023

  2. [2]

    The tabulated results indicate the superior performance of our proposed MO-BAI algorithm over BASELINE on the SNW dataset. Notably, this dataset involves a greater number of decision variables compared to the synthetic dataset instance (i.e., 206 versus 20), posing increased difficulty in running the optimization routine of BASELINE . Consequently, to ach...

    work page 2016

  3. [3]

    The empirical findings underscore that our proposed MO-BAI is significantly better than B ASELINE -NON -UNIFORM on the SNW dataset. 15 OPTIMAL MULTI-OBJECTIVE BEST ARM IDENTIFICATION WITH FIXED CONFIDENCE Algorithm 4 MO-SE (Multi-objective adaptation of Successive Elimination (Even-Dar et al., 2006)) Input: K ∈ N: number of arms δ ∈ (0, 1): confidence lev...

    work page 2006

  4. [4]

    In particular, we set αt = p 2 ln (4M Kt2/δ) /t in Algorithm 3 of Even-Dar et al

    Specifically, in MO-SE , there are M rounds, and we determine the empirical best arm of m−th objective in m−th round using the principle of successive elimination. In particular, we set αt = p 2 ln (4M Kt2/δ) /t in Algorithm 3 of Even-Dar et al. (2006), which is a natural adaption to the multiobjective case as there are total M K arms and the noises are G...

    work page 2006

  5. [6]

    It is noteworthy that the same holds true of multi-objective BAI problems; for a formal proof of this, see Appendix C. In light of the above rationale, we adopt the threshold log((1 + log t)/δ) for our simulations following Garivier and Kaufmann (2016), and note that is different from our theoretical threshold β(t, δ) defined in Section 4.2. Even with the...

    work page 2016

  6. [7]

    It is important to note that the approach proposed by Garivier and Kaufmann (2016) for solving the optimization problem in line 6 of BASELINE becomes impractical when M >1 due to the various best arms across different objectives. In our implementation of BASELINE , we adopt the sub-routine in Algorithm 3 to solve the optimisation problem in Line 6 of Algo...

    work page 2016

  7. [10]

    For pairs (i, m) where i = m, µi,m is uniformly selected from [1.2, 2]

    For all pairs (i, m) where i ̸= m, µi,m is uniformly chosen from the interval [0, 1]. For pairs (i, m) where i = m, µi,m is uniformly selected from [1.2, 2]. These values remain constant throughout the experiment. Let v = [µi,m : (i, m) ∈ [K] × [M ]]⊤. It is evident that i∗ m(v) = m for every m ∈ [M ]. Additionally, ∆i,m(v) > 0.2 for all i ̸= i∗ m(v). SNW...

    work page 2016

  8. [11]

    We observe that the performance for η = 0.1 is superior to that for η >0.1, This observation aligns with our theoretical findings. Indeed, because Ni,t/t ≈ bωi,t for all large t (noting that |Bi,t| ≤1), and mini∈[K] bωi,t ≥ η K(1+η), it is evident that the fraction of times each arm is pulled in the long run increases with increase in η (as η 7→ η/(1 + η)...

    work page 2016

Show all 14 references
  1. [12]

    D Proof of Proposition 3.1 Firstly, we introduce a useful lemma adapted from Kaufmann et al. (2016). Lemma D.1. Fix δ >0 and a δ-PAC policy π with stopping time τδ. Let Fτδ = σ({(XAt,m(t), At) : t ∈ [τδ], m∈ [M ]}) denote the history of all the arm pulls and rewards seen up to...

    2016

  2. [14]

    (119) The inequality above follows by observing that bω·,t′ ∈ Γ(η) for all t′. We note that t′ X s=1 1{As=i} (XAs,m(s) − µi,m(v)) ∞ t′=K+1 31 OPTIMAL MULTI-OBJECTIVE BEST ARM IDENTIFICATION WITH FIXED CONFIDENCE is a bounded martingale difference sequence with finite variance....

    1999

  3. [20]

    A.4 Curated Threshold for Simulations It is customary in the fixed-confidence BAI literature to employ thresholds in simulations that differ from theo- retical thresholds. Notably, in the single-objective case, Garivier and Kaufmann (2016) utilized βempirical GK (t, δ) = log((...

    2016

  4. [32]

    M., and Ménard, P

    Degenne, R., Koolen, W. M., and Ménard, P. (2019). Non-asymptotic pure exploration by solving games. Advances in Neural Information Processing Systems. Degenne, R., Ménard, P., Shang, X., and Valko, M. (2020). Gamification of pure exploration for linear bandits. In Internation...

    2019 arXiv

  5. [2013]

    20 OPTIMAL MULTI-OBJECTIVE BEST ARM IDENTIFICATION WITH FIXED CONFIDENCE Definition F.1 (Curvature)

    of a concave function. 20 OPTIMAL MULTI-OBJECTIVE BEST ARM IDENTIFICATION WITH FIXED CONFIDENCE Definition F.1 (Curvature). Given a concave function f : D →R defined on a convex domain D, the curvature of f is defined as Ccur(f ) := sup ω,y∈D, γ∈(0,1), d∈∂f (ω) 2 γ2 f (ω) + ⟨z...

    2013

  6. [2023]

    Consequently, under this definition, the best arm for each objective (as defined in our paper) is inherently Pareto optimal

    on Pareto frontier identification, an arm i is defined as Pareto optimal if, for every other arm j where j ̸= i, there exists at least one objective m ∈ [M ] for which µi,m > µj,m. Consequently, under this definition, the best arm for each objective (as defined in our paper) i...

    2021

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.