When evaluating a large pool of candidates—whether they are machine learning models, hyperparameter configurations, prompt variations, or even data points in a clustering algorithm—the traditional approach relies on uniform evaluation. If you have 100 candidate models, you might test every single one on the same 1,000 validation examples.
This uniform allocation of resources is simple, but it wastes an immense amount of computation and time. To find the single best candidate, you do not need a highly precise estimate of exactly how poor the underperforming candidates are; you only need enough evidence to confidently reject them.
A rapidly growing body of research addresses this bottleneck by framing evaluation as a Multi-Armed Bandit (MAB) problem, specifically focusing on Best-Arm Identification. By dynamically shifting evaluation resources away from poor performers and toward the most promising options, these techniques drastically cut down the computational, financial, and human costs of selection.
The Core Insight: Shifting from Estimation to Identification
To understand why bandit-based evaluation works, consider the difference between estimation and identification.
In a standard evaluation setup, your goal is to accurately estimate the true performance score of every candidate. If you are evaluating text-to-image generative models using a metric like the Fréchet Inception Distance (FID), uniform evaluation requires generating tens of thousands of samples for every single model to get tight error bars on their scores.
Bandit-based evaluation changes the goal: the objective is solely to identify the best model with high statistical confidence. In this framework:
- Each candidate is treated as an arm of a multi-armed bandit.
- A pull of an arm corresponds to a single, incremental evaluation step (e.g., testing a model on one more data point, generating one more image, or calculating a single distance metric).
- The reward is the performance observed during that step.
By tracking the running average and the uncertainty (confidence intervals) for each candidate, an adaptive algorithm can make real-time decisions about where to spend the next unit of its evaluation budget.
Uniform Evaluation (Wasteful):
Candidate A: [-------------------] (1000 tests)
Candidate B: [-------------------] (1000 tests) -> Clearly bad, yet fully evaluated
Candidate C: [-------------------] (1000 tests)
Bandit-Based Evaluation (Efficient):
Candidate A: [-------------------] (1000 tests) -> Top contender
Candidate B: [--] (50 tests) -> Discarded early
Candidate C: [------------] (600 tests) -> Explored until confidence was reached
The Mechanics of Adaptive Allocation
How do these algorithms know when to stop evaluating a bad candidate? They primarily leverage two adaptive strategies: Successive Rejects and Optimistic Sampling.
Successive Rejects and Early Stopping
In frameworks utilizing successive rejects, the evaluation proceeds in phases. At the end of each phase, the worst-performing candidates are permanently discarded, and the remaining budget is split among the survivors.
For example, Jerry Li et al. implemented this in Automatic Prompt Optimization with "Gradient Descent" and Beam Search to optimize large language model (LLM) prompts. Instead of testing dozens of generated prompt variations across an entire dataset, their algorithm uses a small data sample to quickly filter out low-performing prompts, focusing the remaining evaluation budget entirely on the top contenders. Similarly, the FIESTA framework proposed by Henry B. Moss et al. in FIESTA: Fast IdEntification of State-of-The-Art models using adaptive bandit algorithms adaptively cuts off underperforming machine learning models early, identifying the state-of-the-art model with up to 50% fewer total evaluations.
Optimistic Sampling (UCB and Thompson Sampling)
Other approaches use continuous allocation rules like the Upper Confidence Bound (UCB) algorithm or Thompson Sampling. These methods choose the next candidate to test based on an "optimistic" estimate of its performance—the sum of its current average score and its uncertainty.
If a candidate has a high average score, it gets tested more to verify its leadership (exploitation). If a candidate has been tested very little, its uncertainty is high, which also makes it a candidate for testing (exploration). As soon as a candidate's upper confidence bound falls below the performance of the current leaders, the algorithm stops sampling it entirely.
This mechanism is highly effective across diverse domains:
- Generative Models: Parham Rezaei et al. applied UCB in Why Settle for Mid: A Probabilistic Viewpoint to Spatial Relationship Alignment in Text-to-image Models to allocate image generation budgets efficiently when ranking text-to-image models. In A Multi-Armed Bandit Approach to Online Selection and Evaluation of Generative Models, Xiaoyan Hu et al. demonstrated that online bandit sampling significantly reduces the sample size needed to compute reliable generative metrics like FID.
- Data Discovery: Yue Gong et al. utilized Thompson Sampling in METAM: Goal-Oriented Data Discovery to navigate massive data lakes, achieving a six-fold reduction in queries when identifying the most impactful datasets for downstream machine learning tasks.
Slashing Complexity Across Domains
The mathematical shift from uniform sampling to best-arm identification fundamentally alters the computational complexity of many classic algorithms.
From Quadratic to Near-Linear Time in Geometry
Finding the medoid—the most central, representative point in a dataset—traditionally requires calculating all pairwise distances, a grueling $O(n^2)$ operation.
Vivek Bagaria et al. bypassed this bottleneck in Medoids in Almost-Linear Time via Multi-Armed Bandits by treating every data point as an arm. By calculating distances only to a randomly sampled subset of the data, their algorithm (Med-dit) identifies the exact medoid in $O(n \log n)$ time. This breakthrough was scaled to clustering by Mo Tiwari et al. in BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits, which reduces the per-iteration complexity of $k$-medoids clustering to near-linear time without sacrificing clustering accuracy. A parallel approach was taken by Pratik Jawanpuria et al. in ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits, using approximate best-arm identification to drastically minimize similarity queries during unsupervised prototype selection.
Minimizing Human Evaluation Effort
In fields like Information Retrieval (IR) and Machine Translation (MT), evaluation relies heavily on expensive human judgments. Bandit allocation ensures human annotators only review the most informative items.
In the TREC 2017 Common Core Track Overview, James Allan et al. detailed how treating retrieval systems as arms allows for dynamic document pooling. Instead of statically collecting a fixed number of documents from every search engine, the system dynamically prioritizes documents from systems that demonstrate a high historical yield of relevant results. Aldo Lipani formalized this in On Biases in Information Retrieval Models and Evaluation, framing document pooling as a reinforcement learning problem to maximize relevance discovery under a strict human assessment budget.
For language translation, Vânia Mendonça et al. demonstrated in Online Learning Meets Machine Translation Evaluation: Finding the Best Systems with the Least Human Effort that an online bandit framework can successfully identify top-tier translation models using just a few hundred human feedback iterations.
Budgeted Model Selection and Hyperparameter Tuning
When computation itself is constrained, bandits optimize how training time is distributed. Alekh Agarwal et al. provided foundational theoretical backing for this in Oracle inequalities for computationally budgeted model selection, proving that an iterative allocation of training time based on optimistic performance bounds can match the selection quality of an all-knowing oracle.
For modern large-scale models, Jin Peng Zhou et al. showed in On Speeding Up Language Model Evaluation that combining multi-armed bandits with low-rank matrix factorization allows practitioners to evaluate LLMs across thousands of prompts while saving up to 95% of the typical evaluation budget.
Maintaining Statistical Rigor
One natural concern with adaptive sampling is that it introduces selection bias: because you sample high-performing models more frequently, standard statistical tests (like classical p-values) become invalid.
To counter this, recent frameworks pair adaptive sampling with modern sequential verification tools. For instance, Matteo Zecchin et al. introduced the Adaptive Learn-then-Test (aLTT) framework in Adaptive Learn-then-Test: Statistically Valid and Efficient Hyperparameter Selection. By replacing static p-values with sequential "e-processes," their method allows an epsilon-greedy bandit policy to aggressively focus the testing budget on promising hyperparameter configurations while still providing rigorous, mathematically valid guarantees on final model performance.
On the algorithmic side, the theoretical foundations of these selection mechanisms continue to mature. In Top Two Algorithms Revisited, Marc Jourdan et al. generalized the "Top Two" family of bandit algorithms to non-parametric distributions. These algorithms function by balancing the selection of the current empirical leader with a penalized challenger, ensuring optimal computational efficiency without requiring heavy re-sampling overhead.
Conclusion
Bandit-based candidate selection works because it aligns the computational effort directly with the decision-making goal. Whether applied to molecular docking simulations (Bin Chong et al. in Reinforcement learning to boost molecular docking upon protein conformational ensemble), search engine benchmarking, or LLM prompt engineering, the underlying intuition remains identical: stop wasting resources on measuring exactly how bad a bad candidate is, and spend your budget distinguishing the great from the good.
Key Foundational Work
Oracle inequalities for computationally budgeted model selection (2011) — contributed 2 concept elements to this direction.
TREC 2017 Common Core Track Overview (2017) — contributed 2 concept elements to this direction.