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

References in corpus (2)

• Joint estimation of intersecting context tree models
• An Asymptotically Optimal Policy for Finite Support Models in the Multiarmed Bandit Problem

Cited by in corpus (25)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Further Optimal Regret Bounds for Thompson Sampling
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
• Generalized Risk-Aversion in Stochastic Multi-Armed Bandits
• Variational inference for the multi-armed contextual bandit
• KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints
• Parallelizing Thompson Sampling
• Multi-Armed Bandits with Fairness Constraints for Distributing Resources to Human Teammates
• Adaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
• Finite-time Regret Bound of a Bandit Algorithm for the Semi-bounded Support Model
• Regret Minimization in Heavy-Tailed Bandits
• Bandits with Knapsacks beyond the Worst-Case
• One-bit feedback is sufficient for upper confidence bound policies
• Online Influence Maximization with Local Observations
• Variance-Dependent Best Arm Identification
• Robustness of Anytime Bandit Policies
• Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
• A KL-LUCB Bandit Algorithm for Large-Scale Crowdsourcing
• Regret vs. Communication: Distributed Stochastic Multi-Armed Bandits and Beyond
• Learning to maximize global influence from local observations
• Instrument-Armed Bandits
• Learning Sequential Channel Selection for Interference Alignment using Reconfigurable Antennas