Every decision system eventually faces the same problem. There are actions whose value you don’t know well: a new offer, a new price point, a message nobody has tried. To find out, you have to take them. But each time you take an action that turns out to be worse, you lose a little. Each time you stick with the current best, you learn nothing about the alternatives.
This is the explore-exploit trade-off, and the classic model of it is the multi-armed bandit: a gambler facing several slot machines with unknown payout rates, trying to win as much as possible over many pulls.
The setup
At each round t, the decision maker picks an arm (action) a, and receives a reward r drawn from that arm’s unknown distribution. The goal is to maximize total reward. Performance is measured by regret: the reward you’d have earned always playing the best arm, minus what you actually earned. Good algorithms have regret that grows slowly (logarithmically) over time: they stop playing bad arms quickly.
In business terms: arms are offers, prices, subject lines, ranking variants; rewards are conversions, retention, margin. Regret is money left on the table while you learn.
Three algorithms
Epsilon-greedy. With probability ε, pick a random arm; otherwise pick the arm with the best observed average. Simple, easy to explain, and a reasonable baseline. Its weakness: it keeps exploring obviously bad arms at the same rate forever, and treats an arm tried twice the same as one tried ten thousand times.
UCB1 (upper confidence bound). Pick the arm with the highest optimistic estimate: its mean plus a bonus that shrinks as the arm gets tried more. “Optimism in the face of uncertainty”: uncertain arms get a chance to prove themselves, then the bonus fades.
Thompson sampling. Keep a posterior distribution over each arm’s value. Each round, draw one sample from each posterior and play the arm with the highest sample. For yes/no rewards, a Beta posterior per arm makes this a few lines:
import numpy as np
class ThompsonBernoulli:
"""Beta-Bernoulli Thompson sampling. One Beta(a, b) per arm."""
def __init__(self, arms, prior=(1.0, 1.0)):
self.arms = list(arms)
self.a = {k: prior[0] for k in self.arms} # successes + prior
self.b = {k: prior[1] for k in self.arms} # failures + prior
self.rng = np.random.default_rng()
def choose(self, eligible=None):
cand = eligible or self.arms
samples = {k: self.rng.beta(self.a[k], self.b[k]) for k in cand}
return max(samples, key=samples.get)
def propensities(self, eligible=None, n=2000):
# P(each arm is chosen) = P(its sample is the max).
# Not available in closed form; estimate by simulation and LOG IT.
cand = eligible or self.arms
draws = np.column_stack([self.rng.beta(self.a[k], self.b[k], n) for k in cand])
wins = np.bincount(draws.argmax(axis=1), minlength=len(cand)) / n
return dict(zip(cand, wins))
def update(self, arm, reward):
self.a[arm] += reward
self.b[arm] += 1 - rewardThompson sampling plays each arm with probability equal to the posterior probability that it’s the best. It’s near-optimal in theory, consistently strong in practice, and easy to extend with priors from business knowledge (for example, start a new offer’s prior near the conversion rate of similar offers). It’s the default choice for most production bandits.
Bandit or A/B test?
They answer different questions:
- An A/B test keeps allocation fixed (say 50/50) to measure the difference between variants precisely, with standard statistical guarantees. During the test, half the traffic gets the worse variant.
- A bandit shifts traffic towards better-performing arms as evidence accumulates, earning more during the experiment but measuring the losing arms less precisely.
Use a bandit when the goal is to earn while learning: many variants, short-lived content (headlines, promotions), continuous optimization. Use an A/B test when you need a defensible estimate for a decision with long-term consequences, or when effects take a long time to appear. A common hybrid: A/B test the big strategic choice, bandit-optimize the tactical variants within the winner.
Production details that make or break bandits
The textbook bandit gets an immediate reward after every pull, in an unchanging world. Production is messier.
Delayed rewards. A retention outcome takes 90 days. A bandit updating on it learns very slowly, and makes thousands of decisions on stale beliefs. Options: use a leading proxy (engagement in the next 14 days), validated to correlate with the true outcome on historical data; or model the delay explicitly by treating pending outcomes as partially observed. Be careful with proxies: a bandit will optimize exactly what you reward, including the proxy’s flaws.
Batching. Most systems don’t update after every decision. They decide in batches (the monthly offer run) or update posteriors hourly. Thompson sampling handles batching gracefully because its randomization naturally spreads a batch across plausible arms. Greedy methods put the whole batch on one arm.
Non-stationarity. Offer effectiveness drifts with seasons, competitors and fatigue. A bandit that remembers everything forever converges and stops adapting. Use discounting (multiply old counts by a factor like 0.99 per day) or a sliding window, so old evidence fades.
Exploration floors and ceilings. Business owners are nervous about bandits sending a big share of traffic to an untested arm, and about any arm getting zero traffic. Clip propensities to a range, for example each eligible arm gets between 2% and 80%. Floors keep learning alive and keep propensities away from zero, which matters for evaluation. Ceilings cap downside while the bandit is uncertain.
Eligibility first. The bandit should only ever choose among actions the rules layer allows for that unit. Exploration never overrides policy.
Log propensities. Every decision should record the probability with which the chosen arm was selected. Bandit data is adaptively collected: good-looking arms get more traffic, so naive averages are biased. Inverse-propensity methods (Lesson 15) correct for that, but only if you logged the propensities at decision time. You can’t reconstruct them later.
Guard the reward pipeline. A bug that marks every reward as 1 for one arm will make the bandit pour traffic into it within hours. Monitor reward rates per arm and alert on sudden jumps.
Where plain bandits stop
A multi-armed bandit learns which arm is best on average. But the best retention offer for a long-tenured annual subscriber is probably different from the best one for a new monthly user. Treating everyone the same leaves value on the table. The next lesson adds context: bandits that learn which action is best for whom.