逼近动态规划与TD学习¶
前置自测¶
📋 前置自测（答不出 ≥ 2 题 → 先回 §6.1 精确动态规划 复习）
- Bellman 最优算子 \(T^*\) 为什么在 sup-norm 下是 \(\gamma\)-压缩？写出证明的关键步骤。
- 策略迭代（PI）与值迭代（VI）各自的收敛性依赖哪些前提条件？
- 什么是 Robbins-Monro 条件？给出步长 \(\alpha_t = 1/t\) 满足该条件的验证。
- 蒙特卡洛估计的核心思想是什么？期望与样本均值之间的关系是什么？
- 给定策略 \(\pi\) 下的状态价值函数 \(V^\pi(s)\) 的 Bellman 期望方程是什么？
本章目标¶
学完本章后，你将能够： 1. 从数学本质上理解 TD 学习——它不是"改进版 MC"，而是 Bellman 方程的在线随机逼近求解器，其收敛性与发散性都有精确的数学刻画。 2. 手推 Tsitsiklis-Van Roy 1997 定理的完整证明——理解投影 Bellman 算子在加权范数下的压缩性，以及 on-policy 条件为何不可或缺。 3. 诊断任何 RL 算法的稳定性问题——用致命三元组的框架判断是 FA、bootstrap 还是 off-policy 在作祟。 4. 理解 DQN 家族每一条设计的数学动机——target network、replay buffer、Double Q、Dueling、PER 各对症下药哪个数学病理。
知识树总览¶
逼近动态规划与TD学习
├── §6.3.1 从精确DP到逼近DP（动机与范式）
├── §6.3.2 蒙特卡洛方法（MC）
│ ├── First-visit / Every-visit
│ ├── 增量式更新与随机近似
│ └── 偏差-方差特性
├── §6.3.3 TD(0)：bootstrapping的艺术
│ ├── TD误差的数学含义
│ ├── 偏差-方差权衡完整分析
│ └── TD vs MC vs DP 三角关系
├── §6.3.4 TD(λ)与eligibility traces
│ ├── n-step return
│ ├── λ-return（前向视图）
│ ├── 资格迹（后向视图）
│ └── 前向/后向视图等价性
├── §6.3.5 SARSA vs Q-learning
│ ├── On-policy vs Off-policy 数学区别
│ ├── Expected SARSA
│ └── Cliff Walking 经典对比
├── §6.3.6 Tabular收敛性定理
├── §6.3.7 线性函数逼近与TVR定理（核心）
│ ├── 投影Bellman算子
│ ├── MSPBE/MSBE/TDE目标函数关系
│ └── 逼近误差界
├── §6.3.8 致命三元组与Baird反例
├── §6.3.9 DQN系列
│ ├── 经验回放（iid近似）
│ ├── 目标网络（半梯度稳定性）
│ ├── Double DQN（过估计修正）
│ └── Dueling / PER / Rainbow
├── §6.3.A GTD/TDC算法
├── §6.3.B LSTD/LSPI
├── §6.3.C Retrace(λ)与V-trace
└── §6.3.D Distributional RL
§6.3.1 从精确DP到逼近DP：动机与范式 ⭐¶
动机：维度诅咒迫使我们放弃查表¶
在 §6.1 中，我们建立了精确动态规划的优美理论：Bellman 算子 \(T^\pi\)、\(T^*\) 在 sup-norm 下是 \(\gamma\)-压缩，值迭代（VI）与策略迭代（PI）由 Banach 不动点定理保证几何收敛。然而这座理论大厦有一个致命前提——状态空间必须可枚举、转移核必须已知、策略必须能用查表存储。
一旦脱离这个乌托邦，无论是 Atari 游戏（\(10^{10000}\) 量级状态）还是机械臂末端位姿（连续高维），精确 DP 立刻崩塌。这就是 Bellman 本人在 1957 年所说的**维度诅咒（curse of dimensionality）**——状态空间随维度呈指数增长，存储与计算复杂度同时失控。
如果不引入逼近会怎样¶
考虑一个 7 自由度机械臂，每个关节的角度和角速度构成 14 维连续状态空间。如果我们天真地将每个维度离散化为 100 个格点，总状态数为 \(100^{14} = 10^{28}\)。用查表法存储 \(V(s)\) 需要 \(10^{28}\) 个浮点数——即使每个只用 4 字节，也需要 \(4 \times 10^{19}\) GB 存储，远超人类已制造的全部硬盘容量之和。
更严重的是，即使我们有无限存储，每个状态至少需要被访问一次才能更新其值。在 14 维空间中均匀覆盖 \(10^{28}\) 个格点所需的样本量，即使以每秒 \(10^6\) 次采样的速度，也需要 \(10^{22}\) 秒——比宇宙年龄还长 4 个数量级。
本质洞察：维度诅咒不是"困难"而是"不可能"。它不是说查表法慢，而是说在合理的物理时间和空间约束下，查表法**原理上不可行**。逼近不是"优化"而是"必须"。
逼近动态规划的三种近似¶
逼近动态规划（Approximate Dynamic Programming, ADP） 的核心思路（Bertsekas 2012《Dynamic Programming and Optimal Control, Vol. II》与 Bertsekas 2019《Reinforcement Learning and Optimal Control》）是用参数化函数 \(V_\theta\) 或 \(Q_\theta\) 代替查表，通常 \(\theta \in \mathbb{R}^d\) 且 \(d \ll |\mathcal{S}|\)。所有 TD 类算法都可纳入这一范式：
| 近似类型 | 含义 | 引入的代价 |
|---|---|---|
| 采样（Sampling） | 用样本均值近似期望 | 方差 |
| 逼近（Approximation） | 用参数函数近似值函数 | 逼近偏差 |
| 迭代（Iteration） | 用有限步迭代近似精确不动点 | 迭代误差 |
这三种"近似"中每一种都会引入偏差或方差，而 TD 学习的理论核心就是**分析这些近似叠加后的稳定性**。类比建筑工程：采样是地基的微小不平整，逼近是梁柱截面的简化，迭代是未完全固化的混凝土。单独来看每个近似都可控，但三者叠加后，某些组合下结构会突然失稳——这就是后面致命三元组要讲的故事。
Bertsekas 的 ADP 三条路径¶
Bertsekas 将 ADP 分为三条路径：
- 逼近值迭代（Fitted VI）：每步先做精确 \(T^*V\)（或对其采样近似），再将结果拟合（回归/投影）到参数空间。代表：DQN 的内循环本质上是 fitted Q-iteration。
- 逼近策略迭代（Fitted PI、LSPI、API）：策略评估用 LSTD/TD 求近似 \(Q^\pi\)，策略提升用 greedy。代表：LSPI（Lagoudakis-Parr 2003）。
- 在线 TD 类（TD(0)、TD(λ)、SARSA、Q-learning）：不显式存储完整值函数，每个样本到来时增量更新参数。代表：本专题的主线。
本专题主要走第三条路径，但 §6.3.B 的 LSTD/LSPI 会回到第二条。
逼近 DP 的哲学：精确性 vs 可计算性¶
本质洞察：ADP 的哲学是一种深刻的工程权衡——我们用"近似但可计算的答案"替代"精确但不可计算的答案"。这不是退而求其次，而是唯一可行的道路。正如数值分析中有限元法用分段线性函数近似 PDE 解，ADP 用参数化函数近似 Bellman 方程的不动点。关键问题不是"能不能精确解"，而是"近似误差有多大、能否控制"。
类比：ADP 之于精确 DP，犹如有限元方法（FEM）之于解析解。精确 DP 给出 \(V^* = T^* V^*\) 的解析不动点（如果可以枚举所有状态），就像 PDE 有时有解析解。但大多数实际问题没有解析解——你必须在有限维子空间中寻找"尽可能好"的近似。FEM 在 Sobolev 空间中做加权投影，ADP 在特征空间中做加权投影——数学结构完全平行。
TD 学习在 ADP 中的历史定位¶
TD 学习不是凭空出现的。它的发展脉络是： - 1957: Bellman 提出动态规划，同时指出维度诅咒 - 1959: Samuel 的跳棋程序使用了 TD 的雏形（temporal credit assignment） - 1972: Klopf 提出"自适应预测"假说，影响了 Sutton - 1988: Sutton 正式定义 TD(λ)，证明了表格收敛性 - 1989: Watkins 提出 Q-learning，开创 off-policy 路径 - 1992: Watkins-Dayan 证明 Q-learning 收敛 - 1995: Baird 揭示致命三元组 - 1997: Tsitsiklis-Van Roy 建立线性 FA 下的完整理论 - 2013-2015: DQN 将 TD 推向深度学习时代 - 2015-2020: PPO + GAE 成为机器人 RL 的标准配置
每一步都是对前一步局限性的回应——理解这个演进脉络有助于理解每个方法"为什么要这样设计"。
练习¶
- 计算一个状态空间为 \(\mathbb{R}^{20}\)（每维离散为 50 格点）的系统，查表法需要多少存储？与 \(d = 100\) 的线性逼近器相比，存储压缩了多少倍？
- 解释为什么 Bellman 算子 \(T^*\) 在有限维子空间上的投影不再保证是压缩映射（提示：投影可能"放大"某些方向的误差）。
- 列举 ADP 的三种近似（采样、逼近、迭代）各自引入的误差类型，并解释为什么 on-policy TD(0) 在 tabular 情形下三种误差中只有采样误差（逼近误差和迭代误差为零）。
§6.3.2 蒙特卡洛方法（MC）⭐⭐¶
动机：最朴素的 model-free 策略评估¶
在引入 TD 学习之前，我们首先理解最简单的 model-free 方法。蒙特卡洛方法的核心思想极其朴素：既然 \(V^\pi(s) = \mathbb{E}[G_t | S_t = s]\) 是一个期望，那就用大量样本的平均来近似它。这正是数理统计中大数定律的直接应用——期望等于无限多次实验结果的平均。
回顾 §6.1：策略 \(\pi\) 的状态值定义为折扣回报的期望 $\(V^\pi(s) = \mathbb{E}_\pi\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \,\bigg|\, S_t = s\right] = \mathbb{E}_\pi[G_t | S_t = s]\)$
蒙特卡洛方法生成完整 episode \((S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T)\)，然后用经验回报 \(G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}\) 作为 \(V^\pi(S_t)\) 的估计。
First-visit MC vs Every-visit MC¶
一个 episode 中状态 \(s\) 可能被多次访问。处理方式有两种：
First-visit MC：仅统计 episode 中状态 \(s\) 第一次**被访问时的回报。数学上，对于第 \(i\) 个 episode 中 \(s\) 第一次出现的时刻 \(t_i\)，有 $\(V(s) \approx \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_{t_i}\)$ 这是 \(V^\pi(s)\) 的**无偏估计（由大数定律保证收敛）。
Every-visit MC：统计 episode 中 \(s\) **每次**被访问的回报。由于同一 episode 内的多次访问之间存在相关性，every-visit MC 是有偏估计——但偏差随样本数趋于零（Singh-Sutton 1996 证明了一致收敛性）。
增量式 MC 更新¶
批量计算均值需要等待所有数据收集完成。更实用的方式是增量式更新：
这个公式的含义是：每当观察到一个新的回报 \(G_t\)，就将 \(V(S_t)\) 朝 \(G_t\) 方向移动一步。当 \(\alpha = 1/N(S_t)\)（\(N(S_t)\) 为 \(S_t\) 被访问的次数）时，这精确等价于样本均值。当 \(\alpha\) 为常数时，它给近期样本更高权重——这在非平稳环境中反而是优势。
这个增量更新公式实际上就是 Robbins-Monro 随机近似算法的一个特例。回顾 §6.1 中均值估计的迭代形式 \(w_{k+1} = w_k - \frac{1}{k}(w_k - x_k)\)，MC 更新与之完全同构。
MC 的偏差-方差特性¶
MC 估计的核心特性：
| 性质 | MC 估计 | 数学原因 |
|---|---|---|
| 偏差 | 无偏（first-visit）或渐近无偏（every-visit） | $\mathbb{E}[G_t |
| 方差 | 高，\(\mathrm{Var}(G_t) = \mathcal{O}\left(\frac{\sigma_r^2}{(1-\gamma)^2}\right)\) | \(G_t\) 包含 \(T-t\) 个随机变量的加权和 |
| 收敛速率 | \(\mathcal{O}(1/\sqrt{n})\)（标准 MC 速率） | 中心极限定理 |
方差的来源可以精确分析。设每步奖励 \(R_t\) 的方差为 \(\sigma_r^2\)，则 $\(\mathrm{Var}(G_t) = \mathrm{Var}\left(\sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\right) \leq \sum_{k=0}^{\infty} \gamma^{2k} \sigma_r^2 = \frac{\sigma_r^2}{1 - \gamma^2}\)$
当 \(\gamma\) 接近 1 时（如 \(\gamma = 0.99\)），方差约为 \(50\sigma_r^2\)——比单步估计大 50 倍！这就是 MC 方差高的本质原因：它把整个 episode 的随机性全部堆叠在一个估计量中。
为什么 MC 在机器人 episode-based 任务上仍实用¶
尽管 MC 方差高，在以下场景中它仍是合理选择：
- Episode 可控（PPO 的 rollout horizon 通常 256-2048 步）——有限步累积的方差不至于失控。
- Reward 不太稀疏——每步都有信号，方差不会被少数高回报 episode 主导。
- 希望避免 bootstrap 引入的系统偏差——在 sim-to-real 中，bootstrap 的偏差可能因仿真误差而被放大。
legged_gym（Rudin 2021）和 Isaac Lab 的 PPO critic 训练本质就用接近 MC 的 GAE（\(\lambda \in [0.95, 0.99]\)）——当 \(\lambda \to 1\) 时 GAE 退化为纯 MC。
本质洞察：MC 方法的哲学是"宁可等久一点得到准确答案，也不要立即得到可能有系统偏差的答案"。TD 方法的哲学是"快速但有偏好过缓慢但无偏"。两种哲学各有适用场景——MC 适合短 episode 或对偏差敏感的任务，TD 适合长 episode 或需要在线学习的任务。
MC 方法的适用条件与局限¶
MC 方法有明确的适用边界：
适用的情况： - Episode 有限长且可等到结束（episodic tasks） - 不需要在线实时更新（可以离线学习） - 对偏差零容忍但对方差有一定容忍度 - 数据充足（可以用大量 episode 降低方差）
不适用的情况： - Continuing tasks（无终止状态，如机器人持续运行） - 需要每步在线更新（如实时控制） - Episode 极长（\(T > 1000\)，方差不可控） - 数据昂贵（如真机实验）
如果不考虑 MC 的局限直接使用会怎样：假设一个四足机器人的控制任务没有明确的"终止"——机器人持续运行。如果强行定义 \(T = 10000\) 步的 episode，MC 的回报方差约为 \(\sigma_r^2 / (1-\gamma^2) \approx 50\sigma_r^2\)（\(\gamma = 0.99\)），而 TD(0) 的方差仅约 \(2\sigma_r^2\)。这意味着 MC 需要约 25 倍的数据才能达到 TD 同样的精度——在真机实验中这可能意味着数周 vs 数小时的差距。
蒙特卡洛 ε-Greedy 与探索-利用权衡¶
从策略评估到策略控制，MC 需要估计动作价值 \(Q^\pi(s,a)\) 而非 \(V^\pi(s)\)。但如果策略 \(\pi\) 是确定性的，很多 \((s,a)\) 对永远不会被访问，无法估计其 \(Q\) 值。
解决方案是 \(\varepsilon\)-greedy 策略： $\(\pi(a|s) = \begin{cases} 1 - \varepsilon + \frac{\varepsilon}{|\mathcal{A}(s)|}, & a = \arg\max_{a'} Q(s,a') \\ \frac{\varepsilon}{|\mathcal{A}(s)|}, & \text{otherwise} \end{cases}\)$
这平衡了**利用（Exploitation）——执行当前认为最好的动作，与**探索（Exploration）——尝试其他动作以发现更好的选择。
GLIE 条件（Greedy in the Limit with Infinite Exploration）保证 MC 控制的收敛：要求 \(\varepsilon_k \to 0\)（最终变贪婪）但 \(\sum_k \varepsilon_k = \infty\)（保证无限探索）。典型选择 \(\varepsilon_k = 1/k\) 同时满足两个条件。
⚠️ 常见陷阱¶
💡 概念误区：认为"MC 无偏所以比 TD 好"
错误理解：既然 MC 无偏，偏差为 0，那它的估计一定比有偏的 TD 更准。
实际上：均方误差 = 偏差² + 方差。MC 偏差为 0 但方差可能极大；TD 有偏差但方差小得多。在有限样本下，低方差的有偏估计往往比高方差的无偏估计**更接近真值**。这就是统计学中经典的偏差-方差权衡。
正确认识：选择 MC 还是 TD 取决于具体场景——episode 短且数据充足选 MC；episode 长或需要在线学习选 TD。
🧠 思维陷阱：认为"MC 只能用于 episodic 任务"
新手想法：MC 需要完整 episode 的回报 \(G_t\)，所以 continuing task 无法使用。
实际上：可以通过人为截断来使用——设定最大步数 \(T_{\max}\)，用截断回报 \(\hat{G}_t = \sum_{k=0}^{T_{\max}-1} \gamma^k R_{t+k+1}\) 近似。PPO 的 rollout 就是这样做的。截断引入偏差但使方差可控。
MC 方法的 Robbins-Monro 视角¶
增量式 MC 更新 \(V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]\) 可以写成 Robbins-Monro 随机近似的标准形式：
其中 \(\theta_t = V_t(s)\)，\(\tilde{g}(\theta, \eta) = \theta - G_t\)（含噪声的梯度），目标方程是 \(g(\theta) = \theta - \mathbb{E}[G_t|S_t = s] = \theta - V^\pi(s) = 0\)。
这个视角揭示了 MC 收敛的数学本质：它是在求解方程 \(V(s) = V^\pi(s)\) 的随机逼近。每个样本 \(G_t\) 提供了真解 \(V^\pi(s)\) 的一个有噪声观测，算法逐步逼近真解。
与 TD 的 RM 视角对比：TD(0) 也是 RM 算法，但它求解的方程不同——是 Bellman 方程 \(V(s) = \mathbb{E}[R + \gamma V(S')|S = s]\)，而非直接的定义式。这就是为什么 TD 需要 \(V(S_{t+1})\)（自身估计）参与：因为 Bellman 方程本身就包含 \(V\)。
MC 与 TD 的统一：随机近似的两种实例化¶
从 RM 的统一视角看，MC 和 TD 的区别仅在于"观测的构造方式"：
| 算法 | 求解的方程 | 观测（噪声梯度） | 噪声来源 |
|---|---|---|---|
| MC | \(V(s) - \mathbb{E}[G_t] = 0\) | \(V(s) - G_t\) | 整个轨迹随机性 |
| TD(0) | \(V(s) - \mathbb{E}[R + \gamma V(S')] = 0\) | \(V(s) - [R + \gamma V(S')]\) | 单步随机性 + bootstrap 误差 |
两者都在 Robbins-Monro 条件下收敛到对应方程的解。区别是：MC 的方程解恰好是 \(V^\pi\)；TD 的方程解在 tabular 下也是 \(V^\pi\)（因为 Bellman 方程的解唯一），但在 FA 下是投影 Bellman 不动点（可能不等于 \(V^\pi\) 的最优投影）。
练习¶
- 对一个 episode 长度为 \(T = 100\)、\(\gamma = 0.99\)、\(|R_t| \leq 1\) 的任务，计算 MC 回报估计 \(G_t\) 的方差上界。与 TD(0) 的单步 target 方差比较。
- 解释为什么 MC ε-greedy 在 Cliff Walking 任务中会选择远离悬崖的安全路径，而 Q-learning 会选择贴悬崖的最短路径。
- 从 Robbins-Monro 视角，解释为什么常数步长 \(\alpha\) 的 MC 不再是无偏估计器（提示：常数步长等价于指数加权移动平均，给近期样本更高权重）。
§6.3.3 TD(0)：bootstrapping的艺术 ⭐⭐¶
动机：为什么要等到 episode 结束¶
MC 方法有一个根本性的限制：必须等到 episode 结束才能获得 \(G_t\) 并更新。这意味着： - 在 continuing task（无终止状态）中完全无法使用 - 在长 episode 中（如数千步的机器人控制），信息传播极慢 - 每步奖励信号要被"稀释"到整个 episode 的所有状态中
TD(0) 的灵感来自一个极简观察：既然 \(V^\pi(s) = \mathbb{E}[R_{t+1} + \gamma V^\pi(S_{t+1}) | S_t = s]\)（Bellman 方程），那为什么不直接用 \(R_{t+1} + \gamma V(S_{t+1})\) 作为 \(V(S_t)\) 的估计目标？
这正是 Sutton 1988《Learning to Predict by the Methods of Temporal Differences》（Machine Learning, Vol. 3, pp. 9-44）的核心思想——用当前已有的估计 \(V(S_{t+1})\) "自举（bootstrap）"来构造目标，无需等待 episode 结束。
TD(0) 更新规则¶
定义 TD 误差（TD error）： $\(\delta_t \triangleq R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\)$
这个 \(\delta_t\) 是整个 RL 理论中最重要的"信号"——它在不同场景下扮演不同角色：
| 场景 | \(\delta_t\) 的角色 |
|---|---|
| Critic 训练 | 值函数回归的损失梯度 |
| Actor-Critic | Policy gradient 的 advantage 近似 |
| GAE | \(\lambda\)-加权的 TD 误差序列 |
| Kalman Filter | Innovation（新息） |
| DQN loss | Huber/MSE 损失的核心项 |
Bootstrapping 的数学含义¶
Bootstrapping 字面意思是"拔靴自助"——用自己举起自己。在 TD 学习中，它指的是**用 \(V\) 的当前估计来构造 \(V\) 的更新目标**。这看起来像循环论证，但数学上是严格合理的。
为什么 bootstrapping 能工作？关键在于 TD target \(R_{t+1} + \gamma V(S_{t+1})\) 中包含了**一个真实数据点 \(R_{t+1}\)**。这个真实奖励就像锚点，即使 \(V(S_{t+1})\) 不准确，\(R_{t+1} + \gamma V(S_{t+1})\) 也"部分地"包含了真实信息。
用类比来说明：想象你在一栋不熟悉的大楼里，不知道从当前楼层到一楼需要走多少级台阶（这是 \(V(S_t)\) 的真值）。MC 方法是让你真的走完全部台阶才告诉你答案。TD 方法是：你走下一层（获得真实的 \(R_{t+1}\)），然后看一眼楼层标示牌（\(V(S_{t+1})\)，虽然可能不太准），用"走了一层的台阶数 + 标示牌说的剩余台阶数"来更新你对总台阶数的估计。标示牌可能有误差，但**每次你真的走了一层，就获得了一个无法伪造的真实观测**。
本质洞察：Bootstrapping 的本质不是"用猜测估计猜测"（那会永远不收敛），而是"用一部分真实数据 + 一个猜测来改进另一个猜测"。真实数据（\(R_{t+1}\)）是收敛的驱动力，猜测（\(V(S_{t+1})\)）是信息传播的加速器。没有真实数据的 bootstrapping 不会收敛，有真实数据的 bootstrapping 通常比纯采样更快。
MC vs TD 的偏差-方差权衡完整分析¶
这是理解 TD 学习最核心的理论问题。
MC 回报 \(G_t\) 的性质： - 无偏：\(\mathbb{E}[G_t | S_t = s] = V^\pi(s)\)（直接由定义） - 高方差：\(G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots\) 包含 \(T-t\) 个随机变量 - 每个 \(R_{t+k+1}\) 依赖于随机的 \(A_{t+k}\)（策略随机性）和随机的 \(S_{t+k+1}\)（转移随机性） - 这些随机性**链式累积**，导致总方差 \(\mathrm{Var}(G_t) = \mathcal{O}(\sigma_r^2 / (1-\gamma^2))\)
TD target \(R_{t+1} + \gamma V(S_{t+1})\) 的性质： - 有偏：\(\mathbb{E}[R_{t+1} + \gamma V(S_{t+1}) | S_t = s] \neq V^\pi(s)\)（除非 \(V = V^\pi\)） - 偏差 = \(\gamma \mathbb{E}[V(S_{t+1}) - V^\pi(S_{t+1}) | S_t = s]\)，即下一状态的估计误差 - 低方差：只包含**一步**随机性（一个动作 \(A_t\) 和一个转移 \(S_{t+1}\)） - \(\mathrm{Var}(R_{t+1} + \gamma V(S_{t+1}) | S_t) = \sigma_{r|s}^2 + \gamma^2 \mathrm{Var}_{s'}[V(s')]\)
数学对比：
当 \(n\) 较小时（有限样本），TD 的低方差优势压过偏差劣势——这就是为什么**在绝大多数实际问题中 TD 比 MC 收敛更快**。Watkins 1989 博士论文《Learning from Delayed Rewards》（Cambridge King's College）详细分析了这一点。
如果不使用 bootstrapping 会怎样： 在一个 episode 长度为 1000 步、\(\gamma = 0.99\) 的任务中，MC 的回报方差约为 \(50\sigma_r^2\)。如果用 TD(0)，单步 target 的方差仅约为 \(\sigma_r^2 + 0.99^2 \cdot \mathrm{Var}[V(S_{t+1})] \approx 2\sigma_r^2\)（假设 \(V\) 已相对准确）。方差降低了 25 倍！代价是引入了偏差——但这个偏差会随着 \(V\) 逼近 \(V^\pi\) 而趋于零。
TD vs MC vs DP：backup 三角关系¶
Sutton-Barto 2018 第 8 章用一个统一框架描述三类方法：
| 方法 | Sampling? | Bootstrapping? | 需要模型? | 更新基础 |
|---|---|---|---|---|
| DP | 否（完整期望） | 是 | 是 | 所有后继状态的加权和 |
| MC | 是（采样轨迹） | 否 | 否 | 完整 episode 回报 |
| TD | 是（采样转移） | 是 | 否 | 一步转移 + 估计 |
TD 是 MC 和 DP 的**杂交（hybrid）**——从 MC 借来了 sampling（不需要模型），从 DP 借来了 bootstrapping（不需要等 episode 结束）。
TD 误差的深层含义¶
TD 误差 \(\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\) 有丰富的解读：
解读1（Bellman 残差的采样版）：如果 \(V = V^\pi\)，则 \(\mathbb{E}[\delta_t | S_t] = 0\)——因为 Bellman 方程精确成立。所以 \(\delta_t \neq 0\) 意味着 \(V \neq V^\pi\)，\(\delta_t\) 量度了"Bellman 方程的违反程度"。
解读2（新信息）：\(\delta_t\) 代表了 agent 从经验 \((S_t, R_{t+1}, S_{t+1})\) 中获得的"新信息"或"惊讶度"。如果 \(V\) 是完美的预测器，那每次转移都"不意外"（\(\delta_t = 0\)）。非零 \(\delta_t\) 说明实际观测偏离了预测——这正是"时序差分"这个名字的由来。
解读3（与 Kalman Filter innovation 的类比）：在 Kalman filter 中，innovation \(y_t - H_t \hat{x}_t\) 衡量观测与预测的偏差；TD 误差 \(\delta_t\) 完全类似——它衡量"实际获得的一步回报 + 下一状态估计"与"当前状态估计"之间的偏差。这个深刻类比（Bertsekas-Tsitsiklis 1996 Ch.6）将在控制理论映射部分详细展开。
Semi-gradient 的深层含义¶
TD(0) 的更新方向 \(\delta_t \phi(S_t)\) 被称为**半梯度（semi-gradient）**。为什么"半"？
考虑均方 Bellman 误差 \(L(\theta) = \frac{1}{2}\mathbb{E}[(V_\theta(S) - T^\pi V_\theta(S))^2]\)。其完整梯度为： $\(\nabla L = \mathbb{E}[\delta \cdot (\nabla V_\theta(S) - \gamma\nabla V_\theta(S'))] = \mathbb{E}[\delta\cdot(\phi(S) - \gamma\phi(S'))]\)$
但 semi-gradient TD 只用了 \(\mathbb{E}[\delta\cdot\phi(S)]\)——丢弃了 \(-\gamma\phi(S')\) 项。
为什么要丢弃？
-
Double Sampling 问题：完整梯度中 \(\delta = R + \gamma V(S') - V(S)\) 包含 \(S'\)，而梯度中也有 \(S'\)——两者是同一个随机变量。用单个样本估计 \(\mathbb{E}[\delta\cdot\phi(S')]\) 时，\(\delta\) 和 \(\phi(S')\) 不独立，估计有偏。除非有环境模型能从同一个 \((S, A)\) 采两个独立的 \(S'\)（double sampling），否则无法无偏估计完整梯度。
-
Semi-gradient 更快收敛：虽然 semi-gradient 不是任何损失的真梯度，但它指向 Bellman 不动点——而且在 on-policy 线性 FA 下收敛**更快**于 residual gradient（Baird 1995 的完整梯度方法）。直觉是：semi-gradient 利用了 Bellman 方程的"因果结构"（当前状态影响下一状态，但不反过来），而 residual gradient 忽略了这个结构。
-
DQN loss 中的
detach()：PyTorch 中target = r + gamma * Q(s_next).detach()正是实现 semi-gradient——断开 target 中 \(\theta\) 的梯度流。如果不 detach，就变成了 residual gradient——理论上可能更好（真梯度），但实践中几乎总是更差（收敛慢、需 double sampling）。
本质洞察：Semi-gradient 不是"偷懒省略了一半梯度"，而是"巧妙利用了 Bellman 方程的递归结构"。这个递归结构使得"追逐移动目标"反而比"固定目标梯度下降"更高效——代价是理论分析从标准优化变成了非标准动力系统分析。
TD(0) 收敛性的直觉¶
为什么 TD(0) 能收敛到正确答案？直觉上：
这将 \(V(S_t)\) 朝 TD target \(\bar{v}_t\) 的方向移动。如果当前 \(V\) 低于真值，\(\bar{v}_t\) 倾向于大于 \(V(S_t)\)（因为 \(\bar{v}_t\) 部分包含真实信息），推动 \(V\) 上升；反之亦然。关键数学保证是：在 \(V = V^\pi\) 处，\(\mathbb{E}[\delta_t] = 0\)——不动点恰好在真解位置。
更严格地： $\(|V_{t+1}(S_t) - \bar{v}_t| = |1 - \alpha_t| \cdot |V_t(S_t) - \bar{v}_t|\)$
由于 \(0 < \alpha_t < 1\)，每次更新都严格缩小 \(V(S_t)\) 与 target 之间的距离。虽然 target 本身也在变（因为 \(V(S_{t+1})\) 也在更新），但在 Robbins-Monro 条件下，"追逐移动目标"的噪声最终被步长衰减吸收。
⚠️ 常见陷阱¶
⚠️ 编程陷阱：忘记对 TD target 做 stop_gradient
错误做法：在 PyTorch 中直接写
loss = (V(s) - (r + gamma * V(s_next)))**2然后.backward()现象：梯度同时穿过 \(V(S_t)\) 和 \(V(S_{t+1})\)，变成了 MSBE 的梯度而非 semi-gradient TD。在某些情况下反而发散更快。
根本原因：TD(0) 是 semi-gradient 方法——只对 prediction \(V(S_t)\) 求梯度，不对 target 中的 \(V(S_{t+1})\) 求梯度。这不是"偷懒"而是刻意设计：如果对 target 也求梯度，算法变成 Residual TD（Baird 1995），虽然是真梯度但收敛到 MSBE 最小值而非 Bellman 不动点，且需要 double sampling。
正确做法：
target = r + gamma * V(s_next).detach()或with torch.no_grad(): target = ...💡 概念误区：认为"TD 的偏差会导致收敛到错误答案"
错误理解：既然 TD target 有偏差，那 TD 最终收敛到的是一个有偏的答案。
实际上：TD 的偏差是**暂时的**——它来自 \(V(S_{t+1}) \neq V^\pi(S_{t+1})\)。随着学习进行，\(V\) 逼近 \(V^\pi\)，偏差也趋于零。在收敛极限处，\(\mathbb{E}[\delta_t | S_t = s] = 0\) 对所有 \(s\) 成立。Tabular TD(0) 的收敛极限就是 \(V^\pi\)（非线性 FA 下可能不同）。
TD(0) 的 Random Walk 例子¶
Sutton 1988 原论文使用一个经典的 5 状态 Random Walk 展示 TD(0) 的优势：
从中间状态 C 开始，每步等概率向左或向右移动。左终止奖励 0，右终止奖励 1。所有中间奖励为 0，\(\gamma = 1\)（无折扣 episodic 任务）。
真实值函数：\(V^\pi(A) = 1/6, V^\pi(B) = 2/6, V^\pi(C) = 3/6, V^\pi(D) = 4/6, V^\pi(E) = 5/6\)
实验结果（Sutton 1988 Figure 3）：TD(0) 在约 100 个 episode 后 RMSE 降到 0.05 以下，而 MC 在 100 个 episode 后仍有 0.15 左右的 RMSE。这是因为 TD(0) 每一步都在传播信息（从终止状态逐步向内传播价值），而 MC 只在 episode 结束时才更新所有访问过的状态。
如果不用 TD 而用 MC 会怎样：假设一个 episode 从 C 出发最终到达右终止。MC 会将 \(G_t = 1\) 分配给路径上所有状态。但这忽略了一个关键信息——E 比 B 更接近右终止，应该获得更高的值。TD 能利用这个结构信息（通过 \(V(S_{t+1})\) 区分不同后继状态），MC 不能。
TD(0) 的最大似然等价性（确定性等价 MLE）¶
Sutton-Barto 2018 第 6.3 节展示了一个深刻结果：batch TD(0) 收敛到的解等价于对环境的最大似然估计下精确求解 Bellman 方程。
具体地：给定一批数据，如果我们先用数据构建一个经验 MDP（转移概率 = 实际转移频率，奖励 = 实际平均奖励），然后在这个经验 MDP 上精确求解 Bellman 方程，得到的解与 batch TD(0) 的收敛极限相同。
这个结果被称为**确定性等价（certainty equivalence）**——先估计模型然后假装估计是准确的来求解。TD(0) 隐式地在做 model-based 的事情，但不需要显式构建模型！
相比之下，batch MC 收敛到的只是 V 的样本均值——它不利用 MDP 的马尔可夫结构。TD(0) 通过 bootstrapping 隐式利用了马尔可夫性，这就是它样本效率更高的深层原因。
练习¶
- 对一个两状态 MDP：\(S = \{A, B\}\)，从 \(A\) 必定转移到 \(B\) 获得奖励 \(r = 1\)，从 \(B\) 终止。设 \(\gamma = 0.9\)。手算 TD(0) 从 \(V(A) = 0, V(B) = 0\) 出发，\(\alpha = 0.1\) 时前 5 步的更新过程。
- 证明：当 \(\alpha_t = 1\) 时（步长为 1），TD(0) 在只有一个 episode 的 batch 情况下退化为 MC。
- 在 5 状态 Random Walk 中，分析为什么 TD(0) 比 MC 收敛快——从"信息传播速度"的角度解释（提示：TD 每步传播一层，MC 每 episode 传播 T 层但方差更大）。
§6.3.4 TD(λ) 与 eligibility traces ⭐⭐¶
动机：在 MC 和 TD(0) 之间做连续取舍¶
MC 无偏但高方差，TD(0) 有偏但低方差——能否找到一个"旋钮"在两者之间连续调节？这正是 n-step return 和 TD(λ) 的设计目标。
n-step Return¶
定义 \(n\) 步回报： $\(G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})\)$
| \(n\) | 回报形式 | 偏差 | 方差 | 等价于 |
|---|---|---|---|---|
| 1 | \(R_{t+1} + \gamma V(S_{t+1})\) | 高 | 低 | TD(0) |
| 2 | \(R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2})\) | 中 | 中 | — |
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | — |
| \(\infty\) | \(R_{t+1} + \gamma R_{t+2} + \cdots\) | 0 | 高 | MC |
\(n\) 越大，使用的**真实奖励越多**（偏差越低），但包含的**随机变量越多**（方差越高）。这是一个光谱，TD(0) 和 MC 分别是两个极端。
λ-Return（前向视图）¶
与其选择一个固定的 \(n\)，不如**对所有 \(n\) 做加权平均**：
权重 \((1-\lambda)\lambda^{n-1}\) 构成几何分布：\(n\) 越大权重越小，总权重归一。
关键性质： - \(\lambda = 0\)：\(G_t^\lambda = G_t^{(1)}\)，退化为 TD(0) target - \(\lambda = 1\)：\(G_t^\lambda = G_t^{(\infty)} = G_t\)，退化为 MC target - \(\lambda \in (0,1)\)：在 TD(0) 和 MC 之间连续插值
为什么用几何权重而不是均匀权重？ 因为几何分布有**无记忆性**——这使得 λ-return 可以通过资格迹在线递归计算，无需存储未来信息。均匀权重需要预知 episode 长度，无法在线实现。
资格迹（Eligibility Traces）：后向视图¶
问题：λ-return 的定义是"前向看"（forward view）——它需要未来的奖励和状态。但在线学习中，agent 不知道未来！如何在每个时间步就做更新？
解决方案：引入**资格迹** \(e_t(s)\)，它追踪每个状态"最近被访问的程度"：
Accumulating traces（累积迹）： $\(e_t(s) = \gamma \lambda \, e_{t-1}(s) + \mathbb{1}[S_t = s]\)$
含义：每当状态 \(s\) 被访问，其资格迹加 1；每个时间步，所有状态的资格迹乘以 \(\gamma\lambda\) 衰减。资格迹衡量的是"这个状态在多大程度上对当前 TD 误差负责"。
Replacing traces（替换迹）：每次访问直接将 \(e_t(s) = 1\)（而非累加）。在某些情况下避免资格迹无限累积。
TD(λ) 后向视图更新规则： $\(\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\)$ $\(V(s) \leftarrow V(s) + \alpha \delta_t \, e_t(s), \quad \forall s\)$
每个时间步，所有状态的值都被更新——但只有资格迹非零的状态才有实质更新。直觉上：当前 TD 误差 \(\delta_t\) 告诉我们"预测有多少偏差"，资格迹 \(e_t(s)\) 告诉我们"哪些过去的状态要对这个偏差负责"。最近访问的状态责任最大（\(e\) 值高），远期访问的状态责任小（\(e\) 已衰减）。
前向视图与后向视图的等价性¶
定理（Sutton 1988；严格版本见 Sutton-Barto 2018 Ch. 12）：在 offline 情形下（即所有更新在 episode 结束后一次性应用），TD(λ) 的后向视图与前向视图产生**完全相同**的总更新。
证明骨架：考虑一个 episode 中状态 \(s\) 在时刻 \(t_1, t_2, \dots\) 被访问。前向视图对 \(s\) 的总更新为 \(\Delta V_{\text{forward}}(s) = \alpha \sum_k [G_{t_k}^\lambda - V(S_{t_k})]\)。后向视图对 \(s\) 的总更新为 \(\Delta V_{\text{backward}}(s) = \alpha \sum_{t=0}^{T-1} \delta_t \, e_t(s)\)。通过展开 \(e_t(s)\) 的定义并交换求和顺序，可以证明两者相等。
关键数学技巧是利用几何级数：\(e_t(s) = \sum_{k: t_k \leq t} (\gamma\lambda)^{t - t_k}\)，然后将 \(\delta_t\) 对 \(e_t(s)\) 的加权和重新整理为对每个访问时刻 \(t_k\) 的前向视图形式。
在线 TD(λ) 的近似性：实际使用中更新是在线的（即时应用），此时前向和后向视图不再严格等价，但差异为 \(\mathcal{O}(\alpha)\)——当步长小时近似成立。
前向/后向视图等价性的完整推导¶
为了让读者完全理解这个等价性，我们给出一个简化情形的完整推导。考虑一个 episode 中状态 \(s\) 只在时刻 \(t_0\) 被访问一次（first-visit）。
后向视图对 \(V(s)\) 的总更新： $\(\Delta V_{\text{backward}}(s) = \alpha \sum_{t=t_0}^{T-1} \delta_t \, e_t(s)\)$
由 \(e_t(s) = (\gamma\lambda)^{t-t_0}\)（对 \(t \geq t_0\)），有： $\(\Delta V_{\text{backward}}(s) = \alpha \sum_{t=t_0}^{T-1} (\gamma\lambda)^{t-t_0} \delta_t\)$
前向视图对 \(V(s)\) 的更新： $\(\Delta V_{\text{forward}}(s) = \alpha [G_{t_0}^\lambda - V(S_{t_0})]\)$
证明两者相等：展开 \(\lambda\)-return \(G_{t_0}^\lambda = (1-\lambda)\sum_{n=1}^{T-t_0} \lambda^{n-1} G_{t_0}^{(n)}\)。
利用恒等式 \(G_{t_0}^{(n)} - V(S_{t_0}) = \sum_{k=0}^{n-1} \gamma^k \delta_{t_0+k}\)（可由 telescoping 证明），代入得：
交换求和顺序（先对 \(k\)，再对 \(n\) 从 \(k+1\) 到 \(T-t_0\)）： $\(= \sum_{k=0}^{T-t_0-1} \gamma^k \delta_{t_0+k} (1-\lambda)\sum_{n=k+1}^{T-t_0} \lambda^{n-1}\)$
内层和 \((1-\lambda)\sum_{n=k+1}^{T-t_0}\lambda^{n-1} = \lambda^k - \lambda^{T-t_0}\)（几何级数）。
当 \(T-t_0 \to \infty\) 时（或等价地 episode 足够长），\(\lambda^{T-t_0} \to 0\)，得到： $\(G_{t_0}^\lambda - V(S_{t_0}) = \sum_{k=0}^{\infty} (\gamma\lambda)^k \delta_{t_0+k} = \sum_{t=t_0}^{\infty} (\gamma\lambda)^{t-t_0} \delta_t\)$
这与后向视图的总更新完全相同！证毕。
这个等价性的意义：前向视图给出了"正确答案是什么"（λ-return 是我们真正想要逼近的目标），后向视图给出了"如何在线高效计算"（资格迹的递归更新）。两者殊途同归。
λ 的最优选择¶
\(\lambda\) 的最优值不是固定的——它取决于多个因素：
| 因素 | 建议的 \(\lambda\) 范围 | 原因 |
|---|---|---|
| \(V\) 当前质量高（训练后期） | 小（0.0-0.5） | 可以放心 bootstrap |
| \(V\) 当前质量低（训练初期） | 大（0.9-1.0） | 减少 bootstrap 引入的偏差传播 |
| Episode 短（如 50 步） | 大（0.95-0.99） | MC 方差不太大，可以利用 |
| Episode 长（如 10000 步） | 小-中（0.5-0.9） | MC 方差太大 |
| Reward 密集 | 中（0.7-0.95） | 每步信号强 |
| Reward 稀疏 | 大（0.95-1.0） | 需要长程信用分配 |
机器人 RL 中的典型选择：legged_gym 和 Isaac Lab 默认 \(\lambda = 0.95\)，这是在"接近 MC 的无偏性"和"利用 critic 加速信息传播"之间的经验最优点。
TD(λ) 在机器人 RL 中的应用：GAE¶
GAE（Generalized Advantage Estimation，Schulman 2016） 就是 TD(λ) 在 advantage 上的直接应用：
其中 \(\delta_t^V = r_t + \gamma V(S_{t+1}) - V(S_t)\) 是标准 TD 误差。GAE 是机器人 RL 中**使用最广泛的 advantage 估计方法**（legged_gym、Isaac Lab、MuJoCo 任务几乎全部使用）。典型超参：\(\lambda \in [0.95, 0.99]\)，接近 MC 端但保留少量 bootstrapping 以加速信息传播。
⚠️ 常见陷阱¶
⚠️ 编程陷阱：资格迹在 episode 边界不重置
错误做法：continuing task 中不重置 \(e\)，或 episodic task 中 episode 结束后 \(e\) 带到下一个 episode。
现象：上一个 episode 的信用分配"泄露"到下一个 episode，导致值函数估计有系统偏差。
正确做法：每个 episode 开始时 \(e_0(s) = 0, \forall s\)。在 continuing task 中，进入 terminal state 时自动清零。
💡 概念误区：认为 "\(\lambda\) 越大越好因为更接近无偏的 MC"
实际上：\(\lambda\) 的最优值取决于 \(V\) 的准确程度。如果 \(V\) 已经相当准确，bootstrap（小 \(\lambda\)）利用了 \(V\) 的信息加速学习；如果 \(V\) 不准，bootstrap 会传播错误，大 \(\lambda\) 更安全。这就是为什么训练初期用大 \(\lambda\)、后期可以减小的策略有时有效。
练习¶
- 证明：当 \(\lambda = 0\) 时，累积资格迹退化为 \(e_t(s) = \mathbb{1}[S_t = s]\)，TD(λ) 更新规则精确退化为 TD(0)。
- 对一个 3 状态链 \(A \to B \to C\)（终止），写出 \(\lambda = 0.5\) 时 \(G_0^\lambda\) 的具体表达式。
§6.3.5 SARSA vs Q-learning：on-policy vs off-policy 的分岔 ⭐⭐¶
动机：从策略评估到策略控制¶
TD(0) 解决了策略评估问题——给定 \(\pi\) 估计 \(V^\pi\)。但我们的最终目标是**找到最优策略 \(\pi^*\)。为此需要估计 **Q 值 \(Q^\pi(s,a)\) 或 \(Q^*(s,a)\)，因为策略提升需要比较不同动作的价值。
从 \(V\) 到 \(Q\) 的转变引出了 RL 史上最重要的一次分岔：on-policy（用行为数据学行为策略的值）vs off-policy（用行为数据学另一个策略的值）。
SARSA：on-policy TD 控制¶
SARSA（Rummery-Niranjan 1994）的名字来自它使用的五元组 \((S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})\)：
其中 \(A_{t+1}\) 是由**当前行为策略**（通常 \(\varepsilon\)-greedy on \(Q\)）实际选择的动作。
SARSA 的数学本质：它是 Bellman 期望算子 \(T^\pi\) 的随机逼近： $\(Q^\pi(s,a) = \mathbb{E}_\pi[R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]\)$
SARSA 收敛到**当前策略 \(\pi\) 的 \(Q^\pi\)**——而 \(\pi\) 通常是 \(\varepsilon\)-greedy，所以 SARSA 收敛到的不是 \(Q^*\)，而是"在持续探索的策略下的最优 Q"。
Q-learning：off-policy TD 控制¶
Q-learning（Watkins 1989）的更新规则：
关键区别：目标里是 \(\max_{a'} Q(S_{t+1}, a')\)，而非实际采样到的 \(Q(S_{t+1}, A_{t+1})\)。
Q-learning 的数学本质：它是 Bellman 最优算子 \(T^*\) 的随机逼近： $\(Q^*(s,a) = \mathbb{E}[R_{t+1} + \gamma \max_{a'} Q^*(S_{t+1}, a') | S_t = s, A_t = a]\)$
无论行为策略如何（只要充分探索每个 \((s,a)\)），Q-learning 都收敛到 \(Q^*\)。这就是 off-policy 的含义——学的策略（greedy on \(Q^*\)）与用的策略（行为策略）不同。
On-policy vs Off-policy 的数学区别¶
| 维度 | On-policy (SARSA) | Off-policy (Q-learning) |
|---|---|---|
| 目标算子 | \(T^\pi\)（期望算子） | \(T^*\)（最优算子） |
| TD target | \(R + \gamma Q(S', A')\)，\(A' \sim \pi\) | \(R + \gamma \max_{a'} Q(S', a')\) |
| 收敛到 | \(Q^\pi\)（当前策略的值） | \(Q^*\)（最优策略的值） |
| 需要策略改进？ | 是（配合 \(\varepsilon\)-greedy 迭代） | 否（直接学 \(Q^*\)） |
| 数据可复用？ | 否（策略变了数据就"过期"） | 是（replay buffer 可行） |
| 致命三元组？ | 只命中 FA + Bootstrap | 命中全部三项 |
Off-policy 的根本优势：数据效率。因为旧策略收集的数据仍然可以用来学习 \(Q^*\)（\(\max\) 操作不依赖行为策略），所以可以用 replay buffer 存储大量历史转移，反复训练——每条数据被使用数百次而非一次就丢。
Off-policy 的根本风险：当与函数逼近和 bootstrapping 结合时，更新分布 \(d^\mu\) 偏离目标分布 \(d^\pi\)，可能导致发散。这是致命三元组的数学根源。
Expected SARSA：两者的桥接¶
Expected SARSA 将 SARSA 的 target 中 \(A_{t+1}\) 的采样噪声用期望替代：
- 当 \(\pi\) = greedy 时：\(\sum_{a'} \pi(a'|S_{t+1}) Q(S_{t+1}, a') = \max_{a'} Q(S_{t+1}, a')\)，退化为 Q-learning
- 当 \(\pi\) = 行为策略时：是 SARSA 的低方差版本（消除了 \(A_{t+1}\) 采样噪声）
Expected SARSA 额外需要计算 \(|\mathcal{A}|\) 个 Q 值的加权和——在动作空间小时可行，大时不经济。
Cliff Walking 经典对比¶
Sutton-Barto 第 6 章的 Cliff Walking 任务完美展示了 on/off-policy 的行为差异：
- Q-learning（off-policy）学到贴悬崖走的最短路径——因为它学的是 \(Q^*\)，假设未来总执行最优动作，不考虑 \(\varepsilon\)-greedy 可能的随机失足。
- SARSA（on-policy）学到远离悬崖的安全路径——因为它学的是 \(Q^{\pi_\varepsilon}\)，知道 \(\varepsilon\)-greedy 策略有概率随机选择动作，贴悬崖走意味着一定概率掉下去。
深层洞察：Q-learning 学的是"如果你以后都很理性会怎样"，SARSA 学的是"考虑到你会继续犯错会怎样"。在训练过程中（\(\varepsilon > 0\)），SARSA 的策略实际获得的平均回报通常更高，因为它的值估计是"自洽"的。但训练结束后如果关闭探索（\(\varepsilon = 0\)），Q-learning 学到的策略是真正最优的。
⚠️ 常见陷阱¶
🧠 思维陷阱：认为"Q-learning 总比 SARSA 好因为它学 \(Q^*\)"
新手想法：Q-learning 直接学最优，SARSA 学当前策略然后迭代——显然直接学最优更高效。
实际上：Q-learning 在训练过程中更"乐观"（假设未来完美），当与函数逼近结合时这种乐观容易导致过估计和发散。SARSA 更"保守"（考虑实际探索噪声），在有 FA 时通常更稳定。这就是为什么机器人 RL 主流用 PPO（on-policy）而非 DQN（off-policy）。
正确认识：on/off-policy 是**权衡**而非"好坏"。数据充足 + FA 稳定 → off-policy 数据效率高；数据有限 + FA 不稳定 → on-policy 更安全。
n-step SARSA 与 Sarsa(λ)¶
与 TD(λ) 对 V 的扩展类似，SARSA 也可以扩展到多步版本：
n-step SARSA： $\(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\left[G_t^{(n)} - Q(S_t, A_t)\right]\)$ $\(G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n}, A_{t+n})\)$
Sarsa(λ) 使用资格迹实现所有 n 步的几何加权： $\(e_t(s,a) = \gamma\lambda \, e_{t-1}(s,a) + \mathbb{1}[S_t = s, A_t = a]\)$ $\(Q(s,a) \leftarrow Q(s,a) + \alpha\delta_t \, e_t(s,a), \quad \forall (s,a)\)$
On-policy 安全性的工程价值¶
在机器人真机部署中，on-policy 方法的一个容易被忽视的优势是**策略-值一致性**：
SARSA 学到的 \(Q^{\pi_\varepsilon}\) 精确反映了"使用当前含噪声策略时的实际预期回报"。如果用这个 Q 值来评估"当前状态是否安全"，评估结果是可靠的——因为它考虑了策略本身的噪声可能导致的意外。
相反，Q-learning 学到的 \(Q^*\) 假设"以后总做最优选择"。如果用 \(Q^*\) 来评估安全性，可能过于乐观——实际执行时的 \(\varepsilon\)-greedy 策略有概率选择次优（甚至危险的）动作。
这在安全关键系统中尤为重要：自动驾驶、手术机器人、人机协作等场景中，"知道自己不完美"比"假装自己完美"更安全。
练习¶
- 在 Cliff Walking 中，设 \(\varepsilon = 0.1\)，分析 SARSA 学到的"绕远路"比 Q-learning 的"贴悬崖"在训练期间多获得多少平均奖励（提示：计算掉下悬崖的概率）。
- 证明：当所有 \((s,a)\) 被无限次访问且步长满足 Robbins-Monro 时，SARSA 配合衰减 \(\varepsilon_t = 1/t\) 最终收敛到 \(Q^*\)。
- 在一个有"危险区域"的网格世界中，比较 SARSA 和 Q-learning 学到的策略。解释为什么 SARSA 倾向于绕过危险区域而 Q-learning 倾向于穿越。
§6.3.6 Tabular 收敛性定理 ⭐⭐¶
定理陈述¶
在表格（tabular）情形下——每个 \((s,a)\) 或 \(s\) 独立存储一个参数、不共享任何逼近结构——TD 类算法的收敛性由两条经典定理保证：
定理 1（TD(0) 几乎必然收敛，Sutton 1988；Dayan 1992）：在有限 MDP 下，若策略 \(\pi\) 诱导的马尔可夫链遍历（ergodic），每个状态被无限次访问，且步长 \(\{\alpha_t\}\) 满足 Robbins-Monro 条件 $\(\sum_t \alpha_t = \infty, \quad \sum_t \alpha_t^2 < \infty\)$ 则 tabular TD(0) 的 \(V_t\) 以概率 1 收敛到 \(V^\pi\)。
定理 2（Q-learning 几乎必然收敛，Watkins-Dayan 1992；Tsitsiklis 1994）：在有限 MDP 下，若每个 \((s,a)\) 被无限次访问、步长满足 Robbins-Monro 条件，则 tabular Q-learning 的 \(Q_t\) 以概率 1 收敛到 \(Q^*\)： $\(\boxed{\;Q_t \xrightarrow{\text{a.s.}} Q^*\;}\)$
证明的核心工具¶
这些收敛性定理的证明依赖**随机逼近理论（Stochastic Approximation, SA）**。核心工具包括：
- Dvoretzky 1956 定理：非负随机序列 \(\{Z_t\}\) 满足 \(Z_{t+1} \leq (1 - \alpha_t) Z_t + \beta_t\) 时的收敛条件。
- 两时间尺度分解：将 TD 更新分解为"均值 ODE + 噪声"，证明噪声项被步长衰减吸收。
- Borkar-Meyn ODE 方法：将随机迭代 \(\theta_{t+1} = \theta_t + \alpha_t f(\theta_t, X_t)\) 的长时间行为归结为平均 ODE \(\dot{\theta} = \bar{f}(\theta)\) 的稳定性。
三个核心要件（记住即可，严格推导留给 §6.5）： - (1) 每个坐标无限访问 - (2) 步长 Robbins-Monro 条件 - (3) 算子压缩性（\(T^\pi\) 或 \(T^*\) 的 \(\gamma\)-contraction）
GLIE 条件与策略控制收敛¶
GLIE（Greedy in the Limit with Infinite Exploration） 是策略控制收敛性的补充条件：
- 性质 1（无限探索）：每个 \((s,a)\) 被无限次访问，即 \(\lim_{k\to\infty} N_k(s,a) = \infty\)
- 性质 2（极限贪婪）：\(\pi_t \to \text{greedy w.r.t. } Q_t\) as \(t \to \infty\)
典型实现：\(\varepsilon_t = 1/t\) 的 \(\varepsilon\)-greedy 同时满足两个性质。
Q-learning + GLIE 同时保证 \(Q_t \to Q^*\) 与 \(\pi_t \to \pi^*\)。
Robbins-Monro 条件的直觉¶
Robbins-Monro 条件 \(\sum \alpha_t = \infty, \sum \alpha_t^2 < \infty\) 看起来是纯数学技术要求，但有深刻的直觉含义：
- \(\sum \alpha_t = \infty\)：保证算法能"走无限远"。如果 \(\sum \alpha_t < \infty\)（如 \(\alpha_t = 1/t^2\)），算法的总移动距离有限，可能在到达真解之前"耗尽动力"。
- \(\sum \alpha_t^2 < \infty\)：保证噪声的累积效果被抑制。每步噪声方差为 \(\mathcal{O}(\alpha_t^2\sigma^2)\)，总噪声为 \(\mathcal{O}(\sigma^2 \sum \alpha_t^2)\)。如果发散（常数步长），算法在真解附近永远震荡。
典型选择 \(\alpha_t = 1/t\) 满足两个条件。实践中常用常数步长 \(\alpha\)——理论上不严格收敛，但在非平稳环境中更实用。
Q-learning 收敛性的证明直觉¶
Watkins-Dayan 1992 的证明基于归纳论证。核心思想：
- 定义误差 \(\Delta_t(s,a) = Q_t(s,a) - Q^*(s,a)\)
- max 操作是非扩张的：\(|\max_a f(a) - \max_a g(a)| \leq \max_a |f(a) - g(a)|\)
- 所以误差递推满足压缩性：\(\|\Delta_{t+1}\|_\infty \leq (1-\alpha)\|\Delta_t\|_\infty + \alpha\gamma\|\Delta_t\|_\infty\)
- 即 \(\|\Delta\|\) 以速率 \(\alpha(1-\gamma)\) 收缩
为什么 off-policy 在 tabular 下不导致发散？ 因为每个 \((s,a)\) 的更新**独立**——更新 \(Q(s_1,a_1)\) 不影响 \(Q(s_2,a_2)\)。行为策略只决定哪些 \((s,a)\) 被访问，不改变更新的数学性质。
从 tabular 到 FA：收敛性为什么会破裂¶
Tabular 收敛性的关键数学保证是：每个状态/状态-动作对的更新互相独立。但一旦引入函数逼近，更新 \(\theta\) 会**同时改变所有状态的值**——因为 \(V_\theta(s') = \phi(s')^T\theta\) 对所有 \(s'\) 依赖同一个 \(\theta\)。
这种"耦合"造成三个问题： 1. 更新干扰：改善 \(V(s)\) 可能恶化 \(V(s')\) 2. 误差传播：\(V(S_{t+1})\) 的误差通过 bootstrap 传到 \(V(S_t)\) 3. 分布依赖：收敛点依赖于访问频率（加权 \(d^\pi\)）
这就是为什么 Tsitsiklis-Van Roy 1997 的工作如此重要——它证明了即使存在耦合，on-policy 线性 TD 仍然收敛。
⚠️ 常见陷阱¶
💡 概念误区：认为"步长 \(1/t\) 在实践中总是最优的"
实际上：\(1/t\) 衰减太快——在 \(t = 10^6\) 时已经是 \(10^{-6}\)，更新几乎停滞。实践中几乎总用常数步长或自适应优化器（Adam）。虽然理论不满足 R-M，但有限时间效果更好。
§6.3.7 线性函数逼近与 Tsitsiklis-Van Roy 定理 ⭐⭐¶
动机：函数逼近的引入¶
将 \(V^\pi\) 参数化为线性形式：\(V_\theta(s) = \phi(s)^T \theta\)，其中 \(\phi: \mathcal{S} \to \mathbb{R}^d\) 是固定的特征映射，\(\theta \in \mathbb{R}^d\) 是待学习参数。
为什么线性逼近重要？ 虽然实际应用多用神经网络（非线性），但线性情形是唯一有完整收敛性理论的 FA 形式。理解线性 TD 的理论是理解非线性 TD（如 DQN）"为什么有时会崩"的基础。
线性 TD(0) with FA 的更新规则¶
其中 TD 误差为： $\(\delta_t = R_{t+1} + \gamma \phi(S_{t+1})^T \theta_t - \phi(S_t)^T \theta_t\)$
关键观察：这不是任何损失函数的真正梯度！ 准确地说它是**半梯度（semi-gradient）**——对 TD target \(R_{t+1} + \gamma \phi(S_{t+1})^T \theta\) 中的 \(\theta\) 不做求导。
如果我们考虑 MSE 损失 \(L(\theta) = \frac{1}{2}[R_{t+1} + \gamma V_\theta(S_{t+1}) - V_\theta(S_t)]^2\)，其真梯度为： $\(\nabla_\theta L = -\delta_t [\phi(S_t) - \gamma \phi(S_{t+1})]\)$
但 semi-gradient TD 只用 \(-\delta_t \phi(S_t)\)——丢弃了 \(\gamma \phi(S_{t+1})\) 项。这个 semi-gradient 性质既是 TD 高效的来源（避免了 double sampling 问题），也是发散风险的根源。
投影 Bellman 算子¶
设 \(\Phi \in \mathbb{R}^{|\mathcal{S}| \times d}\) 是特征矩阵（第 \(s\) 行为 \(\phi(s)^T\)），逼近空间 \(\mathcal{F} = \{\Phi\theta : \theta \in \mathbb{R}^d\}\) 是 \(\mathbb{R}^{|\mathcal{S}|}\) 的 \(d\) 维线性子空间。
问题：\(T^\pi V_\theta\) 通常不在 \(\mathcal{F}\) 内——Bellman 算子将值函数映射出了逼近空间。不能直接在 \(\mathcal{F}\) 内寻找 Bellman 方程的不动点。
解决方案：先做 \(T^\pi\)，再**投影**回 \(\mathcal{F}\)。定义加权投影算子： $\(\Pi_D = \Phi (\Phi^T D \Phi)^{-1} \Phi^T D\)$
其中 \(D = \mathrm{diag}(d^\pi)\) 是稳态分布的对角权重矩阵。\(\Pi_D\) 是在加权 \(\ell_2\) 范数 \(\|V\|_D^2 = \sum_s d^\pi(s) V(s)^2\) 下的正交投影。
投影 Bellman 算子 \(\Pi_D T^\pi\) 先将 \(V\) 做一步 Bellman 更新，再投影回 \(\mathcal{F}\)。线性 TD 收敛到的就是这个复合算子的不动点。
Tsitsiklis-Van Roy 1997 定理¶
定理（Tsitsiklis-Van Roy 1997，IEEE TAC Vol. 42, No. 5, pp. 674-690）：在有限 MDP、特征矩阵 \(\Phi\) 列满秩、策略 \(\pi\) 诱导遍历马尔可夫链、步长 Robbins-Monro 等条件下，沿 \(\pi\) 的单轨迹运行的**线性 TD(λ)** 以概率 1 收敛到唯一的参数 \(\theta^*\)，满足投影 Bellman 方程： $\(\Phi\theta^* = \Pi_{d^\pi} T^\pi_\lambda \Phi\theta^*\)$
进一步，存在逼近误差界： $\(\boxed{\;\|\Phi\theta^*_\lambda - V^\pi\|_{d^\pi} \le \frac{1-\lambda\gamma}{\sqrt{(1-\gamma)(1+\gamma-2\lambda\gamma)}}\|\Pi_{d^\pi} V^\pi - V^\pi\|_{d^\pi}\;}\)$
特别地 \(\lambda = 0\) 时：\(\|\Phi\theta^* - V^\pi\|_{d^\pi} \le \frac{1}{\sqrt{1-\gamma^2}}\|\Pi V^\pi - V^\pi\|_{d^\pi}\)
\(\lambda = 1\) 时：退化为 \(1 \cdot \|\Pi V^\pi - V^\pi\|\)（MC 得到最优投影，无放大）。
证明骨架（4 步）¶
第一步：\(P^\pi\) 在 \(\|\cdot\|_{d^\pi}\) 下非扩张。
因为 \(d^\pi\) 是 \(P^\pi\) 的不变测度（\(d^{\pi T} P^\pi = d^{\pi T}\)），由 Jensen 不等式： $\(\|P^\pi V\|_{d^\pi}^2 = \sum_s d^\pi(s) \Big(\sum_{s'} P^\pi(s,s') V(s')\Big)^2 \le \sum_s d^\pi(s) \sum_{s'} P^\pi(s,s') V(s')^2 = \|V\|_{d^\pi}^2\)$
关键洞察：这一步**只在 \(D = D^\pi\) 时成立**——因为需要 \(d^\pi\) 是 \(P^\pi\) 的不变测度。如果用其他分布 \(d^\mu\)，\(P^\pi\) 在 \(\|\cdot\|_{d^\mu}\) 下可能是**扩张的**——这就是 off-policy 发散的数学根源。
第二步：\(T^\pi\) 是 \(\|\cdot\|_{d^\pi}\) 下的 \(\gamma\)-压缩。
第三步：\(\Pi_{d^\pi}\) 是 \(\|\cdot\|_{d^\pi}\) 下的非扩张。
正交投影算子在其度量下总是非扩张的（几何直观：投影只会缩短向量长度）。
第四步：复合算子 \(\Pi_{d^\pi} T^\pi\) 是 \(\gamma\)-压缩。
由第二步和第三步的复合：\(\|\Pi T^\pi V - \Pi T^\pi V'\| \le \|\Pi\| \cdot \|T^\pi V - T^\pi V'\| \le 1 \cdot \gamma \|V - V'\|\)。
由 Banach 不动点定理，\(\Pi_{d^\pi} T^\pi\) 存在唯一不动点 \(\Phi\theta^*\)。线性 TD(0) 的期望更新零点恰为此不动点，加上 Robbins-Monro 条件即得几乎必然收敛。
本质洞察：Tsitsiklis-Van Roy 定理的核心不是"线性 TD 收敛"这个结论，而是它揭示了收敛性的**精确条件**：采样分布必须与目标策略的稳态分布匹配。这不是偶然的技术要求，而是**本质的数学必然**——\(P^\pi\) 的非扩张性只在其不变测度下成立。偏离这个条件（off-policy），非扩张性失效，压缩性失效，不动点可能不存在或不稳定。
线性 TD 的期望更新矩阵¶
将线性 TD(0) 的单步更新展开。TD 误差 \(\delta_t = R_{t+1} + \gamma\phi(S_{t+1})^\top\theta_t - \phi(S_t)^\top\theta_t\)，更新为 \(\theta_{t+1} = \theta_t + \alpha_t\delta_t\phi(S_t)\)，即： $\(\theta_{t+1} = \theta_t - \alpha_t\phi(S_t)\bigl(\phi(S_t) - \gamma\phi(S_{t+1})\bigr)^\top\theta_t + \alpha_t R_{t+1}\phi(S_t)\)$
注意外积方向：\(\phi(S_t)\bigl(\phi(S_t)-\gamma\phi(S_{t+1})\bigr)^\top\) 是 \(d\times d\) 矩阵（列向量乘行向量），右乘 \(\theta_t\) 后得到 \(d\times 1\) 向量。这里 \(\phi(S_t)\) 在**左侧**（它是 TD 误差的"梯度方向"），\((\phi(S_t)-\gamma\phi(S_{t+1}))^\top\) 在**右侧**（它与 \(\theta\) 形成当前值估计的线性组合）。
取期望（对稳态分布 \(d^\pi\) 和转移核 \(P^\pi\)）： $\(\mathbb{E}[\theta_{t+1} - \theta_t] = \alpha_t(-A\theta_t + b)\)$
其中： $\(A = \mathbb{E}_{S\sim d^\pi}\bigl[\phi(S)\bigl(\phi(S) - \gamma\phi(S')\bigr)^\top\bigr] = \Phi^\top D^\pi(I - \gamma P^\pi)\Phi\)$ $\(b = \mathbb{E}[R\,\phi(S)]\)$
\(A\) 的性质分析： - \(A\) 一般**不对称**（因为 \(\phi(S)(\phi(S) - \gamma\phi(S'))^T\) 不对称） - 但 TVR 1997 证明了 \(A\) 的实部特征值全正（即 \(A + A^T\) 正定） - 这保证了线性系统 \(-A\theta + b = 0\) 的唯一解 \(\theta^* = A^{-1}b\) 是渐近稳定的
直觉：\(A\) 正定等价于"TD 更新在期望上是收缩的"——无论从哪个 \(\theta\) 出发，期望更新方向都指向 \(\theta^*\)。这是 on-policy 条件的数学体现：\(D^\pi\) 与 \(P^\pi\) 的匹配保证了 \(A\) 的正定性。
如果 \(A\) 不正定（off-policy）：\(A\) 可能有负实部特征值，意味着某些方向上的更新是"膨胀"而非"收缩"的——\(\theta\) 在这些方向上指数增长，即 Baird 反例中观察到的发散行为。
MSPBE/MSBE/TDE 目标函数关系¶
线性 TD 收敛到的点可以用多个等价的目标函数刻画：
| 目标函数 | 定义 | 可采样？ | TD 不动点是否为其最小值？ |
|---|---|---|---|
| MSBE | \(\|V_\theta - T^\pi V_\theta\|_D^2\) | 否（需 double sampling） | 否（TD 不动点不最小化 MSBE） |
| MSPBE | \(\|\Pi_D T^\pi V_\theta - V_\theta\|_D^2\) | 是（需辅助变量） | 是（TD 不动点 = MSPBE 零点） |
| NEU | \(\|\mathbb{E}[\delta_t \phi_t]\|^2\) | 是 | 是（与 MSPBE 零点相同） |
MSPBE 的梯度形式为： $\(\nabla \mathrm{MSPBE}(\theta) = -2 \mathbb{E}[(\phi - \gamma\phi')\phi^T] \cdot C^{-1} \cdot \mathbb{E}[\delta\phi]\)$ 其中 \(C = \mathbb{E}[\phi\phi^T]\)。这个梯度涉及两个期望的乘积——不能用单个样本无偏估计——这就是 GTD 需要双时间尺度的原因。
投影 Bellman 方程的几何直觉¶
这是理解线性 TD 收敛结果最重要的直觉图景：
想象 \(\mathbb{R}^{|\mathcal{S}|}\) 空间中： - \(V^\pi\) 是一个固定的点（真实值函数） - \(\mathcal{F} = \{\Phi\theta : \theta \in \mathbb{R}^d\}\) 是一个 \(d\) 维超平面 - \(\Pi V^\pi\) 是 \(V^\pi\) 到 \(\mathcal{F}\) 的正交投影（FA 能达到的"最好"） - \(\Phi\theta^*\) 是线性 TD 的收敛点（投影 Bellman 方程的不动点）
关键洞察：\(\Pi V^\pi \neq \Phi\theta^*\) 一般成立！ 线性 TD 不是收敛到 \(V^\pi\) 的最佳近似，而是收敛到一个"稍差"的近似——因为 TD 解的是投影 Bellman 方程而非投影最小二乘。
为什么 TD 不直接收敛到 \(\Pi V^\pi\)？ 因为 TD 没有直接访问 \(V^\pi\)——它只能通过 Bellman 算子间接获取信息。Bellman 算子 \(T^\pi\) 将 \(V_\theta\) 映射出子空间 \(\mathcal{F}\)，投影 \(\Pi\) 再拉回来。这个"映射出去再拉回来"的过程引入了额外的误差。只有 MC（\(\lambda = 1\)）能直接收敛到 \(\Pi V^\pi\)——因为 MC 不经过 Bellman 算子。
三者的位置关系： $\(\|V^\pi - \Phi\theta^*\|_D \leq \underbrace{\|V^\pi - \Pi V^\pi\|_D}_{\text{FA 能力上限}} + \underbrace{\|\Pi V^\pi - \Phi\theta^*\|_D}_{\text{TD 额外代价}}\)$
TD 额外代价被 \((\frac{1}{\sqrt{1-\gamma^2}} - 1) \|V^\pi - \Pi V^\pi\|\) 控制——当 \(\gamma\) 小时额外代价小，\(\gamma\) 大时可能显著。
逼近误差界的物理意义¶
- 最优投影误差 \(\|V^\pi - \Pi V^\pi\|\)：这是逼近空间 \(\mathcal{F}\) 的"表达能力上限"——即使用最好的 \(\theta\) 也无法消除的误差。由特征设计决定。
- 放大因子 \(1/\sqrt{1-\gamma^2}\)：TD 引入的额外代价。当 \(\gamma \to 1\) 时放大因子趋于 \(\infty\)——说明长折扣视野下 TD 的逼近质量退化。\(\lambda\) 增大可以减小放大因子（MC 的放大因子为 1）。
⚠️ 常见陷阱¶
💡 概念误区：认为"线性 TD 收敛到 \(V^\pi\) 的最优逼近"
错误理解：既然 \(\theta^*\) 使投影 Bellman 方程成立，它就是 \(\mathcal{F}\) 中最接近 \(V^\pi\) 的点。
实际上：最接近 \(V^\pi\) 的点是 \(\Pi V^\pi\)（直接投影），而 TD 不动点 \(\Phi\theta^*\) 一般不等于 \(\Pi V^\pi\)！逼近误差界告诉我们 \(\|V_{\theta^*} - V^\pi\| \leq \frac{1}{\sqrt{1-\gamma^2}} \|V^\pi - \Pi V^\pi\|\)——TD 不动点可能比最优投影差 \(1/\sqrt{1-\gamma^2}\) 倍。只有当 \(\lambda = 1\)（MC）时 TD 不动点才等于 \(\Pi V^\pi\)。
练习¶
- 对一个 3 状态 MDP 和 2 维特征 \(\phi(1) = [1, 0]^T, \phi(2) = [1, 1]^T, \phi(3) = [0, 1]^T\)，计算投影矩阵 \(\Pi_D\)（假设均匀 \(d^\pi\)）。
- 验证 Tsitsiklis-Van Roy 证明第一步：构造一个例子说明当 \(D \neq D^\pi\) 时 \(\|P^\pi V\|_D > \|V\|_D\) 可能成立。
§6.3.8 致命三元组与 Baird 反例 ⭐⭐¶
致命三元组的定义¶
Sutton-Barto（2018）第 11 章将 TD 学习的不稳定性归因于三个因素的组合——致命三元组（The Deadly Triad）：
- 函数逼近（Function Approximation）：用参数化 \(V_\theta\) 而非查表
- Bootstrapping：用 \(V_\theta\) 自身估计构造 TD target
- Off-policy learning：更新分布偏离目标策略的稳态分布
三者单独或两两组合通常不引起发散：
| 组合 | 结果 | 原因 |
|---|---|---|
| FA + Off-policy（无 bootstrap） | 稳定 | 退化为加权回归 |
| FA + Bootstrap（on-policy） | 收敛 | Tsitsiklis-Van Roy 1997 保证 |
| Bootstrap + Off-policy（tabular） | 收敛 | Q-learning 的经典收敛 |
| FA + Bootstrap + Off-policy | 可能发散 | 投影 Bellman 算子失去压缩性 |
Baird 1995 反例详解¶
Baird 1995（"Residual Algorithms"，ICML pp. 30-37）给出了著名的 7-star MDP 反例：
结构：
- 7 个状态（编号 1-7），每状态 2 个动作：dashed 和 solid
- dashed 动作以等概率 \(1/6\) 到达状态 1-6 之一
- solid 动作确定性到达状态 7
- 所有转移奖励为 0，故 \(V^\pi(s) \equiv 0\) 对任意策略
- 折扣 \(\gamma = 0.99\)
- 目标策略 \(\pi\)：始终选 solid（确定性转到状态 7）
- 行为策略 \(\mu\)：dashed 概率 \(6/7\)、solid 概率 \(1/7\)
特征设计（8 维参数 \(\theta \in \mathbb{R}^8\)）： - 状态 \(i \in \{1,\dots,6\}\): \(\phi(i) = 2e_i + e_8\) - 状态 7: \(\phi(7) = e_7 + 2e_8\) - 值函数 \(\hat{V}(s) = \phi(s)^T\theta\) - 真解 \(\theta = \mathbf{0}\) 可精确表示！——问题不在逼近能力
发散机制：
Off-policy semi-gradient TD(0) 的期望更新为 \(\theta_{t+1} = \theta_t + \alpha A\theta_t + \alpha b\)，其中： $\(A = \Phi^T D_\mu (\gamma P^\pi - I)\Phi\)$
当 \(D_\mu \neq D^\pi\) 时，\(A\) 不再保证负定（即 \(-A\) 不保证正定）。直接代入 Baird 配置可数值验证 \(A\) 有正实部特征值，导致 \(\|\theta_t\| \to \infty\) 单调发散。
为什么真解可表示却无法收敛？
这是 Baird 反例最深刻的地方。问题不在于： - 逼近能力（真解精确可达） - Bootstrapping 本身（tabular 用 bootstrap 也稳定） - 采样噪声（期望动态也发散）
根源在于 \(\Pi_{d^\mu} T^\pi\) 不再是压缩算子。 \(P^\pi\) 在 \(\|\cdot\|_{d^\mu}\) 范数下不是非扩张（TVR 证明第一步对 \(D_\mu \neq D^\pi\) 失效），整个压缩性证明链断裂。
如果不理解致命三元组会怎样： 你会在调 DQN 时遇到 Q 值爆炸，以为是学习率太大——实际上即使 \(\alpha \to 0\) 也发散（因为期望动态不稳定）。你会增大 replay buffer——但这只是"缓慢发散"而非"不发散"。正确诊断需要理解问题出在 off-policy + FA + bootstrap 的组合上。
非线性 FA 下的发散：even on-policy can fail¶
Tsitsiklis-Van Roy 1997 附录给出了一个更令人不安的结果：即使 on-policy，非线性函数逼近下 TD 也可能发散。
反例构造：一个三状态 MDP + sigmoid-like 非线性逼近器，使得期望更新的 ODE 有不稳定均衡点。这说明 TVR 定理的"线性"假设不是可有可无的——它是本质的。
对 DQN 的启示：DQN 使用非线性 CNN——理论上即使在 on-policy 下也没有收敛保证，更不用说 off-policy。DQN 在 Atari 上的"成功"完全依赖于 CNN 在这些特定任务上"恰好"避开了病态区域——这是经验性的，不是定理保证的。
这不意味着"非线性 FA 不能用"——只是说我们没有像线性情形那样的理论保证。实践中需要依赖： - 充分的正则化（dropout、weight decay、layer norm） - 保守的超参选择（小学习率、大 batch） - 大量的工程调试经验 - 监控训练稳定性（Q 值增长曲线、梯度范数）
致命三元组的定量分析¶
van Hasselt et al. 2018（arXiv:1812.02648, "Deep Reinforcement Learning and the Deadly Triad"）给出了致命三元组的大规模实证研究：
- 在 57 款 Atari 游戏上系统评估了不同组合的稳定性
- 发现 bootstrapping 程度（n-step 的 \(n\)）越大、off-policy 程度（replay buffer 越大 / importance ratio 越大）越强，发散概率越高
- 但也发现在某些游戏上，适度的 off-policy + bootstrap 反而比 on-policy MC 效果好——说明致命三元组是"风险"而非"必然灾难"
这篇实证论文为理论不完美的 DQN 提供了"什么时候会出问题"的经验性指导。
解决致命三元组的四条路径¶
| 路径 | 方法 | 核心思想 | 代表工作 |
|---|---|---|---|
| 修正采样分布 | Emphatic TD | 用 emphasis 权重使更新矩阵正定 | Sutton 2016 |
| 换目标函数 | GTD/TDC | 最小化 MSPBE（真梯度方法） | Sutton 2009 |
| 工程修补 | Target Network + Replay | 冻结算子 + 平均分布 | Mnih 2015 DQN |
| 去掉 Bootstrap | MC-based | 不用 \(V\) 自身构造 target | PPO + MC critic |
⚠️ 常见陷阱¶
🧠 思维陷阱：认为"致命三元组只在理论上发散，实际中不会"
新手想法：Baird 反例是人为构造的，实际任务中不会这么巧。DQN 在 Atari 上工作得很好，说明致命三元组不是真正的问题。
实际上：DQN 在 Atari 上"能 work"完全依赖于 target network + replay buffer 的工程修补——这些正是对致命三元组的对症治疗。在更困难的任务（长视野、稀疏奖励、高维连续动作）上，DQN 系列的不稳定性是常见现象，不是超参问题而是结构性问题。机器人 RL 社区主流用 PPO 正是因为它不命中三元组。
练习¶
- 写出 Baird 7-star MDP 的 \(\Phi\) 矩阵（\(7 \times 8\)），计算在 \(D_\mu = I/7\)、\(P^\pi\) 将所有状态映射到状态 7 时，\(A = \Phi^T D_\mu(\gamma P^\pi - I)\Phi\) 的特征值。
- 解释：为什么在 Baird 反例中，即使将步长 \(\alpha\) 设为 \(10^{-10}\)，TD 仍然发散（只是发散更慢）？
§6.3.9 DQN 系列：工程修复致命三元组 ⭐⭐¶
动机：深度 Q 网络的必要性¶
Mnih 2013（NeurIPS Deep Learning Workshop）与 Mnih 2015（Nature 518:529-533）的 Deep Q-Network（DQN）把 Q-learning 与深度 CNN 结合，在 49 款 Atari 上达到人类水平。从致命三元组视角看，DQN 同时启用了三个元素：非线性 FA（CNN）+ bootstrap（one-step TD target）+ off-policy（replay buffer 混合历史策略数据）。
理论上本该发散，实际上却能工作——其秘诀在于两项关键的工程修补。
经验回放（Experience Replay）的数学分析¶
问题：RL 数据是高度时序相关的——相邻时刻的 \((s_t, a_t, r_t, s_{t+1})\) 和 \((s_{t+1}, a_{t+1}, r_{t+1}, s_{t+2})\) 共享状态 \(s_{t+1}\)。神经网络训练假设数据 IID，时序相关数据导致梯度方向高度偏斜，训练震荡。
解决方案：维护一个 Replay Buffer \(\mathcal{D}\)（容量 \(N = 10^6\)），存储历史转移 \((s, a, r, s')\)。每次训练时从中均匀随机采样 mini-batch。
数学作用三重：
(a) 打破时序相关性。 设 Buffer 中存储了 \(N\) 条转移，随机采样 \(B\) 条。当 \(N\) 足够大时，采样的 \(B\) 条之间近似独立——因为它们来自时间上分散的不同片段。严格地，若 MDP 的混合时间为 \(\tau_{\text{mix}}\)，且 \(N \gg B \cdot \tau_{\text{mix}}\)，则 mini-batch 内的相关性为 \(\mathcal{O}(\tau_{\text{mix}} / N)\)——趋于零。
(b) 平均化多时间窗策略。 Buffer 中的数据来自不同时期的策略 \(\pi_1, \pi_2, \dots\)。均匀采样等价于对这些策略的"平均行为分布"做更新，比纯 off-policy（只用最旧策略数据）的分布错配更温和。
(c) 样本复用。 每条数据被采样约 \(N_{\text{epochs}} = \text{total training steps} \cdot B / N\) 次。典型 DQN 中每条数据被使用 8-10 次——这是 off-policy 方法数据效率高的根本来源。
如果不用经验回放会怎样： Lin 1992 的早期实验表明，不用 replay 的 Q-learning + 神经网络在简单任务上就无法收敛——网络"过拟合"当前局部轨迹，一旦策略改变进入新区域，旧区域的 Q 值立即退化。
目标网络（Target Network）的半梯度稳定性分析¶
问题：Q-learning 的 target 是 \(r + \gamma \max_{a'} Q_\theta(s', a')\)。如果用同一个网络 \(Q_\theta\) 既计算估计值又计算目标值，每次更新 \(\theta\) 都会**同时改变**目标——相当于"狗追自己的尾巴"，优化方向不稳定。
解决方案：创建两个网络： - 主网络（\(Q_\theta\)）：实时更新，负责选择动作 - 目标网络（\(Q_{\theta^-}\)）：参数冻结，负责计算 target
TD target 变为：\(y = r + \gamma \max_{a'} Q_{\theta^-}(s', a')\)
每 \(C\) 步（Nature 版 \(C = 10000\)）硬复制 \(\theta^- \leftarrow \theta\)。
数学分析：在两次复制之间，target \(y\) 对于 \(\theta\) 是常数——损失函数 \(L(\theta) = \mathbb{E}[(Q_\theta(s,a) - y)^2]\) 变成了标准的监督学习回归问题！Semi-gradient 的"追尾"问题被消除。
代价是引入了**目标陈旧性**——\(\theta^-\) 比 \(\theta\) 落后最多 \(C\) 步。但这是可控的：只要网络在 \(C\) 步内不剧烈变化，陈旧偏差有界。
**软更新（Soft Update / Polyak Averaging）**作为替代方案（SAC、TD3 使用）： $\(\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-, \quad \tau \in [10^{-3}, 10^{-2}]\)$
软更新等价于对 \(\theta\) 做指数移动平均（EMA），类似低通滤波器——过滤训练中的高频噪声，保留参数变化的大趋势。
Double DQN：过估计修正¶
问题：Q-learning 的 \(\max_{a'} Q(s', a')\) 操作导致系统性**正偏估计**。
数学推导：设真值 \(Q^*(s', a_i)\) 加零均值噪声 \(\epsilon_i\)：\(\hat{Q}(s', a_i) = Q^*(s', a_i) + \epsilon_i\)。则 $\(\mathbb{E}[\max_i \hat{Q}(s', a_i)] \geq \max_i \mathbb{E}[\hat{Q}(s', a_i)] = \max_i Q^*(s', a_i)\)$
由 Jensen 不等式（\(\max\) 是凸函数），取最大值再取期望 ≥ 取期望再取最大值。偏差恒为正，且噪声越大偏差越大。
在 DQN 中为什么尤其严重？ 网络初始化时 Q 值有大量噪声，\(\max\) 操作选出的不是真正最好的动作而是"恰好被高估的动作"。高估的 Q 值通过 bootstrap 传播到其他状态，形成正反馈循环——Q 值越来越膨胀。
Double DQN 的解决方案（van Hasselt-Guez-Silver 2016）：将"选择动作"和"估值"解耦到两个网络： $\(y = r + \gamma Q_{\theta^-}(s', \arg\max_{a'} Q_\theta(s', a'))\)$
- 主网络选择 \(a^* = \arg\max_{a'} Q_\theta(s', a')\)（可能过高估计）
- 目标网络对 \(a^*\) 估值 \(Q_{\theta^-}(s', a^*)\)（独立估计，不被主网络偏差污染）
在独立性假设下，\(\mathbb{E}[Q_{\theta^-}(s', a^*)]\) 不再有系统正偏——因为 \(\theta^-\) 的噪声与 \(\theta\) 用于选择 \(a^*\) 的噪声是独立的。
Dueling DQN：V+A 分解¶
Wang et al. 2016（ICML Best Paper）将 \(Q(s,a)\) 显式分解为： $\(Q(s,a) = V(s) + A(s,a) - \frac{1}{|\mathcal{A}|}\sum_{a'} A(s,a')\)$
- Value 流 \(V(s)\)：状态的"固有好坏"（不依赖动作）
- Advantage 流 \(A(s,a)\)：选择 \(a\) 比平均动作好/坏多少
为什么有效？ 在很多状态下（如 Atari 中空地移动），不同动作的 Q 值差别很小（advantage ≈ 0）。此时学 \(V(s)\) 的信号更强——不需要尝试每个动作就能学到"这个状态大概值多少"。只有在关键决策点，advantage 才提供有意义的区分。
Prioritized Experience Replay (PER)¶
Schaul et al. 2016（ICLR）：按 TD 误差的绝对值 \(|\delta_t|^\omega\) 对 Buffer 做优先级采样。
直觉：\(|\delta_t|\) 大的转移是"模型最意外/最不准"的——从中学到的信息最多。均匀采样浪费大量时间在"已经学好"的转移上。
数学修正：非均匀采样改变了梯度的期望方向。必须用重要性权重 \(w_t = (N \cdot P(t))^{-\beta}\) 修正，否则收敛到错误的不动点。这是 importance sampling 纠正分布偏移的经典应用。
DQN 的完整训练循环¶
将上述组件整合，DQN 的完整训练循环为：
- 采样：从环境中执行 \(\varepsilon\)-greedy 策略（基于 \(Q_\theta\)），将 \((s, a, r, s', \text{done})\) 存入 Replay Buffer
- 采样 Mini-batch：从 Buffer 均匀随机采样 \(B = 32\) 条（或用 PER 加权采样）
- 计算 Target：\(y_i = r_i + \gamma(1 - \text{done}_i) \cdot \max_{a'} Q_{\theta^-}(s'_i, a')\)
- 计算 Loss：\(L = \frac{1}{B}\sum_{i=1}^B (Q_\theta(s_i, a_i) - y_i)^2\)（或 Huber loss）
- 梯度下降：\(\theta \leftarrow \theta - \eta\nabla_\theta L\)（注意：\(y_i\) 对 \(\theta\) 不求梯度！）
- Target 更新：每 \(C\) 步硬复制 \(\theta^- \leftarrow \theta\)，或每步软更新 \(\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-\)
- \(\varepsilon\) 衰减：\(\varepsilon_t = \max(\varepsilon_{\min}, \varepsilon_{\text{start}} - t/T_{\text{decay}})\)
为什么用 Huber loss 而非 MSE？ MSE loss \(L = (Q - y)^2\) 的梯度 \(2(Q-y)\) 在 \(|Q-y|\) 大时梯度也大——可能导致参数剧烈跳变。Huber loss 在 \(|Q-y| > 1\) 时退化为线性，截断了大 TD 误差的梯度——相当于对异常值（outlier）做鲁棒回归。Nature DQN 原文使用 MSE，但后续工作（包括 Rainbow）普遍使用 Huber。
n-step DQN¶
将 one-step target 替换为 n-step target： $\(y = \sum_{k=0}^{n-1} \gamma^k R_{t+k+1} + \gamma^n \max_{a'} Q_{\theta^-}(S_{t+n}, a')\)$
\(n \in [3, 5]\) 是常用范围。优点：信息传播更快（一次更新传播 \(n\) 步奖励信号而非 1 步）；缺点：引入更重的 off-policy 偏差（\(n\) 步内策略可能已改变），且实现复杂度更高（需要在 Buffer 中存储连续 \(n\) 步的信息）。
Rainbow 的 ablation 表明 n-step（\(n=3\)）是单项贡献最大的改进之一——说明信息传播速度是 DQN 性能的重要瓶颈。
Rainbow 集成¶
Hessel et al. 2018（AAAI）将 6 项改进集成：Double + Dueling + PER + n-step (\(n=3\)) + Distributional (C51) + Noisy Nets。
各组件的定量贡献（Ablation）：
| 去掉的组件 | 性能下降幅度 | 原因 |
|---|---|---|
| Distributional (C51) | 大 | 更丰富的学习信号 |
| Multi-step (n=3) | 大 | 加速信息传播 |
| Prioritized Replay | 大 | 聚焦高信息量样本 |
| Dueling | 中 | 改善 V 学习效率 |
| Double | 中 | 抑制过估计 |
| Noisy Nets | 小 | 更好的探索（可被 ε-greedy 近似替代） |
这个 ablation 对工程实践的指导意义：如果计算预算有限，优先实现 n-step + PER + Distributional（贡献最大的三项），再考虑 Double + Dueling。
一句话总结¶
DQN 家族的每一项设计都指向致命三元组的某个病理：
| 设计 | 对治的病理 |
|---|---|
| Target network | Bootstrap 的"追尾"风险 |
| Replay buffer | Off-policy 的分布错配 |
| Reward clipping | 梯度尺度不稳定 |
| Double Q | \(\max\) bias 的正反馈 |
| Dueling | 稀疏 advantage 信号 |
| PER | 均匀采样的信息浪费 |
即便如此，DQN 在非线性 FA 下没有任何形式化收敛保证——仅是工程意义上的"实用修补"。
⚠️ 常见陷阱¶
⚠️ 编程陷阱：DQN target network 更新频率错配
错误表现：\(C\) 太小（如 100）——target 更新太频繁，追尾效应未被充分抑制；\(C\) 太大（如 100000）——target 过于陈旧，学习信号滞后严重。
诊断方法：监控 Q 值的增长曲线。如果 Q 单调无限增大→ \(C\) 太小或有 max bias 问题。如果 Q 学习极慢→ \(C\) 太大。
经验法则：Nature DQN 用 \(C = 10000\)；soft update 用 \(\tau \in [10^{-3}, 10^{-2}]\)（等价于 \(C \approx 1/\tau = 100 \sim 1000\)）。
💡 概念误区：认为"DQN 能处理连续动作空间"
错误理解：DQN 用神经网络逼近 Q 值，应该能处理任何维度。
实际上：DQN 的核心是 \(\max_{a'} Q(s', a')\)——需要在动作空间上做 argmax。连续动作空间中这个 argmax 本身就是一个优化问题（非凸、高维）。离散化 \(k\) 维连续动作到每维 \(m\) 格点需要 \(m^k\) 个离散动作——维度诅咒再次降临。这就是为什么连续控制用 DDPG/TD3/SAC 而非 DQN。
练习¶
- 推导 single DQN 的过估计偏差：设 \(\hat{Q}(s', a_i) = Q^*(s', a_i) + \epsilon_i\)，\(\epsilon_i \sim \mathcal{N}(0, \sigma^2)\) iid，\(|\mathcal{A}| = 10\)，计算 \(\mathbb{E}[\max_i \hat{Q}] - \max_i Q^*\) 的数值。
- 解释 target network 的软更新公式 \(\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-\) 为什么等价于对 \(\theta\) 的历史轨迹做指数加权平均。
§6.3.A GTD/TDC 算法：Off-policy 收敛的梯度方法 ⭐⭐⭐¶
动机：从 semi-gradient 到 true gradient¶
Semi-gradient TD 不是任何损失函数的真梯度——这是它在 off-policy 下可能发散的根本原因。一个自然的想法是：直接定义合适的损失函数，对其做真正的 SGD。
Sutton 等在 2008-2009 年的系列工作（NIPS 2008 GTD、ICML 2009 GTD2/TDC）给出了答案：最小化 MSPBE。
MSPBE 的梯度推导¶
回顾 MSPBE 的定义： $\(\mathrm{MSPBE}(\theta) = \|\Pi_D T^\pi V_\theta - V_\theta\|_D^2 = (\mathbb{E}[\delta\phi])^T C^{-1} (\mathbb{E}[\delta\phi])\)$
其中 \(C = \mathbb{E}[\phi\phi^T]\)。对 \(\theta\) 求梯度： $\(\nabla \mathrm{MSPBE}(\theta) = -2 \underbrace{\mathbb{E}[(\phi - \gamma\phi')\phi^T]}_{A^T} \underbrace{C^{-1} \mathbb{E}[\delta\phi]}_{w^*}\)$
问题：这涉及**两个期望的乘积** \(A^T \cdot C^{-1} \cdot b\)，不能用单个样本无偏估计（因为 \(\mathbb{E}[XY] \neq \mathbb{E}[X]\mathbb{E}[Y]\) 一般不成立）。
解决方案：引入辅助权重 \(w\) 来在线估计 \(C^{-1} \mathbb{E}[\delta\phi]\)，形成**两时间尺度**更新：
GTD2 算法¶
\(w\) 在快时间尺度上（步长 \(\beta > \alpha\)）估计 \(C^{-1}\mathbb{E}[\delta\phi]\)；\(\theta\) 在慢时间尺度上沿 MSPBE 梯度下降。
TDC（TD with Gradient Correction）¶
第一项 \(\alpha\delta_t\phi_t\) 是普通 semi-gradient TD 更新，第二项 \(-\alpha\gamma\phi'_t(\phi_t^T w_t)\) 是**梯度修正项**——恰好补偿 semi-gradient 遗漏的梯度分量。TDC 在 on-policy 下退化为近似 TD（修正项趋于零），在 off-policy 下保证收敛。
Emphatic TD（另辟蹊径）¶
Sutton-Mahmood-White 2016（JMLR Vol. 17）不改目标函数，而是改采样权重。通过一个时变 emphasis 权重 \(M_t\) 放缩每步更新，使期望更新矩阵在 off-policy 下仍正定：
\(M_t\) 由 follow-on trace 递推计算： $\(F_t = \gamma \rho_{t-1} F_{t-1} + I_t\)$ $\(M_t = \lambda I_t + (1-\lambda) F_t\)$
其中 \(\rho_t = \pi(A_t|S_t)/\mu(A_t|S_t)\) 是 importance sampling 比率，\(I_t\) 是 interest 函数（通常取 1）。
直觉解释：Emphatic TD 的核心思想是"不是所有样本都应该被平等对待"。Off-policy 时某些状态被过度采样（相对于目标策略的稳态分布），emphasis 权重 \(M_t\) 通过放大/缩小不同样本的影响力来"修正"采样分布，使期望更新矩阵重新正定。
优缺点对比：
| 维度 | GTD/TDC | Emphatic TD |
|---|---|---|
| 参数向量数 | 2（\(\theta\) 和 \(w\)） | 1（\(\theta\)） |
| 超参数 | 2 个步长（\(\alpha\), \(\beta\)） | 1 个步长 |
| 方差 | 较低 | 可能很大（\(M_t\) 可能爆炸） |
| 理论保证 | 严格（Maei 2011） | 严格（Yu 2015 COLT） |
| 实际使用 | 研究中 | 研究中 |
Saddle-point formulation（GTD 的另一种视角）：MSPBE 最小化可以等价写成一个 saddle-point 问题： $\(\min_\theta \max_w \; 2w^T \mathbb{E}[\delta\phi] - w^T C w\)$
内层最大化关于 \(w\) 是凸的（给出 \(w^* = C^{-1}\mathbb{E}[\delta\phi]\)），外层最小化关于 \(\theta\) 用此 \(w^*\) 代入就是 MSPBE。GTD2 的双时间尺度更新正是这个 min-max 问题的交替梯度下降/上升——快时间尺度 \(w\) 做梯度上升追踪内层最优，慢时间尺度 \(\theta\) 做梯度下降优化外层。
这个 saddle-point 视角与现代机器学习中的 GAN（生成对抗网络）有深刻的结构类比：GAN 也是一个 min-max 问题，也需要两个网络以不同学习率交替优化。理解 GTD 的 saddle-point 结构有助于理解现代 RL 中双时间尺度方法（如 SAC 的 temperature 自动调节）的设计思想。
GTD 家族的历史演进¶
| 年份 | 算法 | 创新 | 出处 |
|---|---|---|---|
| 2008 | GTD | 首个 \(O(d)\) off-policy 收敛 TD | Sutton-Szepesvari-Maei, NIPS |
| 2009 | GTD2/TDC | MSPBE 真梯度 + 修正项 | Sutton-Maei 等, ICML |
| 2010 | GQ(λ) | 扩展到 Q 值 + 资格迹 | Maei-Sutton, ICML |
| 2015 | Proximal GTD | 加正则化防止 \(w\) 爆炸 | Liu 等, NIPS |
| 2016 | Emphatic TD(λ) | 不改目标，改权重 | Sutton-Mahmood-White, JMLR |
| 2020 | TDRC | 正则化修正，更稳定 | Ghiassian 等, AAAI |
⚠️ 常见陷阱¶
💡 概念误区：认为"GTD 比 TD 好所以应该总用 GTD"
实际上：GTD 有收敛保证但收敛**更慢**——因为它需要双时间尺度，且 MSPBE 梯度中 \(C^{-1}\) 的估计本身就是一个子问题。在 on-policy 情形下，普通 semi-gradient TD 既收敛又快，没有理由用 GTD。GTD 只在**必须 off-policy 且需要线性 FA 收敛保证**时才值得使用。
🧠 思维陷阱：认为"GTD 解决了致命三元组所以可以放心用 off-policy + FA + bootstrap"
新手想法：GTD 在 off-policy 线性 FA 下有收敛保证，所以致命三元组不再是问题。
实际上：GTD 只在**线性** FA 下有保证。非线性 FA（神经网络）下 GTD 没有收敛性定理。而且 GTD 的收敛速度通常比 on-policy TD 慢很多——在实践中很少比 target network + replay 这种工程方案表现更好。致命三元组对非线性 FA 仍然是根本性的开放问题。
练习¶
- 写出 TDC 更新规则的完整形式，并验证当 \(w = 0\)（修正项为零）时退化为普通 TD(0)。
- 解释为什么 GTD 需要两个时间尺度（\(\beta > \alpha\)），如果 \(\beta = \alpha\) 会出什么问题。
- 推导 MSPBE 的 saddle-point 形式：从 \(\mathrm{MSPBE}(\theta) = b^T C^{-1} b\)（其中 \(b = \mathbb{E}[\delta\phi]\)）出发，利用 \(x^T A^{-1} x = \max_w [2w^T x - w^T A w]\) 得到 min-max 形式。
§6.3.B LSTD 与 LSPI ⭐⭐⭐¶
动机：用最小二乘替代随机梯度¶
TD(0) 用随机梯度逐步逼近不动点，收敛速率为 \(\mathcal{O}(1/\sqrt{n})\)。能否直接**求解**投影 Bellman 方程而非迭代逼近？
LSTD：最小二乘时序差分¶
投影 Bellman 方程 \(\Phi\theta^* = \Pi_D T^\pi \Phi\theta^*\) 的闭式条件为： $\(\mathbb{E}[\phi_t(\phi_t - \gamma\phi_{t+1})^T]\theta = \mathbb{E}[r_t \phi_t]\)$
用样本平均估计两端： $\(A_T = \frac{1}{T}\sum_{t=0}^{T-1} \phi_t(\phi_t - \gamma\phi_{t+1})^T, \quad b_T = \frac{1}{T}\sum_{t=0}^{T-1} r_t \phi_t\)$ $\(\theta_{\mathrm{LSTD}} = A_T^{-1} b_T\)$
LSTD 与线性回归的联系：LSTD 可以看作一个"广义线性回归"——目标不是 \(y = \phi^T\theta + \epsilon\)（标准回归），而是 Bellman 方程 \(V(s) = r + \gamma V(s')\) 在线性逼近空间中的最小二乘投影。\(A_T\) 类似于协方差矩阵（但不对称！），\(b_T\) 类似于交叉相关。
优缺点：
| 优点 | 缺点 |
|---|---|
| 样本效率高（不依赖步长 \(\alpha\)） | 存储 \(\mathcal{O}(d^2)\)（矩阵 \(A\)） |
| 收敛速率 \(\mathcal{O}(1/n)\)（比 TD 的 \(1/\sqrt{n}\) 快） | 求逆 \(\mathcal{O}(d^3)\) |
| 无超参（不用调步长） | 仅适合中小 \(d\)（\(d \leq 10^4\)） |
LSPI：嵌入策略迭代¶
LSPI（Lagoudakis-Parr 2003，JMLR Vol. 4）将 LSTD 扩展到 Q 版本（LSTDQ）并嵌入策略迭代外循环：
- 策略评估：用 LSTDQ 在当前 batch 上估计 \(Q^\pi\)
- 策略提升：\(\pi' = \text{greedy w.r.t. } Q^\pi\)
- 重复直到策略不再变化
LSPI 是 **off-policy 兼容**的（只要数据覆盖所有状态-动作对），是 batch / offline RL 的经典范式——与 §6.6 的现代 offline RL（CQL、IQL）有直接血缘关系。
LSTD 的递归实现与 Sherman-Morrison 公式¶
直接求逆 \(A_T^{-1}\) 需要 \(\mathcal{O}(d^3)\)，但利用 Sherman-Morrison 公式可以在每步 \(\mathcal{O}(d^2)\) 内递归更新：
设 \(B_T = A_T^{-1}\)，则当新数据 \((\phi_t, r_t, \phi_{t+1})\) 到来时： $\(B_{t+1} = B_t - \frac{B_t \phi_t (\phi_t - \gamma\phi_{t+1})^T B_t}{1 + (\phi_t - \gamma\phi_{t+1})^T B_t \phi_t}\)$
这使得 LSTD 可以在线运行，避免了批量求逆的代价。这个递归形式与 Kalman 滤波的增益更新公式结构完全类似——再次印证了 TD 与 Kalman filter 的深层联系。
LSTD 与 TD(0) 的对比¶
| 维度 | TD(0) | LSTD |
|---|---|---|
| 更新方式 | 随机梯度（增量式） | 闭式解（批量/递归） |
| 步长 | 需要调节 \(\alpha\) | 无超参 |
| 样本效率 | \(\mathcal{O}(1/\sqrt{n})\) 收敛 | \(\mathcal{O}(1/n)\) 收敛 |
| 计算复杂度 | \(\mathcal{O}(d)\) per step | \(\mathcal{O}(d^2)\) per step |
| 存储 | \(\mathcal{O}(d)\) | \(\mathcal{O}(d^2)\) |
| 适用规模 | 任意 \(d\) | \(d \leq 10^4\) |
| 非线性 FA | 不适用（但 semi-gradient 可推广） | 不适用 |
选择建议：当特征维度 \(d\) 中等（几十到几千）且需要高样本效率时选 LSTD；当 \(d\) 很大（如神经网络的百万参数）时只能用 SGD 式的 TD。
LSPI 在机器人中的历史地位¶
LSPI 在 2003-2010 年间是机器人 RL 的重要方法，特别是在数据有限的真机场景中。经典应用包括： - 四足机器人步态优化（Kolter-Ng 2009） - 直升机控制（Abbeel et al. 2007 用类似思想） - 机器人抓取策略学习
但 2015 年后随着深度 RL 的兴起（DQN、DDPG、PPO），LSPI 因无法处理高维非线性特征而逐渐退出主流。然而其核心思想——"batch 数据上的 off-policy 策略迭代"——在现代 offline RL（CQL、IQL）中重新焕发生命。
练习¶
- 对一个 2 状态、2 动作的 MDP，手动计算 \(A_T\) 和 \(b_T\)（给定 5 条转移数据），求 \(\theta_{\mathrm{LSTD}}\)。
- 解释为什么 LSTD 的矩阵 \(A_T\) 一般不对称——提示：比较 \(\phi_t(\phi_t - \gamma\phi_{t+1})^T\) 与 \((\phi_t - \gamma\phi_{t+1})\phi_t^T\)。
- 用 Sherman-Morrison 公式推导 LSTD 的递归更新，并解释为什么分母中的 \(1 + (\phi_t - \gamma\phi_{t+1})^T B_t \phi_t\) 在实践中可能接近零（数值不稳定），以及如何通过正则化 \(A_T + \epsilon I\) 解决。
§6.3.C Retrace(λ) 与 V-trace：分布式 RL 的数学基础 ⭐⭐⭐¶
动机：Off-policy 多步 return 的安全性¶
Off-policy 学习中，如果直接使用 n-step return \(G_t^{(n)} = \sum_{k=0}^{n-1} \gamma^k R_{t+k+1} + \gamma^n V(S_{t+n})\)，由于数据由行为策略 \(\mu\) 产生而非目标策略 \(\pi\)，需要 importance sampling (IS) 修正：
问题：IS 比率的乘积可能**指数爆炸**或**趋于零**——当 \(\pi\) 和 \(\mu\) 差异大时，\(n\) 步的 IS 乘积方差为 \(\mathcal{O}(\rho_{\max}^{2n})\)，使估计完全不可用。
这是 off-policy 多步学习的核心挑战：如何在保持正确收敛目标（无偏或低偏差）的同时控制方差？
Retrace(λ)：统一框架¶
Munos 等 2016（NeurIPS）提出 Retrace(λ) 统一了此前的多种方法：
其中 trace coefficient \(c_k = \lambda \min\left(1, \frac{\pi(A_k|S_k)}{\mu(A_k|S_k)}\right)\)（截断的 IS 比率）。
Retrace(λ) 的三大性质：
- 安全性：对**任意**行为策略 \(\mu\)，只要 \(\pi(a|s) > 0 \Rightarrow \mu(a|s) > 0\)（覆盖条件），Retrace(λ) 收敛到 \(Q^\pi\)。不需要 \(\mu \approx \pi\)。
- 低方差：\(c_k \leq 1\) 恒成立（因为 \(\min(1, \cdot) \leq 1\)），所以 trace 系数的乘积 \(\prod c_k\) 不会爆炸——方差被天然控制。
- 高效性：当 \(\pi \approx \mu\) 时，\(\pi/\mu \approx 1\)，\(c_k \approx \lambda\)，退化为 on-policy TD(λ)——充分利用了 on-policy 数据的效率。
历史意义：Retrace(λ) 还顺带证明了 Watkins Q(λ) 的收敛性——这是 1989 年 Watkins 提出以来悬而未决近 30 年的开放问题。
V-trace：分布式 Actor-Learner 架构¶
Espeholt et al. 2018（IMPALA，ICML）为分布式训练量身定制了 V-trace。在 IMPALA 架构中： - Actor（数百个）在各自环境中生成数据 - Learner（中央）用这些数据训练网络
由于 actor 和 learner 的参数不同步（策略滞后 policy lag），actor 用的策略 \(\mu\) 总比 learner 当前策略 \(\pi\) "落后"几步。V-trace 处理这种滞后：
其中 \(c_i = \min(\bar{c}, \pi(A_i|S_i)/\mu(A_i|S_i))\)，\(\rho_t = \min(\bar{\rho}, \pi(A_t|S_t)/\mu(A_t|S_t))\)。
两个截断阈值的物理含义： - \(\bar{\rho}\) 控制**收敛不动点**：\(\bar{\rho} = 1\) 收敛到 \(V^\pi\)；\(\bar{\rho} > 1\) 收敛到介于 \(V^\pi\) 与 \(V^\mu\) 之间的中间策略 - \(\bar{c}\) 控制**方差**：\(\bar{c}\) 越小，trace 衰减越快，方差越小但偏差越大
IMPALA 的工程影响：在 DMLab-30 多任务上吞吐量比 A3C 高 3 个数量级。SEED RL（2020）进一步扩展到 TPU。MuZero 也使用 Retrace-like 的 reanalysis 技术。
练习¶
- 证明：当 \(\bar{\rho} = \bar{c} = +\infty\)（不截断）时，V-trace 退化为完整 IS 估计。当 \(\bar{\rho} = \bar{c} = 1\) 且 \(\pi = \mu\)（on-policy）时退化为 TD(λ)。
- 解释为什么 Retrace(λ) 的 \(c_k = \lambda\min(1, \pi/\mu)\) 设计保证了 \(\prod c_k\) 不发散——即使 \(\pi/\mu\) 很大。
§6.3.D Distributional RL 与值分布 ⭐⭐⭐¶
动机：为什么只学均值不够¶
传统 TD 学 \(Q^\pi(s,a) = \mathbb{E}[\sum \gamma^k R_{t+k+1}]\)——只学回报的**一阶矩**（均值）。但很多实际决策需要了解回报的**完整分布**： - 风险敏感决策：机器人不仅要知道"平均回报多少"，还要知道"最坏情况有多差" - 探索：不确定性大的状态-动作对值得更多探索 - 辅助学习信号：分布提供比均值更丰富的梯度信号
分布 Bellman 方程¶
Bellemare-Dabney-Munos 2017（ICML）提出学整个回报分布 \(Z^\pi(s,a)\)： $\(Z^\pi(s,a) \stackrel{D}{=} R(s,a) + \gamma Z^\pi(S', A'), \quad A' \sim \pi(\cdot|S')\)$
等号上的 \(D\) 表示分布相等（不仅是均值相等）。
分布 Bellman 算子在 Wasserstein 度量下是 \(\gamma\)-压缩： $\(\bar{d}_p(\mathcal{T}^\pi Z_1, \mathcal{T}^\pi Z_2) \leq \gamma \bar{d}_p(Z_1, Z_2)\)$
其中 \(\bar{d}_p\) 是 \(p\)-Wasserstein 距离的上确界形式。这保证了分布 Bellman 方程存在唯一的不动点分布。
C51 算法¶
C51 用 51 个原子（atoms）\(\{v_i\}_{i=1}^{51}\) 均匀分布于 \([V_{\min}, V_{\max}]\)，神经网络输出 51 维 softmax 概率向量 \(p(s,a)\)，表示回报分布的离散近似。
训练时：TD target 是分布的 \(\gamma\)-缩放加平移 \(r\)，再投影回原子网格（因为 \(r + \gamma v_i\) 通常不落在网格点上），用 KL 散度作为损失回归。
QR-DQN 与 IQN¶
QR-DQN（Dabney 2018）用 \(N\) 个分位数代替固定原子，做分位数回归。优势：不需要预设 \(V_{\min}\)、\(V_{\max}\)；理论上证明了在 Wasserstein 度量下的压缩性。
IQN（Implicit Quantile Networks）进一步参数化为连续分位数函数——输入一个分位数 \(\tau \in [0,1]\)，输出对应的回报值。更灵活但计算量更大。
Distributional RL 在机器人中的应用¶
- D4PG（Barth-Maron 2018）：DDPG + C51 critic + N-step + PER + 分布式 actor，在 DMControl 困难任务上显著超越 DDPG
- DSAC（Duan 2021）：SAC 的 critic 改为分位数 distributional，抑制 Q 过估
- 风险敏感控制：利用回报分布的 CVaR（条件风险值）做保守决策——适合安全关键的机器人任务
练习¶
- 解释为什么 C51 需要投影步骤：当 reward \(r = 0.3\) 且 \(\gamma = 0.99\) 时，原子 \(v_i\) 的 target \(r + \gamma v_i\) 为什么不再落在原始网格上？
- 比较 C51 的 KL 散度损失与 QR-DQN 的分位数回归损失在理论性质上的区别（提示：投影后的 Wasserstein 压缩性）。
§6.3.E 与控制理论的深层映射 ⭐⭐⭐¶
为什么控制理论视角重要¶
理解 TD 学习最深的方式之一，是把它放回控制理论和滤波理论的语境。对于有控制背景的机器人工程师来说，TD 不是"机器学习的新发明"，而是经典系统辨识和自适应控制在 MDP 框架下的自然延伸。这个视角不仅帮助理解，更帮助诊断——当 TD 学习出问题时，用控制理论的语言往往能更快定位根因。
TD 作为随机版策略评估¶
精确策略评估解 \(V^\pi = T^\pi V^\pi\)，即线性方程 \((I - \gamma P^\pi) V^\pi = r^\pi\)，解为 \(V^\pi = (I - \gamma P^\pi)^{-1} r^\pi\)。若 \(P^\pi\)、\(r^\pi\) 已知且可操作，直接求解（需 \(\mathcal{O}(|\mathcal{S}|^3)\)）。
TD(0) 是这个线性系统的在线随机逼近：每个样本 \((S_t, R_{t+1}, S_{t+1})\) 提供 \((I - \gamma P^\pi)\) 的一行（对应 \(S_t\) 行）与 \(r^\pi\) 的一个元素的无偏估计。TD(0) 的期望更新方向恰好是 Richardson 迭代 \(\theta \leftarrow \theta - \eta(A\theta - b)\)（其中 \(A = I - \gamma P^\pi\), \(b = r^\pi\)）的随机化版本。
Q-learning 作为随机版值迭代：精确 VI \(V_{k+1} = T^* V_k\) 对应确定性算子迭代。Q-learning 是 \(T^*\) 作用在 Q 函数空间上的**异步随机逼近**——每次只更新一个 \((s,a)\) 坐标、用一个样本估计期望。Tsitsiklis 1994 的异步 SA 理论正是为证明这种不完全更新方式的收敛性而建立。
TD 与 Kalman Filter 的深刻类比¶
（Bertsekas-Tsitsiklis 1996 Ch.6；Meyn 2022 Ch.10）
这个类比是理解 TD 数学本质最深刻的视角之一。考虑线性测量模型： $\(y_t = \phi_t^T \theta^* + \varepsilon_t\)$
其中 \(\theta^*\) 是未知参数（类似真实值函数的参数），\(\phi_t\) 是特征向量，\(\varepsilon_t\) 是测量噪声。
Kalman 滤波（或 RLS）更新： $\(\theta_{t+1} = \theta_t + K_t(y_t - \phi_t^T \theta_t)\)$
其中 \(K_t\) 是 Kalman 增益，\((y_t - \phi_t^T\theta_t)\) 是 innovation（新息）——预测与观测之间的偏差。
TD 更新 \(\theta_{t+1} = \theta_t + \alpha \phi_t \delta_t\) 与此结构完全平行：
| Kalman Filter | TD Learning |
|---|---|
| 未知参数 \(\theta^*\) | 真实值函数参数 \(\theta^*\) |
| 观测 \(y_t\) | TD target \(R_{t+1} + \gamma\phi_{t+1}^T\theta\) |
| 预测 \(\phi_t^T\theta_t\) | 当前估计 \(\phi_t^T\theta_t\) |
| Innovation \(y_t - \hat{y}_t\) | TD 误差 \(\delta_t\) |
| Kalman Gain \(K_t\) | 步长 \(\alpha \phi_t\) |
| 协方差更新 \(P_{t+1}\) | （无，用固定步长替代） |
关键对应： - 在最优点 \(\theta = \theta^*\) 处 \(\mathbb{E}[\delta_t | S_t] = 0\)——类似 Kalman 的 innovation 白化性质 - 更新方向 \(\phi_t \delta_t\) 的期望 \(\mathbb{E}[\phi_t\delta_t]\) 是 Bellman 残差的协方差投影——正交性原理（orthogonality principle）
LSTD 就是这个类比的闭式版：RLS（递归最小二乘）在标准回归中直接给出闭式解 \((X^TX)^{-1}X^Ty\)；LSTD 在 Bellman 方程的投影问题中给出闭式解 \(A_T^{-1}b_T\)。结构完全平行。
Choi-Van Roy 2006（Discrete Event Dynamic Systems）与 Geist-Pietquin 2010（JAIR 39）的 "Kalman Temporal Differences" 明确把 TD 作为广义 Kalman filter 在线性不动点方程上的推广。
Advantage as Innovation¶
Actor-critic 的 policy gradient \(\nabla J \approx \mathbb{E}[\delta_t \nabla \log \pi]\) 中，\(\delta_t\) 就是 innovation——它衡量"实际转移比预期好/坏多少"。GAE 是"λ-smoothed innovation"——类似对 innovation 序列做低通滤波（多步 Kalman smoother），得到更稳定的 advantage 估计。
Meyn 2022 §10.2 明确指出：Advantage function 就是 value function 预测问题中的 innovation process。这不是隐喻而是数学等价——在线性 critic 下可以严格证明。
致命三元组与系统辨识的 Off-policy 类比¶
系统辨识中有一个经典问题：用策略 \(\pi\) 生成的数据来估计另一个策略 \(\mu\) 下的系统响应。这需要 IS 权重或干预假设（intervention assumption）。RL 的 off-policy evaluation 是这个问题在 MDP 框架下的特例。
这个类比的工程价值在于：系统辨识领域 50 年的经验（如持续激励条件、数据充分性、病态问题的正则化）可以直接迁移到 RL。例如： - 系统辨识中的"持续激励条件" \(\leftrightarrow\) RL 中的"充分探索" - 辨识中的"正则化最小二乘" \(\leftrightarrow\) LSTD 的正则化 \(A + \epsilon I\) - 辨识中的"遗忘因子" \(\leftrightarrow\) TD 的步长衰减或 replay buffer 的 FIFO 替换
连续时间 TD 与 HJB 预告¶
当采样间隔 \(\Delta t \to 0\) 时，离散 TD 误差 \(\delta_t / \Delta t\) 退化为连续时间 Bellman（HJB）方程的残差： $\(\rho V(x) - \mathcal{L}^\pi V(x) - r(x, \pi(x)) = 0\)$
其中 \(\mathcal{L}^\pi\) 是策略 \(\pi\) 诱导的扩散过程的生成元算子。连续时间 TD 学习（Doya 2000）和基于 HJB 方程的 RL 将在 §6.4 中详细展开。这个连续化视角对于机器人控制尤其重要——因为机器人本质上是连续时间系统，离散 TD 只是其在采样时钟下的近似。
ODE 视角预告：非线性 FA 的稳定性分析¶
Borkar 2008《Stochastic Approximation: A Dynamical Systems Viewpoint》 建立了 SA 与 ODE 之间的桥梁：将随机更新 \(\theta_{t+1} = \theta_t + \alpha_t f(\theta_t, X_t)\) 的长时间行为归结为其**平均 ODE** \(\dot\theta = \bar{f}(\theta) \triangleq \mathbb{E}_{X\sim\mu}[f(\theta, X)]\) 的稳定性。
线性 on-policy TD 的 ODE：\(\dot\theta = -A\theta + b\)，其中 \(A = \Phi^T D^\pi(I - \gamma P^\pi)\Phi\)。由 TVR 证明 \(A\) 正定——ODE 全局线性稳定，唯一均衡点 \(\theta^* = A^{-1}b\)。
非线性 FA 或 off-policy 的风险：\(A\) 未必正定时，ODE 可能有不稳定均衡点——随机迭代在噪声驱动下偏离均衡，参数发散。Tsitsiklis-Van Roy 1997 附录给出的非线性反例正是构造了 ODE 有不稳定均衡的情形。
DQN 的"幸运"：非线性 FA (CNN) 下没有一般性的稳定性保证。DQN 在 Atari 上"恰好"工作，可能是因为 CNN 在这些任务上的特征表示"接近线性"——使得局部 ODE 的 \(A\) 正定。但在更复杂任务上这个"幸运"不一定持续。
严格的 ODE 方法分析留给 §6.5 专题。
练习¶
- 写出 Kalman filter 与 LSTD 的更新公式对比，指出哪些项对应。
- 解释为什么 TD(0) 不做协方差更新（不像 Kalman filter），这在什么条件下是合理的简化？
- 对线性 on-policy TD 的平均 ODE \(\dot\theta = -A\theta + b\)，证明当 \(A\) 正定时均衡点 \(\theta^* = A^{-1}b\) 是全局渐近稳定的（提示：用 Lyapunov 函数 \(L(\theta) = (\theta - \theta^*)^T A (\theta - \theta^*)\)）。
§6.3.F 机器人应用映射 ⭐⭐¶
为什么机器人很少直接用 DQN¶
核心观察：legged locomotion、dexterous manipulation 等主流机器人 RL 任务，2020 年后绝对主流是 PPO 与 SAC，DQN 几乎不出现在真机上。这背后有清晰的数学原因：
(1) 连续动作空间天然不友好。 机器人控制多为关节扭矩、末端速度、位姿命令——连续高维。DQN 依赖 \(\max_a Q(s,a)\)，离散化 \(k\) 维动作到每维 \(m\) 格点至少需要 \(m^k\) 个离散动作。以 12 自由度四足机器人为例，每维 10 格点就有 \(10^{12}\) 个动作——维度诅咒立刻回归。PPO/SAC/TD3/DDPG 原生处理连续动作。
唯一例外是 QT-Opt（Kalashnikov et al. 2018 CoRL）：用 cross-entropy method (CEM) 在连续动作空间内部做 argmax——相当于"软化的 DQN"，但需要 580k 真机样本 + 7 台 KUKA。
(2) 致命三元组完全命中。 DQN 同时启用 FA + bootstrap + off-policy。在机器人设置下——样本昂贵、数据分布剧烈非平稳（课程学习、domain randomization、sim-to-real）——off-policy bootstrap 的 TD target 极易震荡。PPO 是 on-policy，每次更新前 fresh rollout，\(d^\mu \approx d^\pi\)，不命中三元组。
(3) GPU 并行仿真改变了样本账。 Isaac Gym（NVIDIA 2021）、Brax（Google 2021）、MuJoCo MJX（2023+）可在单 GPU 上同时跑数千环境。Rudin 2021 的 legged_gym 用 4096 并行环境 + PPO，平坦地形 4 分钟训好 ANYmal 四足步态。在这种"仿真超便宜"的范式下，PPO 的"低样本效率"不再是瓶颈，DQN/SAC 的 off-policy 样本效率优势被抹平。
(4) PPO critic 本质是 on-policy TD(λ)。 legged_gym 与 Isaac Lab 的 PPO 使用 GAE： $\(\hat{A}_t^{\mathrm{GAE}(\lambda)} = \sum_{l=0}^{\infty} (\gamma\lambda)^l \delta_{t+l}^V\)$
Critic 的训练 target 是 \(R_t = \hat{A}_t + V(s_t) = \lambda\text{-return}\)。整个流程是 on-policy TD(λ) 的 actor-critic——Tsitsiklis-Van Roy 1997 几乎完美适用，不命中致命三元组。
致命三元组视角的机器人 RL 方法选型¶
| 方法 | FA | Bootstrap | Off-policy | 稳定性 | 机器人常见度 |
|---|---|---|---|---|---|
| PPO + MC critic (\(\lambda=1\)) | 有 | 无 | 无 | 高 | 常见（稀疏奖励） |
| PPO + GAE (\(\lambda \approx 0.95\)) | 有 | 弱 | 无 | 高 | 绝对主流 |
| SAC / TD3 | 有 | 有 | 有 | 中 | 常见（灵巧操作） |
| DQN / QT-Opt | 有 | 有 | 有 | 低 | 少见 |
DQN 在机器人上确实适用的场景¶
尽管主流不用 DQN，但在以下场景中它仍有价值：
-
高层离散决策：选择哪个 motion primitive、去哪个 waypoint、执行哪个技能。动作空间天然离散且小（如 5-20 个选项），DQN 的 off-policy 效率优势可以发挥。
-
视觉导航：动作天然离散（前进/左转/右转/停止），R2D2 风格（LSTM + Distributed DQN）在 DMLab、Habitat、AI2-THOR 等视觉导航任务上表现优秀。
-
大规模离散抓取：QT-Opt 验证了只要数据量足够大（580k 真机样本 + 7 KUKA），off-policy Q-learning 可以在真机上工作。
-
Distributional RL 的机器人应用：
- D4PG（ICLR 2018）：DDPG + C51 critic，在 DMControl 困难任务上超越 DDPG
- DSAC（2021）：SAC + 分位数 distributional critic，在 MuJoCo Humanoid 上超越 SAC/TD3
- 核心价值：风险敏感策略、不确定性估计辅助 sim-to-real
PPO + GAE 为什么稳定：致命三元组的完整分析¶
让我们用致命三元组框架完整分析 PPO 的 critic 训练为什么稳定：
- 函数逼近：PPO critic 使用 MLP/CNN——非线性 FA，命中条件 1
- Bootstrapping：GAE 使用 \(\delta_t = r_t + \gamma V(S_{t+1}) - V(S_t)\)——bootstrap，命中条件 2
- Off-policy：PPO 每次 policy update 前收集 fresh rollout——数据来自当前策略 \(\pi_\theta\)。虽然一个 epoch 内 critic 更新多次用的是同一批数据（轻微 off-policy），但：
- Rollout 长度有限（通常 2048 步）
- Critic epoch 数有限（通常 5-10 次）
- 每次大 policy update 后重新收集数据
- 所以采样分布 \(d^\mu\) 与当前策略 \(d^\pi\) 差异很小
结论：PPO 的 critic 近似 on-policy——它在致命三元组的边缘，但不完全命中。加上 GAE 的 \(\lambda\) 接近 1（减弱 bootstrap 依赖），整体稳定性高。
如果把 PPO 改成完全 off-policy 会怎样？ 如果给 PPO 加一个 replay buffer 存储旧 rollout（如 IPO、ACER），critic 训练会立即面临致命三元组的全部风险。实践中这些方法虽然样本效率更高，但训练不稳定性显著增加——需要更多 trick（如 IS clipping、trust region on critic）来维持。
从 TD 理论到工程实践的完整对应¶
理解本章理论后，机器人 RL 工程中的每个设计选择都有了数学根据：
| 工程实践 | 理论依据 |
|---|---|
| PPO 用 GAE 而非纯 MC | \(\lambda < 1\) 的 TD(λ) 比 MC 方差低，§6.3.4 |
| SAC 用 min-double-Q | Double Q 抑制过估计，§6.3.9 |
| SAC 用 soft target update | Target network 稳定 bootstrap，§6.3.9 |
| Isaac Lab 不用 replay | On-policy 避免致命三元组，§6.3.8 |
| 训练初期用大 \(\lambda\)、后期减小 | V 不准时减少 bootstrap 偏差，§6.3.4 |
| Reward normalization | 控制 TD target 的尺度，防止梯度爆炸 |
| Critic 学习率 > Actor | 类似 GTD 的快-慢时间尺度，§6.3.A |
本章常见误解汇总¶
| 误解 | 正确理解 |
|---|---|
| "TD 学习有偏差，所以不如 MC 好" | TD 的偏差来自 bootstrap（用 \(V(S_{t+1})\) 的估计替代真实回报），但偏差随训练会逐渐消失（\(V\) 趋向真实值）。而 MC 的方差不会自行减小——它来自回报的内在随机性。在长 episode 或连续任务中，MC 的高方差远比 TD 的偏差更有害 |
| "函数逼近只是为了处理大状态空间的工程手段" | 函数逼近不仅仅是"压缩存储"，它从根本上改变了算法的数学性质。投影 Bellman 算子 \(\Pi T^\pi\) 不再是压缩映射（在 sup-norm 下），收敛性依赖于投影范数与转移矩阵的精微交互。致命三元组（off-policy + FA + bootstrapping）的发散正是这种质变的体现 |
| "Baird 反例只是人造的病态情况，实践中不会遇到" | Baird 反例揭示的不是特殊 MDP 的问题，而是期望更新矩阵 \(A\) 可能有正实部特征值的**结构性问题**。任何 off-policy + 线性 FA + TD 的组合都可能触发。DQN 通过 target network 和 experience replay 缓解（而非解决）了这个问题；GTD/TDC 才是理论上的根治方案 |
| "Experience Replay 只是为了打破相关性" | Experience Replay 有三重作用：(1) 打破时间相关性使 SGD 的 i.i.d. 假设近似成立；(2) 提高数据效率（每条经验被多次使用）；(3) 改变有效采样分布（replay buffer 的分布不等于当前策略的分布，这引入了 off-policy 偏差——正是 target network 要补偿的） |
| "Target network 更新越频繁越好" | Target network 的延迟更新（\(\tau\) 小或每 \(C\) 步硬更新）是稳定性的关键。更新太频繁 \(\to\) target 随 online 网络波动 \(\to\) bootstrap target 不稳定 \(\to\) 可能发散。更新太慢 \(\to\) target 过时 \(\to\) 学习效率低。典型 \(\tau=0.005\)（软更新）或 \(C=10000\)（硬更新）是经验平衡点 |
本章小结¶
| 知识点 | 核心结论 | 关键条件 | 适用场景 |
|---|---|---|---|
| MC 方法 | 无偏但高方差 | 需完整 episode | 短 episode、稀疏奖励 |
| TD(0) | 有偏但低方差 | 需 Robbins-Monro 步长 | 长/连续任务 |
| TD(λ) | MC-TD 连续插值 | \(\lambda\) 控制偏差-方差权衡 | 通用（GAE） |
| SARSA | On-policy，学 \(Q^\pi\) | 配合 ε-greedy 迭代 | 安全性敏感场景 |
| Q-learning | Off-policy，学 \(Q^*\) | 充分探索 + R-M 步长 | 数据复用场景 |
| 线性 TD 收敛 | \(\Pi_D T^\pi\) 是 \(\gamma\)-压缩 | On-policy + 线性 FA | 中等规模问题 |
| 致命三元组 | FA + Bootstrap + Off-policy → 可能发散 | 三者同时 | 所有深度 RL |
| DQN | Target network + Replay 工程修补 | 无形式保证 | Atari、离散任务 |
| GTD/TDC | 真梯度下降 MSPBE | 两时间尺度 | Off-policy 线性 FA |
| LSTD/LSPI | 闭式 TD 解 | \(d\) 中小 | Batch/Offline RL |
代码验证：TD 学习核心算法¶
以下 Python 代码用于验证本章的核心理论结论。代码仅作为理论验证工具，不是生产代码。
验证 1：Tabular TD(0) vs MC 在 Random Walk 上的收敛对比¶
import numpy as np
def random_walk_td0(n_episodes=100, alpha=0.1, gamma=1.0):
"""5-state Random Walk: TD(0) 策略评估"""
# 状态 0,1,2,3,4 (终止状态 -1 左端, 5 右端)
V = np.array([0.5, 0.5, 0.5, 0.5, 0.5]) # 初始化
true_V = np.array([1/6, 2/6, 3/6, 4/6, 5/6])
rmse_history = []
for ep in range(n_episodes):
s = 2 # 从中间开始
while 0 <= s <= 4:
# 等概率左右移动
s_next = s + np.random.choice([-1, 1])
# 奖励：到达右终止得1，其他为0
r = 1.0 if s_next == 5 else 0.0
# TD(0) 更新
if 0 <= s_next <= 4:
V[s] += alpha * (r + gamma * V[s_next] - V[s])
else:
V[s] += alpha * (r + 0 - V[s]) # 终止状态值为0
s = s_next
rmse_history.append(np.sqrt(np.mean((V - true_V)**2)))
return V, rmse_history
验证 2：Baird 反例的发散¶
def baird_counterexample(n_steps=1000, alpha=0.01, gamma=0.99):
"""Baird 7-star MDP: 验证 off-policy TD 发散"""
# 特征矩阵 Phi (7x8)
Phi = np.zeros((7, 8))
for i in range(6):
Phi[i, i] = 2.0 # 状态1-6: 2*e_i + e_8
Phi[i, 7] = 1.0
Phi[6, 6] = 1.0 # 状态7: e_7 + 2*e_8
Phi[6, 7] = 2.0
theta = np.array([1., 1., 1., 1., 1., 1., 10., 1.])
theta_history = [theta.copy()]
# 行为策略 mu: dashed 6/7, solid 1/7
# 目标策略 pi: 始终 solid (转到状态7)
for t in range(n_steps):
# 从行为策略采样
if np.random.random() < 6/7: # dashed
s = np.random.randint(0, 6) # 均匀到状态0-5
else: # solid
s = 6
s_next = 6 # 在目标策略下, 总转到状态7
r = 0.0 # 所有奖励为0
# Semi-gradient TD(0) 更新 (off-policy)
delta = r + gamma * Phi[s_next] @ theta - Phi[s] @ theta
theta += alpha * delta * Phi[s]
theta_history.append(theta.copy())
return np.array(theta_history)
# 观察: theta[6] 和 theta[7] 会指数增长!
验证 3：Double DQN 过估计修正¶
def demo_max_bias(n_actions=10, sigma=1.0, n_trials=10000):
"""验证 max 操作导致的正偏估计"""
true_Q = np.zeros(n_actions) # 所有动作真值为0
# Single estimator: max of noisy Q
single_bias = []
for _ in range(n_trials):
Q_noisy = true_Q + np.random.randn(n_actions) * sigma
single_bias.append(np.max(Q_noisy))
# Double estimator: 用一个选动作，另一个估值
double_bias = []
for _ in range(n_trials):
Q1 = true_Q + np.random.randn(n_actions) * sigma
Q2 = true_Q + np.random.randn(n_actions) * sigma
best_a = np.argmax(Q1)
double_bias.append(Q2[best_a])
print(f"Single DQN bias: {np.mean(single_bias):.3f}") # 正偏
print(f"Double DQN bias: {np.mean(double_bias):.3f}") # 约为0
# 当 n_actions=10, sigma=1 时, single bias ≈ 1.54
累积项目：本章新增模块¶
项目：从零构建 TD 学习实验平台
本章新增：
- 模块 1：实现 Tabular TD(0)、SARSA、Q-learning 在 FrozenLake 上对比
- 模块 2：实现线性 TD(0) with tile coding 在 MountainCar 上
- 模块 3：复现 Baird 7-star 反例的发散现象（numpy）
- 模块 4：用 CleanRL 的 dqn.py 训练 CartPole，监控 Q 值增长
前续模块（§6.1）：精确 VI/PI 的 tabular 实现 后续模块（§6.4）：连续时间 TD 与 LQR 解析解对比
延伸阅读¶
| 资源 | 难度 | 内容 |
|---|---|---|
| Sutton-Barto 2018 Ch. 6, 7, 9, 11 | ⭐⭐ | TD/n-step/FA/Deadly Triad 最佳入门 |
| Tsitsiklis-Van Roy 1997 IEEE TAC | ⭐⭐⭐ | 线性 TD 收敛原论文 |
| Bertsekas 2019 RL and Optimal Control Ch. 4-7 | ⭐⭐⭐ | 控制理论视角的 ADP |
| Mnih et al. 2015 Nature | ⭐⭐ | DQN 原论文 |
| Sutton et al. 2009 ICML (GTD2/TDC) | ⭐⭐⭐⭐ | Gradient TD 理论 |
| Baird 1995 ICML | ⭐⭐⭐ | 致命三元组反例 |
| Meyn 2022 Control Systems and RL Ch. 8-10 | ⭐⭐⭐⭐ | ODE/SA/TD 的最深层统一 |
| Hessel et al. 2018 Rainbow | ⭐⭐⭐ | DQN 改进集成 |
| Munos et al. 2016 Retrace(λ) | ⭐⭐⭐⭐ | 安全 off-policy return |
🔧 故障排查手册¶
| 症状 | 可能原因 | 排查步骤 | 相关节 |
|---|---|---|---|
| Q 值单调增大不收敛 | Max bias + 无 Double Q | 1.打印各动作 Q 值 2.启用 Double DQN 3.检查 reward scale | §6.3.9 |
| 线性 TD 参数发散 | Off-policy + 错配分布 | 1.检查采样策略 2.换 GTD/TDC 3.或改 on-policy | §6.3.8 |
| DQN loss 剧烈震荡 | Target 更新太频繁 | 1.增大 \(C\) 或减小 \(\tau\) 2.检查 replay buffer 大小 | §6.3.9 |
| GAE 给出零 advantage | \(\gamma\) 或 \(\lambda\) 设为 0 / critic 完美拟合 | 1.打印 TD 误差分布 2.检查 critic loss 是否趋零 | §6.3.4 |
| Replay buffer 内存爆炸 | 存储了高维观测（如图像） | 1.压缩存储 2.用 LazyFrame 3.减小 buffer size | §6.3.9 |
跨章综合练习¶
综合题 1（需要 §6.1 + §6.3）：对一个 5 状态环形 MDP，分别用精确 VI（§6.1）、Tabular TD(0)、线性 TD(0)（2 维特征）求解 \(V^\pi\)。比较三者的解，验证线性 TD 的逼近误差界 \(\|V_{\theta^*} - V^\pi\| \leq \frac{1}{\sqrt{1-\gamma^2}}\|\Pi V^\pi - V^\pi\|\)。
综合题 2（需要 §6.2 + §6.3）：解释 PPO 中 GAE 的 critic 训练为什么是 on-policy TD(λ)，并说明它如何避免致命三元组。如果把 PPO 的 critic 改成 off-policy（使用 replay buffer），会遇到什么理论风险？
时间预算与节奏建议¶
目标读者：完成 §6.1（精确 DP）和 §6.2（策略梯度基础）、有 PyTorch 工程经验的机器人算法工程师。总预算 3-4 周（每周约 10-12 小时）。
第 1 周：Tabular TD 与 DQN 工程（约 12h）
- Sutton-Barto 2018 Ch. 6, 7 通读 + 笔记（4h）
- 手写 tabular TD(0)、SARSA、Q-learning 在 FrozenLake/Cliff Walking 上实验（3h）
- 读 Mnih 2015 Nature 原文 + CleanRL dqn.py 单文件精读（2h）
- 跑 CleanRL DQN CartPole + Atari Pong baseline（3h）
第 2 周：线性 FA 与 TVR 定理（约 12h） - Bertsekas 2019 Ch. 7 或 Sutton-Barto Ch. 9, 11 深读（4h） - 手推 TVR 1997 四步证明——本周最重要的任务（3h） - 手推 Baird 反例、numpy 复现发散（3h） - 读 TVR 1997 原论文核心引理（2h）
第 3 周：DQN 变体与分布式 RL（约 12h）
- Double、Dueling、PER、Rainbow 各论文摘要 + 代码对照（4h）
- C51 原文 + CleanRL c51.py 精读（3h）
- IMPALA V-trace + Retrace 原论文浏览（2h）
- 机器人视角综述：QT-Opt、D4PG、DSAC 论文摘要（3h）
第 4 周（可选，进阶）：Gradient TD 与深化（约 10h） - Sutton 2009 GTD2/TDC + Emphatic TD 2016 原文（4h） - Meyn 2022 Ch. 8-10 ODE 视角浏览（3h） - 自测题目全答 + 综合练习（3h）
验收标准：能在白板上讲清 (a) Baird 反例机制、(b) TVR 证明四步、(c) DQN target network 对致命三元组的对症下药、(d) 机器人为什么主流用 GAE 而非 off-policy TD。
附录 A：关键定理清单¶
| 编号 | 定理 | 出处 | 结论 |
|---|---|---|---|
| T1 | TD(0) tabular 收敛 | Sutton 1988；Dayan 1992 | \(V_t \to V^\pi\) a.s. |
| T2 | Q-learning tabular 收敛 | Watkins-Dayan 1992；Tsitsiklis 1994 | \(Q_t \to Q^*\) a.s. |
| T3 | On-policy 线性 TD(λ) 收敛 | Tsitsiklis-Van Roy 1997 | 收敛到投影 Bellman 不动点 |
| T4 | \(\Pi_{d^\pi} T^\pi\) 是 \(\gamma\)-压缩 | TVR 1997 核心引理 | \(P^\pi\) 的 \(d^\pi\)-不变性 + Jensen |
| T5 | Off-policy 线性 TD 可发散 | Baird 1995 | 7-star MDP 权重发散 |
| T6 | GTD/TDC off-policy 收敛 | Sutton 2009 | 两时间尺度 SA，最小化 MSPBE |
| T7 | Emphatic TD off-policy 收敛 | Sutton 2016；Yu 2015 | Emphasis 权重使 \(A\) 正定 |
| T8 | 分布 Bellman 算子 Wasserstein 压缩 | Bellemare 2017 | 值分布不动点理论 |
| T9 | Retrace(λ) 安全 off-policy 收敛 | Munos 2016 | 截断 IS 比 |
附录 B：常见陷阱速查表¶
| 陷阱 | 错误表现 | 纠正 |
|---|---|---|
| 把 semi-gradient 当 gradient | 以为 TD 在最小化某损失 | TD target 中 \(\theta\) 需 stop_gradient |
| Off-policy 下用线性 TD 期望收敛 | 参数发散归咎于超参 | 用 GTD/Emphatic/target network |
| PER 忘记 IS 修正 | 收敛到错误分布的不动点 | 必须乘 \((NP(i))^{-\beta}\) |
| 把 TD 收敛极限当 \(V^\pi\) | 线性 TD 收敛到 \(\Phi\theta^*\) | 有 \(1/\sqrt{1-\gamma^2}\) 放大界 |
| DQN 处理连续动作 | 离散化维度爆炸 | 用 SAC/TD3/DDPG |
| C51 投影忽略端点 | 概率泄漏 | clip 到 \([V_{\min}, V_{\max}]\) |
| n-step + off-policy 忘记 IS | 方差爆炸 | 用 Retrace(λ) 或 V-trace |
| Robot critic 用 off-policy TD | 训练震荡 | 用 PPO + GAE |
附录 C：经典论文清单（按时间顺序）¶
| 年份 | 论文 | 作者 | 场所 | 关键贡献 |
|---|---|---|---|---|
| 1988 | Learning to Predict by the Methods of TD | Sutton | Machine Learning 3:9-44 | TD(λ) 定义，线性 TD(0) 收敛性 |
| 1989 | Learning from Delayed Rewards | Watkins | PhD, Cambridge | 首次提出 Q-learning |
| 1992 | Q-learning | Watkins, Dayan | Machine Learning 8:279-292 | Tabular Q-learning 收敛性证明 |
| 1994 | Asynchronous SA and Q-learning | Tsitsiklis | Machine Learning 16:185-202 | 异步 SA 下 Q-learning 收敛 |
| 1995 | Residual Algorithms | Baird | ICML pp.30-37 | 7-star 发散反例 |
| 1996 | Neuro-Dynamic Programming | Bertsekas, Tsitsiklis | Athena Scientific | TD-Kalman 类比 |
| 1997 | TD Learning with FA Analysis | Tsitsiklis, Van Roy | IEEE TAC 42(5):674-690 | On-policy 线性 TD 收敛 |
| 2003 | LSPI | Lagoudakis, Parr | JMLR 4:1107-1149 | LSTDQ + PI |
| 2008 | GTD | Sutton 等 | NIPS 21 | 首个 off-policy 收敛 TD |
| 2009 | GTD2/TDC | Sutton, Maei 等 | ICML pp.993-1000 | MSPBE + 两时间尺度 |
| 2013 | DQN 初版 | Mnih 等 | NeurIPS DL Workshop | CNN + Q-learning + replay |
| 2015 | DQN Nature 版 | Mnih 等 | Nature 518:529-533 | Target network |
| 2016 | Double DQN | van Hasselt 等 | AAAI | 解决 max bias |
| 2016 | Dueling DQN | Wang 等 | ICML Best Paper | V + A 分解 |
| 2016 | PER | Schaul 等 | ICLR | 按 TD 误差优先采样 |
| 2016 | Retrace(λ) | Munos 等 | NeurIPS | 安全 off-policy return |
| 2017 | C51 | Bellemare 等 | ICML | 学值分布 |
| 2018 | Rainbow | Hessel 等 | AAAI | 6 项改进集成 |
| 2018 | IMPALA / V-trace | Espeholt 等 | ICML | 分布式 actor-learner |
| 2018 | QT-Opt | Kalashnikov 等 | CoRL | 大规模真机抓取 |
附录 D：免费 PDF 与在线资源¶
- Sutton-Barto《RL: An Introduction》2nd ed. 官方 PDF：http://incompleteideas.net/book/the-book-2nd.html
- Bertsekas 2019 章节草稿：http://web.mit.edu/dimitrib/www/RLbook.html
- Tsitsiklis-Van Roy 1997：http://web.mit.edu/~jnt/www/Papers/J063-97-bvr-td.pdf
- Baird 1995：https://www.cs.cmu.edu/~leemon/papers/1995_baird_residual.pdf
- DQN Nature 2015：https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf
- Maei 2011 博士论文：https://sites.ualberta.ca/~szepesva/papers/maei_phd.pdf
- Rainbow arXiv:1710.02298；C51 arXiv:1707.06887；IMPALA arXiv:1802.01561
附录 E：视频课程¶
- David Silver RL Course（UCL/DeepMind 2015）：第 4-6 讲覆盖 TD/Q-learning/FA
- Sergey Levine CS285（UC Berkeley）：Lectures 7-9 讲 Q-learning 与 DQN 变体
- Emma Brunskill CS234（Stanford）：第 4-7 讲覆盖 MC/TD/Q-learning/FA
- Hado van Hasselt RL Lecture Series 2021（UCL/DeepMind）：第 4-8 讲
- 赵世钰《强化学习的数学原理》：B 站系列，第 23-26 节覆盖 TD/SARSA/Q-learning
附录 F：C++/Python 库对照¶
| 库 | DQN 完整度 | PER | C51/QR-DQN | 机器人集成 | 代码可读性 |
|---|---|---|---|---|---|
| SB3 | ⭐⭐⭐ | 需 fork | QR-DQN(contrib) | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐ |
| CleanRL | ⭐⭐⭐ | 否 | C51 有 | ⭐⭐ | ⭐⭐⭐⭐⭐ |
| TorchRL | ⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | C51 有 | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ |
| Tianshou | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | 齐全 | ⭐⭐⭐ | ⭐⭐⭐⭐ |
| Dopamine | ⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | 齐全 | ⭐ | ⭐⭐⭐⭐ |
| RLlib | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | C51 有 | ⭐⭐⭐⭐ | ⭐⭐ |
附录 G：自测题目（完整版）¶
T1（TD 推导）：推导 TD(0) 在线性 FA 下的期望更新矩阵 \(A = \Phi^T D(I - \gamma P^\pi)\Phi\)，并说明 \(A\) 正定的充要条件。
T2（Baird 反例）：写出 Baird 7-star 的 \(\Phi\) 矩阵，取 \(D_\mu = I/7\)、\(P^\pi\) 将所有状态映射到状态 7，计算 \(A\) 的特征值。
T3（DQN target network）：论证 target network + replay buffer 近似等价于每个"outer loop"内做监督学习。
T4（TD vs MC 权衡）：给出 TD(0)、TD(λ)、MC 三种估计的方差上界（假设 \(|r_t| \leq R\)）。
T5（Q-learning vs SARSA）：用 \(T^\pi\) 与 \(T^*\) 的定义解释 Cliff Walking 中两者行为差异。
T6（Double DQN 偏差）：推导 \(\max_a \hat{Q}(s,a)\) 的正偏估计来源。
T7（TVR 证明补全）：用 Jensen 不等式严格证明 \(\|P^\pi V\|_{d^\pi} \leq \|V\|_{d^\pi}\)。说明 \(d^\pi\) 换成其他分布是否仍成立。
T8（投影 Bellman 几何）：在 2 维特征、3 状态的玩具例中，画出 \(V^\pi\)、\(\Pi V^\pi\)、TD 不动点 \(\Phi\theta^*\) 三者位置关系。
附录 H：核心公式速查¶
| 算法 | 更新规则 |
|---|---|
| MC | \(V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]\) |
| TD(0) | \(V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]\) |
| TD(λ) backward | \(V(s) \leftarrow V(s) + \alpha\delta_t e_t(s)\) |
| 累积资格迹 | \(e_t(s) = \gamma\lambda e_{t-1}(s) + \mathbb{1}[S_t=s]\) |
| SARSA | \(Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha[R + \gamma Q(S',A') - Q(S_t,A_t)]\) |
| Q-learning | \(Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha[R + \gamma\max_{a'}Q(S',a') - Q(S_t,A_t)]\) |
| Expected SARSA | target: $R + \gamma\sum_{a'}\pi(a' |
| DQN target | \(y = R + \gamma\max_{a'}Q_{\theta^-}(S',a')\) |
| Double DQN | \(y = R + \gamma Q_{\theta^-}(S', \arg\max_{a'}Q_\theta(S',a'))\) |
| Linear TD(0) | \(\theta_{t+1} = \theta_t + \alpha\delta_t\phi(S_t)\) |
| GTD2 | \(w \leftarrow w + \beta(\delta-\phi^Tw)\phi\); \(\theta \leftarrow \theta + \alpha(\phi-\gamma\phi')(\phi^Tw)\) |
| TDC | \(\theta \leftarrow \theta + \alpha\delta\phi - \alpha\gamma\phi'(\phi^Tw)\) |
| LSTD | \(\theta = A_T^{-1}b_T\) |
| GAE | \(\hat{A}_t = \sum_{l=0}^{\infty}(\gamma\lambda)^l\delta_{t+l}^V\) |
| Soft target | \(\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-\) |
| Retrace | \(c_k = \lambda\min(1, \pi/\mu)\) |
| V-trace | \(\rho_t = \min(\bar\rho, \pi/\mu)\), \(c_i = \min(\bar c, \pi/\mu)\) |
| TVR 误差界 | \(\|V_{\theta^*} - V^\pi\|_{d^\pi} \leq \frac{1}{\sqrt{1-\gamma^2}}\|\Pi V^\pi - V^\pi\|_{d^\pi}\) |
| MSPBE | \(\mathrm{MSPBE}(\theta) = (\mathbb{E}[\delta\phi])^T C^{-1}(\mathbb{E}[\delta\phi])\) |
| 期望更新矩阵 | \(A = \Phi^T D^\pi(I - \gamma P^\pi)\Phi\) |
| 投影算子 | \(\Pi_D = \Phi(\Phi^T D\Phi)^{-1}\Phi^T D\) |
关键不等式：
- \(\|P^\pi V\|_{d^\pi} \leq \|V\|_{d^\pi}\)（非扩张，on-policy only）
- \(\|T^\pi V - T^\pi V'\|_{d^\pi} \leq \gamma\|V - V'\|_{d^\pi}\)（\(\gamma\)-压缩）
- \(\mathbb{E}[\max_i \hat{Q}_i] \geq \max_i \mathbb{E}[\hat{Q}_i]\)（Jensen 不等式，max bias）
关键等式：
- \(\mathbb{E}[\delta_t | S_t = s] = 0\) 当且仅当 \(V = V^\pi\)
- \(G_t^\lambda - V(S_t) = \sum_{k=0}^{\infty}(\gamma\lambda)^k\delta_{t+k}\)（forward-backward equivalence）
- TD 不动点：\(\Phi\theta^* = \Pi_{d^\pi}T^\pi\Phi\theta^*\)
附录 I：总结与向后衔接¶
TD 学习的全部美感可以浓缩为一句话：用 bootstrapping 换取样本效率、用 sampling 换取 model-free、用 function approximation 换取可扩展性——而三项优势同时启用时，理论保证会瞬间瓦解。
这是 RL 工程师与理论研究者之间认知割裂的主要来源：Atari 上 DQN 能 work 并不意味着它"收敛"，legged_gym 上 PPO 能 work 也不意味着它不脆弱。
本专题的深层教益有三：
第一，所有 RL 算法的稳定性问题都可以用致命三元组的视角体检——问自己是 FA 还是 bootstrap 还是 off-policy 在作祟，往往能直接定位 bug。
第二，工程 trick 不是玄学而是对症下药：target network 冻结算子、replay buffer 平均分布、PER 的 IS 权重、Double Q 的选估分离，每一条都有数学出处。
第三，机器人工程师对 TD 的"保守"选择有数学理由：on-policy PPO + GAE 不是因为它最强，而是因为它不命中三元组；GPU 并行仿真让 on-policy 的样本劣势彻底消失，于是理论优势变成了工程主流。
向后衔接： - §6.4（LQR 与 HJB）：连续时间 TD、HJB-based RL、确定性策略梯度（DPG）；LQR 是线性 FA + on-policy TD 解析可解的特例 - §6.5（随机逼近收敛性）：Robbins-Monro 条件、Kushner-Clark 与 Borkar-Meyn ODE 方法、两时间尺度 SA、Zap SA——将为本专题所有收敛定理提供严格证明 - §6.6（Offline RL）：致命三元组在 offline setting 下彻底爆发——数据完全 off-policy 且无交互修正机会；催生了 CQL、IQL、BCQ、TD3+BC 等 pessimism-based 方法。LSPI 是它们的历史前身
TD 学习不是一条孤立的技术线，而是精确 DP、随机逼近、Kalman filter、系统辨识、深度学习、机器人控制的**交汇点**。理解它，就等于握住了现代 RL 数学的骨架。
从这里出发，6.4 将把 TD 推向连续时间——Hamilton-Jacobi-Bellman 方程是 Bellman 方程的连续化极限，连续时间 TD 学习（Doya 2000）是 TD(0) 在 \(\Delta t \to 0\) 时的推广。6.5 将为本章所有"以概率 1 收敛"的声明补上严格的 measure-theoretic 证明——Borkar 的 ODE 方法将每个 SA 算法归结为一个确定性 ODE 的稳定性分析。6.6 将面对致命三元组的终极挑战——当数据来自未知的旧策略且无法与环境交互时，如何安全地学习？
一句话给每个后续专题的预告：
- §6.4：当 \(\Delta t \to 0\) 时 TD 误差变成 HJB 残差——连续控制的 RL 数学基础
- §6.5：Borkar ODE 方法——为什么 SA 算法"跟踪"其平均动力系统的轨迹
- §6.6：离线数据 + 致命三元组 = 需要"悲观原则"——如果没见过就假设它很差
本章与前置章节的知识图谱关系：
- §6.1（精确 DP）提供了 Bellman 算子 \(T^\pi, T^*\) 和 \(\gamma\)-压缩的理论基础 → 本章的投影 Bellman 算子在此基础上加入了"投影"步骤
- §6.2（策略梯度）中的 critic 训练 → 就是本章 TD 学习的直接应用；GAE 就是 TD(λ) 的 advantage 版本
- 随机近似理论（Robbins-Monro 1951）→ 所有 TD 算法的收敛性证明骨架
- Kalman 滤波理论 → TD 误差作为 innovation 的深层类比，LSTD 作为 RLS 的推广
- 系统辨识中的持续激励条件 → RL 中的"充分探索"要求
- 自适应控制中的参数收敛理论 → TD 参数收敛的 ODE 分析方法
- 鲁棒控制中的不确定性建模 → Distributional RL 的风险敏感决策
本章的终极一句话总结：
TD 学习的数学本质是 Bellman 方程的在线随机近似求解——它的收敛性取决于算子的压缩性，而压缩性取决于采样分布与目标分布的匹配。所有 TD 算法的设计（从 GAE 到 DQN 到 GTD）都是在这个基本原理上的不同工程实例化。