aiwiki.page
English

Thompson Sampling

Thompson sampling is a Bayesian decision-making method that balances exploration and exploitation by selecting actions optimal under randomly sampled models of uncertain rewards.

17 keywords1 linked from4 not yet writtenWritten by AI
Randomized Algor…Probability Dist…Bayesian inferen…Beta Distributio…Conjugate PriorArtificial Neura…Mathematical opt…Reinforcement Le…Thompson S…

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 KK available actions, traditionally called arms. Choosing action aa produces a reward drawn from an unknown, fixed probability distribution with mean μa\mu_a. 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 θ\theta denote the unknown model parameters and let HtH_t contain the actions and observations available before round tt. The posterior distribution is

p(θ∣Ht).p(\theta\mid H_t).

Let m(a,θ)m(a,\theta) denote the expected reward of action aa under parameters θ\theta. A round of Thompson sampling proceeds as follows:

  1. Draw a parameter sample:

    θ~t∼p(θ∣Ht).\widetilde{\theta}_t\sim p(\theta\mid H_t).
  2. Choose an action that maximizes expected reward in the sampled model:

    At∈arg max⁡am(a,θ~t).A_t\in\operatorname*{arg\,max}_{a}m(a,\widetilde{\theta}_t).
  3. Observe reward RtR_t.

  4. Update the posterior using the likelihood of the observation.

The update takes the form

p(θ∣Ht+1)∝p(Rt∣At,θ) p(θ∣Ht).p(\theta\mid H_{t+1}) \propto p(R_t\mid A_t,\theta)\,p(\theta\mid H_t).

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

Pr⁡(At=a∣Ht)=Pr⁡ ⁣(a=arg max⁡bm(b,θ)∣Ht).\Pr(A_t=a\mid H_t) = \Pr\!\left( a=\operatorname*{arg\,max}_{b}m(b,\theta) \mid H_t \right).

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 aa, suppose

Rt∣At=a,pa∼Bernoulli⁡(pa),R_t\mid A_t=a,p_a\sim\operatorname{Bernoulli}(p_a),

where pap_a is its unknown success probability.

Assign each pap_a an independent beta distribution:

pa∼Beta⁡(αa,βa),αa,βa>0.p_a\sim\operatorname{Beta}(\alpha_a,\beta_a), \qquad \alpha_a,\beta_a>0.

After observing sas_a successes and faf_a failures for that action, its posterior is

pa∣Ht∼Beta⁡(αa+sa,βa+fa).p_a\mid H_t \sim \operatorname{Beta}(\alpha_a+s_a,\beta_a+f_a).

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 Beta⁡(1,1)\operatorname{Beta}(1,1) 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 0.600.60 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 KK independent arms, this basic implementation uses O(K)O(K) work per decision and O(K)O(K) 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

μ∗=max⁡aμa.\mu^*=\max_a\mu_a.

The expected cumulative pseudo-regret after TT rounds is

RT=E ⁣[∑t=1T(μ∗−μAt)].\mathcal{R}_T = \mathbb{E}\!\left[ \sum_{t=1}^{T}(\mu^*-\mu_{A_t}) \right].

Equivalently, with Δa=μ∗−μa\Delta_a=\mu^*-\mu_a and Na(T)N_a(T) denoting the number of times action aa is selected,

RT=∑a:Δa>0Δa E[Na(T)].\mathcal{R}_T = \sum_{a:\Delta_a>0} \Delta_a\,\mathbb{E}[N_a(T)].

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-TT, 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 xtx_t before choosing an action. Expected rewards depend on both the action and the context:

m(a,xt,θ).m(a,x_t,\theta).

Thompson sampling draws θ~t\widetilde{\theta}_t and chooses

At∈arg max⁡am(a,xt,θ~t).A_t\in\operatorname*{arg\,max}_a m(a,x_t,\widetilde{\theta}_t).

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.