A Tutorial on Thompson Sampling

By Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband. 2017

1,218 citations recorded by the source corpus.

Thompson sampling is an algorithm for online decision problems where actions are taken sequentially in a manner that must balance between exploiting what is known to maximize immediate performance and investing to accumulate new information that may improve future performance. The algorithm addresses a broad range of problems in a computationally efficient manner and is therefore enjoying wide use. This tutorial covers the algorithm and its application, illustrating concepts through a range of examples, including Bernoulli bandit problems, shortest path problems, product recommendation, assortment, active learning with neural networks, and reinforcement learning in Markov decision processes. Most of these problems involve complex information structures, where information revealed by taking an action informs beliefs about other actions. We will also discuss when and why Thompson sampling is or is not effective and relations to alternative algorithms.

Subfields: Artificial Intelligence, Reinforcement Learning, Statistical Learning 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

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Learning World Graphs to Accelerate Hierarchical Reinforcement Learning (2019, neutral): “To ensure differentiablity, we opt to use a continuous relaxation of discrete binary latent variables by learning a Beta distribution as the priors for z t ’s [82].”
Balanced Linear Contextual Bandits (2018, methodology): “Thompson Sampling (Thompson 1933), (Scott 2010), (Agrawal and Goyal 2012), (Russo et al. 2018) and Upper Confidence Bounds (UCB) (Lai and Robbins 1985), (Auer, CesaBianchi, and Fischer 2002) are two different methods which are highly effective in dealing with the exploration vs.”
Estimation Considerations in Contextual Bandits (2017, methodology): “Thompson sampling [61, 55, 5, 52] and upper confidence bound (UCB) [40, 12] are two different methods for assigning contexts to arms which are highly effective in dealing with the exploration-exploitation trade-off.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “If K-learning is run with the optimal choice of temperature τ t then it is additionally a stationary strategy in that the action distribution depends solely on the posteriors and is otherwise independent of the time period [49].”
Watch, Try, Learn: Meta-Learning from Demonstrations and Reward (2019, background): “One simple and effective strategy for exploration is posterior or Thompson sampling [31, 30], i.”
Behaviour Suite for Reinforcement Learning (2019, neutral): “These results are not predicted by the theoretical scaling of proven bounds (Lu & Van Roy, 2017), but are consistent with previous empirical ﬁndings (Osband et al., 2017; Russo et al., 2017).”
Hypermodels for Exploration (2020, methodology): “See (Russo et al., 2018) for an understanding when and why TS is effective.”
A Contextual Bandit Bake-off (2018, neutral): “In particular, strategies based on upper conﬁdence bounds (Abbasi-Yadkori et al., 2011; Li et al., 2010) or Thompson sampling (Agrawal and Goyal, 2013; Russo et al., 2018) are often intractable for sparse, high-dimensional datasets, and make strong assumptions on the model representation.”
Meta-learning of Sequential Strategies (2019, background): “(do an update step) return f the reader to [Russo et al., 2018, Osband and Van Roy, 2016, Ouyang et al., 2017] for a detailed discussion.”
Effective Diversity in Population-Based Reinforcement Learning (2020, methodology): “Let’s start by defining the Thompson Sampling updates for Bernoulli random variables.”
Neural Approaches to Conversational AI (2018, positive): “information leads to a natural exploration strategy, inspired by Thompson Sampling (Thompson, 1933; Chapelle and Li, 2012; Russo et al., 2018).”
AutoSeM: Automatic Task Selection and Mixing in Multi-Task Learning (2019, background): “…Bayesian approach, and it can capture a wide variety of underlying functions or relations be-tween inputs and outputs by taking advantage of the full information provided by the history of observations and is thus very data-efﬁcient (Ras-mussen, 2004; Shahriari et al., 2016; Schulz et al., 2018).”
Making Sense of Reinforcement Learning and Probabilistic Inference (2020, methodology): “Thompson sampling is a simple and effective method that successfully balances exploration with exploitation (Russo et al., 2018).”