Thompson Sampling: A Practical Tour

Matthew Reda Experimental design

Every always-on test faces the same tension, whether the thing under test is creative rotation, a landing page, or a bid strategy: 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. What follows is the mechanics of that move, the case against the obvious alternatives, and the places 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. Then the internet made the problem operationally urgent. An ad server runs thousands of small experiments per hour, and every impression is at once 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, and 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 then 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, and each \( \theta_k \) carries 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 and \( \beta_k \) tallies failures, and the posterior concentrates as both grow. Written out, the whole 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. That holds even on combinatorially large action spaces, where the argmax step might be Dijkstra's algorithm run 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 is asking "if this were the true rate, what would I do?", never "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. Thompson regret then grows far slower than the even-split baseline’s straight line.

Greedy, UCB, and the Case for Sampling

Greedy assigns zero value to uncertainty. If an early lucky streak flatters a mediocre arm, greedy plays that arm 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. That fixes the lock-in, at the cost of exploring uniformly and spending budget on arms the posterior has already ruled out.

Take 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 the three with probabilities of roughly 0.82, 0, and 0.18, which are their posterior probabilities 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. Its canonical index, UCB1 (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 at once. That assumption draws a hyper-rectangular confidence set, and the rectangle grows wildly over-optimistic as components multiply, while the plausible region is closer to an ellipsoid. A joint posterior draw has no such defect. One coordinate can run high, but all of them rarely deviate together. That is why the sampling variant wins at scale in the cascading-recommendation experiments of Russo et al. (2018). A re-tuned UCB narrows the gap and can win at small sizes, so read the comparison as scale-dependent rather than a blanket verdict.

RuleHow it treats uncertaintyCharacteristic failure
GreedyIgnores it and acts on the point estimateLocks onto a lucky early arm and 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 into 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, while sublinear growth 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. That is 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. One asymmetry survives the conversion. 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 rather than with 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. That is why informative priors and rich feedback 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. Behind the second sits the chain rule for mutual information: the total information ever gained about \( x^* \) cannot exceed its prior entropy. That 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 binding constraint becomes the ratio rather than the entropy.

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 rather than 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), which is cheap but sensitive to parameterization. Langevin Monte Carlo runs a gradient-guided random walk whose stationary distribution is the posterior, and with minibatch gradients and preconditioning it scales well. The bootstrap resamples history and refits. Nonparametric and easy to ship, with essentially no 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," which carries the idea over to neural-network reward models. Roughly thirty members suffice, and too few collapses the method back 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 that 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. That is usually the arm you are trying to learn about, and the deflation lands 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. Extra regret shows up as an additive term bounded by the mean delay. Their second result covers what happens when outcomes older than some window are permanently lost, which is the realistic case for media, since attribution stops matching after days or weeks. Under that condition 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, which widens 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, and seasonality shifts the base rate. A standard posterior concentrates monotonically through all of that, so exploration decays to zero and the algorithm ends up completely confident in stale data. The remedy is to re-inject uncertainty on purpose: decay the pseudo-counts toward the prior at some rate \( \gamma \) each period, so the posterior never fully hardens. That 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, which is the "concurrence" setting studied in the bandit literature: many actions drawn from one frozen posterior, none of them informed by the others' outcomes. Independent draws per decision works, and 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.

Some media questions should not be given to Thompson sampling at all. Probability matching maximizes reward during learning, so it exploits as soon as it is confident. That is the wrong shape for pure identification, the "which creative wins, decided once at quarter end" question, where the algorithm converges slowly on near-ties it no longer cares to separate. The same holds for time-boxed tests, and for "revealing" actions: an action known to pay poorly that would nonetheless settle every open question 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, and account for batched assignment. Reach for a pure-exploration method when the goal is a one-shot decision rather than cumulative reward.

References