随机逼近与 ODE 方法¶

定位：本专题回答 RL 理论中的"终极问题"——为什么 TD、Q-learning、Actor-Critic 会收敛？ 所有主流 RL 算法的收敛性证明最终都归约为一个数学框架：随机逼近（Stochastic Approximation, SA）的 ODE 分析。本专题是"强化学习数学"方向中数学密度最高的硬核章节，档位 4 内容占比超过 60%，面向博士入学或 qual 考试水平。

前置自测¶

📋 前置自测（答不出 >= 2 题 --> 先回对应章节复习）

什么是 Banach 不动点定理？它要求的完备度量空间和压缩映射分别是什么含义？（见 6.1）
策略梯度定理（Policy Gradient Theorem）的精确陈述是什么？为什么需要"兼容特征"假设？（见 6.2）
什么是 Baird 反例？它说明了线性 TD 在 off-policy 下的什么问题？（回顾 6.3：Baird 的 7-star MDP 表明，当采样分布 $d^\mu$ 偏离目标策略稳态分布 $d^\pi$ 时，TD 的期望更新矩阵 $A=\Phi^\top D_\mu(\gamma P^\pi - I)\Phi$ 可能有正实部特征值，导致参数单调发散——这是致命三元组的经典案例。）
Lyapunov 函数的定义是什么？一个正定函数沿系统轨迹的导数为负定意味着什么？（见 01_数学/40_控制理论/70_Lyapunov稳定性理论）
鞅差序列（martingale difference sequence）的定义是什么？什么条件下有限二阶矩的鞅差序列的部分和满足大数定律？

本章目标¶

学完本专题后，你将能：

从第一性原理推导 Robbins-Monro 定理的完整收敛证明，理解步长条件 $\sum\alpha=\infty,\sum\alpha^2<\infty$ 的必要性与几何直觉
陈述并解读 Borkar-Meyn ODE 定理的四条假设，理解它如何把 RL 收敛性归约为 ODE 稳定性问题
独立完成 TD(0) 收敛性的完整 ODE 证明（构造 $A$ 矩阵 --> 证正定 --> Lyapunov 方程 --> Borkar-Meyn）
诊断训练发散：面对 Isaac Lab / legged_gym 训练崩盘时，能从 $A$ 矩阵谱、步长条件、两时间尺度分离、噪声方差等维度做结构化排查
与控制博士对话：用 Lyapunov 函数、singular perturbation、Hurwitz 矩阵等共同语言讨论算法稳定性

知识树¶

随机逼近与ODE方法
├── §6.5.1 起源与动机（为什么需要 SA？）
│   ├── 均值估计的增量算法
│   ├── Robbins-Monro 1951 原始问题
│   ├── SA 在 RL 中的普遍性
│   └── SA 与 SGD 的关系与区别
├── §6.5.2 Robbins-Monro 定理完整证明 ⭐⭐
│   ├── 严格陈述（现代版本）
│   ├── 完整证明五步骤
│   ├── 步长条件的几何直觉与必要性证明
│   └── 步长选择的工程指南
├── §6.5.3 Borkar ODE 方法核心框架 ⭐⭐
│   ├── 核心思想：离散折线追踪连续 ODE
│   ├── Borkar-Meyn 定理完整陈述
│   ├── 证明三层结构
│   └── ODE 方法为什么是"终极武器"
├── §6.5.4 TD(0) 收敛性完整证明 ⭐⭐（最重要证明）
│   ├── 线性 TD(0) 的 SA 形式
│   ├── A 矩阵正定性证明
│   ├── ODE 稳定性 + Lyapunov 方程
│   ├── Borkar-Meyn 四条件验证
│   └── 与 Baird 反例的 ODE 联系
├── §6.5.5 Q-learning 收敛性证明 ⭐⭐
│   ├── 异步 SA 三重难点
│   ├── Tsitsiklis 1994 异步 SA 框架
│   ├── max 算子的非扩展性
│   └── ODE 视角重新诠释
├── §6.5.6 Polyak-Ruppert 平均 ⭐⭐⭐
│   ├── 平均化加速原理
│   ├── 最优渐近协方差矩阵
│   └── 与 SGD with averaging 的联系
├── §6.5.A 两时间尺度 SA 与 Actor-Critic ⭐⭐⭐
│   ├── Borkar 1997 定理
│   ├── Konda-Tsitsiklis 2003 定理
│   ├── 快慢分离的 singular perturbation 解释
│   └── GTD/TDC 作为两时间尺度 SA
├── §6.5.B 鞅收敛定理精细应用 ⭐⭐⭐⭐
│   ├── Doob supermartingale 收敛
│   ├── Azuma-Hoeffding 有限样本界
│   └── Poisson 方程与 Markov 噪声处理
├── §6.5.C 含噪声 ODE 稳定性与 SDE 视角 ⭐⭐⭐⭐
│   ├── 扩散极限定理
│   └── 随机 Lyapunov 方法
├── §6.5.D 异步 SA 框架 ⭐⭐⭐⭐
│   ├── Tsitsiklis 六条假设
│   └── 分布式 RL / 并行仿真中的异步性
├── §6.5.E Lyapunov 函数构造方法 ⭐⭐⭐
│   ├── 线性系统 Lyapunov 方程
│   ├── LaSalle 不变集原理
│   └── RL 专属 Lyapunov 选择
├── §6.5.F Zap SA 与渐近最优性 ⭐⭐⭐⭐
│   ├── Newton 方向替代梯度
│   ├── Zap-Q learning
│   └── 与 LSTD/RLS 的联系
├── §6.5.G SA 与 SGD 的统一视角 ⭐⭐⭐
│   ├── SA --> SGD --> Adam --> Natural Gradient
│   └── Cramér-Rao 下界与信息几何
├── §6.5.H 发散诊断工程指南 ⭐⭐
│   ├── ODE 稳定性视角的六维诊断
│   ├── A 矩阵特征值检查
│   └── 步长条件与噪声方差实操
└── §6.5.I Fazel 2018 PL 条件全局收敛 ⭐⭐⭐⭐
    ├── PL 不等式回顾
    ├── LQR 的 PL 证明
    └── SA + PL = 非凸 RL 全局收敛

引言：为什么随机逼近是 RL 收敛性的"终极武器"¶

在 6.1 我们学到，Bellman 算子 $T^\pi$ 与 $T^*$ 是 $\gamma$-压缩的，由 Banach 不动点定理立即得到同步值迭代 $V_{k+1} = T V_k$ 收敛。但真实的 RL 算法从不"同步"地计算算子 $T$：TD(0) 用一条采样轨迹的一步 bootstrap 更新，Q-learning 每步只更新一个坐标，Actor-Critic 同时在两套参数上做不同频率的更新。这些算法为什么收敛，就无法再靠 Banach 定理一招打完——它们是带噪声、异步、耦合的递推过程。

随机逼近理论，特别是 Borkar-Meyn 的 ODE 方法，正是把这类"脏"的递推过程统一成一个干净命题：若与算法对应的"平均 ODE" $\dot\theta = \bar h(\theta)$ 在 $\theta^*$ 处全局渐近稳定，且步长、噪声、有界性三个技术条件满足，则 $\theta_t \to \theta^*$ 几乎必然。这一条定理把 RL 收敛性的所有证明——TD(0)（Tsitsiklis-Van Roy 1997）、Q-learning（Tsitsiklis 1994）、Actor-Critic（Konda-Tsitsiklis 2003）、GTD/TDC（Sutton-Maei 2009）、Zap-Q（Devraj-Meyn 2017）——都化归为一个**ODE 稳定性问题**，从而与控制理论中的 Lyapunov 分析无缝对接。这就是本专题反复强调的"终极武器"：不是万能药，而是一把能把 RL 收敛性问题转译成经典动力系统问题的钥匙。

本质洞察：随机逼近的 ODE 方法之所以是"终极武器"，不是因为它能证明一切，而是因为它**把 RL 特有的困难（采样噪声、异步更新、非梯度方向）剥离出去**，只留下一个经典问题："确定性 ODE 稳不稳定？"而 ODE 稳定性有 130 年的积累。 这是一个"问题翻译器"，把不会做的新问题翻译成已经解决的老问题。

对机器人 RL 工程师而言，本专题的收益不是"会证收敛定理"，而是**获得"发散诊断能力"**——当你的 legged locomotion 训练 curve 崩掉时，你能从 ODE 稳定性、$A$ 矩阵正定性、两时间尺度分离、步长条件等第一性原理层面判断问题的根源，而不是盲目地调 lr、调 batch size、加 target network。

跨领域类比：SA 的 ODE 方法类似于电路分析中的"交流小信号模型"——你有一个复杂的非线性电路（对应带噪声的 RL 算法），想知道它在工作点附近是否稳定。你不直接分析完整电路，而是先对它做线性化得到一个小信号等效电路（对应平均 ODE），然后用经典线性系统理论判断稳定性。如果小信号模型稳定，原电路在工作点附近也稳定。ODE 方法做的事情完全一样——用"平均场"替代"完整随机过程"，用 ODE 稳定性替代 SA 收敛性。但区别在于：电路的小信号模型是局部的（只在工作点附近有效），而 Borkar-Meyn 的 ODE 方法可以给出**全局**收敛结论。

RL 收敛性证明的历史脉络：在 SA/ODE 方法被引入 RL 之前，RL 算法的收敛性证明是零散的、ad hoc 的。每个新算法都需要从头构造证明。Tsitsiklis 1994 和 Borkar-Meyn 2000 的贡献不仅在于证明了 Q-learning 和 TD 的收敛，更在于**建立了一个统一框架**——此后所有新 RL 算法的收敛性分析都沿袭这个模式。这种"元定理"（meta-theorem）的价值远超单个算法的证明——它教会了我们"怎么证"，而不只是"证了什么"。

反事实推理：如果没有 ODE 方法，RL 理论会是什么样子？每个新算法（TD、Q-learning、SARSA、Actor-Critic、GTD、TDC ...）都需要独立的收敛性证明，每个证明都需要从零构造 Lyapunov 函数。这在数学上是可行的，但效率极低——相当于每证一个微分方程的稳定性都要重新发明 Lyapunov 方法。ODE 方法的价值在于它把这个过程**自动化**了：你只需要写出平均 ODE，然后调用 130 年的 ODE 稳定性工具库。这就像有了 Scipy 之后你不需要手写 FFT 一样——工具的抽象让你专注于问题本身。

§6.5.1 随机逼近的起源与动机 ⭐⭐¶

从均值估计到增量算法¶

在正式进入 Robbins-Monro 之前，让我们从最简单的问题出发：估计一个随机变量的均值。

设随机变量 $X$ 的期望 $\mathbb{E}[X]$ 未知，我们依次观测到样本 $x_1, x_2, \ldots$。最直接的估计方法是蒙特卡洛：收集 $N$ 个样本后计算均值 $\bar{x}_N = \frac{1}{N}\sum_{i=1}^N x_i$。但这要求等到所有样本收集完毕才能给出估计。

**增量式算法**避开了这个限制。定义在线估计 $w_{k+1} = \frac{1}{k}\sum_{i=1}^{k} x_i$，通过简单的代数操作可得递推形式：

\[w_{k+1} = \frac{1}{k}\Bigl(\sum_{i=1}^{k-1} x_i + x_k\Bigr) = \frac{1}{k}\bigl((k-1)w_k + x_k\bigr) = w_k - \frac{1}{k}(w_k - x_k).\]

这就是增量均值估计的递推公式。每收到一个新样本 $x_k$，只需用当前估计 $w_k$ 和新样本做一次加权更新。其中步长 $\alpha_k = 1/k$ 自然地出现了。

这个递推为什么重要？ 三个原因：第一，它不需要存储所有历史数据——只保存当前估计 $w_k$ 和步数 $k$，内存从 $O(N)$ 降到 $O(1)$。第二，它是在线的——每收到一个样本就能更新。第三，它是 RL 中所有值函数更新的原型——TD(0)、Q-learning 的更新公式与这个增量均值估计**结构完全一致**，只是把"均值"换成了"Bellman 方程的根"。

反事实推理：如果不用增量式而用批量式，会怎样？在 RL 场景中，agent 与环境交互产生的数据流是无限的（或至少非常长），不可能先收集完所有数据再算均值。更关键的是，RL 中要估计的不是一个简单均值，而是满足 Bellman 方程的不动点——这个方程本身依赖于参数 $\theta$（因为 $T^\pi V_\theta$ 中 $V_\theta = \phi^\top\theta$ 出现在"目标"里）。所以我们必须**一边采样一边更新**，这正是随机逼近的核心需求。

Robbins-Monro 1951 的原始问题 ⭐⭐¶

1951 年 Herbert Robbins 与 Sutton Monro 在 Annals of Mathematical Statistics 22(3):400-407 发表的 "A Stochastic Approximation Method" 提出了如下问题：设 $M(x)$ 是某实验在水平 $x$ 处响应变量 $Y$ 的期望 $M(x)=\mathbb{E}[Y\mid x]$，$M$ 是未知但单调的函数；给定常数 $\alpha$，要求解方程

\[M(\theta)=\alpha.\]

难点是 $M$ 不可直接计算，每次"询问"一个 $x_n$ 只能得到带噪声的观测 $y_n = M(x_n)+\varepsilon_n$。Robbins-Monro 提出迭代

\[x_{n+1}=x_n+a_n\,(\alpha-y_n)\]

并证明在如下三组条件下 $x_n \to \theta$：

步长条件（后人称 Robbins-Monro 条件）：$a_n>0,\;\sum a_n=\infty,\;\sum a_n^2<\infty$；
函数条件：$M$ 单调、至少有一个满足方程的根、$|M(x)|$ 线性增长；
噪声条件：$\varepsilon_n$ 在 $x_n$ 给定条件下有限二阶矩、期望为 0。

这是有监督学习之前，人类第一次用递推方式在噪声下求解方程。原始证明收敛是 依概率 收敛；Blum 1954 加强到 a.s. 收敛。

历史背景：Robbins 当时在哥伦比亚大学统计系，主要关心的是生物统计中的"剂量-反应"问题——给一定剂量的药物，观察到的反应是随机的，要找到产生特定平均反应的剂量。这个看似简单的应用问题催生了一个横跨统计学、控制论、机器学习三大领域的数学理论。Robbins 的另一个重大贡献是 empirical Bayes 方法，体现了他对"用数据替代模型"思想的一贯追求。

SA 在 RL 中的普遍性 ⭐⭐¶

所有主流 RL 算法都是 SA 的特例。写出它们的通用形式：

\[\boxed{\;\theta_{t+1}=\theta_t+\alpha_t\,h(\theta_t,X_t)\;}\qquad (*)\]

其中 $\theta_t\in\mathbb{R}^d$ 是待学参数（值函数/Q 函数/策略参数），$X_t$ 是环境交互返回的随机样本（状态-动作-奖励），$h$ 是更新增量。

算法	$h(\theta, X)$	目标根
线性 TD(0)	$[r+\gamma\phi(s')^\top\theta-\phi(s)^\top\theta]\phi(s)$	$\Phi^\top D^\pi(T^\pi V_\theta-V_\theta)=0$
Q-learning（异步）	在坐标 $(s,a)$ 上：$r+\gamma\max_{a'}Q(s',a')-Q(s,a)$	$T^*Q-Q=0$
SARSA	类似 Q-learning 但用 $Q(s',a')$ 不取 max	$T^{\pi_Q}Q-Q=0$
Actor（两时间尺度）	$\nabla\log\pi_\theta(a\mid s)\,Q_w(s,a)$	$\nabla J(\theta)=0$
GTD2 / TDC	双变量：$(w,\theta)$ 联合 SA	投影 Bellman 方程根
Natural Actor	$F(\theta)^{-1}\nabla J(\theta)$	$\nabla J(\theta)=0$

这里的统一之美：无论 algorithmic tricks 多么五花八门，最终你都可以写成 $(*)$ 的形式，问它两个问题——(1) $h$ 的"平均场" $\bar h(\theta)=\mathbb{E}[h(\theta,X)]$ 长什么样？(2) ODE $\dot\theta=\bar h(\theta)$ 稳定吗？这两个答案就决定了算法会收敛到哪里。

本质洞察：$(*)$ 式的统一性揭示了一个深刻的事实—— RL 算法的多样性不在于数学结构，而在于 $h$ 函数的选择。 TD、Q-learning、Actor-Critic 看似截然不同，但在 SA 框架下只是 $h$ 的不同实例化。这意味着证明一个新 RL 算法收敛，你只需要做三件事： (1) 写出 $h$；(2) 算出 $\bar h$；(3) 分析 $\dot\theta = \bar h(\theta)$ 的稳定性。

SA 与 SGD 的关系 ⭐⭐¶

表面上，随机梯度下降（SGD）$\theta_{t+1}=\theta_t-\alpha_t\nabla\ell(\theta_t,X_t)$ 是 SA 的特例（取 $h=-\nabla\ell$，平均 ODE 即 gradient flow）。但 RL 中的 SA 普遍不是梯度：TD(0) 的更新方向 $\delta\phi$ 不是任何标量目标的梯度——它被称为 "semi-gradient"，原因是 Bellman 目标 $T^\pi V_\theta$ 自己依赖 $\theta$，求梯度时没有"穿透"这一层依赖。这是 Baird 反例（见 6.3）出现的根源，也是 **ODE 方法在 RL 中必须取代纯梯度分析**的原因。

跨领域类比：SGD 与 SA 的关系，类似于圆和椭圆的关系。圆是椭圆的特例（两个焦点重合），拥有更多对称性（旋转不变性）和更简单的分析工具。SGD 作为 SA 的特例，更新方向恰好是某个目标函数的梯度，因此可以用凸优化/非凸优化的全套工具（Lipschitz 梯度、PL 条件、Nesterov 加速等）。但 RL 中的 SA 不具有这种"梯度结构"——更新方向不对应任何标量目标的梯度，如同一个一般的椭圆不具有圆的旋转对称性。这就是为什么 RL 理论比监督学习困难一个量级——你不能直接套用 SGD 的收敛率，而必须使用 SA 的 ODE 方法或鞅方法。

为了让这个区别更加具体，考虑以下对比：

性质	SGD（监督学习）	SA（RL）
更新方向 $h$	$-\nabla\ell(\theta,X)$，是目标 $L(\theta)=\mathbb{E}[\ell]$ 的无偏梯度	$h(\theta,X)$ 可以不是任何目标的梯度
平均场 $\bar h$	$-\nabla L(\theta)$，gradient flow	一般的向量场 $\bar h(\theta)$
Lyapunov 函数	天然有：$V(\theta)=L(\theta)-L^*$	需要手工构造或从 ODE 结构推导
稳定性分析	凸性/PL/KL 条件直接给出	必须分析 ODE $\dot\theta=\bar h(\theta)$ 的谱
反例	一般不发散（只是收敛慢）	可以发散（Baird 反例）

常数步长 vs 递减步长的 trade-off ⭐⭐¶

这是理论与工程之间最大的裂隙之一，值得深入讨论。

递减步长 $\alpha_t=c/t$（满足 Robbins-Monro）：保证几乎必然收敛到 $\theta^*$，但后期进步极慢，且对非平稳环境（sim-to-real、课程学习）适应性极差。
常数步长 $\alpha_t=\alpha$：不满足 $\sum\alpha_t^2<\infty$，故**不**在点意义上收敛，但迭代"最终"以 $O(\alpha)$ 为半径在 $\theta^*$ 附近形成稳态分布（stationary distribution of the noisy iterate）。实务中 PPO/SAC 几乎从不用递减步长——因为机器人训练本就非平稳（reward shaping、domain randomization），工程师宁愿用常数步长 + early stopping + learning rate schedule（linear / cosine）来做显式控制。

反事实推理：如果在 Isaac Lab 的 4096 并行环境 PPO 训练中使用严格的 Robbins-Monro 步长 $\alpha_t = 3\times10^{-4}/t$，会发生什么？第一个 epoch（约 $t=1$）步长正常；但到 $t=1000$（约几分钟后），步长已降到 $3\times10^{-7}$，参数几乎冻结。而此时 domain randomization 还在不断改变环境参数，policy 需要持续适应——但步长已经小到无法跟踪变化。最终结果：训练前期正常，中后期 reward 停滞甚至缓慢下降。这就是为什么工程师用常数步长或分段线性 schedule——非平稳环境要求步长不能太快衰减。

步长条件的几何直觉将在 §6.5.2 中详细展开。

⚠️ 常见陷阱（§6.5.1）¶

💡 概念误区：认为"SA 就是 SGD 的另一个名字"

新手想法："随机逼近不就是随机梯度下降吗？换个名字而已。"

实际上：SGD 是 SA 的一个**严格特例**——SGD 的更新方向必须是某个标量目标的无偏梯度估计，而 SA 的更新方向可以是任意向量场。RL 中的 TD 更新是 semi-gradient（不对应任何目标的梯度），Actor-Critic 是两个耦合的 SA（不是一个优化问题的梯度），Q-learning 含 max 非线性（不可微）。把 SA 当成 SGD 会导致你错误地期望所有 RL 算法都有收敛保证——实际上只有满足 ODE 稳定性条件的才收敛。

🧠 思维陷阱：把 Robbins-Monro 步长条件当成"理论要求，工程可以忽略"

新手想法："$\sum\alpha=\infty$ 和 $\sum\alpha^2<\infty$ 是数学家的玩具，工程上用常数 lr 就行。"

实际上：步长条件反映了真实的物理约束。$\sum\alpha=\infty$ 说的是"探索能量必须足够"——步长太快衰减，算法连目标都走不到。$\sum\alpha^2<\infty$ 说的是"噪声必须被衰减"——步长不够衰减，算法永远在目标附近震荡。工程上用常数步长确实违反第二条，代价是**永远不精确收敛**（只收敛到一个稳态分布）。如果你的任务需要高精度（如精密控制参数辨识），常数步长是不够的；如果只需"足够好"（如 PPO 训练），常数步长的 $O(\alpha)$ bias 通常可接受。关键是理解你在做什么 trade-off。

§6.5.2 Robbins-Monro 定理：完整证明 ⭐⭐¶

严格陈述（现代版本）¶

设 $h:\mathbb{R}^d\to\mathbb{R}^d$ 是 Lipschitz 连续函数，$\theta^*$ 满足 $h(\theta^*)=0$。考虑

\[\theta_{t+1}=\theta_t+\alpha_t\bigl[h(\theta_t)+M_{t+1}\bigr],\]

其中 $\{M_{t+1}\}$ 是关于滤过 $\mathcal{F}_t=\sigma(\theta_0,M_1,\dots,M_t)$ 的鞅差序列，$\mathbb{E}[M_{t+1}\mid\mathcal{F}_t]=0$，$\mathbb{E}[\|M_{t+1}\|^2\mid\mathcal{F}_t]\le K(1+\|\theta_t\|^2)$。若：

(S1) 步长：$\alpha_t>0,\sum\alpha_t=\infty,\sum\alpha_t^2<\infty$；
(S2) 强单调性 / Lyapunov 条件：存在 $C^1$ 函数 $V\ge 0$，$V(\theta^*)=0$，$\nabla V(\theta)^\top h(\theta)\le -c V(\theta)$，$c>0$；
(S3) 有界性：$\sup_t\|\theta_t\|<\infty$ a.s.（通过 projection 或 a priori 论证）。

则 $\theta_t\to\theta^*$ a.s.

在正式证明前，让我们先理解每个条件在"说什么"：

(S1) 是步长条件，前面已经讨论过。这里补充一个精确的理解：把 SA 迭代看成一个"数字滤波器"，$\alpha_t$ 是滤波器的带宽。$\sum\alpha_t=\infty$ 保证滤波器在长时间内传递了无限多的"信号能量"（确保目标可达）；$\sum\alpha_t^2<\infty$ 保证滤波器传递的"噪声能量"有限（确保最终精度）。

(S2) 是确定性漂移条件。如果没有噪声（$M=0$），迭代变成 $\theta_{t+1}=\theta_t+\alpha_t h(\theta_t)$，这是 ODE $\dot\theta=h(\theta)$ 的 Euler 离散化。(S2) 说的是 $h$ 作为向量场指向 $\theta^*$（在 $V$ 的度量下），保证无噪声版本收敛。回顾 01_数学/40_控制理论/70_Lyapunov稳定性理论：Lyapunov 直接法的核心就是"沿系统轨迹，$V$ 严格递减"——(S2) 正是这个条件的量化版本。

(S3) 是技术条件，保证迭代不会"先跑到无穷远再回来"。在实际 RL 中，通常通过梯度裁剪（gradient clipping）、状态归一化或投影来保证。Borkar-Meyn 2000 的重大贡献之一是**去掉了 (S3)**——用缩放 ODE 的稳定性替代。

完整证明五步骤¶

核心思想：用 $V(\theta_t)$ 构造一个"近似 supermartingale"，让 Doob 的鞅收敛定理发挥作用。

Step 1：Taylor 展开

对 $V$ 在 $\theta_t$ 处做二阶 Taylor 展开。由 $\theta_{t+1} = \theta_t + \alpha_t[h(\theta_t) + M_{t+1}]$：

\[V(\theta_{t+1}) = V(\theta_t) + \nabla V(\theta_t)^\top \cdot \alpha_t[h(\theta_t) + M_{t+1}] + \frac{1}{2}\alpha_t^2 [h(\theta_t) + M_{t+1}]^\top \nabla^2 V(\xi_t) [h(\theta_t) + M_{t+1}],\]

其中 $\xi_t$ 是 $\theta_t$ 与 $\theta_{t+1}$ 之间的某点（Taylor 余项的 Lagrange 形式）。

为什么用 Taylor 展开？ 因为我们需要把 $V(\theta_{t+1})$ 表示成 $V(\theta_t)$ 加上一些可控的修正项。一阶项会给出"确定性漂移"（来自 $h$）和"鞅差"（来自 $M$），二阶项给出"噪声方差"（来自 $\alpha_t^2$）。这三部分各有不同的衰减速率，正是收敛证明的核心。

Step 2：取条件期望

对上式取 $\mathbb{E}[\cdot\mid\mathcal{F}_t]$。利用三个关键事实：

鞅差性质：$\mathbb{E}[M_{t+1}\mid\mathcal{F}_t]=0$，因此 $\nabla V(\theta_t)^\top M_{t+1}$ 的条件期望为 0；
Lyapunov 条件 (S2)：$\nabla V(\theta_t)^\top h(\theta_t) \le -cV(\theta_t)$；
噪声方差控制：$\mathbb{E}[\|M_{t+1}\|^2\mid\mathcal{F}_t] \le K(1+\|\theta_t\|^2)$。

得到：

\[\mathbb{E}[V(\theta_{t+1})\mid\mathcal{F}_t] \le V(\theta_t) - c\alpha_t V(\theta_t) + C'\alpha_t^2(1 + \|\theta_t\|^2),\]

其中 $C'$ 是一个与 $\nabla^2 V$ 的界、$K$、$h$ 的 Lipschitz 常数有关的常数。

关键观察：第一项 $V(\theta_t)$ 是当前值，第二项 $-c\alpha_t V(\theta_t)$ 是"确定性下降"（来自 $h$ 指向 $\theta^*$），第三项 $C'\alpha_t^2(\cdots)$ 是"噪声抬升"（来自鞅差的方差）。收敛的关键是**下降项（$O(\alpha_t)$）比抬升项（$O(\alpha_t^2)$）快**。

由有界性 (S3)，存在常数 $B$ 使得 $\|\theta_t\|^2 \le B$ a.s.，因此：

\[\mathbb{E}[V(\theta_{t+1})\mid\mathcal{F}_t] \le V(\theta_t)(1 - c\alpha_t) + C\alpha_t^2,\]

其中 $C = C'(1+B)$。

Step 3：构造 supermartingale

定义序列

\[U_t = V(\theta_t) + C\sum_{s=t}^{\infty} \alpha_s^2.\]

由 $\sum\alpha_s^2 < \infty$（条件 (S1)），尾和 $\sum_{s=t}^\infty \alpha_s^2$ 是有限且递减的。计算：

\[\mathbb{E}[U_{t+1}\mid\mathcal{F}_t] = \mathbb{E}[V(\theta_{t+1})\mid\mathcal{F}_t] + C\sum_{s=t+1}^\infty \alpha_s^2$$ $$\le V(\theta_t)(1-c\alpha_t) + C\alpha_t^2 + C\sum_{s=t+1}^\infty \alpha_s^2$$ $$= V(\theta_t)(1-c\alpha_t) + C\sum_{s=t}^\infty \alpha_s^2$$ $$\le V(\theta_t) + C\sum_{s=t}^\infty \alpha_s^2 = U_t.\]

（最后一步用了 $c\alpha_t V(\theta_t) \ge 0$。）因此 $\{U_t\}$ 是非负 supermartingale！

为什么构造 $U_t$？ 原始的 $V(\theta_t)$ 不是 supermartingale——它在每一步可能因噪声而增加。但增加量是 $O(\alpha_t^2)$，累积起来 $\sum\alpha_t^2 < \infty$。通过加上这个"补偿尾和"，我们把偶然的增长"预支"了，使得 $U_t$ 成为严格的 supermartingale。这个技巧在随机分析中极为常见，被称为"Robbins-Siegmund 引理"的思想。

Step 4：Doob 收敛

Doob 的 supermartingale 收敛定理（回顾：这是概率论中鞅理论的核心结果之一）：非负 supermartingale 几乎必然收敛。

因此 $U_t \to U_\infty$ a.s.，其中 $0 \le U_\infty < \infty$。由于 $\sum_{s=t}^\infty \alpha_s^2 \to 0$（$t\to\infty$），我们得到 $V(\theta_t) \to U_\infty$ a.s.

Step 5：证明极限为零

还需要证明 $U_\infty = 0$（即 $V(\theta_\infty) = 0$）。

从 Step 2 的不等式迭代展开：

\[\mathbb{E}[V(\theta_{t+1})] \le \mathbb{E}[V(\theta_t)](1-c\alpha_t) + C\alpha_t^2.\]

对这个递推做归纳，设 $v_t = \mathbb{E}[V(\theta_t)]$：

\[v_{t+1} \le v_t(1-c\alpha_t) + C\alpha_t^2.\]

注意 $\prod_{s=0}^{t}(1-c\alpha_s) \le \exp(-c\sum_{s=0}^t \alpha_s) \to 0$（因 $\sum\alpha_s = \infty$）。这意味着"确定性漂移"的衰减因子趋于零。同时，"噪声累积"$\sum C\alpha_s^2 < \infty$。标准的 Gronwall 引理给出：

\[v_t \le v_0 \prod_{s<t}(1-c\alpha_s) + C\sum_{s<t} \alpha_s^2 \prod_{s<k\le t}(1-c\alpha_k) \to 0.\]

因此 $\mathbb{E}[V(\theta_t)] \to 0$。结合 $V(\theta_t)$ a.s. 收敛到 $U_\infty$（Step 4），由 Fatou 引理 $\mathbb{E}[U_\infty] \le \liminf \mathbb{E}[V(\theta_t)] = 0$。又 $U_\infty \ge 0$，故 $U_\infty = 0$ a.s.

因此 $V(\theta_t) \to 0$ a.s.，由 $V$ 的正定性 $\theta_t \to \theta^*$ a.s. $\blacksquare$

步长条件的几何直觉与必要性 ⭐⭐¶

$\sum\alpha_t = \infty$ 的必要性：

想象你在一条无限长的走廊里，目标在走廊尽头。每一步你的步长是 $\alpha_t$。如果 $\sum\alpha_t < \infty$，你的总行程 $\sum\alpha_t$ 有限——你永远走不到走廊尽头（如果 $\theta^*$ 恰好在这个有限距离之外）。更精确地说：如果 $\sum\alpha_t < \infty$，则 $\|\theta_t - \theta_0\| \le \sum_{s=0}^\infty \alpha_s \|h(\theta_s) + M_{s+1}\|$，当 $h$ 和 $M$ 有界时这个和有限，迭代只能在 $\theta_0$ 的有限邻域内活动。

反例：取 $\alpha_t = 1/t^2$（满足 $\sum\alpha^2<\infty$ 但 $\sum\alpha = \pi^2/6 < \infty$）。考虑简单的标量 SA $\theta_{t+1} = \theta_t + \alpha_t(\theta^* - \theta_t)$（无噪声）。若 $\theta_0 = 0, \theta^* = 100$，则 $\theta_t = 100(1-\prod_{s=1}^t(1-\alpha_s))$。由 $\sum\alpha_s<\infty$，$\prod(1-\alpha_s) > 0$，故 $\theta_t \to 100(1-c)$ 对某 $c>0$——永远到不了 100。

$\sum\alpha_t^2 < \infty$ 的必要性：

每一步噪声对 $V(\theta_t)$ 的贡献量级为 $\alpha_t^2 \mathbb{E}[\|M\|^2]$。如果 $\sum\alpha_t^2 = \infty$，噪声的累积贡献无限大——确定性漂移无法压住噪声，迭代永远在震荡。

反例：取 $\alpha_t = 1/\sqrt{t}$（满足 $\sum\alpha=\infty$ 但 $\sum\alpha^2 = \sum 1/t = \infty$）。对带噪声的 SA，可以证明 $\mathrm{Var}(\theta_t) \not\to 0$——迭代在 $\theta^*$ 附近永远震荡，振幅不衰减。

临界典范：$\alpha_t = c/t$ 恰好在边界上——$\sum 1/t = \infty$（调和级数发散）但 $\sum 1/t^2 = \pi^2/6 < \infty$（Basel 问题）。这就是为什么 $1/t$ 衰减是"最慢的足够快"的步长。

步长选择	$\sum\alpha$	$\sum\alpha^2$	RM 条件	备注
$c/t$	$\infty$	$<\infty$	满足	经典选择，临界边界
$c/t^{0.7}$	$\infty$	$<\infty$	满足	工程常用，前期更快
$c/t^{0.5}$	$\infty$	$=\infty$	不满足	噪声不衰减
$c/t^2$	$<\infty$	$<\infty$	不满足	步长衰减太快
$c/(t\log t)$	$\infty$	$<\infty$	满足	比 $1/t$ 更慢衰减
常数 $c$	$=\infty$	$=\infty$	不满足	不收敛到点，但有稳态分布

对 RL 人的思维模板¶

不要死记证明，记住这个**思维模版**：遇到"证明 SA 收敛"的任何变体，套路都是"找 Lyapunov 函数 $V$ --> 证明 $V$ 沿着迭代几乎是 supermartingale --> Doob 收敛 --> 说明唯一可能的极限是 $V=0$"。本专题后面所有证明（TD、Q-learning、Actor-Critic）都是这个套路的不同变奏。

⚠️ 常见陷阱（§6.5.2）¶

⚠️ 编程陷阱：步长实现中的 off-by-one 错误

错误做法：在代码中用 alpha = c / t 但 t 从 0 开始，导致第一步 alpha = c/0 = inf。

现象：第一步更新量为 inf，参数直接变成 NaN，后续所有计算失败。

正确做法：alpha = c / max(t, 1) 或 alpha = c / (t + 1)。在工业代码（CleanRL、stable-baselines3）中，步长 schedule 通常用 linear_schedule 函数显式管理，避免手写除法。

💡 概念误区：认为 $\sum\alpha^2 < \infty$ 是"噪声必须有界"

新手想法："第二个条件说的是噪声不能太大吧？"

实际上：$\sum\alpha^2 < \infty$ 是对**步长**的约束，不是对噪声的约束。噪声 $M_t$ 的方差可以随 $\|\theta_t\|$ 线性增长（$\le K(1+\|\theta_t\|^2)$），只要步长衰减足够快，噪声的累积贡献就是有限的。根本原因：每步噪声对 $V$ 的贡献 = $\alpha_t^2 \times \text{噪声方差}$，步长平方可求和保证了这个贡献可求和。

练习（§6.5.2）¶

手推：证明 $\alpha_t = 1/t^{0.9}$ 满足 Robbins-Monro 条件。（提示：$\sum 1/t^{0.9}$ 与 $\sum 1/t^{1.8}$ 分别是否收敛？用积分判别法。）
反事实：构造一个一维 SA $\theta_{t+1} = \theta_t + \alpha_t(-\theta_t + \varepsilon_t)$，其中 $\varepsilon_t \sim \mathcal{N}(0,1)$。分别取 $\alpha_t = 1/t$ 和 $\alpha_t = 0.01$，用 Python 模拟 10000 步并画轨迹图。观察前者收敛到 0、后者在 0 附近震荡的区别。
进阶：在 Step 5 的证明中，说明为什么不能省略 Fatou 引理而直接从 $\mathbb{E}[V(\theta_t)] \to 0$ 推出 $V(\theta_t) \to 0$ a.s.。（提示：$L^1$ 收敛不蕴含 a.s. 收敛。）

§6.5.3 Borkar 的 ODE 方法：核心框架 ⭐⭐¶

核心思想¶

Robbins-Monro 1951 要求手动找 Lyapunov 函数 $V$，这在 RL 中难度极高（$A$ 不对称时没有自然 $V$）。Borkar 的 ODE 方法**换一个视角：**把离散 SA 迭代看成一条在连续时间 ODE 的轨迹上"跳跃前进"的折线。如果 ODE 本身在 $\theta^*$ 处稳定（用经典控制论工具如 Lyapunov 直接法判定），那么折线也会收敛到 $\theta^*$。

跨领域类比：这个思想类似于数值分析中用 Euler 方法求解 ODE。Euler 方法把连续 ODE $\dot\theta = f(\theta)$ 离散化为 $\theta_{n+1} = \theta_n + h_n f(\theta_n)$，步长 $h_n$ 足够小时离散解追踪连续解。SA 的 ODE 方法做的是**反过来**的事情：给定一个离散递推（SA），问它是否在追踪某个连续 ODE。如果是，且这个 ODE 稳定，则 SA 也收敛。区别在于 Euler 方法没有噪声，SA 有噪声——但 ODE 方法的核心贡献正是**证明噪声的扰动在长时间尺度上可以被忽略**。

关键转换：定义时间刻度 $t(n)=\sum_{k=0}^{n-1}\alpha_k$（累积步长），构造插值轨迹

\[\bar\theta(t)\;:=\;\theta_n+\frac{t-t(n)}{\alpha_n}(\theta_{n+1}-\theta_n),\quad t\in[t(n),t(n+1)].\]

当步长足够小、噪声被累平均掉后，$\bar\theta(t)$ 的长时间行为由 ODE

\[\dot\theta(t)=\bar h(\theta(t)),\qquad \bar h(\theta):=\lim_{T\to\infty}\tfrac{1}{T}\int_0^T\mathbb{E}[h(\theta,X_t)\mid\theta_0=\theta]\,dt\]

给出。对 i.i.d. $X_t$，$\bar h(\theta)=\mathbb{E}[h(\theta,X)]$；对 Markov 链，取对平稳分布的期望。

为什么取平稳分布的期望？ 因为 SA 的每一步都在用"当前"的随机样本 $X_t$ 来近似"平均行为"$\bar h$。如果 $X_t$ 是 i.i.d. 的，单次样本就是均值的无偏估计。但如果 $X_t$ 是 Markov 链（RL 中 agent 的状态转移就是 Markov 的），单次样本有偏，但 Markov 链的遍历定理保证时间平均收敛到空间平均（平稳分布下的期望）。这就是为什么平稳分布在这里出现。

Borkar-Meyn 定理（2000, SIAM J. Control Optim. 38(2):447-469） ⭐⭐¶

定理（Borkar-Meyn 2000）：考虑 SA 递推 $\theta_{t+1}=\theta_t+\alpha_t[h(\theta_t)+M_{t+1}]$。假设：

(A1) $h:\mathbb{R}^d\to\mathbb{R}^d$ 全局 Lipschitz；
(A2) 步长满足 Robbins-Monro 条件 $\sum\alpha_t=\infty,\sum\alpha_t^2<\infty$；
(A3) 鞅差噪声 $\mathbb{E}[M_{t+1}\mid\mathcal{F}_t]=0$，$\mathbb{E}[\|M_{t+1}\|^2\mid\mathcal{F}_t]\le K(1+\|\theta_t\|^2)$；
(A4)（Borkar-Meyn 标度条件）缩放函数 $h_c(\theta):=h(c\theta)/c$ 在 $c\to\infty$ 时一致收敛到连续的 $h_\infty$，且缩放 ODE $\dot\theta=h_\infty(\theta)$ 以原点为**全局渐近稳定平衡点**。

则：

迭代 $\{\theta_t\}$ 几乎必然有界（这是 Borkar-Meyn 在 Borkar 1988/Kushner-Clark 基础上的重要贡献——无需 a priori 的有界性假设）；
若 ODE $\dot\theta=\bar h(\theta)$ 有内部闭不变集 $J$，则 $\theta_t\to J$ a.s.；
特别地，若 ODE 以 $\theta^*$ 为唯一全局渐近稳定平衡点，则 $\theta_t\to\theta^*$ a.s.

条件 (A4) 的深层含义：为什么需要"缩放 ODE"？这是 Borkar-Meyn 相对于前人（Ljung 1977、Kushner-Clark 1978）的核心创新。考虑一个问题：如果 SA 迭代跑到了很远的地方（$\|\theta_t\|$ 很大），它还会被拉回来吗？ Ljung 和 Kushner 需要先假设迭代有界（条件 (S3)），但这在 RL 中很难验证。Borkar-Meyn 的思路是：在 $\|\theta\|$ 很大时，$h(\theta)$ 的行为由缩放极限 $h_\infty$ 决定。如果 $h_\infty$ 的 ODE 稳定（把东西拉回原点），则迭代不可能跑到无穷远——因为"在远处"的动力学总是把它拉回来。这就用 (A4) 自动推出了有界性，不再需要额外假设。

反事实推理：如果没有 (A4)，会怎样？考虑 $h(\theta) = \theta$（正反馈）。ODE $\dot\theta = \theta$ 的解 $\theta(t) = \theta_0 e^t$ 指数增长到无穷。对应的 SA 即使有 Robbins-Monro 步长，也会发散——因为确定性漂移把迭代推向无穷，步长衰减不够快来对抗指数增长。(A4) 排除了这种情况。

证明三层结构¶

整个证明分三层，每层解决一个子问题：

第一层（追踪引理 / tracking lemma）

在任意时间窗 $[t(n), t(n)+T]$ 内，插值曲线 $\bar\theta$ 与从 $\theta_n$ 出发的 ODE 解 $\theta(\cdot)$ 的偏差一致趋于 0（概率 1）。

证明关键是把噪声 $\sum_{k=n}^{n+m}\alpha_k M_{k+1}$ 视为鞅，由 Doob 极大不等式得鞅差对轨迹的扰动 $\to 0$。更精确地，对任意 $T>0$ 和 $\epsilon>0$：

\[\mathbb{P}\Bigl(\sup_{t\in[t(n),t(n)+T]}\|\bar\theta(t)-\theta^{ODE}(t)\|>\epsilon\Bigr)\to 0 \quad\text{as}\;n\to\infty.\]

直觉：在窗口 $[t(n),t(n)+T]$ 内，步长 $\alpha_k$ 已经很小（$k$ 很大），每步的噪声贡献 $\alpha_k M_{k+1}$ 也很小；虽然步数很多（大约 $T/\alpha_n$），但鞅差的累积标准差只有 $O(\sqrt{\sum \alpha_k^2})$，由 $\sum\alpha^2<\infty$ 保证最终趋于 0。

第二层（有界性 / stability）

更详细地：假设 $\|\theta_{n_k}\| \to \infty$ 沿某子序列。定义 $\hat\theta_k = \theta_{n_k}/\|\theta_{n_k}\|$（归一化到单位球面上）。由 (A4)，在 $\|\theta\|$ 大时 $h(\theta) \approx \|\theta\| h_\infty(\theta/\|\theta\|)$，所以 $\hat\theta_k$ 近似追踪 $\dot{\hat\theta} = h_\infty(\hat\theta)$。但 $h_\infty$ 以原点为全局渐近稳定点，故 $\hat\theta_k \to 0$——与 $\|\hat\theta_k\|=1$ 矛盾。

第三层（收敛）

既然轨迹有界、且在任意有限窗追踪 ODE，且 ODE 本身渐近稳定，经典动力系统中的 Hirsch lemma / Benaim 方法给出 $\theta_t\to\theta^*$。

关键工具是 Benaim 1996 的"渐近伪轨迹（asymptotic pseudo-trajectory）"理论：如果一条曲线在每个有限时间窗内都近似追踪某个 ODE 的真实轨迹，那么这条曲线的 $\omega$-极限集必须是 ODE 的某个内部闭不变集。如果 ODE 只有一个不变集（唯一全局渐近稳定平衡点 $\theta^*$），则曲线必须收敛到 $\theta^*$。

ODE 方法的具体计算流程（给工程师的操作手册） ⭐⭐¶

对任何 RL 算法，应用 ODE 方法的具体步骤如下。这不是抽象理论，而是一个**可操作的流程**：

Step 1：写出 SA 形式

把你的 RL 算法写成 $\theta_{t+1} = \theta_t + \alpha_t h(\theta_t, X_t)$。这一步要求你明确： - $\theta_t$ 是什么？（值函数参数/Q 参数/策略参数） - $X_t$ 是什么？（采样的 $(s,r,s')$ 或 $(s,a,r,s')$） - $h(\theta, X)$ 的精确表达式是什么？

Step 2：计算平均场 $\bar h(\theta) = \mathbb{E}[h(\theta, X)]$

对 i.i.d. 采样直接取期望；对 Markov 采样取平稳分布下的期望。关键技巧：如果 $h$ 关于 $\theta$ 是线性的（如线性 TD），$\bar h$ 可以精确计算为 $\bar h(\theta) = b - A\theta$。

Step 3：写出平均 ODE

\[\dot\theta = \bar h(\theta).\]

Step 4：分析 ODE 稳定性

线性 ODE（$\bar h$ 线性）：检查系统矩阵是否 Hurwitz（特征值实部全负）
非线性 ODE：构造 Lyapunov 函数或用 LaSalle 不变集原理
对 Q-learning：用 $\infty$-范数 Lyapunov $V = \|Q-Q^*\|_\infty$

Step 5：验证 Borkar-Meyn 四条件

逐条检查 (A1)-(A4)。最常出问题的是 (A3)（Markov 噪声不是严格鞅差）和 (A4)（缩放 ODE 稳定性）。

Step 6：下结论

如果 ODE 有唯一全局渐近稳定平衡点，且四条件满足，则 SA 收敛。

步骤	TD(0) 的实例	Q-learning 的实例
$\theta$	值函数参数 $\theta\in\mathbb{R}^d$	Q-table $Q\in\mathbb{R}^{\\|S\\|\times\\|A\\|}$
$X_t$	$(S_t, R_t, S_{t+1})$	$(S_t, A_t, R_t, S_{t+1})$
$h(\theta, X)$	$\delta_t\phi(S_t)$	$e_{s,a}(R+\gamma\max Q - Q(s,a))$
$\bar h(\theta)$	$b - A\theta$	$T^*Q - Q$
ODE	$\dot\theta = -A\theta + b$	$\dot Q = T^*Q - Q$
稳定性工具	$A$ 正定 --> Hurwitz	$\gamma$-压缩 --> $\infty$-Lyapunov
结论	$\theta \to A^{-1}b$ a.s.	$Q \to Q^*$ a.s.

ODE 方法为什么是 RL 的终极武器¶

把"随机、异步、带噪声、非梯度"的算法，化归到"确定性 ODE 的稳定性"。而 ODE 稳定性分析有 130 多年的积累（Lyapunov 1892 直接法、LaSalle 不变集定理 1960、Poincare-Bendixson 定理、线性化 + Hartman-Grobman 定理等）。

回顾 01_数学/40_控制理论/70_Lyapunov稳定性理论：Lyapunov 直接法的核心思想是"找一个正定函数 $V$，如果 $V$ 沿系统轨迹严格递减，则系统稳定"。ODE 方法告诉你：如果你能对 RL 的平均 ODE 做 Lyapunov 分析，就等于证明了 RL 算法的收敛性。这意味着 RL 收敛性分析可以直接调用整个控制理论工具箱。

本质洞察：ODE 方法的力量不在于它给了一个新的证明技术，而在于它建立了一座桥梁——把 RL（年轻领域，工具不足）连接到 ODE 稳定性理论（成熟领域，工具丰富）。 使用 ODE 方法不需要你发明新数学，只需要你会"翻译"。

⚠️ 常见陷阱（§6.5.3）¶

💡 概念误区：认为"ODE 方法就是取均值忽略噪声"

新手想法："平均 ODE 就是把噪声去掉嘛，那直接忽略噪声不就行了？"

实际上：ODE 方法**不是**忽略噪声。它严格处理噪声——证明噪声在累积步长尺度下对轨迹扰动趋于零。"忽略"与"证明可忽略"是天壤之别。如果你只是"忽略"噪声，你无法回答"噪声什么时候不能忽略？"（答案：常数步长下不能忽略，因为噪声累积不趋于零）。ODE 方法的精确性允许你区分这两种情况。

🧠 思维陷阱：认为"只要 ODE 稳定，SA 就一定收敛"

新手想法："Borkar-Meyn 说 ODE 稳定就行，所以我只需要检查 ODE。"

实际上：(A1)-(A4) 四个条件**缺一不可**。ODE 稳定只是 (A4) 的一部分；如果步长不满足 Robbins-Monro (A2)、或噪声不是鞅差 (A3)、或 $h$ 不 Lipschitz (A1)，收敛性保证消失。最常见的失效场景：off-policy TD 的噪声不满足严格鞅差条件（因为采样策略与目标策略不同），需要额外的 Poisson 方程修正或重要性采样校正。

练习（§6.5.3）¶

概念：解释为什么 (A4) 中需要"缩放极限 $h_c \to h_\infty$"而不是直接要求"$h$ 在无穷远处指向原点"。（提示：考虑 $h(\theta) = -\theta + \sin\theta$。）
手推：对线性 SA $h(\theta) = -A\theta + b$，验证 Borkar-Meyn 的 (A4)：求 $h_c(\theta) = h(c\theta)/c$，取 $c\to\infty$ 极限，并说明缩放 ODE 的稳定性等价于 $A$ 的什么性质。
跨章综合：结合 6.1 的 Banach 不动点定理和本节的 ODE 方法，解释同步值迭代 $V_{k+1}=TV_k$ 和异步 TD(0) 收敛性证明的本质区别。为什么前者不需要 ODE 方法？

§6.5.4 TD(0) 收敛性的 ODE 完整证明 ⭐⭐（本专题最重要证明之一）¶

本节补上 6.3 只陈述不证明的 Tsitsiklis-Van Roy 1997 定理（IEEE TAC 42(5):674-690）。这是将 ODE 方法应用于 RL 的最经典范例，每一步都值得仔细理解。

Step 1：写出线性 TD(0) 的 SA 形式 ⭐⭐¶

用特征 $\phi:\mathcal{S}\to\mathbb{R}^d$，近似 $V_\theta(s)=\phi(s)^\top\theta$。On-policy 采样得到 $(S_t,R_t,S_{t+1})$，TD 误差 $\delta_t=R_t+\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).\]

把 $h(\theta, X_t) = \delta_t \phi(S_t)$ 展开：

\[h(\theta, (S_t, R_t, S_{t+1})) = [R_t + \gamma\phi(S_{t+1})^\top\theta - \phi(S_t)^\top\theta]\,\phi(S_t).\]

这就是 SA 公式 $(*)$ 中的 $h$。注意 $h$ 关于 $\theta$ 是线性的——这是"线性 TD(0)"的精确含义（特征 $\phi$ 固定，$\theta$ 进入的方式是线性的）。

为什么 TD 更新不是梯度？ 如果 TD 是某个目标 $J(\theta)$ 的梯度下降，那应该有 $h(\theta,X) = -\nabla_\theta J(\theta)$。但 TD 误差中的"目标"$R_t + \gamma\phi(S_{t+1})^\top\theta$ 本身依赖于 $\theta$，而 TD 更新**没有对这一项求导**（所以叫 semi-gradient）。用 PyTorch 的语言：TD 目标做了 detach()，梯度没有"穿透"到目标中。如果穿透了，你得到的是所谓的"residual gradient"方法（Baird 1995），那确实是真梯度，但收敛到的不是 Bellman 不动点而是 Bellman 残差的最小化——通常不是我们想要的。

Step 2：求平均 ODE 的右端 $\bar h$ ⭐⭐¶

设 Markov 链有平稳分布 $d^\pi$，转移矩阵 $P^\pi$。

\[\bar h(\theta)=\mathbb{E}_{s\sim d^\pi,s'\sim P^\pi(\cdot\mid s)}\bigl[(R+\gamma\phi(s')^\top\theta-\phi(s)^\top\theta)\phi(s)\bigr].\]

展开这个期望。记 $\Phi$ 为 $|\mathcal{S}|\times d$ 特征矩阵（第 $s$ 行是 $\phi(s)^\top$），$D^\pi = \mathrm{diag}(d^\pi)$，$R^\pi$ 为奖励向量（$R^\pi(s) = \mathbb{E}[R\mid s, \pi]$）：

\[\bar h(\theta) = \Phi^\top D^\pi R^\pi + \Phi^\top D^\pi(\gamma P^\pi - I)\Phi\theta = b - A\theta,\]

其中 $b = \Phi^\top D^\pi R^\pi$，$A = \Phi^\top D^\pi(I - \gamma P^\pi)\Phi$。

平均 ODE：

\[\boxed{\;\dot\theta = -A\theta + b.\;}\]

这是一个**线性时不变系统**。它的稳定性由 $-A$ 的谱决定（所有特征值实部为负 $\iff$ $A$ 所有特征值实部为正，即 $-A$ 是 Hurwitz 矩阵）。

与控制理论的连接：回顾 01_数学/40_控制理论/70_Lyapunov稳定性理论中线性系统稳定性的判据——线性系统 $\dot x = Fx$ 渐近稳定当且仅当 $F$ 是 Hurwitz 的（所有特征值实部为负）。这里 $F = -A$，所以我们需要 $A$ 的所有特征值实部为正。TD(0) 收敛性的全部秘密就藏在 $A$ 矩阵的谱中。

Step 3：关键引理——$A$ 正定性证明 ⭐⭐（TVR 1997 核心）¶

引理（Tsitsiklis-Van Roy 1997）：若 Markov 链不可约非周期，$\phi$ 列向量在 $D^\pi$ 加权内积下线性无关，则 $A + A^\top \succ 0$（正定）。

为什么需要 $A + A^\top$ 正定？ $A$ 本身可能不对称（因为 $P^\pi$ 通常不对称），但 $A + A^\top$ 正定蕴含 $A$ 的所有特征值实部为正——这是因为对任意特征值 $\lambda$ 及对应特征向量 $v$，$v^*(A+A^\top)v = 2\mathrm{Re}(\lambda)\|v\|^2 > 0$。

完整证明：

计算

\[A + A^\top = \Phi^\top D^\pi(I - \gamma P^\pi)\Phi + \Phi^\top(I - \gamma P^\pi)^\top D^\pi \Phi = \Phi^\top\bigl[2D^\pi - \gamma(D^\pi P^\pi + (P^\pi)^\top D^\pi)\bigr]\Phi.\]

记 $Q = D^\pi P^\pi$。由平稳性 $d^{\pi\top} P^\pi = d^{\pi\top}$，得：

$Q$ 的每行和：$\sum_j Q_{ij} = \sum_j d^\pi(i) P^\pi_{ij} = d^\pi(i)$（因 $P^\pi$ 行和为 1）；
$Q$ 的每列和：$\sum_i Q_{ij} = \sum_i d^\pi(i) P^\pi_{ij} = d^\pi(j)$（因平稳性）。

因此中间方阵 $M := 2D^\pi - \gamma(Q + Q^\top)$ 的元素为： - 对角元 $M_{ii} = 2d^\pi(i) - 2\gamma Q_{ii}$； - 非对角 $M_{ij} = -\gamma(Q_{ij} + Q_{ji})$。

核心不等式（对所有 $x \in \mathbb{R}^{|\mathcal{S}|}$，$x \neq 0$）：

\[x^\top M x = 2\sum_i d^\pi(i)x_i^2 - 2\gamma\sum_{i,j} Q_{ij} x_i x_j.\]

对第二项应用 AM-GM 不等式 $x_i x_j \le \frac{x_i^2 + x_j^2}{2}$：

\[\sum_{i,j} Q_{ij} x_i x_j \le \sum_{i,j} Q_{ij} \frac{x_i^2 + x_j^2}{2} = \frac{1}{2}\Bigl(\sum_i x_i^2 \sum_j Q_{ij} + \sum_j x_j^2 \sum_i Q_{ij}\Bigr) = \sum_i d^\pi(i) x_i^2.\]

因此：

\[x^\top M x \ge 2\sum_i d^\pi(i)x_i^2 - 2\gamma\sum_i d^\pi(i)x_i^2 = 2(1-\gamma)\sum_i d^\pi(i)x_i^2 > 0,\]

当 $x \neq 0$ 且 $\gamma < 1$。所以 $M \succ 0$。

最后，$\Phi$ 列无关（在 $D^\pi$ 加权内积下）意味着 $\Phi$ 是列满秩的（$\mathrm{rank}(\Phi) = d$），因此 $A + A^\top = \Phi^\top M \Phi \succ 0$。$\blacksquare$

$A$ 正定的物理含义：它就是"TD 方向与真误差方向在 $D^\pi$-范数下夹角小于 90 度"——保证 TD 更新总体指向正确方向。Baird 反例之所以发散，恰恰是因为 off-policy 下 $D$ 不是 $P$ 的不变测度，上述引理失效，$A$ 可以有负实部特征值。

反事实推理——Off-policy 下引理在哪里失效？ 如果用行为策略 $\mu$ 采样（$\mu \neq \pi$），则平稳分布变为 $d^\mu$，但转移矩阵仍是 $P^\pi$（我们要评估的是 $\pi$ 的值函数）。此时 $Q = D^\mu P^\pi$，而 $d^\mu$ 不是 $P^\pi$ 的不变测度，因此 $\sum_i Q_{ij} = \sum_i d^\mu(i) P^\pi_{ij} \neq d^\mu(j)$。AM-GM 步骤中用到的"列和 = $d^\pi(j)$"失效，$M$ 不再保证正定。在 Baird 反例中，$M$ 确实有负特征值，导致 $A$ 有负实部特征值，ODE 发散。

Step 4：ODE 稳定性 + Lyapunov 函数 ⭐⭐¶

$A$ 所有特征值实部为正 $\Rightarrow -A$ Hurwitz $\Rightarrow$ ODE $\dot\theta = -A\theta + b$ 以 $\theta^* = A^{-1}b$ 为全局指数稳定平衡点。

构造 Lyapunov 函数：将 ODE 平移到平衡点 $e = \theta - \theta^*$，得 $\dot e = -Ae$。

回顾 01_数学/40_控制理论/70_Lyapunov稳定性理论中的线性系统 Lyapunov 方程：对 Hurwitz 矩阵 $-A$，连续 Lyapunov 方程

\[A^\top P + PA = I\]

有唯一正定解 $P \succ 0$。取 Lyapunov 函数 $V(e) = e^\top P e$，则

\[\dot V = \dot e^\top P e + e^\top P \dot e = -e^\top A^\top P e - e^\top P A e = -e^\top(A^\top P + PA)e = -e^\top e = -\|e\|^2 < 0\]

对 $e \neq 0$。因此 $V$ 沿 ODE 轨迹严格递减，$\theta^*$ 是全局指数稳定平衡点。

Step 5：调用 Borkar-Meyn 验证四条件 ⭐⭐¶

(A1) $\bar h(\theta) = b - A\theta$ 全局 Lipschitz（$A$ 有限矩阵，$\|h(\theta)-h(\theta')\| = \|A(\theta-\theta')\| \le \|A\|\|\theta-\theta'\|$）✓；
(A2) Robbins-Monro 步长 ✓；
(A3) 噪声 $M_{t+1} = h(\theta_t, X_t) - \bar h(\theta_t)$ 在 Markov 平稳后是 asymptotic 鞅差（可用 Poisson 方程修正为严格鞅差，见 Benveniste-Metivier-Priouret 1990 第 2 章）；
(A4) 缩放极限 $h_\infty(\theta) = \lim_{c\to\infty} h(c\theta)/c = -A\theta$ 线性，原点为全局指数稳定平衡点 ✓。

结论： $$\boxed{\;\theta_t \to \theta^* = A^{-1}b \text{ a.s.}\;}$$ 这正是 Bellman 投影不动点 $\Pi T^\pi V_{\theta^*} = V_{\theta^*}$ 的坐标。$\blacksquare$

为什么这个证明对机器人 RL 人重要¶

第一，你现在拥有完整的发散诊断链条：on-policy 保证 $A \succ 0 \Rightarrow$ 收敛；off-policy（重要性采样、replay buffer）破坏 $A$ 对称正定性 $\Rightarrow$ 可能发散。这直接解释了为什么 DQN 需要 target network + replay buffer（见 6.3），也解释了为什么纯线性 off-policy TD 需要 GTD/TDC 这类两时间尺度修复。

第二，这个证明揭示了 TD 与经典**系统辨识中的递归最小二乘 (RLS)** 的深刻关联——都在解一个形如 $A\theta = b$ 的方程，只是 TD 不知道 $A, b$，只能通过采样估计。

第三，Lyapunov 方程 $A^\top P + PA = I$ 出现在控制理论的每个角落——LQR 的 cost-to-go 矩阵、Kalman 滤波的协方差传播、$\mathcal{H}_\infty$ 控制的性能界。掌握 TD 收敛性证明后，你对 Lyapunov 方程的理解将远超"教科书上一个定理"的水平——它是你亲手用过的工具。

⚠️ 常见陷阱（§6.5.4）¶

💡 概念误区：认为"$A$ 正定等于 $A$ 对称正定"

新手想法："正定不就是对称矩阵特征值全正吗？"

实际上：$A = \Phi^\top D^\pi(I-\gamma P^\pi)\Phi$ 通常不对称（因为 $P^\pi$ 不对称）。我们证明的是 $A + A^\top \succ 0$，这等价于"$A$ 的所有特征值实部为正"——对非对称矩阵，这是正定性的正确推广。非对称矩阵可以有复数特征值，但 $A + A^\top \succ 0$ 保证实部为正。

⚠️ 编程陷阱：计算 $A$ 矩阵时忘记 $D^\pi$ 加权

错误做法：A = Phi.T @ (np.eye(n) - gamma * P_pi) @ Phi（漏了 $D^\pi$）

现象：计算出的 $A$ 可能不正定（因为 $\Phi^\top(I-\gamma P)\Phi$ 不保证正定），导致 ODE 稳定性诊断给出错误结论。

正确做法：A = Phi.T @ D_pi @ (np.eye(n) - gamma * P_pi) @ Phi。$D^\pi$ 的权重是**必需**的——它反映了"on-policy 采样频率"对不同状态的加权。

🧠 思维陷阱：认为"非线性函数近似（NN）下 TD 一定发散"

新手想法："线性 TD 才有 $A$ 矩阵正定性，NN 不是线性的，所以 NN-TD 没有收敛保证，可能发散。"

实际上：非线性函数近似下的 TD 确实没有全局收敛的理论保证（Tsitsiklis-Van Roy 的反例适用于非线性），但这不意味着"一定发散"。实践中 NN-TD（如 DQN、PPO 的 critic）通常工作良好，原因是：(1) target network 隐式地让 $A$ 矩阵"更接近正定"；(2) 有限步更新 + 重新采样避免了"长期积累偏差"；(3) batch normalization / layer normalization 起到了隐式正则化的作用。正确的认知是：理论保证缺失不等于实践必然失败，但当失败时你需要回到理论诊断根因。

练习（§6.5.4）¶

手推：对 3 状态、2 维特征的线性 TD(0)，给定具体的 $P^\pi$、$d^\pi$、$\Phi$，手动计算 $A$ 矩阵并验证 $A + A^\top \succ 0$。然后修改 $D$ 为非平稳分布的对角阵，观察 $A + A^\top$ 是否仍正定。
编程：实现 5-state random walk（Sutton-Barto §6.2），用 NumPy 跑线性 TD(0)，同时用 scipy.linalg.solve_continuous_lyapunov 解 Lyapunov 方程求 $P$，画 $V(\theta_t) = (\theta_t - \theta^*)^\top P(\theta_t - \theta^*)$ 的轨迹，验证其单调递减。
Baird 反例 ODE 分析：查 Baird 反例的 $\Phi$ 和 $P^\pi$（Sutton-Barto 第 2 版 §11.2 或原文 Baird 1995），计算 off-policy 下的 $A$ 矩阵，用 np.linalg.eig(A) 验证存在负实部特征值。

§6.5.5 Q-learning 收敛性的异步 SA 证明 ⭐⭐¶

Watkins 1989 / Tsitsiklis 1994 的三重难点¶

Q-learning 的更新

\[Q_{t+1}(s,a)=Q_t(s,a)+\alpha_t(s,a)\bigl[r+\gamma\max_{a'}Q_t(s',a')-Q_t(s,a)\bigr]\]

有三重难点：(1) 异步——每步只更新一个坐标 $(s,a)$，其他坐标不动；(2) 非线性——max 运算破坏了 TD(0) 的线性结构；(3) 每个坐标的步长序列不同——$\alpha_t(s,a)$ 只在访问到 $(s,a)$ 时使用。

为什么 max 算子是特殊的？ TD(0) 的平均 ODE 是线性的（$\dot\theta = -A\theta + b$），分析起来"只需要"检查 $A$ 的谱。但 Q-learning 含 $\max$，平均 ODE 变成非线性的 $\dot Q = T^* Q - Q$，线性工具不再适用。幸运的是，$\max$ 有一个关键性质弥补了非线性的困难——非扩展性。

max 算子的非扩展性 ⭐⭐¶

引理：$\max$ 算子是 $\infty$-范数下的非扩展映射（non-expansive）：

证明：设 $a^* = \arg\max_a f(a)$，则 $\max_a f(a) - \max_a g(a) = f(a^*) - \max_a g(a) \le f(a^*) - g(a^*) \le |f(a^*) - g(a^*)| \le \|f-g\|_\infty$。对称地得下界。$\blacksquare$

为什么这很重要？ 由此立即得到 $T^*$ 是 $\gamma$-压缩映射（6.1 已证），但现在我们还需要它在**异步**设置下仍然工作——这正是 Tsitsiklis 1994 的贡献。

Tsitsiklis 1994 的异步 SA 框架 ⭐⭐（Machine Learning 16(3):185-202）¶

定理（Tsitsiklis 1994 Theorem 1/3 简化版）：考虑异步 SA

\[\theta_{t+1}(i)=\theta_t(i)+\alpha_t(i)\bigl[H_i(\theta_t)-\theta_t(i)+w_t(i)\bigr]\quad\text{若}\;i\in Y_t,\]

$\theta_{t+1}(i)=\theta_t(i)$ 若 $i\notin Y_t$。假设：

(T1) 每个坐标 $i$ 被无限次更新：$\sum_t\mathbb{1}[i\in Y_t]=\infty$ a.s.；
(T2) 每坐标步长 Robbins-Monro：$\sum_t\alpha_t(i)=\infty,\sum_t\alpha_t(i)^2<\infty$ a.s.；
(T3) 噪声 $w_t$ 鞅差条件方差 $\le K(1+\|\theta_t\|_\infty^2)$；
(T4) 算子 $H$ 在加权 $\infty$-范数下是压缩：存在正权重 $w$ 与 $\beta<1$，使 $\|H(\theta)-H(\theta')\|_{w,\infty}\le\beta\|\theta-\theta'\|_{w,\infty}$，其中 $\|x\|_{w,\infty}=\max_i|x_i|/w(i)$。

则 $\theta_t\to\theta^*=H(\theta^*)$ a.s.

条件 (T1) 的含义：每个状态-动作对都要被无限次访问。如果某个 $(s,a)$ 只被访问有限次，它的 $Q$ 值永远停留在初始值附近，不可能收敛到 $Q^*$。$\varepsilon$-greedy 策略保证了这一点（以 $\varepsilon$ 概率随机选动作）。

条件 (T4) 的含义：这是 Banach 不动点定理的推广版——不要求所有坐标同步更新，只要算子整体是压缩的。

对 Q-learning 的应用¶

取 $\theta = Q \in \mathbb{R}^{|\mathcal{S}\times\mathcal{A}|}$，$H = T^*$（最优 Bellman 算子）：

\[(T^*Q)(s,a)=\mathbb{E}\bigl[R(s,a)+\gamma\max_{a'}Q(s',a')\bigr].\]

6.1 已证 $T^*$ 是 $\infty$-范数下 $\gamma$-压缩 $\Rightarrow$ (T4) 成立（取 $w\equiv 1$，$\beta=\gamma$）。(T1) 来自"每对 $(s,a)$ 被 policy 以正概率访问"（常用 $\varepsilon$-greedy 保证）。(T2) 是工程选择。(T3) 对 finite MDP 显然成立。

结论：$\boxed{\;Q_t\to Q^* \text{ a.s.}\;}$

证明骨架（两段法）¶

Step A（噪声清洗）：定义辅助过程 $\tilde Q_t = T^* Q_t$，迭代可改写为

\[Q_{t+1} = Q_t + \alpha_t(\tilde Q_t - Q_t) + \alpha_t w_t.\]

由 (T3) + Robbins-Monro + Doob 最大不等式 $\Rightarrow$ 噪声对 $Q_t$ 的累积扰动收敛到 0 a.s.

Step B（压缩驱动）：由 $T^*$ 的 $\gamma$-压缩性，定义误差 $e_t = \|Q_t - Q^*\|_\infty$。Jaakkola-Jordan-Singh 1994 引理给出

\[\mathbb{E}[e_{t+1}\mid\mathcal{F}_t] \le (1-\alpha_t) e_t + \gamma\alpha_t e_t + O(\alpha_t^2) = (1-(1-\gamma)\alpha_t) e_t + o(\alpha_t).\]

（这是 $\gamma < 1$ 关键处——$(1-\gamma)$ 是"压缩余量"。）迭代这条不等式 + $\sum\alpha_t = \infty \Rightarrow e_t \to 0$ a.s. $\blacksquare$

ODE 视角的重新诠释¶

把 Q-learning 的平均 ODE 写成 $\dot Q = T^*Q - Q$，这是一个在 $\infty$-范数下指数稳定的系统（Lyapunov $V = \|Q - Q^*\|_\infty$，$\dot V \le -(1-\gamma)V$）。异步 + 噪声由 Borkar-Meyn 在 Borkar 1998、Borkar 2008 第 7 章的异步版定理处理。

与 TD(0) 证明的对比：

方面	TD(0)	Q-learning
平均 ODE	线性 $\dot\theta = -A\theta + b$	非线性 $\dot Q = T^*Q - Q$
稳定性工具	Hurwitz 矩阵 + Lyapunov 方程	$\infty$-范数 Lyapunov + 压缩映射
同步/异步	可同步可异步	天然异步
关键困难	$A$ 正定性	max 非线性 + 异步
范数	$D^\pi$-加权 2-范数	$\infty$-范数

从 ODE 角度理解 $\gamma < 1$ 的必要性 ⭐⭐¶

Q-learning 的平均 ODE 是 $\dot Q = T^*Q - Q$，其中 $T^*$ 是最优 Bellman 算子。定义误差 $e(t) = Q(t) - Q^*$，由 $T^*Q^* = Q^*$：

\[\dot e = T^*Q - Q - (T^*Q^* - Q^*) = (T^*Q - T^*Q^*) - (Q - Q^*) = (T^*Q - T^*Q^*) - e.\]

因此 $\dot V \le \gamma V - V = -(1-\gamma)V$，其中 $V = \|e\|_\infty$。这给出指数衰减 $V(t) \le V(0)e^{-(1-\gamma)t}$。

$\gamma = 1$ 时的灾难：如果 $\gamma = 1$，$T^*$ 是 $1$-Lipschitz（非扩展但不压缩），$\dot V \le 0$ 但不严格负——ODE 不再保证收敛（只保证 $V$ 不增长）。在 $\infty$-范数 Lyapunov 意义下，系统只是"稳定"而非"渐近稳定"。实践中 $\gamma = 0.99$ 的 PPO 之所以工作良好，正是因为 $(1-\gamma) = 0.01$ 虽小但非零——它提供了微弱但持续的"压缩力"。

反事实推理：如果强行让 $\gamma = 1$（无折扣），Q-learning 的 ODE 会怎样？ODE $\dot Q = T^*Q - Q$ 中 $T^*$ 变成非压缩的——系统可能有多个不动点（平均奖励 MDP 的 bias 不唯一），也可能在它们之间游荡而不收敛。这就是为什么"平均奖励 RL"（R-learning、differential TD）需要完全不同的分析框架——不能直接用压缩映射论证。

Q-learning 收敛速率的定量分析 ⭐⭐⭐¶

Srikant-Ying 2019 和 Even-Dar-Mansour 2003 给出了 Q-learning 的有限样本复杂度。对同步 Q-learning（tabular，所有 $(s,a)$ 每步更新），步长 $\alpha_t = 1/(1 + (1-\gamma)^{-1} N_{sa}(t))^w$（$w \in (0.5, 1)$，$N_{sa}$ 是访问计数）：

\[\mathbb{E}\|Q_T - Q^*\|_\infty \le \tilde O\Bigl(\frac{1}{(1-\gamma)^3\sqrt{T}}\Bigr).\]

与 TD(0) 的速率对比：TD(0) 的速率为 $\tilde O(1/((1-\gamma)\sqrt{T}))$——比 Q-learning 快 $(1-\gamma)^{-2}$ 倍。这反映了一个深刻的事实：off-policy + max 非线性让 Q-learning 比 on-policy TD 在统计效率上更差。工程启示：如果你的任务允许 on-policy 采样（如 Isaac Lab 的并行仿真），用 PPO（本质上是 on-policy）比 DQN（off-policy Q-learning）在样本复杂度上更优——这有理论支撑。

⚠️ 常见陷阱（§6.5.5）¶

💡 概念误区：认为"Q-learning 收敛靠 Banach 不动点定理"

新手想法："$T^*$ 是压缩映射，Banach 定理直接给收敛，为什么还要 Tsitsiklis？"

实际上：Banach 不动点定理只保证**同步**迭代 $Q_{k+1} = T^*Q_k$ 的收敛。Q-learning 是**异步的**（每步只更新一个坐标）且**带噪声的**（用单样本 $r + \gamma\max_{a'}Q(s',a')$ 替代期望 $T^*Q$）。这两个"脏"的因素需要额外的数学工具——Tsitsiklis 的异步 SA 定理正是提供这些工具的。

🧠 思维陷阱：认为"$\varepsilon$-greedy 的 $\varepsilon$ 越大探索越好"

新手想法："条件 (T1) 要求无限次访问每个 $(s,a)$，所以 $\varepsilon$ 越大越好。"

实际上：$\varepsilon$ 越大确实保证了更快的覆盖（满足 T1），但也引入了更大的噪声（因为行为策略更偏离最优策略），收敛速度反而可能变慢。最优的 $\varepsilon$ 衰减策略（如 $\varepsilon_t = 1/t^{0.5}$）在理论和实践中都是 trade-off——前期大 $\varepsilon$ 探索，后期小 $\varepsilon$ 利用。

练习（§6.5.5）¶

手推：证明 max 算子的非扩展性引理。（提示：不等式链。）
概念：为什么 $\gamma = 1$ 时 Q-learning 不保证收敛？从两个角度解释：(a) Bellman 算子不再是压缩映射；(b) Step B 中 $(1-\gamma)$ 压缩余量为零。
工程：在 CleanRL 的 DQN 实现中，找到 Q-learning 更新的代码行，指出哪里对应 $r + \gamma\max_{a'}Q(s',a')$，哪里对应 detach() / stop_gradient。

§6.5.6 Polyak-Ruppert 平均与收敛加速 ⭐⭐⭐¶

动机：SA 的渐近方差太大¶

标准 Robbins-Monro SA 的收敛速率为 $\mathbb{E}\|\theta_t - \theta^*\|^2 = O(1/t)$，但渐近方差（即 $O(1/t)$ 前面的常数）取决于步长选择和 $h$ 的 Jacobian，通常不是最优的。有没有办法在不改变 $h$ 的情况下降低渐近方差？

Polyak 1990 / Ruppert 1988 的简单思想¶

定理（Polyak 1990, SIAM J. Control Optim. 28(6):999-1012）：考虑 SA 递推

\[\theta_{t+1} = \theta_t + \alpha_t[h(\theta_t) + M_{t+1}],\]

定义**平均迭代**（averaged iterate）

\[\bar\theta_t = \frac{1}{t}\sum_{s=1}^{t} \theta_s.\]

若 $\alpha_t = c/t^\beta$，$\beta \in (1/2, 1)$（注意：不满足标准 Robbins-Monro 的 $\sum\alpha^2 < \infty$！），则 $\bar\theta_t$ 几乎必然收敛到 $\theta^*$，且

\[\sqrt{t}(\bar\theta_t - \theta^*) \xrightarrow{d} \mathcal{N}(0, \Sigma^*),\]

其中 $\Sigma^* = J^{-1} S (J^{-1})^\top$，$J = \nabla\bar h(\theta^*)$（$h$ 的 Jacobian），$S = \mathrm{Cov}(h(\theta^*, X))$（噪声协方差）。

核心要点：

$\Sigma^*$ 是信息论下界——它等于 Cramer-Rao 下界（Fisher 信息矩阵的逆），是**任何无偏渐近正态估计的最小可能方差**。
步长 $\alpha_t$ 不需要精确选择——只要 $\beta \in (1/2, 1)$，平均化后的渐近方差都是最优的。这比标准 SA（渐近方差依赖于 $c$ 的选择）鲁棒得多。
实现极简——只需在原始 SA 的基础上多维护一个运行平均。

跨领域类比：Polyak-Ruppert 平均在统计学中的角色，类似于 PID 控制中的积分项。纯比例控制（P 控制，对应原始 SA）有稳态误差（对应非最优渐近方差）；加入积分项（I 控制，对应取时间平均）消除了稳态误差（达到最优方差）。但积分也引入了"响应变慢"（平均化使得早期的坏估计被长时间记住）——在非平稳环境中，这可以是一个问题。

对 RL 的意义¶

在 tabular TD(0) 或线性 TD(0) 中，Polyak-Ruppert 平均可以直接应用：

\[\bar\theta_t = \frac{1}{t}\sum_{s=1}^{t} \theta_s.\]

这给出了 TD(0) 参数的渐近最优估计。但在实践中（NN 函数近似），平均化很少使用——原因是 NN 参数空间是非凸的，"参数平均"不等价于"函数平均"。工程师转而使用 Exponential Moving Average (EMA) 或 target network：$\theta_{\rm target} = \tau\theta + (1-\tau)\theta_{\rm target}$，这是 Polyak 平均的指数衰减版本，更适合非平稳和非线性设置。

反事实推理：如果在 PPO 的 critic 中使用 Polyak-Ruppert 平均，会怎样？由于 PPO 的目标函数随策略更新而变化（非平稳），简单的 $1/t$ 平均会"记住"过时的 critic 参数，导致值函数估计滞后于当前策略。EMA（$\tau$ 接近 1）通过快速遗忘解决了这个问题——它既有平均化的方差降低效果，又能跟踪非平稳目标。

Polyak-Ruppert 平均的完整证明思路 ⭐⭐⭐¶

为了理解 Polyak-Ruppert 为什么达到最优方差，让我们追踪关键步骤。

设定：一维情形 $h(\theta) = -a(\theta-\theta^*)$，$a > 0$。SA 迭代为 $\theta_{t+1} = \theta_t + \alpha_t(-a(\theta_t - \theta^*) + M_{t+1})$，噪声 $\mathbb{E}[M_{t+1}^2] = \sigma^2$。

Step 1：原始 SA 的渐近行为

取 $\alpha_t = c/t^\beta$，$\beta \in (1/2, 1)$。由于 $\beta < 1$，$\sum\alpha_t^2 = \sum c^2/t^{2\beta}$ 在 $2\beta > 1$ 时收敛，满足 RM 条件。但由于 $\beta < 1 < 2\beta$（当 $\beta > 1/2$），原始 $\theta_t$ 的收敛速率是 $O(1/t^\beta)$，比最优的 $O(1/\sqrt{t})$ 慢。

Step 2：平均化的"魔法"

定义 $\bar\theta_t = \frac{1}{t}\sum_{s=1}^t \theta_s$。对误差 $e_t = \theta_t - \theta^*$ 求和：

\[t\bar e_t = \sum_{s=1}^t e_s = \sum_{s=1}^t \Bigl(e_{s-1} + \alpha_s(-ae_{s-1} + M_s)\Bigr) = \sum_{s=1}^t (1-a\alpha_s)e_{s-1} + \sum_{s=1}^t \alpha_s M_s.\]

经过仔细分析（展开递推、交换求和顺序），可以证明：

\[\sqrt{t}\,\bar e_t \xrightarrow{d} \mathcal{N}\Bigl(0, \frac{\sigma^2}{a^2}\Bigr).\]

关键：渐近方差 $\sigma^2/a^2$ 不依赖于步长中的常数 $c$ 或指数 $\beta$！这是因为平均化"冲掉"了步长选择的细节。

Step 3：最优性

对方程 $h(\theta) = -a(\theta-\theta^*)$ 的根 $\theta^*$，Fisher 信息为 $I = a^2/\sigma^2$（因为"一次观测"$h(\theta,X) = -a(\theta-\theta^*)+M$ 的方差是 $\sigma^2$，"信号强度"是 $a$）。Cramer-Rao 下界 = $1/I = \sigma^2/a^2$。Polyak-Ruppert 平均恰好达到此下界。

高维推广：对 $h(\theta) = -A(\theta-\theta^*) + M$，Jacobian $J = -A$，噪声协方差 $S = \sigma^2 I$（或一般的 $S$），渐近方差为 $\Sigma^* = A^{-1} S (A^{-1})^\top = A^{-1} S A^{-\top}$。

Polyak 平均与 EMA 的精确对比¶

特性	Polyak-Ruppert ($1/t$ 平均)	EMA ($\theta_{\rm ema} = \tau\theta + (1-\tau)\theta_{\rm ema}$)
遗忘速度	均匀加权所有历史	指数遗忘，半衰期 $\approx 1/(1-\tau)$
非平稳适应	差（早期坏样本永远影响）	好（旧信息快速遗忘）
渐近最优性	达到 Cramer-Rao 下界	不一定最优（取决于 $\tau$）
RL 中的化身	tabular LSTD	target network（$\tau$=0.995/0.999）
计算开销	$O(d)$：维护均值	$O(d)$：维护 EMA

在 DQN/SAC 中的 target network（$\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-$）本质上是 Polyak 平均的 EMA 版本。$\tau$ 的选择（通常 0.005 或 0.001）控制了"target 滞后当前多少"——$\tau$ 大则跟踪快但方差大，$\tau$ 小则稳定但滞后。这正是 SA 稳态分布方差（$\propto$ 有效步长）的工程映射。

⚠️ 常见陷阱（§6.5.6）¶

💡 概念误区：把 Polyak 平均与 batch normalization 的 running mean 混为一谈

新手想法："这不就是 running average 吗？和 BatchNorm 里的一样。"

实际上：BatchNorm 的 running mean 是对**统计量**（激活的均值/方差）做 EMA，用于推理时的归一化。Polyak 平均是对**参数**本身做平均，用于降低估计方差。目的、对象、效果完全不同。

⚠️ 编程陷阱：在非平稳目标下使用 Polyak 均匀平均

错误做法：在 online RL 训练中对 critic 参数做 $\bar\theta_t = \frac{1}{t}\sum \theta_s$。

现象：训练前期 reward 上升，后期停滞或下降——因为早期的"坏"参数被均匀平均记住，拖累了当前估计。

根本原因：Polyak-Ruppert 的最优性建立在**平稳**假设上——目标 $\theta^*$ 不变。RL 中目标随策略变化而变化（非平稳），均匀平均不再最优。

正确做法：使用 EMA（$\tau$ 接近 1）或 periodic hard update（每 $C$ 步 $\theta^- \leftarrow \theta$）。

练习（§6.5.6）¶

手推：对一维线性 SA $\theta_{t+1} = \theta_t + \alpha_t(-\theta_t + \varepsilon_t)$，$\varepsilon_t \sim \mathcal{N}(0,1)$，$\alpha_t = 1/t^{0.7}$，推导 $\bar\theta_t$ 的渐近方差。验证它等于 $1/a^2 = 1$（Cramer-Rao 下界）。
编程：实现 Polyak 平均 vs EMA vs 原始 SA 的对比实验。画三条曲线的方差衰减速率，验证 Polyak 平均的 $O(1/t)$ 速率优于原始 SA。
工程思考：在 SAC 中 target network 的 $\tau = 0.005$。如果改成 $\tau = 0.5$（快速 EMA），理论上和实践中会发生什么？

§6.5.A 两时间尺度 SA 与 Actor-Critic 收敛性 ⭐⭐⭐¶

Actor-Critic 的两时间尺度结构（6.2 回顾）¶

回顾 6.2：策略梯度定理给出 $\nabla J(\theta) = \mathbb{E}[\nabla\log\pi_\theta(a\mid s) Q^\pi(s,a)]$。Actor-Critic 用一个参数化的 $Q_w$ 代替真实的 $Q^\pi$，同时更新 $w$（critic）和 $\theta$（actor）：

\[\begin{cases}w_{t+1}=w_t+\beta_t\,g_{\rm critic}(w_t,\theta_t,X_t)\\\theta_{t+1}=\theta_t+\alpha_t\,g_{\rm actor}(w_t,\theta_t,X_t)\end{cases}\]

若 $\alpha_t/\beta_t\to 0$（$\alpha_t$ 慢、$\beta_t$ 快），从 actor 的视角看 critic "瞬时"收敛到给定 $\theta$ 下的真值函数 $w^*(\theta)$；从 critic 的视角看 actor "几乎不动"。

为什么需要两个时间尺度？ 如果 actor 和 critic 用相同的步长，它们会相互干扰——critic 还没收敛到正确的值函数，actor 就基于错误的值函数做了策略更新，策略更新又改变了 critic 的目标。两时间尺度分离解决了这个"鸡生蛋还是蛋生鸡"的问题：让 critic 先收敛（快时间尺度），然后 actor 基于"几乎正确"的 critic 更新（慢时间尺度）。

Borkar 1997 两时间尺度 SA 定理 ⭐⭐⭐¶

定理（Borkar 1997, Systems & Control Letters 29(5):291-294）：考虑

\[w_{t+1}=w_t+\beta_t[f(w_t,\theta_t)+M^1_{t+1}],\quad\theta_{t+1}=\theta_t+\alpha_t[g(w_t,\theta_t)+M^2_{t+1}].\]

假设：

两套步长均 Robbins-Monro 且 $\alpha_t/\beta_t\to 0$；
噪声 $M^1, M^2$ 鞅差方差受控；
快尺度 ODE（$\theta$ 冻结）$\dot w = f(w,\theta)$ 对每个 $\theta$ 有唯一全局渐近稳定平衡 $\lambda(\theta)$，$\lambda$ Lipschitz；
慢尺度 ODE $\dot\theta = g(\lambda(\theta),\theta)$ 有唯一全局渐近稳定平衡 $\theta^*$；
迭代几乎必然有界。

则 $(\theta_t, w_t) \to (\theta^*, \lambda(\theta^*))$ a.s.

证明思路：以 $\beta_t$ 时间刻度看，$\theta$ 近似常数，$w$ 追踪 $\dot w = f(w,\theta) \to \lambda(\theta)$；以 $\alpha_t$ 时间刻度看，$w$ 已被快拉到 $\lambda(\theta)$ 附近，$\theta$ 追踪 $\dot\theta = g(\lambda(\theta),\theta)$。

与控制理论的 singular perturbation 的深刻联系：这个证明思路与 Kokotovic 1984 的 $\epsilon$-奇异摄动框架完全平行：

\[\dot x = f(x,z),\quad \epsilon\dot z = g(x,z).\]

当 $\epsilon \to 0$ 时（"快子系统极快"），$z$ 几乎瞬时收敛到 $z = \lambda(x)$（即 $g(x,z)=0$ 的根），$x$ 的运动由"降阶模型"$\dot x = f(x,\lambda(x))$ 描述——这就是 Tikhonov 定理。Borkar 1997 是 Tikhonov/Kokotovic 的离散随机版本。

回顾 01_数学/40_控制理论/70_Lyapunov稳定性理论：singular perturbation 理论是 Lyapunov 稳定性的一个重要推广——用快子系统和慢子系统各自的 Lyapunov 函数，构造复合 Lyapunov 函数证明整体稳定性。两时间尺度 SA 的证明走的是完全相同的路线。

Konda-Tsitsiklis 2003 Actor-Critic 定理 ⭐⭐⭐¶

定理（Konda-Tsitsiklis 2003, SIAM J. Control Optim. 42(4):1143-1166）：在 Polish 状态-动作空间、兼容特征（compatible features）、步长两时间尺度、遍历性条件下，Actor-Critic 的 $\theta_t$ a.s. 收敛到 $\nabla J(\theta)=0$ 的集合；critic 参数 $w_t$ a.s. 收敛到 $w^*(\theta_t)$，即 $Q^{\pi_{\theta_t}}$ 在兼容特征张成子空间上的投影。

什么是"兼容特征"？ Sutton et al. 2000 定义的条件：critic 的特征 $\psi(s,a)$ 等于 $\nabla_\theta\log\pi_\theta(a\mid s)$。在这种选择下，critic 的近似误差不影响 actor 的梯度方向——即 $\nabla_\theta J(\theta) = \mathbb{E}[\psi(s,a)Q_w(s,a)]$ 在 $w = w^*(\theta)$ 时是精确的策略梯度。这是理论上的一个优美条件，但实践中很少严格满足（NN 的特征不是手动设计的）。

对工程师的要点：在 Isaac Lab / legged_gym 的 PPO 实现中，critic 的学习率通常大于 actor（典型 $5\times 10^{-4}$ vs $3\times 10^{-4}$）——这正是两时间尺度分离的工程实现。若违反（critic lr 远小于 actor lr），收敛的理论保证消失。

Konda-Tsitsiklis 证明的关键困难 ⭐⭐⭐¶

Konda-Tsitsiklis 2003 的证明比 Borkar 1997 的抽象定理复杂得多，原因是 RL 中的几个特殊困难：

策略变化导致 Markov 链转移核变化：当 $\theta$ 更新时，策略 $\pi_\theta$ 变了，状态转移分布也变了——这意味着 critic 的"目标"$Q^{\pi_\theta}$ 在缓慢移动。需要证明 critic 的收敛速度快于目标的移动速度。
平稳分布依赖策略参数：$d^{\pi_\theta}$ 是 $\theta$ 的函数。快 ODE 的平衡点 $w^*(\theta)$ 隐式依赖 $d^{\pi_\theta}$，其 Lipschitz 连续性不是显然的。
策略空间的非凸性：慢 ODE $\dot\theta = \nabla J(\theta)$ 的右端是非凸目标的梯度，只能保证收敛到**临界点集**（$\nabla J = 0$），不能保证全局最优。

这些困难的解决需要用到：遍历性理论（保证 Markov 链快速混合）、兼容特征条件（保证 critic 近似误差不影响 actor 梯度方向）、LaSalle 不变集原理（处理非严格下降）。

GTD/TDC 作为两时间尺度 SA ⭐⭐⭐¶

Gradient TD (Sutton-Maei 2009) 解决了 off-policy 线性 TD 的发散问题。它引入辅助变量 $w$ 来估计 $\mathbb{E}[\phi\phi^\top]^{-1}(\cdot)$，主参数 $\theta$ 慢更新。两个变量的更新构成两时间尺度 SA：

\[w_{t+1} = w_t + \beta_t(\delta_t\phi_t - \phi_t\phi_t^\top w_t), \quad \theta_{t+1} = \theta_t + \alpha_t(\phi_t - \gamma\phi'_t)(\phi_t^\top w_t).\]

快尺度 ODE（$\theta$ 冻结）：$\dot w = A_w w + b_w$，其中 $A_w = -\mathbb{E}[\phi\phi^\top] \prec 0$——快系统稳定（因为 $\mathbb{E}[\phi\phi^\top]$ 是 Gram 矩阵，正半定，列独立时正定）。慢尺度 ODE：$\dot\theta = $ 真策略梯度方向——套 Borkar 1997，证出 off-policy 线性 TD 的收敛。

GTD/TDC 为什么能在 off-policy 下收敛？ 关键在于它把"不是梯度的 TD 更新"替换成了一个真正的梯度：目标函数是 MSPBE（Mean Squared Projected Bellman Error）$J(\theta) = \|V_\theta - \Pi T^\pi V_\theta\|_{D^\mu}^2$。GTD2 最小化的是这个目标的精确梯度——因此它是 SGD 而非一般 SA，梯度结构自动保证了 ODE 的稳定性（梯度流在凸函数上全局收敛）。

两时间尺度的工程实现方式 ⭐⭐¶

理论要求 $\alpha_t/\beta_t \to 0$，但工程中很少严格用不同衰减率。实际的两时间尺度实现有三种方式：

方式	实现	理论对应	常用于
lr 比值固定	critic_lr = 5x actor_lr	近似满足（常数比不严格 $\to 0$）	PPO/SAC (Isaac Lab, rl_games)
多步 critic 更新	每个 actor 步做 5-10 个 critic 步	等效于 $\beta$ 更大	PPO (多 epoch critic)
target network + 周期更新	每 C 步 $\theta^- \leftarrow \theta$	离散时间尺度分离	DQN, SAC

实验观察：在 Isaac Lab 的 ANYmal locomotion 训练中，典型配置为 learning_rate = 3e-4（actor 和 critic 共享），但 critic 做 5 个 mini-batch epoch 而 actor 做 1-3 个。这等效于 critic 的有效步长是 actor 的 2-5 倍——近似满足两时间尺度条件。

两时间尺度违反的具体后果：当 critic lr 远小于 actor lr 时： 1. Critic 估计的 $\hat Q$ 严重滞后于当前策略 $\pi_\theta$ 2. Actor 基于过时的 $\hat Q$ 计算 advantage，得到**有偏的策略梯度** 3. 有偏梯度导致策略向错误方向更新 4. 错误的策略产生更差的数据，进一步恶化 critic 的估计 5. 正反馈循环 --> 训练震荡或发散

⚠️ 常见陷阱（§6.5.A）¶

⚠️ 编程陷阱：在 PPO 中把 critic lr 设得太小

错误做法：critic_lr = 1e-5, actor_lr = 3e-4（critic 比 actor 慢 30 倍）。

现象：critic 还没收敛到正确的值函数，actor 就已经基于错误的 advantage 估计做了大量更新，导致策略震荡或发散。

根本原因：违反了两时间尺度条件 $\alpha_t/\beta_t \to 0$——应该是 actor 慢 critic 快（$\alpha_t \ll \beta_t$），反过来就丧失了理论保证。

正确做法：critic_lr = 5e-4, actor_lr = 3e-4（critic 比 actor 快 1.5-5 倍）。或者让 critic 每步更新多次（PPO 中常见做 5-10 个 epoch 的 critic 更新 vs 1-3 个 epoch 的 actor 更新）。

练习（§6.5.A）¶

概念：写出 Actor-Critic 的两个 ODE。快 ODE 的右端为什么是 TD 误差？慢 ODE 的右端为什么是 $\nabla J(\theta)$？（用策略梯度定理 + 兼容特征。）
工程：在 Isaac Lab 的 PPO 中做 ablation：(a) critic lr = 5x actor lr（标准）；(b) critic lr = 0.2x actor lr（违反两时间尺度）。记录 reward 曲线和 value loss 曲线的差异。
跨章综合（需 6.2 + 6.3 + 本章）：为什么 GTD/TDC 能在 off-policy 下收敛，而普通 TD 不行？从两时间尺度 SA 的角度和 $A$ 矩阵正定性的角度分别解释。

§6.5.B 鞅收敛定理在 RL 中的精细应用 ⭐⭐⭐⭐¶

Doob 的 supermartingale 收敛定理（核心工具）¶

定理：设 $\{X_t,\mathcal{F}_t\}$ 是非负 supermartingale，$\sup_t\mathbb{E}[X_t]<\infty$（对非负 supermartingale 自动成立：$\mathbb{E}[X_t]\le\mathbb{E}[X_0]$），则 $X_t\to X_\infty$ a.s. 且 $\mathbb{E}[X_\infty]\le\mathbb{E}[X_0]$。

在 RL 中的应用：$V(\theta_t)$ 或其修正版本 $U_t=V(\theta_t)\prod_s(1+C\alpha_s^2)^{-1}$ 是近似 supermartingale，直接调用此定理给出 $V(\theta_t)$ 收敛 $\Rightarrow\theta_t$ 收敛。

Azuma-Hoeffding 与有限样本集中 ⭐⭐⭐⭐¶

定理（Azuma-Hoeffding）：鞅差 $\{d_t\}$，$|d_t|\le c_t$ a.s.，则

\[\mathbb{P}\bigl(\bigl|\sum_{t\le T}d_t\bigr|\ge u\bigr)\le 2\exp\bigl(-u^2/(2\sum_t c_t^2)\bigr).\]

对 TD 的意义：配合 Robbins-Monro 可得**有限样本界**（Bhandari-Russo-Singal 2018, Srikant-Ying 2019）：常数步长 TD(0) 在 $T$ 步后 $\mathbb{E}\|\theta_T-\theta^*\|^2\le(1-2(1-\gamma)\alpha)^T\|\theta_0-\theta^*\|^2+\frac{\alpha C}{1-\gamma}$。

这是现代 RL 理论从"渐近收敛"到"样本复杂度"的跨越——渐近分析只说"最终会收敛"，有限样本分析回答"多少数据才够？"。对机器人 RL 来说，"多少数据"直接转化为"多少 GPU 小时"或"多少真机实验"，有直接的工程价值。

鞅构造技巧：Poisson 方程 ⭐⭐⭐⭐¶

对 Markov 噪声，严格的鞅差不存在（因为 $X_t$ 依赖于 $X_{t-1}$），但可通过解 Poisson 方程 $\hat v - P\hat v = h - \bar h$ 把 $h(\theta,X_t)$ 分解为 $\bar h(\theta) + (\hat v(X_t) - P\hat v(X_{t-1})) + \Delta_t$，中间项是严格鞅差，$\Delta_t$ 是小项。

为什么需要 Poisson 方程？ 因为 RL 中 agent 的状态转移是 Markov 的，不是 i.i.d. 的。连续两步的样本 $(S_t, S_{t+1})$ 是相关的。为了应用鞅收敛定理，需要把 Markov 噪声"折叠"成鞅差加上一个可控的余项。这是 Benveniste-Metivier-Priouret 1990 第 2 章的核心技术，在 Konda-Tsitsiklis 2003 中被反复使用。

§6.5.C 含噪声 ODE 稳定性与 SDE 视角 ⭐⭐⭐⭐¶

扩散极限定理¶

常数步长 SA $\theta_{t+1}=\theta_t+\alpha[h(\theta_t)+M_{t+1}]$ 经适当缩放（时间 $\alpha\to 0$、$\theta$ 中心化并缩放 $\sqrt\alpha$）后，极限是随机微分方程

\[d\theta=\bar h(\theta)dt+\sqrt\alpha\,\sigma(\theta)dW.\]

这给出**常数步长 SA 的稳态方差精确刻画**：$\theta_t^\infty\sim\mathcal{N}(\theta^*,\tfrac{\alpha}{2}\Sigma_\infty)$，其中 $\Sigma_\infty$ 满足连续 Lyapunov 方程 $A\Sigma+\Sigma A^\top=\sigma\sigma^\top$。

对机器人工程师：常数学习率下 bias-variance trade-off 的精确定量——学习率 $\alpha$ 减半，稳态方差减半，但收敛速度也减半。

随机 Lyapunov 方法¶

$V(\theta)$ 在 SDE 下的 infinitesimal generator：

\[\mathcal{L}V=\nabla V^\top\bar h+\tfrac{1}{2}\mathrm{tr}(\sigma\sigma^\top\nabla^2V).\]

若 $\mathcal{L}V\le -cV$ $\Rightarrow$ SDE 指数稳定。这是 Kushner 1967 的经典理论，用于分析带噪声 SA 的**漂移-扩散竞争**：漂移项 $\nabla V^\top\bar h$ 把迭代拉向 $\theta^*$，扩散项 $\frac{1}{2}\mathrm{tr}(\sigma\sigma^\top\nabla^2V)$ 把迭代推开。稳定性要求漂移占主导。

§6.5.D 异步 SA 框架 ⭐⭐⭐⭐¶

Tsitsiklis 1994 的六条假设¶

原文实际假设为 Assumptions 1-6，结构为：(1) 每坐标步长 Robbins-Monro；(2) 无穷次更新；(3) 延迟有界；(4) 噪声鞅差；(5) 噪声方差线性增长；(6) 算子是 $\infty$-范数压缩或存在单调 Lyapunov。

对分布式 RL 的意义¶

IMPALA (Espeholt 2018)、Ape-X (Horgan 2018)、R2D2 (Kapturowski 2019)、SEED RL (Espeholt 2020) 都是分布式 actor-learner 系统——多个 actor 在旧参数下产生数据，learner 在某一 "wall-clock time" 用混合代数旧数据做 SA 更新。这**正是异步 SA** 的现代实例。Tsitsiklis 1994 保证了只要"参数延迟有界 + 每坐标无限访问"，收敛性不变。

反事实推理：如果在 IMPALA 中不控制参数延迟（让 actor 用任意旧的参数），会怎样？延迟无界意味着某些 actor 产生的数据对应的参数 $\theta_{t-\tau}$ 中 $\tau$ 可以任意大——这些数据几乎不包含当前 $\theta_t$ 的信息，引入了巨大的 bias。V-trace（Espeholt 2018）通过截断重要性比率来限制这个 bias，本质上是在"修补"延迟无界的问题。

机器人并行仿真中的异步性¶

Isaac Gym / Isaac Lab 在单 GPU 上并行 4096 个环境，虽然数据在 GPU 上同步，但异步 SA 分析仍然揭示：不同环境采样分布不完全相同（domain randomization），这相当于异步 SA 中每个"虚拟坐标"被不同频率访问——影响收敛速率但不破坏收敛性，前提是 coverage 充分。

§6.5.E Lyapunov 函数构造方法 ⭐⭐⭐¶

线性系统：Lyapunov 方程¶

对 $\dot\theta=-A\theta$，$A$ 的特征值实部全正（即 $-A$ Hurwitz），取 $V(\theta)=\theta^\top P\theta$，$P$ 由 Lyapunov 方程 $A^\top P+PA=I$ 唯一解出（$P\succ 0$）。

符号约定说明：ODE 为 $\dot\theta = -A\theta$，沿轨迹求导得 $\dot V = -\theta^\top(A^\top P + PA)\theta = -\theta^\top I\,\theta = -\|\theta\|^2 < 0$。注意这里的 Lyapunov 方程是 $A^\top P+PA=Q$（$Q\succ 0$），不是 $A^\top P+PA=-Q$。后者对应的是系统 $\dot x = Ax$（$A$ Hurwitz，即特征值实部全负）的标准形式。两种写法的区别仅在于 ODE 右端是 $-A\theta$ 还是 $A\theta$——本章 ODE 右端带负号（因为 SA 的漂移项 $\bar h(\theta)=-A\theta+b$ 在不动点附近线性化后为 $-A(\theta-\theta^*)$），故取正号形式 $A^\top P+PA=I$。

回顾 01_数学/40_控制理论/70_Lyapunov稳定性理论：Lyapunov 方程是线性系统稳定性分析的标准工具。在 TD(0) 中 $A = \Phi^\top D^\pi(I-\gamma P^\pi)\Phi$（特征值实部全正），此 $P$ 在代码中可由 scipy.linalg.solve_continuous_lyapunov 数值求解，从而验证 TD 轨迹沿 $V$ 严格下降。

import numpy as np
from scipy.linalg import solve_continuous_lyapunov

# A 矩阵来自 TD(0) 的平均 ODE: d theta/dt = -A theta + b
# A 的特征值实部全正 (on-policy 保证), 即 -A 是 Hurwitz
A = np.array([[0.8, -0.2], [-0.1, 0.6]])  # 示例

# 解 Lyapunov 方程 A^T P + P A = I (注意正号!)
# scipy.solve_continuous_lyapunov 求解 X A^T + A X = Q
# 所以传入 A^T 作为第一个参数，I 作为第二个参数
P = solve_continuous_lyapunov(A.T, np.eye(A.shape[0]))

# 验证 P 正定
eigvals_P = np.linalg.eigvalsh(P)
print(f"P 的特征值: {eigvals_P}")  # 应该全为正
# 用 V(theta) = theta^T P theta 作为 Lyapunov 函数

非线性系统：LaSalle 不变集原理¶

定理（LaSalle）：若 $V\ge 0$，$\dot V\le 0$（注意：只需要非正，不需要严格负），$M=\{x : \dot V(x)=0\}$ 的最大不变集是 $\{\theta^*\}$，则 $\theta\to\theta^*$。

常用于 Actor-Critic 的慢 ODE 不是严格下降（$\nabla J$ 可能为 0 但非最优）时——LaSalle 保证收敛到平稳点集。

RL 专属：Bellman 残差范数¶

对 Q-learning，$V(Q)=\|Q-Q^*\|_\infty$ 是 $\infty$-Lyapunov；对 TD(0)，$V(\theta)=\|V_\theta-V^\pi\|_{D^\pi}^2$ 是 $D^\pi$-范数 Lyapunov。选择范数比选择函数更难——Baird 反例的本质是"没有合适的范数能让 Bellman 算子在 off-policy 下变成压缩"。

本质洞察：在 SA 收敛性分析中，Lyapunov 函数的选择不是"随意的创造"，而是**由问题结构决定的**。线性系统用二次型（Lyapunov 方程给出）；压缩映射用不动点距离（范数给出）；Actor-Critic 用值函数差（策略梯度结构给出）。 找 Lyapunov 函数 = 找到问题的正确"度量衡"。

Lyapunov 函数选择的决策树 ⭐⭐⭐¶

面对一个新的 SA/ODE 稳定性问题，按以下决策树选择 Lyapunov 函数：

ODE 类型？
├── 线性 (dot_theta = F*theta, F Hurwitz)
│   └── 解 Lyapunov 方程 F^T P + P F + I = 0 --> V = theta^T P theta
│       (等价形式：若 ODE 写作 dot_theta = -A*theta 且 A 正定，
│        则 Lyapunov 方程为 A^T P + P A = I)
├── 算子是压缩映射 (dot_Q = TQ - Q)
│   └── V = ||Q - Q*||_norm （用压缩映射的范数）
├── 梯度流 (dot_theta = -grad J)
│   └── V = J(theta) - J* （目标函数本身）
├── 满足 PL (||grad J||^2 >= 2mu(J-J*))
│   └── V = J(theta) - J* （自动有指数衰减）
└── 一般非线性
    ├── 尝试 V = ||theta - theta*||^2 （如果有强单调性）
    ├── 尝试 LaSalle （如果只有弱单调性）
    └── 尝试 converse Lyapunov （稳定性已知，反构造 V）

交叉引用：关于 Lyapunov 方程的更多细节（求解方法、数值稳定性、与 Riccati 方程的关系），请参见本项目的 01_数学/40_控制理论/70_Lyapunov稳定性理论 §4 "线性系统的 Lyapunov 分析"。

练习（§6.5.E）¶

手推：对 2 维线性 ODE $\dot\theta = F\theta$，$F=\bigl(\begin{smallmatrix}-2&1\\0&-3\end{smallmatrix}\bigr)$，(a) 验证 $F$ Hurwitz（特征值 $-2,-3$，实部全负）；(b) 解 Lyapunov 方程 $F^\top P + PF + I = 0$（即 $F^\top P + PF = -I$，此处 ODE 右端为 $F\theta$，$F$ Hurwitz，故 RHS 取负号）；(c) 画出 $V(\theta) = \theta^\top P\theta$ 的等值线和 ODE 轨迹。

符号对照：此题 ODE 形式为 $\dot\theta=F\theta$（$F$ Hurwitz），与 §6.5.E 正文中 TD 的 ODE $\dot\theta=-A\theta$（$A$ 正定）等价——只需令 $F=-A$。两种 Lyapunov 方程分别为 $F^\top P+PF=-I$ 和 $A^\top P+PA=I$，本质相同。
编程：用 scipy.linalg.solve_continuous_lyapunov 对 TD(0) 的 $A$ 矩阵（5-state random walk）计算 $P$，然后在 SA 迭代中监控 $V(\theta_t) = (\theta_t-\theta^*)^\top P(\theta_t-\theta^*)$ 是否单调递减。
概念：为什么 Q-learning 不用二次 Lyapunov $V = \|Q-Q^*\|_2^2$ 而用 $\infty$-范数 $V = \|Q-Q^*\|_\infty$？（提示：$T^*$ 在哪个范数下是压缩的？）

§6.5.F Zap SA 与渐近最优性 ⭐⭐⭐⭐¶

思想：用 Newton 方向代替梯度¶

Robbins-Monro：$\theta_{t+1}=\theta_t+\alpha_t h(\theta_t,X_t)$——收敛速率 $O(1/\sqrt t)$（无 Polyak 平均时）。

Zap SA（Devraj-Meyn 2017）：$\theta_{t+1}=\theta_t-\alpha_t\hat A_t^{-1}h(\theta_t,X_t)$，其中 $\hat A_t$ 是 Jacobian $\nabla\bar h(\theta^*)$ 的第二时间尺度估计。矩阵增益让 SA 的局部动力学像 Newton 迭代，渐近方差达到 Cramer-Rao 下界。

跨领域类比：标准 SA 与 Zap SA 的关系，就像梯度下降与 Newton 法的关系。梯度下降沿 $-\nabla f$ 方向走，在条件数大的问题上进展缓慢（沿着"峡谷"来回震荡）。Newton 法用 Hessian 逆乘以梯度，$-H^{-1}\nabla f$，把"峡谷"变换成"碗"，大幅加速收敛。Zap SA 做的事情完全一样——用 Jacobian 逆把 SA 的"不对称漂移"变换成"对称漂移"，达到最优收敛速率。代价是需要估计并求逆一个 $d\times d$ 矩阵，在高维问题中计算量大。

Devraj-Meyn 2017 Zap-Q¶

Zap Q-learning：同时估计 Jacobian

\[A_t=\mathbb{E}[\partial_Q(r+\gamma\max_{a'}Q(s',a'))-\mathbb{1}]\]

的在线版本，用两时间尺度；主 Q 递推用 $-A_t^{-1}(T^*Q_t-Q_t)$。理论收敛速率是 Watkins Q-learning 的最优（Meyn 2022 第 11 章）。

与 RLS/LSTD 的联系¶

LSTD（Bradtke-Barto 1996）：$\theta=A^{-1}b$ 直接解方程，用样本估 $\hat A,\hat b$。Zap-TD 就是 LSTD 的二时间尺度版本。历史链条：RLS（1950s 系统辨识）--> LSTD（1996）--> Zap-Q（2017），Newton 型方法在 SA 的反复再发明。

工程现状¶

Zap SA 在机器人 RL 主流实现中**尚未普及**——工程师担心矩阵求逆的稳定性、内存开销（$O(d^2)$ 存储 $\hat A$）。但 Meyn 2022 论证：在中小参数维度（LQR、线性 MPC、tabular）下 Zap-Q 将训练时间缩短 1-2 个数量级。值得关注的前沿方向。

§6.5.G SA 与 SGD 的统一视角 ⭐⭐⭐¶

从 SA 到 Adam：统一框架¶

SA 是一个"大帐篷"，涵盖了几乎所有基于采样的迭代优化/方程求解方法。以下是统一谱系：

方法	$h(\theta, X)$	增益矩阵 $G_t$	特点
Robbins-Monro	$h(\theta, X)$（一般向量场）	$I$	最一般
SGD	$-\nabla\ell(\theta, X)$	$I$	$h$ 是梯度
SGD + Momentum	$-\nabla\ell(\theta, X) + \beta v_{t-1}$	$I$	加了惯性
RMSprop	$-\nabla\ell(\theta, X)$	$\mathrm{diag}(1/\sqrt{v_t+\epsilon})$	自适应标量增益
Adam	$-\nabla\ell(\theta, X)$	$\mathrm{diag}(\hat m_t / (\sqrt{\hat v_t}+\epsilon))$	Momentum + 自适应
Natural Gradient	$-F(\theta)^{-1}\nabla J(\theta)$	$F(\theta)^{-1}$	Fisher 信息矩阵增益
Zap SA	$h(\theta, X)$	$-\hat J^{-1}$	Jacobian 增益，渐近最优

所有这些方法都可以写成：

\[\theta_{t+1} = \theta_t + \alpha_t G_t h(\theta_t, X_t),\]

区别只在于增益矩阵 $G_t$ 的选择。$G_t = I$ 最简单但可能不是最优；$G_t = -J^{-1}$（Newton/Zap）渐近最优但计算昂贵；Adam 等自适应方法是介于两者之间的工程折衷。

Cramer-Rao 下界与信息几何 ⭐⭐⭐¶

为什么 Zap 的渐近方差是最优的？ 因为在估计理论中，任何无偏估计量的方差不低于 Cramer-Rao 下界 $I(\theta^*)^{-1}$（Fisher 信息矩阵的逆）。Zap SA 的增益矩阵 $G = -J^{-1}$ 恰好让渐近方差达到这个下界。

Natural Gradient 的信息几何解释：Amari 1998 的 natural gradient $-F(\theta)^{-1}\nabla J(\theta)$ 在策略空间的 Fisher-Rao 度量下是最速下降方向。这与 Zap SA 的最优性是同一个思想在不同空间的体现——Zap 在参数空间最优（Cramer-Rao），Natural Gradient 在分布空间最优（Fisher-Rao）。

从 SA 视角理解 Adam 优化器 ⭐⭐⭐¶

Adam（Kingma-Ba 2015）是深度学习中最流行的优化器，从 SA 视角看它做了什么？

\[m_t = \beta_1 m_{t-1} + (1-\beta_1)\nabla\ell(\theta_t, X_t), \quad v_t = \beta_2 v_{t-1} + (1-\beta_2)[\nabla\ell(\theta_t, X_t)]^2,$$ $$\theta_{t+1} = \theta_t - \alpha \frac{\hat m_t}{\sqrt{\hat v_t} + \epsilon}.\]

在 SA 框架下： - $m_t$ 是对梯度的 EMA 估计（一阶矩）——对应 Polyak 平均思想 - $v_t$ 是对梯度方差的 EMA 估计（二阶矩）——对应自适应步长 - $G_t = \mathrm{diag}(1/(\sqrt{\hat v_t}+\epsilon))$ 是**对角增益矩阵**

与 Zap SA 的关系：Zap 用完整的矩阵增益 $G = -J^{-1}$（$d\times d$ 矩阵逆），Adam 用对角近似 $G = \mathrm{diag}(\cdots)$。Adam 可以看成是"穷人版 Zap"——放弃了坐标间的耦合信息（非对角元素），换取 $O(d)$ 而非 $O(d^2)$ 的空间/时间复杂度。

Adam 不满足标准 SA 收敛条件：严格来说，Adam 的步长不满足 Robbins-Monro（它是常数 $\alpha$ 除以自适应分母），其收敛理论需要额外的假设（如 Reddi et al. 2018 的 AMSGrad 修正）。但实践中 Adam "就是好用"——这提醒我们：SA 收敛定理给出的是充分条件，不是必要条件。不满足定理条件不意味着一定发散，只是没有理论保证。

SA 谱系的历史演进¶

1951 Robbins-Monro     --> 最基本的 SA，步长 I（恒等增益）
  |
1956 Dvoretzky         --> 统一抽象框架
  |
1958 Kiefer-Wolfowitz  --> 有限差分梯度估计
  |
1977 Ljung             --> ODE 方法系统化
  |
1988 Polyak-Ruppert    --> 平均化加速，达到 Cramer-Rao 下界
  |
1990s SGD/Momentum     --> 深度学习时代的 SA
  |                    
  |--- 1994 Tsitsiklis --> 异步 SA + Q-learning
  |--- 1997 Borkar     --> 两时间尺度 SA + Actor-Critic
  |--- 2000 Borkar-Meyn --> 无先验有界性的 ODE 主力定理
  |
2012 Adam / RMSprop    --> 自适应对角增益（"穷人版 Zap"）
  |
2015 TRPO             --> 信任域（Fisher 矩阵近似增益）
  |
2017 Devraj-Meyn Zap  --> 完整 Jacobian 增益，渐近最优
  |
2018 Fazel et al.     --> PL + SA = 非凸全局收敛
  |
2019-now              --> 有限样本分析、分布式 SA、Markovian SA

这条线索揭示了一个大趋势：SA 方法从"学术玩具"到"工程主力"的演进，关键是增益矩阵 $G_t$ 的进化——从 $I$（Robbins-Monro）到对角自适应（Adam）到完整矩阵（Natural Gradient / Zap）。每一步都在"计算复杂度"和"统计效率"之间做 trade-off。

练习（§6.5.G）¶

概念：写出 SGD、SGD+Momentum、Adam、Natural Gradient 在 SA 框架 $\theta_{t+1} = \theta_t + \alpha_t G_t h(\theta_t, X_t)$ 下各自的 $h$ 和 $G_t$。
比较：对简单的二次目标 $J(\theta) = \frac{1}{2}\theta^\top H\theta$（$H$ 条件数 $\kappa = 100$），计算 SA（$G=I$）和 Zap（$G=-H^{-1}$）的收敛速率差异。
工程：在 PyTorch 中对同一个简单 RL 问题（CartPole）分别用 SGD、Adam、Natural Gradient（用 Fisher 矩阵的 Kronecker 近似 K-FAC），比较训练曲线。从 SA 增益矩阵的角度解释差异。

§6.5.H 发散诊断工程指南 ⭐⭐¶

这一节是本专题对机器人 RL 工程师**最直接有用**的部分。当你在 Isaac Lab / legged_gym / rl_games 中遇到训练发散时，按以下六维诊断框架排查：

六维诊断清单¶

维度	检查项	对应理论	排查方法
1. On/Off-policy	$A$ 矩阵是否正定？	TVR 1997 §6.5.4	检查算法是否使用 replay buffer；若是，检查 importance ratio 是否截断
2. 步长条件	学习率 schedule 是否合理？	Robbins-Monro §6.5.2	打印 lr 曲线；检查是否过早衰减或根本不衰减
3. 两时间尺度	critic lr > actor lr？	Borkar 1997 §6.5.A	检查配置文件中 critic/actor 的 lr 比值
4. 噪声方差	batch size 是否足够？梯度是否 clip？	(A3) 噪声方差条件	打印梯度范数；减小 lr 或增大 batch
5. 有界性	Q 值/advantage 是否爆炸？	(A4)/(S3) 有界性	打印 $\\|Q\\|_\infty$；加 state/reward normalization
6. 异步延迟	多 GPU 参数同步延迟？	Tsitsiklis 1994 §6.5.D	检查 NCCL 通信频率；降低 num_workers

具体诊断流程¶

症状 1：Reward 在训练前期上升，中期突然崩溃

可能原因：值函数估计爆炸（$\|Q\|$ 或 $\|V\|$ 增长到 $10^6$ 以上），advantage 估计失准，策略做出极端动作。

排查步骤： 1. 打印每个 epoch 的 value_loss 和 max(|V|) 2. 如果 max(|V|) 指数增长 --> 加 value clipping（PPO 的 clip_vloss=True）或 value normalization 3. 如果 value_loss 正常但 reward 崩溃 --> 检查 KL divergence，可能策略更新步长太大 --> 减小 clip_range 或加 KL penalty 4. 从 ODE 角度：$A$ 矩阵的条件数可能很大（某些方向收敛快，某些慢），导致"快方向"过冲

症状 2：Reward 从不上升，始终在初始水平附近波动

可能原因：学习率过小或 exploration 不足。

排查步骤： 1. 打印梯度范数，如果 $< 10^{-6}$ --> lr 太小 2. 检查 entropy bonus 是否开启 3. 从 SA 角度：$\sum\alpha_t$ 的有效值可能太小（等效于"探索能量不足"条件 $\sum\alpha < \infty$）

症状 3：Reward 缓慢上升但显著震荡

可能原因：常数步长的稳态方差过大。

排查步骤： 1. 尝试增大 batch size（降低方差 $\propto 1/B$） 2. 或者在训练后期线性降低 lr 3. 从 SDE 角度（§6.5.C）：稳态方差 $\propto \alpha$，减半 lr 减半方差

症状 4：Reward 前期正常，加入 domain randomization 后发散

可能原因：非平稳环境下递减步长衰减太快，算法无法跟踪变化的目标。

排查步骤： 1. 改用常数 lr 或 cosine schedule 2. 增大 dr 的 warmup 期 3. 从 SA 角度：非平稳 = $\theta^*$ 在移动，递减步长的"冻结"效应使迭代跟不上

完整的发散诊断代码模板 ⭐⭐¶

以下代码模板可以嵌入你的 RL 训练循环，实时监控 ODE 稳定性相关的诊断量：

import numpy as np
from collections import deque

class SADiagnostics:
    """随机逼近发散诊断工具

    基于 ODE 方法理论，监控六个关键维度：
    1. 参数有界性 (Borkar-Meyn A4)
    2. 梯度范数 (噪声方差控制)
    3. 值函数量级 (Q/V 爆炸检测)
    4. 两时间尺度比率 (Actor-Critic 平衡)
    5. 有效步长累积 (Robbins-Monro 条件)
    6. TD 误差方向 (A 矩阵正定性代理)
    """

    def __init__(self, window_size=100):
        self.grad_norms = deque(maxlen=window_size)
        self.param_norms = deque(maxlen=window_size)
        self.value_maxs = deque(maxlen=window_size)
        self.td_errors = deque(maxlen=window_size)
        self.critic_losses = deque(maxlen=window_size)
        self.actor_losses = deque(maxlen=window_size)

    def check(self, grad_norm, param_norm, value_max, td_error,
              critic_loss, actor_loss, critic_lr, actor_lr):
        """每步调用，返回诊断报告"""
        self.grad_norms.append(grad_norm)
        self.param_norms.append(param_norm)
        self.value_maxs.append(value_max)
        self.td_errors.append(td_error)
        self.critic_losses.append(critic_loss)
        self.actor_losses.append(actor_loss)

        warnings = []

        # 检查 1：参数爆炸（违反有界性 S3/A4）
        if len(self.param_norms) > 10:
            recent = list(self.param_norms)[-10:]
            if recent[-1] > 3 * recent[0] and recent[-1] > 100:
                warnings.append(
                    "PARAM_EXPLOSION: 参数范数指数增长。"
                    "可能原因：A矩阵不正定(off-policy)或步长过大。"
                    "建议：加gradient clipping或检查on/off-policy设置"
                )

        # 检查 2：值函数爆炸
        if value_max > 1e4:
            warnings.append(
                f"VALUE_EXPLOSION: |V|_max = {value_max:.1e} > 1e4。"
                "可能原因：reward scale过大或缺少value normalization。"
                "建议：加PopArt/value clipping或检查reward设计"
            )

        # 检查 3：两时间尺度违反
        if critic_lr < actor_lr:
            warnings.append(
                f"TIMESCALE_VIOLATION: critic_lr={critic_lr:.1e} < "
                f"actor_lr={actor_lr:.1e}。"
                "理论要求 critic 比 actor 快（Borkar 1997）。"
                "建议：设 critic_lr >= 2 * actor_lr"
            )

        # 检查 4：梯度范数异常
        if grad_norm > 100:
            warnings.append(
                f"GRAD_EXPLOSION: ||grad|| = {grad_norm:.1e}。"
                "可能原因：步长过大或函数近似不稳定。"
                "建议：加max_grad_norm=0.5的gradient clipping"
            )

        return warnings

A 矩阵特征值的近似在线检查 ⭐⭐⭐¶

对线性 TD(0)，$A$ 矩阵可以从采样数据在线估计：

\[\hat A_t = \frac{1}{t}\sum_{s=1}^t \phi(S_s)[\phi(S_s) - \gamma\phi(S_{s+1})]^\top.\]

每隔一定步数（如每 1000 步），计算 $\hat A_t$ 的特征值：

# 在线估计 A 矩阵（线性 TD 诊断）
# phi_buffer: (T, d) 特征矩阵
# phi_next_buffer: (T, d) 下一状态特征矩阵
A_hat = (phi_buffer.T @ (phi_buffer - gamma * phi_next_buffer)) / T
eigvals = np.linalg.eigvals(A_hat)
min_real_part = np.min(np.real(eigvals))

if min_real_part < 0:
    print(f"WARNING: A矩阵有负实部特征值 {min_real_part:.4f}")
    print("TD(0) 在当前采样分布下可能发散！")
    print("建议：检查 on/off-policy 比率，或切换到 GTD/TDC")

注意：这个诊断只对线性函数近似有效。对 NN 函数近似，可以用 Jacobian 的谱作为近似代理（通过 torch.autograd.functional.jacobian），但计算代价高昂，通常只在调试时使用。

⚠️ 常见陷阱（§6.5.H）¶

🧠 思维陷阱：遇到训练发散就盲目降低学习率

新手做法：reward 崩了 --> 把 lr 从 3e-4 降到 1e-5 --> 再跑。

实际上：降低 lr 只治标不治本。如果发散原因是 off-policy bias（$A$ 不正定），降低 lr 只是延缓了发散（$\theta_t$ 走得更慢，但方向还是错的）。如果原因是值函数爆炸，降低 lr 可能帮不上忙——因为即使每步更新很小，只要方向不对，积累起来还是会爆。正确做法是先诊断根因，再对症下药。

💡 概念误区：把"梯度爆炸"和"SA 发散"混为一谈

新手想法："梯度很大 = 发散。"

实际上：梯度大可能是正常的（初期远离目标时梯度自然大），也可能是问题的征兆。关键区分是**方向**而非**大小**：如果梯度大但方向正确（指向 $\theta^*$），那只是收敛前期的正常现象；如果方向错误（$A$ 不正定），那再小的梯度也会累积发散。正确的监控量不是 $\|g\|$ 本身，而是 $g^\top(\theta - \theta^*)$ 的符号——正号意味着在远离目标。

练习（§6.5.H）¶

工程实操：在你的 RL 训练代码中加入上述 SADiagnostics 类，记录一次完整训练过程中的六维诊断量。绘制这些量随训练步数的变化曲线。
发散复现：故意制造一次发散（如把 critic lr 设为 actor lr 的 1/10，或关闭 gradient clipping），用诊断工具定位根因。
跨章综合（需 6.3 Baird 反例 + 本章）：对 Baird 反例，用诊断代码中的 $\hat A$ 估计方法，在线打印特征值，观察负实部特征值的出现。

§6.5.I Fazel 2018 全局收敛的完整证明工具 ⭐⭐⭐⭐¶

PL（梯度支配）条件回顾（6.4 内容）¶

回顾 6.4：PL 不等式：存在 $\mu>0$，$\|\nabla J(\theta)\|^2\ge 2\mu(J(\theta)-J^*)$。

PL 条件的直觉：它说"梯度的大小控制了次优性"——如果你离最优还很远（$J(\theta)-J^*$ 大），那梯度必须足够大（$\|\nabla J\|$ 大）。这保证了梯度下降不会在远离最优处"卡住"（梯度为零但不是最优点）。

注意：PL 条件比凸性弱得多——非凸函数也可以满足 PL。LQR 的 cost $J(K)$ 就是典型例子：它关于增益矩阵 $K$ 是非凸的（因为 $J(K)$ 涉及 Riccati 方程的解），但满足 PL。

Fazel 2018 对 LQR 的证明（ICML 2018）¶

定理（Fazel et al. 2018）：LQR 的 cost $J(K)$（作为策略增益 $K$ 的函数）非凸，但在稳定区域满足 PL 条件。因此**梯度流** $\dot K = -\nabla J(K)$ 全局收敛到 $K^*$。

SA + PL = 全局线性收敛 ⭐⭐⭐⭐¶

把 Fazel 的梯度流视为 SA 的平均 ODE：

定理（现代综合）：若 $\bar h = -\nabla J$ 且 $J$ 满足 PL，Robbins-Monro 步长 + 鞅差噪声 $\Rightarrow$ $J(\theta_t) - J^* \to 0$，且期望速率 $\mathbb{E}[J(\theta_t)-J^*] \le \exp(-2\mu\sum_s\alpha_s)(\cdots) + \text{噪声项}$。

Lyapunov：$V(\theta)=J(\theta)-J^*$，由 PL $\dot V=-\|\nabla J\|^2\le-2\mu V\Rightarrow$ 指数收敛。这就是 6.4 提到的"PL 条件 + ODE 方法 = 非凸 RL 全局收敛"的完整数学骨架。

PL 条件为什么对 LQR 成立？直觉解释¶

LQR 问题：$\min_K J(K) = \mathbb{E}[\sum_{t=0}^\infty x_t^\top Q x_t + u_t^\top R u_t]$，$u_t = -Kx_t$，$x_{t+1} = Ax_t + Bu_t$。

$J(K)$ 关于 $K$ 是非凸的——但为什么满足 PL？直觉如下：

唯一全局最小值：在稳定增益集合 $\{K : A-BK \text{ stable}\}$ 中，$J(K)$ 有唯一最小值 $K^* = R^{-1}B^\top P^*$（$P^*$ 解 ARE）。
无局部最小值：$J(K)$ 没有"陷阱"——任何满足 $\nabla J(K)=0$ 的 $K$ 都必须是 $K^*$。这是因为 $\nabla J(K) = 0$ 等价于 ARE 的必要条件，而 ARE 在稳定区域只有唯一解。
梯度与次优性的量化关系：Fazel 2018 证明了 $\|\nabla J(K)\|_F^2 \ge 2\mu(J(K)-J^*)$，其中 $\mu$ 依赖于 $Q, R, A, B$ 的条件数。这意味着**远离最优时梯度必须足够大**——不存在"梯度小但离最优远"的情况。

为什么 PL 不等于凸性？ 考虑一维类比：$f(x) = x^2$ 是凸的且满足 PL；$f(x) = x^4$ 是凸的但不满足 PL（在 $x=0$ 附近 $f'(x) = 4x^3$ 可以任意小而 $f(x)-f^* = x^4$ 不那么小）；$f(x) = x^2(2+\sin(1/x))$（适当光滑化）可以是非凸的但满足 PL。PL 条件关心的是"梯度大小与函数值差距的关系"，与凸性（Hessian 半正定）是正交的概念。

Fazel 定理对机器人控制 RL 的意义¶

直接应用场景：四足机器人站立平衡（线性化后是 LQR 问题）的 model-free policy gradient 训练——Fazel 定理保证了即使不知道动力学模型 $(A, B)$，只要能评估 $J(K)$（在仿真中跑一条轨迹即可），policy gradient 就能找到最优 $K^*$。

推广到非线性系统：Fazel 2018 之后，一系列工作（Malik et al. 2019, Mohammadi et al. 2021）把 PL 条件推广到 robust LQR、LQG、混合系统。对四足 locomotion 中 MPC 内层的 LQR 子问题，这些理论直接适用。

局限性：PL 条件对全连接 NN 策略（PPO 中常见）不成立——NN 的 loss landscape 有鞍点和局部极小。这就是为什么 PPO/SAC 的收敛性没有完整的理论保证——它们在实践中工作良好，但理论上我们只能说"大概率收敛到某个临界点"。

练习（§6.5.I）¶

手推：对一维 LQR $J(k) = \sum_{t=0}^\infty (x_t^2 + k^2 x_t^2)$，$x_{t+1} = (a-bk)x_t$，$x_0=1$。写出 $J(k)$ 的解析表达式，验证它在稳定区域 $|a-bk|<1$ 内满足 PL 条件。
概念：为什么 Fazel 定理不能直接推广到 NN 策略？从 PL 条件出发说明障碍在哪里。
跨章综合（需 6.4 + 本章）：梳理 Fazel 2018 的完整证明逻辑链：(a) 证 $J(K)$ 满足 PL；(b) 由 PL 得梯度流全局收敛；(c) 由 ODE 方法得 stochastic PG 也收敛。标明每步用到了哪个定理。

§6.5.J 收敛速率的完整比较与工程选择 ⭐⭐⭐¶

本节汇总所有 SA 变体的收敛速率，给出实用的工程选择指南。

渐近收敛速率比较表¶

方法	渐近方差 $\mathrm{Var}(\theta_t) \cdot t$	是否最优	计算复杂度/步	适用场景
标准 SA ($G=I$, $\alpha=c/t$)	$c^2 \sigma^2 / (2ca-1)$（依赖 $c$ 选择）	否	$O(d)$	简单问题
Polyak-Ruppert 平均	$\Sigma^* = J^{-1}S J^{-\top}$（Cramer-Rao）	是	$O(d)$	平稳目标
LSTD（直接解 $\hat A^{-1}\hat b$）	与 Polyak 相同	是	$O(d^2)$	中小维度
Zap SA ($G=-\hat J^{-1}$)	$\Sigma^*$（Cramer-Rao）	是	$O(d^2)$	中小维度
常数步长 SA ($\alpha$ 固定)	$\alpha\sigma^2/(2\mu)$（稳态偏差）	N/A	$O(d)$	非平稳环境

工程决策指南：

你的问题是什么？
├── 平稳目标 + 小维度 (d < 100)
│   └── 用 LSTD 或 Zap SA（达到最优速率）
├── 平稳目标 + 中维度 (100 < d < 10000)
│   └── 用标准 SA + Polyak-Ruppert 平均
├── 非平稳目标（RL 训练）
│   └── 用常数步长 + EMA / target network
└── 高维度 (d > 10000, NN 参数)
    └── 用 Adam / RMSprop（自适应对角增益）

有限样本复杂度的统一公式¶

对常数步长 $\alpha$ 的线性 SA $\theta_{t+1} = \theta_t + \alpha(-A\theta_t + b + M_{t+1})$，Srikant-Ying 2019 给出：

\[\mathbb{E}\|\theta_T - \theta^*\|^2 \le \underbrace{(1-2\mu\alpha)^T \|\theta_0-\theta^*\|^2}_{\text{初始误差衰减}} + \underbrace{\frac{\alpha\sigma^2}{2\mu}}_{\text{稳态偏差}}.\]

其中 $\mu = \lambda_{\min}(A+A^\top)/2 > 0$（TD(0) 中这就是 $(1-\gamma)$），$\sigma^2 = \mathrm{tr}(\mathrm{Cov}(M))$。

解读： - 第一项指数衰减，半衰时间 $T_{1/2} \approx 1/(2\mu\alpha)$ - 第二项是由于常数步长不衰减导致的"最终偏差" - 最优 $\alpha$：给定 $T$ 步预算，最小化总误差 --> $\alpha^* \approx \frac{1}{\mu T}\log(\mu T \|\theta_0\|^2/\sigma^2)$

对 RL 工程师，这个公式的直接价值是**训练预算估计**：给定目标精度 $\epsilon$，需要多少步？

\[T \ge \frac{1}{2\mu\alpha}\log\frac{\|\theta_0-\theta^*\|^2}{\epsilon} + \frac{\sigma^2}{2\mu\epsilon}.\]

在 Isaac Lab 的 PPO 训练中，$\mu \approx 0.01$（$(1-\gamma)$ 级别），$\alpha = 3\times10^{-4}$，$\sigma^2$ 可从梯度方差估计。这给出了"训练多少步才够"的理论参考。

练习（§6.5.J）¶

计算：对 5-state random walk，$\gamma=0.9$（故 $\mu \approx 0.1$），$\alpha=10^{-3}$，初始误差 $\|\theta_0-\theta^*\|^2 \approx 1$，噪声方差 $\sigma^2 \approx 1$。计算达到 $\epsilon = 0.01$ 精度需要多少步。
工程：在你的 PPO 训练中，从前 1000 步的数据估计 $\mu$ 和 $\sigma^2$（通过观察 value loss 的衰减速率和梯度方差），用上述公式预测总训练步数，与实际对比。

综合练习 ⭐⭐⭐¶

以下练习要求综合运用本章多个小节的知识，适合作为 qualifying exam 或 reading group 的讨论题。

练习 1（ODE 稳定性与 TD 收敛的完整链条）

考虑 3 状态 Markov 链（状态 $\{1,2,3\}$），策略 $\pi$ 下的转移矩阵 $P^\pi=\bigl(\begin{smallmatrix}0&0.5&0.5\\0.3&0&0.7\\0.6&0.4&0\end{smallmatrix}\bigr)$，折扣 $\gamma=0.9$，特征矩阵 $\Phi=\bigl(\begin{smallmatrix}1&0\\0&1\\1&1\end{smallmatrix}\bigr)$。

(a) 计算稳态分布 $d^\pi$，构造 $D^\pi=\mathrm{diag}(d^\pi)$。

(b) 计算 $A = \Phi^\top D^\pi(I-\gamma P^\pi)\Phi$。验证 $A+A^\top\succ 0$（提示：计算特征值）。

(c) 写出对应的平均 ODE $\dot\theta = -A\theta + b$（给定 $r=(1,0,-1)^\top$，计算 $b=\Phi^\top D^\pi r$）。求不动点 $\theta^*=A^{-1}b$。

(d) 解 Lyapunov 方程 $A^\top P + PA = I$ 并验证 $P\succ 0$。物理解释：$V(\theta)=(\theta-\theta^*)^\top P(\theta-\theta^*)$ 为什么沿 TD ODE 轨迹单调递减？

(e) 若将采样改为均匀分布 $d_{\mathrm{unif}}=(1/3,1/3,1/3)$（off-policy），重新计算 $A_{\mathrm{off}}=\Phi^\top D_{\mathrm{unif}}(I-\gamma P^\pi)\Phi$。$A_{\mathrm{off}}+A_{\mathrm{off}}^\top$ 是否仍正定？讨论。

练习 2（两时间尺度 Actor-Critic 的分离条件）

在 Actor-Critic 中，actor 用步长 $\alpha_t = c_1/(t+1)^{0.6}$，critic 用 $\beta_t = c_2/(t+1)^{0.8}$。

(a) 验证 $\alpha_t/\beta_t \to 0$（快/慢分离成立）。

(b) 验证 $(\alpha_t,\beta_t)$ 都满足 Robbins-Monro 条件。

(c) 若将步长改为 $\alpha_t = 10^{-4}$（常数）和 $\beta_t = 10^{-3}$（常数），两时间尺度分离条件是否满足？此时 Borkar 1997 定理还适用吗？讨论实践中常数步长 Actor-Critic 的收敛性保证（提示：参考 §6.5.A 的"工程近似"讨论）。

(d) 在 Isaac Lab PPO 中，默认 actor lr = critic lr = $3\times 10^{-4}$（相同）。解释为什么这在实践中仍然有效（提示：PPO 不是严格的两时间尺度 AC，它用 truncated rollout + 多 epoch 更新来分离评估与改进）。

练习 3（Polyak-Ruppert 平均的渐近最优性验证）

考虑一维 SA：$\theta_{t+1} = \theta_t + \alpha_t(-2\theta_t + \varepsilon_t)$，其中 $\varepsilon_t\sim\mathcal{N}(0,4)$ i.i.d.，$\alpha_t = 1/t^{0.7}$。

(a) 写出平均 ODE：$\dot\theta = -2\theta$。不动点 $\theta^*=0$。Jacobian $J=-2$。

(b) 计算噪声协方差 $S = \mathrm{Var}(\varepsilon) = 4$。

(c) 由 Polyak-Ruppert 定理，$\bar\theta_T = \frac{1}{T}\sum_{t=1}^T\theta_t$ 满足 $\sqrt{T}\bar\theta_T \xrightarrow{d} \mathcal{N}(0,\Sigma^*)$，其中 $\Sigma^* = J^{-1}S(J^{-1})^\top = (-2)^{-1}\cdot 4\cdot(-2)^{-1} = 1$。

(d) 用 Python 模拟 $T=10^5$ 步，计算 $\bar\theta_T$ 的经验方差（重复 1000 次），验证是否接近 $\Sigma^*/T = 10^{-5}$。

(e) 与不做平均的 $\theta_T$ 的方差对比。Polyak 平均加速了多少倍？

练习 4（常数步长 SA 的稳态分析与偏差-方差权衡）

常数步长 $\alpha$ 的 TD(0)（线性函数近似）不在点意义上收敛，而是收敛到围绕 $\theta^*$ 的稳态分布。

(a) 由 Srikant-Ying 2019 的有限样本界：$\mathbb{E}\|\theta_T - \theta^*\|^2 \le (1-2\mu\alpha)^T\|\theta_0-\theta^*\|^2 + \frac{\alpha\sigma^2}{2\mu}$。解释两项的物理含义（bias 指数衰减 + variance 稳态 floor）。

(b) 若要在 $T$ 步后达到总误差 $\le \epsilon$，推导 $\alpha$ 的最优选择（对 $\alpha$ 求最小化总界）。答案应形如 $\alpha^* = O(\log(T)/(\mu T))$。

(c) 讨论：在 PPO 训练中，为什么通常使用"warmup + cosine decay"而非纯常数步长？从 SA 理论的角度解释。

(d) 对 $\mu=0.1, \sigma^2=1, T=10^4$，数值计算最优 $\alpha^*$ 和对应的终态误差界。

练习 5（Baird 反例的完整 ODE 诊断）

Baird 的 7-star 反例（Sutton-Barto 第 2 版 §11.2）：7 个状态，off-policy behavior policy 均匀随机选，target policy 确定性选状态 7。

(a) 写出此 MDP 的 $P^\pi$（$7\times 7$ 矩阵，target policy 下所有状态转移到状态 7）和 off-policy 采样分布 $d^\mu=(\frac{1}{7},\ldots,\frac{1}{7})$。

(b) 构造 $A_{\mathrm{off}} = \Phi^\top D_\mu(I - \gamma P^\pi)\Phi$（$\Phi$ 的具体形式见 Sutton-Barto 原文）。

(c) 计算 $A_{\mathrm{off}}$ 的特征值。验证至少存在一个特征值的实部为负。

(d) 由此解释为什么 off-policy TD 在此例中必然发散（ODE $\dot\theta = -A_{\mathrm{off}}\theta+b$ 不稳定）。

(e) 若改为 on-policy 采样（$d^\pi$ = target policy 的稳态分布 = $(0,\ldots,0,1)$），重新计算 $A_{\mathrm{on}}$。是否正定？解释为什么 on-policy 保证了稳定性。

本章常见误解汇总¶

误解	正确理解
"Robbins-Monro 步长条件 $\sum\alpha=\infty, \sum\alpha^2<\infty$ 只是技术假设"	这两个条件有清晰的物理含义。$\sum\alpha=\infty$ 保证步长"够大"——算法有能力从任何初始点走到最优解（如果步长总和有限，算法走不远就停下了）。$\sum\alpha^2<\infty$ 保证噪声的累积效应有限——如果步长衰减不够快，噪声的方差累积会让迭代永远震荡。两者缺一不可
"ODE 方法只是把离散算法近似成连续系统，精度不够"	ODE 方法不是近似——它是严格的。Borkar-Meyn 定理证明了：如果关联 ODE $\dot\theta = h(\theta)$ 的全局吸引子是 $\theta^$，那么 SA 迭代 $\theta_{t+1} = \theta_t + \alpha_t[h(\theta_t) + M_t + \beta_t]$ 在适当条件下几乎必然收敛到 $\theta^$。连续化不损失信息，反而让分析工具（Lyapunov 函数、相平面）变得可用
"两时间尺度只是让一个更新跑快一点、另一个慢一点"	两时间尺度的本质是奇异摄动（singular perturbation）。快时间尺度的变量在慢时间尺度看来是"瞬时平衡"的——它已经跟踪到了慢变量当前值对应的不动点。这不是"快一点慢一点"的程度问题，而是时间尺度分离后的质变：慢变量看到的是一个确定性系统（快变量的不动点映射），而非随机系统
"实践中用 Adam 优化器，不满足 R-M 条件，所以收敛理论没用"	Adam 的自适应步长确实不满足经典 R-M 条件，但有两点值得注意：(1) Adam 可以看作一种隐式的步长调度，在每个坐标方向上自适应地满足"步长够大但不太大"的精神；(2) RL 的实际训练往往不是收敛到不动点，而是在不动点附近的邻域内振荡（常数步长 SA 的行为）。理论框架仍然指导着超参选择的方向
"TD(0) 的 ODE 收敛证明只适用于线性函数逼近"	正确。ODE 方法的核心在于证明 $A = \Phi^\top D^\pi(I-\gamma P^\pi)\Phi$ 正定。线性 FA 下 $A$ 是常数矩阵，可以直接分析特征值。非线性 FA（深度网络）下 $A$ 变成了依赖 $\theta$ 的非线性映射，ODE 变成非线性系统，全局稳定性分析困难得多。这也是深度 RL 缺乏收敛保证的根本原因

本章小结¶

主题	核心定理/方法	关键条件	RL 应用
Robbins-Monro	SA 收敛定理	$\sum\alpha=\infty$, $\sum\alpha^2<\infty$, Lyapunov 条件	所有 RL 算法的祖先
ODE 方法	Borkar-Meyn 2000	(A1)-(A4), 缩放 ODE 稳定	SA --> ODE 稳定性的桥梁
TD(0) 收敛	TVR 1997	$A+A^\top\succ 0$（on-policy 保证）	线性 TD 的完整 ODE 证明
Q-learning 收敛	Tsitsiklis 1994	每坐标无限访问 + $\gamma$-压缩	异步 SA 框架
Polyak-Ruppert	平均化加速	$\beta\in(1/2,1)$	达到 Cramer-Rao 下界
两时间尺度	Borkar 1997	$\alpha/\beta\to 0$ + 快/慢 ODE 稳定	Actor-Critic / GTD
Zap SA	Devraj-Meyn 2017	Jacobian 估计	渐近最优速率
PL 全局收敛	Fazel 2018	PL 条件	非凸 RL（LQR）全局收敛

累积项目：本章新增模块¶

SA 实验平台（基于 NumPy）：

本章在累积项目中新增以下模块：

tabular TD(0) + ODE 追踪可视化：实现 5-state random walk，用 scipy.integrate.odeint 解平均 ODE $\dot\theta = -A\theta + b$，叠加 SA 样本轨迹与 ODE 曲线，直观验证 Borkar 追踪定理
Baird 反例复现 + $A$ 矩阵诊断：实现 Baird 7-star 反例，打印 $A$ 的特征值，可视化发散轨迹
步长条件实验：对同一问题用 $\alpha=c/t$、$\alpha=c/t^{0.7}$、$\alpha=c/\sqrt{t}$、$\alpha=c$（常数）四种步长运行，对比收敛/发散/震荡行为
两时间尺度 Actor-Critic：在简单 MDP 上实现两时间尺度 AC，做 critic/actor lr 比值 ablation

# 项目骨架：SA 实验平台
import numpy as np
from scipy.integrate import odeint
import matplotlib.pyplot as plt

class SAExperiment:
    """SA 实验基类"""
    def __init__(self, h_func, dim, theta_star):
        self.h = h_func       # h(theta, x) -> 更新方向
        self.dim = dim         # 参数维度
        self.theta_star = theta_star  # 目标不动点

    def run_sa(self, alpha_schedule, n_steps, noise_std=1.0):
        """运行 SA 迭代并返回轨迹"""
        theta = np.zeros(self.dim)  # 初始化
        trajectory = [theta.copy()]
        for t in range(1, n_steps + 1):
            alpha = alpha_schedule(t)
            noise = noise_std * np.random.randn(self.dim)
            theta = theta + alpha * (self.h(theta) + noise)
            trajectory.append(theta.copy())
        return np.array(trajectory)

    def solve_ode(self, t_span, theta0=None):
        """求解平均 ODE"""
        if theta0 is None:
            theta0 = np.zeros(self.dim)
        t = np.linspace(0, t_span, 1000)
        sol = odeint(lambda th, t: self.h(th), theta0, t)
        return t, sol

延伸阅读¶

资源	难度	阅读建议
Borkar 2008 Stochastic Approximation: A Dynamical Systems Viewpoint (Cambridge)	⭐⭐⭐	本专题主教材，176 页薄而精，第 2、3、6、7 章必读
Meyn 2022 Control Systems and Reinforcement Learning (Cambridge)	⭐⭐⭐	最现代主教材，免费 PDF，第 4、8、11 章直接对应本专题
Kushner-Yin 2003 Stochastic Approximation and Recursive Algorithms 2nd ed (Springer)	⭐⭐⭐⭐	百科全书风格参考书，查具体定理用
Benveniste-Metivier-Priouret 1990 Adaptive Algorithms and Stochastic Approximations (Springer)	⭐⭐⭐⭐	经典，读第 2 章 Markov 噪声处理
Bertsekas & Tsitsiklis 1996 Neuro-Dynamic Programming (Athena Scientific)	⭐⭐⭐	RL 数学"圣经"，第 4-6 章为本专题历史起点
赵世钰 Mathematical Foundations of Reinforcement Learning	⭐⭐	中英文双版本，直接讲 SA/ODE/收敛证明，中文替代首选
Bhandari-Russo-Singal 2018 "Finite Time Analysis of TD" (COLT)	⭐⭐⭐⭐	有限样本分析的现代里程碑
Srikant-Ying 2019 "Finite-Time Error Bounds for Linear SA" (COLT)	⭐⭐⭐⭐	常数步长 TD 精细界

🔧 故障排查手册¶

症状	可能原因	排查步骤	相关章节
TD 参数 $\theta_t$ 发散到 $\pm\infty$	Off-policy 采样导致 $A$ 矩阵不正定	1. 打印 $A$ 的特征值 2. 检查 behavior/target policy 差异 3. 切换到 GTD/TDC	§6.5.4, 6.3
Q-learning reward 不涨	$\varepsilon$-greedy 的 $\varepsilon$ 过小导致覆盖不足	1. 打印每个 $(s,a)$ 的访问次数 2. 增大 $\varepsilon$ 3. 检查 replay buffer 是否过小	§6.5.5
Actor-Critic 训练震荡	Critic/Actor lr 比值不当	1. 确认 critic lr > actor lr 2. 增加 critic 更新次数 3. 打印 value loss 曲线	§6.5.A
PPO reward 前期上升后崩溃	值函数估计爆炸	1. 打印 `max(\\|V\\|)` 2. 开启 value clipping 3. 加 state/reward normalization	§6.5.H
分布式训练不收敛	参数延迟过大	1. 检查 NCCL 同步频率 2. 降低 num_workers 3. 加 V-trace 校正	§6.5.D

核心教材深度对照¶

教材	覆盖重点	档位	读法建议
Borkar 2008 Stochastic Approximation: A Dynamical Systems Viewpoint (Cambridge / Hindustan)	第 2 章基本收敛、第 3 章稳定性、第 6 章两时间尺度、第 7 章异步	3-4	本专题主教材，176 页薄而精，适合两周啃完第 2、3、6、7 章
Kushner-Yin 2003 Stochastic Approximation and Recursive Algorithms and Applications 2nd ed (Springer)	全面但百科全书风格，ODE 方法、约束 SA、分布式 SA	4	参考书，不推荐通读；查具体定理用
Benveniste-Metivier-Priouret 1990 Adaptive Algorithms and Stochastic Approximations (Springer)	自适应控制/信号处理背景，Poisson 方程处理 Markov 噪声极为严格	4	经典，读第 2 章 Markov 噪声处理
Meyn 2022 Control Systems and Reinforcement Learning (Cambridge)	控制视角的 RL，Zap-Q、收敛速率设计	3-4	最现代主教材，免费 pre-pub PDF，第 4、8、11 章与本专题直接对应
Bertsekas & Tsitsiklis (1996) Neuro-Dynamic Programming (Athena Scientific)	RL 数学的"圣经"，TD、Q-learning、Actor-Critic 的经典收敛证明	3-4	第 4-6 章为本专题的历史起点，定理陈述经典

关键定理清单¶

定理	年份	陈述位置	本专题用途
Robbins-Monro	1951	Ann. Math. Stat. 22(3):400-407	SA 鼻祖，步长条件来源
Dvoretzky	1956	Proc. 3rd Berkeley Symp.	统一 SA 收敛框架
Doob supermartingale 收敛	1953	Doob Stochastic Processes	所有 SA 证明的核心鞅工具
Ljung ODE 方法	1977	IEEE TAC 22(4):551-575	ODE 方法系统化奠基
Polyak-Ruppert 平均	1988/1990	SIAM J. Control Optim.	渐近最优收敛速率
Tsitsiklis 1994 异步 SA	1994	Machine Learning 16(3):185-202	Q-learning 收敛直接来源
Tsitsiklis-Van Roy 1997	1997	IEEE TAC 42(5):674-690	线性 TD 收敛 + Baird 反例反向解释
Borkar 1997 两时间尺度	1997	Syst. Control Lett. 29(5):291-294	Actor-Critic / GTD 收敛基础
Borkar-Meyn ODE	2000	SIAM J. Ctrl. Optim. 38(2):447-469	现代 SA 主力定理
Konda-Tsitsiklis	2003	SIAM J. Ctrl. Optim. 42(4):1143-1166	Actor-Critic 严格收敛
Devraj-Meyn Zap-Q	2017	NeurIPS 2017 / arXiv 1707.03770	渐近最优 SA
Fazel et al. LQR PG	2018	ICML 2018 / arXiv 1801.05039	PL + SA = 非凸 RL 全局收敛

C++/Python 库 / 实验对照¶

本专题虽纯理论，但有明确的工程对照：

NumPy 手写 tabular TD(0)/Q-learning：实现一个 5-state random walk（Sutton-Barto §6.2），用递减步长 $\alpha_t=1/t^{0.7}$ 跑 TD(0)，用 matplotlib 画 $\theta_t$ 轨迹；同时用 scipy.integrate.odeint 解 $\dot\theta=-A\theta+b$ 画 ODE 曲线。叠加可视化可以直观看到 SA 折线"追踪" ODE 解——这是 Borkar 定理的实验验证。
Baird 反例复现：同上但用 off-policy 采样（behavior policy $\neq$ target policy），观察 $\theta_t$ 发散，打印 $A$ 的特征值可见实部有负值。直接对应 §6.5.4 的数学解释。
scipy.integrate.odeint / solve_ivp：解平均 ODE 的首选工具，在教学中把"ODE 解"与"SA 样本轨迹"叠画。
CleanRL（vwxyzjn/cleanrl）：每个算法单文件实现，其 PPO 的 learning_rate = linear_schedule(2.5e-4) 是工程上对 Robbins-Monro 的近似（线性下降到 0）；DQN 默认常数 lr 对应"常数步长 SA + stationary distribution"范式。
stable-baselines3：默认 constant lr，可以传入 callable 实现 schedule。
rl_games（Denys88/rl_games）/ Isaac Lab：PPO 实现中 config.learning_rate 通常为 $3\times 10^{-4}$ 常数，critic lr 大于 actor lr（典型 $5\times 10^{-4}$ vs $3\times 10^{-4}$）——两时间尺度的工程映射。
legged_gym：ANYmal / Cassie 训练脚本默认用 AdaptiveLR（基于 KL-divergence 自适应降 lr），本质上是对 PL/SA 动力学的启发式控制。
JAX / PyTorch autograd：actor-critic 中 critic 梯度 $\nabla_w(y-Q_w)^2=-2(y-Q_w)\nabla_w Q_w$（停 $y$ 梯度）就是 "semi-gradient"——由 autograd 的 stop_gradient/detach() 实现，这直接对应 §6.5.1 中"TD 不是真梯度"的数学事实。

工程深层理解：为什么真实 PPO/SAC 几乎从不用 Robbins-Monro 递减步长？ 1. 非平稳环境（reward shaping、domain randomization）下 $\theta^*$ 本身在漂移，递减步长会"冻结"在过时目标上； 2. 常数步长下的稳态分布方差 $\propto\alpha$ 可控，工程师可接受 $O(\alpha)$ bias 换取跟踪速度； 3. 大 batch 并行采样（Isaac 的 4096 env）已经隐式平滑了噪声，不再需要 $\alpha\to 0$ 来淹没噪声。

与控制理论的映射¶

本专题是 RL 与控制理论交汇最深的地方：

SA 与自适应控制 (adaptive control)：Astrom & Wittenmark 1973 的自适应 LQR、Landau 1974 的模型参考自适应控制 (MRAC)，其 parameter adaptation law 本身就是 SA。**Ljung 1977 ODE 方法的直接动机**即分析 Astrom 的 self-tuning regulator。Borkar 1997/2008 是 Ljung 思想的现代概率化版本。
ODE 稳定性与 Lyapunov 直接法：本专题的 TD 证明中 $A^\top P+PA=I$（ODE 为 $\dot\theta=-A\theta$，$A$ 正定）就是控制理论教科书里 Lyapunov 方程的标准配方。等价地，若将 ODE 写为 $\dot\theta=F\theta$（$F=-A$ Hurwitz），则方程为 $F^\top P+PF=-I$。两种写法本质相同，仅记号约定不同。RL 工程师可以直接读 Khalil Nonlinear Systems 第 4、9 章，或本项目的 01_数学/40_控制理论/70_Lyapunov稳定性理论。
两时间尺度与 singular perturbation theory：Kokotovic 1984 的 $\epsilon$-奇异摄动框架

\[\dot x=f(x,z),\;\epsilon\dot z=g(x,z)\]

的极限 $\epsilon\to 0$（"快-慢系统"），Tikhonov 定理给快子系统的拟静态近似 $z\approx\lambda(x)$——与 Borkar 1997 的证明是同一思想的连续时间版。

Zap SA 与 Newton-type system ID：Ljung-Soderstrom 1983 的递推最大似然辨识、扩展最小二乘 (ELS) 都是 Newton 类型的递推。Zap-Q 把这套带回 RL。
SA 与 simulated annealing / stochastic optimization：退火步长 $\alpha_t=c/\log t$ 满足 Robbins-Monro 但发散更慢——在非凸 RL (e.g. 多模态 reward) 中被偶尔使用。

统一图景：Lyapunov 函数构造 = 控制稳定性证明 = SA 收敛性证明 = 最优化分析。掌握本专题后，你对"一个系统为什么稳"拥有了**与控制博士共享的语言**。

控制理论与 RL 的数学工具对照表¶

这是本专题最重要的"翻译表"——帮助你在两个领域之间无缝切换：

控制理论概念	RL/SA 对应	关系说明
Lyapunov 函数 $V(x)$	SA 收敛证明中的 Lyapunov	完全相同的概念
Hurwitz 矩阵 $A$	TD(0) 中的 $-A$ 矩阵	$-A$ Hurwitz $\iff$ TD 收敛
Lyapunov 方程 $F^\top P + PF = -Q$（$F$ Hurwitz）等价形式 $A^\top P + PA = Q$（$A=-F$ 正定）	TD 收敛性中的 $P$ 矩阵	同一个方程，不同记号约定
Singular perturbation $\epsilon\dot z = g(x,z)$	两时间尺度 SA (fast critic)	离散随机版本
自适应控制 parameter law	SA 递推公式	历史同源（Ljung 1977）
系统辨识 RLS	LSTD / Zap-TD	Newton 型递推
阻尼振荡/超调	常数步长 SA 的震荡	步长 $\leftrightarrow$ 阻尼比
稳态误差	常数步长的 $O(\alpha)$ bias	类似概念
带宽/响应速度	步长大小	大步长=高带宽=快响应+多噪声
Bode 图增益裕度	$A$ 正定性的"余量" $(1-\gamma)$	都衡量"距离不稳定有多远"
闭环稳定性	on-policy TD 收敛	负反馈保证稳定
开环不稳定/正反馈	off-policy TD 发散	正反馈导致发散

这张表的使用方式：当你在 RL 训练中遇到问题时，尝试用右列的"控制语言"重新描述问题。例如："PPO 训练震荡" --> "系统欠阻尼" --> 解决方案：增大阻尼（增大 batch size 或减小 lr）。这种"翻译"往往能激发直觉。

机器人应用映射¶

SA 理论的机器人工程师价值 (summary)：从"调 bug"进化到"诊断发散"的关键——遇到 training curve 崩盘的那一刻，你能立刻从 on/off-policy（$A$ 正定性）、步长 schedule（Robbins-Monro）、两时间尺度分离（critic lr vs actor lr）、噪声方差增长（replay buffer 大小）、有界性（grad clipping / state normalization）、异步延迟（multi-env lag）这六个维度做结构化排查。

具体应用场景：

legged locomotion sim-to-real（ANYmal / Unitree A1）：Isaac Gym 中 4096 并行环境使常数步长 $3\times 10^{-4}$ 的 PPO 训练 30 分钟收敛——这是"大 batch 平滑噪声 + 常数步长 + 稳态分布 bias 可忍受"范式。SA 理论告诉你：要降低最终 policy 的方差，要么减 lr（bias下降 variance下降但速度下降），要么加 batch size（variance下降），要么两段式训练（先大 lr 后小 lr，近似 Robbins-Monro）。
分布式训练 (IMPALA-like)：Isaac Lab 的多 GPU RLlib 部署，Tsitsiklis 1994 异步 SA 的延迟有界假设必须被显式工程保证——设置 max_lag、检查 V-trace 的 importance ratio 上界。
sim-to-real 训练预算：用 SA 渐近方差公式 $\sigma^2\propto\alpha$，可估计"再跑多少步 variance 降一半"——理论指导训练预算分配。
manipulation RL (Isaac Lab / Orbit)：长 horizon 任务中 TD 误差的非线性依赖让 $A$ 病态（Hessian condition number 大），这时 Zap SA 类 Newton 方法有潜力。
嵌入式部署：仿到真机后若继续在线微调，此时是小 batch + 非平稳，只能用常数 lr 的 SA 稳态分布范式——Robbins-Monro 彻底失效。
多模态 locomotion（跑、跳、爬坡切换）：不同模态对应不同的 $A$ 矩阵（不同环境动力学）。模态切换时 $A$ 突变，ODE 的平衡点 $\theta^*$ 跳变——这就是 PPO 训练中"加入新 reward term 后 reward 先崩后恢复"的数学解释。SA 理论建议：模态切换时加 warmup（重新初始化学习率到较大值），让算法有足够"探索能量"到达新平衡点。
视觉-运动策略（ViNT / RT-2 style）：大型视觉编码器 + 小型策略头的架构中，编码器和策略头使用不同学习率是标准做法（encoder lr = 0.1x policy lr）。这是**三时间尺度 SA** 的一个实例——encoder（最慢）、critic（中）、actor（最慢或中）。Borkar 的两时间尺度理论可以推广到三时间尺度（Borkar 2008 第 6.4 节），但工程上通常用"冻结 encoder 前 $N$ 步"的简化方案。

自测题目¶

基础：证明 $\alpha_t=1/t$ 满足 Robbins-Monro 条件，而 $\alpha_t=1/\sqrt t$ 不满足（哪一条？）。反之 $\alpha_t=1/t^{0.9}$ 和 $\alpha_t=1/(t\log t)$ 如何？
TD 关键引理：自行推导 §6.5.4 Step 3 中 $A+A^\top\succ 0$，明确指出哪一步用到了"$d^\pi$ 是 $P^\pi$ 的不变测度"。若换成 off-policy 采样（$D\neq D^\pi$），上述推导在哪一行失效？
Borkar-Meyn 条件验证：对 tabular Q-learning，验证 Borkar-Meyn 四条件 (A1)-(A4)。（提示：$h$ 不光滑——含 $\max$，但局部 Lipschitz；在 $\|Q\|_\infty\le R_{\max}/(1-\gamma)$ 的球内分析。）
两时间尺度：写出 Actor-Critic 的两 ODE，明确慢 ODE 的右端为什么是 $\nabla J(\theta)$ 而非别的量（用 policy gradient theorem, 6.2）。
Baird 反例的 ODE 解释：找出 Baird 反例中矩阵 $A$ 的特征值（可查原文或 Sutton-Barto 第 2 版 §11.2），说明为什么 off-policy 下某特征值实部为负 $\Rightarrow$ ODE 发散。
有限样本：用 Azuma-Hoeffding 推导常数步长 $\alpha$ 下 TD(0) 在 $T$ 步后的集中不等式（假设 $A+A^\top\succeq 2\mu I$）。
Zap 思想：为什么 Zap-Q 需要第二时间尺度估计矩阵 $A_t$？如果直接用 $\hat A_t=\frac{1}{t}\sum_{s\le t}(\cdot)$ 而不做两时间尺度，收敛性会在哪里出问题？
工程：在 Isaac Lab 的 PPO 中，如果将 critic lr 设为 actor lr 的 1/10（违反两时间尺度），理论上会发生什么？实际通常观察到什么现象？
Polyak 平均：对一维 SA $\theta_{t+1} = \theta_t + \alpha_t(-\theta_t + \varepsilon_t)$，$\varepsilon_t\sim\mathcal{N}(0,1)$，取 $\alpha_t = 1/t^{0.6}$。(a) 验证 RM 条件；(b) 模拟 $\theta_t$ 和 $\bar\theta_t = \frac{1}{t}\sum_{s=1}^t \theta_s$ 的轨迹；(c) 比较两者的方差衰减速率。
跨章综合（需 6.1 + 6.3 + 6.4 + 本章）：梳理 RL 收敛性证明的完整链条：(a) Banach 不动点 --> 同步值迭代收敛（6.1）；(b) ODE 方法 --> TD(0) 收敛（本章）；(c) PL + ODE --> LQR 全局收敛（6.4 + 本章）；(d) 说明每一环解决了哪些新困难。

常见陷阱速查¶

陷阱	正确认识
"TD 是 SGD"	错。TD 是 semi-gradient，不是任何标量目标的梯度；Baird 反例即其后果
"所有 RL 算法 on-policy 就一定收敛"	错。On-policy 只保证了 $A+A^\top\succ 0$；非线性函数近似（NN）下这条引理不成立
"常数步长 SA 不收敛"	半对。不在点意义上收敛，但会收敛到一个围绕 $\theta^*$ 的稳态分布，方差 $\propto\alpha$
"Robbins-Monro 步长 $\alpha_t=c/t$ 是最优选择"	错。它是渐近最优但前期慢；工程常用 $\alpha_t=c/t^{0.5\sim 0.7}$ 或常数 + warmup
"两时间尺度就是 critic lr 远大于 actor lr"	精确条件是 $\alpha_t/\beta_t\to 0$（比率趋于 0），而不是固定比值大
"Q-learning 收敛靠 Banach 不动点"	不完全对。需要 Tsitsiklis 1994 的异步 SA 定理，Banach 仅给出 $Q^*$ 存在唯一
"鞅差条件方差一定要有界"	错。允许 $\mathbb{E}[\\|M\\|^2\mid\mathcal F_t]\le K(1+\\|\theta\\|^2)$——线性增长即可
"ODE 方法等于取均值忽略噪声"	错。ODE 方法严格处理噪声：证明噪声在累积步长尺度下对轨迹扰动 $\to 0$
"Zap SA 总是最优"	错。Zap 只是渐近方差最优，常数倍数复杂度更高；小维度有优势，大维度未必
"PL 条件就是凸性"	错。PL 是"梯度主导"，非凸函数（如 LQR 的 $J(K)$）可以满足
"Polyak 平均在 NN 训练中直接有用"	部分对。NN 参数空间非凸，参数平均不等于函数平均。EMA / target network 是更实用的替代
"SA 只在 tabular 有理论保证"	错。线性函数近似下 TD、GTD、LSTD 都有严格的 SA 收敛保证；NN 下是开放问题

与后续专题/批次的桥梁¶

上节讲完了本专题的核心内容。在结束前，让我们为后续学习铺好路——SA 理论不是一个封闭的话题，它向前向后都有丰富的连接。

样本复杂度与前沿理论（下一章）：off-policy evaluation (FQE, LSTD-Q) 的收敛性需要本专题的 off-policy SA 工具（GTD 的两时间尺度分析）；pessimism-based methods 的收敛性证明用带约束的 SA / projected SA。
SLAM 与状态估计方向：EKF / UKF 的 innovation 过程本身是 SA（Kalman gain 是 Zap-like matrix gain）；Ljung 1977 正是为辨识 EKF 而写。
优化理论方向：SGD、Adam、SVRG 都是 SA 的特例；Adam 的 adaptive lr 可视为 Zap SA 的轻量版。
回溯 6.1：Banach 不动点定理给了"$T^*$ 的不动点存在唯一"；本专题补上"算法能找到这个不动点"。
回溯 6.2：policy gradient theorem 给出慢 ODE 右端；本专题解释为什么 Actor-Critic 慢变量能收敛到 critical point。
回溯 6.3：Tsitsiklis-Van Roy 1997 定理、Baird 反例本专题给出完整 ODE 证明。
回溯 6.4：Fazel 2018 PL 证明的数学工具 = SA + PL。

经典论文清单（按时间顺序）¶

Robbins & Monro 1951 "A Stochastic Approximation Method", Annals of Mathematical Statistics 22(3):400-407. SA 的起点。
Dvoretzky 1956 "On Stochastic Approximation", Proc. 3rd Berkeley Symp. on Math. Stat. & Prob. 1:39-55. 统一抽象定理。
Ljung 1977 "Analysis of Recursive Stochastic Algorithms", IEEE TAC 22(4):551-575. ODE 方法系统化奠基。
Polyak 1990 "New Method of Stochastic Approximation Type", Automation & Remote Control 51(7):937-946. 均值化加速。
Jaakkola, Jordan, Singh 1994 "On the Convergence of Stochastic Iterative Dynamic Programming Algorithms", Neural Computation 6(6):1185-1201. Q-learning 收敛的 MIT 版证明。
Tsitsiklis 1994 "Asynchronous Stochastic Approximation and Q-Learning", Machine Learning 16(3):185-202. 异步 SA 与 Q-learning 收敛。
Bertsekas & Tsitsiklis (1996) Neuro-Dynamic Programming, Athena Scientific. RL 数学化的第一本专著。
Borkar 1997 "Stochastic Approximation with Two Time Scales", Systems & Control Letters 29(5):291-294. 两时间尺度 SA 鼻祖。
Tsitsiklis & Van Roy 1997 "An Analysis of Temporal-Difference Learning with Function Approximation", IEEE TAC 42(5):674-690. 线性 TD + Baird。
Borkar & Meyn 2000 "The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning", SIAM J. Ctrl. Optim. 38(2):447-469. 现代 SA 主力定理。
Konda & Tsitsiklis 2003 "On Actor-Critic Algorithms", SIAM J. Ctrl. Optim. 42(4):1143-1166. Actor-Critic 收敛的严格证明。
Sutton, Maei et al. 2009 "Fast Gradient-Descent Methods for Temporal-Difference Learning with Linear Function Approximation", ICML. GTD/TDC。
Devraj & Meyn 2017 "Zap Q-Learning", NeurIPS 2017 / arXiv 1707.03770. 矩阵增益 SA，渐近最优。
Fazel, Ge, Kakade, Mesbahi 2018 "Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator", ICML 2018 / arXiv 1801.05039. PL + SA 全局收敛。
Bhandari, Russo, Singal 2018 "A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation", COLT. TD 有限样本分析。
Srikant & Ying 2019 "Finite-Time Error Bounds for Linear Stochastic Approximation and TD Learning", COLT. 常数步长 TD 精细界。
Chen, Devraj, Busic, Meyn 2020 "Zap Q-Learning for Optimal Stopping", ACC 2020 / arXiv 1904.11538. Zap 在线性函数近似下收敛。

时间预算与节奏建议¶

阶段	时长	目标
第 1 周	15-20h	必学 §6.5.1-6.5.3：精读 Borkar 2008 第 2、3 章；自己推导 Robbins-Monro 的 supermartingale 证明；NumPy 实现 TD(0) 追踪 ODE 实验
第 2 周	15-20h	必学 §6.5.4-6.5.5：啃 Tsitsiklis-Van Roy 1997 原文 + Tsitsiklis 1994 原文；实现 Baird 反例并从 ODE 角度诊断发散
第 3 周	10-15h	核心 §6.5.6, §6.5.A, §6.5.E：Polyak-Ruppert 平均 + Borkar 2008 第 6 章两时间尺度 + Lyapunov 构造方法
第 4 周（选）	10-15h	进阶 §6.5.B-D, §6.5.F-I：Meyn 2022 第 4、8、11 章（Zap-Q）；Fazel 2018 读通

核心提醒：本专题的**最低可接受目标**是掌握 §6.5.1-§6.5.5——理解 SA 框架 + 能陈述 Borkar-Meyn 定理 + 看懂 TD(0) 的 ODE 证明。若时间紧张，§6.5.6 及档位 4 全部跳过不影响继续后续章节。

学习路径建议（按个人背景分层）：

你的背景	建议路径	跳过内容
纯工程师（只关心调参）	§6.5.1 动机 + §6.5.H 诊断指南	所有证明细节
算法工程师（需要理解原理）	§6.5.1-5 全部 + §6.5.H	档位 4 的理论深度
博士生/理论方向	全部内容，特别是证明	无
控制背景转 RL	重点读"与控制理论映射" + §6.5.4 证明	§6.5.B 鞅理论（如果已经会）

总结¶

本专题给出了 RL 收敛性证明的**统一数学语言**：一切迭代 RL 算法 = 随机逼近 $(*)$ 式；一切收敛性分析 = 平均 ODE 的稳定性分析；一切稳定性分析 = Lyapunov 方法。这个链条让你与控制博士的 qual 考试语言完全打通。

在更深的层次，本专题展示了 20 世纪中叶两条线的汇流：一条是 Robbins-Monro 1951 开启的统计学递推估计，另一条是 Lyapunov 1892 以降的动力系统稳定性理论。Ljung 1977 把它们接通，Borkar-Meyn 2000 用现代概率工具完美化，Meyn 2022 用它重构整个 RL。

对机器人 RL 工程师，本专题真正的收益是三重的： 1. 诊断力：从调 bug 到诊断发散的结构化能力； 2. 设计力：理解 critic/actor lr 分离、常数步长、异步训练等工程决策背后的数学约束； 3. 语言力：与控制博士、优化博士、RL 理论家在同一语义层面对话的能力。

当你下一次在 Isaac Lab 面前看到 training curve 崩盘，你不会再盲调 lr——你会先画出 $A$ 的条件数、检查两时间尺度比率、估计噪声方差、看 Q 的有界性。这就是本专题存在的终极理由。

最后的鸟瞰：把本专题的所有内容浓缩成一句话——

任何 RL 算法的收敛性 = 对应 ODE 的稳定性 + 三个技术条件（步长、噪声、有界性）。

这句话是你 qual 考试上的万能答案起点，也是你面对任何新 RL 算法时的第一反应："写出它的 ODE，看它稳不稳。"如果稳——它大概率会收敛。如果不稳——理论上它必然发散，无论你调什么超参数。这就是第一性原理的力量。

开放问题与前沿方向（2024-2026 活跃研究）：

NN 函数近似下的 SA 收敛理论：当前所有严格理论都限于 tabular 或线性函数近似。NN（过参数化）下的 SA 收敛是开放问题。NTK（Neural Tangent Kernel）视角给出了一些部分结果（Cai et al. 2019），但远未完善。
Non-Markovian SA：transformer-based RL（如 Decision Transformer）中的记忆依赖打破了 Markov 假设。如何扩展 SA 理论到长程依赖是前沿问题。
Mean-field SA：多 agent RL 中每个 agent 的 SA 相互耦合，mean-field 近似（Carmona-Delarue 2018）给出了可处理的框架。
Federated SA：机器人集群的分布式学习中，每个机器人做本地 SA 并定期通信。通信延迟和异质性的理论处理是活跃方向。
SA 与 diffusion models：score-matching 中的去噪过程可以视为 SA 的反向版本。这个联系正在被探索。

附录¶

附录 A：免费 PDF / 在线资源¶

Sean Meyn, Control Systems and Reinforcement Learning (Cambridge 2022) 作者官方免费 pre-publication PDF：https://meyn.ece.ufl.edu/control-systems-and-reinforcement-learning/ （Meyn 获 Cambridge 授权公开）；镜像：https://archive.org/details/Meyn2022_CSRL
Robbins-Monro 1951 原文（Columbia 公开）：https://www.columbia.edu/~ww2040/8100F16/RM51.pdf ；Project Euclid 开放获取：https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-22/issue-3/A-Stochastic-Approximation-Method/10.1214/aoms/1177729586.full
Dvoretzky 1956 (Berkeley Symposium 开放)：https://projecteuclid.org/euclid.bsmsp/1200501645
Tsitsiklis 1994 原文（作者 MIT 主页）：https://www.mit.edu/~jnt/Papers/J052-94-jnt-q.pdf
Tsitsiklis-Van Roy 1997 原文：https://www.mit.edu/~jnt/Papers/J063-97-bvr-td.pdf
Borkar-Meyn 2000 原文（Meyn 主页）：https://meyn.ece.ufl.edu/wp-content/uploads/sites/77/archive/spm_files/Papers_pdf/ode.pdf
Konda-Tsitsiklis 2003：https://www.mit.edu/~jnt/Papers/J094-03-kon-actors.pdf
Devraj-Meyn Zap-Q：https://arxiv.org/abs/1707.03770 ；NeurIPS 版：https://proceedings.neurips.cc/paper_files/paper/2017/file/4671aeaf49c792689533b00664a5c3ef-Paper.pdf
Fazel et al. 2018 LQR：http://proceedings.mlr.press/v80/fazel18a/fazel18a.pdf ；arXiv：https://arxiv.org/pdf/1801.05039
Sutton & Barto 2018 RL 2nd ed（官方）：http://incompleteideas.net/book/the-book-2nd.html
Szepesvari Algorithms for RL（Alberta 官方）：https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf
Bertsekas (2019) 相关免费讲义：https://web.mit.edu/dimitrib/www/RLbook.html （RL and Optimal Control 免费草稿）

附录 B：视频课程资源¶

Sean Meyn, Simons Institute "Theory of RL" 2020 系列讲座：https://simons.berkeley.edu/workshops/rl-2020-bc —— Meyn 亲自讲 ODE 方法、Zap-Q
Csaba Szepesvari, RL Theory 课程（DLRL Summer School / 自己 YouTube）：https://sites.ualberta.ca/~szepesva/RLBook.html 与 YouTube 上多个 tutorial
Simons Institute "Theory of Reinforcement Learning" program 系列（2020 秋）：https://simons.berkeley.edu/programs/rl20
Borkar 本人在 TIFR / IISc 的 stochastic approximation 讲座 可在 YouTube 搜 "Vivek Borkar stochastic approximation"
Benjamin Van Roy, Stanford MS&E 338 Reinforcement Learning：https://web.stanford.edu/class/msande338/
Emma Brunskill, Stanford CS 234：http://web.stanford.edu/class/cs234/ ——第 4-6 讲涉及 TD 收敛
UCL / DeepMind David Silver RL 课程：https://www.davidsilver.uk/teaching/ —— Lecture 4-5 涉及 MC/TD 收敛性直觉

附录 C：中文资源¶

王树森《深度强化学习》（高等教育出版社 2023）：第 5 章 TD、第 8 章 Actor-Critic 章节涉及收敛性直觉；配套 GitHub：https://github.com/wangshusen/DeepLearning
郭宪、方勇纯《深入浅出强化学习：原理入门》：第 5-7 章覆盖 TD、Q-learning、Actor-Critic 的中文推导
李宏毅 2022/2024 RL 课程（B 站）：https://www.bilibili.com/video/BV1UE411G78S （中文英讲，逻辑清晰）
周志华《机器学习》（西瓜书） 第 16 章强化学习：入门级 TD/Q-learning 中文
赵世钰（Shiyu Zhao）《Mathematical Foundations of Reinforcement Learning》：中英文双版本，GitHub：https://github.com/MathFoundationRL/Book-Mathmatical-Foundation-of-Reinforcement-Learning —— 本专题中文替代首选，直接讲 SA、ODE、收敛证明，强烈推荐
知乎"强化学习"话题：搜索"随机逼近收敛""TD 收敛性证明""Borkar ODE"可找到多篇技术博客
CSDN / 博客园相关技术博客：搜 "Robbins-Monro 证明""Borkar-Meyn 定理"

附录 D：优质博客与讲义¶

Nan Jiang, UIUC CS 542 "Statistical Reinforcement Learning"：https://nanjiang.cs.illinois.edu/cs542.html —— 全套 lecture notes + scribe
Csaba Szepesvari, RL Theory blog：https://rltheory.github.io/ （含 RL theory confessions 等长文）
Ambuj Tewari, Michigan STATS 710 / EECS 598：https://ambujtewari.github.io/teaching/
Shipra Agrawal, Columbia IEOR 8100：http://www.columbia.edu/~sa3305/
Dimitri Bertsekas 主页：http://web.mit.edu/dimitrib/www/home.html —— 各种 RL/DP 综述 PDF
Matteo Pirotta / Alessandro Lazaric RL theory 课程（INRIA）
Lilian Weng 博客"Policy Gradient Algorithms"：https://lilianweng.github.io/posts/2018-04-08-policy-gradient/ （涉及 Actor-Critic 收敛性直觉）
Tor Lattimore 2020 "Bandits and RL" 讲义：https://tor-lattimore.com/downloads/book/book.pdf （含 SA 章节）

附录 E：开源代码仓库¶

CleanRL: https://github.com/vwxyzjn/cleanrl —— 单文件 RL 实现，观察 PPO/DQN 的步长 schedule
stable-baselines3: https://github.com/DLR-RM/stable-baselines3
rl_games: https://github.com/Denys88/rl_games —— Isaac Gym 官方 PPO 骨干
Isaac Lab: https://github.com/isaac-sim/IsaacLab
legged_gym: https://github.com/leggedrobotics/legged_gym
rljax (JAX 实现): https://github.com/toshikwa/rljax
TorchRL: https://github.com/pytorch/rl
本专题专用实验仓库建议自建：tabular TD(0) + Baird + ODE 可视化，参考 https://github.com/ShangtongZhang/reinforcement-learning-an-introduction （Sutton-Barto 第二版习题代码，含 Baird 反例）

附录 F：关键符号表¶

符号	含义	首次出现
$\theta_t$	SA 迭代的参数（第 $t$ 步）	§6.5.1
$\alpha_t$	步长（学习率）	§6.5.1
$h(\theta, X)$	SA 更新增量函数	§6.5.1
$\bar h(\theta)$	$h$ 的平均场：$\mathbb{E}[h(\theta,X)]$	§6.5.3
$M_{t+1}$	鞅差噪声：$h(\theta_t,X_t) - \bar h(\theta_t)$	§6.5.2
$V(\theta)$	Lyapunov 函数	§6.5.2
$A$	TD(0) 的平均 ODE 矩阵：$\Phi^\top D^\pi(I-\gamma P^\pi)\Phi$	§6.5.4
$P$	Lyapunov 方程 $A^\top P + PA = I$ 的解	§6.5.4
$D^\pi$	策略 $\pi$ 下的平稳分布对角矩阵	§6.5.4
$T^*$	最优 Bellman 算子	§6.5.5
$\gamma$	折扣因子	§6.5.1
$\Phi$	特征矩阵（$\\|\mathcal{S}\\| \times d$）	§6.5.4
$J$	Jacobian $\nabla\bar h(\theta^*)$ 或策略目标函数	依上下文
$\Sigma^*$	Polyak-Ruppert 的最优渐近协方差矩阵	§6.5.6
$\mu$	PL 常数或最小特征值相关常数	§6.5.I/J
$\sigma^2$	噪声方差 $\mathrm{tr}(\mathrm{Cov}(M))$	§6.5.J

附录 G：社区与论坛¶

RL Theory Virtual Seminar: https://rl-theory.github.io/ （每周在线讲座 + 录像）
Simons Institute YouTube: https://www.youtube.com/user/SimonsInstitute （RL Theory 项目完整录像）
arxiv-sanity-lite: https://arxiv-sanity-lite.com/ （RL theory 最新预印本）
OpenReview (ICLR/NeurIPS): https://openreview.net —— RL 理论论文的公开 review 常含 SA 讨论
r/reinforcementlearning: https://reddit.com/r/reinforcementlearning （工程为主，偶有理论讨论）
r/MachineLearning: https://reddit.com/r/MachineLearning
Twitter / X 上 Sean Meyn (@SeanMeyn)、Csaba Szepesvari、Ben Recht (@beenwrekt)、Nan Jiang 等账号：跟踪 SA/RL theory 前沿
Discord "Papers We Love" 与 "Yannic Kilcher Discord"：有 RL paper reading 频道

附录 H：常用公式速查¶

Robbins-Monro 条件：$\alpha_t > 0$，$\sum_{t=1}^\infty \alpha_t = \infty$，$\sum_{t=1}^\infty \alpha_t^2 < \infty$。

TD(0) 的 $A$ 矩阵：$A = \Phi^\top D^\pi(I - \gamma P^\pi)\Phi$，其中 $\Phi$ 是特征矩阵，$D^\pi = \mathrm{diag}(d^\pi)$。

TD(0) 的 $b$ 向量：$b = \Phi^\top D^\pi R^\pi$。

TD(0) 不动点：$\theta^* = A^{-1}b$。

Lyapunov 方程：对 ODE $\dot\theta=-A\theta$（$A$ 正定），$A^\top P + PA = I$，$P \succ 0$。等价地，对 ODE $\dot\theta=F\theta$（$F$ Hurwitz），$F^\top P + PF = -I$。条件：$P\succ 0 \iff$ 系统渐近稳定。

Borkar-Meyn 缩放极限：$h_\infty(\theta) = \lim_{c\to\infty} h(c\theta)/c$。

Polyak-Ruppert 渐近方差：$\Sigma^* = J^{-1} S (J^{-1})^\top$，其中 $J = \nabla\bar h(\theta^*)$，$S = \mathrm{Cov}(h(\theta^*, X))$。

常数步长稳态方差：$\mathrm{Var}(\theta_\infty) \approx \frac{\alpha}{2} A^{-1} S (A^{-1})^\top$。

有限样本界（Srikant-Ying 2019）：$\mathbb{E}\|\theta_T-\theta^*\|^2 \le (1-2\mu\alpha)^T\|\theta_0-\theta^*\|^2 + \frac{\alpha\sigma^2}{2\mu}$。

$\gamma$-压缩映射：$\|T^*Q - T^*Q'\|_\infty \le \gamma\|Q-Q'\|_\infty$，$\gamma < 1$。

两时间尺度条件：$\alpha_t/\beta_t \to 0$（actor 步长远小于 critic 步长）。

PL 不等式：$\|\nabla J(\theta)\|^2 \ge 2\mu(J(\theta) - J^*)$，$\mu > 0$。

Zap SA 增益：$\theta_{t+1} = \theta_t - \alpha_t \hat J_t^{-1} h(\theta_t, X_t)$，$\hat J_t$ 是 Jacobian 估计。

后续衔接：下一章"样本复杂度与前沿理论"将使用本章建立的 SA 工具分析 offline policy evaluation 的收敛性，并展开 safe RL/CMDP 与 distributional RL 的数学基础。

算法	\(h(\theta, X)\)	目标根
线性 TD(0)	\([r+\gamma\phi(s')^\top\theta-\phi(s)^\top\theta]\phi(s)\)	\(\Phi^\top D^\pi(T^\pi V_\theta-V_\theta)=0\)
Q-learning（异步）	在坐标 \((s,a)\) 上：\(r+\gamma\max_{a'}Q(s',a')-Q(s,a)\)	\(T^*Q-Q=0\)
SARSA	类似 Q-learning 但用 \(Q(s',a')\) 不取 max	\(T^{\pi_Q}Q-Q=0\)
Actor（两时间尺度）	\(\nabla\log\pi_\theta(a\mid s)\,Q_w(s,a)\)	\(\nabla J(\theta)=0\)
GTD2 / TDC	双变量：\((w,\theta)\) 联合 SA	投影 Bellman 方程根
Natural Actor	\(F(\theta)^{-1}\nabla J(\theta)\)	\(\nabla J(\theta)=0\)

步长选择	\(\sum\alpha\)	\(\sum\alpha^2\)	RM 条件	备注
\(c/t\)	\(\infty\)	\(<\infty\)	满足	经典选择，临界边界
\(c/t^{0.7}\)	\(\infty\)	\(<\infty\)	满足	工程常用，前期更快
\(c/t^{0.5}\)	\(\infty\)	\(=\infty\)	不满足	噪声不衰减
\(c/t^2\)	\(<\infty\)	\(<\infty\)	不满足	步长衰减太快
\(c/(t\log t)\)	\(\infty\)	\(<\infty\)	满足	比 \(1/t\) 更慢衰减
常数 \(c\)	\(=\infty\)	\(=\infty\)	不满足	不收敛到点，但有稳态分布

步骤	TD(0) 的实例	Q-learning 的实例
\(\theta\)	值函数参数 \(\theta\in\mathbb{R}^d\)	Q-table \(Q\in\mathbb{R}^{\\|S\\|\times\\|A\\|}\)
\(X_t\)	\((S_t, R_t, S_{t+1})\)	\((S_t, A_t, R_t, S_{t+1})\)
\(h(\theta, X)\)	\(\delta_t\phi(S_t)\)	\(e_{s,a}(R+\gamma\max Q - Q(s,a))\)
\(\bar h(\theta)\)	\(b - A\theta\)	\(T^*Q - Q\)
ODE	\(\dot\theta = -A\theta + b\)	\(\dot Q = T^*Q - Q\)
稳定性工具	\(A\) 正定 --> Hurwitz	\(\gamma\)-压缩 --> \(\infty\)-Lyapunov
结论	\(\theta \to A^{-1}b\) a.s.	\(Q \to Q^*\) a.s.

方法	\(h(\theta, X)\)	增益矩阵 \(G_t\)	特点
Robbins-Monro	\(h(\theta, X)\)（一般向量场）	\(I\)	最一般
SGD	\(-\nabla\ell(\theta, X)\)	\(I\)	\(h\) 是梯度
SGD + Momentum	\(-\nabla\ell(\theta, X) + \beta v_{t-1}\)	\(I\)	加了惯性
RMSprop	\(-\nabla\ell(\theta, X)\)	\(\mathrm{diag}(1/\sqrt{v_t+\epsilon})\)	自适应标量增益
Adam	\(-\nabla\ell(\theta, X)\)	\(\mathrm{diag}(\hat m_t / (\sqrt{\hat v_t}+\epsilon))\)	Momentum + 自适应
Natural Gradient	\(-F(\theta)^{-1}\nabla J(\theta)\)	\(F(\theta)^{-1}\)	Fisher 信息矩阵增益
Zap SA	\(h(\theta, X)\)	\(-\hat J^{-1}\)	Jacobian 增益，渐近最优

性质	SGD（监督学习）	SA（RL）
更新方向 \(h\)	\(-\nabla\ell(\theta,X)\)，是目标 \(L(\theta)=\mathbb{E}[\ell]\) 的无偏梯度	\(h(\theta,X)\) 可以不是任何目标的梯度
平均场 \(\bar h\)	\(-\nabla L(\theta)\)，gradient flow	一般的向量场 \(\bar h(\theta)\)
Lyapunov 函数	天然有：\(V(\theta)=L(\theta)-L^*\)	需要手工构造或从 ODE 结构推导
稳定性分析	凸性/PL/KL 条件直接给出	必须分析 ODE \(\dot\theta=\bar h(\theta)\) 的谱
反例	一般不发散（只是收敛慢）	可以发散（Baird 反例）

方面	TD(0)	Q-learning
平均 ODE	线性 \(\dot\theta = -A\theta + b\)	非线性 \(\dot Q = T^*Q - Q\)
稳定性工具	Hurwitz 矩阵 + Lyapunov 方程	\(\infty\)-范数 Lyapunov + 压缩映射
同步/异步	可同步可异步	天然异步
关键困难	\(A\) 正定性	max 非线性 + 异步
范数	\(D^\pi\)-加权 2-范数	\(\infty\)-范数

特性	Polyak-Ruppert (\(1/t\) 平均)	EMA (\(\theta_{\rm ema} = \tau\theta + (1-\tau)\theta_{\rm ema}\))
遗忘速度	均匀加权所有历史	指数遗忘，半衰期 \(\approx 1/(1-\tau)\)
非平稳适应	差（早期坏样本永远影响）	好（旧信息快速遗忘）
渐近最优性	达到 Cramer-Rao 下界	不一定最优（取决于 \(\tau\)）
RL 中的化身	tabular LSTD	target network（\(\tau\)=0.995/0.999）
计算开销	\(O(d)\)：维护均值	\(O(d)\)：维护 EMA

方式	实现	理论对应	常用于
lr 比值固定	critic_lr = 5x actor_lr	近似满足（常数比不严格 \(\to 0\)）	PPO/SAC (Isaac Lab, rl_games)
多步 critic 更新	每个 actor 步做 5-10 个 critic 步	等效于 \(\beta\) 更大	PPO (多 epoch critic)
target network + 周期更新	每 C 步 \(\theta^- \leftarrow \theta\)	离散时间尺度分离	DQN, SAC

维度	检查项	对应理论	排查方法
1. On/Off-policy	\(A\) 矩阵是否正定？	TVR 1997 §6.5.4	检查算法是否使用 replay buffer；若是，检查 importance ratio 是否截断
2. 步长条件	学习率 schedule 是否合理？	Robbins-Monro §6.5.2	打印 lr 曲线；检查是否过早衰减或根本不衰减
3. 两时间尺度	critic lr > actor lr？	Borkar 1997 §6.5.A	检查配置文件中 critic/actor 的 lr 比值
4. 噪声方差	batch size 是否足够？梯度是否 clip？	(A3) 噪声方差条件	打印梯度范数；减小 lr 或增大 batch
5. 有界性	Q 值/advantage 是否爆炸？	(A4)/(S3) 有界性	打印 \(\\|Q\\|_\infty\)；加 state/reward normalization
6. 异步延迟	多 GPU 参数同步延迟？	Tsitsiklis 1994 §6.5.D	检查 NCCL 通信频率；降低 num_workers

方法	渐近方差 \(\mathrm{Var}(\theta_t) \cdot t\)	是否最优	计算复杂度/步	适用场景
标准 SA (\(G=I\), \(\alpha=c/t\))	\(c^2 \sigma^2 / (2ca-1)\)（依赖 \(c\) 选择）	否	\(O(d)\)	简单问题
Polyak-Ruppert 平均	\(\Sigma^* = J^{-1}S J^{-\top}\)（Cramer-Rao）	是	\(O(d)\)	平稳目标
LSTD（直接解 \(\hat A^{-1}\hat b\)）	与 Polyak 相同	是	\(O(d^2)\)	中小维度
Zap SA (\(G=-\hat J^{-1}\))	\(\Sigma^*\)（Cramer-Rao）	是	\(O(d^2)\)	中小维度
常数步长 SA (\(\alpha\) 固定)	\(\alpha\sigma^2/(2\mu)\)（稳态偏差）	N/A	\(O(d)\)	非平稳环境

误解	正确理解
"Robbins-Monro 步长条件 \(\sum\alpha=\infty, \sum\alpha^2<\infty\) 只是技术假设"	这两个条件有清晰的物理含义。\(\sum\alpha=\infty\) 保证步长"够大"——算法有能力从任何初始点走到最优解（如果步长总和有限，算法走不远就停下了）。\(\sum\alpha^2<\infty\) 保证噪声的累积效应有限——如果步长衰减不够快，噪声的方差累积会让迭代永远震荡。两者缺一不可
"ODE 方法只是把离散算法近似成连续系统，精度不够"	ODE 方法不是近似——它是严格的。Borkar-Meyn 定理证明了：如果关联 ODE \(\dot\theta = h(\theta)\) 的全局吸引子是 \(\theta^\)，那么 SA 迭代 \(\theta_{t+1} = \theta_t + \alpha_t[h(\theta_t) + M_t + \beta_t]\) 在适当条件下几乎必然收敛到 \(\theta^\)。连续化不损失信息，反而让分析工具（Lyapunov 函数、相平面）变得可用
"两时间尺度只是让一个更新跑快一点、另一个慢一点"	两时间尺度的本质是奇异摄动（singular perturbation）。快时间尺度的变量在慢时间尺度看来是"瞬时平衡"的——它已经跟踪到了慢变量当前值对应的不动点。这不是"快一点慢一点"的程度问题，而是时间尺度分离后的质变：慢变量看到的是一个确定性系统（快变量的不动点映射），而非随机系统
"实践中用 Adam 优化器，不满足 R-M 条件，所以收敛理论没用"	Adam 的自适应步长确实不满足经典 R-M 条件，但有两点值得注意：(1) Adam 可以看作一种隐式的步长调度，在每个坐标方向上自适应地满足"步长够大但不太大"的精神；(2) RL 的实际训练往往不是收敛到不动点，而是在不动点附近的邻域内振荡（常数步长 SA 的行为）。理论框架仍然指导着超参选择的方向
"TD(0) 的 ODE 收敛证明只适用于线性函数逼近"	正确。ODE 方法的核心在于证明 \(A = \Phi^\top D^\pi(I-\gamma P^\pi)\Phi\) 正定。线性 FA 下 \(A\) 是常数矩阵，可以直接分析特征值。非线性 FA（深度网络）下 \(A\) 变成了依赖 \(\theta\) 的非线性映射，ODE 变成非线性系统，全局稳定性分析困难得多。这也是深度 RL 缺乏收敛保证的根本原因

主题	核心定理/方法	关键条件	RL 应用
Robbins-Monro	SA 收敛定理	\(\sum\alpha=\infty\), \(\sum\alpha^2<\infty\), Lyapunov 条件	所有 RL 算法的祖先
ODE 方法	Borkar-Meyn 2000	(A1)-(A4), 缩放 ODE 稳定	SA --> ODE 稳定性的桥梁
TD(0) 收敛	TVR 1997	\(A+A^\top\succ 0\)（on-policy 保证）	线性 TD 的完整 ODE 证明
Q-learning 收敛	Tsitsiklis 1994	每坐标无限访问 + \(\gamma\)-压缩	异步 SA 框架
Polyak-Ruppert	平均化加速	\(\beta\in(1/2,1)\)	达到 Cramer-Rao 下界
两时间尺度	Borkar 1997	\(\alpha/\beta\to 0\) + 快/慢 ODE 稳定	Actor-Critic / GTD
Zap SA	Devraj-Meyn 2017	Jacobian 估计	渐近最优速率
PL 全局收敛	Fazel 2018	PL 条件	非凸 RL（LQR）全局收敛

症状	可能原因	排查步骤	相关章节
TD 参数 \(\theta_t\) 发散到 \(\pm\infty\)	Off-policy 采样导致 \(A\) 矩阵不正定	1. 打印 \(A\) 的特征值 2. 检查 behavior/target policy 差异 3. 切换到 GTD/TDC	§6.5.4, 6.3
Q-learning reward 不涨	\(\varepsilon\)-greedy 的 \(\varepsilon\) 过小导致覆盖不足	1. 打印每个 \((s,a)\) 的访问次数 2. 增大 \(\varepsilon\) 3. 检查 replay buffer 是否过小	§6.5.5
Actor-Critic 训练震荡	Critic/Actor lr 比值不当	1. 确认 critic lr > actor lr 2. 增加 critic 更新次数 3. 打印 value loss 曲线	§6.5.A
PPO reward 前期上升后崩溃	值函数估计爆炸	1. 打印 `max(\\|V\\|)` 2. 开启 value clipping 3. 加 state/reward normalization	§6.5.H
分布式训练不收敛	参数延迟过大	1. 检查 NCCL 同步频率 2. 降低 num_workers 3. 加 V-trace 校正	§6.5.D

控制理论概念	RL/SA 对应	关系说明
Lyapunov 函数 \(V(x)\)	SA 收敛证明中的 Lyapunov	完全相同的概念
Hurwitz 矩阵 \(A\)	TD(0) 中的 \(-A\) 矩阵	\(-A\) Hurwitz \(\iff\) TD 收敛
Lyapunov 方程 \(F^\top P + PF = -Q\)（\(F\) Hurwitz）等价形式 \(A^\top P + PA = Q\)（\(A=-F\) 正定）	TD 收敛性中的 \(P\) 矩阵	同一个方程，不同记号约定
Singular perturbation \(\epsilon\dot z = g(x,z)\)	两时间尺度 SA (fast critic)	离散随机版本
自适应控制 parameter law	SA 递推公式	历史同源（Ljung 1977）
系统辨识 RLS	LSTD / Zap-TD	Newton 型递推
阻尼振荡/超调	常数步长 SA 的震荡	步长 \(\leftrightarrow\) 阻尼比
稳态误差	常数步长的 \(O(\alpha)\) bias	类似概念
带宽/响应速度	步长大小	大步长=高带宽=快响应+多噪声
Bode 图增益裕度	\(A\) 正定性的"余量" \((1-\gamma)\)	都衡量"距离不稳定有多远"
闭环稳定性	on-policy TD 收敛	负反馈保证稳定
开环不稳定/正反馈	off-policy TD 发散	正反馈导致发散

符号	含义	首次出现
\(\theta_t\)	SA 迭代的参数（第 \(t\) 步）	§6.5.1
\(\alpha_t\)	步长（学习率）	§6.5.1
\(h(\theta, X)\)	SA 更新增量函数	§6.5.1
\(\bar h(\theta)\)	\(h\) 的平均场：\(\mathbb{E}[h(\theta,X)]\)	§6.5.3
\(M_{t+1}\)	鞅差噪声：\(h(\theta_t,X_t) - \bar h(\theta_t)\)	§6.5.2
\(V(\theta)\)	Lyapunov 函数	§6.5.2
\(A\)	TD(0) 的平均 ODE 矩阵：\(\Phi^\top D^\pi(I-\gamma P^\pi)\Phi\)	§6.5.4
\(P\)	Lyapunov 方程 \(A^\top P + PA = I\) 的解	§6.5.4
\(D^\pi\)	策略 \(\pi\) 下的平稳分布对角矩阵	§6.5.4
\(T^*\)	最优 Bellman 算子	§6.5.5
\(\gamma\)	折扣因子	§6.5.1
\(\Phi\)	特征矩阵（\(\\|\mathcal{S}\\| \times d\)）	§6.5.4
\(J\)	Jacobian \(\nabla\bar h(\theta^*)\) 或策略目标函数	依上下文
\(\Sigma^*\)	Polyak-Ruppert 的最优渐近协方差矩阵	§6.5.6
\(\mu\)	PL 常数或最小特征值相关常数	§6.5.I/J
\(\sigma^2\)	噪声方差 \(\mathrm{tr}(\mathrm{Cov}(M))\)	§6.5.J