# An varepsilon-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 41 references that are in the map.
- First posted on arXiv 25 May 2023.

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

- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)

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

- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits](https://mlsanity.com/paper/2410.07638/) (2024)
- [Fixed Confidence Best Arm Identification in the Bayesian Setting](https://mlsanity.com/paper/2402.10429/) (2024)

## Abstract (arXiv)

We propose EB-TCvarepsilon, a novel sampling rule for varepsilon-best arm identification in stochastic bandits. It is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TCvarepsilon is an *anytime* sampling rule that can therefore be employed without modification for fixed confidence or fixed budget identification (without prior knowledge of the budget). We provide three types of theoretical guarantees for EB-TCvarepsilon. First, we prove bounds on its expected sample complexity in the fixed confidence setting, notably showing its asymptotic optimality in combination with an adaptive tuning of its exploration parameter. We complement these findings with upper bounds on its probability of error at any time and for any error parameter, which further yield upper bounds on its simple regret at any time. Finally, we show through numerical simulations that EB-TCvarepsilon performs favorably compared to existing algorithms, in different settings.