# On the complexity of All varepsilon-Best Arms Identification

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 21 references that are in the map.
- First posted on arXiv 13 Feb 2022.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [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)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Gradient Ascent for Active Exploration in Bandit Problems](https://mlsanity.com/paper/1905.08165/) (2019)

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

- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Choosing Answers in varepsilon-Best-Answer Identification for Linear Bandits](https://mlsanity.com/paper/2206.04456/) (2022)
- [Non-Asymptotic Analysis of (Sticky) Track-and-Stop](https://mlsanity.com/paper/2505.22475/) (2025)
- [Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy](https://mlsanity.com/paper/2605.07171/) (2026)

## Abstract (arXiv)

We consider the question introduced by citeMason2020 of identifying all the varepsilon-optimal arms in a finite stochastic multi-armed bandit with Gaussian rewards. We give two lower bounds on the sample complexity of any algorithm solving the problem with a confidence at least 1-δ. The first, unimprovable in the asymptotic regime, motivates the design of a Track-and-Stop strategy whose average sample complexity is asymptotically optimal when the risk δ goes to zero. Notably, we provide an efficient numerical method to solve the convex max-min program that appears in the lower bound. Our method is based on a complete characterization of the alternative bandit instances that the optimal sampling strategy needs to rule out, thus making our bound tighter than the one provided by citeMason2020. The second lower bound deals with the regime of high and moderate values of the risk δ, and characterizes the behavior of any algorithm in the initial phase. It emphasizes the linear dependency of the sample complexity in the number of arms. Finally, we report on numerical simulations demonstrating our algorithm's advantage over state-of-the-art methods, even for moderate risks.