Thompson sampling

Also known as: posterior sampling

On this page 7

Thompson sampling is a Bayesian decision strategy for sequential choice problems in which an agent selects each action with the probability that it is the best action, given everything observed so far. In reinforcement learning it is best known as a solution to the multi-armed bandit problem, where it balances the exploration-exploitation tradeoff by drawing a random sample from the posterior distribution of each action’s expected reward and playing the action whose sample is highest.

The method is also called posterior sampling or probability matching. It dates back to a 1933 proposal by William R. Thompson for clinical trials and became widely used once researchers showed that it achieves near-optimal regret in many bandit settings while remaining simple to implement.

How Thompson sampling chooses an action

Thompson sampling chooses an action by sampling one plausible model of the world from the posterior and acting optimally for that sample. The agent keeps a probability distribution over the unknown reward parameter of every action. In each round it repeats a short loop.

  1. Sample: draw one value of the expected reward from each action’s posterior.
  2. Act: play the action with the highest sampled value.
  3. Observe: record the reward returned by the environment.
  4. Update: apply Bayes’ rule to refine the posterior of the action that was played.

Exploration emerges automatically. An action with few observations has a wide posterior, so its samples sometimes come out high and the action is tried again. An action that has been tested often has a narrow posterior centered on its true mean, so it is chosen only if that mean is genuinely competitive. The amount of exploration therefore shrinks as uncertainty shrinks, without any hand-tuned schedule.

Conjugate priors and posterior updates

Thompson sampling is cheapest when the prior and the reward likelihood form a conjugate pair, because the posterior then stays in the same family and updates reduce to adding counts or sums. The most common case is the Beta-Bernoulli model for binary rewards such as click or no click: each arm starts with Beta(1, 1), and every success adds one to alpha while every failure adds one to beta.

Reward typePriorPosterior update
Binary successBeta(alpha, beta)Add successes to alpha, failures to beta
Real-valued, known varianceNormal on the meanPrecision-weighted average of observations
Counts per periodGamma on the rateAdd counts to shape, periods to rate
Categorical outcomeDirichletAdd one to the observed category
Linear in context featuresMultivariate normalBayesian linear regression update
Common reward models for Thompson sampling

When no conjugate form exists, for example with neural network reward models, practitioners use approximate posteriors: bootstrapped ensembles, Laplace approximations, Markov chain Monte Carlo or variational inference. These keep the logic of the method but add computing cost and approximation error, which can weaken exploration if the posterior is too narrow.

Thompson sampling compared with other exploration strategies

Thompson sampling differs from other bandit strategies in that it randomizes according to uncertainty rather than adding a fixed amount of noise or an explicit optimism bonus. The table contrasts it with the two neighboring approaches most often used in practice.

StrategyExploration mechanismMain strengthMain weakness
Thompson samplingRandom draws from the posteriorStrong empirical performanceNeeds a usable posterior
Upper confidence boundOptimism bonus on each estimateDeterministic, strong theoryBonus constants need care
Epsilon-greedyRandom action with probability epsilonTrivial to implementExplores bad arms forever
Pure greedyNoneNo wasted trialsCan lock onto a poor arm
Exploration strategies for bandit problems

For Bernoulli bandits, Thompson sampling attains logarithmic regret that matches the Lai-Robbins lower bound asymptotically, the same guarantee class as the best upper confidence bound methods. Its random choices are also an advantage under delayed or batched feedback, because parallel decisions made before rewards arrive naturally spread across arms instead of all repeating one choice.

Contextual and reinforcement learning extensions

Thompson sampling extends beyond simple bandits to contextual bandits and full Markov decision processes by sampling a whole model instead of a single number per action. In a contextual bandit, the agent samples weights of a reward model and scores each action for the current user or situation.

SettingWhat is sampledTypical example
Multi-armed banditMean reward per armChoosing among ad creatives
Contextual banditParameters of a reward modelPersonalized article ranking
Episodic MDPTransition and reward modelPosterior sampling for reinforcement learning, PSRL
Deep reinforcement learningValue function from an ensembleBootstrapped deep Q-networks
Where posterior sampling is applied

In posterior sampling for reinforcement learning, the agent samples one complete environment model at the start of each episode, plans the optimal policy for that model and follows it for the whole episode. This gives deep, temporally consistent exploration, which per-step randomization such as epsilon-greedy cannot provide in environments with sparse rewards.

Limitations and practical pitfalls of Thompson sampling

The quality of Thompson sampling depends on the quality of the posterior, and most failures trace back to a wrong or overconfident model. The table lists frequent problems seen in production systems.

ProblemCauseRemedy
Premature convergenceOverly strong or narrow priorUse weak priors, check posterior width
Stale beliefsRewards drift over timeDiscount old data or use sliding windows
Slow decisionsExpensive approximate posteriorUse conjugate models or cached samples
Hard-to-audit choicesRandomized action selectionLog seeds, samples and posteriors
Common problems and remedies

Thompson sampling also optimizes cumulative reward, not statistical certainty about which arm is best. When the goal is a clean comparison with a fixed error rate, a classical experiment or a best-arm identification algorithm is the more suitable tool.

Understanding it simply

Thompson sampling is a way of choosing under uncertainty by letting your doubts vote. Imagine choosing between several new lunch places. For each one, you hold a rough guess of how good it is, and the less you know, the vaguer the guess. Each day you imagine one possible quality for every place, drawn from your guess, and go to the one that looks best today.

Places you barely know sometimes look great in your imagination, so you still try them. Places you know well stop surprising you. Over time you eat mostly at the best place while having tried the others just enough.

Applied in practice

An online newspaper tests six headline variants for its lead story during the first hour after publication. A classical A/B test would split traffic evenly for the full hour, sending most readers to weaker headlines. Instead, the editorial platform runs a Beta-Bernoulli Thompson sampling policy that treats each click as a success and each impression without a click as a failure.

After about 20 minutes and 30,000 impressions, one headline with a click rate near 4.1 percent receives more than 80 percent of the traffic, while the weakest variants, near 2 percent, are shown only occasionally. Because the platform discounts older observations, a headline that improves after a breaking update can still regain traffic.

Compared with an even split, the newsroom estimates that the policy recovers most of the clicks an even test would have lost, while editors still see which headline won.