Optimal Best Arm Identification with Fixed Confidence

Garivier, Aurélien; Kaufmann, Emilie

Document type :

Communication dans un congrès avec actes

Title :

Optimal Best Arm Identification with Fixed Confidence

Author(s) :

Garivier, Aurélien [Auteur]
Institut de Mathématiques de Toulouse UMR5219 [IMT]
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]

Conference title :

29th Annual Conference on Learning Theory (COLT)

City :

New York

Country :

Etats-Unis d'Amérique

Start date of the conference :

2016-06-23

Journal title :

JMLR Workshop and Conference Proceedings

Publication date :

2016-02-12

English keyword(s) :

MDL
best arm identification
multi-armed bandits

HAL domain(s) :

Mathématiques [math]/Statistiques [math.ST]
Statistiques [stat]/Machine Learning [stat.ML]

English abstract : [en]

We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which ...
Show more >We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Apprentissage Adaptatif pour le Crowdsourcing Intelligent et l'Accès à l'Information
Statistique Semi-Paramétrique pour l'Allocation Dynamique de Ressources et l'Optimisation

Collections :