Multi-Armed Bandits and Thompson Sampling
By the end of this lesson, you should be able to: explain Thompson sampling in three sentences, say what a bandit optimises and what it gives up, name the two conditions it needs, and choose between a bandit and an experiment based on the question.
The cost of a fair split
An A/B test with four versions sends a quarter of users to each until the end, including the versions that are clearly losing halfway through. Every user sent to a loser is a sale you could have had.
Steven Scott, a statistician at Google, put the economics plainly in 2015: for online experiments, the cost of experimenting is dominated by this opportunity cost, the value lost by showing people worse versions, rather than by the cost of getting users. A multi-armed bandit is designed to cut that cost. It shifts traffic as it goes: the more a version looks like the winner, the more users it gets. The name comes from a gambler choosing between slot machines ("one-armed bandits") with unknown payouts.
Thompson sampling
The version worth knowing is Thompson sampling, first proposed by William Thompson in 1933 for choosing between treatments in medicine. It's three sentences:
- Keep a posterior for each version's conversion rate: the Beta distribution from Bayesian A/B testing.
- For each user, draw one random value from each version's posterior, and show the version whose draw came out highest.
- Update that version's posterior with what the user did.
There's no exploration setting to tune. A version gets traffic in proportion to the probability that it's the best one, and that falls out of the random draws. A version that might be best still gets tried; one that almost certainly isn't stops getting traffic.
In 2011, Olivier Chapelle and Lihong Li at Yahoo! tested it on simulated data and on real display-ad and news-recommendation data. They called it "one of oldest heuristic" for the trade-off between exploring and exploiting, found it "highly competitive", and argued it should be a standard baseline.