Further Optimal Regret Bounds for Thompson Sampling

By Shipra Agrawal, Navin Goyal. 2012

469 citations recorded by the source corpus.

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have comparable or better empirical performance compared to the state of the art methods. In this paper, we provide a novel regret analysis for Thompson Sampling that proves the first near-optimal problem-independent bound of O( √ NT lnT ) on the expected regret of this algorithm. Our novel martingale-based analysis techniques are conceptually simple, and easily extend to distributions other than the Beta distribution. For the version of Thompson Sampling that uses Gaussian priors, we prove a problem-independent bound of O( √ NT lnN) on the expected regret, and demonstrate the optimality of this bound by providing a matching lower bound. This lower bound of Ω( √ NT lnN) is the first lower bound on the performance of a natural version of Thompson Sampling that is away from the general lower bound of O( √ NT ) for the multi-armed bandit problem. Our near-optimal problem-independent bounds for Thompson Sampling solve a COLT 2012 open problem of Chapelle and Li. Additionally, our techniques simultaneously provide the optimal problem-dependent bound of (1+ ǫ) ∑ i lnT d(μi,μ1) +O(Nǫ2 ) on the expected regret. The optimal problem-dependent regret bound for this problem was first proven recently by Kaufmann et al. [2012b]. Appearing in Proceedings of the 16 International Conference on Artificial Intelligence and Statistics (AISTATS) 2013, Scottsdale, AZ, USA. Volume 31 of JMLR: W&CP 31. Copyright 2013 by the authors.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

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 Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

Learning to Optimize via Posterior Sampling (2013, methodology): “This view also suggests that to attain strong minimax regret bounds, one should not choose a uniform prior as in Agrawal and Goyal [5], but should instead place more prior weight on the worst-possible realizations of (see the discussion of “least favorable” prior distributions in Lehmann and Casel”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, background): “This prompted a surge of interest, and a variety of strong theoretical guarantees are now available [12, 13, 14, 15].”
Generalization and Exploration via Randomized Value Functions (2014, methodology): “We will use the following concentration inequality [2] to bound these terms.”
A Tutorial on Thompson Sampling (2017, positive): “A series of papers provided proofs confirming this finding [37, 38, 39].”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, methodology): “…algorithms include the KL-UCB algo-rithm of Capp´e et al. (2013)—a variant of UCB1 (Auer et al. (2002)) using informational upper bounds, Thompson Sampling (Kaufmann et al. (2012b); Agrawal and Goyal (2013)), the DMED algorithm (Honda and Takemura, 2011) and Bayes-UCB (Kaufmann et al., 2012a).”
Deep Exploration via Randomized Value Functions (2017, background): “Further, the theory suggests that “well-designed” upper-confidence-bound-based approaches, which appropriately couple uncertainties across state-action pairs, but are often computationally intractable, are similarly near-optimal (statistically) and competitive with Thompson sampling in such…”
Thompson Sampling for Contextual Bandits with Linear Payoffs (2012, background): “For the the basic (i.e. without contexts) version of the stochastic MAB problem, some signiﬁcant progress was made by Agrawal & Goyal (2012), Kaufmann et al. (2012) and, more recently, by Agrawal & Goyal (2013b), who provided optimal regret bounds on the expected regret.”
An Information-Theoretic Analysis of Thompson Sampling (2014, background): “Agrawal and Goyal [2, 3], Kauﬀmann et al. [18] and Korda et al. [19] studied on the classical multiarmed bandit problem, where sampling one action provides no information about other actions.”
Learning to Optimize via Information-Directed Sampling (2014, background): “empirically eﬀective, and have strong theoretical guarantees. Speciﬁc UCB algorithms and Thompson sampling are known to be asymptotically eﬃcient for multi–armed bandit problems with independent arms [2, 6, 11, 13, 14] and satisfy strong regret bounds for some problems with dependent arms [5, 8, 9, ”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, background): “…the posterior (such as Thompson sampling [Thompson, 1933, 1935] which has been analyzed recently in [Agrawal and Goyal, 2012, Kauffmann et al., 2012, Agrawal and Goyal, 2013, Kaufmann et al., 2013], the Gittins indexes, see [Gittins., 1979, Gittins et al., 1989], and optimistic Bayesian…”
Optimistic posterior sampling for reinforcement learning: worst-case regret bounds (2022, background): “…Long Beach, CA, USA. attractive empirical performance [Chapelle and Li, 2011, Kaufmann et al., 2012], as well as provably optimal performance bounds that have been recently obtained for many variations of MAB [Agrawal and Goyal, 2012, 2013b,a, Russo and Van Roy, 2015, 2014, Bubeck and Liu, 2013].”
Double Thompson Sampling for Dueling Bandits (2016, methodology): “Inspired by the insights from Condorcet dueling bandits, we also discuss how to refine the regret of D-TS in general Copeland dueling bandits.”
Meta reinforcement learning as task inference (2019, background): “…this belief state is at the heart of Bayesian reinforcement learning (Strens, 2000), and many algorithms with optimal regret guarantees such as Thompson sampling (Agrawal & Goyal, 2013) effectively separate the algorithm for estimating the belief state from that for acting based on this estimate.”
Bao: Making Learned Query Optimization Practical (2020, background): “loration, one would choose entirely at random. If one wished to maximize exploitation, one would choose the modal (i.e., E[P(j E)]). Sampling from P( jE) strikes a balance between these two goals [8]. To reiterate, sampling from P(jE) is not the same as training a model over E. We discuss the dieren”
Introduction to Multi-Armed Bandits (2019, methodology): “m (Kaufmann et al., 2012; Agrawal and Goyal, 2013).6 4The statement of Lemma 3.11 is a corollary of a result in Russo and Roy (2014), which makes the technique more transparent. 5For Gaussian priors, Agrawal and Goyal (2013) achieve a slightly stronger version, with logKinstead of T. 6Kaufmann et al”