第 2 课 · 多臂老虎机问题
对应《动手学强化学习》第 2 章 · 约 35 分钟（含动手实验）
1. 问题定义与形式化
有一台拥有 K 根拉杆的老虎机，每根拉杆对应一个未知的奖励概率分布。每次拉一根拉杆，就从对应分布获得奖励 r。目标是在操作 T 次后获得尽可能高的累积奖励。形式化为元组 ⟨A, R⟩：
- A：动作集合 {a₁, …, a_K}，一个动作 = 拉一根拉杆；
- R(r|a)：拉杆 a 对应的奖励概率分布，不同拉杆分布通常不同。
目标是 max Σt=1..T rt，其中 rt ~ R(·|at)。
累积懊悔（cumulative regret）
定义动作 a 的期望奖励 Q(a) = E[r]，最优期望奖励 Q* = max Q(a)。懊悔 R(a) = Q* − Q(a)，即"这一拉比拉最优拉杆差了多少（期望上）"。T 步决策的累积懊悔：
最大化累积奖励 ⟺ 最小化累积懊悔。懊悔增长越慢（次线性 < 线性）的算法越好。
增量式期望更新（贯穿全书的重要技巧）
拉第 k 次后更新估值：
不必存下所有历史奖励，时间与空间复杂度都是 O(1)。
2. 探索与利用的平衡
| 探索（exploration） | 利用（exploitation） |
|---|---|
| 尝试更多拉杆，摸清各拉杆获奖情况 | 拉当前已知期望奖励最大的拉杆 |
| 信息收益高，短期奖励可能低 | 短期奖励高，但可能错过真正最优拉杆 |
只利用不加探索（完全贪婪）会卡死在有限观测里的"局部最优"；只探索不利用则浪费拉杆次数。好的策略要在两者间平衡——常用思路是先多探索，估计准确后再多利用。
🎮 亲手试试：你来当智能体
3. ε-贪婪算法
每步以概率 1−ε 拉估值最大的拉杆（利用），以概率 ε 随机拉一根（探索）。固定 ε 时，每做一次随机探索产生固定懊悔，所以累积懊悔随时间线性增长。改进：让 ε 随时间衰减（如 ε=1/t），探索越来越少，累积懊悔变为次线性。
4. 上置信界（UCB）算法
基于不确定性：一根拉杆拉得越少，不确定性越大，越值得探索。由霍夫丁不等式可推出不确定性度量：
每次选择"期望奖励估值 + c·不确定性"最大（即期望奖励上界最大）的拉杆：
5. 汤普森采样（Thompson sampling）
为每根拉杆的获奖概率维护一个 Beta 分布：拉了 k 次中 m₁ 次获奖、m₂ 次未获奖，则分布为 Beta(m₁+1, m₂+1)。每步从各拉杆的 Beta 分布各采样一个值，选采样值最大的拉杆。拉得少 → 分布宽 → 采样值波动大 → 自然探索；拉得多 → 分布集中 → 自然利用。
6. 动手实验：在浏览器里复现书中结果
点击运行，比较各算法的累积懊悔曲线（10 臂伯努利老虎机，奖励为 0/1，T=5000，取多次实验平均）。你可以勾选/取消算法再运行多次——每次都会随机生成一台新的老虎机。
- 固定 ε 的算法：懊悔近似线性增长（ε 越大斜率越大）；
- ε 衰减、UCB、汤普森采样：懊悔次线性（对数级）增长——书中结论：ε-贪婪 ≈ 25.5，ε 衰减 ≈ 10.1，UCB ≈ 4.4。
检查你的理解
练习（书后习题方向）
① 用书中的 Solver 框架实现"每步随机拉杆"的纯探索策略，它的累积懊悔增长是线性还是次线性？
② 尝试 UCB 的系数 c=1 与 c=5，观察 c 如何影响探索-利用的平衡。
《动手学强化学习》第 2 章及完整代码：hrl.boyuai.com 第 2 章。理论深入可读 Auer 等人的 UCB 原始论文（Finite-time analysis of the multiarmed bandit problem, 2002）。
💡 有不懂的地方随时回到对话中问你的 AI 老师。