Multi-Armed Bandit (MAB)

The Multi-Armed Bandit (MAB) is a single-state, no-state-transition online decision problem: at each round pick an action $a_t$ among $K$ arms and observe a stochastic reward $r_t$ (e.g., Bernoulli click $r_t \sim \text{Bernoulli}(\mu_{a_t})$). The core metric is regret: $R_T = T\mu^* - \mathbb{E}[\sum_{t=1}^T \mu_{a_t}]$, where $\mu^* = \max_a \mu_a$ is the best arm's mean — the expected gap between your total reward and always playing the optimal arm.

traffic allocation and cold-start in recsys/ads, an online alternative to A/B testing, AutoML hyperparameter search, clinical trials; in interviews it is the entry point for "RL with a single state" and the exploration-exploitation trade-off vs Q-Learning.

static A/B testing wastes samples on inferior variants via fixed split ratios; MAB adaptively shifts traffic toward good arms from live feedback, achieving the optimal $O(\ln T)$ regret with UCB/Thompson sampling (vs $O(\sqrt{T})$ in general), delivering significantly higher cumulative reward than uniform/random allocation under the same budget.

Test Your Knowledge: Practice Questions for "Multi-Armed Bandit (MAB)"

Single choice pitfall questions with instant feedback and mistake tracking.