A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
Maillard, Odalric-Ambrym ; Munos, Rémi ; Stoltz, Gilles
arXiv, 1105.5820 / Harvested from arXiv
Text on arXiv
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).
Publié le : 2011-05-29
Classification:  Mathematics - Statistics Theory 
@article{1105.5820,
     author = {Maillard, Odalric-Ambrym and Munos, R\'emi and Stoltz, Gilles},
     title = {A Finite-Time Analysis of Multi-armed Bandits Problems with
  Kullback-Leibler Divergences},
     journal = {arXiv},
     volume = {2011},
     number = {0},
     year = {2011},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1105.5820}
}

Maillard, Odalric-Ambrym; Munos, Rémi; Stoltz, Gilles. A Finite-Time Analysis of Multi-armed Bandits Problems with
  Kullback-Leibler Divergences. arXiv, Tome 2011 (2011) no. 0, . http://gdmltest.u-ga.fr/item/1105.5820/