4.1 蒙特卡洛方法
4.1 蒙特卡洛方法
本节摘要：MC 用完整 episode 的实际回报 G_t 估计 V^π 或 Q^π，无 bootstrapping。First-visit 与 every-visit 两种平均。仅 episodic 任务；需等回合结束才更新。
本节目标
- 写回报 G_t = r_{t+1} + γ r_{t+2} + ...
- 区分 first-visit 与 every-visit MC
- 说明 MC 为何不能每步在线更新
核心思想
无模型：不估计 P，只从策略 π 采样轨迹。
MC 评估：对状态 s，收集每次访问 s 后的 G_t，取平均 → V^π(s)。
从 episode 末尾反向： G ← 0 for t = T-1 .. 0: G ← γ*G + R_{t+1} 若 first-visit 且 s_t 首次出现：记录 G 到 Returns(s_t) V(s) ← mean(Returns(s))
| 变体 | 计数规则 |
|---|---|
| First-visit | 每 episode 每状态只计第一次 |
| Every-visit | 每次出现都计 |
MC 控制
MC control：评估 Q^π + ε-greedy 改进。探索性起始或同策略探索保证每 (s,a) 无限访问。
问题驱动：稀疏终止奖励的 long episode → MC 方差大、信用分配慢 → 引出 TD。
⚠️ 常见坑：continuing 任务无明确 T——MC 需分幕或改用 TD。
💡 关键直觉：MC 无偏但高方差；每步不 bootstrap，信息要等整条轨迹。
重点提炼
- 经验平均 G_t
- episodic 限定
- first/every-visit
- MC control + ε-greedy
- 高方差→TD 动机
深度扩展：first-visit 为什么更常用，以及方差从哪来
蒙特卡洛的两种计数规则——first-visit 与 every-visit——在实际效果上有微妙差别，这里解释清楚，并顺着"方差大"这个缺点引出时序差分。
一条 episode：S1 → S2 → S3 → S1 → S4（终止） 状态 S1 出现了两次（t=0 和 t=3） first-visit：只记录 t=0 时刻算出的 G_0，丢掉第二次的样本 every-visit：t=0 和 t=3 两次的回报都记录，取平均
为什么 first-visit 更常用：同一状态在一局里多次出现时，两次回报高度相关（共享了中间的大段轨迹），every-visit 平均这些相关样本，并没有增加多少"独立信息"，理论分析还更复杂。而 first-visit 每次记录的都是"该状态本局的完整命运"，样本间更接近独立，收敛性质更清晰。实践中两者结果通常接近，但 first-visit 是教材与实现的默认选择。
方差为什么大：MC 用完整回报 G_t = r_t + γr_{t+1} + γ²r_{t+2} + ... 估计价值，而 G_t 是一条具体轨迹上的随机结果。轨迹越长、环境随机性越大，G_t 的波动就越大——尤其当奖励稀疏、只在终局给 ±1 时，同一状态下不同局算出的 G_t 可能一正一负，方差非常大。要降方差就得收集海量 episode，样本效率低。这就是"MC 无偏但高方差"的完整图景：无偏是因为它用真实回报，不引入估计的偏差；高方差是因为一条轨迹的运气成分太重。
MC 控制的两个探索保障：用 MC 做控制（学 Q 再 ε-greedy 改进）时，必须保证每个 (s,a) 对都能被无限次访问，否则 Q 值缺失。两种常用保障是探索性起始（开局随机撒到各种状态）或同策略探索（行为策略就是 ε-greedy）。这也埋下了 off-policy 的伏笔：如果想用旧策略收集的数据学新策略（数据复用），就要引入重要性采样等 off-policy 技术，复杂且方差更大。
为什么引出 TD：MC 的核心痛点是"必须等到 episode 结束才能更新"，且方差大。如果能每走一步就用"当前奖励 + 对下一状态的已有估计"来更新，就不必等结束、方差也小得多——这正是下一节时序差分的动机。理解 MC 的这两个缺点，才能理解 TD 每一处设计都在解决什么。
动手练习：手算一条 episode 的 MC 回报
用一条具体轨迹把 MC 的回报计算走一遍，把"反向累加"的手感练出来。轨迹如下（γ=0.9）：状态序列 S1→S2→S3→S4（终止），每步奖励依次是 +2、+1、0、+5（最后一步是进入终止状态的奖励）。
从末尾反向累加： G_3（S3 处） = R_4 + γ·(终止回报0) = 5 + 0 = 5 G_2（S2 处） = R_3 + γ·G_3 = 0 + 0.9×5 = 4.5 G_1（S1 处） = R_2 + γ·G_2 = 1 + 0.9×4.5 = 5.05 G_0（S0 处） = R_1 + γ·G_1 = 2 + 0.9×5.05 = 6.545
这里有两个要点。第一，反向累加的方向性——必须从终点往前算，因为每个 G 都依赖下一个 G，正着算只能一步步展开成多项和，容易出错。第二，回报共享轨迹——S1 的回报 6.545 包含了 S2、S3、S4 的全部未来奖励，所以同一局里不同状态的回报是"嵌套包含"的，这正解释了 first-visit 为什么常被优先选用：同一状态在一局内多次出现时，两次回报会共享中间大量项，相关性极高，every-visit 平均它们并不会带来多少独立信息。
再做一个延伸思考：如果这局跑得很"幸运"（奖励全是正数），MC 会用这个幸运值更新所有状态——这就是它"高方差"的现场。请想象 100 局里 S2 的回报从 -3 到 +9 剧烈波动，平均下来才勉强接近真值，这正是样本效率低的原因。把这个数字例子在纸上复算一遍，你对 MC"无偏但高方差"的理解就落地了。同时也为下一节做个铺垫：如果不想干等整局结束，而是每走一步就用"当前的奖励 + 下一步价值的估计"来更新，方差会立刻降下来——这正是时序差分的思想，也是 MC 最直接的接班人。