# Best Arm Identification with Fixed Budget: A Large Deviation Perspective

arXiv: https://arxiv.org/abs/2312.12137 · HTML: https://mlsanity.com/paper/2312.12137/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 19 Dec 2023.

## Builds on (most cited first, 17 of 17)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2106.04763/) (2021)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Open Problem: Optimal Best Arm Identification with Fixed Budget](https://mlsanity.com/paper/2303.00950/) (2023)
- [Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Sampling](https://mlsanity.com/paper/2109.08229/) (2021)
- [On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits](https://mlsanity.com/paper/2210.00895/) (2022)

## Built on by (most cited first, 12 of 12)

- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Training a Generally Curious Agent](https://mlsanity.com/paper/2502.17543/) (2025)
- [Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances](https://mlsanity.com/paper/2312.12741/) (2023)
- [Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2405.15090/) (2024)
- [Admissibility of Completely Randomized Trials: A Large-Deviation Approach](https://mlsanity.com/paper/2506.05329/) (2025)
- [An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration](https://mlsanity.com/paper/2502.01429/) (2025)
- [Cost-Aware Optimal Pairwise Pure Exploration](https://mlsanity.com/paper/2503.07877/) (2025)
- [On the Optimality of Tracking Fisher Information in Adaptive Testing with Stochastic Binary Responses](https://mlsanity.com/paper/2510.07862/) (2025)
- [Fundamental Limitations of Fixed-Budget Best-Arm Identification](https://mlsanity.com/paper/2607.11635/) (2026)
- [Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?](https://mlsanity.com/paper/2608.15365/) (2026)
- [Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments](https://mlsanity.com/paper/2608.21995/) (2026)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

We consider the problem of identifying the best arm in stochastic Multi-Armed Bandits (MABs) using a fixed sampling budget. Characterizing the minimal instance-specific error probability for this problem constitutes one of the important remaining open problems in MABs. When arms are selected using a static sampling strategy, the error probability decays exponentially with the number of samples at a rate that can be explicitly derived via Large Deviation techniques. Analyzing the performance of algorithms with adaptive sampling strategies is however much more challenging. In this paper, we establish a connection between the Large Deviation Principle (LDP) satisfied by the empirical proportions of arm draws and that satisfied by the empirical arm rewards. This connection holds for any adaptive algorithm, and is leveraged (i) to improve error probability upper bounds of some existing algorithms, such as the celebrated sr (Successive Rejects) algorithm citepaudibert2010best, and (ii) to devise and analyze new algorithms. In particular, we present sred (Continuous Rejects), a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. Applying our Large Deviation results, we prove that sred enjoys better performance guarantees than existing algorithms, including sr. Extensive numerical experiments confirm this observation.