Multi-Armed Bandits: Exploration in Its Purest Form#
Strip the MDP down to a single state and you get the multi-armed bandit: $K$ slot machines, unknown payout distributions, and one question — which arm do you pull next?
The dilemma#
- Exploit: pull the arm that looks best so far.
- Explore: pull other arms to reduce uncertainty about them.
Pure exploitation gets stuck on early luck; pure exploration wastes pulls forever. Every RL algorithm embeds some answer to this trade-off.
Three classic strategies#
| Strategy | Rule | Character |
|---|---|---|
| $\varepsilon$-greedy | Best arm with prob. $1-\varepsilon$, random otherwise | Simple, ubiquitous |
| UCB | Pull $\arg\max_a \hat\mu_a + c\sqrt{\ln t / N_a}$ | “Optimism in the face of uncertainty” |
| Thompson sampling | Sample from posterior of each arm, pick the best sample | Bayesian, strong in practice |
Science connection: adaptive experiment design is a bandit problem — each “arm” is an experimental condition, each “pull” costs beam time or reagents. Bayesian optimization is the continuous-armed cousin.
Deep dive: why optimism works
UCB adds a bonus proportional to $\sqrt{\ln t / N_a}$ — an upper confidence bound on
the arm's mean. Arms are pulled either because they are good (high $\hat\mu_a$) or
because they are uncertain (low $N_a$). Either way you learn something useful, which
yields regret growing only as $O(\ln t)$, matching the information-theoretic lower
bound up to constants.