The multi-armed bandit problem: choose repeatedly between options with unknown payoffs, balancing learning with earning.
The Name
Imagine slot machines ("one-armed bandits") with different payout rates. You want to find the best while losing as little as possible along the way.
Common Strategies
- Epsilon-greedy: usually pick the best-known option; occasionally explore at random.
- Upper confidence bound (UCB): favour options with high potential given uncertainty.
- Thompson sampling: choose options in proportion to the probability that each is best — effective and widely used.
Versus A/B Testing
A/B tests split traffic evenly and decide at the end, maximising learning. Bandits shift traffic to winners during the experiment, reducing the cost of showing worse options — but give less precise estimates.
Good Uses
- Headline and creative optimisation.
- Recommendations and promotions.
- Situations with many options or short-lived content.
Contextual Bandits
Use information about the user or situation to choose, personalising decisions.
Cautions
Bandits can lock onto early winners if rewards change over time; use methods that handle non-stationary rewards.