{"id":"8e834d20-c5c4-4814-a70e-8fea27f6dbf1","arxiv_id":"2602.03972","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Any fixed-confidence best-arm identification algorithm with sample complexity A ln(1/δ)+C yields a fixed-budget algorithm whose sample complexity matches up to polylog(A, ln(1/δ)) factors.","lead":"This paper shows that any fixed-confidence best-arm identification algorithm can be converted into a fixed-budget algorithm with nearly the same sample complexity, up to logarithmic factors. It settles a basic relationship between the two standard bandit settings and improves fixed-budget guarantees for several structured problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma K.1's proof uses the false bound R <= ln(B/Q) (R is floor(log2(B/Q))), so Assumption B.2 and Theorem 3.2 are not proven as stated.","rationale":"The paper's central claim is a constructive reduction from fixed-confidence to fixed-budget, and the proof hinges on Lemma K.1 to ensure that the algorithm reaches the stage where the FC algorithm can stop with low error probability. The reader correctly identified several concrete defects, including the false inequality in Lemma K.1 and the informal 'generally' step. I agree these are significant. However, I view the Lemma K.1 issue as the single most load-bearing concern because it directly undermines the main theorem, whereas the reader's weakest assumption about the existence of strong/weak FC algorithms is less critical: any FC algorithm with an almost-surely finite stopping time satisfies Definition 4.1 for some delta0 (via the quantile of its stopping time), and thus the weak-FC assumption is nearly universal; the paper's own Appendix E admits uncertainty only for algorithms like Track-and-Stop, which likely stop a.s. The Lemma K.1 gap, by contrast, is an internal inconsistency in the proof of the theorem that states the main result. The reduction idea appears sound and likely fixable with adjusted constants, so I do not recommend REJECT or ACCEPT; the reader's CONDITIONAL verdict remains appropriate, and my analysis does not change it.","tokens_in":27778,"tokens_out":21355,"duration_ms":210951,"concrete_test":"Perform a numerical and analytical check of Lemma K.1. Analytically, re-derive the lemma using the correct bound R <= log2(B/Q) and see whether Assumption B.2 still implies r* <= R. Numerically, scan over representative parameters (e.g., A in {1,10,100}, C in {0,100,1000}, delta0 in {0.5, 1/e}, Q in {1,5}) and for each triple compute the smallest B satisfying Assumption B.2, then compute R = floor(log2(B/Q)) and r* = min{r >= 1 : floor(B/R) >= A ln(1/(delta0^{2^{R-r}})) + C}. If any instance has r* > R, Lemma K.1 is false and the proof of Theorem 3.2 fails for that instance. If no counterexample appears, check whether the conclusion holds after replacing ln with log2 in the assumption; this would confirm that only a constant-factor correction is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central constructive guarantee of the paper, Theorem 3.2, relies on Lemma K.1 to ensure that the critical stage r* (the first stage whose budget B' exceeds the FC algorithm's high-probability stopping time) occurs within the R stages of Algorithm 3. If r* > R, the FC2FB algorithm never reaches a stage with both a sufficiently small error probability and sufficient budget, and the error bound in Theorem 3.2 collapses. The proof of Lemma K.1 argues by contrapositive and contains the step 'B < R·A ln(1/delta0) + R·(C+1)', then replaces R with ln(B/Q). But R = floor(log2(B/Q)) <= log2(B/Q), and for B/Q > 1, log2(B/Q) > ln(B/Q); the replacement is invalid. A correct bound would use log2(B/Q), which would strengthen Assumption B.2 by roughly a factor of ln 2 in the logarithmic term. The lemma also concludes B >= 2R(C+1) via an informal 'Generally, A ln(1/delta0) is orderwise larger than (C+1)' rather than a rigorous inequality. Since the proof of Theorem 3.2 depends on r* <= R to guarantee that the first self-terminating stage has both small error probability and sufficient budget, this gap means the paper's headline result is not established as stated. This is load-bearing: if Lemma K.1 cannot be repaired, the sample-complexity claim 'optimal FC is an upper bound on optimal FB' may fail in finite regimes, although the issue appears fixable by changing constants and is not a fundamental flaw of the reduction idea.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a black-box reduction from fixed-budget (FB) to fixed-confidence (FC) best-arm identification. For any 'strong' FC algorithm satisfying Definition 3.1, i.e. δ-correctness for every δ and a high-probability stopping time T*_δ = A ln(1/δ)+C, Algorithm FC2FB runs the FC algorithm in R = floor(log2(B/Q)) stages with doubly exponentially increasing δ, force-terminating stages that do not self-terminate within B', and outputs the first self-terminated recommendation. Theorem 3.2 claims an error bound of order 3 exp(-B/(4Q ln(1/δ0)+4A log2(B/Q))), which translates into an FB sample complexity matching the FC sample complexity up to logarithmic factors, without the learner knowing A or C. The paper also provides FCW2S, a weak-to-strong FC conversion, and applies the framework to heterogeneous-noise, linear, unimodal, and cascading bandits, with supporting experiments. The central thesis is that optimal FC sample complexity upper-bounds optimal FB sample complexity up to logarithmic factors.","tokens_in":28083,"tokens_out":12501,"duration_ms":115360,"significance":"If the main theorem is correct, the result is significant: it gives a general, constructive transfer from FC to FB with only logarithmic overhead, and it immediately improves several existing FB sample-complexity bounds by leveraging better FC algorithms. The reduction is conceptually clean, and the weak-to-strong conversion FCW2S is a useful contribution in its own right. The paper is also careful to state its assumptions and to give detailed proofs. However, the proof of Theorem 3.2 currently rests on an invalid inequality in Lemma K.1, and the broad title/abstract goes beyond what is established because Definition 3.1 excludes common asymptotically optimal FC algorithms such as Track-and-Stop (Appendix E). With Lemma K.1 repaired and the scope stated accurately, this would be a strong contribution to the BAI literature.","major_comments":[{"comment":"The contrapositive proof of Lemma K.1 replaces the integer R=floor(log2(B/Q)) by ln(B/Q) after obtaining B < R(A ln(1/δ0)+C+1). For B/Q>1, floor(log2(B/Q)) can be strictly larger than ln(B/Q) (e.g. B/Q=4 gives 2>1.386), so the step 'B < ln(B/Q)(A ln(1/δ0)+C+1)' is invalid. Consequently Assumption B.2 is not shown to imply r*≤R. The later inference B≥2R(C+1) is justified only by the informal statement that 'Generally, A ln(1/δ0) is orderwise larger than (C+1)', with no concrete inequality. Both facts are used in Case 2 of the proof of Theorem 3.2 to lower-bound 2^{R-r*}; as stated, the main theorem is therefore not proved. The issue appears fixable by carrying log2 through the argument at the cost of constants, so I do not view the reduction idea itself as invalid.","section":"Appendix K, Lemma K.1; used in Proposition B.3 and Theorem 3.2, Case 2"},{"comment":"The headline claim that 'optimal FC is an upper bound on optimal FB' is conditional on the existence of a strong FC algorithm with finite A,C satisfying Definition 3.1 for all δ. Appendix E explicitly concedes that the reduction is not analyzed for algorithms such as Track-and-Stop, which are the typical asymptotic-optimal FC algorithms. For a generic structured BAI problem the paper does not prove that such a strong algorithm exists; FCW2S only converts a weak FC algorithm (Definition 4.1) that already has a finite f(δ0) for some δ0<1/(4e). The authors should either prove or cite a strong FC algorithm for the claimed generic statement, or restate the main result as conditional on the availability of a strong/weak FC algorithm.","section":"Definition 3.1, Appendix E, Theorem 3.2"},{"comment":"Corollary 5.4 uses 'Fixed Budget Peace (Katz-Samuels et al., 2020, Algorithm 3)' as the base algorithm inside FC2FB. However, FC2FB requires a fixed-confidence algorithm satisfying Definition 3.1 as input; a fixed-budget algorithm does not provide δ-correctness or a high-probability stopping-time guarantee in the sense of Definition 3.1. If the intended base is the fixed-confidence algorithm from the same paper (e.g. 'Peace' rather than 'Fixed Budget Peace'), the text should say so and the corollary should be re-derived accordingly. As written, this advertised application is not an instance of Theorem 3.2.","section":"Section 5.3, Corollary 5.4"}],"minor_comments":[{"comment":"The text says K=64 arms for the first experiment, while the caption says K=32 arms. Please make the two consistent.","section":"Figure 1 and its caption"},{"comment":"Substituting Q=1 and δ0=1/e into Theorem 3.2 gives a denominator 4 + 4A log2(B) = 4 + (4/ln2)A ln(B), not 4 + 4A ln(B). The displayed bound is weaker than Theorem 3.2, so it is not incorrect, but the constants should be aligned for reproducibility.","section":"Corollaries 5.2 and 5.3"},{"comment":"The notation A(δ_{L_r}^0) is easy to misread as A(δ, L_r, 0). Please write A(δ0^{L_r}) or otherwise make explicit that the input failure rate is δ0 raised to the power L_r.","section":"Algorithm 3"},{"comment":"The proof says 'because (μ1-μj)≥1', but the argument only needs (μ1-μj)≥0, and Theorem 5.1 assumes Δj≤1. The displayed inequality is salvageable, but the stated reason is wrong and should be corrected.","section":"Appendix F, Proposition F.4"},{"comment":"The expression ln(4K(ln2)^2/δ ln^2(4/Δj)) is ambiguous. It should be ln((4K(ln2)^2/δ)(ln(4/Δj))^2), matching the proof.","section":"Theorem 5.1 formula"},{"comment":"The clarification about the set V of terminated instances should be incorporated directly into the pseudocode of Algorithm 4, since the current description in the main text is ambiguous.","section":"Appendix C, Algorithm 4"}],"recommendation":"major_revision","confidential_remarks":"The central reduction is promising and the paper is likely to become acceptable, but the main proof currently contains a localized false inequality in Lemma K.1. I would also ask the authors to temper the abstract/title: the theorem is conditional on the existence of a strong FC algorithm, and Appendix E acknowledges that common asymptotic-optimal FC algorithms are not covered. The Section 5.3 application appears to use a fixed-budget algorithm as the FC input, which should be clarified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's core idea is good and worth taking seriously: run a strong fixed-confidence algorithm in stages with geometrically increasing failure rates, force-terminate overrunning stages, and output the first self-terminating arm. That gives a blackbox reduction from FC to FB for structured BAI, up to polylog factors, without knowing the algorithm's complexity constants A and C. As far as I know, that is genuinely new — Gabillon et al. is restricted to unstructured problems and not blackbox, and Jun & Nowak is LUCB-specific plus apparently flawed. The applications to heterogeneous noise, linear bandits, unimodal bandits, and cascading bandits are useful even if some corollaries inherit the meta-theorem's baggage. The empirical comparison with SH/SHVar is honest and helpful. The related-work discussion is unusually candid, including the note that Track-and-Stop is not covered by the analysis.\n\nNow the soft spots, in order of severity. The stress-test is right: Lemma K.1's proof replaces R = floor(log2(B/Q)) with ln(B/Q), which is smaller for B/Q > 1, so the implication r* ≤ R is not established. That is load-bearing because Theorem 3.2 needs r* ≤ R to guarantee the first self-terminating stage has both small error probability and sufficient budget. The proof also leans on an informal 'Generally, A ln(1/δ0) is orderwise larger than (C+1)' to conclude B ≥ 2R(C+1). These are fixable — replace ln with log2 and state explicit inequalities — but as written the headline theorem is not proven. I'd also flag Corollary 5.3, which defines A with a δ^{-1} factor, making it δ-dependent and violating Definition 3.1. Appendix C admits a missing set V in Algorithm 4; that is cosmetic. Appendix E limits the main claim to strong/weak FC algorithms and leaves universal optimality open; that is a real scope limitation but not a flaw.\n\nThe central architecture is sound in outline. The stage-counting argument, the geometric union bound, and the force-termination trick are all natural and likely correct after adjusting constants. I disagree with anyone who would reject the reduction idea on the strength of the current Lemma K.1 gap. But the paper does need a revised appendix before the abstract's claim is formally true.\n\nWho gets value: BAI theorists and people building FB algorithms for structured problems. It deserves a serious referee, but the referee should be told to check Lemma K.1 carefully and request a corrected proof. My recommendation: engage with it, desk-reject nothing, but insist on the fix before accepting the sample-complexity claim.","headline":"A clean, likely-fixable reduction from fixed-confidence to fixed-budget BAI, but the main theorem as stated relies on a false inequality in Lemma K.1 and needs a repair before the headline claim is proven.","tokens_in":28678,"tokens_out":1559,"would_cite":true,"duration_ms":18722,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes a constructive reduction: any fixed-confidence best-arm identification algorithm whose stopping time grows like A ln(1/δ)+C can be turned into a fixed-budget algorithm with the same sample complexity up to logarithmic","keywords":["best-arm identification","fixed-budget setting","fixed-confidence setting","meta-algorithm","sample complexity","multi-armed bandits","structured bandits","reduction"],"falsifier":"Try to falsify Theorem 3.2 on a simple K=2 Gaussian instance where A and C are computable: use a valid strong FC algorithm, run FC2FB for a range of budgets B, and check whether the empirical misidentification probability exceeds the stated 3 exp(-B/(4Q ln(1/δ0)+4A log2(B/Q))) bound. Because the bound is explicit and non-asymptotic, one violation with a certified-valid base algorithm would refute the theorem; alternatively, exhibit a strong FC algorithm satisfying Definition 3.1 whose stopping time has a heavy tail in the force-termination regime, and show the error guarantee fails.","tokens_in":27587,"feed_emoji":"🎰","tokens_out":7209,"duration_ms":75189,"temperature":0.7,"pith_summary":"This paper tries to establish that, in best-arm identification, giving the learner a hard sampling budget is no harder than asking it to certify its answer, up to logarithmic factors. It proves this constructively with FC2FB, a meta-algorithm that accepts any fixed-confidence (FC) algorithm with a logarithmic stopping-time guarantee and returns a fixed-budget (FB) algorithm whose error probability decays at essentially the same rate. The base algorithm's unknown problem-dependent constant does not need to be known; the conversion only pays polylogarithmic overhead. If correct, this means every known FC algorithm becomes an FB algorithm with comparable sample complexity, and the optimal FC complexity bounds the optimal FB complexity up to logs.","feed_headline":"Fixed-budget bandits can match fixed-confidence guarantees up to logs","feed_subtitle":"Same sample complexity up to log factors, with no need to know the problem's hardness.","key_machinery":"The central object is the FC2FB loop: it splits the budget B into R=⌊log2(B/Q)⌋ stages, runs the base FC algorithm at failure levels δ0^(2^(R-r)) (doubly exponentially decreasing δ), force-terminates any run that exceeds its per-stage budget, and outputs the first self-terminated recommendation. The proof's key move is identifying the first stage r* whose per-stage budget exceeds the base algorithm's A ln(1/δ)+C stopping time; before that stage, errors have extremely small δ, and after it, the stopping-time guarantee makes non-termination unlikely. The companion FCW2S procedure converts a weak FC algorithm guaranteed only at one fixed δ into a strong one by running L copies in parallel and m","core_discovery":"For any strong fixed-confidence algorithm whose δ-correct stopping time is at most A ln(1/δ)+C, the FC2FB meta-algorithm converts it into a fixed-budget algorithm with error at most 3 exp(-B / (4Q ln(1/δ0) + 4 A log2(B/Q))), which translates to sample complexity O(A ln(1/δ) polylog(A, ln(1/δ))) while A and C remain unknown to the learner. The paper also gives FCW2S, which boosts a weak FC algorithm—one guaranteed only at a single confidence level—into a strong FC algorithm by running many copies in parallel and majority-voting. The authors conclude that the optimal fixed-confidence sample complexity is an upper bound on the optimal fixed-budget sample complexity up to logarithmic factors, an","pith_inferences":["Editorial inference: if the reduction is tight, observed FB-vs-FC gaps in the literature are likely artifacts of particular analyses rather than information-theoretic differences; known lower-bound constructions that force an extra logarithmic factor in FB would mark the boundary of what the generic conversion can promise.","Editorial inference: the meta-algorithm discards samples between stages; a version that reuses samples or shares them across the parallel weak copies would likely reduce constants and could make the approach practical for small budgets, an issue the paper itself flags.","Editorial inference: the reduction's assumption of a unique best arm is restrictive; if extended to ε-good arms, it would let FC algorithms for approximate identification yield FB algorithms that work for every ε simultaneously, a direction the authors list as open.","Editorial inference: because FC2FB inherits the base algorithm's behavior, applying it to asymptotic-only FC algorithms such as track-and-stop remains an open problem, as the paper's appendix notes; the proved guarantee requires finite-time control of the stopping time."],"forward_implications":["Composing FC2FB with state-of-the-art FC algorithms yields, for heterogeneous-noise, linear, unimodal, and cascading bandits, FB sample-complexity bounds that the paper shows are orderwise better than the best published FB bounds in several regimes.","The optimal FC sample complexity is an upper bound (up to polylog factors) on the optimal FB sample complexity for any problem admitting a strong (or weak) FC algorithm—so the two settings become algorithmically equivalent up to logs, not merely comparable.","Practitioners can turn an FC solver they already trust into an anytime FB solver (via the FC2AT variant) without re-deriving problem-specific budget analyses.","A weak FC algorithm verified at one confidence level can be boosted to a strong one, so the reduction is available for many existing FC algorithms that lack a full ln(1/δ) guarantee.","The conversion works without knowing the instance-dependent hardness constant A, removing a practical obstacle that plagues many fixed-budget algorithms."],"fun_headline_variants":["Fixed-budget BAI matches fixed-confidence up to log factors","FC2FB turns any fixed-confidence algorithm into fixed-budget","Fixed-budget and fixed-confidence: same sample complexity up to logs","Fixed-budget BAI is no harder than fixed-confidence up to logs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the input FC algorithm really has a finite, δ-independent constant A and a high-probability stopping time A ln(1/δ)+C for every δ (or at one fixed δ after boosting); if a problem admits only asymptotic-optimal FC algorithms without such finite-time control, the proved conversion does not apply.","fun_headline_variants_meta":{"raw":{"variants":["Fixed-budget BAI matches fixed-confidence up to log factors","FC2FB turns any fixed-confidence algorithm into fixed-budget","Fixed-budget and fixed-confidence: same sample complexity up to logs","Fixed-budget BAI is no harder than fixed-confidence up to logs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000855,"raw_usage":{"total_tokens":3576,"prompt_tokens":793,"completion_tokens":2783,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":537,"completion_tokens_details":{"reasoning_tokens":2709}},"tokens_in":537,"tokens_out":2783,"duration_ms":20551,"temperature":1.0,"reasoning_tokens":2709,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T04:49:41.945444+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Try to falsify Theorem 3.2 on a simple K=2 Gaussian instance where A and C are computable: use a valid strong FC algorithm, run FC2FB for a range of budgets B, and check whether the empirical misidentification probability exceeds the stated 3 exp(-B/(4Q ln(1/δ0)+4A log2(B/Q))) bound. Because the bound is explicit and non-asymptotic, one violation with a certified-valid base algorithm would refute the theorem; alternatively, exhibit a strong FC algorithm satisfying Definition 3.1 whose stopping time has a heavy tail in the force-termination regime, and show the error guarantee fails.","supporting_citations":[],"review_version":1}