A Tutorial on Thompson Sampling
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni et al. · now publishers, Inc. eBooks · 2018
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. A Tutorial on Thompson Sampling 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. It also discusses when and why Thompson sampling is or is not effective and relations to alternative algorithms.
Cited by 380 works. doi:10.1561/9781680834710
Authors
References
- Reinforcement Learning: An Introduction
- Explaining the Gibbs Sampler
- Introduction to Reinforcement Learning
- Finite-time Analysis of the Multiarmed Bandit Problem
- Asymptotically efficient adaptive allocation rules
- ON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLES
- Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
- A contextual-bandit approach to personalized news article recommendation
- Multi-Armed Bandit Allocation Indices.
- Bayesian Learning via Stochastic Gradient Langevin Dynamics