{"id":"771095d3-43b6-40ce-bc59-4e76281aee76","arxiv_id":"2506.05329","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Batched arm elimination designs with a sufficiently large first batch achieve a strictly higher large-deviation efficiency exponent than completely randomized trials for every Gaussian instance with K at least 3.","lead":"This theory paper shows that in best-arm identification with three or more treatments, simple adaptive designs that eliminate the worst-performing arm after a first batch always beat non-adaptive random assignment in the large-sample limit. It resolves an open question about whether experimenters can safely ignore the option of adapting a trial mid-course.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's lower bound depends entirely on Theorem 8, an unproved joint large-deviation principle for adaptive Gaussian allocation; until Theorem 8 is proved or replaced, the dominance result is conditional.","rationale":"Read in good faith: the paper's architecture is coherent, and Theorem 5 would follow if Theorem 8 were true and applicable. The lower bound on Γ (Lemma 3) appears correct; the sufficient condition in Theorem 5 is easy to verify; and the paper is honest that the numerical section is illustrative. However, the decisive ingredient is the joint LDP in Theorem 8, stated without proof. This is not a matter of disagreeing with consensus; it is an unproved technical hypothesis in the proof of the main result. The reader's conditional verdict identified exactly this. I also noticed that the introductory two-batch example uses β_K = K/(2(K-1)), which sits on the boundary of the strict inequality in Theorem 5; this is a presentational flaw but not load-bearing, since choosing β_K slightly larger fixes it. Therefore I do not change the reader's CONDITIONAL verdict.","tokens_in":12061,"tokens_out":8800,"duration_ms":114909,"concrete_test":"Independently re-derive the joint lower bound in Theorem 8 for the concrete case K=3 with the two-batch BAE design β_3>3/4, replacing the citation to Wang et al. [2023] with a direct change-of-measure argument on the round-robin allocation. In particular, compute the rate function I for {p_t} and verify I(p*)=0 at the target allocation p*; then confirm that inf_{p∈P} max{F_{θ,M}(p),I(p)} equals inf_{p∈P} F_{θ,M}(p). If the direct argument needs bounded rewards or if I(p*)>0, the Gaussian extension in Theorem 8 is not established and Lemma 7's next step is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 5) is obtained by combining Lemma 2's lower bound with Lemma 3. The proof of Lemma 2 reduces to Lemma 7, whose key step is the invocation of Theorem 8 (Appendix A.1): liminf_{t→∞} -1/t ln P_θ(m_t∈M, p_t∈P) ≥ inf_{p∈cl(P)} max{F_{θ,M}(p), I(p)}. Two things are needed to apply Theorem 8 to BAE and to drop the I(p) term in the next line of Lemma 7. First, the empirical allocation sequence {p_t} of BAE must satisfy an LDP upper bound with some rate function I; the paper never defines I or proves this for BAE. Second, at the deterministic allocation p* on P one needs I(p*)=0 to justify replacing inf_p max{F,I(p)} by inf_p F(p); this is plausible for a consistent allocation but is not shown. The theorem is stated as an extension of Wang et al. [2023, Theorem 1] from bounded observations to Gaussian observations, but no proof or truncation argument is given. For a state-dependent, adaptively eliminating allocation, this extension is nontrivial: the allocation can react to deviations of the empirical means, and unbounded rewards complicate the change-of-measure argument. If Theorem 8 fails or yields a larger rate, Lemma 7's lower bound, Lemma 2, and Theorem 5 are unsupported. The numerical section does not test the LDP; it only reports finite-sample regret.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies best-arm identification with Gaussian arms of known variance and compares adaptive batched arm elimination (BAE) designs against completely randomized trials (CRTs) using the large-deviation efficiency exponent of the utilitarian regret. Under Assumption 1, the authors claim that whenever K >= 3, there exist simple instance-agnostic BAE designs whose efficiency exponent is strictly larger than that of a CRT for every problem instance (Theorem 5), resolving the second open problem posed in Qin [2022]. The proof combines a lower bound on the error exponent of general BAE designs (Lemma 2, via Lemma 7) with a lower bound on the minimal information quantity Gamma (Lemma 3). The key technical step is an unproved joint large-deviation principle stated as Theorem 8 in Appendix A.1, which is asserted as an extension of Wang et al. [2023] to Gaussian observations. A numerical experiment on a skewed charity-donation distribution is reported.","tokens_in":12341,"tokens_out":6876,"duration_ms":80349,"significance":"If the main claim holds, it is conceptually significant: it shows that an adaptive design can strictly dominate a non-adaptive benchmark instance-by-instance in a canonical bandit task, rather than only on average or in a minimax sense. The sufficient condition in Theorem 5 is explicit, and the paper identifies a very simple two-batch design. The algebraic work in Lemma 9 is correct, and the paper is generally well organized. The manuscript also contains a thoughtful discussion of related work and the distinction between fixed-budget and fixed-confidence settings. However, the central large-deviation theorem is stated without proof and is load-bearing for the main result, so the paper's conclusions are conditional on the validity of that theorem and on the verification of its hypotheses for BAE.","major_comments":[{"comment":"Theorem 8 is the only bridge in Lemma 7 between the event {m_Tn in M, p_Tn in P} and the rate w_n Gamma_{theta,n}, but it is stated without proof. The claimed extension of Wang et al. [2023, Theorem 1] from bounded observations to unbounded Gaussian observations is nontrivial for an adaptive elimination algorithm, because the allocation can react to deviations of the empirical means and because unbounded rewards complicate change-of-measure arguments. The authors should either provide a complete proof of Theorem 8 or give a precise reference that covers the Gaussian case; otherwise Lemma 2 and Theorem 5 are unsupported.","section":"Appendix A.1, Theorem 8"},{"comment":"To apply Theorem 8 to BAE, the paper must verify that the empirical allocation sequence {p_t} of BAE satisfies the assumed large-deviation upper bound with some rate function I, and it must define that rate function. The manuscript never does so. I note that the subsequent step of replacing inf_p max{F(p), I(p)} by inf_p F(p) in Lemma 7 is valid without any condition on I(p*), because max{F,I} >= F; the substantive gap is the unproved theorem and the unverified LDP condition on the allocation sequence.","section":"Lemma 7 and Theorem 8 hypotheses"},{"comment":"The simulation evaluates a design with K=4, s=1, and first batch fraction beta_K = 2/3. For these parameters, the sufficient condition in Example 1 requires beta_K > 1/2 + 1/(2(K-s)) = 1/2 + 1/6 = 2/3, so the simulated design is exactly at the boundary and is not covered by Theorem 5. The numerical experiment therefore cannot be cited as empirical support for the dominance result; the authors should either use a strictly larger first batch or report the simulation as an exploratory robustness check outside the proven range.","section":"Section 4, numerical example"}],"minor_comments":[{"comment":"The sentence 'a policy pi is large-deviation admissible is there is no policy' should read '... is admissible if there is no policy'.","section":"Definition 2"},{"comment":"The variable r in the condition 'if r >= 2 and t = (beta_K + ... + beta_r)T' is not defined; it should be the current number of remaining arms n.","section":"Algorithm 1, line 6"},{"comment":"There is a typo: 'speical case' should be 'special case'.","section":"Section 2"},{"comment":"The text refers to the design 'described in Corollary 1 with s = 1', but no Corollary 1 appears in the paper; the intended reference appears to be Example 1.","section":"Section 4"},{"comment":"The notation ln(K) in the successive rejects weights is nonstandard and should be defined, e.g., as the K-th harmonic number over 2 plus terms.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript addresses an interesting open problem and the high-level argument is appealing, but the missing proof of Theorem 8 is a serious gap. I am not recommending rejection because the gap is localized: if the authors can supply a proof or a verifiable reference for the Gaussian extension and verify the LDP hypothesis for BAE, the paper would be suitable. The numerical issue at beta_K = 2/3 should also be corrected before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives a clean sufficient condition for batched arm elimination (BAE) to strictly beat completely randomized trials in fixed-budget best-arm identification, and it claims to settle an open problem from Qin (2022). The main dominance theorem is genuinely new, the proof chain from Lemma 2 through Corollary 4 to Theorem 5 is transparent, and the algebra in Lemma 9 checks out. The batch weights are instance-agnostic and no fitting or circular reasoning enters. The citation pattern is honest, with the reliance on Wang et al. (2023) explicit.\n\nThe soft spots are real but concentrated. The entire lower bound on BAE's error exponent depends on Theorem 8, a joint large-deviation principle for non-anticipating algorithms with unbounded Gaussian observations. That theorem is stated without proof, described only as an extension of Wang et al.'s bounded-observation result. For a state-dependent adaptive allocation like BAE, this is not a cosmetic gap: one needs an LDP upper bound for the allocation sequence with a rate function that is never defined, plus a check that the rate is zero at the limiting allocation. No truncation argument is given. If Theorem 8 fails, the dominance result is unsupported. The numerical experiment does not test the LDP, only finite-sample regret, so it provides no reassurance on this point.\n\nThere is also a small but embarrassing boundary issue. The two-batch design showcased in the introduction and used in the numerics sets the first-batch fraction to K/(2(K-1)) (and to 2/3 for K=4), which is exactly the threshold in Example 1's condition, not strictly above it. The theorem requires a strict inequality, so the showcased design does not actually satisfy the paper's own sufficient condition. The fix is trivial—take the first batch slightly larger—but as written the example is outside the claimed result.\n\nMy overall take is conditional, not negative. The main idea is credible and the result would be important if Theorem 8 can be proved. I would send this to a serious referee rather than desk reject. The referee's primary job is to verify or refute Theorem 8; the authors should also fix the boundary example and either prove the LDP or cite a version that covers Gaussian adaptive allocations. This paper is worth a reading group discussion and, once the gap is closed, worth citing.","headline":"Elegant dominance result for BAI that hinges on an unproved joint LDP and a boundary example; send to review with a demand for the missing proof.","tokens_in":12896,"tokens_out":2735,"would_cite":true,"duration_ms":34151,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60F10","62L05","62F07"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that simple batched arm elimination designs strictly dominate completely randomized trials for best-arm identification whenever at least three arms are available.","keywords":["best-arm identification","batched arm elimination","completely randomized trial","large deviations","efficiency exponent","admissible designs","adaptive experiments","Gaussian bandits"],"falsifier":"Simulate the two-batch design with $K=3$ arms, Gaussian outcomes with common variance $\\sigma^2=1$ and means $(0,0,\\Delta)$ for $\\Delta>0$, and first-batch fraction $\\beta_3=0.8$; estimate $-\\frac{1}{T}\\log P(\\text{misidentification})$ at $T=10^4,10^5,10^6$. The paper's Theorem 5 predicts the limiting rate is strictly above the CRT rate $\\Delta^2/12$; a rate converging to $\\Delta^2/12$ or below would falsify the central claim.","tokens_in":11777,"feed_emoji":"🎯","tokens_out":8960,"duration_ms":104459,"temperature":0.7,"pith_summary":"This paper asks whether an experimenter who could run an adaptive trial is ever justified in running a non-adaptive completely randomized trial (CRT). It answers no for the best-arm identification problem when there are at least three treatment arms: there exist simple batched arm elimination designs whose large-sample error probability decays exponentially faster than that of a CRT on every Gaussian instance with known variance. The comparison is made through the efficiency exponent, the rate at which the chance of deploying the wrong arm vanishes as the sample grows. Establishing the dominance settles an open problem about the admissibility of completely randomized trials among adaptive designs.","feed_headline":"Adaptive trials beat complete randomization for 3+ arms","feed_subtitle":"A two-batch elimination rule gets a strictly faster error decay than a non-adaptive trial on every Gaussian instance.","key_machinery":"The central object is the batched arm elimination (BAE) design, a successive-rejects style rule that at pre-specified checkpoints discards the arm with the lowest empirical mean. Its error probability is controlled by two quantities: $w_n$, the total sample fraction accumulated toward the arm eliminated when $n$ arms remain, and $\\Gamma_{\\theta,n}$, the minimal Kullback-Leibler information needed for the best arm to look like the worst member of an $n$-arm set. The lower bound $e^{\\mathrm{BAE}}_{\\theta} \\ge \\min_n w_n \\Gamma_{\\theta,n}$, combined with Lemma 3's bound $\\Gamma_{\\theta,n} \\ge \\frac{n-1}{n}\\frac{\\Delta_{\\min}(\\theta)^2}{2\\sigma^2}$, converts the design question into the algebraic condition $\\min_n w_n(n-1)/n > 1/(2K)$. The exponential-rate proof itself rests on a joint large-deviation principle for empirical means and allocation sequences, stated as Theorem 8 and extended from bounded observations to Gaussian ones.","core_discovery":"The paper's central claim is Theorem 5: under Gaussian arms with known common variance and a unique best arm, every batched arm elimination design whose batch weights satisfy $\\min_{n=K,\\ldots,2} w_n\\frac{n-1}{n} > \\frac{1}{2K}$ achieves $e^{\\mathrm{BAE}}_{\\theta} > e^{\\mathrm{Unif}}_{\\theta}$ for every instance $\\theta$. Here $w_n$ is the fraction of the sample allocated, by the end of the batch that begins with $n$ arms, to the arm that is then eliminated, and the efficiency exponent $e^\\pi_{\\theta}$ measures the exponential decay rate of the misidentification probability, equivalently of the utilitarian regret. Since the CRT exponent is $\\Delta_{\\min}(\\theta)^2/(4K\\sigma^2)$ and the BAE lower bound is $\\Delta_{\\min}(\\theta)^2/(2\\sigma^2) \\min_n w_n(n-1)/n$, the algebraic condition marks exactly where the adaptive design pulls ahead. The paper highlights a two-batch special case: randomize on all $K$ arms for a fraction $\\beta_K$ of the sample, eliminate the $s$ worst arms, then randomize uniformly on the survivors, with $\\beta_K$ large enough (for $s=1$, $\\beta_K > 1/2 + 1/(2(K-1))$).","pith_inferences":["An experimenter reading these results would be tempted to adopt the two-batch rule in practice; the numerical example suggests the advantage survives a skewed, zero-inflated outcome distribution, but the stated theorem only covers Gaussian arms with known common variance.","Because the proof depends on an unproved Gaussian extension of a bounded-observation large-deviation theorem, the cleanest test of the paper's core claim is to verify Theorem 8 directly for the two-batch design rather than to re-simulate finite-sample regret.","The same weighted-allocation condition could serve as a template for other batched rules, such as eliminating several arms per batch or using unequal batch lengths, whenever the per-arm cumulative allocation stays above the threshold.","If the large-deviation extension holds, the admissibility question for other non-adaptive benchmarks, such as stratified or matched-pair designs, becomes a natural next target, since the argument here is built specifically around uniform randomization as the baseline."],"forward_implications":["Whenever $K \\ge 3$ and the batch weights satisfy $\\min_n w_n(n-1)/n > 1/(2K)$, the error probability of BAE decays exponentially faster than that of complete randomization on every Gaussian instance with known variance, and the same ordering holds for utilitarian regret.","The two-batch rule with $s=1$ requires only that the first batch be larger than half the sample, namely $\\beta_K > 1/2 + 1/(2(K-1))$, so the dominating design is simple to implement and needs no problem-specific tuning.","Completely randomized trials are not large-deviation admissible among fixed-budget adaptive policies when $K \\ge 3$, settling the open question in the negative.","The sufficient condition spells out the design check: for each number of remaining arms, the per-arm cumulative allocation fraction, weighted by $(n-1)/n$, must clear the uniform-allocation threshold of $1/(2K)$."],"supporting_citations":[{"why":"defined the fixed-budget best-arm identification setting and posed the open question of whether completely randomized trials are admissible among adaptive designs, which this paper answers.","marker":"Qin [2022]"},{"why":"introduced best-arm identification and the successive rejects algorithm, the template that BAE generalizes by allowing arbitrary batch weights and regret-based analysis.","marker":"Audibert et al. [2010]"},{"why":"provides the large-deviation rate for the misidentification probability of uniform allocation, yielding the CRT efficiency exponent $\\Delta_{\\min}^2/(4K\\sigma^2)$ that BAE must beat.","marker":"Russo [2020, Proposition 2]"},{"why":"supplies the large-deviation result for bounded observations that Theorem 8 extends to Gaussian outcomes; Lemma 7 and therefore Theorem 5 depend on this extension.","marker":"Wang et al. [2023, Theorem 1]"},{"why":"provides the field-experiment data whose fitted distribution is used in the numerical section to illustrate that BAE's advantage persists outside the Gaussian assumption.","marker":"Karlan and List [2007]"}],"fun_headline_variants":["Adaptive trials dominate non-adaptive for 3+ arms","For 3+ arms, adaptive strictly beats complete randomization","Batched elimination beats CRT in best-arm identification","Simple adaptive designs dominate CRTs for 3+ arms","Efficiency exponent shows adaptive wins for 3+ arms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the error-probability lower bound relies on a large-deviation theorem for Gaussian observations that is stated without proof in the appendix; if that theorem fails for adaptive, state-dependent allocation rules like BAE, the strict dominance result is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive trials dominate non-adaptive for 3+ arms","For 3+ arms, adaptive strictly beats complete randomization","Batched elimination beats CRT in best-arm identification","Simple adaptive designs dominate CRTs for 3+ arms","Efficiency exponent shows adaptive wins for 3+ arms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000738,"raw_usage":{"total_tokens":3316,"prompt_tokens":986,"completion_tokens":2330,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":602,"completion_tokens_details":{"reasoning_tokens":2250}},"tokens_in":602,"tokens_out":2330,"duration_ms":21630,"temperature":1.0,"reasoning_tokens":2250,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:22:49.349989+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the two-batch design with $K=3$ arms, Gaussian outcomes with common variance $\\sigma^2=1$ and means $(0,0,\\Delta)$ for $\\Delta>0$, and first-batch fraction $\\beta_3=0.8$; estimate $-\\frac{1}{T}\\log P(\\text{misidentification})$ at $T=10^4,10^5,10^6$. The paper's Theorem 5 predicts the limiting rate is strictly above the CRT rate $\\Delta^2/12$; a rate converging to $\\Delta^2/12$ or below would falsify the central claim.","supporting_citations":[{"cited_title":"Best arm identification in multi-armed bandits","cited_arxiv_id":null,"evidence_quote":"introduced best-arm identification and the successive rejects algorithm, the template that BAE generalizes by allowing arbitrary batch weights and regret-based analysis."},{"cited_title":"Best arm identification with fixed budget: A large deviation perspective","cited_arxiv_id":null,"evidence_quote":"supplies the large-deviation result for bounded observations that Theorem 8 extends to Gaussian outcomes; Lemma 7 and therefore Theorem 5 depend on this extension."},{"cited_title":"Does price matter in charitable giving? evidence from a large-scale natural field experiment","cited_arxiv_id":null,"evidence_quote":"provides the field-experiment data whose fitted distribution is used in the numerical section to illustrate that BAE's advantage persists outside the Gaussian assumption."}],"review_version":1}