The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

Abstract

This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm satisfies a uniformly better regret bound than UCB or UCB2; second, in the special case of Bernoulli rewards, it reaches the lower bound of Lai and Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm are also optimal for specific classes of (possibly unbounded) rewards, including those generated from exponential families of distributions. A large-scale numerical study comparing KL-UCB with its main competitors (UCB, UCB2, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and stable, including for short time horizons. KL-UCB is also the only method that always performs better than the basic UCB policy. Our regret bounds rely on deviations results of independent interest which are stated and proved in the Appendix. As a by-product, we also obtain an improved regret bound for the standard UCB algorithm.

18 pages, 3 figures; Conf. Comput. Learning Theory (COLT) 2011 in Budapest, Hungary

Cited by in corpus (58)

• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Minimal Exploration in Structured Stochastic Bandits
• Informational Confidence Bounds for Self-Normalized Averages and Applications
• Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
• Online Learning to Rank in Stochastic Click Models
• DCM Bandits: Learning to Rank with Multiple Clicks
• Taming Non-stationary Bandits: A Bayesian Approach
• Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
• Multi-objective Contextual Multi-armed Bandit with a Dominant Objective
• Thompson Sampling for Budgeted Multi-armed Bandits
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
• Online Learning under Delayed Feedback
• Multiple-Play Bandits in the Position-Based Model
• Generalized Risk-Aversion in Stochastic Multi-Armed Bandits
• Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
• Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions
• Unimodal Bandits without Smoothness
• Thompson Sampling for Complex Bandit Problems
• Concurrent bandits and cognitive radio networks
• MOTS: Minimax Optimal Thompson Sampling
• Bandits with heavy tail
• An Analysis of the Value of Information when Exploring Stochastic, Discrete Multi-Armed Bandits
• Logarithmic regret bounds for Bandits with Knapsacks
• Empirical Bayes Regret Minimization
• Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• Learning the distribution with largest mean: two bandit frameworks
• SLOPT: Bandit Optimization Framework for Mutation-Based Fuzzing
• The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates
• Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits
• Accurate Inference for Adaptive Linear Models
• Online Learning in Decentralized Multiuser Resource Sharing Problems
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
• Context Tree Selection: A Unifying View
• Finite-time Regret Bound of a Bandit Algorithm for the Semi-bounded Support Model
• A survey on multi-player bandits
• Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
• Memory-Constrained No-Regret Learning in Adversarial Bandits
• Bandit-Based Random Mutation Hill-Climbing
• Accelerated learning from recommender systems using multi-armed bandit
• Efficient Algorithms for Stochastic Repeated Second-price Auctions
• Global Bandits with Holder Continuity
• Regenerative Particle Thompson Sampling
• A PAC algorithm in relative precision for bandit problem with costly sampling
• Thompson Sampling for Unimodal Bandits
• Dynamic Rate and Channel Selection in Cognitive Radio Systems
• Instrument-Armed Bandits
• An order optimal policy for exploiting idle spectrum in cognitive radio networks
• A KL-LUCB Bandit Algorithm for Large-Scale Crowdsourcing
• On Adaptive Estimation for Dynamic Bernoulli Bandits
• Stochastic Multi-armed Bandits in Constant Space
• Learning Sequential Channel Selection for Interference Alignment using Reconfigurable Antennas
• Adapting Improved Upper Confidence Bounds for Monte-Carlo Tree Search
• Robustness of Anytime Bandit Policies
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation