An ε-Best-Arm Identification Algorithm for ...
Type de document :
Communication dans un congrès avec actes
Titre :
An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond
Auteur(s) :
Jourdan, Marc [Auteur]
Scool [Scool]
Degenne, Rémy [Auteur]
Scool [Scool]
Kaufmann, Emilie [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Scool [Scool]
Degenne, Rémy [Auteur]
Scool [Scool]
Kaufmann, Emilie [Auteur]
![refId](/themes/Mirage2//images/idref.png)
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Titre de la manifestation scientifique :
Advances in Neural Information Processing Systems (NeurIPS)
Ville :
New Orleans
Pays :
Etats-Unis d'Amérique
Date de début de la manifestation scientifique :
2023-12-10
Discipline(s) HAL :
Statistiques [stat]/Autres [stat.ML]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Projet ANR :
Collections :
Source :
Fichiers
- document
- Accès libre
- Accéder au document
- TTeBAI.pdf
- Accès libre
- Accéder au document
- 2305.16041
- Accès libre
- Accéder au document