蒙特卡洛 — 等一整局打完,拿真回报说话
这一章讲三件事: 怎么只靠完整回合的平均回报估出值函数,不要任何环境模型; 「探索」在这个框架下怎么解决(以及那个被作者点名悬而未决的收敛问题); 以及 off-policy 学习的开端——怎么用 A 策略的经验估 B 策略的值。 读完你会拿到方法空间的第一根轴:bootstrap 还是不 bootstrap。
1. 定位:第一类「学习」方法
前两章都有点「作弊」:DP 直接给你环境的完整规则。本章开始什么都不知道,只有玩出来的经验——一串串真实的状态、动作、奖励序列。蒙特卡洛(MC)方法只做一件事:每个状态–动作对的值,取「从它出发的那些完整回合的实际回报」的平均1。
它的边界条件写在定义里:本书的 MC 只对情节任务——必须有「一局打完」这回事,因为只有打完才知道整局的回报;所以它能按局增量,不能按步增量2。
对比第 02 章的老虎机:现在有多个状态,每个状态像一个独立的老虎机——但这些老虎机互相牵连:这一步之后能拿多少,取决于后面每一步你还在怎么变。从早期状态看,问题天生是非平稳的——解法是把第 04 章的 GPI 搬过来,只是值函数改用「样本回报的平均」来估3。
2. 主走查:二十一点,平均 50 万局
书里的例 5.1 用二十一点演示 MC 评估(规则、状态数、局数与数值均为书中给出)4:
状态 = 三个变量的组合:玩家点数(12–21)× 庄家明牌(A–10)× 有无「可用的 A」
→ 共 200 个状态
策略:拿到 20 或 21 就停牌,否则要牌(固定策略,先学会「评估」它)
奖励:只有终局有数——赢 +1、输 −1、平 0;中途全是 0;不折扣
跑法:模拟一局 → 从头到尾记下经过的每个状态 → 终局回报 G(±1 或 0)
→ 对每个「到访过」的状态,把 G 记到它的账上
→ V(s) = 账上所有 G 的平均
1 万局后:值函数起伏很大(尤其「可用 A」那半张图,状态罕见、样本少)
50 万局后:值函数已经非常平滑、接近稳定
这个例子还顺手说明了 MC 的一个意外优势。二十一点的环境规则其实完全已知,理论上能用 DP——但算不出:想用 DP 得先回答「庄家明牌是 5、我 14 点选择停牌,最终赢的概率是多少」这类转移概率,这类计算复杂且容易错;而模拟一局对局却很容易。作者说这种情况出奇地常见:能轻易生成样本经验、却写不出现成的概率分布5。
MC 还有一张 DP 没有的牌:各状态的估计互相独立,不 bootstrap——估一个状态的值不需要碰别的状态的估计。于是可以只算感兴趣的那一个状态,别的一概不管(例 5.4 就是这么干的)6。
3. 核心原理一:到访一次还是到访多次
同一个状态可能在一局里出现多次。只记第一次到访后的回报,叫 first-visit MC;每次到访都记,叫 every-visit MC。两者都收敛到真值;first-visit 更好证(每次记录是独立的同分布样本,误差按 1/√n 缩小),every-visit 更容易推广到函数逼近7。
4. 核心原理二:控制——探索起点,以及一个没被证明的定理
从估价值到找最优策略,还是 GPI:估完 q 就把策略对 q 贪心。但这里横着一个第 02 章的旧问题:确定性的贪心策略只会在每个状态试出一个动作,其余动作的值永远没有样本——没有比较,谈何最优8。
本书的临时解法是探索起点(exploring starts):规定每一局都从「随机挑的状态–动作对」出发,且每对都有正概率被挑中。配上「每局结束后立刻改进」,得到 Monte Carlo ES:收敛到最优策略这件事「看起来不可避免,但至今没有被正式证明」——作者写道,这也许是强化学习里最根本的未解理论问题之一9。这句话值得原样带走:教科书也有它自己没合上的口子。
5. 核心原理三:off-policy——用 A 的经验,学 B 的值
探索起点在真实交互里做不到(你没法决定自己「从哪个动作开始人生」)。真正的出路是把探索和学习拆开:用一个爱探索的行为策略(behavior policy)b 去产生数据,同时学一个想变得最优的目标策略(target policy)π。数据来自 b,答案要的是 π 的——这就叫 off-policy 学习10。
换算的工具是重要性采样:一条轨迹在 π 下出现的概率与在 b 下出现的概率之比 ρ(把两边的概率表达式写开,环境动力学部分上下相消,比值只依赖两个策略和这条轨迹,与模型无关)11。把 b 产生的回报乘上 ρ,期望就变成了 π 下的回报。
两种平均法,取舍鲜明:
| ordinary(普通平均) | weighted(加权平均) | |
|---|---|---|
| 定义 | ρ·G 的简单平均 | Σρ·G / Σρ |
| 偏差 | 无偏 | 有偏(渐近消失) |
| 方差 | 可以无界 | 有限,实践中「方差低得惊人」,强烈首选12 |
6. 全书最生动的反例:方差无穷,永不收敛
一个只有一个状态的迷你例子,把 ordinary 重要性采样的毛病演到极致(数字全部来自书)13:
唯一的非终止状态 s;两个动作:
right → 必然终止,奖励 0
left → 90% 回到 s,10% 终止且奖励 +1
目标策略 π:永远选 left → 每局都是「绕几圈后 +1」,vπ(s) = 1
行为策略 b:left、right 各 50%(用来产生数据)
weighted 方法:凡最后走了 right 的局,ρ=0,直接不算;
最后走 left 的局,ρ 恰好把 50/50 抵消,回报恰为 +1
→ 第一局后就永远输出精确的 1。
ordinary 方法:绕圈局的 ρ = (1/0.5)^k(k 为圈数),回报又恒为 +1,
于是样本变成 2^k 这样的巨数;书里算出方差确实无穷,
一亿局之后,估计仍可能在 1 和 10 之间乱跳,不收敛。
教训:off-policy 的换算是必要的,但它自带方差账单;「学得关于谁」与「数据来自谁」分得越开,账单越重。这条主线在第 07 章(n-step 的离策方差)与第 11 章(发散问题)反复回来加码。
7. 作者的判断与证据
实验支撑的: 二十一点的 1 万/50 万局对比、off-policy 单状态估计(真值 0.27726,由一亿局单独测定)中加权法早期误差显著更低14;无穷方差例的数值计算(书里把期望的平方逐项求和,证得 1=0.2·Σ0.9^k·2^k·2 无穷)13。
作者的立场与坦白: MC ES 的收敛未证明(见上);off-policy MC「尽管概念简单,预测与控制两端都仍未成定论,是正在进行的研究主题」15。另外作者给 MC 记了第四笔潜在优势——不 bootstrap,所以对 Markov 性的破坏不那么敏感——这是他替 MC 留的一句公道话16。
8. 边界与局限
- 只能等局终:长回合任务里学习被整局拖住;没有回合的任务直接出局——这正是下一章 TD 的切入口。
- 探索起点假设在真实交互里不成立,ε-soft 的 on-policy 版只是折中(收敛到 ε-soft 里最好的策略,不是全局最优(全部策略里最好的))17。
- off-policy MC 控制只从回合尾部学:一旦中途出现非贪心动作,前面全白走;书里自己给的补救建议就是「引入时序差分」18。
- ordinary 重要性采样的方差问题没有银弹;本章末的两个减方差设计(折扣感知、per-decision)只降不除。
9. 可带走的
- MC=完整回合回报的平均;不要模型,但要「一局会结束」。
- 能模拟≠能写出分布:二十一点算不出转移概率,却随便模拟——经验样本本身就是武器。
- 不 bootstrap:各状态独立估值,可单点突破;也是对 Markov 性破坏更宽容的原因。
- 探索与学习拆开:行为策略管闯,目标策略管学;两者不同就叫 off-policy。
- 重要性采样=轨迹概率比;环境动力学相消,换算与模型无关。
- 永远优先加权版:有偏但方差有限;单状态迷你例里 ordinary 一亿局不收敛。
- MC ES 收敛至今未证明——教科书也会把没合上的口子明写出来,这是好学术的样子。
- 更新模板对照:MC 的「目标」是完整回报 G(t)——下一章把它换成「一步的奖励+下一步的估计」,世界就变了。
10. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 只要经验、情节限定、按局增量 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:5(搜「require only experience」) · text/08-fm-monte-carlo-methods.txt:19(搜「episode-by-episode」) · text/08-fm-monte-carlo-methods.txt:22(搜「complete returns」) |
| 多状态=关联老虎机、非平稳、GPI | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:27(搜「different bandit」) · text/08-fm-monte-carlo-methods.txt:32(搜「general policy iteration」) |
| first/every-visit、收敛 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:51(搜「first visit」) · text/08-fm-monte-carlo-methods.txt:80(搜「law of large numbers」) |
| 二十一点 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:86(搜「Blackjack」) · text/08-fm-monte-carlo-methods.txt:106(搜「usable」) · text/08-fm-monte-carlo-methods.txt:112(搜「sticks」) |
| DP 难用、模拟容易 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:152(搜「error-prone」) |
| 不 bootstrap、单状态可算 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:79(搜「independent」) · text/08-fm-monte-carlo-methods.txt:174(搜「independent of the number of states」) |
| 探索起点 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:239(搜「maintaining exploration」) · text/08-fm-monte-carlo-methods.txt:245(搜「exploring starts」) |
| MC ES 未 证明收敛 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:372(搜「formally proved」) |
| on/off-policy 定义、soft | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:460(搜「on-policy」) · text/08-fm-monte-carlo-methods.txt:467(搜「soft」) |
| target/behavior、coverage | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:598(搜「target policy」) · text/08-fm-monte-carlo-methods.txt:619(搜「coverage」) |
| 重要性采样比、动力学相消 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:640(搜「importancesampling ratio」) · text/08-fm-monte-carlo-methods.txt:651(搜「cancel」) |
| ordinary vs weighted | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:701(搜「biases and variances」) · text/08-fm-monte-carlo-methods.txt:709(搜「strongly preferred」) |
| 无穷方差例 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:758(搜「Infinite Variance」) · text/08-fm-monte-carlo-methods.txt:801(搜「estimates fail」) |
| off-policy 控制只学尾部 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:979(搜「tails of episodes」) |
| 对 Markov 破坏更宽容 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:1172(搜「less harmed」) |
| off-policy 尚未成定论 | Monte Carlo Methods | text/08-fm-monte-carlo-methods.txt:1205(搜「unsettled」) |