Bandits in production: Thompson sampling, explained with coupons

Say you have three discount coupons and want to know which one gets the most people to buy. The textbook answer is an A/B test: split traffic evenly, wait until the result is significant, then ship the winner. It works, but for the whole test a third of your users see each losing coupon, even after the data has made it fairly obvious they’re losing.

A multi-armed bandit handles that by moving traffic toward what’s working while the test is still running. On the experimentation platform I worked on, we ran bandits for exactly this kind of problem, coupon optimisation and adaptive traffic allocation, using Thompson sampling. This post explains the algorithm with coupons, then shows how we fitted it into a production system.

Explore or exploit

Every bandit balances two needs. Exploiting means showing the coupon that looks best so far, to earn conversions now. Exploring means still showing the others sometimes, because “looks best” is based on limited data and might be wrong. Pure exploitation locks in an early lucky guess; pure exploration is just an A/B test. Thompson sampling gets the balance from how uncertain it is about each coupon.

Thompson sampling in one picture

For each coupon, keep two numbers: how many people saw it and how many converted. Those two numbers define a Beta distribution, the bandit’s belief about that coupon’s true conversion rate, here the share of people who buy after seeing it. Little data gives a wide curve; lots of data gives a narrow one.

What the bandit believes after some traffic. Each curve is a Beta distribution over a coupon's true conversion rate. C has little data, so its curve is wide and it still wins some draws. Probability of being best: B 58%, C 38%, A under 5%.

The whole algorithm is: for each user, draw one random value from each coupon’s curve, and show the coupon with the highest draw.

import random

def choose(stats):
    # stats: {"A": (conversions, views), ...}
    draws = {
        coupon: random.betavariate(1 + conv, 1 + views - conv)
        for coupon, (conv, views) in stats.items()
    }
    return max(draws, key=draws.get)

That’s enough to get the balance right. A coupon with a high, narrow curve wins most draws, so it gets most of the traffic. A coupon with a wide curve sometimes draws high, so it still gets explored until the data settles what it’s worth. A coupon with a low, narrow curve almost never wins. Nobody has to tune an exploration rate; uncertainty does the work.

Sampling per request, or in batches

The textbook version draws per user, updates the counts after every conversion, and draws again. Ours ran differently: the bandit was a batch job that edits a traffic split. Batching like this has real advantages over per-request sampling:

Purchases arrive late. Someone who sees a coupon might buy hours later. Updating per request would mostly update on “no purchase yet”.
Users see consistent variants. Drawing per request could show the same person a different coupon on every page.
The request path stays simple. Assignment is a hot, latency-sensitive service that already knows how to assign users by a traffic split.

Every few hours, the job recomputed each coupon’s posterior from logged exposures and conversions, estimated the probability that each coupon is the best, and wrote those probabilities back as the experiment’s new traffic split.

def split_from_posteriors(stats, draws=10_000):
    wins = {coupon: 0 for coupon in stats}
    for _ in range(draws):
        wins[choose(stats)] += 1
    return {coupon: n / draws for coupon, n in wins.items()}

Allocating traffic in proportion to “probability of being best” is exactly what Thompson sampling does on average, just applied in batches. The new split then travels to the assignment service like any other config change, which is why the config delivery work mattered: bandits were among the most frequent writers.

The loop in production. Nothing in the request path samples anything: the bandit is a batch job that edits the traffic split, and the split travels to the assignment service like any other config change.

What it looks like over time

Here is a simulated run, with the true conversion rates set to 6%, 10% and 7.5%, and a few hundred users between updates:

A simulated run with true rates of 6%, 10% and 7.5%. The split starts even, wavers between B and C while C's curve is still wide, then settles on B. A 5% floor keeps the losers in the test.

The early updates are the interesting part. After the first batch, B and C look about equally good and split the traffic between them. As C collects more data its curve narrows below B’s, and traffic moves to B. A drops out almost immediately.

The payoff is measured as regret: conversions lost compared with already knowing the best coupon.

Regret: conversions lost compared with a world where you already knew the best coupon. A fixed split keeps paying for its losers at the same rate; the bandit stops paying once it's confident.

Both lines start the same, because both begin with an even split. After that, the fixed split keeps losing conversions at the same rate until the test ends, while the bandit’s losses flatten once it’s confident.

What production adds

The algorithm is ten lines. Most of the work is everything around it:

Define the reward carefully. A bandit optimises exactly what you give it. Our reward was a purchase, not a click on the coupon: the two can favour different coupons. The window for counting a purchase matters too; too short, and it under-counts people who take a while to decide.
Keep a floor. If a losing variant’s share can reach zero, the bandit can never notice that it has improved. A small minimum share keeps every arm observable.
Expect the world to change. Coupon performance drifts with seasons, weekdays and campaigns. Old data can be discounted, or the counts computed over a recent window, so the bandit can change its mind.
Decide what happens when the split moves. If users are hashed into buckets by split, changing the split moves some users between variants. Either that’s acceptable for the product, or first assignments need to be stored.
Don’t use it to measure. A bandit is built to earn while it learns, not to produce a clean estimate of the difference between variants. Because the losing arms get little traffic, their estimates stay noisy, and adaptive allocation biases naive confidence intervals. If the question is “how much better is B, and is it significant?”, run an A/B test.

When to reach for a bandit

Use an A/B test when you need to learn: a product decision, an effect size, something you’ll report. Use a bandit when you need to earn while choosing among options with fast, measurable feedback: coupons, banners, notification copy, ranking tweaks. If the options change often, or the test would otherwise run for weeks while showing users a clearly worse option, a bandit usually pays for itself.

References

Thompson, W. R. On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 1933. https://doi.org/10.1093/biomet/25.3-4.285 — the original idea.
Russo, D. et al. A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning, 2018. https://arxiv.org/abs/1707.02038
Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, 2020. https://www.cambridge.org/core/books/bandit-algorithms/8E39FD004E6CE036680F90DD0C6F09FC
Chapelle, O. and Li, L. An Empirical Evaluation of Thompson Sampling. Advances in Neural Information Processing Systems 24 (NIPS), 2011. https://papers.nips.cc/paper/2011/hash/e53a0a2978c28872a4505bdb51db06dc-Abstract.html
Agrawal, S. and Goyal, N. Analysis of Thompson Sampling for the Multi-armed Bandit Problem. arXiv, 2011 (rev. 2012). https://arxiv.org/abs/1111.1797 — regret bounds.
Nie, X. et al. Why Adaptively Collected Data Have Negative Bias and How to Correct for It. AISTATS, 2018. https://arxiv.org/abs/1708.01977