# On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2016.

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

- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/2110.08627/) (2021)
- [Rate-optimal Bayesian Simple Regret in Best Arm Identification](https://mlsanity.com/paper/2111.09885/) (2021)
- [Learning in Restless Bandits under Exogenous Global Markov Process](https://mlsanity.com/paper/2112.09484/) (2021)
- [Restless Multi-Armed Bandits under Exogenous Global Markov Process](https://mlsanity.com/paper/2202.13665/) (2022)
- [Optimal Stochastic Nonconvex Optimization with Bandit Feedback](https://mlsanity.com/paper/2103.16082/) (2021)
- [Federated Learning in UAV-Enhanced Networks: Joint Coverage and Convergence Time Optimization](https://mlsanity.com/paper/2308.16889/) (2023)
- [Best Arm Identification in Batched Multi-armed Bandit Problems](https://mlsanity.com/paper/2312.13875/) (2023)
- [Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliability](https://mlsanity.com/paper/2201.12482/) (2022)
- [AgentOpt v0.1 Technical Report: Client-Side Optimization for LLM-Based Agent](https://mlsanity.com/paper/2604.06296/) (2026)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

We consider the best-arm identification problem in multi-armed bandits, which focuses purely on exploration. A player is given a fixed budget to explore a finite set of arms, and the rewards of each arm are drawn independently from a fixed, unknown distribution. The player aims to identify the arm with the largest expected reward. We propose a general framework to unify sequential elimination algorithms, where the arms are dismissed iteratively until a unique arm is left. Our analysis reveals a novel performance measure expressed in terms of the sampling mechanism and number of eliminated arms at each round. Based on this result, we develop an algorithm that divides the budget according to a nonlinear function of remaining arms at each round. We provide theoretical guarantees for the algorithm, characterizing the suitable nonlinearity for different problem environments described by the number of competitive arms. Matching the theoretical results, our experiments show that the nonlinear algorithm outperforms the state-of-the-art. We finally study the side-observation model, where pulling an arm reveals the rewards of its related arms, and we establish improved theoretical guarantees in the pure-exploration setting.