Thompson Sampling in Bandits

Keep a belief curve over each option's true payout, draw one sample from each curve, and play the winner. Uncertain options win draws just by having wide curves.

Three arms with posterior means 0.25, 0.75, and 0.50 draw 0.179, 0.481, and 0.729, so the uncertain third arm wins the pull and its mean moves to 0.60 after a success

Why Does This Exist?

A multi-armed bandit forces one choice: pull the current best arm or test the rest. The classic rules each have a blind spot. Epsilon-greedy explores blindly, spending tries on arms already proven bad. The upper confidence bound explores by formula, but its curiosity constant is a knob you must tune, and it can keep probing hopeless arms just because their counts are low.

Thompson sampling, from Thompson (1933), removes the knob. The agent keeps a full belief distribution over each arm's true payout, draws one plausible value from each belief, and pulls the arm with the highest draw. Each arm is then picked with exactly the probability that it is the best arm, a behavior called probability matching. Wide beliefs produce occasional high draws (exploration); tight beliefs around high means win most draws (exploitation). The shift from one regime to the other happens on its own as evidence arrives. This is one corner of the broader exploration versus exploitation tradeoff.

The one idea you need first.

A posterior is a belief after seeing evidence. Start with a prior guess about an arm's payout, observe successes and failures, and update with Bayes' rule to get the posterior. For binary win-or-lose rewards the convenient pair is the Beta prior with Bernoulli rewards: beliefs stay Beta-shaped forever, and updating means adding counts, as you will compute below.

Think of It Like This

Opinion dice for unfamiliar slot machines

You walk into a casino with three unfamiliar machines and one opinion die per machine. The faces show payouts you currently believe possible. The die for the machine that paid rarely is loaded with low faces. The die for the steady winner shows mostly high faces. The die for the machine you have barely touched is fair, with every face equally likely.

Before each coin, you roll all three dice and play whichever machine rolled highest. Most rounds the loaded winner rolls a high number and gets the coin. But every so often the fair die rolls its top face and beats the favorite, so you test the unknown machine. A win replaces low faces with high ones; a loss shaves the high faces off.

Point for point: the dice are the posteriors, one roll each is the sampling step, playing the highest roll is the argmax, and swapping faces is the conjugate update. Where it stops: real dice have a fixed set of faces, while Beta beliefs are continuous curves that sharpen smoothly, and no die captures the exact update arithmetic of adding one success or failure count.

How It Actually Works

Each arm $k$ has an unknown true success probability $\theta_k$ , a number between 0 and 1. The agent's belief about $\theta_k$ is a Beta distribution with two counters: $\alpha_k$ counts successes (plus the prior) and $\beta_k$ counts failures (plus the prior). The Beta mean, the agent's current estimate, is $\alpha_k / (\alpha_k + \beta_k)$ . A flat prior of $\alpha_k = 1, \beta_k = 1$ is a uniform belief over the whole interval.

Each round runs four steps:

Sample. Draw one value $\hat{\theta}_k$ from each arm's Beta belief.
Select. Pull $a = \arg\max_k \hat{\theta}_k$ , the arm with the highest draw.
Observe. Collect the binary reward $r$ , either 1 or 0.
Update. Add the outcome to the pulled arm's counters: $\alpha_a \leftarrow \alpha_a + r$ and $\beta_a \leftarrow \beta_a + (1 - r)$ . Untouched arms keep their counters. Because Beta is conjugate to Bernoulli, the belief stays Beta, so no integration is ever needed.

Worked example

Three arms, with beliefs summarized by mean and standard deviation (both computed from the counters by hand):

Arm 1, disappointing and well known: Beta(3, 9), mean $3/12 = 0.25$ , sd $\approx 0.12$ .
Arm 2, strong and well known: Beta(18, 6), mean $18/24 = 0.75$ , sd $\approx 0.09$ .
Arm 3, barely tried: Beta(2, 2), mean $2/4 = 0.50$ , sd $\approx 0.22$ .

One round (seeded draws, reproducible in the snippet below): the samples come out $0.179$ , $0.481$ , and $0.729$ . Arm 3 wins the argmax even though its mean trails Arm 2 by a quarter point, because its wide belief reaches further into high values. Suppose it pays $r = 1$ . Its counters become Beta(3, 2) with mean $3/5 = 0.60$ , and its belief tightens a notch.

A later round shows the other regime: draws $0.171$ , $0.877$ , $0.406$ hand the pull to Arm 2, the proven leader. A success there moves Beta(18, 6) to Beta(19, 6) with mean $19/25 = 0.76$ . Exploration and exploitation are the same code path. Only the widths differ.

Code

The worked example as a seeded script: beliefs, one sampling round per seed, and the conjugate update. Seeds make the draws reproducible.

1import random2from typing import List3
4
5def sample_round(alphas: List[float], betas: List[float], seed: int) -> List[float]:6    """One posterior draw per arm from Beta(alpha, beta) beliefs."""7    random.seed(seed)8    return [random.betavariate(a, b) for a, b in zip(alphas, betas)]9
10
11def update(alphas: List[float], betas: List[float], arm: int, reward: int) -> float:12    """Add the observed reward to the pulled arm's counters; return its new mean."""13    alphas[arm] += reward14    betas[arm] += (1 - reward)15    return alphas[arm] / (alphas[arm] + betas[arm])16
17
18alphas, betas = [3.0, 18.0, 2.0], [9.0, 6.0, 2.0]19draws = sample_round(alphas, betas, 4)20print([f"{d:.3f}" for d in draws])  # -> ['0.179', '0.481', '0.729']21print(max(range(3), key=lambda i: draws[i]))  # -> 222print(f"{update(alphas, betas, 2, 1):.2f}")  # -> 0.60

The printout matches the hand arithmetic: Arm 3 (index 2) wins the draws and its mean moves from $0.50$ to $0.60$ after the success.

Watch Out For

A Gaussian belief on a rate between 0 and 1

Conversion rates live in $[0, 1]$ , but a Gaussian belief has infinite tails. Symptom: the sampler draws negative "probabilities" or values above 1, which either crash the argmax or silently bias traffic toward arms whose tails leak furthest. With small rates near $0.005$ , the symmetric Gaussian also mangles the true skew.

Match the belief to the outcome type: Beta-Bernoulli for binary rewards, and the matching conjugate pair for anything else. If you must approximate with a Gaussian, clip or squash the draws and say so, because unclipped Gaussian Thompson sampling on rates is a different algorithm than the one with the guarantees.

Batching updates while feedback is still in flight

In production, conversions land hours after the impression, so posteriors update in batches. Symptom: the same stale belief serves thousands of impressions between updates, and a full batch of traffic pours into an arm that fresher data would already have demoted.

Count the in-flight exposures. Penalize arms with many pending outcomes (virtual counts or a conservative posterior) until their feedback lands, and shorten the batch window as far as the pipeline allows. If most of your pulls come from beliefs older than your feedback delay, the batching is the algorithm now, not the sampling.

The Quick Version

Thompson sampling draws one sample per arm from its posterior belief and pulls the highest draw, picking each arm with the probability it is best.
Beta beliefs with binary rewards update by counting: add 1 to alpha per success and 1 to beta per failure, with no integration.
Wide beliefs explore on their own: a 2-and-2 arm at mean 0.50 beats a 24-pull arm at 0.75 whenever its draw lands higher, as the 0.729 over 0.481 round shows.
Tight beliefs exploit on their own: proven winners win most draws and their means barely move per outcome, 0.75 to 0.76 on a success.
Rate outcomes need Beta beliefs, not Gaussians, whose tails leak outside 0 and 1 and distort small conversion rates.
Under delayed feedback, discount arms with outcomes still in flight, or stale batches will spend the budget the fresh posterior would have saved.