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 performance with learning, often under complex information structures and computational constraints. This tutorial explains Thompson sampling across a broad range of applications and shows that its efficiency can exploit problem structure, while also identifying settings where it performs poorly.

  • Problem

    Sequential decision-making must balance exploiting uncertain actions with exploring to learn, while some structured problems have exponentially many actions that cannot be searched directly.

    Source: Introduction · pp. 3, 6

  • Method

    The tutorial explains Thompson sampling, which selects actions by sampling from posterior distributions, and develops applications across diverse online decision problems.

    Source: Introduction · p. 8, §14 · p. 15

  • Results

    Thompson sampling can learn efficiently in shortest-path problems through bounds depending on the number of edges and the prior entropy of the shortest path.

    Source: Regret Bounds via Information Theory · p. 81

  • Takeaways & Limitations

    Thompson sampling is effective across a broad range of problems, but its value depends on whether the setting requires both exploration and exploitation.

    Source: §8.2 · p. 83, §8.2.2 · p. 85

    The tutorial identifies settings where Thompson sampling leaves substantial value on the table, including problems that do not require exploitation.

    Source: §8.2 · p. 83, §8.2.2 · p. 85

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

The introduction frames sequential decision-making as a tradeoff between exploiting known high-performing actions and exploring to improve future performance. It presents Thompson sampling as a flexible, efficient approach for structured problems and outlines the tutorial’s scope, applications, practical guidance, and limitations.

Motivation

  • Sequential decision problems require balancing exploitation of observed rewards with exploration that can reveal better future actions.The Bernoulli bandit formalizes unknown, fixed success probabilities and cumulative-performance maximization over many periods.Source: Introduction · pp. 3–4
  • Fixed-fraction random exploration can waste samples in Bernoulli bandits and fail completely in more complicated problems.The introduction contrasts this naive strategy with settings where experimentation is costly or data-rich, such as highway and Internet advertising.Source: Introduction · p. 4
  • Online learning systems generate their own training data through interaction, creating opportunities for algorithms that explore systematically while optimizing future performance.Recommendation systems exemplify this feedback loop, while shortest-path learning illustrates the extension to structured decisions.Source: Introduction · p. 5

Structured decision problems

  • Shortest-path learning is challenging because the action space can grow exponentially, making exhaustive path sampling and enumeration computationally intractable.The agent observes realized edge travel times, accumulates path costs, and must exploit statistical and computational structure.Source: Introduction · p. 6

Thompson sampling

  • Thompson sampling accommodates flexible feedback and statistical models while offering an efficient exploration approach for structured problems such as shortest paths.The introduction notes that feedback may reveal edge-level or only total-path outcomes, and delays may be correlated rather than independent.Source: Introduction · pp. 6–7

Tutorial scope

  • The tutorial explains when, why, and how to apply Thompson sampling across diverse examples, including approximations, priors, safety, nonstationarity, theory, poor-performance settings, and alternatives.It also releases Python code reproducing the experiments and figures and begins with a non-exploring baseline.Source: Introduction · pp. 7–8

Greedy Decisions

Greedy online decision algorithms choose the action maximizing estimated immediate reward, but they do not actively explore uncertainty. This can prevent learning about potentially superior actions, while ε-greedy exploration may waste trials on actions that are very unlikely to be optimal.

Greedy Decisions

  • Greedy algorithms estimate a model from historical data and select the action optimal under that estimate, assuming the estimated parameters are correct.At each time t, supervised learning fits parameters to historical pairs, predicts reward, and an optimization procedure selects the maximizing action before observing the outcome.Source: Greedy Decisions · p. 9
  • Greedy decisions can severely curtail performance because they do not actively explore uncertain actions that might yield higher long-run rewards.In the Bernoulli bandit example, repeatedly choosing the well-estimated best action prevents learning whether an uncertain action is actually superior.Source: Greedy Decisions · pp. 9–11
  • ε-greedy exploration improves on pure greediness but wastes trials by exploring actions uniformly, including those almost certainly inferior.It chooses the greedy action with probability 1−ε and otherwise selects uniformly at random, allocating equal exploratory effort even when uncertainty differs sharply across actions.Source: Greedy Decisions · p. 11
  • Thompson sampling provides an alternative to dithering that allocates exploration effort more intelligently.The approach is motivated by the need to explore uncertain actions while avoiding experimental trials for actions that are very unlikely to be optimal.Source: Greedy Decisions · pp. 11–12

Thompson Sampling for the Bernoulli Bandit

This section introduces Thompson sampling through a Bernoulli bandit with unknown, fixed action success probabilities and Bayesian beliefs about those probabilities. Each action yields binary rewards, and the agent updates its decision process sequentially after observing outcomes.

Beta-Bernoulli Bandit

  • The Beta-Bernoulli bandit has K actions with unknown but fixed success probabilities θ_k, where each play produces a binary reward.Action k yields reward 1 with probability θ_k and reward 0 with probability 1 − θ_k; the agent selects actions and observes rewards over successive periods.Source: Thompson Sampling for the Bernoulli… · p. 13
  • Thompson sampling represents uncertainty by assigning independent beta-distributed prior beliefs to each action’s success probability.The priors are parameterized by action-specific α and β values.Source: Thompson Sampling for the Bernoulli… · p. 13

14 Thompson Sampling for the Bernoulli Bandit

For Bernoulli bandits, Thompson sampling samples each action’s success probability from its beta posterior, selects the largest sampled value, and updates only the selected action’s posterior after observing the reward. Unlike greedy selection or uniform dithering, it explores in proportion to the posterior probability that an action is optimal, concentrating learning where it may improve decisions.

Comparison

  • Greedy selection chooses the action with the highest posterior mean, whereas TS replaces that deterministic estimate with a posterior sample while retaining the same selection and update structure.Greedy behavior can miss valuable learning opportunities, while uniform dithering may probe actions that are very unlikely to be optimal.Source: §14 · pp. 14–15

Algorithm

  • TS samples each action’s success probability from its beta posterior, selects the action with the largest sample, and updates that action’s beta parameters using the observed reward.The update adds the binary reward to α and its complement to β.Source: §14 · pp. 14–15
  • TS represents a statistically plausible success probability, not a statistically plausible binary observation.This distinction prevents confusing posterior sampling of θ̂_k with sampling the outcome y_t that would follow action k.Source: §14 · p. 14

Exploration

  • TS explores according to each action’s posterior probability of being optimal, avoiding probes whose feedback is unlikely to improve identification of the best action.In the illustrated three-armed case, actions 1, 2, and 3 are sampled with probabilities approximately 0.82, 0, and 0.18, respectively.Source: §14 · p. 15

16 Thompson Sampling for the Bernoulli Bandit

In the three-armed Bernoulli bandit, Thompson sampling avoids the greedy algorithm’s tendency to become trapped on a poor action and learns to select the optimal action. Its per-period regret vanishes over time, including when averaged across bandit instances drawn from prior distributions.

Action selection

  • Thompson sampling learns to select optimal action 1 within 1,000 periods, whereas the greedy algorithm can remain trapped repeatedly selecting poor action 3.Greedy selection of action 3 can be reinforced after early rewards, as its estimated mean converges toward 0.7 while alternatives remain at 0.5.Source: §16 · p. 16, Figure 3.1 · p. 16

Regret

  • The average per-period regret of Thompson sampling vanishes as time progresses, unlike the greedy algorithm’s regret.Per-period regret is the difference between the optimal action’s mean reward and the selected action’s reward, averaged over 10,000 simulations.Source: §16 · pp. 16–17, Figure 3.2 · p. 17

Prior-averaged regret

  • Across 10,000 simulations with action rewards sampled independently from uniform priors, Thompson sampling shows qualitatively similar regret behavior, with differences driven by the spacing of action means.When means are close, early regret is smaller but later differentiation can take longer, as for θ = (0.9, 0.8, 0.7).Source: §16 · p. 17, Figure 3.2 · p. 17

General Thompson Sampling

Thompson sampling extends beyond Bernoulli bandits to general sequential decision problems by sampling model parameters, selecting reward-maximizing actions, and updating beliefs from observations. Its performance depends on modeling information structures, with coherent treatment of correlated observations improving shortest-path learning.

General Framework

  • In the general framework, TS samples θ from the current prior, chooses an action maximizing expected reward under that model, observes an outcome, and updates the distribution by conditioning.The action set may be finite or infinite, outcomes follow q_θ(·|x_t), and rewards are r(y_t).Source: General Thompson Sampling · pp. 19–20

Bernoulli Bandit

  • The Bernoulli bandit with independent beta-distributed arm parameters is a special case in which TS samples each arm’s parameter from its beta posterior and selects the largest sample.The posterior is represented by α and β parameters, and rewards are the observed outcomes.Source: General Thompson Sampling · pp. 20–21

Shortest Path Applications

  • For shortest paths, TS samples edge travel-time means, solves the resulting deterministic shortest-path problem efficiently, and updates beliefs using observed edge travel times.The independent model uses log-Gaussian priors and likelihoods, while correlated observations require Gaussian posterior means and covariance matrices.Source: General Thompson Sampling · pp. 22, 24

Independent Travel Times

  • In independent-travel-time shortest paths, Thompson sampling converges quickly to optimal regret and learns faster than greedy or ϵ-greedy exploration.Cumulative travel time relative to optimal converges to one for TS, while ϵ-greedy exploration progresses more slowly because it selects paths randomly rather than informatively.Source: General Thompson Sampling · p. 22, Figure 4.1 · p. 23

Correlated Travel Times

  • Accounting for interdependencies among correlated edge travel times yields substantial improvement over misspecified Thompson sampling.Coherent TS models posterior dependencies, whereas misspecified TS independently updates each edge; the comparison assumes paths are chosen before each trip.Source: General Thompson Sampling · pp. 25–26, Figure 4.3 · p. 25

Approximations

This section presents approximate posterior-sampling methods for Thompson sampling when exact Bayesian inference is computationally intractable, including incremental ensemble sampling with bootstrap-based model updates. It illustrates these methods on online shortest-path problems with binary feedback and discusses their behavior relative to exact Thompson sampling and computationally incremental variants.

Approximations

  • Approximate Thompson sampling methods learn effectively from binary feedback, with vanishing regret on the twenty-stage path problem and performance qualitatively similar to exact Thompson sampling in tractable sanity checks.Figure 5.1 reports vanishing regret for Langevin Monte Carlo, Laplace approximation, and bootstrap methods relative to greedy; Figure 5.2 shows competitive approximate-method performance against exact Thompson sampling.Source: Approximations · p. 28, Figure 5.1 · p. 29, §5.5 · p. 36

5.1 Gibbs Sampling

  • Gibbs sampling draws approximate posterior samples through coordinate-wise one-dimensional updates, but can remain computationally demanding for complex problems and large simulation workloads.Its limiting Markov-chain distribution is the target posterior under reasonable conditions, while one-dimensional sampling improves viability; nevertheless, repeated simulations over many periods can be time-consuming.Source: §5.1 · pp. 29–30

5.2 Laplace Approximation

  • The Laplace approximation replaces a posterior with a Gaussian near its mode and is efficient for smooth, sharply peaked, log-concave posteriors with tractable gradients and Hessians.A suitable variable substitution can make the approximation exact, but in the binary-feedback path problem its regret decays while remaining worse than Langevin Monte Carlo, likely because the posterior is not sufficiently Gaussian.Source: §5.2 · pp. 30–32

5.3 Langevin Monte Carlo

  • Langevin Monte Carlo approximately samples posteriors by combining gradient-driven motion with Gaussian noise, while stochastic gradients and Hessian-based preconditioning improve efficiency and mixing.The implementation uses minibatches of 100 observations and a preconditioning matrix based on the negative inverse Hessian at the posterior mode; sufficiently small or decaying step sizes support convergence guarantees.Source: §5.3 · pp. 32–33

5.4 Bootstrapping

  • The bootstrap incorporates prior and resampled-history randomness into approximate posterior samples, performs about as well as Laplace here, and is flexible but lacks general theoretical guarantees.Prior randomness drives early exploration, whereas resampled histories dominate with more data; unlike Laplace and Langevin methods, bootstrap performance does not rely on Gaussian or log-concavity assumptions.Source: §5.4 · pp. 34–35

5.5 Sanity Checks

  • In sanity checks where exact Thompson sampling is tractable, approximation methods are broadly competitive: Laplace is marginally worse in the beta-Bernoulli bandit, while bootstrap is marginally less effective for correlated edge delays.Gibbs sampling is exact for the independent beta-Bernoulli posterior, and an appropriate variable substitution makes Laplace exact for correlated log-Gaussian edge delays.Source: §5.5 · p. 36

5.6 Incremental Implementation

  • Because approximate methods repeatedly access all past observations, their per-period computation grows over time; incremental Laplace and bootstrap variants maintain fixed rather than growing computational effort.The incremental Laplace method updates posterior-mode and curvature statistics online, supports Gaussian approximate samples, and admits Sherman-Woodbury-Morrison updates for linear and generalized linear models.Source: §5.6 · pp. 37–38
  • Ensemble sampling maintains, incrementally updates, and samples from a finite set of models that approximates the posterior distribution, though actions can skew the ensemble distribution.The approach is presented in more depth in Lu and Van Roy (2017), drawing inspiration from Osband et al. (2016a).Source: §5.6 · pp. 38–39
  • A bootstrap-based ensemble maintains N models, each fitted to a different bootstrap sample, with independent Poisson-distributed samples of mean one and randomness from initialization and random weights.Source: §5.6 · p. 39
  • At each period, the algorithm samples a model uniformly from the ensemble and chooses the action maximizing expected reward under that model as an approximate posterior sample.Each ensemble model is effectively fit to a distinct history distinguished by its random observation-replica counts.Source: §5.6 · p. 39
  • Per-period computation grows with N, the ensemble-size tuning parameter, and the bootstrap method is one incremental-update mechanism alongside another used for active learning with neural networks.The alternative mechanism is discussed in Section 7.4.Source: §5.6 · p. 39

Practical Modeling Considerations

The section extends Thompson sampling beyond idealized stationary settings by addressing prior specification, changing constraints and context, nonstationarity, and concurrent actions. These extensions show how modeling choices affect learning and performance in practical applications.

6.1 Prior Distribution Specification

  • A prior represents plausible parameter values and directs Thompson sampling to perform well on average, so incorporating relevant knowledge can reduce learning time.In banner advertising, empirical priors can be built from stylistically similar past ads, such as a smoothed beta(1, 100) approximation.Source: §6.1 · pp. 41–42
  • Figure 6.2 shows that a misspecified prior increases regret and delays learning relative to coherent priors in a three-armed Bernoulli bandit.The simulations average 10,000 independent runs with action means drawn from beta(1, 50), beta(1, 100), and beta(1, 200).Source: §6.1 · pp. 42–43, Figure 6.2 · p. 43

6.2 Constraints, Context, and Caution

  • Time-varying action constraints preserve Thompson sampling by restricting its maximization, while contextual decisions can be handled by augmenting actions with observed context and imposing corresponding constraint sets.Constraints can also enforce an expected-reward baseline by excluding actions whose expected reward falls below r.Source: §6.2 · p. 44, §6.3 · p. 45

6.3 Nonstationary Systems

  • For nonstationary systems, Thompson sampling must continue exploring; simple approaches use a sliding observation window or discount past observations through an uncertainty-injection parameter γ.In the Bernoulli case, γ = 0 injects no uncertainty, while γ = 1 makes each parameter independently beta-distributed over time.Source: §6.3 · pp. 45–46
  • Figure 6.3 shows that nonstationary TS retains reasonable performance as the system drifts, whereas stationary TS becomes less effective; no algorithm can guarantee vanishing regret.The simulation averages 10,000 independent runs with decay rate γ = 0.01.Source: Figure 6.3 · p. 47, §6.4 · p. 47

6.4 Concurrence

  • Concurrent Thompson sampling draws independent posterior samples for multiple agents, with synchronous, asynchronous, and adaptive variants requiring different posterior-update designs.Concurrent actions should diversify experience, while adapting actions to other agents’ recent observations requires careful design.Source: §6.4 · pp. 48–49
  • Figure 6.4 shows that concurrent TS reduces per-action regret faster as the number of agents grows, but regret decays more slowly with the collective action count.Shared observations accelerate learning, while posterior updates delayed until concurrent actions finish prevent actions from using observations generated by other agents.Source: Figure 6.4 · p. 48, §6.4 · p. 48

Further Examples

This section broadens Thompson sampling’s scope across contextual recommendation, product assortment, cascading recommendation, neural-network active learning, and reinforcement learning. It illustrates how posterior or policy sampling is adapted to complex application-specific models while balancing immediate rewards with information acquisition and delayed consequences.

7.1 News Article Recommendation

  • The news-recommendation model uses user features and article-specific parameters in a logistic model, enabling generalization across users while defining regret against the best feature-dependent article.Features can encode recent activities, demographics, and contextual information such as location and day of week.Source: §7.1 · p. 52
  • For news recommendation, exact Bayesian inference is inefficient, so the tutorial applies Laplace and Langevin Monte Carlo posterior approximations alongside an optimized ϵ-greedy baseline.The model learns separate θ_x parameters for articles, while alternative feature vectors z_t,x enable transfer learning across related articles; changing article inventories remain contextual-bandit cases.Source: §7.1 · pp. 52–54
  • In news recommendation, Thompson sampling substantially outperforms optimized ϵ-greedy, whose lowest regret occurs at ϵ = 0.01, in simulations averaged over 2,000 random problem instances.The setting has K = 3 articles and feature dimension d = 7, with article parameters sampled independently from N(0, I).Source: §7.1 · pp. 52–53, Figure 7.1 · p. 53

7.2 Product Assortment

  • In product assortment, Thompson sampling draws a parameter matrix from its Gaussian posterior and selects the assortment maximizing expected profit under that sample, with posterior updates available in closed form.Demand is log-Gaussian and depends on the full assortment through a matrix whose diagonal captures individual product demand and off-diagonal terms capture interactions.Source: §7.2 · pp. 54–56
  • In product assortment, Thompson sampling outperforms greedy and both fixed- and annealed-ϵ-greedy variants, with the latter’s best simulated parameter set by m = 9.The simulation uses n = 6, σ2 = 0.04, p_i = 1/6, and ϵ = 0.07 for fixed ϵ-greedy; Figure 7.2 reports the performance comparison.Source: §7.2 · p. 56, §7.3 · p. 57, Figure 7.2 · p. 57

7.3 Cascading Recommendations

  • Cascading bandits model ordered recommendation lists in which users sequentially inspect items, click the first attractive item, and yield feedback that updates itemwise attraction beliefs.The optimal list contains the J items with largest attraction probabilities; CascadeTS samples independent Beta attraction probabilities, whereas CascadeUCB uses itemwise upper confidence bounds.Source: §7.3 · pp. 57–59
  • In cascading recommendations, CascadeTS far outperforms CascadeUCB in the K = 1000, J = 100 setting because independent posterior samples reflect uncertainty more accurately than overly optimistic rectangular confidence bounds.The comparison uses 1000 randomly sampled instances over 20000 periods; CascadeUCB’s optimism arises because it simultaneously assigns every recommended item its largest plausible attraction probability.Source: §7.3 · pp. 59–60
  • Tuned CascadeUCB can outperform CascadeTS in the lower-dimensional K = 50, J = 10 setting, suggesting that confidence-set geometry and problem dimension affect the comparison.The result uses c = 0.1 and advantages CascadeUCB through tuning for the specific setting and horizon; the text attributes the qualitative difference partly to hyper-rectangular sets approximating ellipsoids more poorly at higher dimension.Source: §7.3 · p. 60, §7.4 · p. 61, Figure 7.4 · p. 61

7.4. Active Learning with Neural Networks

  • In neural-network active learning, actions trade off immediate rewards against data collection that reduces uncertainty in network weights, using an ensemble of sampled models.Each model is initialized from the prior and incrementally updated with stochastic gradient descent.Source: §7.4 · p. 63
  • Ensemble sampling outperforms the best tuned ε-schedules, and an ensemble with as few as 30 members provides very good performance.Fewer ensemble members produce greedier behavior that may help over shorter horizons but risks premature, suboptimal convergence relative to true TS.Source: §7.4 · pp. 64–65

7.5 Reinforcement Learning in Markov Decision Processes

  • Reinforcement learning requires deep exploration because actions affect future states and rewards, so TS must account for delayed consequences rather than optimize each period myopically.A naive policy resampling scheme within an episode fails to maintain the consistent behavior needed for informative future actions.Source: §7.5 · pp. 65–66
  • TS for episodic MDPs samples rewards and transition dynamics, solves the resulting optimal policy, and can use Dirichlet posteriors for finite-state transitions.This approach samples the optimal policy indirectly and updates transition beliefs by incrementing Dirichlet pseudo-observations.Source: §7.5 · pp. 66–67
  • Sampling once per episode learns the optimal policy within one episode, whereas timestep-wise resampling is exponentially unlikely to reach either rewarding end of the chain.In the comparison, timestep-wise sampling requires at least 2^N episodes for the first expected reward, while episode-wise sampling learns the true MDP structure in one episode.Source: §7.5 · pp. 67–68, Figure 7.7 · p. 68
  • With less favorable priors, episode-wise sampling still outperforms timestep-wise sampling, with advantages that grow with problem size and reduce computation by solving for a policy once per episode.Figure 7.7 shows that the benefit can become arbitrarily large as the MDP grows.Source: §7.5 · p. 68, Figure 7.7 · p. 68

Why it Works, When it Fails, and Alternative · Approaches · 8.1 Why Thompson Sampling Works

The section explains why Thompson sampling (TS) explores efficiently, reviews regret analyses establishing when it is asymptotically or nearly order-optimal, and identifies important limitations for broader problem classes. It also motivates alternative analyses for complex online decisions where structure and prior knowledge can help or hurt performance.

Approaches

  • The tutorial adapts TS across practically important problem classes, then examines why it works, where it is poorly suited, and which alternatives may apply.The broader analysis connects TS’s exploration intuition with theoretical results and failure cases.Source: Approaches · p. 71

8.1 Why Thompson Sampling Works

  • TS samples actions according to their posterior probability of being optimal, exploring plausible candidates while progressively discarding actions believed to underperform.This mechanism tracks changing beliefs about action rewards and prioritizes promising actions without permanently excluding uncertain ones.Source: §8.1 · p. 71

8.1.1 Regret Analysis for Classical Bandit Problems

  • In classical Bernoulli bandits with a unique optimal action, TS matches the asymptotic regret scaling established as unimprovable by Lai and Robbins (1985).The result was first observed empirically by Chapelle and Li (2011) and later proved by Agrawal and Goyal (2012), Agrawal and Goyal (2013a), and Kauffmann et al. (2012).Source: §8.1.1 · p. 72
  • These asymptotic optimality results extend to Gaussian rewards, canonical one-dimensional exponential families, and Gaussian rewards with unknown variance.Honda and Takemura (2014) established these extensions, while the broader prior-distribution question remains open.Source: §8.1.1 · pp. 72–73
  • Asymptotic O(log(T)) bounds can hide substantial finite-horizon differences and become vacuous when many actions are nearly optimal, especially in complex structured problems.The asymptotic regime mainly concerns occasional exploration after the best action is nearly identified; near-optimal actions dominate the relevant regret expression.Source: §8.1.1 · p. 73
  • For Bernoulli bandits with a uniform prior, TS has a regret bound holding uniformly over all instances and is nearly order-optimal.Agrawal and Goyal (2013a) provide the bound, while Bubeck and Cesa-Bianchi (2012) establish a matching lower-bound order over a distribution of instances.Source: §8.1.1 · pp. 73–74

8.1.2 Regret Analysis for Complex Online Decision Problems

  • For complex online decision problems, classical bandit regret results do not by themselves justify TS; broader analyses instead examine its exploitation of structure and prior knowledge and its poor-performance settings.The tutorial emphasizes that modeling prior knowledge and problem structure can accelerate learning, but the resulting guarantees depend on the application.Source: §8.1.2 · p. 74

Problem Formulation · Regret Bounds via UCB

The section formulates Bayesian online decision-making through expected regret and shows how UCB-style confidence analyses yield regret guarantees for Thompson sampling. These guarantees extend across structured reward classes and depend on model complexity, including eluder dimension.

Problem Formulation

  • The Bayesian formulation models outcomes as y_t = g(x_t, θ, w_t), with uncertainty about θ inducing uncertainty about the optimal action and integrated expected regret.Bayesian regret averages over the prior, disturbances, and algorithmic randomization, prioritizing performance in more likely parameter scenarios.Source: Problem Formulation · pp. 74–75

Regret Bounds via UCB

  • A UCB algorithm selects the action maximizing a history-dependent optimistic estimate of expected reward, with uncertainty bonuses shrinking as actions are repeatedly observed.A representative heuristic uses a posterior mean plus a 2 ln(t)/t_x bonus and forces each action to be selected once.Source: Regret Bounds via UCB · p. 76
  • Thompson sampling inherits many UCB expected-regret bounds because its posterior sampling identity makes the pessimism term nonpositive while the width term admits standard UCB analysis.This relationship is established in Russo and Van Roy (2014b).Source: Regret Bounds via UCB · pp. 76–77
  • For linear rewards with sub-Gaussian noise, translated UCB analyses provide Thompson-sampling guarantees that depend on parameter dimension d rather than the number of actions.The bound applies for any prior over a compact parameter set, assuming bounded action magnitudes, parameter realizations, and noise variance proxy.Source: Regret Bounds via UCB · p. 77
  • Across broad online decision problems, Thompson sampling and well-designed UCB algorithms satisfy a unified regret bound governed by reward-function complexity.The relevant complexity measures are covering numbers and eluder dimension.Source: Regret Bounds via UCB · p. 78
  • Eluder dimension captures how effectively unobserved action values can be inferred from observed samples, while covering numbers capture reward-class sensitivity to statistical overfitting.Both measures characterize the approximate structure of the reward-function class at a horizon-dependent scale.Source: Regret Bounds via UCB · p. 78
  • Standard supervised-learning complexity notions, including covering numbers and Kolmogorov and Vapnik–Chervonenkis dimensions, are insufficient alone for online regret bounds.The eluder dimension introduced in Russo and Van Roy (2014b; 2013) is essential to the unified guarantee.Source: Regret Bounds via UCB · p. 79

Regret Bounds via Information Theory

Information-theoretic regret bounds use an information ratio measuring expected regret per bit of information gained about the optimal action. The resulting bounds expose how prior uncertainty and feedback structure affect Thompson sampling’s performance, while also identifying limitations for large or infinite action spaces.

Information ratio

  • The information ratio divides squared expected single-period regret by the conditional mutual information gained about the uncertain optimal action.It can be interpreted as the expected cost per bit of information acquired, with small ratios linking large regret to substantial expected learning.Source: Regret Bounds via Information Theory · p. 79

General regret bound

  • The general regret bound depends on Γ and the prior entropy H(x∗), thereby capturing benefits of prior information absent from earlier bounds.The proof uses the fact that cumulative information gain cannot exceed H(x∗), formalized through the chain rule of mutual information.Source: Regret Bounds via Information Theory · p. 80

Shortest-path applications

  • For shortest-path problems, the bound scales with the number of edges d rather than the potentially exponential number of paths and improves with lower prior entropy H(x∗).Informative priors about edge lengths reduce uncertainty over which path is shortest and therefore improve the bound.Source: Regret Bounds via Information Theory · pp. 80–81

Feedback structure

  • Richer feedback reduces information ratios from d/2 to 1/2 or d/2m, with corresponding regret bound dH(x∗)T/2m when m is the maximum path length.These values reflect how each feedback structure changes Thompson sampling’s regret per acquired bit of information.Source: Regret Bounds via Information Theory · p. 81

Limitations and extensions

  • The entropy-based bound can become vacuous for many actions, motivating rate-distortion analyses that remain an open direction for standard Thompson sampling.Rate-distortion functions would measure the information needed for near-optimal performance, and related work studies satisficing-action variants.Source: Regret Bounds via Information Theory · pp. 81–82

Further Regret Analyses

Further analyses examine the limits and extensions of Thompson sampling regret guarantees, while a motivating example shows that stationary randomization is necessary for sublinear regret. Deterministic stationary strategies can instead achieve such bounds only by becoming nonstationary.

Further Regret Analyses

  • For linear bandits, (Agrawal and Goyal, 2013b) analyze a variance-inflated posterior-sampling variant, whose worst-case regret bound has an additional d^1/2 factor relative to (8.5).The bound does not apply to standard Thompson sampling with proper posterior updating, leaving its corresponding worst-case guarantee open; improved proof techniques were later provided by (Abeille and Lazaric, 2017).Source: Further Regret Analyses · p. 82
  • Related work analyzes Thompson-sampling variants for assortment optimization, asymptotic behavior in finite-parameter problems, and reinforcement-learning extensions. study modified-posterior sampling for assortment optimization; provide an asymptotic analysis; and (Gopalan and Mannor, 2015) study reinforcement-learning extensions.Source: Further Regret Analyses · p. 82

8.1.3 Why Randomize Actions

  • Stationary randomization is necessary for sublinear expected cumulative regret, whereas any stationary deterministic strategy can incur linear regret for some prior.A deterministic stationary strategy either repeatedly selects the uninformative action or repeatedly selects the uncertain action, yielding linear expected cumulative regret; deterministic nonstationary strategies such as UCB can avoid this.Source: §8.1.3 · pp. 82–83

8.2 Limitations of Thompson Sampling

Thompson sampling leaves value on the table in four settings: exploration may be unnecessary, exploitation may be unnecessary, time horizons may favor satisficing, or actions may provide information disproportionate to their rewards.

8.2.1 Problems that do not Require Exploration

  • When exploration is unnecessary, TS is usually outperformed by greedier methods, although contextual randomness can provide passive exploration and binary contexts or offset parameters can make active exploration essential.Historical returns can eliminate costly experimentation in portfolio selection, whereas binary contexts may cause greedy policies to stop learning an optimal action.Source: §8.2.1 · pp. 83–85

8.2.3 Time Sensitivity

  • t = 1/ϵ periods suffice to identify an ϵ-optimal action independently of K by ordered sampling, whereas TS keeps sampling new actions when t ≪K.This time-sensitivity problem motivates satisficing TS (Russo and Van Roy, 2018b), and reduced exploration may also help in nonstationary systems.Source: §8.2.3 · pp. 86–87

8.2.4 Problems Requiring Careful Assessment of Information Gain

  • TS can ignore actions that are suboptimal themselves but reveal other actions’ values, requiring d/2 periods instead of log(d) in the sparse linear model and n instead of ⌈n/m⌉ periods in assortment learning.Information-directed sampling addresses these failures (Russo and Van Roy, 2018a), though its more complex computations may limit practical use.Source: §8.2.4 · pp. 87–90

8.3 Alternative Approaches

Alternative approaches include Gittins-index policies, which are optimal for finite independent-action bandits but computationally onerous, and UCB algorithms, which provide efficient exploration across broader problem classes but may sacrifice statistical efficiency relative to TS.

Gittins indices

  • Gittins indices characterize an optimal discounted-reward strategy for finite independent-action bandits, but implementing it requires a computationally onerous dynamic program and generally fails for more complicated problems.The tutorial cites Gittins and Jones (1979), Katehakis and Veinott (1987), and Gittins et al. (2011).Source: §8.3 · p. 90

Upper-confidence bounds

  • UCB algorithms explore efficiently by sampling promising actions while gradually discarding underperforming ones, paralleling TS at a high level.Their formal relation to TS was established in (Russo and Van Roy, 2014b).Source: §8.3 · p. 90
  • UCB algorithms have been developed for independent-action, linear, continuous-action, and reinforcement-learning bandits.The cited applications include,,, and.Source: §8.3 · p. 90
  • Designing UCBs that achieve both statistical and computational efficiency is challenging, so some implementations sacrifice statistical efficiency relative to TS.This tradeoff is discussed in (Russo and Van Roy, 2014b; Osband and Van Roy, 2017a; Osband and Van Roy, 2017b).Source: §8.3 · p. 90

8.3. Alternative Approaches

Alternative approaches seek to balance immediate reward against information acquisition more explicitly, while other methods address the time-sensitivity of information or adversarial environments.

Alternative Approaches

  • Information-directed sampling minimizes the information ratio to manage the trade-off between immediate reward and information acquired through action sampling.Knowledge gradient and related heuristics likewise assess the value of information and address time-sensitivity (Frazier et al., 2008; Frazier et al., 2009; Francetich and Kreps, 2017a; Francetich and Kreps, 2017b).Source: §8.3 · p. 91
  • A substantial literature studies online decision problems in adversarial environments, but it is outside this tutorial’s review scope; see (Bubeck and Cesa-Bianchi, 2012).Source: §8.3 · p. 91

Related papers

Loading 1707.02038v3…