Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On the complexity of All ε-Best Arms Identification

Aymen Al Marjani 1 Tomas Kocak 2 Aurélien Garivier 1 
UMPA-ENSL - Unité de Mathématiques Pures et Appliquées
Abstract : We consider the question introduced by \cite{Mason2020} 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-\delta$. 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 $\delta$ 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 \cite{Mason2020}. The second lower bound deals with the regime of high and moderate values of the risk $\delta$, 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Aymen Al Marjani Connect in order to contact the contributor
Submitted on : Monday, June 20, 2022 - 3:25:37 PM
Last modification on : Thursday, June 23, 2022 - 3:37:15 AM


Files produced by the author(s)


  • HAL Id : hal-03570280, version 2



Aymen Al Marjani, Tomas Kocak, Aurélien Garivier. On the complexity of All ε-Best Arms Identification. 2022. ⟨hal-03570280v2⟩



Record views


Files downloads