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

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.