REVIEW 3 major objections 6 minor 5 references
Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors
T0 review · 3 major / 6 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read 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
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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
What would settle it
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.
Extended reading notes
Core claim
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
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Appendix K, Lemma K.1; used in Proposition B.3 and Theorem 3.2, Case 2] 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.
- [Definition 3.1, Appendix E, Theorem 3.2] 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 5.3, Corollary 5.4] 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.
minor comments (6)
- [Figure 1 and its caption] The text says K=64 arms for the first experiment, while the caption says K=32 arms. Please make the two consistent.
- [Corollaries 5.2 and 5.3] 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.
- [Algorithm 3] 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.
- [Appendix F, Proposition F.4] 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.
- [Theorem 5.1 formula] 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.
- [Appendix C, Algorithm 4] 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.
Circularity Check
No significant circularity: FC2FB is a conditional black-box reduction from assumed FC guarantees to FB guarantees, with self-contained proofs.
full rationale
The central derivation is conditional rather than circular. Theorem 3.2 assumes only Definition 3.1 for the input algorithm A—δ-correctness and a high-probability stopping time T*_δ = A ln(1/δ)+C—and then derives the FB error bound from forced-termination, stopping-time, and correctness events across stages. The proof does not assume the conclusion; A and C enter as assumed properties of the base FC algorithm, not as fitted values. FCW2S likewise supplies its own probabilistic analysis in Appendix C, using only Definition 4.1 and Lemma K.2; the inspiration from Balagopalan et al. (2025) is not used as the source of correctness. The self-citation is therefore not load-bearing. The global claim that optimal FC sample complexity upper-bounds optimal FB is conditional on the existence of strong/weak FC algorithms, and Appendix E explicitly concedes: 'we can still apply FC2FB on fixed-confidence algorithms that are not Weak FC (Eg: Track-and-Stop). However, the analysis of the latter framework is an open problem.' That is a scope limitation, not a circular step. A separate mathematical concern is Lemma K.1's replacement of R = floor(log2(B/Q)) by ln(B/Q), which is not generally valid and may affect the proof of r* ≤ R; this is an apparent proof gap, not a self-referential reduction. Accordingly, no circularity is present.
Assumptions & free parameters
free parameters (3)
- Q
- δ0
- δ1 =
1/(8e) in unimodal application
assumptions (5)
- standard math Standard probability inequalities: sub-Gaussian/Hoeffding tails, Markov's inequality, KL-divergence concentration (Lemma K.2).
- domain assumption The BAI instance has a unique best arm, rewards are i.i.d. across pulls, and the model class M_K is known.
- domain assumption The input FC algorithm is strong (Definition 3.1) or weak (Definition 4.1) with finite A,C (or f(δ0)) and δ0<1/(4e) for the weak case.
- standard math Kiefer-Wolfowitz theorem for G-optimal design (Appendix G).
- domain assumption Theorem 3.7 of Poiani et al. (2024) providing the finite-time expected stopping-time bound for UniTT in unimodal bandits.
Cite this review
Pith. "Pith review of Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors." pith.science (2026). https://pith.science/paper/J6E6GBXI
@misc{pith2026260203972,
author = {Pith},
title = {Pith review of: Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors},
year = {2026},
howpublished = {\url{https://pith.science/paper/J6E6GBXI}},
note = {Machine review of arXiv:2602.03972}
}
abstract
The best-arm identification (BAI) problem is one of the most fundamental problems in interactive machine learning, which has two flavors: the fixed-budget setting (FB) and the fixed-confidence setting (FC). For $K$-armed bandits with a unique best arm, the optimal sample complexities for both settings have been settled down, and they match up to logarithmic factors. This prompts an interesting research question about the generic, potentially structured BAI problems: is FB harder than FC or the other way around? In this paper, we show that FB is no harder than FC up to logarithmic factors. We do this constructively: we propose a novel algorithm called FC2FB (fixed confidence to fixed budget), which is a meta algorithm that takes in an FC algorithm $\mathcal{A}$ and turn it into an FB algorithm. We prove that FC2FB enjoys a sample complexity that matches, up to logarithmic factors, that of the sample complexity of $\mathcal{A}$. This means that the optimal FC sample complexity is an upper bound of the optimal FB sample complexity up to logarithmic factors. Our result not only reveals a fundamental relationship between FB and FC, but also has a significant implication: FC2FB combined with existing state-of-the-art FC algorithms leads to improved sample complexity for a number of FB problems.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
Property 1=⇒Property 2 This hold by definition
-
[2]
Property 3=⇒Property 2 This hold by definition
-
[3]
Property 4=⇒Property 2 By Markov’s inequality, forT ′ δ ≥T ∗ δ P τ≥T ′ δ ≤ E[τ] T ′ δ ≤ T ∗ δ T ′ δ
-
[4]
21 Fixed Budget is No Harder Than Fixed Confidence To help with the understanding, we now discuss a few representative algorithms from the literature
Property 6=⇒Property 2 This hold by definition. 21 Fixed Budget is No Harder Than Fixed Confidence To help with the understanding, we now discuss a few representative algorithms from the literature. • Successive Elimination ((Even-Dar et al., 2006)) enjoys Property 1 and Property 3, but not Property 4 and Property 6. • LUCB1 ((Kalyanakrishnan et al., 2012...
2006
-
[6000]
33 Fixed Budget is No Harder Than Fixed Confidence K
Results are averaged over5,000trials. 33 Fixed Budget is No Harder Than Fixed Confidence K. Lemmata Lemma K.1.For the budget B and the number of stages R defined in Algorithm 3, A, Cdefined in Definition 3.1, r∗ defined in Definition B.1,δ 0 <1, and anyQ >0, the following statements hold. B≥2 Aln 1 δ0 + (C+ 1) ! ln 2 A Q ln 1 δ0 + 2(C+ 1) Q ! =⇒r ∗ ≤RandB...
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.