A Tutorial on Thompson Sampling

Abstract

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.

References in corpus (11)

• Further Optimal Regret Bounds for Thompson Sampling
• Deep Exploration via Randomized Value Functions
• An Efficient Bandit Algorithm for Realtime Multivariate Optimization
• Cascading Bandits: Learning to Rank in the Cascade Model
• Convergence of Langevin MCMC in KL-divergence
• Ensemble Sampling
• Model-based Reinforcement Learning and the Eluder Dimension
• Information Directed Sampling for Stochastic Bandits with Graph Feedback
• Asynchronous Parallel Bayesian Optimisation via Thompson Sampling
• On Optimistic versus Randomized Exploration in Reinforcement Learning
• Time-Sensitive Bandit Learning and Satisficing Thompson Sampling

Cited by in corpus (21)

• On the Sample Complexity of the Linear Quadratic Regulator
• Bayesian Optimization of Combinatorial Structures
• Behaviour Suite for Reinforcement Learning
• Neural Thompson Sampling
• Thompson Sampling for Dynamic Pricing
• Scalable Coordinated Exploration in Concurrent Reinforcement Learning
• PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits
• Active Feature Acquisition with Generative Surrogate Models
• Decoupling Exploration and Exploitation for Meta-Reinforcement Learning without Sacrifices
• VFunc: a Deep Generative Model for Functions
• Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models
• The Potential of the Return Distribution for Exploration in RL
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Efficient Model-Free Reinforcement Learning Using Gaussian Process
• Parallelizing Thompson Sampling
• Coordinated Exploration in Concurrent Reinforcement Learning
• Adaptively Optimize Content Recommendation Using Multi Armed Bandit Algorithms in E-commerce
• A Reliability-aware Multi-armed Bandit Approach to Learn and Select Users in Demand Response
• Finite Horizon Throughput Maximization and Sensing Optimization in Wireless Powered Devices over Fading Channels
• Dynamic Feature Acquisition with Arbitrary Conditional Flows
• Sonic: A Sampling-based Online Controller for Streaming Applications