The Multi-Armed Bandit Problem
What you'll learn: How the multi-armed bandit problem formalizes the exploration-exploitation tradeoff as a simplified reinforcement learning scenario.
The Classic Slot Machine Analogy
Imagine standing in a casino facing a row of slot machines (called "one-armed bandits"). Each machine has a different, unknown probability of paying out. You have a limited budget of coins. Which machines do you play, and when?
This is the multi-armed bandit problem: you must decide between exploiting the machine that seems best so far (to maximize immediate reward) or exploring other machines (to potentially discover better options).
The Bandit Formulation
In the bandit setting:
- You face
kactions (arms/machines) - Each action has an unknown reward distribution
- At each time step, you choose one action and receive a reward sampled from its distribution
- Your goal: maximize cumulative reward over time
Unlike full MDPs, bandits have:
- No states – the environment doesn't change
- No sequential consequences – pulling one arm doesn't affect future options
- Pure focus on the exploration-exploitation tradeoff
Why Bandits Matter
Bandits isolate the core challenge you've been studying: should your agent exploit what it knows (greedy, epsilon-greedy) or explore uncertainties (UCB, Thompson sampling)? They're used in:
- A/B testing and online advertising
- Clinical trials
- Recommendation systems
- Hyperparameter tuning
By mastering bandits, you understand the foundation of exploration strategies before adding the complexity of state transitions and long-term planning.
Key Takeaway: The multi-armed bandit problem strips RL down to its essence—balancing exploration and exploitation without states—making it the perfect testbed for understanding action selection strategies.