Thompson Sampling

Thompson sampling is a decision rule for the multi-armed bandit problem — the challenge of repeatedly choosing among several options whose payoffs are unknown, learning as you go. Named after William R. Thompson, who described it in 1933, it takes a Bayesian view. For each option, or 'arm,' it holds a probability distribution representing its current belief about that arm's reward rate. On every round it draws one random sample from each arm's distribution and plays the arm whose sample came out highest. Then it observes the result — a click, a conversion, a reward — and updates that arm's distribution to reflect the new evidence. Over many rounds the distributions sharpen, the better arms get sampled high more often, and traffic naturally flows to the winners while still occasionally testing the rest.

The elegance is that the exploration is built in, not bolted on. Because each choice comes from a random draw, an arm the algorithm is still unsure about — one with a wide distribution — will sometimes produce a high sample and get played, giving it a chance to prove itself. An arm the algorithm is confident is weak has a narrow, low distribution and rarely wins a draw, so it is quietly starved of traffic. As evidence accumulates, uncertainty shrinks and the sampling concentrates on the genuinely best arm. This is why Thompson sampling is called a probability-matching method. It plays each arm roughly in proportion to the probability that it is the best. Marketers use it to allocate traffic across creatives, offers, or layouts without hand-tuning a schedule.

Thompson sampling is one of three well-known bandit strategies, and each explores differently. Epsilon-greedy is the bluntest. Most of the time it plays the arm with the best average so far, but with a fixed small probability — epsilon — it picks a random arm to explore. That works, but the exploration is undirected. It wastes pulls on arms already known to be poor just as readily as on promising ones. Upper Confidence Bound (UCB) is smarter. It plays the arm with the highest optimistic estimate, adding a bonus for arms it has tried less, so uncertainty itself drives exploration. Thompson sampling reaches a similar goal by a different route — randomized draws from Bayesian beliefs — and in practice it often matches or beats UCB while being simple to implement and naturally handling delayed or batched feedback.

The practical differences guide the choice. Epsilon-greedy is trivial to code and explains itself in a sentence, but its constant random exploration is inefficient and you must tune epsilon. UCB is deterministic and comes with strong theoretical guarantees, which appeals when you want provable behavior, but it can be sensitive to its tuning constant and to noisy rewards. Thompson sampling is randomized, adapts its exploration automatically as beliefs sharpen, and tends to be robust and sample-efficient in messy real-world settings — the reason many production experimentation systems favor it. Its one demand is a probability model for the rewards, typically a simple Beta distribution for click-or-convert outcomes. When you want hands-off, self-balancing allocation, Thompson sampling is usually the strongest default of the three.

Use Thompson sampling when you have many rounds, want to minimize regret — the reward lost by not always playing the best arm — and can update beliefs as results arrive. Pick a reward model that fits your outcome. A Beta distribution pairs naturally with binary conversion data, since it updates cleanly with each success or failure. Let the algorithm run long enough for the distributions to sharpen before you read too much into which arm is 'winning,' and feed it fresh data continuously so it can react to change. For binary metrics like conversion rate, it slots neatly into an experimentation platform and reallocates traffic on its own, steering toward the best creative or offer while still probing the others enough to catch a late bloomer.

The traps are real. Thompson sampling optimizes for reward, not for a clean, fixed-horizon statistical test, so if your goal is a rigorous A/B test with a preplanned sample size and p-value, a bandit is the wrong tool — it deliberately imbalances traffic. Non-stationary environments, where the best arm changes over time, can fool a naive implementation that never forgets old evidence, so use discounting or sliding windows so stale data does not anchor the beliefs. Delayed feedback needs care so the model is not updated on incomplete results. And a poorly chosen reward model gives poorly calibrated beliefs. Respect those limits and Thompson sampling is a powerful, self-tuning way to earn while you learn, converging on the best option with less wasted spend than a fixed split.

Thompson sampling is named for William R. Thompson, who proposed the idea in a 1933 paper on choosing between treatments, and it was revived decades later for online machine learning.

Etymology: source.

Search interest for this term over the last five years:

View interest-over-time on Google Trends →

Areas of marketing where thompson sampling is a core concern: