Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis
By Emilie Kaufmann, N. Korda, R´emi Munos. 2012
619 citations recorded by the source corpus.
The question of the optimality of Thompson Sampling for solving the stochastic multi-armed bandit problem had been open since 1933. In this paper we answer it positively for the case of Bernoulli rewards by providing the first finite-time analysis that matches the asymptotic rate given in the Lai and Robbins lower bound for the cumulative regret. The proof is accompanied by a numerical comparison with other optimal policies, experiments that have been lacking in the literature until now for the Bernoulli case.
Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research, Reinforcement Learning, Game & Decision Theory
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
- Sergey Levine
- Yoshua Bengio
- Pieter Abbeel
- Ruslan Salakhutdinov
- Chelsea Finn
- Quoc V. Le
- Mohit Bansal
- Jianfeng Gao
In Electrical and Electronic Engineering
- R´emi Munos
- Navin Goyal
- Shipra Agrawal
- Tor Lattimore
- Shimon Whiteson
- Csaba Szepesvari
- Benjamin Van Roy
- Elias Bareinboim
In Management Science and Operations Research
- R´emi Munos
- Ian Osband
- Csaba Szepesvari
- Tor Lattimore
- Benjamin Van Roy
- Daniel Russo
- Brendan O'Donoghue
- Nando de Freitas
In Reinforcement Learning
- Sergey Levine
- Pieter Abbeel
- R´emi Munos
- Shimon Whiteson
- Ian Osband
- Yuxi Li
- Chelsea Finn
- Brendan O'Donoghue
In Game & Decision Theory
- R´emi Munos
- Tor Lattimore
- Csaba Szepesvari
- Nando de Freitas
- Aurélien Garivier
- Daniel Russo
- Matthew D. Hoffman
- Gilles Stoltz
Citations in the corpus
- Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “…regret bounds in the deterministic setting [43]; bounds for contextual Gaussian process bandits [89]; Bayes regret bounds for Thompson sampling [85], [127]; bounds for high-dimensional problems with a underlying low-rank structure [46]; bounds for parallel Bayesian optimization [45]; and…”
- Learning to reinforcement learn (2016, methodology): “Model simulations were conducted with the PymaBandits toolbox from (Kaufmann et al., 2012a) and custom Matlab scripts.”
- Weight Uncertainty in Neural Networks (2015, background): “There is an increasing literature concerning the efficacy and justification of this means of exploration (Chapelle and Li, 2011; May et al., 2012; Kaufmann et al., 2012; Agrawal and Goyal, 2012; 2013).”
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “In Salomon and Audibert [2011] it is proved that for anytime strategies (i.e., strategies that do not use the time horizon n) it is basically impossible to improve this polynomial concentration to a classical exponential concentration.”
- Learning to Optimize via Posterior Sampling (2013, background): “[22]) provide regret bounds for posterior sampling when applied to MAB problems with finitely many independent actions and rewards that follow Bernoulli processes.”
- 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).”
- Thompson Sampling for Contextual Bandits with Linear Payoffs (2012, methodology): “Several studies (e.g., Granmo (2010); Scott (2010); Graepel et al. (2010); Chapelle & Li (2011); May & Leslie (2011); Kaufmann et al. (2012)) have empirically demonstrated the efficacy of TS: Scott (2010) provides a detailed discussion of probability matching techniques in many general settings along…”
- Near-optimal Reinforcement Learning in Factored MDPs (2014, background): “Posterior sampling has already been shown to perform extremely well in bandits [15, 16, 17] and non-factored MDPs [13].”
- From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, background): “…as a function of 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…”
- Boltzmann Exploration Done Right (2017, background): “There exist several algorithms guaranteeing matching upper bounds, even for finite horizons [7, 10, 15].”
- Convex Optimization: Algorithms and Complexity (2015, neutral): “[Kaufmann et al., 2012b] For any > 0, there exists a problem-dependent constant C( ,θ) such that the regret of TS satisfies Eθ [ Regret(T ) ] ≤ (1 + ) ∑ a6=a∗ ∆a ( ln(T ) + ln ln(T ) ) KLθ (a, a∗) + C( ,θ).”
- Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “D-TS relies on Thompson sampling (Thompson, 1933; Agrawal and Goyal, 2013; Kaufmann et al., 2012; Chapelle and Li, 2011) to choose an optimal action that maximizes the expected reward according to the agent’s current belief (randomly drawn according to the current prior).”
- Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling (2018, methodology): “The algorithm is a variant of Thompson Sampling [34, 1] that is conditioning on the “worst” outcome µ ∗ γ , hence the name Murphy Sampling.”
- An Information-Theoretic Analysis of Thompson Sampling (2014, background): “Agrawal and Goyal [2, 3], Kauffmann 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.”