Minimax policies for adversarial and stochastic bandits

Jean-Yves Audibert 1, 2 Sébastien Bubeck 3
2 IMAGINE [Marne-la-Vallée]
LIGM - Laboratoire d'Informatique Gaspard-Monge, CSTB - Centre Scientifique et Technique du Bâtiment, ENPC - École des Ponts ParisTech
3 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 fill in a long open gap in the characterization of the minimax rate for the multi-armed bandit prob- lem. Concretely, we remove an extraneous loga- rithmic factor in the previously known upper bound and propose a new family of randomized algorithms based on an implicit normalization, as well as a new analysis. We also consider the stochastic case, and prove that an appropriate modification of the upper confidence bound policy UCB1 (Auer et al., 2002) achieves the distribution-free optimal rate while still having a distribution-dependent rate log- arithmic in the number of plays.
Type de document :
Communication dans un congrès
COLT, Jun 2009, Montreal, Canada. pp.217-226, 2009
Liste complète des métadonnées

https://hal-enpc.archives-ouvertes.fr/hal-00834882
Contributeur : Pascal Monasse <>
Soumis le : lundi 17 juin 2013 - 15:19:50
Dernière modification le : jeudi 5 juillet 2018 - 14:25:04
Document(s) archivé(s) le : mercredi 18 septembre 2013 - 04:15:37

Fichier

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

Identifiants

  • HAL Id : hal-00834882, version 1

Citation

Jean-Yves Audibert, Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. COLT, Jun 2009, Montreal, Canada. pp.217-226, 2009. 〈hal-00834882〉

Partager

Métriques

Consultations de la notice

568

Téléchargements de fichiers

577