multi-armed bandit
**Multi-Armed Bandit** is a **sequential decision-making framework that formalizes the exploration-exploitation tradeoff, where an agent repeatedly selects from K unknown reward distributions (arms) to maximize cumulative reward** — providing the mathematical foundation for A/B testing, clinical trials, recommendation systems, and online advertising through algorithms that systematically balance learning about uncertain options with exploiting the best-known choice.
**What Is the Multi-Armed Bandit Problem?**
- **Definition**: A sequential decision problem with K arms, each yielding stochastic rewards from an unknown distribution; the agent pulls one arm per round and observes only that arm's reward, aiming to maximize cumulative reward over T rounds.
- **Exploration-Exploitation Tradeoff**: Exploitation means pulling the empirically best arm; exploration means pulling other arms to learn whether they might be better — balancing these is the core algorithmic challenge.
- **Regret Framework**: Performance measured by cumulative regret R(T) = T·μ* - Σ E[r_t], where μ* is the best arm's mean reward; optimal algorithms achieve O(log T) regret — sublinear in T.
- **Stochastic vs. Adversarial**: Stochastic bandits assume fixed reward distributions; adversarial bandits allow an adversary to choose rewards after seeing the algorithm — requires EXP3 and related algorithms.
**Why Multi-Armed Bandits Matter**
- **A/B Testing Acceleration**: Bandit algorithms adaptively allocate traffic to better-performing variants, reducing experimentation cost compared to fixed equal-split A/B tests.
- **Personalization**: Contextual bandits enable per-user recommendation by conditioning arm selection on user features — foundational in Netflix, Spotify, and e-commerce personalization.
- **Clinical Trial Efficiency**: Response-adaptive randomization routes more patients to effective treatments during the trial — both ethical and statistically efficient.
- **Online Advertising**: Real-time bidding selects ads to maximize click-through or revenue; bandit algorithms learn which ads perform best for each context without offline training.
- **Hyperparameter Optimization**: Successive Halving and Hyperband use bandit principles to allocate compute budget to promising hyperparameter configurations.
**Core Algorithms**
**ε-Greedy**:
- With probability ε, select random arm; with probability 1-ε, select empirical best arm.
- Simple but inefficient — explores all arms equally regardless of estimated quality.
- Standard baseline; works well with small K and sufficient T; widely used in production for its simplicity.
**Upper Confidence Bound (UCB)**:
- Select arm i with highest UCB_i = μ̂_i + √(2 log t / n_i) where n_i is the pull count.
- "Optimism in the face of uncertainty" — preferentially explore uncertain but potentially high-reward arms.
- Achieves optimal O(log T) regret; no hyperparameter tuning required — purely data-driven.
**Thompson Sampling**:
- Maintain Bayesian posterior over each arm's mean reward; sample from posteriors; pull arm with highest sample.
- Provably optimal regret; naturally balances exploration and exploitation through posterior uncertainty.
- Easy to extend to contextual settings with Bayesian linear regression or neural networks.
**Algorithm Extensions**
| Variant | Description | Application |
|---------|-------------|-------------|
| **Contextual Bandits** | Rewards depend on context features | Personalized recommendations |
| **Combinatorial Bandits** | Select subset of arms per round | Slate recommendations |
| **Restless Bandits** | Arm distributions change over time | Dynamic environments |
| **Cascading Bandits** | User clicks first satisfying item | Search result ranking |
Multi-Armed Bandit is **the rigorous framework for intelligent experimentation under uncertainty** — enabling systems to learn and optimize simultaneously rather than sequentially, replacing wasteful fixed-allocation A/B tests with adaptive algorithms that maximize cumulative reward while systematically minimizing the cost of learning which options are best.