Thompson Sampling: A Practical Tour

Matthew Reda Experimental design

Every always-on test — creative rotation, landing pages, bid strategies — faces the same tension: keep serving the option that looks best, or spend impressions learning whether something else is better. Thompson sampling resolves it with one move: draw a sample from the posterior, act as if the sample were true, update, repeat. This post covers how it works, why it beats the obvious alternatives, and where it quietly fails on media problems.

Sample, Act, Repeat

The multi-armed bandit is the canonical formalization of learning while earning: \( K \) actions ("arms"), each period the agent picks one, collects a reward from that arm's unknown distribution, and tries to maximize the cumulative total. The internet made the problem operationally urgent: an ad server runs thousands of small experiments per hour, and every impression is simultaneously a trial and a payout. Exploration is not free — it has to be earned back through better future decisions.

Definition: Thompson sampling (probability matching)

Maintain a posterior over the unknown parameters \( \theta \). Each period, draw one sample \( \hat\theta \), play the action that would be optimal if \( \hat\theta \) were the truth, and update on the observed outcome. Because \( \hat\theta \) is a posterior draw, each action is selected with probability equal to the posterior probability that it is best:

$$ \Pr(x_t = k \mid \mathbb{H}_{t-1}) \;=\; \Pr\big(k = x^* \mid \mathbb{H}_{t-1}\big). $$

That equality is the whole design. Arms that could plausibly be optimal keep getting tried, in proportion to how plausible they are; arms the posterior has written off get abandoned — no confidence bounds, no exploration rate to tune. The idea is old: Thompson (1933) proposed it for allocating patients between two treatments, and it sat largely ignored for eight decades until Chapelle and Li (2011) and Scott (2010) showed it beating standard alternatives in display advertising and web optimization; it now runs in production across most large internet platforms. Where bandits sit alongside Bayesian experimental design and Bayesian optimization is the subject of a companion post; the short version is that bandits are the branch that insists on earning reward during the experiment.

The Beta-Bernoulli Bandit

The cleanest concrete instance is binary rewards with conjugate priors. Arm \( k \) pays 1 with unknown probability \( \theta_k \) and 0 otherwise; give each \( \theta_k \) an independent \( \mathrm{Beta}(\alpha_k, \beta_k) \) prior (\( \alpha_k = \beta_k = 1 \) is uniform). Conjugacy makes the posterior update after playing arm \( x_t \) and observing reward \( r_t \in \{0,1\} \) a pair of counter increments:

$$ (\alpha_{x_t}, \beta_{x_t}) \;\leftarrow\; (\alpha_{x_t} + r_t,\; \beta_{x_t} + 1 - r_t), $$

with all other arms untouched. The parameters are pseudo-counts — \( \alpha_k \) tallies successes, \( \beta_k \) failures — and the posterior concentrates as they grow. The full algorithm fits in a few lines:

# illustrative
# Beta-Bernoulli Thompson sampling: two counters of state per arm
alpha = [1.0] * K                       # prior successes + 1
beta  = [1.0] * K                       # prior failures  + 1
for t in range(T):
    samples = [rng.beta(alpha[k], beta[k]) for k in range(K)]
    k = argmax(samples)                 # act as if the draw were true
    r = pull(k)                         # observe 0/1 reward
    alpha[k] += r                       # conjugate update
    beta[k]  += 1 - r

The greedy version is identical except for one line: it acts on the posterior mean \( \alpha_k/(\alpha_k+\beta_k) \) instead of a draw. That single line is the difference between an algorithm that provably keeps learning and one that can lock onto a mediocre arm forever. And the pattern generalizes verbatim: wherever you can sample the posterior and solve the best-action problem for a given \( \hat\theta \), Thompson sampling is greedy with the point estimate swapped for a draw — even on combinatorially large action spaces, where the argmax step might be Dijkstra's algorithm on sampled edge weights.

💡 The draw is a parameter, not an outcome

A common misreading: the sampled \( \hat\theta_k \) is not a simulated click or conversion. It is a statistically plausible value of the arm's underlying success rate — the algorithm asks "if this were the true rate, what would I do?", not "what might happen next?". Sampling outcomes instead of parameters is a different, much worse algorithm.

Play the bandit

Three creatives with hidden true conversion rates of 0.30, 0.60, and 0.45 (dotted lines). Each arm carries a \( \mathrm{Beta}(\alpha,\beta) \) posterior over its rate. A pull draws one sample from every arm, plays the arm with the highest draw, observes a 0/1 reward, and does the two-counter update — watch B’s posterior sharpen and crowd out the others. The regret readout tracks reward lost against the unknown best arm, next to an even-split baseline that never stops exploring.

Pulls  A · B · C0 · 0 · 0
Believes best—
Regret (Thompson)0.00
Regret (even split)0.00

Probability matching sends traffic to each arm in proportion to its posterior chance of being best, so the losing arm A starves while the plausible contender keeps some share — and Thompson regret grows far slower than the even-split baseline’s straight line.

Greedy, UCB, and the Case for Sampling

Why not just be greedy? Because greedy assigns zero value to uncertainty: if an early lucky streak flatters a mediocre arm, greedy plays it forever and never collects the data that would correct the mistake. The standard patch, \( \epsilon \)-greedy "dithering," forces a random action some fixed fraction of the time — fixing the lock-in but exploring uniformly, wasting budget on arms the posterior has already ruled out.

A worked example from Russo et al. (2018): two arms have been played a thousand times each, with posteriors concentrated near success rates of 0.6 and 0.4; a third has been tried only three times. Thompson sampling plays them with probabilities of roughly 0.82, 0, and 0.18 — each arm's posterior probability of being best. The hopeless middle arm gets nothing; the uncertain newcomer gets real traffic. An \( \epsilon \)-greedy scheme would split its exploration budget evenly between the two.

The serious classical competitor is the upper-confidence-bound (UCB) family: score each arm by a statistically plausible best case and play the highest. The canonical UCB1 index (Auer, Cesa-Bianchi, and Fischer, 2002) adds an exploration bonus that shrinks with plays:

$$ U_t(k) \;=\; \frac{\alpha_k}{\alpha_k+\beta_k} \;+\; c\,\sqrt{\frac{1.5\,\log t}{\alpha_k+\beta_k}}. $$

UCB and Thompson sampling are close cousins — far closer to each other than either is to greedy. Where they diverge is on structured actions. Scoring a ranked list or bundle by each component's individually optimistic bound assumes every component attains its best case simultaneously — a hyper-rectangular confidence set that grows wildly over-optimistic as components multiply, when the truly plausible region is closer to an ellipsoid. A joint posterior draw has no such defect: one coordinate can run high, but all rarely deviate together. This is why the sampling variant wins at scale in the cascading-recommendation experiments of Russo et al. (2018) — though a re-tuned UCB narrows the gap and can win at small sizes. The comparison is scale-dependent, not a blanket verdict.

RuleHow it treats uncertaintyCharacteristic failure
GreedyIgnores it — acts on the point estimateLocks onto a lucky early arm; never self-corrects
\( \epsilon \)-greedyIgnores it, plus uniform random probesWastes exploration on arms already known to be bad
UCBInflates each estimate by a confidence widthPer-coordinate optimism compounds on structured actions
Thompson samplingPropagates it — acts on a joint posterior drawOver-explores when identification, not reward, is the goal

What "Near-Optimal" Means

The field's performance currency is regret: the cumulative reward lost to not knowing the best arm from the start,

$$ \mathrm{Regret}(T) \;=\; \sum_{t=1}^{T} \Big( \mu(x^*, \theta) - \mu(x_t, \theta) \Big), $$

where \( x^* \) is the optimal action under the true \( \theta \). Linear growth means the algorithm is failing to learn; sublinear means its per-period mistakes vanish. Three results calibrate "near-optimal."

It hits the classical gold standard. For the Bernoulli bandit, Lai and Robbins (1985) proved that no reasonable algorithm's regret can grow slower than \( \log T \), with an instance-dependent constant governed by the arms' gaps and KL divergences. Thompson sampling attains it exactly, constant included (Agrawal and Goyal, 2012; Kaufmann, Korda, and Munos, 2012), after Chapelle and Li (2011) showed it empirically. It also carries a worst-case guarantee of order \( \sqrt{KT \log T} \) against a fundamental limit of order \( \sqrt{KT} \) for any algorithm — within a logarithmic factor of unbeatable.

Its guarantees inherit from UCB on structured problems. Because Thompson sampling plays \( x_t \) with the posterior distribution of the optimum \( x^* \), any history-measurable confidence sequence satisfies \( \mathbb{E}[U_t(x_t)] = \mathbb{E}[U_t(x^*)] \) — so nearly any UCB regret proof converts into a Thompson-sampling bound, with one asymmetry: UCB's performance depends on the specific bound it uses, while Thompson sampling only needs a good bound to exist (Russo and Van Roy, 2014). For linear reward models in dimension \( d \), this route gives regret of order \( d\sqrt{T}\log T \) — scaling with model dimension, not the number of actions, which may be infinite.

Information theory explains the "why." Russo and Van Roy (2016) define the information ratio — squared expected per-period regret divided by the information gained about the optimal action's identity — and show that any algorithm keeping it below \( \overline{\Gamma} \) satisfies

$$ \mathbb{E}[\mathrm{Regret}(T)] \;\le\; \sqrt{\overline{\Gamma}\; H(x^*)\; T}, $$

where \( H(x^*) \) is the entropy of the prior over which action is best. Read it as a budget: the algorithm pays regret to buy bits about \( x^* \), and there are only \( H(x^*) \) bits to buy. The bound scales with the entropy of the answer, not the size of the action space — which is why informative priors and rich feedback genuinely accelerate learning. On an online shortest-path problem, observing each edge's travel time rather than only the total cost improves the ratio from order \( d \) to a small constant.

Deep diveThe entropy-budget argument in four lines

Write \( I_t = I\big(x^*; (x_t, y_t) \mid \mathbb{H}_{t-1}\big) \) for the information the period-\( t \) observation carries about the optimal action, and let \( \Gamma_t \) be the information ratio, so that expected per-period regret equals \( \sqrt{\Gamma_t I_t} \). Then

$$ \mathbb{E}[\mathrm{Regret}(T)] \;=\; \sum_{t=1}^{T} \sqrt{\Gamma_t\, I_t} \;\le\; \sqrt{\overline{\Gamma}\, T \sum_{t=1}^{T} I_t} \;\le\; \sqrt{\overline{\Gamma}\, T\, H(x^*)}. $$

The first inequality is Cauchy–Schwarz; the second is the chain rule for mutual information — the total information ever gained about \( x^* \) cannot exceed its prior entropy. The same decomposition predicts the failure modes below: when the most informative action is not a plausibly optimal one, probability matching never plays it, and the ratio — not the entropy — becomes the binding constraint.

Extensions That Matter

Nothing in the algorithm required independent arms or Bernoulli rewards. Two extension families carry most of the practical weight.

Contextual and linear bandits

If a context arrives before each decision — user features, time of day — no new algorithm is needed: fold the context into the action and let the admissible set vary period to period. The workhorse model is linear or generalized-linear: in the news-recommendation setting of Chapelle and Li (2011), an article's click probability is a logistic function \( g(z_t^\top \theta_x) \) of user features, and Thompson sampling draws from the posterior over the coefficients. Two structural lessons matter more than the model. Model correlations between actions: a sampler that captures shared shocks substantially outperforms one that pretends arms are independent, because one arm's outcome then teaches you about many. And share parameters across arms: per-article coefficients learn nothing transferable, while interaction features with a single shared vector let every impression inform every article. In a product-assortment example, Thompson sampling beats greedy precisely because greedy never deliberately probes the substitution effects between products.

Approximate posterior sampling

Conjugate posteriors are the exception. Once the reward model has a logistic link or a neural network in it, the exact draw is unavailable — and the fix is to approximate the sample, not the whole posterior. Four methods recur. The Laplace approximation fits a Gaussian at the posterior mode (Chapelle and Li's choice for display-ad click models); cheap, but sensitive to parameterization. Langevin Monte Carlo runs a gradient-guided random walk whose stationary distribution is the posterior; with minibatch gradients and preconditioning it scales well. The bootstrap resamples history and refits — nonparametric and easy to ship, but essentially without guarantees. And ensemble sampling (Lu and Van Roy, 2017) maintains a few dozen perturbed models trained in parallel, picking one at random each period as the "draw" — extending the idea to neural-network reward models; roughly thirty members suffice, and too few collapses it toward greedy. Where exact sampling is available as a benchmark, all of these track its regret closely.

This is also where bandits connect back to marketing measurement. A geo-level budget experiment is a bandit whose "arm" is a spend allocation and whose posterior lives over a response surface; drawing one sample of the surface and allocating as if it were true is precisely the wave-level recommendation logic in this framework's continuous learning methodology. Same principle, heavier posterior.

Where It Breaks for Media

Thompson sampling's guarantees assume rewards arrive immediately, the world is stationary, and decisions update one at a time. Media violates all three.

⚠️ Delayed conversions bias the posterior against new arms

A conversion credited days after the impression is not a missing failure — but a naive update treats it as one. Every pending outcome counted as a zero deflates the estimated rate of whichever arm was played most recently — usually the arm you are trying to learn about — precisely while the algorithm is deciding its fate. The estimator must be corrected for the probability that each pull's outcome could have arrived yet.

The theory here is sharper than folklore suggests. Vernade, Cappé, and Perchet (2017) model each pull as triggering a latent conversion indicator plus a random delay, and prove two contrasting results. If every conversion is eventually observed, delay costs nothing in the leading-order regret rate — the extra regret is an additive term bounded by the mean delay. But if outcomes older than some window are permanently lost — the realistic case: attribution stops matching after days or weeks — the problem is exactly as hard as a bandit whose conversion rates are all scaled down by the probability of landing inside the window. Their delay-corrected algorithms discount each pull by the probability its outcome could have resolved by now — widening recent arms' uncertainty instead of penalizing them. The translation for a Thompson-sampling system: update on resolved outcomes with a delay-aware likelihood, and expect learning to slow as conversion lag grows relative to decision cadence.

Non-stationarity is the second breakage. Creative fatigues, competitors move, seasonality shifts the base rate — but a standard posterior concentrates monotonically, so exploration decays to zero and the algorithm ends up totally confident in stale data. The remedy is to deliberately re-inject uncertainty — decay the pseudo-counts toward the prior at some rate \( \gamma \) each period, so the posterior never fully hardens. The price is permanent: per-period regret can no longer reach zero, because the target never stops moving.

Batched assignment is the third. Ad servers do not update a posterior between impressions; they assign thousands of users per model refresh. This is the "concurrence" setting: many actions drawn from one frozen posterior, none informed by the others' outcomes. Independent draws per decision works — regret per action falls faster as more decisions run in parallel — but learning per action count is slower than fully sequential updating, so a batched system needs more traffic to reach the same certainty. Batching also compounds delay: by the time one batch resolves, several more have been assigned from the stale posterior.

Finally, some media questions should not be given to Thompson sampling at all. Probability matching maximizes reward during learning — it exploits as soon as it is confident. That is the wrong shape for pure identification ("which creative wins, decided once at quarter end"), where it converges slowly on near-ties it no longer cares to separate; for time-boxed tests; and for "revealing" actions — an action known to pay poorly but that would settle all uncertainty is never played, because it is never plausibly optimal. Those cases call for pure-exploration variants or information-directed sampling, which buy information deliberately rather than incidentally.

Takeaways

  • Thompson sampling is greedy with one line changed: act on a posterior draw instead of the posterior mean. The draw is a plausible parameter value, not a simulated outcome.
  • Probability matching explores where uncertainty is decision-relevant — unlike \( \epsilon \)-greedy's uniform dithering or UCB's per-coordinate optimism on structured actions.
  • It matches the Lai–Robbins \( \log T \) lower bound for Bernoulli arms; information-theoretic bounds scale with the entropy of the optimal action, not the size of the action space.
  • Non-conjugate models are not a blocker — Laplace, Langevin, bootstrap, and ensemble approximations track exact sampling closely.
  • For media, delay-correct the updates, decay the posterior under drift, account for batched assignment — and use a pure-exploration method when the goal is a one-shot decision, not cumulative reward.

References