第 2 章 · 多臂赌博机：试探与开发
课程第 2 课 · 依据《强化学习（第 2 版）》第 2 章 · 约需 35–45 分钟
1. 评估性反馈 vs 指导性反馈
强化学习与其他机器学习最大的不同：训练信号是评估性的——只告诉你"刚才那个动作有多好"，而不告诉你"正确动作是什么"。
| 评估性反馈（RL） | 指导性反馈（有监督学习） | |
|---|---|---|
| 内容 | 当前采取的动作的好坏程度 | 应该选择的正确动作 |
| 是否依赖所采取的动作 | 依赖：选不同动作得到不同反馈 | 不依赖：无论你选什么，反馈相同 |
评估性反馈无法确定当前动作是不是所有可能中最好或最差的——这正是必须试探的原因。本章在"只有一个状态"的简化情形下研究它，即 k 臂赌博机问题。
2. k 臂赌博机问题（§2.1）
重复地在 k 个动作中选择，每次选择获得由该动作的平稳概率分布产生的收益，目标是一段时间内（如 1000 步）最大化总收益期望。名字源于有 k 个控制杆的老虎机。
动作 a 的真实价值：
我们不知道 q*(a)，只能维护估计值 Qt(a)，希望它接近真值。若知道每个动作的价值，问题就平凡了：每次都选价值最高的动作。
3. 动作-价值方法与 ε-贪心（§2.2）
自然的估计：采样平均法——用实际收益的平均值估计价值：
由大数定律，分母→∞ 时 Qt(a) 收敛到 q*(a)。选择规则两种：
- 贪心：At ≐ argmaxa Qt(a)——完全不试探，容易卡死在次优动作上；
- ε-贪心：以 1−ε 概率贪心，以 ε 概率从所有动作中随机等概率选。只要时间足够长，每个动作都被无限次采样，Q 收敛到真值，选中最优动作的概率收敛到大于 1−ε。
10 臂测试平台（§2.3）——亲手复现
书中的实验设置：2000 个随机生成的 10 臂赌博机，q*(a) ~ N(0,1)，收益 R ~ N(q*(A), 1)。下方模拟器完全按此设置在浏览器中运行，勾选算法后点击运行，对比"平均收益"和"选中最优动作的比例"两条曲线（对应书中图 2.2 / 2.4）：
观察要点（对照书图 2.2）：
- 贪心起步略快，但长期卡在约 1.0 的低收益，只在约 1/3 的任务中找到最优动作——最初采样不好就被锁死；
- ε=0.1发现最优动作早，但选中最优动作的比例上限只有 1−ε = 91%；
- ε=0.01改善慢，但 1000 步后两条曲线都反超 ε=0.1。
ε-贪心的优势依赖于任务：收益方差大（噪声多）时它远胜贪心；收益确定（方差 0）时贪心最好；任务非平稳（价值随时间变）时必须持续试探——而 RL 实际面对的常常是非平稳问题。
4. 增量式实现（§2.4）——贯穿全书的形式
不必存所有收益再求平均。记 Ri 为某动作第 i 次被选时的收益，可推出：
只需保存 Qn 和 n，内存与每步计算量恒定。这个形式将贯穿全书：
5. 非平稳问题与固定步长（§2.5）
采样平均（步长 1/n）适合平稳问题。非平稳时应给近期收益更高权重——最流行的是固定步长 α：
展开后 Qn+1 是历史收益的指数近因加权平均：Ri 的权重为 α(1−α)n−i，越久远权重指数式衰减。
理论上有名的收敛条件（随机逼近理论）：
1/n 两条都满足（收敛）；常数 α 第二条不满足（永不完全收敛，随最近收益波动）——在非平稳环境中这恰恰是我们想要的。
6. 乐观初始值（§2.6）
把初始估计设得远高于可能的真实值（如 10 臂测试平台上设 Q1(a)=+5，而真值来自 N(0,1)）。效果：无论选哪个动作，实际收益都低于估计 → 学习器"失望" → 转向别的动作。结果是即使纯贪心也会把每个动作都试好几遍，试探后估计收敛、表现反超（书图 2.3）。
7. UCB：基于置信度上界的选择（§2.7）
ε-贪心的试探是盲目的（不偏向接近最优或不确定性大的动作）。UCB 按"潜力"选择：
- 平方根项是对动作值估计不确定性的度量：Nt(a) 越大（试得越多），不确定性越小；
- 别的动作被选时 t 增大而 Nt(a) 不变，该动作的不确定性上升——保证所有动作最终都会被选中；
- Nt(a)=0 的动作视为最大（先试没试过的）；c>0 控制试探程度。
在 10 臂测试平台上 UCB 通常优于 ε-贪心（可在上方模拟器勾选 UCB 验证，注意起始的尖峰：前 k 步强制尝试所有未选动作）。但它难推广到非平稳问题和函数逼近的大状态空间——这也是书中更常用 ε-贪心的原因。
8. 梯度赌博机算法（§2.8）
不再估计动作价值，而是学习数值偏好 Ht(a)，按 softmax 分布选动作：
更新规则（𝑅̄t 是至今所有收益的平均值，作基准项）：
Ht+1(a) ≐ Ht(a) − α(Rt − 𝑅̄t)πt(a)，∀a ≠ At (2.12)
直觉：收益高于基准 → 未来多选 At；低于基准 → 少选。书中证明了式 (2.12) 恰是期望收益 𝔼[Rt] 的随机梯度上升（期望更新 = 真实梯度），因此收敛性有保证。基准项只需不依赖所选动作——设成 0 或 1000 都仍是随机梯度上升，但用 𝑅̄t 能显著降低方差；没有基准项时性能明显变差（书图 2.5）。
9. 关联搜索：通往完整 RL 的桥（§2.9）
每步随机面对不同的赌博机任务，但能观察到任务线索（如老虎机颜色）——此时可学策略：情境 → 最优动作的映射（红色选 1 号臂，绿色选 2 号臂）。这叫关联搜索（今称上下文相关赌博机）：
| k 臂赌博机 | 关联搜索 | 完整 RL | |
|---|---|---|---|
| 多情境？ | 否（单状态） | 是，需学策略 | 是，需学策略 |
| 动作影响未来？ | 否，只影响即时收益 | 否 | 是——影响下一情境与收益 |
一旦动作可以影响下一时刻的情境和收益，就是完整的强化学习问题——下一章（有限 MDP）正式展开。
10. 本章小结（§2.10）
- ε-贪心：小概率随机试探；UCB：确定性地优先选样本少的动作；梯度赌博机：不估价值，用偏好 + softmax 概率化选择；乐观初始值：让贪心方法也显式试探。
- 参数研究图（书图 2.6）显示各算法性能曲线呈倒 U 形——参数太大太小都不行；且各算法对参数在一个数量级范围内都不太敏感。此测试平台上 UCB 表现最好。
- 经典但受限的进阶：Gittins 指数（需先验分布）、贝叶斯方法 / Thompson 采样（后验采样）。
- 这些方法看似简单，却被公认为当前可用的最好技术之一；试探与开发的平衡远未彻底解决。
11. 检索练习
📝 书后练习（欢迎来和我讨论）
- 练习 2.1：ε=0.5、两个动作时，贪心动作被选中的概率是多少？（提示：两种途径都算一算）
- 练习 2.2：给定动作收益序列，判断哪些时刻肯定/可能发生了随机试探？
- 练习 2.5（编程）：非平稳版测试平台（q* 每步随机游走 σ=0.01），比较采样平均 vs 固定步长 α=0.1——想玩的话我可以把模拟器加一个"非平稳模式"。
- 练习 2.8：UCB 曲线在第 11 步为何出现尖峰？
- 练习 2.9：证明两动作时 softmax 等价于 sigmoid。
- 练习 2.10：2 臂、两种情况 A/B 的关联搜索任务，最优期望值是多少？