第 171 题：探索与利用的多臂老虎机，UCB与Thompson Sampling的收敛速度？
题目
探索与利用的多臂老虎机，UCB与Thompson Sampling的收敛速度？
完整讲解
一、多臂老虎机与探索—利用权衡
多臂老虎机（MAB）：每轮选一个臂（动作）并得到随机奖励，目标在有限轮次内最大化累计奖励。探索：尝试信息不足的臂以获取更多信息；利用：选当前估计最优的臂以获取即时收益。二者需权衡。
二、UCB（Upper Confidence Bound）
- 思想：选「估计收益 + 乐观上界」最大的臂，即 $\mu_i + \sqrt{2\ln n / n_i}$（或变体），其中 $n$ 为总轮数、$n_i$ 为该臂被选次数。上界随尝试次数增加而缩小，自然平衡探索与利用。
- 收敛：在随机 MAB 下，UCB 的遗憾（与最优臂的累计收益差）为 $O(\log T)$，即渐近最优；常数依赖臂间差距。
三、Thompson Sampling（TS）
- 思想：为每个臂维护奖励分布的后验（如 Beta），每轮从各臂后验抽样得到样本，选样本最大的臂执行；观测到奖励后更新该臂后验。贝叶斯方式自然实现探索—利用。
- 收敛：在 Bernoulli 等常见设置下，TS 的遗憾也为 $O(\log T)$，且常数常优于 UCB；对上下文 Bandit 扩展自然（如 LinTS）。
四、收敛速度对比
- 二者均为对数遗憾，渐近等价；TS 在小样本时探索更平滑、工程上常更省调参；UCB 确定性、易分析。实际选型看场景（上下文、延迟反馈、可解释性）。
面试要点
- 能说清 MAB 的探索—利用权衡及 UCB、Thompson Sampling 的基本思想。
- 能写出 UCB 的选臂公式（估计+置信上界）及 TS 的「后验抽样→选最大」流程。
- 能说明二者收敛速度均为 $O(\log T)$ 遗憾，以及 TS 与 UCB 的适用场景差异。
记忆要点
- UCB：选估计+上界最大的臂，遗憾 $O(\log T)$；TS：后验抽样选最大，同样 $O(\log T)$。
- TS 贝叶斯、探索更平滑；UCB 确定性、易分析；二者渐近等价，按场景选型。