A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
Maillard, Odalric-Ambrym ; Munos, Rémi ; Stoltz, Gilles
HAL, inria-00574987 / Harvested from HAL
Text on HAL
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-07-09
Classification:  [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST],  [STAT.TH]Statistics [stat]/Statistics Theory [stat.TH],  [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG] 
@article{inria-00574987,
     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 = {HAL},
     volume = {2011},
     number = {0},
     year = {2011},
     language = {en},
     url = {http://dml.mathdoc.fr/item/inria-00574987}
}

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