Thompson sampling is a randomized algorithm for sequential decision-making under uncertainty. At each step, it samples a possible model of the environment from its current posterior distribution, chooses an action that is optimal under that sampled model, observes the outcome, and updates its beliefs. It is best known as a solution to the multi-armed bandit problem, where a decision-maker repeatedly chooses among alternatives with initially unknown rewards. Its central purpose is to balance learning about uncertain alternatives with using alternatives that already appear valuable.
Decision problem
In the standard stochastic bandit setting, there are available actions, traditionally called arms. Choosing action produces a reward drawn from an unknown, fixed probability distribution with mean . Only the reward of the chosen action is observed; the rewards that other actions would have produced remain unknown.
The decision-maker seeks to accumulate reward over a sequence of rounds. This creates the exploration–exploitation trade-off:
- Exploration selects actions partly to learn about their rewards.
- Exploitation selects actions that currently appear to offer high rewards.
Always choosing the action with the highest estimated mean can prematurely abandon a good alternative after unlucky observations. Exploring indefinitely at a fixed rate, however, can waste many decisions on clearly inferior alternatives.
Thompson sampling addresses this tension through uncertainty in the reward model. An uncertain action can be selected when a posterior sample makes it appear best, while an action that is consistently supported by observations tends to win more frequently.
Bayesian formulation
Thompson sampling uses Bayesian inference to represent uncertainty about the environment. Let denote the unknown model parameters and let contain the actions and observations available before round . The posterior distribution is
Let denote the expected reward of action under parameters . A round of Thompson sampling proceeds as follows:
Draw a parameter sample:
Choose an action that maximizes expected reward in the sampled model:
Observe reward .
Update the posterior using the likelihood of the observation.
The update takes the form
The sampled quantity is a model parameter, or an expected reward implied by that parameter—not normally a simulated realization of the next reward. Sampling a noisy reward and choosing the largest such realization is a different procedure.
For independent arm models, implementations often sample one parameter for each arm. If actions share parameters or have correlated uncertainties, sampling must preserve that joint structure.
Probability matching
If the optimal action is unique with posterior probability one, exact Thompson sampling satisfies
Thus, each action is chosen with the posterior probability that it is optimal. This property explains the alternative name probability matching. If ties have positive probability, the equality requires a consistent tie-breaking rule.
An action’s probability of being optimal is not the same as its posterior mean reward. An uncertain action may have a lower mean estimate but still have a substantial chance of being the best.
Beta–Bernoulli example
A common example involves binary rewards, such as a click or no click. For action , suppose
where is its unknown success probability.
Assign each an independent beta distribution:
After observing successes and failures for that action, its posterior is
The beta distribution is a conjugate prior for the Bernoulli likelihood, so the posterior update requires only two parameters per action.
The resulting procedure is:
Initialize alpha[a] > 0 and beta[a] > 0 for every action a
For each round:
For every action a:
Sample q[a] from Beta(alpha[a], beta[a])
Choose an action with the largest q[a]
Observe binary reward r
alpha[chosen] += r
beta[chosen] += 1 - r
A prior is uniform over success probabilities from zero to one. Other parameter choices express different prior beliefs and strengths of evidence.
For example, an extensively observed action with a success rate near may have a narrow posterior, while a little-tested action has a much wider posterior. The uncertain action sometimes produces a higher sampled success probability and is selected. Further observations then determine whether its apparent promise is supported.
With independent arms, this basic implementation uses work per decision and storage, assuming constant-cost beta sampling.
Exploration and performance
Thompson sampling explores through posterior uncertainty rather than through a separate instruction to take random actions. As evidence accumulates against an action, the posterior probability that it is optimal typically decreases, reducing its selection frequency.
This is not equivalent to explicitly calculating the value of information. Thompson sampling does not generally solve the full Bayesian planning problem of selecting actions to maximize expected reward over all future rounds. Instead, it acts optimally in one sampled model. It can perform well without being Bayes-optimal for a particular finite horizon.
Regret
Performance is often measured using regret. In a stationary bandit, let
The expected cumulative pseudo-regret after rounds is
Equivalently, with and denoting the number of times action is selected,
Two common perspectives are:
- Frequentist regret, which fixes the true environment and averages over reward noise and algorithmic randomization.
- Bayesian regret, which additionally averages over an assumed prior on environments.
For standard finite-armed Bernoulli bandits with independent beta priors, Thompson sampling has logarithmic-in-, problem-dependent regret guarantees. Suitable versions attain asymptotically optimal leading behavior under established assumptions. The constants depend on how difficult it is to distinguish inferior actions from the best action.
These results do not provide a universal guarantee for every application called Thompson sampling. The reward model, prior, action space, and accuracy of posterior sampling matter.
Extensions
Contextual bandits
In a contextual bandit, the decision-maker observes information before choosing an action. Expected rewards depend on both the action and the context:
Thompson sampling draws and chooses
Examples include linear reward models, logistic models for binary outcomes, and models using neural networks. Shared parameters allow an observation about one action or context to inform predictions elsewhere.
The tractability of inference varies substantially. Linear models with suitable Gaussian assumptions permit efficient exact updates; more complex models often require approximate inference.
Structured and combinatorial actions
An action may be an assortment of products, a route through a network, or another structured object rather than one item from a short list. Thompson sampling then draws uncertain parameters and solves a corresponding optimization problem.
This separates statistical inference from action selection: a solver for a known-parameter problem can sometimes be reused with posterior samples. The optimization step may nevertheless be computationally difficult.
Reinforcement learning
In reinforcement learning, actions can change future states as well as immediate rewards. Posterior sampling can be extended by drawing an environment model, computing a policy for it, and following that policy for an episode or another specified interval.
This is often called posterior sampling for reinforcement learning. Keeping a sampled model fixed across multiple decisions can produce temporally coherent exploration. Independently resampling at every step can lead to different exploratory behavior.
Relationship to other methods
Thompson sampling differs from several common alternatives:
- Greedy selection chooses the action with the highest current estimated reward and may perform no deliberate exploration.
- Epsilon-greedy selection usually acts greedily but chooses a random action with a specified probability.
- Upper-confidence-bound methods choose actions using optimistic estimates constructed from reward estimates and uncertainty bounds.
- Bayes-optimal planning explicitly accounts for how present actions affect future knowledge and rewards.
Both Thompson sampling and upper-confidence-bound methods use uncertainty to guide exploration. Their mechanisms differ: Thompson sampling randomizes through posterior draws, while confidence-bound methods typically optimize an optimistic index.
Applications
Thompson sampling is used in online experimentation, advertising allocation, recommendation systems, and other settings where decisions and feedback arrive sequentially. It is especially natural when alternatives can be tested repeatedly and the objective is cumulative reward during learning.
In contrast to a conventional randomized controlled experiment with fixed allocation probabilities, Thompson sampling adapts allocation in response to outcomes. Reward optimization and statistical inference are distinct goals: adaptive allocation does not automatically support conventional fixed-design estimators, significance tests, or stopping rules without appropriate analysis.
Applications may also involve delayed feedback, changing action sets, resource limits, or multiple objectives. Such features generally require modifications to the basic algorithm.
Limitations and practical considerations
Model and prior dependence. Posterior probabilities are conditional on the assumed model. A misspecified likelihood or an excessively concentrated, misleading prior can distort exploration. If the prior excludes the true environment, observations cannot simply recover it through ordinary posterior updating.
Approximate inference. Exact posterior sampling is often unavailable. Methods such as Markov chain Monte Carlo, variational inference, and ensemble approximations can be used, but their uncertainty estimates affect exploration. An approximation that understates uncertainty may explore too little.
Nonstationarity. The basic formulation assumes fixed reward distributions. Under distribution shift, accumulating all past observations can make the model slow to respond. Discounting, sliding windows, or explicit models of temporal change alter this behavior, but also change the assumptions behind performance guarantees.
Delayed and batched observations. Several actions may be selected before any new outcomes arrive. Decisions then rely on less current information, and sequential-update guarantees may not transfer unchanged.
Safety and constraints. Randomized exploration can select inferior or unacceptable actions. Standard Thompson sampling does not itself impose safety requirements, fairness criteria, budget constraints, or limits on exposure to poor outcomes. These must be represented separately in the decision problem.
Reward specification. The method optimizes the supplied reward signal. High performance on that signal does not establish that it captures every relevant objective or long-term consequence.
History
William R. Thompson introduced the underlying idea in 1933 in work on choosing between two treatments when their success probabilities were uncertain. His proposal allocated choices according to the probability, given the available evidence, that one alternative was better than the other.
The method later became a central approach to bandit learning. Research in the early 2010s established strong empirical results and increasingly precise regret guarantees, helping extend its use to contextual decisions, structured action spaces, and reinforcement learning.