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.

Interactive

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 μk\mu_k. A strategy aims to collect as many successes as possible in TT pulls, but must first discover which arm is best. Regret measures the cost of learning:

R(T)=∑t=1T(μ∗−μat),μ∗=max⁡kμkR(T) = \sum_{t=1}^{T} \left(\mu^{*} - \mu_{a_t}\right), \qquad \mu^{*} = \max_k \mu_k

Three strategies compete:

  • Thompson sampling (Thompson 1933) maintains a posterior Beta⁡(1+sk, 1+fk)\Beta(1 + s_k,\, 1 + f_k) for each arm, with sks_k successes and fkf_k 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 ε\varepsilon 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 μ^k+2ln⁡t/nk\hat\mu_k + \sqrt{2 \ln t / n_k}, 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

  1. 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.
  2. Close differences. Choose “Close”. Every strategy needs longer; regret increases because distinguishing 12% from 15% requires many observations.
  3. Change ε. With large ε\varepsilon, ε-greedy keeps exploring and accumulates linearly increasing regret. With very small ε\varepsilon, 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

  1. 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.
  2. PaperAuer, P., Cesa-Bianchi, N. and Fischer, P. (2002): Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47, 235–256.

From NyxAI

smartlytics is the learning hub of NyxAI GmbH.

Explore the methods we work with, explained openly, with sources and calculations you can reproduce.

Decision Core

NyxAI is developing a Decision Core for Decision Intelligence that combines optimisation, simulation, statistics and reinforcement learning: compare options, make uncertainty visible and learn from outcomes, with people in control.

AI workflows at NyxAI

DeepSquare

Explainable chess AI with human playing styles: NyxAI’s testing ground for understandable decisions under time pressure.