An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond

Marc Jourdan
Rémy Degenne
  • Fonction : Auteur
  • PersonId : 748911
  • IdHAL : remydegenne

Résumé

We propose EB-TC ε , a novel sampling rule for ε-best arm identification in stochastic bandits. It is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TC ε 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-TC ε. 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-TC ε performs favorably compared to existing algorithms, in different settings.

Domaines

Autres [stat.ML]
Fichier principal
Vignette du fichier
TTeBAI.pdf (1.73 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04306214 , version 1 (24-11-2023)

Licence

Paternité

Identifiants

Citer

Marc Jourdan, Rémy Degenne, Emilie Kaufmann. An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond. Advances in Neural Information Processing Systems (NeurIPS), Dec 2023, New Orleans, United States. ⟨hal-04306214⟩
32 Consultations
14 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More