Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors

AI summary

Overview

Research area: theoretical machine learning, specifically pure-exploration multi-armed bandits (best-arm identification, BAI). Technical level: Advanced. This paper proves a reduction showing that the fixed-budget variant of BAI is no harder than the fixed-confidence variant up to logarithmic factors, via a meta-algorithm called FC2FB.

What This Paper Is About

Best-arm identification comes in two protocols: fixed-confidence (FC), where a learner keeps sampling until it can certify the best arm with failure probability at most δ, and fixed-budget (FB), where the learner gets exactly B pulls and must then output an answer. The paper asks whether one setting is fundamentally harder than the other for generic, possibly structured bandit problems, and answers constructively: an FC algorithm can be turned into an FB algorithm with essentially the same sample complexity, up to logarithmic factors, without needing to know the problem-dependent constants inside the FC guarantee.

Key Contributions

1. FC2FB, a meta-algorithm that converts any "strong" FC algorithm A with high-probability sample complexity T*_δ = A ln(1/δ) + C into an FB algorithm, without requiring knowledge of the constants A and C.
2. A non-asymptotic correctness guarantee (Theorem 3.2) showing that the factor A from the FC bound is preserved in the FB error guarantee up to logarithmic factors, implying that the optimal FC sample complexity upper-bounds the optimal FB sample complexity up to polylog(A, ln(1/δ)) factors.
3. FCW2S, a "boosting"/voting framework that converts a weak FC algorithm (one guaranteed only for some fixed δ₀, or with non-logarithmic dependence on 1/δ) into a strong FC algorithm, thereby relaxing the input requirement of FC2FB.
4. Applications to several FB problems — known heterogeneous noise, heterogeneous noise with unknown variance, linear bandits, and (from the introduction) unimodal and cascading bandits — where combining FC2FB with state-of-the-art FC algorithms improves existing FB sample complexity guarantees.
5. An extension, FC2AT, that turns a strong FC algorithm into an anytime algorithm (details deferred to Appendix D).

Main Findings

• FB is no harder than FC up to logarithmic factors: FC2FB converts an FC algorithm with sample complexity A ln(1/δ) + C into an FB algorithm whose sample complexity is O(Q ln(1/δ) + A ln(1/δ) · ln(A ln(1/δ)/Q) + C), which is A ln(1/δ) + C up to polylog(A, ln(1/δ)) factors, or simply up to polylog(T*_δ).
• Explicit error bound (Theorem 3.2): for δ₀ ≤ 0.5, Q ≤ B/2, and B ≥ 2(A ln(1/δ₀) + (C+1)) ln(2(A/Q) ln(1/δ₀) + 2(C+1)/Q), FC2FB satisfies ℙ(Ĵ ≠ 1) ≤ 3 exp(−B / (4Q/ln(1/δ₀) + 4A log₂(B/Q))).
• Hyperparameter guidance: δ₀ can be a constant such as 1/2 or 1/e; Q is recommended as 2K ln K in the algorithm listing, with a generic recommendation of Q = 1, Q = K for unstructured K-armed bandits and Q = d for linear bandits; guarantees hold as long as Q ≤ B/2.
• The constants need not be known: a naive warm-up framework matching FC sample complexity up to additive constant A ln 2 requires knowing A and C, which is impractical since they are problem-dependent; FC2FB removes that requirement by trying a wide range of δ values across stages.
• Known heterogeneous noise: Algorithm 5 (PE-KHN) has FC sample complexity T*δ = (64σ₁²/Δ₂²) ln(4K(ln 2)²/δ · ln²(4/Δ₂)) + Σ{j≠1} (64σ_j²/Δ_j²) ln(4K(ln 2)²/δ · ln²(4/Δ_j)), matching the lower bound of Lu et al. (2021) up to ln K terms. FC2FB(PE-KHN) with δ₀ = 1/e and Q = 1 gives ℙ(Ĵ ≠ 1) ≤ 3 exp(−B/(4 + 4A ln B)) for B ≥ 2A ln(4A) with A = Θ((σ₁²/Δ₂² + Σ_{i=2}^K σ_i²/Δ_i²) ln K).
• Concrete separation from prior FB work: on an instance with Δ₂ = 1/K⁵, Δ_i = 1/K⁴ for i = 3,…,K, σ₁² = σ₂² = 1/K⁵ and σ_i² = 1/K² for i = 3,…,K, FC2FB achieves O(K⁷) while SHVar yields O(K⁹).
• Known noise comparison (Table 1): SHVar achieves Õ(σ₁²/Δ₂² + Σ_{i=2}^K σ_i²/Δ₂²), SH (Karnin et al., 2013) achieves Õ(σ₁²/Δ₂² + Σ_{i=2}^K (σ₁² + σ_i²)/Δ_i²), and FC2FB(PE-KHN) achieves Õ(σ₁²/Δ₂² + Σ_{i=2}^K σ_i²/Δ_i²).
• Unknown-variance bounded rewards: applying FC2FB to VD-BESTARMID (Lu et al., 2021), which has complexity O(Σ_{i=1}^K (σ_i²/Δ_i² + 1/Δ_i) ln δ⁻¹) with Δ₁ := Δ₂, gives ℙ(Ĵ ≠ 1) ≤ 3 exp(−B/(4 + 4A ln B)) for B ≥ 2A ln(4A). Table 2 compares this to VBR (Faella et al., 2020), Õ(max_{i=2…K} (σ₁² + σ_i²)/Δ_i² · K), and SHAdaVar, Õ(σ_max²/Δ₂² · K); FC2FB(VD-BESTARMID) is better than each by a factor of K under the stated conditions.
• Linear bandits: the best known FC complexity reported is γ* + ρ* ln(1/δ) + d (Katz-Samuels et al., 2020), while the corresponding FB bound is (γ* + ρ*) ln(1/δ) + d, where γ* now carries a logarithmic factor. Corollary 5.4 shows FC2FB combined with Fixed Confidence Peace satisfies, for B₀ = Θ̃(γ* + ρ* + d), the bound ℙ(Ĵ ≠ 1) ≤ c exp(−B / Θ̃(ρ*) ln(B)), matching (3) up to doubly logarithmic factors. Since ρ* = Õ(H_{2,lin}) where H_{2,lin} := max_{2≤i≤d} i Δ_i^{-2} and γ* ≤ c ρ* ln(K) for a numerical constant c, the resulting complexity is no larger than that of OD-LinBAI (Yang and Tan, 2022). The authors also construct instances in Appendix G where ρ* and H_{2,lin} differ arbitrarily.
• Scope caveat: the result is a non-asymptotic reduction between sample-complexity guarantees, not a claim that a universally exponent-optimal fixed-budget algorithm exists — a question the paper notes is subtle given recent minimax (Komiyama et al., 2022) and no-complexity (Degenne, 2023) results.
• Applicability limit: FC2FB cannot be analyzed with FC algorithms that have only asymptotic stopping-time guarantees, such as Track-and-Stop (Garivier and Kaufmann, 2016).
• Background context cited: in unstructured K-armed bandits the optimal FC (Garivier and Kaufmann, 2016) and FB (Katz-Samuels and Jamieson, 2020; Zhao et al., 2023) complexities differ by a logarithmic factor, and Carpentier and Locatelli (2016) report instances where FB must suffer an extra logarithmic factor; some FB problems (e.g., K-armed bandits with heterogeneous noise, linear bandits) have best-known FB complexity orderwise smaller than their FC counterparts.
• Empirical study: the introduction states that Section 6 contains an empirical study showing the procedure can outperform existing FB algorithms; the specific results are not included in the provided text.
• Truncation note: the provided content ends mid-sentence in Section 5.4 (Unimodal Bandits), so the unimodal-bandit guarantee, the cascading-bandit case mentioned in the introduction, and the details of Section 6 and the concluding Section 7 are not reported in the available text.

Methodology in Plain English

The researchers do not invent a new sampling policy for FB; they build a wrapper. FC2FB takes an FC algorithm that is guaranteed to stop within about A ln(1/δ) + C samples, splits the total budget B into R ≈ log₂(B/Q) stages of about B/R samples each, and runs a fresh copy of the FC algorithm in each stage. Across stages the requested failure rate is loosened at a doubly exponential rate (the r-th stage uses δ₀^{L_r} with L_r = 2^{R−r}), so early stages almost never terminate in time and are force-terminated, while later stages are easy enough to finish. The first stage where the FC algorithm stops on its own supplies the returned arm, and the loop breaks. This works because the FC stopping time scales with the input δ: by covering a wide range of δ values, the wrapper is guaranteed to hit one that finishes within the per-stage budget, and the exponentially shrinking δ produces an exponentially decaying error probability in B minus a log term. A probabilistic argument converts that error-probability statement into a sample complexity via a proposition analogous to Proposition 2.1, which inverts a bound of the form F exp(−B/H) to obtain B' = Θ(H ln(F/δ) + B₀). The second ingredient, FCW2S, runs L independent copies of a weak FC algorithm in round-robin, collects votes from every copy that terminates, stops once ⌊L/2⌋ copies have terminated, and outputs the majority vote, so that the probability of a wrong majority decays exponentially and a weak guarantee becomes a strong one.

Why This Matters

Impact on research: the paper gives a general, non-asymptotic bridge between the two central BAI protocols, so new FC algorithms automatically yield new FB algorithms with comparable guarantees. This reframes the field's working assumption: the well-known logarithmic gap in unstructured bandits is a per-instance phenomenon rather than evidence that FB is generically harder, and any large (even polynomial-looking) gap between the best known FC and FB bounds for a structured problem can now be attacked by improving the FC side first.

Real-world applications (as cited or implied in the paper):

• A/B testing and multivariate testing, where deciding which variant to ship is exactly a best-arm identification problem.
• Hyperparameter optimization, where each pull of an arm is an expensive model training run and budgets are fixed in advance.
• Heteroskedastic variance designs, where arms have differing, possibly known noise levels and the fixed number of trials is planned ahead of time.
• Linear-bandit style recommendation or design problems, where arm means are linear in known feature vectors and γ*, ρ* characterize instance difficulty.
• Unimodal and cascading bandit settings (named in the introduction as application areas for the reduction).

Industry relevance: two of the authors are affiliated with Meta Inc, and the FB setting — a fixed, known number of experiments — matches industrial experimentation workflows better than FC, which requires an adaptive stopping rule. The practical payoff claimed is a concrete factor-of-K improvement over prior FB methods such as SHAdaVar and VBR in the unknown-variance regime, and orderwise improvement over SHVar in the stated heterogeneous-noise instance.

Future Directions

• Extending the reduction to FC algorithms that only have asymptotic stopping-time guarantees, such as Track-and-Stop (Garivier and Kaufmann, 2016), which the paper explicitly acknowledges FC2FB cannot currently handle.
• Determining whether the logarithmic factors in the FC-to-FB transfer can be removed, and clarifying how the reduction relates to the known extra logarithmic factor required by FB in the unstructured case (Carpentier and Locatelli, 2016).
• Fully characterizing the FB side of the structured problems covered here — for instance, whether the O(K⁷) and Õ(Σ(σ_i²/Δ_i² + 1/Δ_i)) bounds are tight, and whether ρ* and H_{2,lin} can be related beyond the arbitrarily large separation shown in Appendix G.
• Understanding the connection to the minimax (Komiyama et al., 2022) and no-complexity (Degenne, 2023) results for fixed-budget BAI, since the paper is careful to frame its contribution as a reduction between sample-complexity guarantees rather than an exponent-optimality claim.

Target Audience

Researchers and graduate students working on multi-armed bandits, pure exploration, and sequential decision making, as well as theoretically minded practitioners in experimentation platforms, recommendation, and hyperparameter tuning who want state-of-the-art fixed-budget guarantees derived from fixed-confidence machinery. Familiarity with sub-Gaussian concentration, elimination algorithms, and sample-complexity notation (Õ, Θ̃, Ω̃) is assumed, so the paper is best suited to readers with an intermediate-to-advanced background in bandit theory.

Authors’ 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.