Thompson Sampling

Bayesian posterior sampling, conjugate models, empirical performance, top-2 TS

You have 5 news headlines, each with a Beta prior over its true CTR. Headline A has Beta(10, 90) — 100 impressions, about 10% estimated CTR. Headline E has Beta(1, 1) — never shown, prior is Uniform[0,1]. Thompson Sampling asks a simple question each round: given what you know, which headline is most likely to be the best? Sample one θ from each arm's posterior. Show the headline with the highest sampled θ.

The mechanism is elegant. Headline E's Beta(1,1) posterior is wide — it samples uniformly across 0 to 1. Its sampled value frequently exceeds the 10% concentrations of A through D. So TS explores headline E aggressively — not because it randomly picks an arm with probability ε, but because uncertainty genuinely warrants it. After 50 more impressions of E, its posterior narrows around whatever its true CTR turns out to be. If E is bad (true CTR 2%), its posterior concentrates near 0.02 and almost never samples above the other headlines. Exploration of E drops to near zero automatically. This is exploration proportional to P(arm is optimal) — not uniform, not confidence-bound-based, but posterior-sampling.

The update rule is trivially simple. On each impression: if click, α += 1; if no click, β += 1. The mean of Beta(α, β) is α/(α+β), which converges to the true CTR as data accumulates. The variance is α·β / [(α+β)²·(α+β+1)], which shrinks as α+β grows. Exploration happens automatically where it is most informative.

NOT this. "Thompson Sampling always requires conjugate priors — Beta for Bernoulli rewards." Beta-Binomial is the most common case, but TS generalizes to any likelihood with an appropriate prior. For Gaussian rewards (continuous feedback like watch time), use Normal-Normal conjugate. For non-conjugate settings, sample from an approximate posterior using Laplace approximation or neural last-layer variance. The conjugate prior is a computational convenience, not a theoretical requirement.

Key points

• Beta-Binomial TS update: on reward r ∈ {0,1} from arm a, α_a += r, β_a += (1−r). Select arm with highest sampled θ_a ~ Beta(α_a, β_a). Arms with few observations have wide posteriors that sample high frequently — exploration happens automatically. Arms with many observations have concentrated posteriors near their true CTR — exploitation dominates. Start with Beta(1,1) for uninformative priors. In production, an informative prior Beta(10, 990) for 1% CTR dramatically reduces early over-exploration of low-CTR arms. Prior misspecification is the main failure mode: Beta(1,1) on an arm with true CTR 0.001 puts 50% probability mass above 0.5 and wastes enormous early exploration budget.
• TS exploration is proportional to P(arm a is optimal): arm a is pulled with probability P(θ_a > θ_j for all j≠a | observations). As arm a accumulates observations and its posterior concentrates near a low value, this probability collapses toward zero. UCB in contrast applies a fixed confidence bonus √(2 ln t / N_a) regardless of how implausible it is that the arm is optimal — TS gives up on clearly inferior arms faster. This is why TS empirically outperforms UCB at finite horizons: the posterior shape adapts to the data in a way that a worst-case Hoeffding-bound formula cannot.
• Applying frequentist stopping rules to TS experiments inflates Type-I error. Classical A/B testing uses fixed random allocation, then applies a p-value test at a predetermined sample size. TS continuously reallocates traffic toward better variants. The allocation is no longer random — it is outcome-dependent. A p-value at a fixed sample size applied to TS data will reject the null too often because you are peeking at adaptive data. Use Bayesian stopping criteria (P(variant B is best) > 0.95, or expected loss < threshold) or always-valid sequential p-values that account for the adaptive allocation.

Recap

• Mechanism: sample θ from each arm's posterior, show the arm with the highest sample.
• Beta-Binomial update: on reward r∈{0,1}, α += r, β += (1−r) — trivially simple.
• Exploration ∝ P(arm optimal): wide posteriors sample high often; inferior arms collapse to near-zero pulls automatically.
• Beats UCB at finite horizons: posterior shape adapts to data; UCB's fixed Hoeffding bonus gives up on losers more slowly.
• Prior misspecification = main failure: Beta(1,1) on true CTR 0.001 puts 50% mass above 0.5 — use informative priors.
• Adaptive allocation breaks frequentist stopping: peeking inflates Type-I error — use Bayesian stopping (P(best)>0.95) or always-valid p-values.
• NOT this: conjugate priors are a computational convenience, not required — Normal-Normal for Gaussian, Laplace/neural for non-conjugate.

Check your understanding