On the complexity of All ε-Best Arms Identification

Aymen Al Marjani (1) , Tomas Kocak (2) , Aurélien Garivier (1)

1 UMPA-ENSL - Unité de Mathématiques Pures et Appliquées
2 University of Potsdam = Universität Potsdam

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.

Domaines: Mathématiques [math]

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