Thompson Sampling

The one idea: Instead of computing a confidence bound and picking the arm with the highest score (UCB's approach), Thompson Sampling keeps a full probability distribution over each arm's true win rate, draws one random guess from each distribution, and pulls whichever arm's guess came out highest. Repeat that draw-and-compare every round, and the arms you're genuinely unsure about get sampled unpredictably often — exploration falls out of the randomness itself, with no bonus term to tune.

⚠️ The trap: "Thompson Sampling is basically UCB with extra math" undersells a real behavioral difference. UCB is deterministic — the same history always produces the same next pull, and it can get stubbornly attached to a near-tie for many rounds. Thompson Sampling's next pull is a random draw from evolving distributions, which in practice adapts faster when one arm turns out to be a fluke, because a single unlucky sample doesn't lock in a decision the way a fixed formula's tie-break rule can.

From confidence bounds to belief distributions

The UCB lesson set up the problem: five ad variants (A–E), each with an unknown true click-through rate (CTR), and a sequential choice — which ad to show next — that both earns clicks and teaches you something. UCB solved it by keeping a point estimate Q(a) per arm plus a shrinking uncertainty bonus, and always pulling the arm with the highest estimate + bonus.

Thompson Sampling solves the same problem with a different piece of machinery: instead of a point estimate and a bonus, it keeps a full probability distribution over each arm's true CTR, updates that distribution as data arrives, and picks the next arm…