Efficient Algorithms for Extreme Bandits

Baudry, Dorian; Russac, Yoan; Kaufmann, Emilie

Type de document :

Communication dans un congrès avec actes

Titre :

Efficient Algorithms for Extreme Bandits

Auteur(s) :

Baudry, Dorian [Auteur]
Scool [Scool]
Centre National de la Recherche Scientifique [CNRS]
Russac, Yoan [Auteur]
Département d'informatique - ENS-PSL [DI-ENS]
Université Paris Sciences et Lettres [PSL]
Kaufmann, Emilie [Auteur]

Centre National de la Recherche Scientifique [CNRS]
Scool [Scool]

Titre de la manifestation scientifique :

International conference on Artificial Intelligence and Statistics (AISTATS)

Ville :

Virtual Conference

Pays :

Espagne

Date de début de la manifestation scientifique :

2022-03-28

Titre de la revue :

Proceedings of Machine Learning Research (PMLR)

Discipline(s) HAL :

Statistiques [stat]/Machine Learning [stat.ML]

Résumé en anglais : [en]

In this paper, we contribute to the Extreme Bandit problem, a variant of Multi-Armed Bandits in which the learner seeks to collect the largest possible reward. We first study the concentration of the maximum of i.i.d random ...
Lire la suite >In this paper, we contribute to the Extreme Bandit problem, a variant of Multi-Armed Bandits in which the learner seeks to collect the largest possible reward. We first study the concentration of the maximum of i.i.d random variables under mild assumptions on the tail of the rewards distributions. This analysis motivates the introduction of Quantile of Maxima (QoMax). The properties of QoMax are sufficient to build an Explore-Then-Commit (ETC) strategy, QoMax-ETC, achieving strong asymptotic guarantees despite its simplicity. We then propose and analyze a more adaptive, anytime algorithm, QoMax-SDA, which combines QoMax with a subsampling method recently introduced by Baudry et al. (2021). Both algorithms are more efficient than existing approaches in two aspects (1) they lead to better empirical performance (2) they enjoy a significant reduction of the memory and time complexities.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Au delà de l'apprentissage séquentiel pour de meilleures prises de décisions

Collections :