A minimax and asymptotically optimal algorithm for stochastic bandits - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Algorithmic Learning Theory Année : 2017

A minimax and asymptotically optimal algorithm for stochastic bandits

Résumé

We propose the kl-UCB ++ algorithm for regret minimization in stochastic bandit models with exponential families of distributions. We prove that it is simultaneously asymptotically optimal (in the sense of Lai and Robbins' lower bound) and minimax optimal. This is the first algorithm proved to enjoy these two properties at the same time. This work thus merges two different lines of research with simple and clear proofs.
Fichier principal
Vignette du fichier
main.pdf (190.01 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01475078 , version 1 (23-02-2017)
hal-01475078 , version 2 (19-09-2017)

Licence

Paternité

Identifiants

Citer

Pierre Ménard, Aurélien Garivier. A minimax and asymptotically optimal algorithm for stochastic bandits. Algorithmic Learning Theory, 2017, 2017 Algorithmic Learning Theory Conference 76. ⟨hal-01475078v2⟩
548 Consultations
344 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More