Thompson Sampling¶

A Bayesian bandit policy that samples a plausible reward model from the current posterior and chooses the action optimal under that sample, thereby probability-matching exploration to uncertainty.

Version: v1 · 2026-09-28 · History
Domain-specific #: 12535
Domain group: Formal Sciences
Origin domain: Experimental Design & Statistics
Subdomains: Bayesian Sequential Design, Multi Armed Bandits → Experimental Design & Statistics

Core Idea¶

Thompson sampling is a Bayesian sequential decision policy for bandits and related online-learning problems. It represents uncertainty about reward-model parameters with a posterior distribution, samples one plausible parameter setting, and chooses the action with highest expected reward under that sample.

Equivalently, each action is selected with the posterior probability that it is optimal. Poorly known actions are explored when sampled beliefs make them look best; actions with strong evidence of high reward are exploited more often. New context–action–reward observations update the posterior before later decisions.

The policy’s simplicity hides important modeling choices: likelihood and prior, contextual features, nonstationarity, delayed outcomes, and the accuracy of approximate posterior sampling. Its randomization is epistemic rather than arbitrary—the distribution of actions is coupled to uncertainty about optimality.

Structural Signature¶

Sig role-phrases:

Reward model and prior. Represents uncertain expected outcomes of actions, optionally conditioned on context. Constitutive Bayesian belief model. If altered: Without a prior and likelihood the policy is no longer Thompson sampling in its standard form.
Observed action–reward history. Updates the parameter posterior using evidence gathered through interaction. Constitutive learning state. If altered: Ignoring new outcomes prevents uncertainty from contracting and policy behavior from adapting.
Posterior sample. Draws one plausible parameter realization at each decision round. Identity-bearing randomization. If altered: Using only the posterior mean becomes a greedy Bayesian policy rather than probability matching.
Sample-optimal action. Maximizes expected reward under the sampled model and current context. Identity-bearing decision rule. If altered: Sampling an action without solving the sampled decision problem breaks the posterior optimality relation.

What It Is Not¶

Not uniform exploration. Actions are randomized according to posterior plausibility, not equal chance.
Not posterior-mean greediness. The policy samples a model rather than optimizing only average expected rewards.
Not generic probability matching. Class base-rate prediction lacks the sequential reward posterior and optimal-action event.
Not UCB. UCB adds deterministic optimism bonuses instead of drawing posterior models.

Scope of Application¶

The policy applies to repeated decisions with observable feedback and a probabilistic model linking contexts and actions to rewards.

Multi-armed bandits. Uncertain arm reward rates are learned while rewards accumulate.
Contextual recommendation. Posterior models condition expected reward on user or situation features.
Online experiments. Traffic allocation shifts toward better variants while retaining uncertainty-driven exploration.
Advertising. Creative or bid choices learn from sequential response.
Approximate Bayesian control. Sampling methods make complex posterior models usable online.

Clarity¶

Specify the reward, horizon, action set, context, likelihood, prior, posterior-update rule, and sampling approximation. Distinguish Bayesian regret claims from frequentist guarantees and check whether feedback is delayed, censored, nonstationary, or action-dependent. Report randomized allocation when evaluating outcomes.

Manages Complexity¶

One posterior sample converts a difficult integration over all possible models into an ordinary optimization under one plausible world. Repetition automatically directs effort toward actions that are both promising and uncertain, coupling inference and control without a separate exploration schedule.

Abstract Reasoning¶

Define a reward model and prior that reflect the action and context structure.
Update the posterior from observed context–action–reward tuples without treating chosen actions as exogenous evidence about the environment.
Draw a parameter or model realization from the current posterior.
Choose the action maximizing expected reward under that realization.
Monitor calibration, regret, nonstationarity, and approximation error as data accumulate.

Knowledge Transfer¶

The posterior-sampling policy transfers from Bernoulli bandits to contextual, combinatorial, and some control settings when a coherent model and sample-optimal action can be computed. Randomized choice without posterior optimality is only analogy.

Examples¶

Canonical¶

For two Bernoulli website variants with Beta posteriors, the system samples one conversion rate for each and displays the variant with the larger sampled rate.

Mapped back: reward model and prior → Beta–Bernoulli rates; observed action–reward history → impressions and conversions; posterior sample → one rate per variant; sample-optimal action → show the larger draw.

Applied / In Practice¶

A contextual recommender samples its posterior model coefficients for the current user and selects the item with greatest sampled expected engagement.

Mapped back: reward model and prior → contextual reward model; observed action–reward history → past user-item outcomes; posterior sample → sampled coefficient vector; sample-optimal action → highest predicted item.

Structural Tensions¶

T1: exploration vs. exploitation. Uncertain actions receive trials in proportion to their posterior chance of being best. Diagnostic: Does the posterior represent uncertainty well enough to allocate exploration?

T2: model fidelity vs. online tractability. Rich reward models improve representation but make posterior sampling costly. Diagnostic: What approximation error changes action probabilities?

T3: adaptive reward vs. causal evaluation. The policy’s own choices determine which outcomes are observed. Diagnostic: How are selection and delayed feedback handled in evaluation?

Structural–Framed Character¶

Thompson sampling is strongly structural and decision-framed. Evaluative weight: cumulative reward and regret define performance. Human-practice-bound: model, prior, reward, and constraints are chosen. Institutional origin: Bayesian statistics and online learning stabilize it. Vocabulary travels: posterior sampling and optimization travel. Import versus recognize: literal use requires sample-optimal Bayesian action. Its character: uncertainty-calibrated randomization through sampled optimal worlds.

Structural Core vs. Domain Accent¶

Skeletal core. Sample one plausible state of the uncertain environment and act optimally as if that state were true.

Domain-bound accent. Beliefs are Bayesian reward-model posteriors, actions form a bandit decision, and feedback updates future allocation.

Why not prime. Sampling under uncertainty is portable, but the named policy is a specific sequential Bayesian decision rule.

This entry is a kind of Algorithm.

Sampling. A posterior draw realizes one plausible reward model.
Updating. Feedback revises the belief state.
Optimization. Each sampled model induces a best action.
The approved root remains.

Relationships to Other Abstractions¶

Current abstraction Thompson Sampling Domain-specific

Parents (1) — more general patterns this builds on

Thompson Sampling is a kind of Algorithm Prime

Thompson Sampling is a domain-specific kind of algorithm under its frozen identity and differentia.

Hierarchy paths (2) — routes to 2 parentless roots

Thompson Sampling → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Thompson Sampling sits in a moderately populated region (55^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Strategic Decision Biases & Mechanisms (29 abstractions)

Nearest neighbors

MAP estimator — 0.87
Bayesian Persuasion — 0.86
Bayesian Programming — 0.86
Particle Filter — 0.86
M-Estimator — 0.84

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Upper confidence bound. Tell: UCB chooses optimistic bounds rather than a sampled posterior model.
Epsilon-greedy. Tell: Its exploration probability is externally scheduled rather than posterior-matched.
Probability matching in classification. Tell: Matching class base rates lacks sequential reward learning.
Bayesian model averaging. Tell: Averaging predictions differs from sampling one model and optimizing it.

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Thompson_sampling (revision 1362198073).
Preserved source candidate: https://www.dropbox.com/s/yhn9prnr5bz0156/1933-thompson.pdf
Preserved source candidate: http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
Preserved source candidate: http://arxiv.org/abs/0810.3605
Preserved source candidate: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701
Preserved source candidate: http://blog.locut.us/2011/09/22/proportionate-ab-testing/
Preserved source candidate: https://web.archive.org/web/20130504042611/http://blog.locut.us/2011/09/22/proportionate-ab-testing/
Preserved source candidate: https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
Preserved source candidate: https://proceedings.neurips.cc/paper/2013/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.