{"id":"39a74894-4019-4156-9f51-8f10ea18a761","arxiv_id":"2501.13607","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For multi-objective best arm identification with independent Gaussian rewards, the paper derives the asymptotic complexity and proposes MO-BAI, a linear-programming algorithm achieving it up to a 1+eta factor.","lead":"This paper studies bandit problems where every pull returns scores on several objectives, and the goal is to find the best option for each objective. It proves a lower bound on the time any correct method needs, then gives an algorithm that reaches this bound up to a small tunable factor.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The expectation upper bound in Theorem 4.2 relies on Lemma F.14, whose proof applies a bounded-martingale inequality to unbounded Gaussian increments; as written, (19) is not rigorously established.","rationale":"The reader's conditional verdict is mainly driven by reproducibility, model assumptions, and the empirical threshold. I agree those are limitations, but they are not internal correctness errors. The single load-bearing correctness issue I find is in Lemma F.14/Appendix F: the proof's tail bound uses a 'bounded' martingale assertion for Gaussian increments. The expectation part of the main theorem depends on E[T_gap] < infinity, so this is not cosmetic. The concern does not overturn the central claim because the Gaussian increments are conditionally sub-Gaussian, so a standard concentration inequality should repair the step; this is exactly why the verdict stays conditional rather than reject. Other parts of the proof, including the lower bound in Proposition 3.1, the tracking argument in Lemma F.8, and the threshold argument in Lemma F.10, appear internally consistent. The statement of Lemma F.13 has a direction typo, but its proof contains the correct inequality tilde-c <= (1+eta)c* needed in Theorem 4.2.","tokens_in":33363,"tokens_out":33191,"duration_ms":309826,"concrete_test":"Check whether de la Pena (1999), Theorem 1.2A applies to martingale differences that are conditionally sub-Gaussian rather than bounded. If it does not, replace that step with a sub-Gaussian martingale concentration bound for d_s (e.g., Chernoff on e^{lambda S_t'} using E[e^{lambda d_s}|F_{s-1}] <= e^{lambda^2/2}), and verify the resulting double series sum_t sum_{t'>=l_t} exp(-c xi^2 eta t'/K(1+eta)) is finite after the correct lower summation index l_t+1 is used. If no valid inequality recovers (120), then Lemma F.14 and the expectation part of Theorem 4.2 fail.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma F.14 is the unique step that proves E[T_gap(v,eta,epsilon)] < infinity, and Theorem 4.2 uses that finiteness to pass from the almost-sure bound (20) to the expectation bound (19). In the proof of (120), the martingale difference d_s = 1{A_s=i}(X_{A_s,m}-mu_{i,m}) is described as a 'bounded martingale difference sequence with finite variance', and de la Pena (1999, Theorem 1.2A) is invoked for its tail. This description is inaccurate: conditional on A_s=i, X_{A_s,m} is Gaussian, so |d_s| is unbounded. The cited theorem, as stated in the paper, does not by itself justify the exponential tail exp(-c(eta t'/(K(1+eta))-1)) in (120). Since conditionally on the history d_s is a centered sub-Gaussian variable with conditional variance at most 1, the tail is very likely recoverable by a standard sub-Gaussian martingale inequality; but the printed proof does not supply that argument. Consequently the statement E_v[T_gap(v,eta,epsilon)] < infinity, and with it limsup E_v[tau_delta]/log(1/delta) <= (1+eta)c*(v), is not fully proven as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":33606,"tokens_out":6382,"duration_ms":59193,"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":[{"comment":"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.","section":"Appendix F, Lemma F.14 and Eq. (120)"}],"minor_comments":[{"comment":"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.","section":"Section 5.1, Eq. (21)"},{"comment":"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.","section":"Appendix D, Lemma D.1"},{"comment":"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.","section":"Appendix E, Lemma E.2"},{"comment":"The sentence 'We present an lower bound' contains a grammatical error; it should read 'a lower bound'.","section":"Section 3, opening sentence"},{"comment":"The proof text refers to 'Theorem 3.1' when the statement in the main text is Proposition 3.1. Please align the numbering.","section":"Appendix D, proof of Proposition 3.1"},{"comment":"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.","section":"Section 6 and Appendix A.4"}],"recommendation":"major_revision","confidential_remarks":"The main technical result is strong and the overall architecture of the proof is sound, but the expectation bound in Theorem 4.2 currently rests on a misstatement in Lemma F.14. The fix is likely routine via sub-Gaussian martingale tails, and the missing lemma proofs are also routine. I would be willing to look at a revised version. The paper is a good fit for the journal if the technical gap is closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the core idea is genuinely nice: instead of solving the max-min oracle-weight program at every step (which is what TAS does and is costly when M>1), they linearize and solve a simple LP via surrogate proportions, then show the empirical proportions converge to an (1+eta)-optimal weight. That is a real contribution, not just an incremental twist. Second, the central theorem is almost certainly true, but the printed proof has a gap: Lemma F.14 claims E[T_gap] < infinity using a \"bounded martingale difference\" argument on unbounded Gaussian increments. The cited de la Pena theorem does not apply as stated, so the exponential tail in (120) is not rigorously justified. The bound is very likely recoverable by a standard sub-Gaussian martingale inequality, so I would call this a fixable gap rather than a fatal flaw—but the expectation part of Theorem 4.2 is not fully proven as written.\n\nWhat is good: the lower bound (Prop 3.1) is a clean change-of-measure argument, and the max-min constant specializes correctly to Garivier-Kaufmann when M=1. The surrogate-proportion analysis (Lemma F.8 and friends) is detailed and internally consistent, and the curvature finiteness argument in Lemma F.5 is careful. The paper is also honest about scope: it explicitly flags the Gaussian-independence assumption, and it admits in Appendix A.4 that the experiments use the practical threshold log((1+log t)/delta) rather than the theoretical beta(t,delta). That transparency is welcome, though it does mean the empirical study validates practicality rather than the exact stopping-rule analysis.\n\nSoft spots, in proportion. (1) The Lemma F.14 gap is real and needs fixing. (2) Lemma D.1 and Lemma E.2 are cited rather than proved; both are standard, but leaning on a self-citation for a key concentration lemma is a minor irritant. (3) The synthetic experiment uses only three trials per point; the SNW table uses 100, so the evidence is mixed. (4) The independence assumption across objectives is load-bearing: with correlated or non-Gaussian rewards, c*(v) is no longer the right complexity constant. That is a scope limitation, not a defect.\n\nBottom line: this paper deserves a serious referee. For anyone working on pure-exploration bandits, the surrogate-proportion technique is worth knowing and citing, and the paper as a whole is a solid step toward computationally feasible asymptotically optimal algorithms. Send it out; ask the referee to check Lemma F.14 and request either a correct reference or a direct sub-Gaussian martingale argument. With that patched, I would expect the result to stand.","headline":"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.","tokens_in":34151,"tokens_out":2447,"would_cite":true,"duration_ms":23804,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["multi-objective multi-armed bandits","best arm identification","fixed confidence","asymptotic optimality","surrogate proportions","track-and-stop","pure exploration"],"falsifier":"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.","tokens_in":33155,"feed_emoji":"🎯","tokens_out":15506,"duration_ms":126944,"temperature":0.7,"pith_summary":"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.","feed_headline":"Algorithm finds every objective's best arm at the optimal rate","feed_subtitle":"A linear-program surrogate matches the theoretical lower bound up to a user-tunable (1+η) factor.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the change-of-measure lower-bound framework and the D-Tracking algorithm that MO-BAI generalizes and improves upon.","marker":"Garivier and Kaufmann (2016)"},{"why":"Provides the KL-based concentration/transportation lemma (their Lemma 19) used to prove the lower bound in Proposition 3.1.","marker":"Kaufmann et al. (2016)"},{"why":"Defines the curvature constant and the Lipschitz bound for concave functions used to control the surrogate-proportion tracking error in Lemma F.5.","marker":"Jaggi (2013)"},{"why":"Inspires the gradient-based, Frank-Wolfe-style sampling idea that leads to the surrogate proportions, as acknowledged in Remark 7.","marker":"Wang et al. (2021)"},{"why":"Contributes the threshold structure and the sub-uniform concentration lemma (their Lemma A.4) used for the $\\delta$-PAC stopping rule.","marker":"Chen et al. (2023)"},{"why":"Provides the martingale exponential inequality used to show the finite expectation of the tracking lag in Lemma F.14.","marker":"de la Pena (1999)"},{"why":"Supplies the time-uniform Gaussian concentration bound (their Lemma 33.8) that underlies the stopping test in Proposition 4.1.","marker":"Lattimore and Szepesvári (2020)"}],"fun_headline_variants":["Surrogate trick nails multi-objective best arm in optimal time","Optimal multi-objective search: every best arm, no Pareto detour","Fixed-confidence MAB: asymptotically optimal across all objectives","Surrogate proportions achieve the theoretical limit for MO-BAI","Multi-objective best arm: one pass, provably optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Surrogate trick nails multi-objective best arm in optimal time","Optimal multi-objective search: every best arm, no Pareto detour","Fixed-confidence MAB: asymptotically optimal across all objectives","Surrogate proportions achieve the theoretical limit for MO-BAI","Multi-objective best arm: one pass, provably optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001387,"raw_usage":{"total_tokens":5670,"prompt_tokens":1057,"completion_tokens":4613,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":673,"completion_tokens_details":{"reasoning_tokens":4526}},"tokens_in":673,"tokens_out":4613,"duration_ms":32027,"temperature":1.0,"reasoning_tokens":4526,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:48:15.072167+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the change-of-measure lower-bound framework and the D-Tracking algorithm that MO-BAI generalizes and improves upon."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the KL-based concentration/transportation lemma (their Lemma 19) used to prove the lower bound in Proposition 3.1."}],"review_version":1}