Imagine you are running a clinical trial with a strict limit on the number of patient tests you can perform, or you are tuning a massive machine learning model with a hard cap on your cloud computing budget. You have several options ("arms"), and you want to find the single best one.
In the world of multi-armed bandits, this is known as pure exploration. Pure exploration problems generally fall into two categories:
- Fixed-Confidence: You sample options until you reach a target certainty level (e.g., 95% confidence), minimizing the number of samples required.
- Fixed-Budget: You are given a strict, non-negotiable allocation of $T$ samples. Your goal is to maximize the probability of identifying the correct arm when the budget expires.
While fixed-confidence settings are well-characterized by algorithms like Track-and-Stop from [Aurélien Garivier] et al. in Optimal Best Arm Identification with Fixed Confidence, adapting these strategies to a fixed budget is notoriously difficult. As noted by [Po-An Wang] et al. in On Universally Optimal Algorithms for A/B Testing, a fixed budget prevents the use of stopping rules based on confidence intervals. You cannot simply run a fixed-confidence algorithm and cut it off early; doing so often yields poor performance because the algorithm did not plan its allocation around a hard deadline.
The Fundamental Challenge: Unknown Instance Complexity
Why is the fixed-budget setting fundamentally harder? The core issue is that the learner must commit to a sampling strategy without knowing the inherent difficulty of the problem instance beforehand.
In a fixed-confidence setting, if the top two arms have nearly identical rewards (a small "gap"), the algorithm automatically samples longer to resolve the ambiguity. In a fixed-budget setting, the total number of samples is fixed regardless of whether the problem is easy or hard.
[Alexandra Carpentier] et al. formalized this difficulty in Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem. They proved that because a learner cannot observe the problem's complexity before the budget is exhausted, it incurs an unavoidable logarithmic penalty ($\log K$, where $K$ is the number of arms) in its error probability compared to an oracle that knows the gaps in advance. This theoretical barrier forces fixed-budget algorithms to adopt entirely different allocation mechanisms.
How It Works: Successive Rejection and Elimination
To maximize accuracy within a strict cap, successful algorithms must aggressively manage their resource allocation over time. The dominant paradigm for achieving this is Successive Rejection (or Successive Elimination).
Instead of trying to maintain uniform confidence intervals across all arms for the entire duration, a successive rejection framework divides the total budget $T$ into discrete phases.
Total Budget (T)
|-------------------|-------------------|---------|---|
Phase 1: Phase 2: Phase 3: ...
Pull all K arms Drop worst arm. Drop next.
Pull remaining.
- Equal Allocation per Phase: In the first phase, the algorithm distributes a portion of the budget equally across all $K$ available arms.
- Discarding the Weakest: At the end of the phase, the arm with the lowest empirical average is permanently discarded.
- Reallocating the Surplus: In the next phase, the remaining arms are sampled again, but because there are fewer arms, each receives a larger share of the remaining budget.
This geometric scheduling ensures that clear losers are filtered out early, saving the bulk of the budget for the subtle, hard-to-distinguish differences between the top contenders. As shown by [Jasmin Brandt] et al. in Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget, this elimination strategy provides a robust buffer against wasting budget on suboptimal choices.
Variance-Aware Allocation
While basic elimination strategies rely purely on empirical means, more sophisticated approaches incorporate variance to optimize budget spending. If an arm has a high average reward but also high variance, it requires more samples to confirm its true quality than a stable, low-variance arm.
[Subhojyoti Mukherjee] et al. leveraged this intuition in Thresholding Bandits with Augmented UCB. By tracking empirical variance alongside mean estimates, algorithms can strategically allocate pulls so that confidence intervals narrow precisely where decisions are most ambiguous. This prevents the algorithm from wasting budget on arms that are either safely above or hopelessly below the target performance threshold, a principle also explored by [Pierre Gaillard] et al. in Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits.
Beyond Simple Arms: Structured Search Spaces
The intuition of fixed-budget allocation extends to more complex, high-dimensional environments where pulling an arm reveals structural information about other choices:
- Linear Bandits: When arms are vectors in a shared linear space, sampling one arm provides information about all others. [Ayya Alieva] et al. in Robust Pure Exploration in Linear Bandits with Limited Budget and [Recep Can Yavas] et al. in Fixed-Budget Best-Arm Identification in Sparse Linear Bandits demonstrate how algorithms can combine experimental design with elimination to isolate the most informative directions within a strict sample cap.
- Multi-Feasibility and Multi-Objective Constraints: Often, the "best" arm must satisfy multiple criteria or constraints (e.g., maximizing drug efficacy while minimizing side effects). [Julian Katz-Samuels] et al. in Top Feasible Arm Identification showed that under a fixed budget, the learner must adaptively balance whether to spend samples verifying an arm's performance or verifying its feasibility.
Ultimately, fixed-budget best-arm identification works because it treats exploration not as a task of reaching absolute certainty, but as an exercise in optimal resource rationing under a hard deadline.