Dealing with Unknown Variances in Best-Arm ...
Document type :
Communication dans un congrès avec actes
Title :
Dealing with Unknown Variances in Best-Arm Identification
Author(s) :
Jourdan, Marc [Auteur]
Scool [Scool]
Degenne, Rémy [Auteur]
Scool [Scool]
Kaufmann, Emilie [Auteur]
Centre de Recherche Réseau Image SysTème Architecture et MuLtimédia [CRISTAL]
Scool [Scool]
Degenne, Rémy [Auteur]
Scool [Scool]
Kaufmann, Emilie [Auteur]
Centre de Recherche Réseau Image SysTème Architecture et MuLtimédia [CRISTAL]
Conference title :
Algorithmic Learning Theory (ALT)
City :
Singapore (SG)
Country :
Singapour
Start date of the conference :
2023-02-20
Book title :
Proceedings of Machine Learning Research (PMLR)
English keyword(s) :
Bandits
Best arm identification
Best arm identification
HAL domain(s) :
Statistiques [stat]/Autres [stat.ML]
English abstract : [en]
The problem of identifying the best arm among a collection of items having Gaussian rewards distribution is well understood when the variances are known. Despite its practical relevance for many applications, few works ...
Show more >The problem of identifying the best arm among a collection of items having Gaussian rewards distribution is well understood when the variances are known. Despite its practical relevance for many applications, few works studied it for unknown variances. In this paper we introduce and analyze two approaches to deal with unknown variances, either by plugging in the empirical variance or by adapting the transportation costs. In order to calibrate our two stopping rules, we derive new time-uniform concentration inequalities, which are of independent interest. Then, we illustrate the theoretical and empirical performances of our two sampling rule wrappers on Track-and-Stop and on a Top Two algorithm. Moreover, by quantifying the impact on the sample complexity of not knowing the variances, we reveal that it is rather small.Show less >
Show more >The problem of identifying the best arm among a collection of items having Gaussian rewards distribution is well understood when the variances are known. Despite its practical relevance for many applications, few works studied it for unknown variances. In this paper we introduce and analyze two approaches to deal with unknown variances, either by plugging in the empirical variance or by adapting the transportation costs. In order to calibrate our two stopping rules, we derive new time-uniform concentration inequalities, which are of independent interest. Then, we illustrate the theoretical and empirical performances of our two sampling rule wrappers on Track-and-Stop and on a Top Two algorithm. Moreover, by quantifying the impact on the sample complexity of not knowing the variances, we reveal that it is rather small.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
ANR Project :
Collections :
Source :
Files
- document
- Open access
- Access the document
- BAIUV.pdf
- Open access
- Access the document
- 2210.00974
- Open access
- Access the document