The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

By Aurélien Garivier, Olivier Capp'e. Annual Conference Computational Learning Theory, 2011

667 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/a7a481032045284382dffa1be4ba90029d14eb41

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “It is only in [60, 92, 44] that a finite-time analysis was derived for KL-based UCB algorithms, KLUCB and Kinf -UCB, that achieve the asymptotic lower bounds of [88] ha l-0 07 47 57 5, v er si on 3 16 S ep 2 01 3”
RecSim: A Configurable Simulation Platform for Recommender Systems (2019, neutral): “In addition, several standard multi-armed bandit algorithms [Auer et al., 2002, Garivier and Cappe, 2011, Agrawal and Goyal, 2013] are provided to support experimentation with exploration (e.g., of latent topic interests).”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, background): “We can also further improve the constant factor from 2(1 + c ) to 4 by setting ¯ µ i = ˆ µ i + 2ln t +lnln t 2 T i at the cost of a second order ln ln n term as in Garivier & Capp´e (2011), with regret at most Comparing to classical MAB.”
Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis (2012, background): “We gather together here some useful preliminaries such as notations not already given in the introduction: • For the rest of this paper, we assume action 1 is the unique optimal action.”
Structural Causal Bandits: Where to Intervene? (2018, neutral): “2). kl-UCB satisfies lim supn→∞ E[Regn] log(n) ≤ ∑ x:µx<µ∗ µ∗−µx KL(µx,µ∗) where KL is Kullback-Leibler divergence between two Bernoulli distributions [Garivier and Cappé, 2011].”
Further Optimal Regret Bounds for Thompson Sampling (2012, methodology): “An algorithm for the MAB problem must decide which arm to play at each time step t , based on the outcomes of the previous t − 1 plays.”
Optimistic Bayesian Sampling in Contextual-Bandit Problems (2012, methodology): “Another class of 'UCB-type' algorithms was proposed initially by Lai and Robbins (1985), with a recent theoretical analysis by Garivier and Cappé (2011).”
Regret Analysis of the Anytime Optimally Confident UCB Algorithm (2016, methodology): “(2) Strategies similar to this have been called KL-UCB+ and suggested as a heuristic by Garivier and Capp´e [2011] (this version is speciﬁed to the subgaussian noise model).”
Kullback–Leibler upper confidence bounds for optimal sequential allocation (2012, background): “The analysis presented here greatly improves over the preliminary results presented, on the one hand by Garivier and Capp´e (2011), and on the other hand by Maillard, Munos and Stoltz (2011); more precisely, the improvements lie in the greater generality of the analysis and by the more precise…”
Non-stochastic Best Arm Identification and Hyperparameter Optimization (2015, background): “Since Theorem 1 is in terms of maxi i(t), such a lower bound would be in stark contrast to the stochastic setting, where arms with smaller variances have smaller envelopes and existing algorithms exploit this fact [27].”
Introduction to Multi-Armed Bandits (2019, background): “Further, (Audibert et al., 2009; Honda and Takemura, 2010; Garivier and Cappé, 2011; Maillard et al., 2011) refine the UCB1 algorithm and obtain improved regret bounds: their regret bounds are at least as good as those for the original algorithm, and get better for some reward distributions.”
On Upper-Confidence Bound Policies for Switching Bandit Problems (2011, background): “In [13], another constant factor is gained by using a different proof.”
Online Learning under Delayed Feedback (2013, methodology): “The KL-UCB algorithm was introduced by Garivier & Capp´e (2011).”
Near-Optimal Regret Bounds for Thompson Sampling (2017, methodology): “…gave the UCB1 algorithm, which achieves a finite time regret bound of [8 Ni = 2 1 Δ ] More recently, Kaufmann et al. (2012a) gave the Bayes-UCB algorithm, and Garivier and Cappé (2011) and Maillard et al. (2011) gave UCB-like algorithms, which achieve the lower bound of Lai and Robbins (1985).”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, background): “Such bounds have sparked recent interest in sequential decision making [18, 19, 20, 21, 22] but to the best of our knowledge we are the first to leverage them for RL.”