Lecture 3: 无模型策略评估 —— 不知道世界如何运作时如何评估策略（Model-Free Policy Evaluation）

目录 · ← l2 · l4 →

Lecture 3: 无模型策略评估 —— 不知道世界如何运作时如何评估策略（Model-Free Policy Evaluation）

对应材料：官方 lecture3pre/post.pdf（pre 53 页 / post 57 页）｜Week 2 周一 2026-01-12｜参考阅读 SB Chp 5.1, 5.5, 6.1–6.3；David Silver Lec 4（Model-Free Prediction） 一句话定位：L2 在「已知 $\mathcal{T}$ 与 $R$」的假设下用动态规划做策略评估；本讲把模型拿掉，只允许与环境交互得到轨迹或 $(s,a,r,s^{\prime})$ 元组，由此引入 RL 最核心的两个估计器——蒙特卡洛（Monte Carlo, MC）与时序差分（Temporal Difference, TD），并第一次正面处理「自举（bootstrapping）」带来的偏差-方差权衡；它是 L4 无模型控制（Q-learning、SARSA、DQN）的直接前置。

3.1 概述

本讲要回答一个问题：在只有直接经验（direct experience）、没有转移概率与奖励模型的条件下，如何估计固定策略 $\pi$ 的价值函数 $V^\pi(s)$？课程给出的三条路线是：蒙特卡洛策略评估（用完整回合的回报 $G_t$ 做经验平均）、时序差分 TD(0)（用 $r_t+\gamma V(s_{t+1})$ 这个自举目标逐步更新）、以及确定性等价（certainty equivalence）（先由数据做极大似然估计得到 $\hat P,\hat r$，再用 L2 的动态规划评估）。

三者的差别可以压缩成一句话：MC 采样但不自举，TD 既采样又自举，确定性等价不自举也不直接采样回报，而是先学一个模型。因此它们的偏差、方差、数据效率与计算开销各不相同，而「在批处理（batch/offline）设定下 MC 与 TD 收敛到不同的不动点」是本讲最锋利、也最容易被学生忽略的结论（AB 例子）。

本讲只处理同策略（on-policy）评估：数据由待评估的 $\pi$ 本身产生。用其他策略产生的数据做评估（离策略，off-policy）留到后续讲次。

3.2 核心概念的数学形式化

3.2.1 从有模型到无模型：为什么需要 model-free

严格定义。给定马尔可夫决策过程 $\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma)$ 与策略 $\pi$，策略评估的目标是求

「有模型」指算法每一步都能查询 $P(s^{\prime}\vert s,a)$ 与 $R(s,a)$；「无模型（model-free）」指算法只能访问一个采样器：给定 $(s,a)$ 返回 $(r,s^{\prime})$，或给定 $\pi$ 返回整条轨迹 $\tau=(s_0,a_0,r_0,s_1,\dots)$。

直观解释。有模型像拿到一本完整的交通地图；无模型像被蒙上眼睛放进城市里，只能坐车、看窗外、记下「从这儿到那儿花了多少钱」。地图精确但可能拿不到（机器人不知道轮胎在湿滑地面的摩擦系数、推荐系统不知道用户的真实点击概率）；经验粗糙但永远拿得到。

具体示例（Mars rover，讲义贯穿使用的例子）。7 个状态 $s_1,\dots,s_7$，奖励向量 $R(s)=[+1,0,0,0,0,0,+10]$，任意动作 $a_1$ 都可以，策略 $\pi(s)=a_1\;\forall s$，从 $s_1$ 或 $s_7$ 出发的任意动作终止回合。若已知模型，L2 的迭代式立刻可用；若无模型，我们只能拿到类似

的一条轨迹。

与前序方法对比。L2 的 $V^\pi_k(s)=r(s,\pi(s))+\gamma\sum_{s^{\prime}}p(s^{\prime}\vert s,\pi(s))V^\pi_{k-1}(s^{\prime})$ 有两条「特权」：（i）$\sum_{s^{\prime}}p(\cdot)V$ 是对全部后继状态的精确期望（无采样噪声）；（ii）$V^\pi_{k-1}$ 是上一轮估计，即自举。MC 放弃（i），TD 同时保留（i）的替代品（单样本后继）与（ii）。

3.2.2 蒙特卡洛（Monte Carlo, MC）策略评估

严格定义。设第 $i$ 条回合为 $s_{i,1},a_{i,1},r_{i,1},\dots,s_{i,T_i}$，定义

首次访问 MC（first-visit MC）：仅在状态 $s$ 于该回合中第一次出现的时刻更新

每次访问 MC（every-visit MC）：对该回合中每一次访问 $s$ 都做同样的累加。增量式 MC（incremental MC）把上式改写为在线形式

直观解释。「价值 = 平均回报」。MC 就是最朴素的统计：把从 $s$ 出发的所有实际回报记下来求平均。它甚至不假设状态是马尔可夫的——轨迹里的历史信息都被包进 $G_t$ 了。

具体示例（Mars rover 手算）。对上面那条轨迹，取折扣 $\gamma<1$，从后往前累积：

• 首次访问：$s_1$ 的首次（也是唯一一次）访问在 $t=4$，其后回报 $=1$，故 $V(s_1)=1$；$s_2$ 第一次出现在 $t=2$，其后奖励序列为 $0,0,1$，故 $V(s_2)=0+\gamma\cdot 0+\gamma^2\cdot 1=\gamma^2$；$s_3$ 在 $t=1$，$V(s_3)=\gamma^3$。即首次访问 MC 给 $[1,\gamma,\gamma^2,0,0,0,0]$。
• 每次访问：$s_2$ 被访问两次，回报分别为 $\gamma$（$t=3$）与 $\gamma^2$（$t=2$），故 $V(s_2)=(\gamma+\gamma^2)/2$，与讲义第 44 页结论 $V^{\text{MC}}(s_2)=\frac{\gamma^2+\gamma}{2}$ 一致。

与前序方法对比。MC 完全不需要 $P,R$，也不需要「状态是马尔可夫」这一假设，但要求回合能终止，且必须等回合结束才能更新。讲义还特别指出一条常被忽视的优点：即使已知真实模型，有时也偏好用 MC 而不是动态规划做评估（因为它直接估计目标量，不引入模型误差）。

3.2.3 时序差分学习 TD(0)

严格定义。TD(0)（1 步 TD）在每一步拿到 $(s_t,a_t,r_t,s_{t+1})$ 后就更新

TD 误差（TD error）定义为

直观解释。MC 说「用真实走完的结果当老师」，TD 说「用下一站的当前估价 + 这一步的即时奖励当老师」。这个「老师」本身会变，所以是自举。类比：开车时 MC 是走完全程才回头总结路线好不好；TD 是每到一个路口就用「导航对下一个路口的估计」来修正「对当前路口的估计」。

具体示例（Mars rover 手算，$\alpha=1$，初值全 0）。按时间顺序在线更新：

最终 $V=[1,0,0,0,0,0,0]$——与讲义第 36、49、57 页给出的结果完全一致。注意 $V(s_2),V(s_3)$ 仍为 0：TD 只在这一条轨迹上「向后传播」了一步的信用，而 MC 一次性把 $1$ 折现传到了 $s_2,s_3$。这正是「TD 更新更局部、方差更低、但早期更依赖初始化」的微观来源。

与前序方法对比。TD 的更新目标 $r+\gamma V(s^{\prime})$ 是 $V^\pi(s)$ 的有偏估计（$V(s^{\prime})$ 本身是估计值），但只含一个随机动作、奖励与后继状态，因此方差远低于 $G_t$（后者是一整条随机序列的函数）。TD 不需要回合终止（可在无限时域、非回合制任务上跑），每步 $O(1)$，且利用了马尔可夫结构——这正是它比 MC 数据效率更高的原因（讲义 L4 第 14 页「TD exploits Markov structure」）。

3.2.4 估计器质量：偏差、方差、MSE 与一致性

严格定义。设真正的参数为 $\theta$（此处 $\theta$ 泛指被估量，如 $V^\pi(s)$），估计量为 $\hat\theta$：

称 $\hat\theta_n$（用 $n$ 个数据点）一致（consistent），若 $\forall\varepsilon>0,\ \lim_{n\to\infty}\Pr(\vert \hat\theta_n-\theta\vert >\varepsilon)=0$。

要点：无偏 不蕴含一致（无偏只说明没有系统性偏移，方差可能不随 $n$ 收缩）。讲义第 25 页专门提这个问题，答案是「不一定」。

各类 MC 的统计性质（讲义第 26 页）：

• 首次访问 MC 无偏：$\mathbb{E}[V^\pi(s)]=\mathbb{E}_\pi[G_t\vert s_t=s]$，且由大数定律（law of large numbers），$N(s)\to\infty$ 时 $V^\pi(s)\to V^\pi(s)$。
• 每次访问 MC 有偏但一致，且在很多场合MSE 更小（每个回合的数据被更充分地利用）。
• 增量 MC 的性质取决于步长：若 $\sum_{n=1}^\infty \alpha_n(s_j)=\infty$ 且 $\sum_{n=1}^\infty \alpha_n^2(s_j)<\infty$（Robbins–Monro 条件），则收敛到 $V^\pi(s_j)$。取 $\alpha_n=1/n$ 时增量 MC 等价于每次访问 MC。

TD(0) 的统计性质（讲义第 40、56 页）：有偏（早期受初始化影响、且目标含估计值），一般方差低于 MC；在表格表示（tabular）下，若步长满足同一组 Robbins–Monro 条件则收敛到 $V^\pi$；但在函数逼近下 TD(0) 并不总是收敛。

MC 的主要缺陷（讲义第 28 页）：高方差、降低方差需要大量数据、必须是回合制（回合不结束就无法更新）。

3.2.5 确定性等价（certainty equivalence）：第三种无模型路线

严格定义。每收集完一个 $(s,a,r,s^{\prime})$ 就重估极大似然（MLE）模型：

然后用 L2 的任意规划方法在 $(\hat P,\hat r)$ 上算 $V^{\hat\pi}$（此处 $\pi$ 固定，故只需策略评估）。

直观解释。先把经验「压缩」成一个模型，再在模型上做精确推理。它非常省数据（每条经验都被完整利用，且马尔可夫结构被显式利用），但计算非常贵：每次更新后都要重新规划，解析矩阵解 $O(\vert \mathcal{S}\vert ^3)$、迭代法 $O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert )$。讲义称其「very data efficient and very computationally expensive」，且对马尔可夫模型是一致估计，还能自然地扩展到离策略评估。

3.2.6 批处理下的 MC 与 TD：它们收敛到不同的东西

严格定义。给定固定的 $K$ 条回合数据，反复从中采样回合并施加 MC 或 TD(0) 更新（数据可重复使用），问极限是什么？

• Batch MC 收敛到训练集上的最小二乘解：每个状态的经验平均回报 \(V_{\text{MC}}(s)=\frac{1}{N(s)}\sum_{i=1}^{N(s)}G_i(s)\)
• Batch TD(0) 收敛到TD 不动点，即在数据的 MLE 模型上解 Bellman 方程得到的值： \(V_{\text{TD}}(s)=\hat r(s,\pi(s))+\gamma\sum_{s'}\hat P(s'\|s,\pi(s))\,V_{\text{TD}}(s')\) 这正是一个确定性等价估计。

AB 例子（SB 2018 Example 6.4，讲义第 46–49 页）。两个状态 $A,B$，$\gamma=1$，8 条回合经验：

A, 0, B, 0          （1 次）
B, 1                （6 次）
B, 0                （1 次）

先算 $V(B)$：$B$ 被访问 8 次，其中 6 次奖励为 1，故 $V(B)=6/8=0.75$（MC 与 TD 一致，因为 $B$ 之后立即终止，没有「后继估计」可自举）。再看 $V(A)$：

同一个数据集、同一个策略，两个「正确运行到收敛」的算法给出 $0$ 和 $0.75$——它们回答的其实是两个不同的问题：MC 回答「在训练集里，从 $A$ 出发实际观测到的平均回报是多少」；TD 回答「若把数据的马尔可夫结构外推成一个 MLE 模型，$A$ 的真实期望回报是多少」。讲义用这个例子强调：batch 设定下「MC 与 TD 收敛到什么」必须被明确理解。

3.2.7 函数逼近下的目标与半梯度（semi-gradient）

当状态太多不能建表时，用参数化近似 $\hat V(s;w)$（$w$ 为值函数参数）。把 MC 与 TD 都改写成「对数据对做监督学习」：

半梯度的含义：TD 的损失 $J(w)=\mathbb{E}\bigl[(r+\gamma\hat V(s^{\prime};w)-\hat V(s;w))^2\bigr]$ 中，目标项 $r+\gamma\hat V(s^{\prime};w)$ 也依赖 $w$，真正的梯度还要包含对它的求导项 $-\gamma\nabla_w\hat V(s^{\prime};w)$。TD 更新故意丢掉这一项，只对 $\hat V(s;w)$ 求导，故称半梯度（semi-gradient）。它不是任何损失函数的梯度，因此不能保证收敛——讲义第 56 页的结论正是：MC 即便在函数逼近下也一致；而 TD(0) 在函数逼近下不总收敛。

直观解释：TD 每步把「移动靶」当成固定靶来打。靶自己会动，所以角度略有偏差，但恰恰是这种「只往当前估计的方向走一步」的贪婪带来了更好的样本效率。

3.2.8 从 TD(0) 到 TD($\lambda$)：$\lambda$-return 与资格迹（eligibility traces）

讲义第 40 页明确写道：本讲介绍的只是 TD(0)，「一般地可以有在 TD(0) 与 MC 之间插值的做法」。标准做法是$n$ 步回报与 $\lambda$-return：

• $\lambda=0$：$G_t^{\lambda}=G_t^{(1)}=r_t+\gamma V(s_{t+1})$，退回 TD(0)。
• $\lambda=1$：$G_t^{\lambda}=G_t$，退回 MC。

资格迹是它的在线实现：为每个状态维护迹 $e_t(s)$（例如累积迹 $e_t(s)=\gamma\lambda e_{t-1}(s)+\mathbb{1}(s_t=s)$），更新

直观解释：TD(0) 每步只把「信用」给刚访问的 $s_t$；MC 把信用平均分给整条轨迹的所有状态；$\lambda\in(0,1)$ 是指数加权的折中——近期访问过的状态拿更多信用。偏差-方差也随 $\lambda$ 单调地从 TD(0)（低方差、高偏差）滑向 MC（高方差、无偏）。

3.3 算法伪代码与完整推导

3.3.1 首次/每次访问 MC 策略评估

Input: 策略 π, 折扣 γ
Initialize N(s) = 0, G(s) = 0, V(s) = 任意值, ∀s ∈ S
Loop (对每条回合 i = 1, 2, ...):
    Sample 一条完整回合 i: s_{i,1}, a_{i,1}, r_{i,1}, ..., s_{i,T_i}, a_{i,T_i}, r_{i,T_i}
    计算回报: G_{i,t} = r_{i,t} + γ r_{i,t+1} + ... + γ^{T_i - t} r_{i,T_i}
    For t = 1 到 T_i:
        s = s_{i,t}
        If (首次访问 MC) 这是 s 在回合 i 中第一次出现,  Or (每次访问 MC) 无条件:
            N(s) = N(s) + 1
            G(s) = G(s) + G_{i,t}
            V(s) = G(s) / N(s)
Termination: 对所有 s, N(s) → ∞ （或 V 的变化小于阈值 ε）
Output: V ≈ V^π

算法逻辑解说：MC 不做任何近似——它直接估计 $\mathbb{E}_\pi[G_t\vert s_t=s]$ 这个定义本身。首次与每次访问的差别只在于「一个回合内重复访问同一状态时，要不要把后续回报也计入」。

数学推导（增量平均）：设某状态已被访问 $N-1$ 次、当前平均为 $V_{N-1}$，第 $N$ 次观测到回报 $G$，则新平均

令 $\alpha=1/N$ 即得增量式 $V\leftarrow V+\alpha(G-V)$。这就是「学习率 × (目标 − 当前估计)」这一 RL 通用更新范式的第一次出现（讲义第 16 页原话：we will see many algorithms of this form with a learning rate, target, and incremental update）。把 $1/N$ 换成固定 $\alpha$，就得到能跟踪非平稳环境的常数步长版本（这也是讲义第 46 页 poll 里「$\alpha>1/N$ 在非平稳域中有用」为真的原因）。

与理论的对应：首次访问无偏性来自 $G_{i,t}$ 与 $V$ 的独立性（不同回合）；一致性来自大数定律。

3.3.2 TD(0) 策略评估

Input: 策略 π, 折扣 γ, 步长 α
Initialize V(s) = 0, ∀s ∈ S
Loop:
    Sample 元组 (s_t, a_t, r_t, s_{t+1})     # 由执行 π 得到
    δ_t = r_t + γ V(s_{t+1}) - V(s_t)        # TD 误差
    V(s_t) = V(s_t) + α δ_t
Termination: 永不终止（在线）／或指定步数 / 回合数
Output: V ≈ V^π

算法逻辑解说：TD 用「一步真实奖励 + 对后继的猜测」代替「真实回报」。它是「采样 + 自举」的组合：采样替换掉了对 $s_{t+1}$ 的期望求和，自举替换掉了对未来的真实回报。

数学推导（TD 不动点）：把 TD 更新写成期望形式。设数据由 $\pi$ 产生，定义在估计 $V$ 上的期望 TD 更新算子

注意它恰是 L2 的 Bellman 算子 $B^\pi$。TD(0) 的不动点满足 $\mathcal{T}^\pi V=V$，即 $V=V^\pi$——在表格表示下 TD(0) 收敛到正确值。这也解释了为什么 TD「利用了马尔可夫结构」：它的每次更新都是在用一步 Bellman 关系做局部一致性约束，而 MC 完全不用这个关系。

与理论的对应：在批处理设定下，把上式中的期望换成数据诱导的 $\hat R,\hat P$，得到的不是同一个方程——见 3.2.6 与下面的 AB 推导。

AB 例子的确定性等价推导（讲义第 50–51 页）。数据给出的 MLE 模型是：$\hat r=[1,0,0,0,0,0,0]$（即 $\hat r(s_1)=1$，其余为 0），$\hat p(\text{terminate}\vert s_1,a_1)=1$，$\hat p(s_2\vert s_3,a_1)=1$，$\hat p(s_2\vert s_2,a_1)=0.5=\hat p(s_1\vert s_2,a_1)$。在「只保留 $s_1,s_2,s_3$」的子空间上，$V=R+\gamma PV\Rightarrow (I-\gamma P)V=R$，讲义给出

（讲义第 50 页的 $[0,\frac{\gamma\cdot 0.5}{1-0.5\gamma},\dots]$ 是排版笔误，第 51 页给出正确解，并注明 “Typo: $V(s_1)$ should = 1”。注意 $V(s_1)=1$ 恰好等于 TD 在该数据上给出的 $V(A)=0.75$ 的同构版本：确定性等价与 batch TD 收敛到同一个量，这不是巧合，因为 TD 不动点就是 MLE 模型上的 Bellman 解。）

3.3.3 确定性等价策略评估

Input: 策略 π（用于选择动作）, 数据集 {(s,a,r,s')}
Initialize 对所有 (s,a) 初始化计数 N(s,a)=0 与后继计数
Loop:
    收集/读取一个元组 (s, a, r, s')
    N(s,a) += 1
    更新后继计数 与 奖励和
    P̂(s'|s,a) = 后继计数 / N(s,a)
    r̂(s,a)    = 奖励和 / N(s,a)
    在 (P̂, r̂) 上用 L2 的方法评估 V̂^π   # 迭代法 O(|S|^2|A|)，矩阵解 O(|S|^3)
Termination: V̂ 收敛 / 预算耗尽
Output: V̂ ≈ V^π

算法逻辑解说：注意代价——「每次更新后都重新规划」是 $O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert )$ 甚至 $O(\vert \mathcal{S}\vert ^3)$，与 TD 的 $O(1)$ 形成极端对比。这是数据效率与计算效率之间最干净的一个权衡样本。

3.4 代码实现与实验分析

3.4.1 实验一：5 状态随机游走上的 MC vs TD(0) 学习曲线

环境：状态 $0..6$，$0$ 与 $6$ 为终止状态（奖励分别为 $0$ 与 $+1$），非终止状态 $1..5$，每步等概率左右移动，从状态 $3$ 出发（Sutton & Barto 例 6.2 的经典随机游走）。真实值有闭式：$V(s_k)=k/6$，即 $[1/6,2/6,3/6,4/6,5/6]$。

"""
CS234 Lecture 3 —— 实验 1：随机游走上的 MC vs TD(0) 学习曲线
依赖：numpy / matplotlib / 标准库
"""
import numpy as np
import matplotlib
matplotlib.use("Agg")   # 无显示环境
import matplotlib.pyplot as plt

np.random.seed(0)

N_STATES = 7
TERMINAL = (0, 6)
START = 3
TRUE_V = np.array([0.0, 1/6, 2/6, 3/6, 4/6, 5/6, 0.0])


def step(s):
    s_next = s + (1 if np.random.rand() < 0.5 else -1)
    r = 0.0 if s_next == 0 else (1.0 if s_next == 6 else 0.0)
    return s_next, r


def sample_episode():
    states, rewards = [START], []
    s = START
    while s not in TERMINAL:
        s, r = step(s)
        states.append(s)
        rewards.append(r)
    return states, rewards


def mc_every_visit(alpha, n_episodes):
    """V(s) <- V(s) + alpha (G_t - V(s))，每回合内每次访问都更新"""
    V = np.zeros(N_STATES)
    for _ in range(n_episodes):
        states, rewards = sample_episode()
        G = 0.0
        for t in range(len(rewards) - 1, -1, -1):
            G = rewards[t] + G
            V[states[t]] += alpha * (G - V[states[t]])
    return V


def mc_first_visit(alpha, n_episodes):
    """首次访问 MC：先正向标记首次访问的时刻，再反向累积 return"""
    V = np.zeros(N_STATES)
    for _ in range(n_episodes):
        states, rewards = sample_episode()
        seen, first_t = set(), set()
        for t in range(len(rewards)):
            if states[t] not in seen:
                seen.add(states[t])
                first_t.add(t)
        G = 0.0
        for t in range(len(rewards) - 1, -1, -1):
            G = rewards[t] + G
            if t in first_t:
                V[states[t]] += alpha * (G - V[states[t]])
    return V


def td0(alpha, n_episodes):
    """TD(0)：V(s) <- V(s) + alpha (r + gamma V(s') - V(s))"""
    V = np.zeros(N_STATES)
    for _ in range(n_episodes):
        states, rewards = sample_episode()
        for t in range(len(rewards)):
            s, s_next, r = states[t], states[t + 1], rewards[t]
            V[s] += alpha * (r + V[s_next] - V[s])
    return V


def rmse(V):
    return float(np.sqrt(np.mean((V[1:6] - TRUE_V[1:6]) ** 2)))


def run_curve(alg, alpha, n_runs=100, n_episodes=200,
              checkpoints=(1, 10, 50, 100, 200)):
    """跑 n_runs 次独立重复，返回平均 RMSE 曲线与关键 checkpoint"""
    curves = np.zeros(n_episodes)
    for _ in range(n_runs):
        V = np.zeros(N_STATES)
        for ep in range(n_episodes):
            if alg == "td":
                states, rewards = sample_episode()
                for t in range(len(rewards)):
                    s, s_next, r = states[t], states[t + 1], rewards[t]
                    V[s] += alpha * (r + V[s_next] - V[s])
            elif alg == "mc_ev":
                states, rewards = sample_episode()
                G = 0.0
                for t in range(len(rewards) - 1, -1, -1):
                    G = rewards[t] + G
                    V[states[t]] += alpha * (G - V[states[t]])
            elif alg == "mc_fv":
                states, rewards = sample_episode()
                seen, first_t = set(), set()
                for t in range(len(rewards)):
                    if states[t] not in seen:
                        seen.add(states[t])
                        first_t.add(t)
                G = 0.0
                for t in range(len(rewards) - 1, -1, -1):
                    G = rewards[t] + G
                    if t in first_t:
                        V[states[t]] += alpha * (G - V[states[t]])
            curves[ep] += rmse(V)
    curves /= n_runs
    return curves, {c: float(curves[c - 1]) for c in checkpoints}


if __name__ == "__main__":
    print("真实 V =", np.round(TRUE_V[1:6], 4).tolist())
    curves = {}
    for name, alg, a in [("TD(0)        alpha=0.1", "td", 0.1),
                         ("MC every-visit alpha=0.1", "mc_ev", 0.1),
                         ("MC first-visit alpha=0.1", "mc_fv", 0.1)]:
        cur, cps = run_curve(alg, a, n_runs=100, n_episodes=200)
        curves[name] = cur
        print(name, {c: round(cps[c], 4) for c in (1, 10, 50, 100, 200)})

    print("\n长时间收敛检查（alpha=0.05, 2000 episodes x 50 runs）：")
    for name, fn in [("TD(0)", td0), ("MC every-visit", mc_every_visit),
                     ("MC first-visit", mc_first_visit)]:
        acc = np.zeros(N_STATES)
        for _ in range(50):
            acc += fn(0.05, 2000)
        acc /= 50
        print(f"  {name:<16} V[1:6]={np.round(acc[1:6], 4).tolist()} RMSE={rmse(acc):.4f}")

    print("\nTD(0) 步长敏感性（100 runs，RMSE @ ep=1/10/100/500）：")
    for a in (0.01, 0.05, 0.1, 0.2, 0.4):
        _, cps = run_curve("td", a, n_runs=100, n_episodes=500,
                           checkpoints=(1, 10, 100, 500))
        print(f"  alpha={a:<5} " + "  ".join(f"ep{c}={cps[c]:.4f}" for c in (1, 10, 100, 500)))

    fig, axes = plt.subplots(1, 2, figsize=(11, 4))
    for name, cur in curves.items():
        axes[0].plot(np.arange(1, 201), cur, label=name)
    axes[0].set_xlabel("episodes"); axes[0].set_ylabel("RMSE vs true V")
    axes[0].set_title("MC vs TD(0) on Random Walk (alpha=0.1)")
    axes[0].legend(fontsize=8); axes[0].grid(alpha=0.3)
    for a in (0.01, 0.05, 0.1, 0.2, 0.4):
        cur, _ = run_curve("td", a, n_runs=50, n_episodes=200)
        axes[1].plot(np.arange(1, 201), cur, label=f"alpha={a}")
    axes[1].set_xlabel("episodes"); axes[1].set_ylabel("RMSE vs true V")
    axes[1].set_title("TD(0): effect of step size")
    axes[1].legend(fontsize=8); axes[1].grid(alpha=0.3)
    plt.tight_layout(); plt.savefig("L03_mc_vs_td.png", dpi=110)

代码做什么：实现一个 5 状态随机游走环境与三个估计器（每次访问 MC、首次访问 MC、TD(0)），用 100 次独立重复的平均 RMSE 对比它们逼近真实 $V$ 的速度；并扫描 $\alpha$ 看步长对 TD 的影响。脚本存于 cs234/code/L03_mc_vs_td.py。

RL 机制透视：这段代码把 3.2 的两个更新式一字不差地实现出来，差别只在目标：MC 用反向累积的真实回报 $G$，TD 用 r + V[s_next]。注意 mc_first_visit 里那个「先正向标记首次访问时刻、再反向累积回报」的两遍写法——这是一个极容易写错的细节：若只在反向扫描时用一个 visited 集合去重，记录的其实是最后一次访问的回报，得到的是有偏结果。（本次实现过程中确实踩到了这个坑：同一套环境直接统计首次访问回报，得到 $\hat V(3)=0.3796$ 而非真值 $0.2580$，修正后两遍式才与真实值吻合。）另外请注意，本实验里每次访问 MC 在 ep=50 之后反而比 TD 更差（0.1554 vs 0.0499 @ ep=200），原因不是 MC 有偏，而是常数步长下高方差的 $G_t$ 使估计长期在真值附近大幅抖动。

实验观察（真实运行输出，python3 L03_mc_vs_td.py，本机实测约 21–27 秒）：

真实 V = [0.1667, 0.3333, 0.5, 0.6667, 0.8333]
                          ep=1     ep=10    ep=50    ep=100   ep=200
TD(0)        alpha=0.1    0.5371   0.4267   0.1577   0.0667   0.0499
MC every-visit alpha=0.1  0.4806   0.2215   0.1634   0.1654   0.1554
MC first-visit alpha=0.1  0.5159   0.2844   0.0896   0.0896   0.0965

长时间收敛检查（alpha=0.05, 2000 episodes x 50 runs）：
  TD(0)            V[1:6]=[0.1493, 0.3175, 0.4917, 0.6693, 0.8379]  RMSE=0.0114
  MC every-visit   V[1:6]=[0.1560, 0.3330, 0.5181, 0.6854, 0.8356]  RMSE=0.0126
  MC first-visit   V[1:6]=[0.1687, 0.3383, 0.5113, 0.6726, 0.8417]  RMSE=0.0073

TD(0) 步长敏感性（100 runs）：
  alpha=0.01   ep1=0.5513  ep10=0.5382  ep100=0.4263  ep500=0.1566
  alpha=0.05   ep1=0.5454  ep10=0.4854  ep100=0.1503  ep500=0.0394
  alpha=0.10   ep1=0.5391  ep10=0.4206  ep100=0.0657  ep500=0.0540
  alpha=0.20   ep1=0.5248  ep10=0.3269  ep100=0.0843  ep500=0.0857
  alpha=0.40   ep1=0.5054  ep10=0.2251  ep100=0.1330  ep500=0.1349

结论：（1）早期 TD 的增益最慢（ep=1 时 TD 的 RMSE 0.5371 最大，MC 每次访问 0.4806、首次访问 0.5159 都更低），因为 TD 有初始化偏差，而 MC 立即给出（首次访问意义下）无偏但高方差的估计；（2）中期 TD 明显领先（ep=100：TD 0.0667 vs 每次访问 MC 0.1654、首次访问 MC 0.0896），因为 TD 利用马尔可夫结构把信息沿状态链逐步传播；（3）长期看每次访问 MC 反而落后（ep=200：TD 0.0499、首次访问 MC 0.0965、每次访问 MC 0.1554）——常数步长下高方差的 $G_t$ 让估计长期在真值附近抖动，这是「TD 方差更低」的直接体现。另外，注意首次访问 MC 在 ep=50–100 一度优于 TD（0.0896 vs 0.1577/0.0667 的交叉），说明「MC 无偏」在中等数据量下确实能换回精度。步长扫描显示 $\alpha$ 太小（0.01）学得慢（ep=500 仍有 0.1566），$\alpha$ 太大（0.4）稳态误差反而升高（ep=500 为 0.1349，比 0.05 的 0.0394 差一个数量级），中间存在最优点（0.05–0.1 附近），与 Robbins–Monro 条件「步长应当衰减」的直觉一致。

3.4.2 实验二：AB 例子（Batch MC vs Batch TD）+ 状态聚合

"""
CS234 Lecture 3 —— 实验 2：AB 例子（SB Ex. 6.4）与状态聚合下的 MC/TD 不动点
依赖：numpy / matplotlib / 标准库
"""
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

np.random.seed(0)

#---- (a) AB 例子：8 条固定 episode ----
#---- 状态编码 0=A, 1=B, 2=terminal；A 走 0 奖励到 B；B 走 r_B 到 terminal
EPISODES = [("A", 0.0, 0.0)] + [("B", 0.0, 1.0)] * 6 + [("B", 0.0, 0.0)]


def sample_ab_episode():
    start, r_a, r_b = EPISODES[np.random.randint(len(EPISODES))]
    if start == "A":
        return [0, 1, 2], [r_a, r_b]
    return [1, 2], [r_b]


def batch_mc(samples, V_init=(0.0, 0.0)):
    """Batch MC，alpha = 1/N(s)：极限 = 训练集上的最小二乘解（经验平均回报）"""
    V = np.array([V_init[0], V_init[1], 0.0])
    N = np.zeros(3)
    for _ in range(samples):
        states, rewards = sample_ab_episode()
        G = 0.0
        for t in range(len(rewards) - 1, -1, -1):
            G = rewards[t] + 1.0 * G          # gamma = 1
            s = states[t]
            N[s] += 1
            V[s] += (G - V[s]) / N[s]
    return V


def batch_td(samples, V_init=(0.0, 0.0)):
    """Batch TD(0)，alpha = 1/N(s)：极限 = TD 不动点（MLE 模型上的 V^pi）"""
    V = np.array([V_init[0], V_init[1], 0.0])
    N = np.zeros(3)
    for _ in range(samples):
        states, rewards = sample_ab_episode()
        for t in range(len(rewards)):
            s, s_next, r = states[t], states[t + 1], rewards[t]
            N[s] += 1
            V[s] += (r + 1.0 * V[s_next] - V[s]) / N[s]
    return V


def repeat(fn, n_repeat, *args, V_init=(0.0, 0.0)):
    out = np.array([fn(*args, V_init=V_init) for _ in range(n_repeat)])
    return out.mean(axis=0), out.std(axis=0)


print("=" * 70)
print("AB 例子（SB Ex. 6.4, gamma=1）：解析解 V(B)=6/8=0.75，"
      "V_MC(A)=0.00，V_TD(A)=0.75")
for name, fn in [("Batch MC", batch_mc), ("Batch TD", batch_td)]:
    for samples in (3000, 12000, 30000):
        m, sd = repeat(fn, 4, samples)
        print(f"  {name:<10} samples={samples:<7} V(A)={m[0]:.4f}  V(B)={m[1]:.4f}")
for name, fn in [("Batch MC", batch_mc), ("Batch TD", batch_td)]:
    v0, _ = repeat(fn, 4, 60000, V_init=(0.0, 0.0))
    v5, _ = repeat(fn, 4, 60000, V_init=(5.0, 5.0))
    print(f"  {name:<10} init(0,0)->V(A)={v0[0]:.4f}   init(5,5)->V(A)={v5[0]:.4f}")

#---- (b) 状态聚合：MC 最小二乘解 vs TD 不动点 ----
N_STATES, TERMINAL, START, GAMMA = 7, (0, 6), 3, 0.9
GROUPS = {1: 0, 2: 0, 3: 1, 4: 2, 5: 2}      # V(s) = w[GROUPS[s]]
N_GROUPS = 3

P = np.zeros((N_STATES, N_STATES)); R = np.zeros(N_STATES)
for s in range(1, 6):
    P[s, s - 1] = 0.5; P[s, s + 1] = 0.5
R[5] = 0.5
TRUE_V = np.linalg.solve(np.eye(N_STATES) - GAMMA * P, R)

#---- 折扣状态访问分布 d^pi（从 START 出发）
d = np.zeros(N_STATES); p = np.zeros(N_STATES); p[START] = 1.0
for t in range(3000):
    d = d + (GAMMA ** t) * p
    p2 = np.zeros(N_STATES)
    for s in range(1, 6):
        p2[s - 1] += 0.5 * p[s]; p2[s + 1] += 0.5 * p[s]
    p = p2

w_mc = np.array([sum(d[s] * TRUE_V[s] for s in GROUPS if GROUPS[s] == g) /
                 sum(d[s] for s in GROUPS if GROUPS[s] == g) for g in range(N_GROUPS)])

A = np.zeros((N_GROUPS, N_GROUPS)); b = np.zeros(N_GROUPS)
for s in range(1, 6):
    g = GROUPS[s]; A[g, g] += d[s]
    for sn in range(N_STATES):
        if P[s, sn] > 0 and sn in GROUPS:
            A[g, GROUPS[sn]] -= GAMMA * d[s] * P[s, sn]
    b[g] += d[s] * R[s]
w_td = np.linalg.solve(A, b)

print("\n状态聚合（gamma=0.9, 组 {1,2}/{3}/{4,5}）")
print("  真实 V[1:6] =", np.round(TRUE_V[1:6], 4).tolist())
for g in range(N_GROUPS):
    print(f"  group {g}: MC={w_mc[g]:.4f}  TD={w_td[g]:.4f}")
def rmse(w):
    V = np.array([0.0] + [w[GROUPS[s]] for s in range(1, 6)] + [0.0])
    return float(np.sqrt(np.mean((V[1:6] - TRUE_V[1:6]) ** 2)))
print(f"  RMSE: MC={rmse(w_mc):.4f}  TD={rmse(w_td):.4f}")

代码做什么：上半部分用 8 条固定回合数据反复采样，分别跑运行平均步长的 Batch MC 与 Batch TD(0)，打印它们收敛到的 $V(A),V(B)$，并做初始化敏感性对照；下半部分在一个 5 状态随机游走上引入状态聚合（把 5 个状态压成 3 个参数），解析地求出 MC 的最小二乘解与 TD 不动点并比较。脚本存于 cs234/code/L03_batch_mc_td.py。

RL 机制透视：（1）AB 例子是「同一份数据、两个不同的问题」的干净演示——Batch MC 求的是最小二乘解，Batch TD 求的是 TD 不动点（等价于 MLE 模型上的 Bellman 解），两者只有在特殊情形下才相同（本例中 $B$ 恰好相同，因为 $B$ 之后立即终止）。（2）状态聚合把「函数逼近」的后果显式化：一旦参数共享，MC 与 TD 的解就分道扬镳，而且谁更接近真值并不固定——这修正了「TD 总是更好/更差」的直觉。

实验观察（完整脚本 python3 L03_batch_mc_td.py 的真实输出节选；上面代码块只保留了该脚本的 AB 例子与状态聚合两部分，省略了 Mars rover 手算校验与常数步长对照，因此直接粘贴运行上面这一块不会打印下表全部行——下表数值全部来自完整脚本，本机实测约 25 秒）：

AB 例子（gamma=1）：解析解 V(B)=6/8=0.75，V_MC(A)=0.00，V_TD(A)=0.75
  Batch MC   samples=3000    V(A)=0.0000  V(B)=0.7527
  Batch MC   samples=12000   V(A)=0.0000  V(B)=0.7554
  Batch MC   samples=30000   V(A)=0.0000  V(B)=0.7497
  Batch TD   samples=3000    V(A)=0.7469  V(B)=0.7470
  Batch TD   samples=12000   V(A)=0.7552  V(B)=0.7528
  Batch TD   samples=30000   V(A)=0.7505  V(B)=0.7487
  高精度极限（60000 采样 x 4 次重复）：
    Batch MC   V(A)=0.0000 ± 0.0000    V(B)=0.7491 ± 0.0014
    Batch TD   V(A)=0.7501 ± 0.0016    V(B)=0.7502 ± 0.0014
  初始化敏感性：
    Batch MC   init(0,0)->V(A)=0.0000    init(5,5)->V(A)=0.0000
    Batch TD   init(0,0)->V(A)=0.7507    init(5,5)->V(A)=0.7501

状态聚合（gamma=0.9, 组 {1,2}/{3}/{4,5}）
  真实 V[1:6] = [0.0655, 0.1456, 0.258, 0.4277, 0.6925]
  折扣访问分布 d = [0.0963, 0.214, 0.3793, 0.214, 0.0963]
  组 {1,2}: MC 最小二乘解=0.1207   TD 不动点=0.1456   真实组均值=0.1055
  组 {3}  : MC=0.2580              TD=0.2580           真实组均值=0.2580
  组 {4,5}: MC=0.5099              TD=0.4277           真实组均值=0.5601
  RMSE vs 真实 V：MC=0.0936   TD=0.1237
  采样仿真（10 次重复 x 20000 episode）：MC=0.1100/0.2576/0.5447  RMSE=0.0881
                                        TD=0.1424/0.2792/0.4868  RMSE=0.1021

几处值得逐字读的观察：

1. AB 例子的极限与理论值严丝合缝：Batch MC 给出 $V(A)=0.0000$（标准差 0），Batch TD 给出 $V(A)=0.7501\pm0.0016$，而 $V(B)$ 两者都收敛到 $0.75$。这正是讲义第 46–49 页 poll 的答案。
2. 初始化敏感性：把 $V$ 初值从 $(0,0)$ 改成 $(5,5)$，Batch MC 的 $V(A)$ 依然是 0.0000（它只依赖观测回报，与初值无关），而 Batch TD 从 0.7507 变到 0.7501——TD 的极限虽然不由初始化决定（有 $\alpha=1/N$ 时渐进无偏），但它在有限样本下会被初值牵引，这就是讲义说 TD「early on will be influenced by initialization」的量化版本。
3. 状态聚合下的分歧：只有单状态组 $\{3\}$ 两者完全相同（0.2580，因为「组均值」与「Bellman 解」在该组重合）。$\{1,2\}$ 组真实均值为 0.1055，MC 给 0.1207（偏差 0.015）、TD 给 0.1456（偏差 0.040），MC 更近；$\{4,5\}$ 组真实均值为 0.5601，MC 给 0.5099（偏差 0.050）、TD 给 0.4277（偏差 0.132），仍是 MC 更近。整体 RMSE 在本例中 MC（0.0936）小于 TD（0.1237）。这是一个诚实的提醒：「MC 与 TD 谁更接近真值」没有普适答案，取决于环境、聚合方式与访问分布；SB 教材例 9.1 的经典结论（TD 常更优）需要具体环境才成立，本实验恰好落在另一侧。
4. 采样仿真验证不动点理论：用真实采样（而非解析式）得到的 MC 值（0.1100/0.2576/0.5447）与解析最小二乘解（0.1207/0.2580/0.5099）、TD 采样值（0.1424/0.2792/0.4868）与解析 TD 不动点（0.1456/0.2580/0.4277）分别对应，方向与量级一致（采样版用常数步长 $\alpha=0.05$，存在稳态波动）。

3.5 评估指标与理论保证

讲义第 23 页给出了评估一个策略评估算法的五个维度，本节把它们与具体形式对应起来。

理论保证（具体形式）：

• 首次访问 MC 无偏性：对任意 $s$，$\mathbb{E}[V^\pi(s)]=V^\pi(s)$；由强大数定律，$N(s)\to\infty$ 时 $V^\pi(s)\xrightarrow{a.s.}V^\pi(s)$。
• 增量式（MC 与 TD 通用）的收敛条件：对每个状态 $s_j$，步长需满足

• TD(0) 的表格收敛性：在上述条件下 $V\to V^\pi$（等价地，$\mathcal{T}^\pi$ 是 $\gamma$-压缩，$\vert \mathcal{T}^\pi V-V^\pi\vert _\infty\le\gamma\vert V-V^\pi\vert _\infty$）。
• 函数逼近下的边界：$\gamma$-压缩性不再成立（半梯度丢弃了目标项对 $w$ 的导数），因此 TD(0) 在函数逼近下不一定收敛；而 MC 即使在函数逼近下仍一致（讲义第 56 页）。

条件依赖分析：

• 探索策略：本讲全部结论建立在同策略样本上（$a_t\sim\pi(\cdot\vert s_t)$）。若数据来自其他策略 $\mu$，MC 与 TD 的直接应用都会有偏，需要重要性采样（后续讲次）。
• 函数逼近：一旦从表格走向参数化，MC 仍一致、TD(0) 可能发散——这是 L4 中「致命三要素（function approximation + bootstrapping + off-policy）」紧张关系的起点。
• 在线 vs 离线：TD 与增量 MC 天然在线；Batch MC/TD 是离线版本，且收敛到不同的不动点。
• 回合制 vs 持续任务：MC 强制要求回合终止；TD 可用于无限时域非回合任务。

3.6 与其他讲次的关联

• 与 L2（有模型规划）：L2 的 $V^\pi_k(s)=r(s,\pi(s))+\gamma\sum_{s^{\prime}}p(s^{\prime}\vert s,\pi(s))V^\pi_{k-1}(s^{\prime})$ 是本讲三个算法的共同祖先。与它的两处偏离——用样本代替期望（MC/TD）与用 MLE 模型代替真模型（确定性等价）——构成本讲的整个结构。L2 的第 8 页已经点出那个求和替换是「an instance of bootstrapping」。
• 与 L4（无模型控制）：L4 开头即「Recap: MC, TD(0) and Certainty Equivalence Policy Evaluation」，并直接给出三者的更新式；随后把策略评估嵌入广义策略迭代（GPI），得到 MC 控制、SARSA、Q-learning。L4 还继续推进到值函数逼近（VFA）：MC VFA（第 48–49 页：对 $\langle(s,a),G_t\rangle$ 做监督学习）与 TD(0) VFA（第 51–54 页：目标换成 $r+\gamma\hat V(s^{\prime};w)$，并明确列出三种近似来源——采样、自举、函数逼近）。
• 与 L9–L12（数据高效 RL / 探索）：本讲的「确定性等价」正是 RMax、PSRL 等乐观/贝叶斯算法的模型学习组件；「样本复杂度与 regret」的评估框架在 L9 被正式引入。
• 与 L6–L7（策略梯度）：L7 会引入 GAE（广义优势估计），它本质上是优势函数的 $\lambda$-return/TD($\lambda$) 版本，是本节 3.2.8 的直接延伸。

3.7 关键要点

• 一句话记住三者的差别：MC 采样不自举（无偏、高方差、必须等回合结束）；TD(0) 采样且自举（有偏、低方差、可在线、利用马尔可夫结构）；确定性等价先学 MLE 模型再规划（最省数据、最费算力）。
• 更新范式统一：$V\leftarrow V+\alpha(\text{target}-V)$。MC 的 target 是 $G_t$，TD 的 target 是 $r_t+\gamma V(s_{t+1})$——换 target 就是换算法。
• Batch 设定下 MC 与 TD 收敛到不同解：MC → 最小二乘解（经验平均回报）；TD → MLE 模型上的 Bellman 不动点。AB 例子把这两者分别钉在 $0.00$ 与 $0.75$。
• TD 用初始化偏差换来效率：早期 TD 受初值影响（实验 ep=1 时 TD 的 RMSE 0.5371 反而是三者中最大的），但中期明显领先（ep=100 时 $0.0667$ vs 每次访问 MC 的 $0.1654$）。这是偏差-方差权衡的具体形状，也说明「无偏」并不等于「在有限数据下更准」。
• 收敛的硬条件：$\sum_n\alpha_n=\infty,\ \sum_n\alpha_n^2<\infty$。固定步长只保证「收敛到真值附近的一个邻域」，不保证收敛到真值——实验中 $\alpha=0.4$ 的稳态 RMSE 高于 $\alpha=0.05$。
• 半梯度是 TD 在函数逼近下失效的根源：丢掉了 $-\gamma\nabla_w\hat V(s^{\prime};w)$，压缩性不再成立；MC 在函数逼近下仍一致，TD 则不保证。

3.8 常见误区与注意事项

1. 误区：TD 一定比 MC 好（或一定更差）。 改正后的认识：二者是偏差-方差权衡的两端，优劣随数据量翻转。实验数据：ep=1 时 TD 的 RMSE（0.5371）最差、MC 更好（0.4806/0.5159）；ep=100 时 TD 最好（0.0667）；ep=200 时 TD 仍最好（0.0499）但首次访问 MC 已追到 0.0965。而在状态聚合实验中，整体 RMSE 反而是 MC（0.0936）优于 TD（0.1237）。选谁取决于数据量、是否回合制、是否要求无偏、以及是否有函数逼近。

2. 误区：TD 是有偏的，所以它收敛不到 $V^\pi$。 改正后的认识：偏差是有限样本/有限步长意义上的，目标里用的是估计值 $V(s_{t+1})$；在表格表示下，只要步长满足 $\sum_n\alpha_n=\infty$、$\sum_n\alpha_n^2<\infty$，TD(0) 就收敛到 $V^\pi$（实验：$\alpha=0.05$、2000 回合后平均估计 $[0.1493,0.3175,0.4917,0.6693,0.8379]$，RMSE 0.0114）。真正会破坏收敛的是函数逼近 + 自举 + 离策略的组合。

3. 误区：首次访问与每次访问 MC 只是实现细节，结果一样。 改正后的认识：统计性质不同——首次访问无偏，每次访问有偏但一致，且每个回合数据被利用得更充分、常常 MSE 更小。Mars rover 那条轨迹是干净的对照：首次访问给 $V(s_2)=\gamma^2=0.8100$，每次访问给 $(\gamma+\gamma^2)/2=0.8550$（$\gamma=0.9$）。

4. 误区：$\alpha=1$ 的 TD 一定会发散。 改正后的认识（讲义 L3N2 poll 的正确答案）：$\alpha=1$ 表示把 $V$ 直接置为 TD 目标；在存在多个可能后继状态的 MDP 上 $V$ 可能永远振荡，但存在确定性 MDP 使 $\alpha=1$ 的 TD 收敛。Mars rover 例子就是后者：$\alpha=1$、初值 0，一条轨迹后得到 $[1,0,0,0,0,0,0]$。

5. 误区：Batch MC 与 Batch TD 在无限次遍历数据后会收敛到同一个值。 改正后的认识：不会。AB 例子中 $V(A)$ 分别是 $0.0000$ 与 $0.7500$，两者都「正确」，只是回答的问题不同——MC 回答「训练集里观测到的平均回报」，TD 回答「数据所暗示的马尔可夫模型的真实值」。

6. 误区：$\alpha=1/N$ 与固定 $\alpha$ 无实质区别。 改正后的认识：$\alpha=1/N$ 使增量 MC 精确等价于每次访问 MC，收敛到经验平均；固定 $\alpha$ 则是指数遗忘的滑动平均，能跟踪非平稳环境（讲义 poll 中「$\alpha>1/N$ 在非平稳域有帮助」为真）。但注意：「增量 MC 在 $\alpha=1$ 时等价于首次访问 MC」是假。

7. 实现陷阱（写代码才会踩）：首次访问 MC 需要两遍处理——先正向标记每个状态首次被访问的时刻，再反向累积回报。若只在反向扫描时用一个 visited 集合去重，记录的其实是最后一次访问的回报，得到的是有偏结果（本笔记在开发该实验时因此把 $V(3)$ 算成 0.3796，而真实值是 0.2580；而 TD(0) 是单遍在线算法，不存在这个问题）。

3.9 思考题（带答案）

题 1（手算，MC vs TD 的差异）

Mars rover 环境：$R=[+1,0,0,0,0,0,+10]$（对应 $s_1..s_7$），$\pi(s)=a_1\ \forall s$，从 $s_1$ 或 $s_7$ 出发的任意动作终止回合。观测到单条轨迹

设 $\gamma=0.9$，$V$ 初值全为 0，TD 步长 $\alpha=1$。求（i）首次访问 MC 的 $V(s_1),V(s_2),V(s_3)$；（ii）每次访问 MC 的 $V(s_2)$；（iii）TD(0) 整条轨迹跑完后的 $V$ 向量。并解释为什么 TD 没有把 $1$ 折现传回 $s_2,s_3$。

答案。

(i) 反向累积回报（$\gamma=0.9$）：

首次访问：$s_1$ 首次出现在 $t=4\Rightarrow V(s_1)=1$；$s_2$ 首次出现在 $t=2\Rightarrow V(s_2)=G_{t=2}=0.81=\gamma^2$；$s_3$ 首次出现在 $t=1\Rightarrow V(s_3)=G_{t=1}=0.729=\gamma^3$。

(ii) 每次访问：$s_2$ 在 $t=2$（回报 0.81）与 $t=3$（回报 0.9）各被访问一次，故 $V(s_2)=(0.81+0.9)/2=0.8550$。

(iii) TD(0) 按时间顺序、$\alpha=1$（即 $V(s_t)\leftarrow r_t+\gamma V(s_{t+1})$），$V(\text{terminal})=0$：

得到 $V=[1,0,0,0,0,0,0]$。

为什么 TD 没有把 $1$ 传回去：TD 每次只用一步的奖励与后继估计来更新，信用（credit）每步只向后传播一个状态。在这条轨迹里，$s_1$ 收到奖励后立即终止，而 $s_2,s_3$ 的更新发生在 $s_1$ 拿到 $1$ 之前（它们当时看到的后继估计还是 0）。若把这条轨迹再跑一遍（或用更大的数据量），$V(s_2)$ 才会通过 $r+\gamma V(s_1)$ 逐步获得非零值——这正是 TD 的「延迟传播」特性。

题 2（推导：TD(0) 在表格下的不动点就是 $V^\pi$）

设数据由策略 $\pi$ 在 MDP $(\mathcal{S},\mathcal{A},P,R,\gamma)$ 上产生。把 TD(0) 更新写成期望算子形式，证明其不动点满足 $V=V^\pi$。

答案。对状态 $s$ 取 TD 更新的条件期望（固定 $V$，只对下一步的随机性取期望）：

当更新达到平稳（期望更新为 0，即方差趋于 0 的极限）时，对所有 $s$ 有 $(\mathcal{T}^\pi V)(s)=V(s)$，即 $V=\mathcal{T}^\pi V$。而 $\mathcal{T}^\pi$ 恰是 L2 的 Bellman 期望算子，其唯一不动点就是 $V^\pi$，因为

（$\gamma$-压缩，不动点唯一）。故表格下 TD(0) 收敛到 $V^\pi$。

关键提醒：上面的期望是对真实 $P$ 取的。在 batch 设定下只能用数据的 $\hat P$，于是不动点变成 $\hat V=\hat R+\gamma\hat P\hat V$，一般不等于 $V^\pi$（AB 例子中 $\hat V(A)=0.75$ 而 MC 给出的经验回报平均是 $0$）。

题 3（概念辨析：为什么 batch MC 与 batch TD 不同，以及 $V^*(A)$ 到底是多少）

仍用 AB 例子（$\gamma=1$，数据：$A,0,B,0$ 一次；$B,1$ 六次；$B,0$ 一次）。回答：（i）两者给出的 $V(A)$ 各是多少？（ii）如果我们把「$B$ 之后有 $3/4$ 概率得 1」当作真实模型，$V(A)$ 应是多少？（iii）这个例子说明了 MC 与 TD 各自的隐含假设是什么？

答案。

(i) Batch MC（$\alpha=1/N$ 或任意衰减步长）收敛到经验平均：唯一经过 $A$ 的回合给回报 $0+\gamma\cdot 0=0$，故 $V_{\text{MC}}(A)=0$。Batch TD 收敛到 TD 不动点，$V(B)=6/8=0.75$ 后由 $V(A)\leftarrow 0+\gamma V(B)$ 得 $V_{\text{TD}}(A)=0.75$。

(ii) $V(A)=0+\gamma\cdot 0.75=0.75$。

(iii) MC 的隐含假设：只关心观测到的数据本身，不做任何外推——它把「这条回合里 $B$ 恰好得了 0」当作 $B$ 价值的证据。TD 的隐含假设：数据来自一个马尔可夫过程，因此可以从 $B$ 的多条独立观测中「拼」出 $B$ 的期望值（$0.75$），再把 $A$ 的期望回报通过一步转移关系外推出来。这个例子最锋利的含义是：TD 在本例中给出了 $V(A)$ 的正确（MLE 意义下）估计，而 MC 给出的是「数据里 A 的回报平均」——两者都不错，但 TD 更接近我们通常想知道的量。反过来，如果状态不满足马尔可夫性，TD 的这种外推就会带来系统误差。

题 4（计算：步长与 $\lambda$-return）

（i）给定 $\sum_{n=1}^\infty\alpha_n=\infty$、$\sum_{n=1}^\infty\alpha_n^2<\infty$，判断 $\alpha_n=1/n$、$\alpha_n=0.1$、$\alpha_n=1/n^2$ 哪些满足收敛条件。（ii）已知 $\lambda$-return $G_t^\lambda=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)}$，验证 $\lambda=0$ 时为 TD(0) 目标、$\lambda=1$ 时为完整回报 $G_t$。

答案。

(i) $\alpha_n=1/n$：$\sum 1/n$ 发散（调和级数），$\sum 1/n^2=\pi^2/6<\infty$——满足。$\alpha_n=1/n^2$：$\sum 1/n^2<\infty$，第一个条件不满足——不满足（会学得过慢，可能到不了真值）。$\alpha_n=0.1$ 常数：$\sum 0.1=\infty$ 但 $\sum 0.01=\infty$——不满足，因此常数步长的 TD/MC 只保证收敛到真值附近的一个邻域（这与实验中 $\alpha=0.4$ 的稳态 RMSE 高于 $\alpha=0.05$ 一致）。

(ii) $\lambda=0$ 时，$(1-\lambda)\sum_{n\ge1}\lambda^{n-1}G_t^{(n)}$ 中只有 $n=1$ 项系数为 1（因为 $\lambda^{0}=1$，其余含 $\lambda^{n-1}=0$），故 $G_t^{\lambda}=G_t^{(1)}=r_t+\gamma V(s_{t+1})$，正是 TD(0) 目标。$\lambda=1$ 时，$(1-1)\sum\cdots$ 出现 $0\cdot\infty$ 形式，需取极限：$\sum_{n=1}^{N}\lambda^{n-1}=(1-\lambda^N)/(1-\lambda)$，故

即退化为一整条轨迹的回报。于是 $\lambda$ 在 $[0,1]$ 上连续地把 TD(0)（低方差、有偏）插值到 MC（无偏、高方差）。

附：本讲涉及的实验脚本

• cs234/code/L03_mc_vs_td.py —— 随机游走上的 MC/TD 学习曲线与步长敏感性（约 27 秒）
• cs234/code/L03_batch_mc_td.py —— AB 例子（Batch MC vs Batch TD）、Mars rover 手算校验、状态聚合不动点（约 25 秒）