Multi-Armed Bandits
Bandit algorithms balance exploring uncertain options against exploiting the best-known one to maximize cumulative reward.
The explore-exploit dilemma
A multi-armed bandit is a decision problem where an agent repeatedly chooses among options (arms), each returning a random reward from an unknown distribution, and wants to maximize total reward over time. The tension is fundamental: exploit the arm that looks best so far, or explore others that might be better but are less certain. Pure exploitation can lock onto a suboptimal arm; pure exploration wastes pulls.
Core algorithms
- Epsilon-greedy: pick the best-known arm most of the time, a random arm with probability epsilon
- Upper Confidence Bound: pick the arm with the highest optimistic estimate, mean plus an uncertainty bonus that shrinks with pulls
- Thompson sampling: keep a posterior over each arm reward, sample from each, and play the arm with the highest sample
UCB and Thompson sampling both formalize optimism under uncertainty and enjoy strong regret guarantees, meaning the gap to always playing the best arm grows only logarithmically with time.
Regret as the yardstick
Performance is measured by regret: the difference between the reward the best fixed arm would have earned and what the algorithm actually earned. Sublinear regret means the average per-round loss vanishes over time, which is the goal. Regret framing separates good exploration schedules from ones that explore too much or too little.
Contextual bandits and uses
Contextual bandits add features describing the situation before each choice, so the best arm depends on context, bridging bandits and supervised learning. This powers news and content recommendation, ad selection, and adaptive experimentation, where classic A/B testing wastes traffic on losing variants. Bandits also inform query selection in active learning and connect to the broader field of reinforcement learning.