Multi-Armed Bandit
- Definition
- The Multi-Armed Bandit formalizes the exploration-vs-exploitation trade-off in a simplified one-step setting: choose among several options with unknown rewards and learn which is best. Think of many slot machines (arms) where you must balance trying new arms against exploiting the best-known one. It differs from full RL because there is no state transition — decisions are single-step but capture the core challenge of learning under uncertainty.
How does it work?
Multi-Armed Bandit operates by interacting with an environment: observe state, choose action, receive reward, and update a policy or value estimator. Practical implementations must balance exploration and exploitation and handle credit assignment across time via bootstrapping or Monte Carlo returns.
Examples
- Ad selection — Balance exploration and exploitation to pick which ad variant to show to maximise clicks.
- Clinical trial allocation — Adaptively assign treatments to patients to improve outcomes while learning efficacy.
- News recommendation — Serve articles while learning click rates with contextual bandit algorithms.
Problems
- Balancing exploration and exploitation without over/under-exploring
- Non-stationary reward distributions breaking standard assumptions
- Scaling poorly with a very large number of arms
- Choosing the right algorithm variant (UCB, Thompson sampling, epsilon-greedy) for the context