A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences

Abstract

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).

Cited by in corpus (6)

• Further Optimal Regret Bounds for Thompson Sampling
• Generalized Risk-Aversion in Stochastic Multi-Armed Bandits
• Finite-time Regret Bound of a Bandit Algorithm for the Semi-bounded Support Model
• Robustness of Anytime Bandit Policies
• A KL-LUCB Bandit Algorithm for Large-Scale Crowdsourcing
• Instrument-Armed Bandits