A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences

Odalric-Ambrym Maillard 1 Rémi Munos 1 Gilles Stoltz 2, 3, 4
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
2 DMA - Département de Mathématiques et Applications - ENS Paris
3 GREGH - Groupement de Recherche et d'Etudes en Gestion à HEC
4 CLASSIC - Computational Learning, Aggregation, Supervised Statistical, Inference, and Classification
DMA - Département de Mathématiques et Applications - ENS Paris, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt
Abstract : We consider a Kullback-Leibler-based algorithm for the stochastic multi-armed bandit problem in the case of distributions with finite supports (not necessarily known beforehand), whose asymptotic regret matches the lower bound of \cite{Burnetas96}. Our contribution is to provide a finite-time analysis of this algorithm; we get bounds whose main terms are smaller than the ones of previously known algorithms with finite-time analyses (like UCB-type algorithms).
Type de document :
Communication dans un congrès
Sham Kakade & Ulrike von Luxburg. 24th Annual Conference on Learning Theory : COLT'11, Jul 2011, Budapest, Hungary. pp.18, 2011
Liste complète des métadonnées
https://hal.inria.fr/inria-00574987
Contributeur : Gilles Stoltz <>
Soumis le : vendredi 27 mai 2011 - 22:44:43
Dernière modification le : mardi 17 avril 2018 - 11:28:57
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 12:53:05

Fichiers

66-Maillard-Munos-Stoltz.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00574987, version 2
  • ARXIV : 1105.5820

Collections

HEC | PARISTECH | INRIA | UNIV-LILLE3 | INSMI | LAGIS | PSL

Citation

Odalric-Ambrym Maillard, Rémi Munos, Gilles Stoltz. A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences. Sham Kakade & Ulrike von Luxburg. 24th Annual Conference on Learning Theory : COLT'11, Jul 2011, Budapest, Hungary. pp.18, 2011. 〈inria-00574987v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

585

Téléchargements de fichiers

229

Contact


archive-ouverte@inria.fr