Best-Arm Identification and Treatment Choice
Finding the best option under a fixed budget of trials — and pinning down the exact limits of how well that can be done.
- best-arm identification
- fixed budget
- minimax optimality
- bandits
The question
Given a budget of experimental units and several treatments, allocate the budget and then recommend one arm. How small can the probability of recommending the wrong arm be, or how small can the simple regret be, and which strategy achieves it?
The same problem is studied in two literatures under two names — best-arm identification in bandits, treatment choice in econometrics — and the results below are stated so that they apply to both. The recurring technical difficulty is that upper and lower bounds in the fixed-budget setting have historically failed to match, leaving the optimal strategy unknown even asymptotically.
Closing the gap
- Minimax and Bayes optimal best-arm identification gives a single strategy that is simultaneously asymptotically minimax and Bayes optimal for the simple regret, with bounds that match including constant terms, attained without knowing the outcome distributions or the prior.
- The Generalized Neyman Allocation resolves the worst-case problem in the small-gap regime, where the misidentification bounds match exactly — the regime in which the problem is genuinely hard.
- The role of contextual information (JMLR) shows how covariates observed during the experiment reduce sample complexity even when the target is a marginalized mean, via a context-aware Track-and-Stop that matches the instance-specific bound.
Further work in this direction includes optimal simple regret in Bayesian best-arm identification (Mathematics of Operations Research) and a comment on adaptive treatment assignment in experiments for policy choice (revise and resubmit at Econometrica).
Adjacent: bandit algorithms
The sequential allocation machinery is shared with regret-minimizing bandits. Work on best-of-both-worlds linear contextual bandits (TMLR) and its generalization LC-Tsallis-INF (AISTATS 2025) develops algorithms that are simultaneously near-optimal in stochastic and adversarial environments, without being told which one they are in.