蒙特卡罗与时序差分

§ 1示例：打滑仓库

这一课不换例子。还是第 1 课那间 4×4 仓库：AGV 每步往上下左右挪一格，撞墙或撞货架留在原地，走到右下角的充电桩就结束；每走一步 −1，进桩之后不再有奖励，γ = 0.9。唯一保留的是第 1 课后半段加上的那一条：地面会打滑——你让它往某个方向走，它有 90% 真的走那个方向，剩下 10% 平分给左右两侧（各 5%）。

策略和它的真值表都是现成的，第 1 课已经用值迭代算过。把它们放在这里，是因为这一课所有的误差都以这张表为准：

左格左上角的小字是坐标。这张真值表是用 P 算出来的——这一课的两个算法都看不到它，它只用来在最后打分：估出来的表离它有多远。

现在让 AGV 真的走一趟。从左上角 (0,0) 出发，照策略走，落点由打滑决定，走到桩就停：

这一条 6 步走完，一次也没滑。整条轨迹的记录就这么多：走过哪些格、每步拿了多少。转移概率一个字都没出现——这正是这一课的前提：你能拿到的只有这样一条条记录。

§ 2期望换采样

上一课那四个算法，写出来都带着同一样东西。把策略评估那一行摊开：

这一行上一课逐字讲过，这里只用它指一个地方：加粗那一项就是这一课要拿掉的东西。它要求你对每一对 (s, a) 都说得出「下一格是谁、各多大概率」。第 1 课的仓库里我们自己写死了 0.90 / 0.05 / 0.05，所以算得出来；真机上没人给你这三个数——地面今天多滑、这个轮子磨损到什么程度、货架有没有被挪走，都不写在任何一张表里。

这就是这一课唯一的改动。那个 Σ 是在算一个期望——「按概率加权平均」。而估计一个期望有两种办法：一种是把概率拿来加权（要 P），另一种是多采几个样本再取平均（只要能采样）。上一课走的是第一条，这一课走第二条：

最后一行是随之而来的第二个改动，绕不开。动态规划算出来的那个数是精确的期望，直接写回表里就行；而一个样本只是那个期望的一次抽样，照着它整个覆盖过去，表会被单次的运气带着跑。所以更新式统一变成「朝目标挪一点」的形状：

这个式子读一遍就够了：拿这次采到的目标和表里的旧值比一比，差多少，就朝那个方向挪 α 那么多。α ∈ (0, 1] 叫步长，它的含义只有一句话：这一个样本，你给它多少信任。α = 1 是完全照它改写，α 很小是几乎不动。

§ 3回报的样本与期望

第 0 课给过回报的定义，这里只回忆一行——从时刻 t 起往后，所有奖励折现相加：

这个式子读一遍就够了：从此刻起往后每一步的奖励，各按离现在多远打一次折，然后全部加起来。而值函数的定义就是它的期望：V^π(s) = E_π[ G_t | S_t = s ]。

这一句是这一课的全部立足点：既然算不出期望，就多采几个样本取平均。大数定律保证，只要样本互相独立、来自同一个分布，样本均值会收敛到期望。到此为止，蒙特卡罗已经讲完了一半。

但「取平均」在这里可靠到什么程度，取决于样本散得有多开。从 (0,0) 出发跑 20000 条轨迹，把每条的 G₀ 都记下来：

把这三行连起来读：取平均之后无偏（−5.0262 对 −5.0279），但单看一条，标准差 0.5184、最差能到 −7.94。这个 0.5184 后面还会出现好几次——蒙特卡罗抖动的全部来源就是它，跟算法怎么写没有关系，是环境的随机性直接透到了目标里。

§ 4蒙特卡罗

把 §2 那个「目标」栏填上 G_t，就是蒙特卡罗。

这个式子读一遍就够了：站在这一幕的第 t 步，把「这一步之后实际拿到的折现总和」当成这一格该有的值，朝它挪 α 那么多。括号里那一项是这次采到的目标和表里旧值的差。

注意「跑完一整幕」这五个字是硬性的：G_t 要把 t 之后每一步的奖励都加进来，不到终止那一刻，这个数就算不出来。所以蒙特卡罗更新的时机只有一个——一幕结束之后，倒着把整幕的 G_t 一次性算完，再统一写回表里。

拿 §1 那条轨迹当例子。它走了 6 步，倒着算：G₅ = −1，G₄ = −1 + 0.9 × (−1) = −1.9，一路推到 G₀ = −4.6856——就是 §1 那张表的第四列。这 6 个数就是这一幕给出的 6 个目标，一个状态一个。

4.1　首次访问与每次访问

一幕里同一格可能被踩到不止一次。打滑之后 AGV 可能滑回去，(2,0) 在一幕里出现两次并不稀奇。这时候有两种记法：

两列都是 30 次独立重跑的平均、用样本均值（不是固定步长）。在这间仓库里两者几乎打平，差别小到不用挑。理论上有区别：首次访问的样本互相独立，是干净的无偏估计；每次访问的样本在同一幕内相关，只保证渐近无偏。知道有这两种写法、知道它们不是同一个估计量就够了，这一课后面一律用首次访问。

4.2　为什么写成「挪一点」而不是「求平均」

直白的做法是把每个状态的所有 G_t 存下来求平均。那要为每一格存一个越来越长的列表，状态一多就存不下。把平均写成递推，就不用存了：

读一遍：新的平均 ＝ 旧的平均 + ¹⁄_n 乘以「这一个新样本比旧平均高出多少」。这就是 §2 那个「挪一点」的形状，只不过步长取成 α_n = 1/n——样本越多，每个新样本的话语权越小。这样一格只要存两个数：当前的平均值，和已经数到第几个。

§ 5时序差分

蒙特卡罗那个「必须跑完一整幕」的限制，代价比看上去大。一幕 6 步还好；一幕几千步、或者根本没有终点（第 0 课那条链），你就一个数都更新不了。时序差分改的正是这一处：不等了，走一步就更新。

可是不等到底，G_t 就算不出来。那用什么当目标？——把 G_t 的定义拆开第一项：

括号里那一整块就是从下一格起往后的回报。它同样要等到终止才知道——但表里已经存着它的一个估计：V(S_t+1)。拿这个估计顶上去，目标就当场凑齐了：

这个式子读一遍就够了：走一步，收到奖励 R_t+1、落到 S_t+1；把「这一步的奖励 + 打折后的落点在表里写着的值」当成目标，朝它挪 α 那么多。这叫 TD(0)——括号里的 0 是说只往前看一步，后面还有看 n 步的写法。

5.1　TD 误差

括号里那一整块有自己的名字，后面每一课都会用到：

于是更新式写成 V(S_t) ← V(S_t) + α δ_t——朝着「减小这一步的意外」的方向挪一小步。δ 恒为 0 意味着表已经处处自洽，那正是第 1 课 Bellman 期望方程说的那件事。所有 TD 类算法做的都是同一件事：测量不自洽，再把值往减小不自洽的方向推一点。

5.2　同一条轨迹上的两个目标

把 §1 那条轨迹拿来，值表全填 0，看两个算法各自填了什么目标：

第 0 稿全是 0，所以 TD 的目标一律是 −1。它只知道「这一步亏了 1」，落点值多少还没人告诉它。而 MC 的目标已经带着整条轨迹的信息——(0,0) 那一行的 −4.6856 里，把后面 5 步全算进去了。

只有最后一行两者相等：第 5 步的落点就是充电桩，V(桩) 恒为 0 不是估计而是事实，这一步的自举没有引入任何偏差。信息就是从这一行开始，一幕一幕往回传的——和第 1 课那张「刷一遍，消息走一格」的传播图是同一件事，只不过那里一遍传一格是因为查表，这里一幕传一格是因为采样。

§ 6偏差与方差

先把两句话摆出来，再用数字对：

「无偏但抖」对上「有偏但稳」——这是这一课要记住的那一句。下面这张图把两边都画出来：

右图那个交叉点值得多看一眼，它不是画错了。把同一组实验的数字列出来：

每一格都是 30 次独立重跑的平均，α = 0.1，起点每幕随机挑一格。

下面这个组件把两条路并排跑一遍。同一条轨迹同时交给两边——数据完全一样，差别只来自更新式：

§ 7步长与收敛条件

α 是这一课新添的唯一一个旋钮，也是后面每一个算法都还会带着的那个。先看它在这间仓库里值多少：

1000 条轨迹，30 次独立重跑的平均。作为对照：MC 改用样本均值（α_n = 1/n）时 RMS 是 0.0452，比任何一个固定 α 都好——固定 α 那条曲线降到某个水平就不再往下走了。

Robbins–Monro 条件——随机逼近里那对经典的求和条件：

两个式子各管一件事，读一遍：第一个说「步子加起来要能走到无穷远」——不管初值填得多离谱，总步长足够把它拉过来；第二个说「步子的平方加起来要有限」——步长缩得够快，单个样本的噪声最终被压下去。

那为什么实践里几乎都用固定 α？因为第二条的代价是「越到后面越不肯动」。环境一变、或者被估的目标自己在动，固定 α 才跟得上。这一课的目标（G_t 或 R+γV）分布是不变的，所以 1/n 更准；下一课开始策略会一直改，被估的东西自己就在漂，那时固定 α 反而是对的。

§ 8确定性等价

把两个算法逼到极限来看：手上只有固定的一批轨迹，反复用同一个更新式刷，直到值表不再动。这叫批量（batch）版本。

12 次独立重跑的平均。同一批数据、都刷到不再动——两者收敛到的却不是同一张表。

这件事值得停一下：数据一模一样，为什么答案不一样？因为两个算法在用这批数据回答两个不同的问题。

后者有个名字：确定性等价估计（certainty-equivalence estimate）。「确定性等价」的意思是——把估出来的模型当成真的模型，然后精确求解，就好像它是确定无疑的一样。

这也是「TD 往往比 MC 快」的真正说法：不是因为它更新得频繁，是因为它在同样多的数据上榨出了更多信息。

§ 9习题

三道题都能在 §6 的组件里直接拉，或者改两行 code/mc_td.py 重跑。每题先自己写下预测的数，再展开对答案。

§ 10本章小结

1. 拿不到 P，那个 Σ 就求不出来；能做的只剩「真的走一步看看」。于是期望换成采样，精确赋值换成朝目标挪 α 那么多——这一课所有内容都是这一句的展开。
2. G_t 是样本，V^π(s) 是它的期望。大数定律保证样本均值收敛到期望，蒙特卡罗就建立在这一条上。
3. 两个算法只差「目标」那一栏。MC 填 G_t（要等一幕跑完），TD 填 R+γV(s′)（走一步就填得出）。其余部分一个字都不差。
4. 无偏但抖，对上有偏但稳。这间仓库里单条轨迹的 G 标准差是 0.5184；1000 条之后 MC 停在 0.1430、TD 停在 0.0870。前 300 条 MC 领先（TD 要一幕传一格），之后 TD 反超（比的是抖不抖）。
5. 自举这一次是真带偏差的。动态规划引用的上一稿是精确的，TD 引用的 V(s′) 只是个估计。看任何一个新算法，先找它的目标里有没有「自己」。
6. 固定的 α 保证不了收敛，只保证在附近抖。Robbins–Monro 两条：Σα = ∞ 管「走得到」，Σα² < ∞ 管「停得下」。1/n 两条都满足，固定 α 差第二条——但目标自己在动的时候，反而要固定 α。
7. TD 比 MC 省数据，是因为它用上了马尔可夫性。batch 版收敛到确定性等价估计：先从数据里数出一个模型，再精确解那个模型。一个只踩到 3 次的格子，也能间接用上它落点上那 200 条信息。
8. 这一课只做了「给定策略估值」，没有改过策略。估值是控制的前半段，后半段在下一课。

10.1　这个骨架后面一直在用

上一课那句「评估 ↔ 改进交替」不是动态规划专有的写法，是后面每一课的骨架。它有个名字：广义策略迭代。这一课换掉的只是「评估」那一格的实现——把「查 P 算精确期望」换成「采样出来的目标」，交替那个结构一个字没动。

把后面要拧的旋钮先列出来，你就知道每一课在动哪一处：

后面每一个算法，都是在这四个旋钮上取一个位置：