The multi-armed bandit problem: you have several options (“arms”) with unknown reward rates, and a sequence of choices to make. Each choice gives information, but also incurs the cost of not having chosen better.
The trade-off
- Exploit: choose the option that currently looks best. Earns now, but you might be wrong.
- Explore: choose an option you are unsure about. Earns less now, but improves future choices.
A fixed 50/50 split ignores this trade-off. A bandit algorithm resolves it explicitly.
Regret
The standard way to evaluate a bandit strategy is regret: the cumulative difference between the rewards you got and the rewards you would have got by always choosing the best arm.
- Equal split → regret grows linearly with the number of visitors: you pay the gap on every one.
- Thompson Sampling → regret grows logarithmically, which is the best achievable in the general case.
In advertising
Each landing page variant is an arm; each visitor is a choice; the reward is a lead. This is why bandit allocation fits traffic better than fixed-sample testing — see Thompson Sampling.
Related terms
- Thompson Sampling — the algorithm
- A/B testing — the classical alternative