Adaptive Candidate Selection via Multi-Armed Bandits

27 concepts17 papers1 proposal

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:


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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adaptive_resource_allocation_bandit_base_81f380b8,
  title = {adaptive resource allocation (bandit-based evaluation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-resource-allocation-bandit-based-evaluation/rdr_81f380b879fe40aca128249d0ceef4a0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_adaptive_resource_allocation_bandit_base_81f380b8_v1,
  title = {adaptive resource allocation (bandit-based evaluation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-resource-allocation-bandit-based-evaluation/rdr_81f380b879fe40aca128249d0ceef4a0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake