Flight log / Transmission 032

Multi-armed bandits, explained like an arcade cabinet

A row of machines, a pocket of quarters, and no idea which one pays out best. In a 2013 simulation published by Google, a bandit reached a call in 66 days where a classic A/B test needed 223.

The name comes from slot machines, nicknamed one-armed bandits. Picture a wall of them, each with a different hidden payout rate. You can only learn a machine's rate by feeding it quarters. Every quarter spent learning is a quarter not spent on the best machine you've found so far.

Swap machines for landing page variants and quarters for visitors, and you have the oldest tension in testing: learn more, or earn more. Bandits try to do both at once. Here's how, and when they shouldn't be invited.

What is a multi-armed bandit?

A multi-armed bandit is a class of problems, and the algorithms that solve them, where you repeatedly choose between options with unknown payoffs and learn from each result. It gets the first technical chapter of Sutton and Barto's standard reinforcement learning textbook, because it's learning by trial and error in its simplest form.

In marketing, the "arms" are variants: two headlines, three offers, four ad creatives. The "payout" is a conversion. A bandit decides, visitor by visitor or batch by batch, which variant to show next based on what it has seen so far.

A classic A/B test does the opposite. It splits traffic evenly, holds that split until a planned sample size, and only then reads the result. Patient, rigid, expensive, clean. If you need a refresher on that side, start with landing page testing without lying to yourself.

What does explore vs. exploit mean?

Every allocation decision is a trade between two goals:

• Explore: send traffic to options you're unsure about, to learn their true rate.
• Exploit: send traffic to the option that looks best right now, to earn conversions.

The Russo et al. tutorial on Thompson sampling frames it as balancing "exploiting what is known to maximize immediate performance" against "investing to accumulate new information." Explore too little and you lock onto an early fluke. Explore too much and you keep paying for a variant you already know is worse.

The bill for exploring has a name: regret, the conversions you gave up by not always showing the best option. A classic A/B test accepts a lot of regret in exchange for a clean measurement. A bandit tries to keep regret low while still finding the winner.

How does epsilon-greedy work?

Epsilon-greedy is the simplest bandit strategy and a staple of introductory texts. Pick a small number, epsilon, say 10%. Then for each visitor:

1. 90% of the time, show the variant with the best observed conversion rate so far.
2. 10% of the time, show a variant chosen at random.

Hypothetical: three headlines, 10,000 visitors. Under epsilon-greedy at 10%, roughly 9,000 visitors see whichever headline is leading, and roughly 1,000 are spread across all three at random so the method can notice if the leader was a fluke.

A common fix decays epsilon over time: explore heavily early, less as evidence builds. Better, but now someone has to pick the decay schedule, and that someone is usually guessing.

What is Thompson sampling?

Thompson sampling is smarter about where it explores. It was first proposed in 1933, and it also goes by posterior sampling and probability matching. The high-level version:

1. Keep a belief, a probability distribution, for each variant's true conversion rate. Few visitors means a wide belief; many visitors means a narrow one.
2. For each visitor, draw one plausible rate from each variant's belief.
3. Show the variant whose draw came out highest.
4. Update that variant's belief with the result. Repeat.

The result: a variant gets traffic roughly in proportion to the probability that it's the best one. Uncertain variants occasionally draw high and get explored. Variants that are clearly worse almost never win a draw, so they fade out on their own instead of collecting a fixed share forever.

If the word "belief" sounds familiar, it should: this is Bayesian reasoning applied to allocation. The Bayesian vs. frequentist guide covers the underlying idea.

Multi-armed bandit vs. A/B test: which should you use?

How much faster is a bandit than an A/B test?

Depends on the setup, so treat any single number as an illustration, not a promise. The best-documented public example comes from Steven L. Scott, then a senior economic analyst at Google, writing on the Google Analytics blog in January 2013.

• The setup: an original converting at 4% vs. a variation converting at 5%, with 100 visits per day.
• The result: the classical test needed 22,330 visits, or 223 days. In the featured run, the bandit finished in 66 days.
• Across 500 simulations: the bandit ended 175 days sooner and saved 97.5 conversions per experiment on average, and picked the correct arm in 482 of 500 runs (96.4%).
• The guardrails: traffic was reallocated twice a day, not per visitor, and the bandit was forced to run at least two weeks by default.

Note what that simulation assumes: conversion rates that never drift and conversions that are recorded right away. Paid B2B traffic rarely gives you either, so expect the real-world gap to be smaller and messier.

When is a multi-armed bandit the wrong tool?

Bandits are good at exactly one thing: picking well while you pick. Ask them for anything else and they get shaky.

• You need to know how big the lift is. A bandit starves losing variants of traffic, so its estimate of the gap is imprecise. If the result goes in a board deck or shapes next year's page strategy, run a proper A/B test.
• Conversions arrive late. If the metric that matters is a qualified lead or opportunity that shows up two weeks after the click, the bandit allocates on early, partial data. It may reward the variant that converts fast, not the one that converts well.
• Performance swings by day or season. Thompson sampling's exploration shrinks toward zero as it settles on a winner, and Russo et al. note it can stop exploring in environments that change. If Monday traffic behaves differently from Saturday traffic, early allocation can lock in a weekday quirk.
• Your traffic mix moves. When allocation shifts over time and your channel mix shifts too, the variant that got more traffic during a strong week can look better than it is.
• You only have two variants and plenty of time. The regret savings are smallest here, and the clean read of a fixed test is worth more.

Where bandits do fit: short-lived decisions like a limited-time offer or seasonal headline, many variants where you want to drop weak ones fast, and cases where every lost conversion during the test is genuinely expensive.

What should you decide before running a bandit?

Bandits feel hands-off. That's the trap: all the judgment moves to before launch. Answer these in writing first:

Where this breaks

The math is solid. The plumbing is where it leaks:

• Small B2B samples. With a few dozen conversions a month, every method is guessing. A bandit just guesses with more confidence in the leader than the data may support.
• The metric choice is the whole game. A bandit optimizes exactly what you feed it. Feed it form fills and it will happily favor whatever produces the most form fills, junk included.
• Minimum run times still apply. Even Google's 2013 implementation forced a two-week minimum by default. Cover full weekly cycles before trusting any allocation, as covered in how long to run an A/B test.

FAQ