Interactive explainer
Bandit simulation: comparing Thompson sampling
Three arms, unknown success rates and limited trials: watch Thompson sampling balance exploration and exploitation, and compare learning’s cost with ε-greedy and UCB1.
Bandit simulation: Thompson sampling, ε-greedy and UCB compared
This explainer requires JavaScript. It simulates three arms with hidden success rates and compares Thompson sampling, ε-greedy and UCB1 through cumulative regret.
How the explainer works
Each of the three arms produces a success on a pull with its hidden rate . A strategy aims to collect as many successes as possible in pulls, but must first discover which arm is best. Regret measures the cost of learning:
Three strategies compete:
- Thompson sampling (Thompson 1933) maintains a posterior for each arm, with successes and failures. At each step, it draws a value from every posterior and plays the arm with the largest draw.
- ε-greedy plays every arm once, then chooses a random arm with probability and otherwise the arm with the highest rate observed so far.
- UCB1 (Auer et al. 2002) plays every arm once, then the arm with the largest , acting optimistically towards arms with little evidence.
The “Live” tab shows a single Thompson-sampling run step by step. The “Comparison” tab repeats the experiment 100 to 500 times for all three strategies using reproducible randomness and shows mean regret.
Three things to try
- Watch a live run. Start slowly: initially the draws vary widely and every arm gets a turn. After a few hundred pulls, the best arm’s posterior is narrow and the others are rarely played.
- Close differences. Choose “Close”. Every strategy needs longer; regret increases because distinguishing 12% from 15% requires many observations.
- Change ε. With large , ε-greedy keeps exploring and accumulates linearly increasing regret. With very small , it sometimes stays with the wrong arm for a long time, visible in the wide variation between runs.
The multi-armed bandits and Thompson sampling article explains the background, formulas and limitations compared with A/B testing.
Sources and further reading
- PaperThompson, W. R. (1933): On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika 25(3/4), 285–294.
- PaperAuer, P., Cesa-Bianchi, N. and Fischer, P. (2002): Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47, 235–256.