多臂老虎机 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})$ 量级),相同预算下累计收益显著高于均匀/随机分配。

写出 regret 定义并解释每一项:为何用最优臂期望 $\mu^*$ 而非实际收益?

数值题:3 臂 $\mu=(0.8, 0.5, 0.3)$, 玩 100 轮, 臂1 被选 60 次、臂2/3 各 20 次, 计算 regret?

MAB 与完整 RL (MDP) 的差别?MAB 如何从 MDP 退化而来?

ε-greedy、UCB、Thompson 采样各自的核心思想与 regret 量级?

regret 下界:为什么任何算法的 worst-case regret 至少是 $\Omega(\sqrt{KT})$?