arXiv (Cornell University) · 2011 · 121 citations · 9 references
Natural SciencesMathematicsAlgorithmsProbability TheoryStochastic ProcessesStochastic OptimizationStochastic ProgrammingBandit AlgorithmsFinite TimeKullback-leibler DivergenceLower Bound ComputationStochastic Bandits
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).
9
Asymptotically efficient adaptive allocation rules
Tze-Leung Lai, Herbert Robbins · Advances in Applied Mathematics · 1985 · 2.5K citations