Thompson sampling

Thompson sampling is a Bayesian exploration strategy: keep a posterior distribution over each action's unknown value, draw one sample from each posterior, and take the action whose sample is highest. Each action ends up chosen with the probability that it is the best one, given the data so far.

The algorithm for Bernoulli rewards

For arms that pay 1 or 0, a Beta prior is conjugate. Start each arm at $\text{Beta}(1,1)$, which is uniform. Then repeat:

1. For each arm $a$, sample ${\tilde{\theta }}_a\sim \text{Beta}({\alpha }_a,{\beta }_a)$.
2. Pull $A_t=\arg {\max }_a{\tilde{\theta }}_a$.
3. On success set ${\alpha }_{A_t}\leftarrow {\alpha }_{A_t}+1$; on failure set ${\beta }_{A_t}\leftarrow {\beta }_{A_t}+1$.

The resulting choice probability is

which is why the method is also called probability matching.

Worked example

Arm A has 7 successes and 3 failures, so its posterior is $\text{Beta}(8,4)$ with mean 0.67. Arm B has 1 success and 1 failure, posterior $\text{Beta}(2,2)$ with mean 0.5. B looks worse but is far more uncertain. Drawing a million samples from each (seeded), B's draw beat A's 27.4% of the time, so Thompson sampling pulls B on roughly a quarter of steps until its posterior narrows. A greedy agent would never pull it.

Properties

• Logarithmic regret: for Bernoulli bandits it achieves the asymptotically optimal regret rate, matching the Lai and Robbins lower bound.
• Self-tuning: exploration fades as posteriors concentrate, with no $ϵ$ schedule to tune.
• Batch friendly: randomisation means parallel decisions naturally diversify, unlike deterministic UCB.
• Needs a posterior: easy for conjugate models, harder for neural networks, where ensembles or bootstrapped heads approximate it.

Why it matters

Proposed by William Thompson in 1933 for allocating patients between treatments, the method was largely ignored for decades and is now a standard choice for adaptive experiments, recommendation and online allocation. It often beats epsilon-greedy and UCB in practice. For evaluation work it is a reminder that a sensible question is not "which option has the best average?" but "how likely is each option to be best?", which is exactly the quantity it tracks.

Related terms

• Multi-armed bandit
• Upper confidence bound (UCB)
• Epsilon-greedy
• Regret
• Exploration-exploitation trade-off

Sources

1. William R. Thompson. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples, 1933. doi.org
2. Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen. A Tutorial on Thompson Sampling, 2017. arxiv.org