Thompson Sampling

Imagine choosing among several slot machines whose payout rates are unknown. You want to earn reward now, but you also need to discover whether an overlooked machine is better. Thompson sampling handles that trade-off by acting as though one plausible version of the world were true, then revising its beliefs after seeing the result.

How it chooses actions
The method keeps a probability distribution over each action’s uncertain reward. On every decision:

• It samples one plausible reward value for each action from its current belief.
• It selects the action with the highest sampled value.
• It observes the reward and updates the relevant belief.

This is called posterior sampling: actions are chosen in proportion to the probability that they are truly best. An action with uncertain value gets tried because it could be excellent; an action with strong evidence of high reward gets selected frequently because it is likely excellent. Unlike epsilon-greedy, it does not spend a fixed fraction of decisions exploring indiscriminately.

A concrete bandit example
Suppose an agent has shown two versions of a webpage to visitors. Version A has many visits and a steady 4% conversion rate. Version B has only a few visits, with an apparent 6% rate. Thompson sampling samples plausible conversion rates from both beliefs. Most draws will favor A because its evidence is reliable, but enough draws favor B to test whether its promising early results are real. As evidence accumulates, random exploration shrinks naturally. For binary rewards, a Beta distribution paired with observed successes and failures gives a particularly simple implementation.

Why it matters in reinforcement learning
In a basic multi-armed bandit, each choice produces an immediate reward. Reinforcement learning extends the idea to states and delayed consequences: an agent can sample a plausible model, value function, or policy and follow it long enough to gather coherent evidence. This can uncover a useful route that greedy action-by-action choices would never enter. The challenge is that neural-network value estimates rarely provide trustworthy uncertainty by themselves; a single DQN output is not a posterior. Practical approximations use ensembles, randomized value functions, or Bayesian models. Poor uncertainty estimates cause either premature commitment to a bad action or wasteful exploration long after the answer is clear.