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.
- Sample: draw one value of the expected reward from each action’s posterior.
- Act: play the action with the highest sampled value.
- Observe: record the reward returned by the environment.
- 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 type | Prior | Posterior update |
|---|---|---|
| Binary success | Beta(alpha, beta) | Add successes to alpha, failures to beta |
| Real-valued, known variance | Normal on the mean | Precision-weighted average of observations |
| Counts per period | Gamma on the rate | Add counts to shape, periods to rate |
| Categorical outcome | Dirichlet | Add one to the observed category |
| Linear in context features | Multivariate normal | Bayesian linear regression update |
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.
| Strategy | Exploration mechanism | Main strength | Main weakness |
|---|---|---|---|
| Thompson sampling | Random draws from the posterior | Strong empirical performance | Needs a usable posterior |
| Upper confidence bound | Optimism bonus on each estimate | Deterministic, strong theory | Bonus constants need care |
| Epsilon-greedy | Random action with probability epsilon | Trivial to implement | Explores bad arms forever |
| Pure greedy | None | No wasted trials | Can lock onto a poor arm |
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.
| Setting | What is sampled | Typical example |
|---|---|---|
| Multi-armed bandit | Mean reward per arm | Choosing among ad creatives |
| Contextual bandit | Parameters of a reward model | Personalized article ranking |
| Episodic MDP | Transition and reward model | Posterior sampling for reinforcement learning, PSRL |
| Deep reinforcement learning | Value function from an ensemble | Bootstrapped deep Q-networks |
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.
| Problem | Cause | Remedy |
|---|---|---|
| Premature convergence | Overly strong or narrow prior | Use weak priors, check posterior width |
| Stale beliefs | Rewards drift over time | Discount old data or use sliding windows |
| Slow decisions | Expensive approximate posterior | Use conjugate models or cached samples |
| Hard-to-audit choices | Randomized action selection | Log seeds, samples and posteriors |
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.