PaperlayerView exact revision on arXiv

Source-linked AI summary

A Tutorial on Thompson Sampling

Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen

arXiv:1707.02038v3cs.LG

TL;DR

Sequential decision problems require balancing immediate rewards against information gathering for future decisions. This tutorial explains Thompson sampling across structured problems and shows that it can focus exploration on actions with a chance of being optimal, while also identifying settings where it performs poorly.

  • Problem

    Online decision systems must balance exploiting known rewards with exploring uncertain actions that may improve future performance.

  • Method

    The tutorial develops Thompson sampling, which uses posterior sampling to guide decisions across problems including bandits and shortest paths.

  • Results

    Thompson sampling explores to resolve uncertainty where doing so may identify the optimal action, while avoiding feedback that would not be helpful.

  • Takeaways & Limitations

    Thompson sampling offers a flexible and efficient approach to exploration in a wide range of structured decision problems.

  • Takeaways & Limitations

    Thompson sampling leaves substantial value on the table in some contexts, including problems that do not require exploration or exploitation.

Abstract

from arXiv · show

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.

Introduction

Online decision problems require balancing immediate exploitation with exploration that generates information for future decisions. The tutorial develops Thompson sampling as a flexible and efficient approach across structured problems such as bandits and shortest paths.

  • Motivation: The multi-armed bandit problem asks how to balance exploiting high-payout actions with exploring alternatives to maximize cumulative payout.
  • Motivation: In Bernoulli bandits, unknown but time-invariant success probabilities must be learned while maximizing cumulative successes over many periods.
  • Motivation: Online recommendation systems generate their own training data, creating potential benefit from algorithms that explore systematically while learning from past outcomes.
  • Structured problems: Shortest-path decisions require learning uncertain edge travel times while minimizing cumulative travel time across repeated trips.
  • Structured problems: Because the number of paths can scale exponentially with graph size, efficient methods must exploit statistical and computational structure rather than enumerate all paths.
  • Tutorial scope: The tutorial explains Thompson sampling, its applications, computational approximations, practical considerations, limitations, and alternatives, with accompanying reproducible Python experiments.

Greedy Decisions

Greedy online algorithms select actions that maximize estimated immediate reward but do not actively explore. Dithering adds random exploration, yet can waste trials on actions that are unlikely to be optimal.

  • Greedy decisions: A greedy algorithm estimates a model from historical data and selects the action that is optimal under the estimated parameters.
  • Greedy decisions: Greedy decisions can severely curtail performance because they do not actively explore uncertain actions that might have higher mean rewards.
  • Dithering: Dithering randomly perturbs greedy choices, with ϵ-greedy exploration selecting the greedy action with probability 1 −ϵ and otherwise sampling uniformly.
  • Dithering: Uniform dithering wastes trials because it explores actions equally even when some are very unlikely to be optimal and others remain meaningfully uncertain.
  • Dithering: Thompson sampling provides an alternative to dithering that allocates exploration effort more intelligently.

Thompson Sampling for the Bernoulli Bandit

The beta-Bernoulli bandit models uncertainty about fixed action success probabilities with Bayesian priors. Thompson sampling builds on this model by updating beliefs from observed binary rewards.

  • Beta-Bernoulli model: In the beta-Bernoulli bandit, each action yields a binary reward with an unknown but fixed success probability.
  • Beta-Bernoulli model: The agent begins with independent beta-distributed prior beliefs over the actions’ success probabilities.

14 Thompson Sampling for the Bernoulli Bandit

For the beta-Bernoulli bandit, Thompson sampling samples each action’s success probability from its posterior and chooses the action with the largest sample. This concentrates exploration on actions that may plausibly be optimal.

  • Algorithm: Greedy estimation uses each action’s posterior mean, αk/(αk + βk), to select the action with the largest estimated success probability.
  • Algorithm: Thompson sampling instead draws each action estimate from its beta posterior before selecting the action with the largest draw.
  • Algorithm: Posterior parameters are updated after observing the selected action’s binary reward.
  • Exploration behavior: In the illustrated three-action example, Thompson sampling selects actions 1, 2, and 3 with approximate probabilities 0.82, 0, and 0.18, respectively.
  • Exploration behavior: These selection probabilities equal the posterior probabilities that the corresponding actions are optimal, so exploration targets uncertainty with potential value.
  • Simulation: Simulations compare Thompson sampling and greedy behavior in a three-armed beta-Bernoulli bandit over ten thousand independent runs and one thousand periods.

16 Thompson Sampling for the Bernoulli Bandit

In the three-armed Bernoulli bandit, Thompson sampling learns the optimal action, while greedy selection can become stuck on a suboptimal action. Accordingly, Thompson sampling’s per-period regret vanishes over time, unlike the greedy algorithm’s.

  • Thompson sampling learns to select optimal action 1 within the thousand-period simulations, whereas greedy selection can remain stuck on a poor action.Greedy selection may reinforce an initially lucky but suboptimal action.
  • The greedy algorithm does not always converge on action 1, the optimal action, because it can repeatedly apply a poor action.
  • Per-period regret of Thompson sampling vanishes as time progresses, unlike the greedy algorithm’s regret.The regret comparison is averaged over ten thousand simulations.
  • Regret was evaluated both for fixed mean rewards and across plausible mean rewards sampled from uniform priors, with qualitatively similar plot features.

General Thompson Sampling

General Thompson sampling samples a model from the current belief distribution, selects the action optimal for that sampled model, observes an outcome, and updates beliefs. The framework extends from Bernoulli bandits to structured problems such as shortest paths, where modeling information dependencies can materially improve learning.

  • General framework: The general formulation supports finite or infinite action sets and outcomes generated according to a parameterized conditional probability measure.
  • General framework: Thompson sampling samples model parameters from the current belief distribution, chooses the action maximizing expected reward under that sample, observes an outcome, and updates beliefs.
  • Bernoulli special case: The Bernoulli bandit with a beta prior is a special case in which actions are arms, only rewards are observed, and action means have independent beta priors.
  • Shortest paths: In the independent-travel-time shortest path problem, sampled edge parameters define a deterministic shortest path optimization that can be solved efficiently, including with Dijkstra’s algorithm.The selected path produces observed edge travel times used to update posterior parameters.
  • Shortest paths: In a twenty-stage binomial bridge with 184,756 paths, Thompson sampling converges quickly to optimal performance, while greedy learning remains far slower.Each plotted data point averages ten thousand independent simulations.
  • Shortest paths: Cumulative travel time under Thompson sampling converges toward the optimal benchmark at a respectable rate, unlike the ϵ-greedy approaches.
  • Correlated travel times: Accounting for interdependencies among correlated edge travel times substantially improves performance relative to misspecified Thompson sampling.The model assumes the agent selects a path before each trip and cannot adjust it during the trip.

Approximations

When exact Bayesian inference is infeasible, approximate posterior-sampling methods provide practical implementations of Thompson sampling, but their assumptions and computational costs differ. In the binary-feedback shortest-path example, these methods support effective learning, while some approximations can underperform or become expensive.

  • Overview: Approximate Thompson sampling uses posterior-sampling methods when complex models make exact Bayesian inference computationally infeasible.The tutorial discusses Gibbs sampling, Langevin Monte Carlo, Laplace approximation, and bootstrap methods.
  • Binary Feedback: In the binary-feedback shortest-path problem, approximate methods achieve effective learning, with regret vanishing over time relative to a greedy baseline.The methods evaluated are Langevin Monte Carlo, Laplace approximation, and bootstrap.
  • Gibbs Sampling: Gibbs sampling generates approximate posterior samples through repeated sweeps over one-dimensional conditional distributions.After the sweeps, the resulting parameter vector is used as the approximate posterior sample.
  • Gibbs Sampling: Gibbs sampling can be computationally viable because one-dimensional sampling is simpler, but complex path problems can still make it computationally demanding.The tutorial therefore turns to more efficient approximation methods for large simulation workloads.
  • Other Approximations: Laplace approximation relies on a local Gaussian approximation, and its shortest-path performance falls short of Langevin Monte Carlo when the posterior is not sufficiently Gaussian.Bootstrap performs about as well as Laplace approximation in the cited example and is nonparametric, whereas Laplace relies on Gaussian structure.
  • Computational Trade-offs: Approximation-method computation grows with time because each past observation must be accessed, unlike exact methods that update posterior parameters using only the latest observation.This creates a practical trade-off between inference flexibility and per-period computation.

Practical Modeling Considerations

Practical Thompson sampling depends on prior specification and extensions for changing action sets, contextual information, caution constraints, and nonstationary systems. Coherent priors improve learning, while nonstationary Thompson sampling preserves reasonable performance when the environment drifts.

  • Prior Distribution Specification: Prior specification matters because informative prior knowledge can reduce the time Thompson sampling needs to identify effective actions.A uniform prior may ignore useful contextual knowledge from past experience.
  • Prior Distribution Specification: Empirical prior selection can use stylistic similarity among past advertisements to construct informative click-through-probability distributions.The resulting prior virtually rules out click-through probabilities greater than 0.05.
  • Prior Distribution Specification: A coherent prior matches the problem’s understanding, whereas a misspecified prior increases regret and delays learning in the three-armed Bernoulli bandit simulations.The comparison uses beta(1, 50), beta(1, 100), and beta(1, 200) action distributions against a uniform prior.
  • Constraints, Context, and Caution: Thompson sampling accommodates time-varying admissible action sets by constraining the maximization step when those sets do not depend on unknown parameters.This extension supports practical action restrictions that may change over time.
  • Constraints, Context, and Caution: Contextual online decisions can be handled by augmenting the action with observed context and constraining the augmented action to preserve that context.The tutorial illustrates this with weather-dependent shortest-path decisions.
  • Nonstationary Systems: For nonstationary systems, nonstationary Thompson sampling retains reasonable performance as the system drifts, whereas stationary Thompson sampling becomes less effective.The simulations use decay rate γ = 0.01 and average results over 10,000 independent simulations; no algorithm can promise vanishing regret under nonstationarity.
  • Concurrency: Concurrent Thompson sampling draws independent posterior samples for multiple agents, but delayed posterior updates prevent concurrent actions from informing one another.The posterior is updated only after the concurrent actions are completed.

Further Examples

The tutorial extends Thompson sampling to contextual news recommendation, using approximate posterior sampling when exact Bayesian inference is impractical. Simulations show substantial regret advantages over optimized ϵ-greedy, while highlighting limitations of article-specific and time-invariant modeling.

  • News Article Recommendation: News recommendation uses user features to choose articles online and learn from recommendation outcomes.Features can include recent activities, demographics, and context such as location or day of week.
  • News Article Recommendation: The model assigns each article its own parameter vector and uses a logistic probability model to predict user approval.This formulation supports generalization across users by learning from recommendations made to different users.
  • News Article Recommendation: Approximate Thompson sampling uses either a Laplace posterior approximation or Langevin Monte Carlo because exact Bayesian inference is computationally infeasible.The comparison includes greedy and ϵ-greedy baselines, with ϵ selected by searching for the best-performing value.
  • News Article Recommendation: Substantially lower regret was achieved by Thompson sampling than by optimized ϵ-greedy in simulations averaged over 2,000 random problem instances.The best ϵ-greedy setting used ϵ = 0.01; both Laplace and Langevin Monte Carlo approximations were evaluated.
  • News Article Recommendation: The simplified model cannot generalize across news articles, requiring separate parameter estimates for each article.Generalization models can instead transfer information from one article to another, while the considered article set is also fixed over time.

7.2 Product Assortment

The product assortment problem requires learning demand interactions while selecting profitable product subsets. Thompson sampling draws from a Gaussian posterior over demand parameters and outperforms the evaluated ϵ-greedy variants in simulation.

  • Problem formulation: The agent selects product assortments to maximize profit when products may be substitutes or complements.Demand for one product can depend on which other products are offered in the same period.
  • Problem formulation: Unknown demand parameters require exploration across assortments while observing realized product demands.If the parameters were known, the agent would always choose the assortment maximizing expected profit.
  • Thompson sampling: Thompson sampling draws a demand-parameter sample from the Gaussian posterior and selects the assortment maximizing expected profit under that sample.Gaussian conjugacy keeps the posterior Gaussian and enables computationally efficient updates.
  • Simulation: The simulation uses n = 6 products, σ2 = 0.04, equal product profits pi = 1/6, and independent Gaussian prior elements with different diagonal and off-diagonal variances.The prior distinguishes standalone demand effects from cross-product demand effects.

7.3. Cascading Recommendations

In cascading recommendations, Thompson sampling selects ordered lists using sampled item attraction probabilities and updates beliefs from observed user behavior. It strongly outperforms one UCB configuration in a high-dimensional setting, although tuned UCB can win in a smaller one.

  • Cascading bandits: A cascading bandit presents an ordered list of J items from K candidates, and the user examines items sequentially until selecting one or leaving.The reward indicates whether any recommended item was selected.
  • Cascading bandits: The optimal list contains the J items with the largest attraction probabilities, and regret compares its expected reward with the selected list’s expected reward.The expected reward is represented by h(xt, θ).
  • Algorithms: CascadeTS samples item attraction probabilities and chooses the list maximizing expected reward, whereas CascadeUCB uses itemwise upper confidence bounds.Both methods update statistics from clicks and views among examined items.
  • Results: Thompson sampling far outperformed UCB1-based CascadeUCB for K = 1000 items and J = 100 recommendations per period.The comparison averages per-period regret over 1,000 simulations, each run for 20,000 periods.
  • Interpretation: Sampled attraction probabilities reflect joint uncertainty more accurately than UCB confidence values that can make every item in a list simultaneously appear overly attractive.Independent sampling makes it unlikely that all items in a list simultaneously receive large upward deviations.

7.4. Active Learning with Neural Networks

The supplied passages for this section report a tuned CascadeUCB comparison in a smaller cascading-bandit setting, where CascadeUCB outperformed CascadeTS.

  • Active Learning with Neural Networks: Tuned CascadeUCB can perform as well as or better than CascadeTS in some settings.The cited comparison uses K = 50 items and J = 10 recommendations per period.

7.4 Active Learning with Neural Networks

Active learning with neural networks uses Thompson sampling principles to select actions that both generate informative data and pursue desirable outcomes. Because exact posterior computation is intractable for complex models, ensemble-based approximations provide a practical approach.

  • Neural-network active learning selects actions to balance immediate performance with generating data that accelerates learning.
  • Posterior computation becomes intractable with neural networks, making approximate and incrementally updated methods necessary.
  • Ensemble sampling offers a viable approximation for applying Thompson sampling with complex model classes.
  • The linear bandit provides a simple setting for explaining ensemble sampling, although exact Bayesian inference is efficiently available through Kalman filtering.

7.4. Active Learning with Neural Networks

The tutorial extends ensemble sampling from linear bandits to neural networks by incrementally updating multiple perturbed models. Simulations show that ensemble sampling can outperform tuned exploration schedules while remaining effective with relatively few ensemble members.

  • Each ensemble model is fit using randomly perturbed priors and observations, producing independent posterior-distributed models conditioned on history.
  • For neural networks, actions and observed responses train models whose choices trade off reducing parameter uncertainty against immediate reward.
  • The neural-network simulations use 100-dimensional inputs, 50-dimensional hidden layers, 100 actions, prior variance λ = 1, and noise variance σ^2_z = 100.
  • Ensemble sampling outperforms the best tuned ϵ-schedules and can perform well with remarkably few ensemble members.

7.5 Reinforcement Learning in Markov Decision Processes

In reinforcement learning, Thompson sampling must account for delayed consequences and temporally extended exploration. Sampling once per episode preserves consistent policies and can greatly outperform resampling at every timestep, while also reducing computation.

  • Reinforcement learning extends online decision problems with delayed feedback and long-term consequences across MDP episodes.
  • A naive timestep-level application of Thompson sampling can explore inefficiently because it fails to maintain consistent policies within an episode.
  • Sampling once before each episode enables deep exploration and learns the optimal policy within a single episode in the chain example.
  • Posterior sampling for policy selection samples rewards and transition dynamics, then solves for the optimal policy under that sampled model.
  • With an informative prior, per-timestep sampling requires a minimum of 2^N episodes for the first expected reward, whereas per-episode sampling learns in one episode.
  • Under less informative priors, per-episode sampling still performs better, with benefits increasing with MDP size and requiring fewer policy computations.

Approaches

The tutorial develops regret analyses showing when Thompson sampling is effective, how it exploits structure and prior knowledge, and where standard guarantees or applications have important limitations.

  • Classical bandit guarantees: Thompson sampling has asymptotically optimal regret scaling for classical Bernoulli bandits, matching the Lai–Robbins lower-bound scaling.The result has been proved for Bernoulli rewards and extended to Gaussian and canonical one-dimensional exponential-family rewards.
  • Classical bandit guarantees: Its O(log(T)) regret bounds can become vacuous when many actions are nearly optimal, especially in complex structured decision problems.In such settings, the relevant bound may become arbitrarily large because it accumulates contributions from near-optimal actions.
  • Scope and limitations: The tutorial cautions that theoretical results alone do not justify applying Thompson sampling to every complex online decision problem.Its broader analyses identify both settings where the algorithm exploits structure and prior knowledge and settings where it performs poorly.
  • Regret bounds via UCB: Broader analyses show that Thompson sampling can inherit expected-regret bounds from corresponding UCB algorithms without requiring an explicitly designed upper-confidence bound.This is especially useful when complicated dependencies among actions make suitable confidence bounds difficult to design and compute.
  • Regret bounds via UCB: For parameterized reward models, regret can depend on model dimension rather than the number of actions, allowing analyses to cover very large or infinite action sets.The unified bounds characterize function-class complexity using covering numbers and eluder dimension; standard supervised-learning complexity notions alone are insufficient.
  • Regret bounds via information theory: In shortest-path problems, information-theoretic bounds depend on the number of edges and the prior entropy over the shortest path, rather than the potentially exponential number of paths.Richer feedback can further improve the information ratio, with edge-level feedback yielding a bound involving d/2m.
Loading 1707.02038v3…