Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence

Victor Gabillon 1 Mohammad Ghavamzadeh 1 Alessandro Lazaric 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : We study the problem of identifying the best arm(s) in the stochastic multi-armed bandit setting. This problem has been studied in the literature from two different perspectives: {\em fixed budget} and {\em fixed confidence}. We propose a unifying approach that leads to a meta-algorithm called unified gap-based exploration (UGapE), with a common structure and similar theoretical analysis for these two settings. We prove a performance bound for the two versions of the algorithm showing that the two problems are characterized by the same notion of complexity. We also show how the UGapE algorithm as well as its theoretical analysis can be extended to take into account the variance of the arms and to multiple bandits. Finally, we evaluate the performance of UGapE and compare it with a number of existing fixed budget and fixed confidence algorithms.
Type de document :
Communication dans un congrès
NIPS - Twenty-Sixth Annual Conference on Neural Information Processing Systems, Dec 2012, Lake Tahoe, United States. 2012
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00772615
Contributeur : Alessandro Lazaric <>
Soumis le : jeudi 10 janvier 2013 - 18:23:46
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : samedi 1 avril 2017 - 03:45:19

Fichier

nips2012l.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00772615, version 1

Collections

INRIA | UNIV-LILLE3 | LAGIS

Citation

Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric. Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence. NIPS - Twenty-Sixth Annual Conference on Neural Information Processing Systems, Dec 2012, Lake Tahoe, United States. 2012. 〈hal-00772615〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

283

Téléchargements de fichiers

139

Contact


archive-ouverte@inria.fr