Kullback–Leibler upper confidence bounds for optimal sequential allocation

By Olivier Capp'e, Aurélien Garivier, Odalric-Ambrym Maillard, R´emi Munos, Gilles Stoltz. 2012

425 citations recorded by the source corpus.

We consider optimal sequential allocation in the context of the so-called stochastic multi-armed bandit model. We describe a generic index policy, in the sense of Gittins (1979), based on upper confidence bounds of the arm payoffs computed using the Kullback-Leibler divergence. We consider two classes of distributions for which instances of this general idea are analyzed: The kl-UCB algorithm is designed for one-parameter exponential families and the empirical KL-UCB algorithm for bounded and finitely supported distributions. Our main contribution is a unified finite-time analysis of the regret of these algorithms that asymptotically matches the lower bounds of Lai and Robbins (1985) and Burnetas and Katehakis (1996), respectively. We also investigate the behavior of these algorithms when used with general bounded rewards, showing in particular that they provide significant improvements over the state-of-the-art.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/161c91acafc365ab0b131dd7e2043a52a68972e3

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 Management Science and Operations Research

Citations in the corpus

Boltzmann Exploration Done Right (2017, background): “There exist several algorithms guaranteeing matching upper bounds, even for finite horizons [7, 10, 15].”
Information Complexity in Bandit Subset Selection (2013, methodology): “Although we have only considered Bernoulli distributions in this paper, note that KL-LUCB naturally extends to rewards in the exponential family (by using an appropriate d function, as shown by Cappé et al. (2013) for KL-UCB), and that Theorems 1 and 2 still hold in this more general setting.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, positive): “[2011] (see also Cappé et al. [2012]) independently proposed a similar algorithm, called KL-UCB, which is shown to attain the optimal rate in finite-time.”
Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem (2013, positive): “Recently reﬁned upper-conﬁdence bounds (such as UCB-V (Audibert et al., 2009) or KL-UCB (Capp´e et al., 2013)) have improved performance for the regular K -armed ban-dit problem.”
Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling (2018, background): “Such exponential families include Gaussian with known variance, Bernoulli, Poisson, see [5] for details.”
A Tutorial on Thompson Sampling (2017, background): “UCB algorithms have been proposed for a variety of problems, including bandit problems with independent arms [36, 53, 54, 55], bandit problems with linearly parameterized arms [30, 56], bandits with continuous action spaces and smooth reward functions [57, 58, 59], and exploration in reinforcement l”
Structural Causal Bandits: Where to Intervene? (2018, methodology): “Many strategies were developed to solve this problem, including classic algorithms such as -greedy, variants of UCB (Auer et al., 2002, Cappé et al., 2013), and Thompson sampling [Thompson, 1933].”
Bandit Algorithms (2020, methodology): “In terms of upper bounds, there now exist policies that are asymptotic optimal for single-parameter exponential families [Cappé et al., 2013].”
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”
Learning to Optimize via Posterior Sampling (2013, background): “[14]) for problems with independent arms, but it is often unclear how to generate tight confidence sets for more complicated models.”
Copeland Dueling Bandits (2015, background): “For instance, SAVAGE’s cumulative regret at time 2 × 107 is lower than at time 107 because the runs that produced the former number were not continuations of those that resulted in the latter, but rather completely independent.”
Optimal Best Arm Identification with Fixed Confidence (2016, neutral): “A strategy is then deﬁned by: • a sampling rule ( A t ) t , where A t is F t 1 -measurable; • a stopping rule τ , which is a stopping time with respect to F t ; • and a F τ -measurable decision rule ˆ a τ .”
Estimating means of bounded random variables by betting (2020, background): “24 [14] Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz.”