Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, 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 problem introduced by [MJTN20] of identifying all the ε-optimal arms in a finite stochastic multi-armed bandit with Gaussian rewards. In the fixed confidence setting, we give a lower bound on the number of samples required by any algorithm that returns the set of ε-good arms with a failure probability less than some risk level δ. This bound writes as T * ε (µ) log(1/δ), where T * ε (µ) is a characteristic time that depends on the vector of mean rewards µ and the accuracy parameter ε. We also provide an efficient numerical method to solve the convex max-min program that defines the characteristic time. 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 [MJTN20]. Using this method, we propose a Track-and-Stop algorithm that identifies the set of ε-good arms w.h.p and enjoys asymptotic optimality (when δ goes to zero) in terms of the expected sample complexity. Finally, using numerical simulations, we demonstrate our algorithm's advantage over state-of-the-art methods, even for moderate values of the risk parameter.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Aymen Al Marjani Connect in order to contact the contributor
Submitted on : Sunday, February 13, 2022 - 11:59:16 AM
Last modification on : Thursday, June 23, 2022 - 3:37:15 AM
Long-term archiving on: : Saturday, May 14, 2022 - 6:11:26 PM


Files produced by the author(s)


  • HAL Id : hal-03570280, version 1


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



Record views


Files downloads