Best-Arm Identification

Follow this topic Ask about this topic

Momentum

3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 26

Oct 7, 2026stat.ML

Best Arm Identification for Bandits with Shifting Means

We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the

K

arms are stable in time, in Shifting Means only the gaps

\boldsymbolΔ

between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means (

\mathsf{ISM}

). Assuming means bounded by

U

and

σ^2

-sub-Gaussian rewards, we show

\mathsf{ISM}

to be

δ

-correct and to enjoy a sample complexity bound of order

K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ

. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.

Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal +2

CWI and Booking.com Science Park 123 1098 XG Amsterdam · CWI and University of Twente Science Park 123 1098 XG Amsterdam · Indian Institute of Science (IISc), Bengaluru CV Raman Rd, Bengaluru, Karnataka 560012, India +2

Multi-Armed Bandits Best-Arm Identification Non-Stationary Bandits

Oct 1, 2026cs.LG

Sharp Non-Asymptotic Analysis of the Penalized Challenger in $β$ -EB-TCI for Bernoulli Bandits

Top-two algorithms are simple and effective for fixed-confidence best-arm identification, but their sharp non-asymptotic behavior is still not well understood. We study this problem for Bernoulli bandits through

β

-EB-TCI, the empirical-best top-two rule of Jourdan et al., whose challenger is chosen using a Bernoulli transportation cost with a logarithmic count penalty. We prove that, after the empirical leader has become the true best arm and its sampling fraction stays close to

β

, the stopping time is

T_β^{\star}(μ)\log(1/δ)

up to lower-order concentration terms. We also show that, in this regime, every challenger is sampled linearly often. Thus, for the original algorithm without forced exploration, the main remaining difficulty is to control when the empirical leader becomes permanently correct. These results imply a non-asymptotic high-probability bound for all Bernoulli instances with a unique best arm. If the algorithm satisfies a finite-mean sufficient-exploration condition, the bound further yields the sharp expected sample complexity. In particular, this gives the sharp expectation result for the unguarded Bernoulli rule when all arm means are pairwise distinct, using the sufficient-exploration result of Jourdan et al. Finally, if we add a mild forced-exploration rule that contributes only

O(\sqrt{Kt})

pulls up to time

t

, we obtain a self-contained expected sample-complexity theorem for any number of arms under the unique-best-arm assumption. We also identify a limitation of proof strategies that try to handle equal suboptimal means through a single index-comparison argument.

Nam Nguyen, Tuan Quang Dam

Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam

Multi-Armed Bandits Best-Arm Identification

Sep 22, 2026cs.LG

Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices

Exhaustively evaluating every candidate LLM configuration on every benchmark item to identify a high-performing one is costly. We formulate configuration selection as a cost-aware Bayesian bandit problem and propose GittinsEval, which draws on the Bayesian-optimal Gittins policy to determine which configuration to evaluate next and when to stop. We extend the policy with an anytime recommendation rule over both fully and partially evaluated configurations, using an LCB-style score to account for posterior uncertainty. GittinsEval is computationally efficient, requiring only lightweight online updates after offline precomputation. Across GSM8K, PIQA, AlpacaEval, and MMLU response matrices, GittinsEval is consistently competitive, with particularly strong gains over configuration-level Bayesian optimization on large-example benchmarks and over cost-unaware bandit baselines on large-candidate tasks. Crucially, GittinsEval often attains near-zero simple regret using only 1% to 2% of the exhaustive-evaluation cost; it also offers an adaptive stopping rule that typically triggers at 1% to 10%.

Qian Xie, Yueli He, Nairen Cao

Cornell University · Columbia University · New York University +1

Multi-Armed Bandits LLM Evaluation Language Model Generation Evaluation Best-Arm Identification

Sep 9, 2026cs.LG

A positive resolution of the gap-entropy conjecture

We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in

[0,1]

, and a unique optimal arm. For each suboptimal arm

i

, let

Δ_i=μ_*-μ_i

be its gap from the optimal mean, and write

H=\sum_{i\ne *}Δ_i^{-2}

. Let

p_r

be the fraction of

H

contributed by arms with

2^{-(r+1)}<Δ_i\le2^{-r}

, and let

\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)

. Among all algorithms that identify the optimal arm with probability at least

1-δ

on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of

H(\log(1/δ)+\mathrm{Ent}(I))

. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus

g^{-2}\log\log(e^e/g)

, where

g=\min_{i\ne *}Δ_i

is the gap to the closest competitor.

P. M. Aronow, Nathan Kallus, Patrick Lopatto

Best-Arm Identification Information-Theoretic Lower Bounds

Aug 4, 2026cs.CL

Dynamically Allocating Evaluation Effort for Model Ranking

While human evaluation is the gold standard in many NLP tasks, it suffers from prohibitive costs and poor scalability. When identifying top-performing models, typical evaluation protocols waste effort by exhaustively evaluating all models on the entire benchmark, a safe but inefficient approach. In this work, we formalize multi-model human evaluation as a best-arm identification problem in a multi-armed bandit setup with correlated arms, where pulling an arm corresponds to human-evaluating a model. By sampling adaptively based on the intermediate model rankings obtained on the samples so far, we can focus the annotation budget on the most competitive models. We prove the optimality of the proposed algorithms and show that it improves discrimination between top-performing models. This makes evaluations faster, cheaper and more aligned with large-scale competition evaluation goals.

Vilém Zouhar, Julia Kreutzer, Alon Lavie +4

ETH Zurich · Cohere Labs · Carnegie Mellon University +3

Model Selection Multi-Armed Bandits Human-in-the-Loop Evaluation Best-Arm Identification

Aug 2, 2026stat.ML

Dominant Arm Identification with Mixing and Recycling Observed Samples

We study the problem of identifying the dominant arm in multi-armed bandits, where the objective is to find the action with the highest probability of exceeding the realized rewards of all other actions. Conventional mean-based and pairwise comparison-based algorithms often fail to identify the arm with the highest realized reward. To address this challenge, we introduce a novel dominant arm criterion and an efficient estimator with theoretical guarantees. Our approach relies on two key technical innovations: (i) a dominance score criterion that an arm beats the locally dominant over the partitioned reward space and (ii) a joint mixing and recycling mechanism coupled with a doubly robust estimator that guarantees simultaneous convergence of the empirical distribution functions for all arms. These key innovations pave a way to efficient computation of global arm dominance. Our proposed elimination algorithm identifies the best dominant arm with nearly optimal rate of sample complexity. Numerical experiments demonstrate that our algorithm consistently achieves exact recovery of the true dominant arm, outperforming existing baselines.

Jonghyun Sim, Wonyoung Kim

Chung-Ang University, Seoul, Republic of Korea.

Multi-Armed Bandits Best-Arm Identification

Jul 16, 2026cs.LG

MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

We design and analyze \underline{M}echanism-\underline{E}nforced \underline{S}equential \underline{HA}lving (MESHA), an algorithm for Best Arm Identification (BAI) in strategic linear bandits. In this setting, each arm may strategically misreport its feature vector to maximize the probability of being identified as the best arm, when rewards are generated from the arms' true but unobservable features. The design of MESHA applies the naïve uniform sampling rule and an epoch-wise Grim Trigger Condition (GTC): the former reduces the impact of arms' strategic behaviours and the latter eliminates arms whose reported features severely deviate from the ground truth. Considering an arbitrary Nash Equilibrium, we prove that any arm would attempt to pass the GTC check to maximize its identified probability and derive an upper bound on the failure probability of MESHA within a fixed budget

T

. We also show that state-of-the-art linear BAI algorithms with

G

-optimal design would fail in such strategic environment, as the optimal design (OD)-based sampling rule based on strategically reported features may {\it starve} the optimal arm of any sampling budget. Finally, extensive numerical experiments indicate that MESHA outperforms baselines that rely on OD-based sampling rules as well as the feature-agnostic baselines, corroborating the efficacy of MESHA.

Xin Li, Zixin Zhong

Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou)

Multi-Armed Bandits Mechanism Design Sequential Decision Making Best-Arm Identification

Jul 13, 2026cs.LG

Fundamental Limitations of Fixed-Budget Best-Arm Identification

In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across

K

arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any

K\ge 3

and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most

\left(1 + \frac{\log(K)}{8}\right)^{-1}

times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.

Motti Goldberger

Yale University

Multi-Armed Bandits Best-Arm Identification Information-Theoretic Lower Bounds

Jul 9, 2026cs.LG

Optimal Top- $k$ Identification from Pairwise Comparisons

We study the active learning problem of fixed-confidence top-

k

identification from noisy pairwise comparisons. In this problem, an algorithm sequentially chooses pairs of items to compare, observes the outcomes, and stops when it can return the set of top-

k

items with error probability at most

δ

. The objective is to design such a

δ

-correct procedure that minimizes the expected number of comparisons (the sample complexity). This problem falls within the broader literature on fixed-confidence pure exploration in bandit models, where a common target is asymptotic optimality: the algorithm's expected sample complexity matches the information theoretic lower bound as

δ\to 0

. Asymptotically optimal procedures have been developed for a range of fixed-confidence pure-exploration problems, however to the best of our knowledge, for top-

1

, or more generally top-

k

identification from pairwise comparisons under latent utility models an asymptotically optimal algorithm has not been established. In this setting, we develop such an algorithm. We characterize the structure of the lower bound and formulate it as a saddle-point problem. This structure enables a computationally efficient primal-dual procedure that learns the asymptotically optimal comparison allocation online. We then construct an adaptive comparison-allocation algorithm that tracks the allocation learned by the primal-dual procedure and prove it is asymptotically optimal.

Motti Goldberger, Nils Rudi

Yale University, New Haven, CT, USA.

Pairwise Preference Learning Multi-Armed Bandits Pairwise Comparison Pairwise Preference Evaluation Pairwise Ranking Best-Arm Identification

Jul 8, 2026cs.LG

Best-Arm Identification with Generative Proxy

Best-arm identification is a canonical model for data-driven decision-making, but in many applications each reward observation is costly. Motivated by the growing availability of cheap predictions from machine learning and large language models, we study fixed-confidence best-arm identification in which each costly reward pull is paired with a cheap but correlated proxy score. The marginal mean of the proxy can be estimated offline and is treated as known, whereas its correlation

ρ

with the reward, which governs how much the proxy helps, is unknown and must be learned online in pair with real rewards. We show that a control-variate adjustment turns this model into a heteroscedastic identification problem whose oracle sample complexity improves by residual variance

1-ρ^2

. The central difficulty is that the correlation must be learned from the same costly samples that identification consumes online, and that a plug-in estimate of the residual variance is anti-conservative and can compromise correctness. We propose PROBE (PRoxy OLS for Best-arm Exploration), a phase-elimination algorithm that directly maintains an upper certificate on the residual variance with an ordinary least squares fit, whose exact chi-square law keeps the certificate valid regardless of the unknown correlation. We prove that PROBE is

δ

-PAC and attains the known-correlation oracle sample complexity up to a constant multiplicative factor and a constant additive calibration cost. The guarantee extends to the

(ε,δ)

-PAC setting under minimal changes to the algorithm. Numerical experiments on synthetic instances and on an auto-loan pricing replay with large language model and tabular proxies confirm that the sample savings of PROBE scale with the strength of the reward-proxy correlation, exactly as the theory predicts.

Tianyi Ma, Hanzhang Qin, Ruihao Zhu +1

School of Operations Research and Information Engineering, Cornell University · Department of Industrial Systems Engineering and Management, National University of Singapore · SC Johnson College of Business, Cornell University +1

Multi-Armed Bandits Best-Arm Identification

Jul 5, 2026stat.ML

Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis

This paper studies the problem of identifying the treatment that maximizes the expected natural direct potential outcome (NDPO), which captures the potential outcome of an intervention while excluding the pathway transmitted through a mediator that researchers may wish to remove from evaluation. We first establish population-level identification of the expected NDPO in a causal bandit setting using observable interventional distributions. We then develop a fixed-confidence best-arm identification (BAI) algorithm based on the Track-and-Stop (TaS) framework, employing a cutting-set method to solve the resulting semi-infinite optimization problem. The proposed algorithm achieves sample-efficient identification with a high-probability correctness guarantee. We prove that it satisfies

δ

-correctness and asymptotic optimality. Finally, we validate the approach through empirical evaluations on a large-scale real-world advertising dataset (IPinYou).

Harsh Shrivastava, Yuta Kawakami, Junpei Komiyama +1

Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi, UAE · RIKEN AIP, Tokyo, Japan

Multi-Armed Bandits Causal Effect Estimation Causal Mediation Analysis Best-Arm Identification Causal Inference

Jun 28, 2026cs.LG

Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition

We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation. Subject to an abstention budget

α

, we analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining. Our central finding is that abstention induces a phase transition: without abstention, the error probability decays polynomially in the sampling budget

T

; in contrast, introducing any small positive abstention budget shifts this to an exponential decay. For Gaussian priors and rewards, in the regime

T\to\infty

followed by

α\downarrow0

, we establish exact matching information-theoretic lower bounds and algorithmic upper bounds on the optimal error exponent, which takes the form

\exp(-\frac{α^{2}T}{8κ_ν^{2}})

. The hardness parameter

κ_ν

represents the prior density of the top-two gap at zero, highlighting that nearly tied instances drive the fundamental error. We introduce an adaptive algorithm, PGWS, that successfully achieves this optimal exponent by expending its abstention budget on statistically ambiguous instances. We further demonstrate that this polynomial-to-exponential improvement is exclusively a Bayesian phenomenon--in the frequentist setting, abstention only affects lower-order exponent terms. We also extend our results beyond the Gaussian model.

Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan

Department of Mathematics, National University of Singapore · Department of Electrical and Computer Engineering, National University of Singapore

Multi-Armed Bandits Best-Arm Identification Bayesian Decision Theory

Jun 20, 2026cs.LG

Ranking-and-Selection with Multiple Correct Answers and Non-Answerable Estimates

We study fixed-precision ranking-and-selection in structured settings where the answer may be non-unique and where noisy estimates may temporarily admit no valid answer at all. This phenomenon arises naturally in problems such as multi-fidelity ranking-and-selection and identifying a Condorcet winner from pairwise comparisons. To address this, we propose a unified framework based on answer-wise acceptance sets, restricted generalized likelihood ratio stopping, and an answer-pitfall decomposition that yields a max-max-min characteristic value and a common sampling principle. We introduce ENDS, a general procedure that combines estimation, nomination, pitfall detection, and cost-aware information-directed selection. We instantiate ENDS for various problems by deriving explicit formulas. Extensive numerical experiments show that this unified recipe performs well across a broad range of pure-exploration problems and offers a practical framework and proof-of-concept algorithmic recipe.

Qiaoqiao Wang, Wei You

Dept. of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology, Hong Kong, China

Best-Arm Identification Adaptive Sampling Sequential Hypothesis Testing

Jun 8, 2026cs.LG

Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

Motivated by the recency effect in online learning, we study algorithms for single-pass sliding-window streaming multi-armed bandits (MABs) in this paper. In this setting, we are given

n

arms with unknown sub-Gaussian reward distributions and a parameter

W

. The arms arrive in a single-pass stream, and only the most recent

W

arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.

Vladimir Braverman, Chen Wang, Liudeng Wang +1

Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University

Multi-Armed Bandits Best-Arm Identification Streaming Algorithms

Jun 5, 2026cs.LG

Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity

Large Language Models are typically benchmarked by evaluating every model on every test query. For practitioners seeking the best model to deploy, this is often wasteful: if a model clearly performs worse than others, there is no need to precisely estimate its performance. Best-arm identification algorithms can be naturally applied to drastically reduce costs by adaptively allocating evaluation budget. Further, language models often respond similarly to the same prompt-a property previous work has tried to leverage with mixed success. We propose Synchronized Successive Rejects (SySRs), augmenting the classical Successive Rejects algorithm with paired comparisons. Unlike prior attempts to leverage model similarity in best-model identification, our approach is hyperparameter-free and enjoys performance guarantees that improve with the degree of similarity between evaluated models. Empirically, our method outperforms all baselines in terms of average error rate across 15 standard benchmarks, and in terms of worst-case budget for reliably identifying the best model.

Zifan Lyu, Chahine Nejma, Tobias Wegel +2

1ETH Zurich · 2Centrale Sup´elec · 3ENS de Cachan +1

Model Selection Multi-Armed Bandits LLM Evaluation Language Model Generation Evaluation Best-Arm Identification

Jun 3, 2026cs.LG

Provably Reduced Sample Cost in Prior-Guided Hyperparameter Optimization

Large-scale hyperparameter optimization (HPO) in automated machine learning (AutoML) consumes substantial computational resources, raising growing concerns about scalability and energy efficiency. Existing methods use prior information heuristically to accelerate both black-box and multi-fidelity settings, but they lack a characterization of how prior informativeness quantitatively reduces sample complexity. In this work, we provide the first distribution-dependent sample complexity bounds for multi-fidelity HPO with priors through the formal lens of fixed-budget best-arm identification. By modeling priors directly over arm means as configuration performance, we derive explicit, distribution-dependent error bounds that quantify the relationship between priors and evaluation budget. Our analysis shows that informative priors, which concentrate probability mass on near-optimal arms, yield reductions in the number of required evaluations, whereas baseline performance is recovered with uninformative or misleading priors. We conduct proof-of-concept experiments on a synthetic benchmark and on LCBench, a common multi-fidelity HPO benchmark for deep learning, to confirm our theoretical results, achieving up to 90% budget reduction while retaining solution quality. Together, our results provide a principled foundation for prior-guided and compute-efficient green AutoML.

Leona Hennig, Jasmin Brandt, Lukas Fehring +3

Institute of Artificial Intelligence Leibniz University Hanover, Germany · University of Bielefeld Bielefeld, Germany · Institute of Artificial Intelligence, Leibniz University Hanover & L3S Research Center Hanover, Germany

Multi-Fidelity Optimization Multi-Armed Bandits Energy-Efficient ML Best-Arm Identification Hyperparameter Optimization

Jun 1, 2026cs.LG

Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits

We study

N

-armed stochastic dueling bandits under the Condorcet-winner assumption, where three widely adopted objectives are considered: best-arm identification (BAI), weak regret, and strong regret. We propose Tree-Guided Identify-Then-Exploit (TG-ITE), the first unified framework to tackle all these objectives to our knowledge. Without requiring stronger assumptions, we propose a shared tree-guided identification approach to find a high-confidence incumbent within

O(N)

comparisons. We further propose varied exploitation strategies to utilize this warm-start stage to optimize the specific objectives at hand. This methodology enables our approach to (1) achieve

O(N)

sample complexity in BAI without commonly adopted stronger assumptions; (2) build the first winner-stays-style algorithm to achieve

O(N)

weak regret; (3) enjoy the same

O(N \log T)

guarantee as specialized strong-regret approaches; (4) realize the joint optimization of BAI and weak regret with

O(N)

guarantees for both, eliminating the sub-optimal gap of

O(\log N)

in the existing approach. Our results provide evidence that the trade-off between BAI and regret minimization is relatively benign in dueling bandits.

Pu Wang, Yao-Xiang Ding

State Key Lab of CAD&CG, Zhejiang University

Multi-Armed Bandits Best-Arm Identification Regret Minimization

Jun 1, 2026cs.LG

Two-Fidelity Best-Action Identification for Stochastic Minimax Tree

We study fixed-confidence best-action identification (BAI) in stochastic minimax trees. This problem is increasingly relevant in modern AI planning, where deep minimax search and Monte Carlo Tree Search (MCTS) with language model long rollouts face a fundamental tradeoff: heuristic evaluations are cheap but biased, while accurate rollouts are reliable but prohibitively expensive. We propose 2FFS, a two-fidelity tree-search algorithm that brings multi-fidelity flat bandit ideas into trees. The algorithm combines minimax-style fast expansion with MCTS-style stochastic sampling, adaptively deciding when to exploit cheap biased evaluations and when to invoke expensive accurate evaluations for local certification. We prove fixed-confidence correctness, establish finite stopping for exact identification, and give a polynomial-depth cost upper bound for general-depth trees. Across numerical stochastic-tree experiments, 2FFS uses substantially fewer samples and computational operations comparing to existing BAI-MCTS baseline.

Peter Chen, Xi Chen

Department of Mathematics Columbia University · Stern School of Business New York University

Multi-Fidelity Optimization Multi-Armed Bandits Sequential Decision Making Monte Carlo Tree Search Best-Arm Identification

May 29, 2026cs.LG

Trajectory-Aware Best-Arm Identification for Local Search Allocation in Bayesian Optimization and Beyond

Bayesian optimization (BO) is effective for expensive black-box optimization, but its performance often degrades on multimodal or high-dimensional problems. A promising remedy is to run multiple local search processes, such as trust region--based BO, and allocate evaluations to those with high potential. However, current best values do not always reflect the final performance of each process. We propose a trajectory-aware best-arm identification (BAI) framework that uses optimization history to guide this allocation. The proposed method extrapolates improvement trajectories, estimates final performance, and progressively eliminates low-potential candidates. For trust region--based BO, we theoretically show that the proposed BAI-guided allocation accelerates convergence to the global optimum under mild assumptions. Experiments on synthetic and real-world benchmarks demonstrate that our method improves BO on multimodal problems. We also show that the same mechanism can enhance other local or population-based optimizers, suggesting its potential as a general extension strategy for multimodal black-box optimization.

Nobuo Namura, Sho Takemori

Fujitsu Limited, Kawasaki, Japan.

Multi-Armed Bandits Bayesian Optimization Black-Box Optimization Best-Arm Identification

May 19, 2026cs.LG

Active Context Selection Improves Simple Regret in Contextual Bandits

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector

p

. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known

p

, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order

\sqrt{n/T \, \lVert p \rVert_{1/2}}

, whereas active sampling with allocation

q_j \propto p_j^{2/3}

achieves the tight rate

\sqrt{n/T} \, \lVert p \rVert_{2/3}

. The resulting improvement can be as large as

Θ(k^{1/4})

, where

k

is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When

p

is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-

p

active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash

College of Management of Technology, EPFL · Department of Computer Science, TU Munich

Multi-Armed Bandits Best-Arm Identification Adaptive Sampling Regret Minimization Contextual Bandits

May 15, 2026cs.LG

On the Power of Adaptivity for $\varepsilon$ -Best Arm Identification in Linear Bandits

We study the minimax sample complexity of

\varepsilon

-best arm identification in linear bandits. Given a compact action set

\mathcal{X}

that spans

\mathbb{R}^d

and an unknown reward vector

θ\in\mathbb{R}^d

, the goal is to output an arm

\widehat{x}\in\mathcal{X}

such that

\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon

with probability at least

1-δ

, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity

\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)

, where

w(\mathcal{X})

is a Gaussian width term dependent on

\mathcal{X}

, and we prove a matching lower bound

Ω\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)

for all non-adaptive fixed-design methods. We then turn to adaptive sampling. We raise an important structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the

\ell_2

ball,

m

-sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set

\mathcal{X}

for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an

\ell_2

-norm estimation subroutine: we design an adaptive algorithm that uses

\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}\right)

samples from the unit

\ell_2

ball in

\mathbb{R}^d

and outputs an estimate

\widehat r

satisfying

|\widehat r-\|θ\|_2|\le \varepsilon

with probability at least

1-δ

, where

θ

is the unknown reward vector.

Arnab Maiti, Yunbei Xu, Kevin Jamieson

University of Washington · National University of Singapore

Multi-Armed Bandits Best-Arm Identification Adaptive Sampling

May 11, 2026cs.LG

Valid Best-Model Identification for LLM Evaluation via Low-Rank Factorization

Selecting the best large language model (LLM) for a fixed benchmark is often expensive, since exhaustive evaluation requires running every model on every example. Multi-armed bandit (MAB) algorithms can reduce the number of LLM calls by sequentially selecting the next model-example pair to evaluate, thereby avoiding wasted evaluations on clearly underperforming models. Further savings can be achieved by predicting model scores from the partially observed model-example score matrix using low-rank factorization. However, such predictions are not ground truth: they can be biased and may therefore lead to incorrect identification of the best model. In this work, we propose a principled framework that combines MAB with cheap predicted scores without compromising statistical validity. Specifically, we derive doubly robust estimators of each model's performance that use the low-rank predictions to reduce variance. This enables the construction of valid finite-sample confidence intervals in our setting, where models are selected adaptively and examples are sampled without replacement. Empirical results on real-world benchmarks show that our approach reduces the number of required evaluations, yielding meaningful savings in compute and cost while accurately identifying the best-performing model.

Elad Tolochinsky, Yaniv Tenzer, Yaniv Romano

Department of Computer Science, Technion – Israel Institute of Technology · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology

Model Selection Multi-Armed Bandits LLM Evaluation Best-Arm Identification Doubly Robust Estimation

May 11, 2026cs.LG

Selection of the Best Policy under Fairness Constraints for Subpopulations

Many high-stakes decisions in health care, public policy, and clinical development require committing to a single policy that will be applied uniformly across a heterogeneous population. Regulatory and fairness standards sometime requires that the chosen policy performs adequately in every pre-specified subpopulation, not only on average. We formalize this as a Selection of the Best with Fairness Constraints (SBFC) problem, in order to identify the policy with the highest average performance among those policies that meet a minimum per-subpopulation threshold. We establish an instance-specific lower bound on sample complexity of the SBFC problem. We then develop a Track-and-Stop with Constraints on Subpopulation (T-a-S-CS) algorithm that achieves the lower bound asymptotically. We extend the framework to general closed-set and penalty-based fairness specifications with matching guarantees. Numerical experiments and a case study using the International Stroke Trial demonstrate substantial efficiency gains over policy-level allocation baselines.

Tingyu Zhu, Yuhang Wu, Zeyu Zheng

Department of Industrial Engineering and Operations Research & Berkeley Artificial Intelligence Research Lab University of California Berkeley

Multi-Armed Bandits Group Fairness Best-Arm Identification Constrained Optimization

May 7, 2026cs.AI

Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback

We study fixed-confidence best arm identification in generalized linear bandits under a hybrid feedback model: at each round, the learner may query either (i) absolute reward feedback from a single arm or (ii) relative (dueling) feedback from an arm pair, both governed by generalized linear models. We introduce a likelihood-ratio--based confidence sequence that unifies heterogeneous generalized linear observations and yields an explicit ellipsoidal confidence set under a self-concordance assumption. Building on this confidence set, we propose a hybrid Track-and-Stop algorithm that adaptively allocates queries by tracking a minimax-optimal design over a joint action space of arms and pairs. We establish

δ

-correctness and provide high-probability upper bounds on the stopping time. We further extend the framework to a cost-aware setting that accounts for heterogeneous acquisition costs across feedback modalities. Empirical experiments demonstrate that the proposed algorithms significantly improve sample efficiency over baseline methods.

Qirun Zeng, Xuchuang Wang, Jiayi Shen +3

Department of Computer Science City University of Hong Kong, Hong Kong SAR, China · Manning College of Information & Computer Science University of Massachusetts Amherst, Amherst, MA, USA · School of Management University of Science and Technology of China, Hefei, Anhui, China +3

Multi-Armed Bandits Best-Arm Identification Generalized Linear Bandits

May 1, 2026cs.LG

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Inria SequeL · CMU · EnLearn

Multi-Armed Bandits Exploration-Exploitation Tradeoff Best-Arm Identification Regret Minimization

Apr 16, 2026stat.ML

Best of both worlds: Stochastic & adversarial best-arm identification

We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.

Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2

Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2

Multi-Armed Bandits Best-Arm Identification Adversarial Bandits