Solving Bernoulli Rank-One Bandits with ...
Type de document :
Communication dans un congrès avec actes
Titre :
Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
Auteur(s) :
Trinh, Cindy [Auteur]
Ecole Normale Supérieure Paris-Saclay [ENS Paris Saclay]
Kaufmann, Emilie [Auteur]
Scool [Scool]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre National de la Recherche Scientifique [CNRS]
Sequential Learning [SEQUEL]
Vernade, Claire [Auteur]
DeepMind [London]
Combes, Richard [Auteur]
Laboratoire des signaux et systèmes [L2S]
CentraleSupélec
Ecole Normale Supérieure Paris-Saclay [ENS Paris Saclay]
Kaufmann, Emilie [Auteur]
Scool [Scool]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre National de la Recherche Scientifique [CNRS]
Sequential Learning [SEQUEL]
Vernade, Claire [Auteur]
DeepMind [London]
Combes, Richard [Auteur]
Laboratoire des signaux et systèmes [L2S]
CentraleSupélec
Titre de la manifestation scientifique :
ALT 2020 - 31st International Conference on Algorithmic Learning Theory
Ville :
San Diego
Pays :
Etats-Unis d'Amérique
Date de début de la manifestation scientifique :
2020-02-08
Date de publication :
2020-02-08
Mot(s)-clé(s) en anglais :
Multi-armed bandits
unimodal bandits
rank-one bandits
unimodal bandits
rank-one bandits
Discipline(s) HAL :
Statistiques [stat]/Machine Learning [stat.ML]
Résumé en anglais : [en]
Stochastic Rank-One Bandits (Katarya et al, (2017a,b)) are a simple framework for regret minimization problems over rank-one matrices of arms. The initially proposed algorithms are proved to have logarithmic regret, but ...
Lire la suite >Stochastic Rank-One Bandits (Katarya et al, (2017a,b)) are a simple framework for regret minimization problems over rank-one matrices of arms. The initially proposed algorithms are proved to have logarithmic regret, but do not match the existing lower bound for this problem. We close this gap by first proving that rank-one bandits are a particular instance of unimodal bandits, and then providing a new analysis of Unimodal Thompson Sampling (UTS), initially proposed by Paladino et al (2017). We prove an asymptotically optimal regret bound on the frequentist regret of UTS and we support our claims with simulations showing the significant improvement of our method compared to the state-of-the-art.Lire moins >
Lire la suite >Stochastic Rank-One Bandits (Katarya et al, (2017a,b)) are a simple framework for regret minimization problems over rank-one matrices of arms. The initially proposed algorithms are proved to have logarithmic regret, but do not match the existing lower bound for this problem. We close this gap by first proving that rank-one bandits are a particular instance of unimodal bandits, and then providing a new analysis of Unimodal Thompson Sampling (UTS), initially proposed by Paladino et al (2017). We prove an asymptotically optimal regret bound on the frequentist regret of UTS and we support our claims with simulations showing the significant improvement of our method compared to the state-of-the-art.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Projet ANR :
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-02396943v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/128-128-all.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/16-16-log.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/32-32-all.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/4-4-all.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/4-4-log.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/64-64-all.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/8-8-log.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/closer-16-16.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/closer-32-32.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/closer-8-8.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943/file/row_4_col_4_log.png
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/1912.03074
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02396943v2/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- Trinh20.pdf
- Accès libre
- Accéder au document
- 128-128-all.png
- Accès libre
- Accéder au document
- 16-16-log.png
- Accès libre
- Accéder au document
- 32-32-all.png
- Accès libre
- Accéder au document
- 4-4-all.jpg
- Accès libre
- Accéder au document
- 4-4-log.png
- Accès libre
- Accéder au document
- 64-64-all.png
- Accès libre
- Accéder au document
- 8-8-log.png
- Accès libre
- Accéder au document
- closer-16-16.png
- Accès libre
- Accéder au document
- closer-32-32.png
- Accès libre
- Accéder au document
- closer-8-8.png
- Accès libre
- Accéder au document
- 1912.03074
- Accès libre
- Accéder au document
- row_4_col_4_log.png
- Accès libre
- Accéder au document