📊 statistics

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

This paper introduces FC2FB, a novel meta-algorithm that transforms any fixed-confidence best-arm identification algorithm into a fixed-budget one, proving that the fixed-budget setting is no harder than the fixed-confidence setting up to logarithmic factors.

Original authors: Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a food critic trying to find the absolute best pizza in a city with 100 different pizzerias. You have two different ways to approach this mission, and this paper is about comparing those two strategies.

The Two Strategies

Strategy 1: The "Confidence" Approach (Fixed-Confidence or FC)
You tell the pizzeria owners: "I will keep eating slices until I am 99% sure I have found the best pizza. Then, I will stop."

The Goal: Be right with high certainty.
The Cost: You don’t know how many slices you’ll eat. It might take 10 slices, or it might take 1,000. But you stop exactly when you feel confident.

Strategy 2: The "Budget" Approach (Fixed-Budget or FB)
You tell yourself: "I have exactly $50 for pizza. I will spend it all, and then I will guess which pizzeria was the best."

The Goal: Make the best guess possible with a strict limit on resources.
The Cost: You don’t get to say "I’m 99% sure." You just have to hope your guess is right after spending your money.

The Big Question

For a long time, researchers in machine learning (the field where computers learn from data, like our pizza critic) wondered: Which strategy is harder?

Is it harder to find the best pizza when you have a strict budget (FB), or is it harder when you need to prove you’re right with high confidence (FC)?

In simple cases (like standard pizzerias), the math showed they were roughly equally hard, with only a tiny difference. But in more complex situations (like pizzerias where some are noisier than others, or where the quality follows a specific pattern), it wasn’t clear. Some experts thought the Budget approach might be significantly harder because you don’t get to stop when you’re "sure"—you just have to stop when you’re "broke."

The Paper’s Discovery

This paper proves a surprising and elegant result: The Budget approach is no harder than the Confidence approach.

In fact, they are almost the same difficulty level. If you have a great strategy for the "Confidence" approach, you can easily turn it into a great strategy for the "Budget" approach. The only penalty is a tiny, logarithmic factor (think of it as a very small overhead, like paying a tiny service fee).

The Magic Tool: FC2FB

The authors created a "meta-algorithm" (a recipe for making other recipes) called FC2FB (Fixed-Confidence to Fixed-Budget).

Think of FC2FB as a translator or a converter.

Input: You give it a "Confidence" strategy (one that stops when it’s sure).
Output: It gives you a "Budget" strategy (one that works with a fixed amount of money).

How does it work?
Imagine you have a strict budget of $50. The FC2FB translator doesn’t just spend the money randomly. It breaks the $50 into small chunks.

It tries the "Confidence" strategy with a very low confidence requirement (e.g., "I’m only 50% sure").
If the strategy finishes early, great! It gives you an answer.
If it doesn’t finish, the translator moves to the next chunk of money and tries again with a slightly higher confidence requirement.
It keeps doing this, getting more and more confident, until it either finds the answer or runs out of money.

Because it starts with low confidence and ramps up, it efficiently uses the budget. It proves that you don’t need to know the "secret numbers" of the pizzerias (like how noisy or difficult they are) to make this work.

Why Does This Matter?

Before this paper, if you wanted to solve a complex problem with a fixed budget (like optimizing a robot’s movement with limited battery life), you had to invent a new, specific algorithm from scratch.

Now, thanks to FC2FB:

You can reuse old work: If someone already invented a great "Confidence" algorithm for a complex problem, you can just plug it into FC2FB to get a great "Budget" algorithm.
Better results: In several complex scenarios (like when the "noise" or uncertainty varies between options, or when the options have a linear structure), the new Budget algorithms created by FC2FB are actually better than the best existing Budget algorithms. They use fewer samples (or less money) to get the right answer.

Real-World Examples Mentioned in the Paper

The paper shows this works for:

Heterogeneous Noise: Imagine some pizzerias are very consistent (low noise) and others are wildly inconsistent (high noise). FC2FB handles this better than old methods.
Linear Bandits: Imagine the quality of pizza depends on a linear combination of ingredients (like cheese + pepperoni). FC2FB improves the efficiency here.
Unimodal Bandits: Imagine the pizzerias are arranged in a line, and quality goes up to a peak and then down (like a mountain). FC2FB can find the peak more efficiently than previous methods.

In Simple Terms

The paper says: "Don’t worry about the difference between having a strict budget and needing high confidence. They are essentially the same problem. If you have a good way to be confident, we can easily convert it into a good way to stay within budget, with almost no loss in efficiency."

It’s like discovering that if you know how to bake a perfect cake when you have unlimited time, you can also figure out how to bake a nearly perfect cake in exactly 30 minutes, using a simple, universal trick.

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

Problem Statement
The paper addresses the Best-Arm Identification (BAI) problem in interactive machine learning, specifically focusing on the relationship between two standard settings: Fixed-Confidence (FC) and Fixed-Budget (FB). In the FC setting, a learner aims to identify the best arm with a failure probability no greater than $\delta$ , minimizing the sample complexity (stopping time). In the FB setting, the learner is given a fixed sampling budget $B$ and aims to minimize the probability of error. While optimal sample complexities for unstructured $K$ -armed bandits in both settings are known to match up to logarithmic factors, it has been unclear whether this relationship holds for generic, potentially structured BAI problems. Specifically, the authors investigate whether FB is fundamentally harder than FC, or vice versa, noting that existing literature shows mixed results, including cases where FB algorithms suffer an extra logarithmic factor or where known FB complexities are order-wise smaller than FC counterparts.

Methodology
The authors propose a constructive reduction framework to demonstrate that FB is no harder than FC up to logarithmic factors. The core contribution is a novel meta-algorithm called FC2FB (Fixed Confidence to Fixed Budget).

FC2FB Algorithm: This meta-algorithm takes an FC algorithm $\mathcal{A}$ as input and transforms it into an FB algorithm. It operates by dividing the total budget $B$ into $R$ stages. In each stage $r$ , it runs the input FC algorithm $\mathcal{A}$ with a specific failure rate $\delta_r$ that increases at a doubly exponential rate across stages. If $\mathcal{A}$ self-terminates within the allocated sub-budget for that stage, FC2FB accepts its output and stops. If $\mathcal{A}$ does not terminate, the stage is force-terminated, and the algorithm proceeds to the next stage with a higher failure rate (lower confidence requirement).
Strong vs. Weak FC Algorithms: The authors define "strong" FC algorithms as those with high-probability sample complexity scaling logarithmically with $1/\delta$ (i.e., $T^*_\delta = A \ln(1/\delta) + C$ ). They initially analyze FC2FB assuming a strong FC input.
FCW2S Framework: To handle cases where only a "weak" FC algorithm is available (one that satisfies guarantees for a constant $\delta_0$ or lacks logarithmic dependence on $1/\delta$ ), the authors introduce FCW2S (Fixed-Confidence Weak to Strong). This meta-framework runs $L$ independent instances of a weak FC algorithm in parallel using round-robin allocation. It aggregates outputs via majority voting among terminated instances to produce a strong FC guarantee. This allows FC2FB to be applied to a broader class of algorithms.

Key Contributions and Results

Theoretical Guarantee: The authors prove that FC2FB preserves the sample complexity of the input FC algorithm up to polylogarithmic factors. Specifically, if an FC algorithm has sample complexity $T^*_\delta = A \ln(1/\delta) + C$ , the resulting FB algorithm via FC2FB achieves an error probability bound that implies a sample complexity of $\tilde{O}(A \ln(1/\delta))$ . This establishes that the optimal FC sample complexity serves as an upper bound for the optimal FB sample complexity up to logarithmic factors.
Applications to Structured Bandits: The paper demonstrates that combining FC2FB with state-of-the-art FC algorithms improves sample complexity guarantees for several FB problems:
- Heterogeneous Noise (Known Variance): Applying FC2FB to a phased elimination algorithm yields a sample complexity of $\tilde{O}(\sum_{i=2}^K \frac{\sigma_i^2}{\Delta_i^2})$ , which is order-wise smaller than existing FB algorithms like SHVar ( $\tilde{O}(\sum_{i=2}^K \frac{\sigma_i^2}{\Delta_2^2})$ ) in specific instances.
- Heterogeneous Noise (Unknown Variance): Using FC2FB with VD-BESTARMID improves upon existing FB bounds (e.g., VBR) by factors of $K$ in regimes where the best arm’s variance is significantly larger than others.
- Linear Bandits: FC2FB combined with the Fixed Confidence Peace algorithm achieves a sample complexity matching the FC lower bound up to doubly logarithmic factors, improving upon previous FB results that had extra logarithmic dependencies on instance-dependent constants.
- Unimodal Bandits: By first converting a weak FC algorithm (UniTT) to a strong one via FCW2S, and then applying FC2FB, the authors achieve an FB sample complexity dependent on local information-theoretic quantities ( $T_\mu(\delta)$ ), which is order-wise smaller than the global gap-dependent complexity ( $\Delta^{-2}$ ) of existing FB algorithms.

Significance and Claims
The paper claims to reveal a fundamental relationship between FB and FC settings, resolving the question of relative difficulty by showing that FB is no harder than FC up to logarithmic factors. The significance lies in the practical utility of the FC2FB meta-algorithm: it allows researchers to transfer superior sample complexity guarantees from the FC literature to the FB setting. This provides a systematic way to construct FB algorithms with improved theoretical guarantees for various structured bandit problems. The authors note that their result is a non-asymptotic reduction between sample-complexity guarantees and does not assert the existence of a universally exponent-optimal FB algorithm. Empirical results on Gaussian bandits support the theoretical findings, showing that FC2FB outperforms existing FB algorithms like Sequential Halving (SH) and SHVar in terms of misidentification probability across varying budgets and numbers of arms.