Multi-Armed Bandits
The multi-armed bandit is the simplest reinforcement learning problem, isolating exploration versus exploitation with no state transitions.
One state, many arms
The multi-armed bandit is a stripped-down reinforcement learning problem. There is a single state and a set of actions (arms), each returning a random reward from an unknown distribution. The agent repeatedly picks an arm and observes its reward, trying to maximize total reward over many pulls. With no state transitions, it isolates the pure exploration-exploitation problem.
The regret objective
Performance is measured by regret: the difference between the reward the agent earned and the reward it would have earned always pulling the best arm. Good algorithms achieve regret that grows only logarithmically with the number of pulls, meaning the fraction of pulls wasted on suboptimal arms shrinks toward zero.
Core algorithms
- Epsilon-greedy: exploit the best-known arm, explore randomly a fraction of the time.
- Upper confidence bound (UCB): pick the arm with the highest optimistic estimate, value plus an uncertainty bonus.
- Thompson sampling: keep a posterior over each arm's reward and sample to decide, exploring in proportion to the chance an arm is best.
Contextual bandits
A contextual bandit adds an observed context (features) before each choice, so the best arm depends on the context, but there are still no transitions between states. This bridges bandits and full RL and underlies many recommendation and personalization systems.
Why study bandits
Bandits give clean theory and tight regret bounds that full MDPs rarely allow, and the exploration strategies developed here — UCB, Thompson sampling — carry directly into deep RL. They are the right mental model whenever choices give immediate feedback and do not change the situation the agent faces next.