多臂老虎机 MAB

多臂老虎机 (Multi-Armed Bandit, MAB) 是单状态、无状态转移的在线决策问题:每轮从 $K$ 个臂中选择一个动作 $a_t$,获得随机奖励 $r_t$(如 Bernoulli 点击 $r_t \sim \text{Bernoulli}(\mu_{a_t})$)。核心指标是 regret(遗憾):$R_T = T\mu^* - \mathbb{E}[\sum_{t=1}^T \mu_{a_t}]$,其中 $\mu^* = \max_a \mu_a$ 是最优臂的期望奖励,即累计奖励相比"每轮都玩最优臂"的期望差距。

推荐/广告的流量分配与物料冷启动、A/B 测试的在线替代、AutoML 超参搜索、临床试验;面试中常作为"单状态 RL"对比 Q-Learning 的切入点,引出探索-利用权衡 (exploration-exploitation)。

静态 A/B 测试按固定比例分配流量,劣方案浪费大量样本;MAB 根据实时反馈动态调整选择概率,以接近最优臂的频率玩好臂,UCB/Thompson 采样可达最优的 $O(\ln T)$ regret(一般算法为 $O(\sqrt{T})$ 量级),相同预算下累计收益显著高于均匀/随机分配。

检验攻克程度：针对「多臂老虎机 MAB」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。