Fixed-confidence guarantees for Bayesian ...
Document type :
Communication dans un congrès avec actes
Title :
Fixed-confidence guarantees for Bayesian best-arm identification
Author(s) :
Shang, Xuedong [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Sequential Learning [SEQUEL]
Scool [Scool]
de Heide, Rianne [Auteur]
Universiteit Leiden = Leiden University
Centrum Wiskunde & Informatica [CWI]
Kaufmann, Emilie [Auteur]
Sequential Learning [SEQUEL]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre National de la Recherche Scientifique [CNRS]
Scool [Scool]
Ménard, Pierre [Auteur]
Sequential Learning [SEQUEL]
Scool [Scool]
Valko, Michal [Auteur]
DeepMind [Paris]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Sequential Learning [SEQUEL]
Scool [Scool]
de Heide, Rianne [Auteur]
Universiteit Leiden = Leiden University
Centrum Wiskunde & Informatica [CWI]
Kaufmann, Emilie [Auteur]
Sequential Learning [SEQUEL]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre National de la Recherche Scientifique [CNRS]
Scool [Scool]
Ménard, Pierre [Auteur]
Sequential Learning [SEQUEL]
Scool [Scool]
Valko, Michal [Auteur]
DeepMind [Paris]
Conference title :
International Conference on Artificial Intelligence and Statistics
City :
Palermo
Country :
Italie
Start date of the conference :
2020
HAL domain(s) :
Informatique [cs]/Apprentissage [cs.LG]
English abstract : [en]
We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS ...
Show more >We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS called Top-Two Transportation Cost (T3C), which disposes of the computational burden of TTTS. As our main contribution, we provide the first sample complexity analysis of TTTS and T3C when coupled with a very natural Bayesian stopping rule, for bandits with Gaussian rewards, solving one of the open questions raised by Russo (2016). We also provide new posterior convergence results for TTTS under two models that are commonly used in practice: bandits with Gaussian and Bernoulli rewards and conjugate priors.Show less >
Show more >We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS called Top-Two Transportation Cost (T3C), which disposes of the computational burden of TTTS. As our main contribution, we provide the first sample complexity analysis of TTTS and T3C when coupled with a very natural Bayesian stopping rule, for bandits with Gaussian rewards, solving one of the open questions raised by Russo (2016). We also provide new posterior convergence results for TTTS under two models that are commonly used in practice: bandits with Gaussian and Bernoulli rewards and conjugate priors.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
ANR Project :
Comment :
Due to COVID-19, the event has been postponed. AISTATS 2020 held online on August 26-28th.
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-02330187v2/document
- Open access
- Access the document
- http://arxiv.org/pdf/1910.10945
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-02330187v2/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-02330187v2/document
- Open access
- Access the document
- document
- Open access
- Access the document
- main.pdf
- Open access
- Access the document
- 1910.10945
- Open access
- Access the document