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.

Write the regret definition and explain each term: why use the best arm's mean $\mu^*$ instead of realized rewards?

Numerical: 3 arms with $\mu=(0.8, 0.5, 0.3)$; over 100 rounds arm1 is chosen 60 times, arms 2/3 20 each — compute the regret?

How does MAB differ from full RL (MDP)? How does it degenerate from an MDP?

Core ideas and regret orders of ε-greedy, UCB, and Thompson sampling?

Lower bound: why is any algorithm's worst-case regret at least $\Omega(\sqrt{KT})$?