RL 理论：收敛、复杂度与界的读法

深度 RL 常给人”炼丹”的印象，但其底层有一套严谨的理论骨架，回答着最要命的问题：算法会不会收敛？收敛到哪？要多少样本？为什么函数逼近一上就发散？探索至少需要多少代价？ 本模块以直觉 + 结论 + 推导骨架为主，不追求把每个界证到底，而是让你会读一个界——理解每个因子（$H$、$S$、$A$、$T$、$\frac{1}{1-\gamma}$）从哪来、意味着什么，从而在实践中判断”我这个问题到底难在哪”。

学习目标

• 证明贝尔曼最优算子是 $\gamma$-压缩，并由此得到收敛速率 $\propto\gamma^k$。
• 把 $\frac{1}{1-\gamma}$ 理解为”有效视野（effective horizon）“，看懂它为何反复出现。
• 复述 performance difference lemma（PDL）及其在信赖域/离线 RL 中的用处。
• 理解”致命三要素”为何在函数逼近下破坏收敛（投影贝尔曼误差）。
• 会读 UCB-VI 的 $\tilde O(\sqrt{HSAT})$ 遗憾界与探索下界的每个因子。

1. 为什么要理论

实践者常问：“能跑就行，为什么要理论？” 三个理由：

• 区分”实现 bug”与”根本不可能”。 若理论给出某设定可发散的反例或满足发散条件，那你调一辈子超参也没用——该换算法结构（如加投影、改成 residual、用离线约束）。
• 预算规划。 样本复杂度界告诉你”要达到 $\epsilon$-最优大概需要多少交互”，量级上指导要不要上真实机器人还是先仿真。
• 指明改进方向。 界里哪个因子最大，就是瓶颈。$\frac{1}{(1-\gamma)^2}$ 说明长视野是主因，$\sqrt{S A}$ 说明状态动作空间是主因。

理论边界地图

定理 精确 Bellman 算子给出不动点与压缩性；随机逼近 表格 Q-learning 还需要充分访问与 Robbins–Monro 步长；投影 线性/函数逼近取决于 $\Pi\mathcal T$ 的范数与谱性质；工程启发式 目标网络与回放缓解风险但不自动恢复定理。压缩性很重要，但不是所有价值方法收敛的“唯一地基”。

2. 贝尔曼算子的压缩性

一切收敛性的地基。定义贝尔曼最优算子 $\mathcal T^\star$ 作用在值函数 $V:\mathcal S\to\mathbb R$ 上：

$$(\mathcal T^\star V)(s)=\max_a\Big[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\,V(s')\Big] \tag{11.1}$$

式中 $\gamma\in[0,1)$ 是折扣因子（越接近 1 越看重长远回报；取值决定”看多远”），$P(s'\mid s,a)$ 是转移概率、$r(s,a)$ 是即时奖励，均沿用前面模块的记号。本讲中 $\gamma$ 身兼两职——既是压缩映射的”收缩系数”（下一段），又决定”有效视野” $\frac{1}{1-\gamma}$（第 3 节），这正是它值得单独盯住的原因。

核心定理：$\mathcal T^\star$ 在无穷范数 $\|\cdot\|_\infty$ 下是模为 $\gamma$ 的压缩映射（$\gamma$-contraction）：

$$\big\|\mathcal T^\star V_1-\mathcal T^\star V_2\big\|_\infty\;\le\;\gamma\,\big\|V_1-V_2\big\|_\infty. \tag{11.2}$$

推导：$\mathcal T^\star$ 是 $\gamma$-压缩（完整步骤）

关键假设

折扣因子 $\gamma\in[0,1)$；奖励有界；用无穷范数 $\|V\|_\infty=\max_s|V(s)|$。用到两条基本不等式：$|\max_a f(a)-\max_a g(a)|\le\max_a|f(a)-g(a)|$，以及概率是非负且和为 1（凸组合不放大无穷范数）。

第 1 步。 固定状态 $s$，写出两者之差并用”max 之差 ≤ 差之 max”：

$$\big|(\mathcal T^\star V_1)(s)-(\mathcal T^\star V_2)(s)\big|\le \max_a\Big|\gamma\sum_{s'}P(s'|s,a)\big(V_1(s')-V_2(s')\big)\Big|. \tag{11.3}$$

奖励项 $r(s,a)$ 相消。

第 2 步（凸组合不放大）。 把差值放大到无穷范数，因 $\sum_{s'}P=1$、$P\ge0$：

$$\Big|\sum_{s'}P(s'|s,a)\big(V_1(s')-V_2(s')\big)\Big|\le\sum_{s'}P(s'|s,a)\,\|V_1-V_2\|_\infty=\|V_1-V_2\|_\infty. \tag{11.4}$$

第 3 步。 于是 $\big|(\mathcal T^\star V_1)(s)-(\mathcal T^\star V_2)(s)\big|\le\gamma\|V_1-V_2\|_\infty$。对 $s$ 取最大得

$$\|\mathcal T^\star V_1-\mathcal T^\star V_2\|_\infty\le\gamma\|V_1-V_2\|_\infty.\qquad\square \tag{11.5}$$

推论（Banach 不动点）。 压缩映射在完备空间有唯一不动点 $V^\star$，且值迭代 $V_{k+1}=\mathcal T^\star V_k$ 几何收敛：$\|V_k-V^\star\|_\infty\le\gamma^k\|V_0-V^\star\|_\infty$。策略评估算子 $\mathcal T^\pi$（把 $\max_a$ 换成对 $\pi$ 求期望）同样是 $\gamma$-压缩，不动点为 $V^\pi$。

更严格：$\|\cdot\|_\infty$ 下 $\gamma$-压缩的完整不等式链

引理（max 之差）

对任意 $f,g:\mathcal A\to\mathbb R$，有 $\big|\max_a f(a)-\max_a g(a)\big|\le\max_a\big|f(a)-g(a)\big|$。
证： 设 $a^\star=\arg\max_a f(a)$，则 $\max_a f-\max_a g\le f(a^\star)-g(a^\star)\le\max_a|f-g|$；交换 $f,g$ 得反向不等式，取绝对值即证。$\square$

记 $Q_i(s,a)=r(s,a)+\gamma\sum_{s'}P(s'|s,a)V_i(s')$，则 $(\mathcal T^\star V_i)(s)=\max_a Q_i(s,a)$。完整链条：

$$\begin{aligned} \big|(\mathcal T^\star V_1)(s)-(\mathcal T^\star V_2)(s)\big| &=\Big|\max_a Q_1(s,a)-\max_a Q_2(s,a)\Big| &&\text{(定义)}\\ &\le \max_a\big|Q_1(s,a)-Q_2(s,a)\big| &&\text{(max 引理)}\\ &=\max_a\Big|\gamma\!\sum_{s'}P(s'|s,a)\big(V_1(s')-V_2(s')\big)\Big| &&(r\ \text{相消})\\ &\le \gamma\,\max_a\sum_{s'}P(s'|s,a)\,\big|V_1(s')-V_2(s')\big| &&\text{(三角不等式)}\\ &\le \gamma\,\max_a\sum_{s'}P(s'|s,a)\,\|V_1-V_2\|_\infty &&(\text{逐点}\le\text{上确界})\\ &=\gamma\,\|V_1-V_2\|_\infty &&\big(\textstyle\sum_{s'}P=1\big). \end{aligned} \tag{11.6}$$

右端与 $s$ 无关，对左端取 $\max_s$ 即得 $\|\mathcal T^\star V_1-\mathcal T^\star V_2\|_\infty\le\gamma\|V_1-V_2\|_\infty$。整条链只在两处用到结构：$\sum_{s'}P=1$ 且 $P\ge0$（随机矩阵是 $\ell_\infty$ 非扩张），以及折扣 $\gamma<1$ 提供严格收缩。 把 $\max_a$ 换成 $\mathbb E_{a\sim\pi}$ 整条链原样成立（期望同为凸组合、不放大 $\|\cdot\|_\infty$），故 $\mathcal T^\pi$ 亦为 $\gamma$-压缩。$\square$

本质 Insight

压缩性说的是：每做一次精确贝尔曼更新，你与真解的最大误差至多变为原来的 $\gamma$ 倍。 这是表格值迭代收敛的核心；表格 Q-learning 还需要充分访问、合适的 Robbins–Monro 步长和有界噪声等随机逼近条件。注意压缩保证只在无穷范数下、精确算子下直接成立——第 6 节会看到，函数逼近引入的投影会改变问题。

3. 收敛速率与 γ 的角色

由 $\|V_k-V^\star\|_\infty\le\gamma^k\|V_0-V^\star\|_\infty$，要把误差压到 $\epsilon$ 所需迭代数为

$$k\;\ge\;\frac{\log(\|V_0-V^\star\|_\infty/\epsilon)}{\log(1/\gamma)}\;\approx\;\frac{1}{1-\gamma}\log\frac{R_{\max}}{(1-\gamma)\epsilon}, \tag{11.7}$$

（式中 $R_{\max}$ 是单步奖励的幅度上界，用于界定价值的量级 $V\le\frac{R_{\max}}{1-\gamma}$；它只影响对数项里的常数，不改变收敛的几何速率。）用到 $\log(1/\gamma)=-\log\gamma=(1-\gamma)+\tfrac{(1-\gamma)^2}{2}+\cdots\approx 1-\gamma$（当 $\gamma\to1$；相对误差约 $\tfrac{1-\gamma}{2}$，如 $\gamma=0.99$ 时仅约 $0.5\%$）。这里冒出了 RL 理论里最重要的一个量：

$$\boxed{\;\text{有效视野 (effective horizon)}\;H_{\mathrm{eff}}\approx\frac{1}{1-\gamma}\;} \tag{11.8}$$

举例

具体感受一下”每轮误差 $\times\gamma$ 收缩”：设 $\gamma=0.9$、初始误差 $\|V_0-V^\star\|_\infty=10$。第 1 轮后变 $10\times0.9=9$，第 2 轮 $8.1$，第 10 轮 $10\times0.9^{10}\approx3.5$。要缩到原来的 $1/10$（即 $\le1$），需 $0.9^k\le0.1$，解得 $k\approx22$ 轮；缩到 $1/100$ 约需 $44$ 轮。这里有效视野 $H_{\rm eff}=\frac{1}{1-0.9}=10$，恰是”误差每衰减一个 $e$ 倍”所需的步数量级。若换成 $\gamma=0.99$，同样缩到 $1/10$ 竟要约 $229$ 轮——视野拉长 10 倍，收敛也慢了约 10 倍，这就是长视野任务”又慢又难”的数值直观。

图 1：收敛速率由 $\gamma^k$ 决定。$\gamma\to1$ 时有效视野 $\frac{1}{1-\gamma}$ 爆炸，是长视野任务困难的根源。

为什么 $\frac{1}{1-\gamma}$ 无处不在

它是”一个决策的影响会往后传播多少步”的尺度：几何级数 $\sum_t\gamma^t=\frac{1}{1-\gamma}$。因此它同时是收敛所需迭代数、价值的量级上界 $V\le\frac{R_{\max}}{1-\gamma}$、以及误差放大因子。很多界里是 $\frac{1}{(1-\gamma)^2}$ 甚至 $\frac{1}{(1-\gamma)^3}$——因为误差会在”值的尺度”和”传播步数”上各吃一次视野。这解释了实践中调 $\gamma$ 的两难：$\gamma$ 大更接近真实长期目标，但学习更难、方差更大。

深化拓展 · 把 $\frac{1}{(1-\gamma)^3}$ 逐层拆开：视野的幂次从哪来

后面第 4 节的样本复杂度里会冒出 $\frac{1}{(1-\gamma)^3}$，常让人费解——为什么恰是三次方？把有效视野 $H_{\rm eff}=\frac{1}{1-\gamma}$（式(11.8)）当作”一个决策向后影响多少步”的尺子，三层幂次就对应三次各自独立地吃到这把尺子：

• 第一层 · 值的量程（吃一次 $H_{\rm eff}$）。 回报是折扣和 $\sum_t\gamma^t r_t$，量级 $\|V\|_\infty\le\frac{R_{\max}}{1-\gamma}=R_{\max}H_{\rm eff}$。要把绝对误差压到 $\epsilon$，等于要把相对精度提高 $H_{\rm eff}$ 倍。
• 第二层 · 误差沿贝尔曼回传放大（再吃一次 $H_{\rm eff}$）。 单步估计误差经不动点迭代累积，$\|\hat Q-Q^\star\|_\infty\lesssim\frac{1}{1-\gamma}\,\|\text{单步误差}\|_\infty$——每一步的偏差都被后续视野反复搬运。
• 第三层 · 集中不等式里的方差沿视野累积（第三次 $H_{\rm eff}$）。 长回报的方差随视野增长；正是用方差感知的集中不等式（Bernstein + total-variance）已经省下一次视野，才把朴素 Hoeffding 分析的 $\frac{1}{(1-\gamma)^4}$ 收紧到 $\frac{1}{(1-\gamma)^3}$（详见第 4 节折叠推导）。

数值直观（逐层相乘）。 取 $\gamma=0.99$ 则 $H_{\rm eff}=100$：相比一个 $H_{\rm eff}=10$（$\gamma=0.9$）的短视野任务，仅”视野”这一项就要把样本量放大 $\big(\tfrac{100}{10}\big)^3=10^3=1000$ 倍；若再放到 $\gamma=0.999$（$H_{\rm eff}=1000$），相对 $\gamma=0.9$ 更是 $100^3=10^6$ 倍。这就是”$\gamma$ 往 1 挪一点点、学习难度却爆炸式上升”的定量根源——每多看一层未来，都得在量程、回传、方差三处各付一次视野的代价。

4. 表格 MDP 的样本复杂度直觉

假设有一个生成模型（generative model）：可以对任意 $(s,a)$ 采样下一状态。要学到 $\epsilon$-最优的 $Q$，每个 $(s,a)$ 大约需要多少样本？结论级结果（minimax 最优）：

$$\text{总样本数}\;\tilde\Theta\!\Big(\frac{S\,A}{(1-\gamma)^3\,\epsilon^2}\Big). \tag{11.9}$$

先厘清这些记号（下文反复出现）：$S=|\mathcal S|$ 是状态数、$A=|\mathcal A|$ 是动作数（表格规模即 $S\cdot A$）；$\epsilon$ 是想达到的目标精度（值误差容忍，“$\epsilon$-最优”指 $\|V^\pi-V^\star\|\le\epsilon$）；稍后出现的 $\delta$ 是允许的失败概率（结论以概率 $\ge1-\delta$ 成立）。$\tilde\Theta$（及后文 $\tilde O$）的波浪号意为”忽略对数因子”；$\Theta$ 表示同时卡住上、下界的紧阶，$O$ 只给上界、$\Omega$ 只给下界。引入这套渐近记号是为了只看主导因子、忽略常数与对数，从而一眼判断”难在哪个维度”。

因子逐项解读

• $S\cdot A$： 每个状态-动作对都得被采样若干次——没有泛化时，样本随表格大小线性增长。
• $1/\epsilon^2$： 标准的统计估计精度代价（蒙特卡洛误差 $\propto 1/\sqrt n$，要精度 $\epsilon$ 就要 $n\propto 1/\epsilon^2$）。
• $1/(1-\gamma)^3$： 视野吃三次。一次来自值的量级 $\frac{R_{\max}}{1-\gamma}$，一次来自误差通过贝尔曼回传的放大 $\frac{1}{1-\gamma}$，还有一次来自方差在长视野上的累积。这是长视野问题”数据饥渴”的理论根源。

举例

“要试多少次才敢说这策略够好？“——就像判断一枚硬币偏不偏：抛 $10$ 次估的正面率可能差出 $\pm0.15$，抛 $1000$ 次才收窄到 $\pm0.015$。这正是 $1/\epsilon^2$ 的含义——想把估计误差从 $0.1$ 砍到 $0.05$（精度翻一倍），样本得翻四倍。RL 还要在每个 $(s,a)$ 上各做一遍这件事（$S\cdot A$ 倍），且长视野让回报方差更大（再吃 $\frac{1}{(1-\gamma)^3}$）。于是一个看似很小的任务 $S=100,A=4,\gamma=0.99,\epsilon=0.1$，理论样本量就已达 $\frac{SA}{(1-\gamma)^3\epsilon^2}=\frac{400}{(0.01)^3(0.1)^2}\approx4\times10^{10}$ 这样的天文数字——这解释了为何无泛化的表格法一旦问题稍大就根本跑不动。

深入：PAC-MDP 的正式定义与 $\frac{1}{(1-\gamma)^3}$ 的三次方从哪来

PAC-MDP（正式）

称一个在线算法是 PAC-MDP 的，若以概率 $\ge1-\delta$，它执行 $\epsilon$-次优动作（$V^{\pi_t}(s_t)<V^\star(s_t)-\epsilon$）的总时刻数被 $\text{poly}(S,A,\tfrac{1}{1-\gamma},\tfrac1\epsilon,\tfrac1\delta)$ 界住。它不要求”每步都好”，只要求”犯明显错误的次数有限”。

三次 $\frac{1}{1-\gamma}$ 的来源（生成模型、$\ell_\infty$ 分析）。记 $H_{\rm eff}=\frac{1}{1-\gamma}$：

1. 值的量级：$\|Q^\star\|_\infty\le\frac{R_{\max}}{1-\gamma}=R_{\max}H_{\rm eff}$。要把绝对误差压到 $\epsilon$，等价于把相对精度提高 $H_{\rm eff}$ 倍 ⇒ 吃一次。
2. 误差经贝尔曼回传放大： 估计算子的单步误差在不动点处被放大，$\|\hat Q-Q^\star\|_\infty\le\frac{1}{1-\gamma}\|\hat{\mathcal T}Q^\star-\mathcal T Q^\star\|_\infty$ ⇒ 再吃一次。
3. 回报方差沿视野累积： 用 Bernstein（而非 Hoeffding）做方差感知分析时，总回报方差正比于 $H_{\rm eff}^2$，但配合”total variance”技巧（$\sum_t\mathrm{Var}\lesssim H_{\rm eff}$ 的贝尔曼式方差方程）省下一个 $H_{\rm eff}$，净得再吃一次。

三者相乘给出 $\frac{1}{(1-\gamma)^3}$，配上统计精度 $\frac{1}{\epsilon^2}$ 与表格规模 $SA$，即式(11.9)那个 minimax 最优的 $\tilde\Theta\!\big(\frac{SA}{(1-\gamma)^3\epsilon^2}\big)$。朴素分析（不用 Bernstein / total-variance）只能得到 $\frac{1}{(1-\gamma)^4}$——差的那一次视野正是”方差感知”省下来的。

注意这里没有 $T$（交互步数）也没有探索代价——因为生成模型假设你可以任意查询任意 $(s,a)$。一旦去掉这个假设、只能沿轨迹交互，探索就变成主角（第 8、9 节）。

5. Performance Difference Lemma

策略优化反复要回答同一个问题：换上新策略 $\pi'$，比旧策略 $\pi$ 究竟好多少，而且能不能只用旧策略手头的量（如旧优势 $A^\pi$）把这个差精确写出来？ 性能差异引理（Performance Difference Lemma, PDL） 正是回答它的”瑞士军刀”，给出无近似的恒等式：

$$J(\pi')-J(\pi)=\frac{1}{1-\gamma}\;\mathbb{E}_{s\sim d^{\pi'}}\;\mathbb{E}_{a\sim\pi'(\cdot|s)}\Big[A^\pi(s,a)\Big] \tag{11.10}$$

其中 $A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)$ 是旧策略的优势函数，$d^{\pi'}$ 是新策略的（折扣）状态访问分布。

推导：PDL（望远镜求和）

关键假设

折扣 MDP；$d^{\pi'}(s)=(1-\gamma)\sum_t\gamma^t\Pr[s_t=s\mid\pi']$ 为折扣占用测度。核心技巧是把 $J(\pi')-J(\pi)$ 写成沿 $\pi'$ 轨迹的望远镜（telescoping）和。

第 1 步。 沿 $\pi'$ 生成的轨迹，插入并抵消 $V^\pi$：

$$J(\pi')-J(\pi)=\mathbb E_{\tau\sim\pi'}\Big[\sum_t\gamma^t r_t\Big]-V^\pi(s_0). \tag{11.11}$$

第 2 步。 用望远镜恒等式 $V^\pi(s_0)=\mathbb E_{\tau\sim\pi'}\big[\sum_t\gamma^t\big(V^\pi(s_t)-\gamma V^\pi(s_{t+1})\big)\big]$（相邻项抵消只剩首项）。相减，把同一 $t$ 的项凑在一起：

$$=\mathbb E_{\tau\sim\pi'}\Big[\sum_t\gamma^t\big(r_t+\gamma V^\pi(s_{t+1})-V^\pi(s_t)\big)\Big]. \tag{11.12}$$

第 3 步。 括号内对 $\pi'$ 取期望即为优势 $A^\pi(s_t,a_t)$ 的期望（因 $\mathbb E[r+\gamma V^\pi(s')]=Q^\pi$）。把 $\sum_t\gamma^t$ 换成占用测度 $\frac{1}{1-\gamma}d^{\pi'}$ 即得式(11.10)。$\square$

本质 Insight 与用途

PDL 说：要提升策略，就在新策略会去到的状态上，让动作有正的旧优势。 麻烦在于期望是对新策略的访问分布 $d^{\pi'}$ 取的——而我们只有旧策略的数据。这正是信赖域/PPO的出发点：当 $\pi'$ 与 $\pi$ 足够接近时 $d^{\pi'}\approx d^\pi$，可用旧分布近似并给出单调改进界（见 模块 6）；也是离线 RL分布漂移问题的理论刻画（见 模块 9）。

6. 函数逼近下的发散

表格里一切美好，为何一上神经网络就爆？致命三要素（deadly triad）：函数逼近 + 自举 + 离策略，三者同时出现时，$Q$-learning/TD 可能发散。理论根源在于——引入了一个投影（projection） 步骤。

用参数化 $V_\theta$（如线性 $V_\theta=\Phi\theta$）时，$\mathcal T^\pi V_\theta$ 一般不在可表示的函数类里，必须投影回去。于是真正迭代的算子是投影贝尔曼算子 $\Pi\mathcal T^\pi$，其中 $\Pi$ 是在某个加权 $\ell_2$ 范数下到函数类的正交投影：

$$\theta_{k+1}:\quad V_{\theta_{k+1}}=\Pi\,\mathcal T^\pi V_{\theta_k},\qquad \Pi X=\arg\min_{\hat V\in\mathcal F}\|\hat V-X\|_{d}. \tag{11.13}$$

为什么会发散：范数不匹配

• $\mathcal T^\pi$ 是无穷范数 $\|\cdot\|_\infty$ 下的 $\gamma$-压缩。
• 投影 $\Pi$ 只在其加权 $\ell_2$ 范数 $\|\cdot\|_d$ 下才是非扩张（non-expansive）。
• 两个范数不一致 ⇒ 复合算子 $\Pi\mathcal T^\pi$ 不保证是任何范数下的压缩 ⇒ 不动点可能不存在或迭代发散。
• 关键前提是”离策略”：若在在策略分布 $d=d^\pi$ 下投影（on-policy TD），可证 $\Pi\mathcal T^\pi$ 在 $\|\cdot\|_{d^\pi}$ 下仍是 $\gamma$-压缩，收敛；一旦数据分布 $d\ne d^\pi$（离策略、经验回放、目标策略≠行为策略），压缩性失效——这就是 Baird 反例发散的机理。

补充刻画：即便收敛，近似解 $V_\theta$ 的误差被放大：$\|V_\theta-V^\pi\|_d\le\frac{1}{1-\gamma}\,\|\Pi V^\pi-V^\pi\|_d$——最好的可表示逼近误差被有效视野放大。

图 2：投影贝尔曼误差。贝尔曼算子把点拉近真解，但投影把它拽回函数类；离策略分布下二者不再协同，收敛保证失效。

线性代数视角：$\Pi\mathcal T^\pi$ 的谱半径与 Baird 发散

矩阵形式

线性逼近 $V_\theta=\Phi\theta$（$\Phi\in\mathbb R^{S\times d}$）。设 $D=\mathrm{diag}(d)$ 为状态权重、投影 $\Pi=\Phi(\Phi^\top D\Phi)^{-1}\Phi^\top D$、策略评估算子 $\mathcal T^\pi V=R+\gamma P^\pi V$。半梯度 TD 的期望迭代是 $\theta_{k+1}=\theta_k+\alpha\,\Phi^\top D\big(\mathcal T^\pi\Phi\theta_k-\Phi\theta_k\big)$，不动点由 $A\theta=b$ 给出，$A=\Phi^\top D(I-\gamma P^\pi)\Phi$。

收敛与谱条件。 对给定固定步长 $\alpha>0$，迭代 $\theta_{k+1}=(I-\alpha A)\theta_k+\alpha b$ 从任意初值收敛到唯一固定点的条件是 $\rho(I-\alpha A)<1$。若 $A$ 的所有特征值实部为正（$A$ 正稳定），则存在充分小的正步长使该谱半径小于 1；这不等价于任意给定 $\alpha$ 都稳定。

• 在策略（$d=d^\pi$）： 可证 $A$ 正定（$D_{d^\pi}(I-\gamma P^\pi)$ 关于该稳态测度正定），$\Pi\mathcal T^\pi$ 在 $\|\cdot\|_{d^\pi}$ 下仍是 $\gamma$-压缩 ⇒ 必收敛。
• 离策略（$d\ne d^\pi$）：$A$ 可能出现负实部特征值。量化：设 $A$ 有特征值 $\lambda=\mathrm{Re}\,\lambda+i\,\mathrm{Im}\,\lambda$，则迭代矩阵 $I-\alpha A$ 对应特征值为 $1-\alpha\lambda$，其模平方 $|1-\alpha\lambda|^2=(1-\alpha\,\mathrm{Re}\,\lambda)^2+(\alpha\,\mathrm{Im}\,\lambda)^2$。只要 $\mathrm{Re}\,\lambda<0$，就有 $1-\alpha\,\mathrm{Re}\,\lambda>1$，故 $|1-\alpha\lambda|>1$ 对任意步长 $\alpha>0$ 成立。于是 $\rho(I-\alpha A)>1$；若初始误差在对应不稳定特征方向上有非零分量，该分量会按 $|1-\alpha\lambda|^k$ 指数增长。落在稳定不变子空间或恰为固定点的初值不受此结论约束。Baird 星形反例正是精心构造 $\Phi$ 与离策略分布，使 $A$ 出现负实部特征值，并可使含不稳定分量的参数序列指数发散。

本质：$\gamma P^\pi$ 是 $\ell_\infty$ 压缩、$\Pi$ 只在 $\ell_2(d)$ 下非扩张；离策略把 $d$ 拧离 $d^\pi$ 后，两者的”友好范数”错位，复合算子的谱半径可越过 1。GTD/TDC 的补救就是直接最小化 MSPBE $\|\Pi\mathcal T^\pi V_\theta-V_\theta\|_d^2$，把半梯度换成真梯度以恢复稳定。

图 3：线性 TD 的谱视角。在策略时 $\Pi\mathcal T^\pi$ 谱半径 $<1$ 收敛；离策略可使某特征值越出单位圆，含相应不稳定分量的误差指数增长（Baird 反例）。

实践对策

目标网络（缓慢更新、近似冻结 $\mathcal T$ 的目标）、经验回放去相关、更小学习率、gradient TD（GTD/TDC，直接最小化投影贝尔曼误差 MSPBE 而非 semi-gradient）、以及离线 RL 里的保守约束（CQL/IQL）都是在人为恢复某种压缩/稳定性。这也解释了模块 5”致命三要素”为何是深度 Q 学习一切工程技巧的理论动机。

本质 Insight · 断裂点就在这里

退一步俯瞰：贝尔曼算子的 $\gamma$-压缩性（第 2 节）是精确值迭代与许多价值分析的核心起点，但不是所有价值方法收敛的唯一依据——表格值迭代、Q-learning 能收敛，全靠它。而函数逼近引入的投影 $\Pi$ 恰恰是在加权 $\ell_2$ 范数下操作，与 $\|\cdot\|_\infty$ 下的压缩互不兼容，复合算子 $\Pi\mathcal T^\pi$ 不再保证压缩——地基由此崩裂。这就是理论与深度实践真正的断裂点，也是模块 5”致命三要素”的数学内核：深度 Q 学习之所以难稳，不是”炼丹没调好”，而是收敛保证被从根上抽掉了，一切工程技巧都在事后人为地把某种稳定性补回来。

7. 策略梯度的收敛性

策略梯度（PG）直接对可微目标 $J(\theta)$ 做（随机）梯度上升，因此可沿用非凸优化的标准分析：在相应假设下讨论收敛到一阶驻点。一阶驻点也可能是鞍点或劣质局部极值，不能直接称为局部最优。

结论与假设

• 结论（渐近）： 若 $J$ 光滑、梯度估计无偏且方差有界，并满足迭代有界等随机逼近条件，Robbins–Monro 步长（$\sum_t\eta_t=\infty,\sum_t\eta_t^2<\infty$）用于支持梯度趋于零或极限点为驻点的渐近结论；具体口径还取决于定理条件。
• 结论（有限步率）： 对预先给定的总步数 $K$，取常步长 $\eta=O(K^{-1/2})$，可得到 $\min_{k<K}\mathbb E\|\nabla J(\theta_k)\|^2=O(K^{-1/2})$，或等价地对按相应权重抽取的输出迭代点给出期望界。该步长安排不满足无限序列的平方可和条件。
• 结论（全局，softmax + 精确梯度）： 近年结果表明，表格 softmax 参数化下带正则或用自然梯度（NPG）时，PG 可全局收敛到最优，速率与 $\frac{1}{1-\gamma}$ 及”分布不匹配系数” $\big\|\frac{d^{\pi^\star}}{d^\pi}\big\|_\infty$ 有关。
• 关键假设/局限：(1) 需要充分探索——若某状态从不被访问，其上策略永不更新，得到的驻点可能离全局最优很远；(2) 无偏梯度要求正确的因果/baseline 处理；(3) 全局结论依赖 softmax 的良性 landscape，一般神经网络参数化下通常只能讨论一阶驻点。

推导骨架：为何 SGD 只保证收敛到驻点，以及非凸性的后果

非凸下的标准结论

设 $J$ 的梯度 $L$-Lipschitz（$\|\nabla J(\theta)-\nabla J(\theta')\|\le L\|\theta-\theta'\|$）、随机梯度 $g_k$ 无偏 $\mathbb E[g_k]=\nabla J(\theta_k)$、方差 $\mathbb E\|g_k-\nabla J\|^2\le\sigma^2$。梯度上升 $\theta_{k+1}=\theta_k+\eta g_k$。

下降（上升）引理。 由 $L$-光滑：$J(\theta_{k+1})\ge J(\theta_k)+\langle\nabla J(\theta_k),\eta g_k\rangle-\tfrac{L\eta^2}{2}\|g_k\|^2$。两边取期望、代入无偏与方差界：

$$\mathbb E[J(\theta_{k+1})]\ge \mathbb E[J(\theta_k)]+\eta\Big(1-\tfrac{L\eta}{2}\Big)\mathbb E\|\nabla J(\theta_k)\|^2-\tfrac{L\eta^2}{2}\sigma^2. \tag{11.14}$$

取 $\eta\le\frac1L$，对 $k=0,\dots,K-1$ 求和并除以 $K$，移项得

$$\min_{k<K}\mathbb E\|\nabla J(\theta_k)\|^2\le \frac{2\big(J^\star-J(\theta_0)\big)}{\eta K}+L\eta\sigma^2. \tag{11.15}$$

取 $\eta\propto1/\sqrt K$ 得 $\min_{k<K}\mathbb E\|\nabla J(\theta_k)\|^2=O(1/\sqrt K)$——只保证梯度范数趋 0，即收敛到一阶驻点，不保证是全局最优。

非凸性的三个后果。(1) 可能停在鞍点/劣质局部最优（$J(\theta)$ 关于策略参数一般非凸）；(2) 探索耦合：$\nabla J=\mathbb E_{d^\pi}[\cdots]$ 只在被访问的状态上有信号，从不被访问处策略永不更新——“驻点”可能因探索不足而离全局最优很远；(3) 高方差使 $\sigma^2$ 大 ⇒ 需 baseline / 优势估计压方差才实用。反差：softmax 表格参数化下目标满足梯度控制条件（gradient domination / PL 型），此时驻点即全局最优、NPG 甚至有 $O(1/K)$ 全局速率——但这依赖良性 landscape，一般深网不具备。

本质 Insight

值方法与策略梯度在理论上是 “稳定性 vs 可表示性”的权衡：值迭代有压缩性的强收敛保证（表格），但函数逼近+离策略会毁掉它；策略梯度在满足光滑、无偏或可控偏差、有界方差与合适步长等假设时可收敛到驻点；离开这些条件仍可能震荡、数值爆炸或性能崩溃——它把一类离策略发散风险换成了驻点质量、高方差与探索问题。

8. 探索的下界

没有生成模型、只能沿轨迹交互时，探索代价成为不可回避的下界。一个干净的直觉构造是”组合锁 MDP（combination-lock / chain）“：一条长度为 $H$ 的链，每步有 $A$ 个动作，只有唯一一条正确动作序列能到达终点的奖励，其余全为零。

下界直觉

随机策略要偶然走对整条长度 $H$、每步 $A$ 选一的链，概率约 $A^{-H}$，期望需要 指数级 $\Omega(A^H)$ 次尝试。更一般地，信息论下界表明：任何算法要在最坏情况 MDP 上达到 $\epsilon$-最优，样本数至少 $\Omega\!\big(\frac{SA}{\epsilon^2}\cdot\text{poly}(H)\big)$——即 $\Omega(SA)$ 是绕不过去的（每个状态-动作至少要”见”若干次才能区分好坏），且长视野带来 poly($H$) 的额外代价。

含义：$SA$ 这个因子在上界（第 9 节 UCB-VI）与下界里同时出现，说明它是本质的、不可改进的（除非引入结构假设如线性 MDP、低秩、平滑，才能把 $S$ 换成特征维度 $d$）。

为什么这样 · 能不能不这样

为什么 RL 理论普遍盯着”最坏情况”的界（minimax、$\Omega(\cdot)$ 下界），而不是”平均情况”？（1）最坏情况这个形式给的是保证 / 可证明性：一个 $\tilde O(\sqrt{HSAT})$ 上界（式(11.16)）意味着无论对手把 MDP 设计得多刁钻，代价都不超过它；而下界 $\Omega(SA)$ 则证明这份难度是问题固有、任何聪明算法都绕不过。这种”对所有实例都成立”的陈述，才配作算法的安全边界。（2）换成平均情况会怎样：得先假定一个”任务分布”，界会漂亮得多、也更贴近实测——但它对分布假设极其敏感，一旦真实任务偏离所设分布，保证瞬间失效，属于乐观但脆弱；且不同工作各挑对自己有利的分布，结论无法横向比较。代价对照：最坏界常常太悲观、离实测很远（第 10、11 节的理论-实践鸿沟），却换来了普适、可比较、能”排除死路”的确定性——这正是理论要的东西。

本质 Insight

探索下界告诉我们：“没有免费的午餐”——在无结构的一般 MDP 里，最坏情况下探索代价必然随状态动作空间与视野增长。 深度 RL 之所以能在实践中远好于最坏界，是因为真实世界有大量可利用的结构（平滑性、局部性、可迁移的表示）。理论下界的价值不是吓人，而是精确指出”要想更快，必须假设什么结构”。

9. PAC-MDP 与 regret 界

两套刻画”边学边做”效率的框架：

• PAC-MDP：“犯大错的次数有限”——除了至多 $\text{poly}(S,A,\frac{1}{1-\gamma},\frac1\epsilon,\frac1\delta)$ 步是 $\epsilon$-次优的，其余步都近似最优（概率 $\ge1-\delta$）。代表：$E^3$、R-MAX、MBIE。
• Regret： 与最优策略相比的累积损失 $\mathrm{Reg}(T)=\sum_k\big(V^\star-V^{\pi_k}\big)$。代表：UCB-VI（有限视野表格 MDP）。

以 UCB-VI（对 $Q$ 做值迭代时给每个 $(s,a)$ 加一个 $\propto1/\sqrt{N(s,a)}$ 的乐观奖励加成）为例，UCBVI-BF 的高概率界（$H$ 为每幕步数，$T=KH$ 为总步数）包含 ^[1]：

$$\boxed{\;\mathrm{Reg}(T)=\tilde O\big(\sqrt{H\,S\,A\,T}+H^2S^2A+H\sqrt T\big)\;} \tag{11.16}$$

当 $T\ge H^3S^3A$ 且 $SA\ge H$ 等范围条件成立时，主项可化为 $\tilde O(\sqrt{HSAT})$；脱离这些条件不能只写主项。

逐因子读法（重点）

• $\sqrt{T}$： 遗憾的黄金标准，平均每步遗憾 $\to0$（$\mathrm{Reg}/T\propto1/\sqrt T$）——意味着算法最终学会近最优。来源与 bandit 一样：置信半径 $\propto1/\sqrt{N}$，累加 $\sum1/\sqrt{N}\propto\sqrt{T}$。
• $\sqrt{SA}$： 状态-动作空间越大，要探索的”格子”越多；与第 8 节下界的 $SA$ 相呼应，是本质的（无结构时）。
• $\sqrt{H}$（或某些分析里 $H^{3/2}$）： 视野因子。每一幕内误差会沿 $H$ 步传播，长幕更难。有限视野这里用 $H$，折扣情形对应 $\frac{1}{1-\gamma}$。
• $\tilde O$： 藏起了 $\log$ 因子（来自并集界/置信水平的 $\log(SAT/\delta)$）。

在上述主项占优的范围内，把式(11.16)与下界 $\Omega(\sqrt{HSAT})$ 对照，可见其主项达到相应 minimax 阶。会读界的收益：看到 $\sqrt{SA}$ 就知道”缩小有效状态空间/共享表示”能直接降低样本量——这正是深度 RL 用神经网络做泛化、以及模块 12 迁移学习的意义。

深入：regret ↔ PAC 转换，与 $\sqrt H$ 里的方差感知

• regret → PAC（online-to-batch）： 把 $\mathrm{Reg}(K)$ 写成幕数 $K$、每幕值域 $\le H$ 的形式后，随机挑一幕的策略，其期望次优度 $\le\mathrm{Reg}(K)/K=\tilde O(\sqrt{H^2SA/K})$。令它 $\le\epsilon$ 解出 $K=\tilde O(H^2SA/\epsilon^2)$——次线性 regret 自动给出 PAC 样本复杂度。
• $\sqrt{T}$： 置信半径 $\propto1/\sqrt{N(s,a)}$，沿访问累加 $\sum_{n}1/\sqrt n\propto\sqrt{N}$，全体求和给 $\sqrt{SAT}$ 量级——与 bandit 同源。
• $\sqrt{H}$ vs $H^{3/2}$： 朴素 Hoeffding 分析把每步值域 $\le H$ 直接代入得 $H^{3/2}$；Bernstein + total-variance（利用”一幕内各步回报方差之和 $\le H^2$ 而非 $H\cdot H^2$“的贝尔曼方差方程）省掉一个 $\sqrt H$，逼近下界 $\Omega(\sqrt{HSAT})$。这与第 4 节 $\frac{1}{(1-\gamma)^3}$（而非 $^4$）省下的是同一个方差感知技巧。
• $\tilde O$： 吞掉 $\log(SAT/\delta)$——来自对所有 $(s,a)$、所有幕做并集界以保证乐观加成”高概率有效”。

图 4：UCB-VI 的次线性遗憾。$\sqrt T$ 保证长期近最优；$\sqrt{HSA}$ 量化问题固有难度。

批判性追问 · “有了收敛/regret 界，深度 RL 就有保证了”？

本讲这些漂亮的界，几乎无一能直接套在你真正跑的深度网络上。(1) 假设太强、几乎不迁移：收敛性依赖 tabular（第 2–3 节），样本 / regret 界依赖 tabular 或线性 / 低秩 MDP（第 4、9、10 节），还常暗含 ergodic / 良好混合、奖励有界、可精确取 $\arg\max$ 等——非线性函数逼近加非平稳回放缓冲一个都不满足，而第 6 节恰恰证明此时压缩性被打破、可发散。(2) 价值在”概念澄清”而非”预测性能”：$\tilde O(\sqrt{HSAT})$、$\frac{1}{(1-\gamma)^3}$ 告诉你”难在长视野、难在状态空间”，是一张定性地图；但拿它去预测”我这个任务要几步收敛”几乎必然离谱（第 11 节会点明：这类界往往既太悲观又太乐观）。(3) 连”收敛到哪”都要小心：策略梯度只保证到驻点 / 局部（第 7 节），“全局最优”结论仅在 softmax + 精确梯度等良性设定下才成立。正确用法是拿界来建立直觉、指明瓶颈、排除死路，而不是把渐近阶当成工程仪表盘——这也是稍后编者按要反复强调的立场。

10. 线性/低秩 MDP 与结构假设：把 $S$ 换成 $d$

第 8、9 节的 $\sqrt{SA}$、下界里的 $\Omega(SA)$ 都在说：无结构的一般 MDP，样本量必随状态动作数增长——这对像素级 $S$ 是灾难。深度 RL 能远好于最坏界，靠的就是真实问题有结构可假设，从而把 $S$ 换成一个小得多的特征维度 $d$。这也是模块 12 迁移 / 表示学习的理论根据。

为什么这样 · 能不能不这样

为什么这些收敛与复杂度结论几乎都证在 tabular 或线性/低秩 MDP 上，而不直接证在你真正跑的深度网络上？（1）选 tabular/线性这层抽象，是因为它恰好保住了证明所需的两根支柱：值函数可被精确（或按式(11.17)线性）表示，且贝尔曼算子的 $\gamma$-压缩性（式(11.2)）在对应范数下不被破坏——于是不动点存在、迭代收敛、样本量可被 $S,A,d,\frac{1}{1-\gamma}$ 干净地刻画。（2）直接证深度网络会怎样：神经网络参数化下目标非凸，且函数逼近引入的 $\ell_2$ 投影与 $\ell_\infty$ 压缩互不兼容（第 6 节），复合算子 $\Pi\mathcal T^\pi$ 不再是任何范数下的压缩，Baird 反例更表明迭代可指数发散——收敛性这块”地基”被抽掉，几乎没有非平凡的全局保证可证。代价对照：tabular/线性的结论只能当一张定性地图（难在长视野、难在状态空间），迁移到深度实践时既太悲观又太乐观；但这是当前唯一能给出可证明陈述的抽象层，故先在这里把问题的形状看清，再靠结构假设（式(11.18) 把 $S$ 换成 $d$）向深度实践架桥。

线性 MDP（Jin et al. 2020）

假设存在已知特征 $\phi(s,a)\in\mathbb R^d$，使转移与奖励都关于 $\phi$ 线性：

$$P(s'\mid s,a)=\langle\phi(s,a),\mu(s')\rangle,\qquad r(s,a)=\langle\phi(s,a),w\rangle. \tag{11.17}$$

关键推论：由式(11.17)的线性结构，任意策略的 $Q^\pi$ 也是 $\phi$ 的线性函数 $Q^\pi(s,a)=\phi(s,a)^\top\theta^\pi$——于是可用岭回归 + 椭球置信集（LinUCB 式加成 $\beta\sqrt{\phi^\top\Lambda^{-1}\phi}$） 做乐观值迭代（LSVI-UCB），其 regret 为

$$\boxed{\;\mathrm{Reg}(T)=\tilde O\big(\sqrt{d^3 H^3 T}\big)\;} \tag{11.18}$$

对照一般 MDP 的式(11.16)，此处 $S,A$ 彻底消失、被 $d$ 取代——这正是”泛化能买到样本效率”的严格版本。

更弱的假设是低秩 MDP：$\phi$ 未知、需一并学出（表示学习），代价是分析更难、常需 oracle。谱系上：表格 MDP ⊂ 线性 MDP ⊂ 低秩 MDP ⊂ 一般 MDP，越往右越贴近深度 RL，理论保证也越弱。

本质 Insight

结构假设的意义不是”让证明好写”，而是精确回答第 8 节下界抛出的问题——“要想绕过 $\Omega(SA)$，你必须假设什么？” 答案是：假设值函数落在一个低维（$d$ 维）可表示族里。深度网络学到的表示 $\phi$ 若真能让 $Q$ 近似线性，样本复杂度就从 $\text{poly}(S)$ 掉到 $\text{poly}(d)$。这是”表示学习 = 样本效率”这一深度 RL 信条的理论心脏，也解释了为何模块 12 的后继特征、共享表示能加速迁移。

图 5：MDP 结构谱系。假设越强，复杂度里的 $S$ 越能被特征维度 $d$ 取代，这是深度 RL 用表示学习换样本效率的严格背书。

方法溯源：动机 · 启发 · 局限

理论模块的”方法”其实是一件件思想工具。把它们按”为回答什么疑问而生 → 受什么数学传统启发 → 边界在哪 → 逼出下一个工具”排开，正好复现主线：为何需要保证 → 表格情形的收敛 → 函数逼近如何破坏它 → 理论与深度实践的鸿沟。这里的溯源侧重”这些理论工具是为解决什么疑问而生”。

工具 / 代表作（年代）	为回答什么疑问	启发 / 脉络	关键局限（→ 引出谁）
贝尔曼算子压缩性（Bellman 1957；Banach 不动点）	“值迭代 / Q-learning 到底收不收敛、收敛到哪？”	动态规划 + 压缩映射的 Banach 不动点定理	只在 $\Vert \cdot\Vert _\infty$、精确表示下成立；表格假设 → 样本复杂度与函数逼近两大追问
PAC-MDP 样本复杂度（E³ 1998、R-MAX 2002、Kakade 2003）	“要学到 $\epsilon$-最优，究竟需要多少样本？”	把监督学习的 PAC 框架搬进 MDP；生成模型下的 minimax 分析	表格、最坏情况；界含显式 $S,A$ → 结构假设（线性 MDP）
regret 界 / UCB-VI（Azar 2017）	“边学边做时，累积损失能否次线性？”	bandit 的 $1/\sqrt{N}$ 乐观加成搬到值迭代；Bernstein 方差感知	表格；$\sqrt{SA}$ 对像素级 $S$ 是灾难 → 线性/低秩 MDP
致命三要素 & 投影贝尔曼误差（Baird 1995、Tsitsiklis–Van Roy 1997）	“为什么一上函数逼近就发散？”	投影的 $\ell_2$ 与压缩的 $\ell_\infty$ 范数不匹配；Baird 星形反例	诊断出病因却不自动给出稳定算法 → GTD / 目标网络 / 保守约束
线性 / 低秩 MDP（Jin 2020；Agarwal 等）	“凭什么深度 RL 能远好于 $\Omega(SA)$ 最坏界？”	用特征线性结构把 $S$ 换成维度 $d$；LinUCB 椭球置信集	需已知/可学的良好特征；低秩下分析更难 → 通往表示学习 / 迁移（模块 12）

演进故事线 · 地基与它的两条隐含桩

整座 RL 理论大厦立在一块地基上：贝尔曼算子是 $\gamma$-压缩。它一句话回答了”为何值迭代必收敛”——每次更新把误差乘以 $\gamma$ 收缩。但这块地基有两条隐含的桩：无穷范数与精确表示。抽掉”精确表示”就冒出”要多少样本才近似得够好”（PAC-MDP、regret 界）；抽掉”无穷范数”——即引入函数逼近的 $\ell_2$ 投影——地基当场开裂（致命三要素）。理论工具正是沿着”哪根桩被抽掉”分化出来的。

演进故事线 · 表格的收敛与样本代价

在表格世界里理论最漂亮：压缩性给出几何收敛，PAC-MDP 与 UCB-VI 进一步把”边学边做”的代价钉死在 $\tilde\Theta\!\big(\frac{SA}{(1-\gamma)^3\epsilon^2}\big)$、$\tilde O(\sqrt{HSAT})$ 上，且上下界吻合、$SA$ 与 $\frac{1}{1-\gamma}$ 都被证明是本质的。这些界之所以珍贵，不在于精确预测步数，而在于告诉你——难在长视野、难在状态空间；同一个”方差感知（Bernstein + total-variance）“技巧同时替样本复杂度省下一个 $\frac{1}{1-\gamma}$、替 regret 省下一个 $\sqrt{H}$。

演进故事线 · 从裂缝到鸿沟，再靠结构补桥

函数逼近 + 自举 + 离策略三者同现，$\Pi\mathcal T^\pi$ 不再是任何范数下的压缩，Baird 反例表明含不稳定分量的参数序列可指数发散——这正是理论与深度实践的断裂点：深度 Q 学习难稳不是”炼丹没调好”，而是收敛保证被从根上抽掉，目标网络 / GTD / 保守约束都在事后把稳定性补回来。而要绕过 $\Omega(SA)$ 的最坏界，唯一出路是假设结构：线性/低秩 MDP 把 $S$ 换成特征维 $d$，这既是”表示学习 = 样本效率”的严格背书，也把接力棒交给了下一模块的迁移与表示学习。

图 6：RL 理论工具的谱系。压缩性是精确动态规划的核心起点；随机逼近、投影与结构假设还各有额外条件，函数逼近的 $\ell_2$ 投影撬开裂缝，结构假设把 $S$ 换成 $d$ 重新架起保证。

11. 理论与实践的鸿沟

把上面的界搬到深度 RL，会发现理论”太悲观”又”太乐观”：

举例

“界很松、实际却好得多”就像导航软件按最堵路况报时：最坏情况界（如 $\tilde O(\sqrt{HSAT})$）允许 MDP 具有最难探索和区分的结构；具体任务则可能具有可利用的平滑性、局部性或表示结构。因此，最坏情况界给出的是适用设定下的保证与难度形状（难在长视野、难在状态空间），不能与另一个具体深度 RL 任务的实测交互量直接作数值比较。

维度	理论（最坏情况）	深度 RL 实践
状态空间	$S$ 显式出现，指数/线性代价	神经网络泛化，$S$ 有效地被特征维度取代
收敛保证	表格值迭代必收敛	函数逼近+离策略可能发散，靠工程技巧稳住
探索	需乐观/后验采样才有 regret 保证	常用 $\epsilon$-greedy + 熵正则也能work（因环境有结构）
假设	已知/有限 MDP、有界奖励、i.i.d.	部分可观测、非平稳、奖励难设定

如何正确使用理论（收官 Insight）

理论不是用来精确预测”我要跑多少步”，而是用来回答定性问题、指明瓶颈、排除死路：
• 看到 $\frac{1}{1-\gamma}$ 的高次幂 → 长视野是主要困难，考虑更好的信用分配（$\lambda$-return、模型、层次化）。
• 看到致命三要素的发散分析 → 不要指望纯离策略 semi-gradient 稳定，加目标网络/保守约束。
• 看到 $\sqrt{SA}$ → 泛化与表示学习能直接买到样本效率，这是深度 RL 相对表格 RL 的根本优势，也是迁移/多任务（模块 12）的理论动机。
• 看到探索下界 → 一般 MDP 无捷径，能加速就得靠结构假设或先验。

前沿实践

将有限时域 RL 的视野因子类比到长序列任务，可以帮助理解信用分配为何随序列增长而变难；但具体系统可能采用在策略优化、离线偏好优化或混合流程，不能从本讲定理推出某类算法是行业默认。线性/低秩 MDP 中“把 $S$ 换成 $d$”的结果，则说明在相应结构假设下，表示维度可取代状态数进入复杂度界。

公开观点 · 理论 vs 规模

以下仅记录一项公开观点，不据此推断机构偏好。

• Sutton《苦涩的教训》(The Bitter Lesson, 2019)。 其公开主张可概括为：长期来看，能随算力规模化的通用方法（搜索与学习）总会压倒依赖人工注入领域知识的精巧设计。呼应本讲——可证明的收敛/复杂度界大多绑在 tabular 或线性/低秩 MDP 上，一旦换成深度网络（第 6 节的致命三要素）就不再成立，正是”精巧的人工结构难敌可规模化的通用做法”的一个注脚。

编者按 · 批判性视角

关于这些界，我想说句逆耳的话：regret 与样本复杂度界固然优美，但它们几乎都建立在 tabular 或线性 MDP 假设之上，并不迁移到深度 RL。$\tilde O(\sqrt{HSAT})$、$\frac{1}{(1-\gamma)^3}$ 这类结果的真正价值在于概念澄清（告诉你”难在长视野、难在状态空间”），而不在于预测真实系统的性能——拿它们去估计”我这个任务要跑多少步”几乎必然离谱。所以学理论是为了建立品味与直觉，不是把渐近界当工程仪表盘。对理论-实践鸿沟（第 10 节）要始终清醒：一个漂亮的界常常既太悲观（忽略了真实世界可利用的结构）又太乐观（假设了现实并不具备的平稳性与完全可观测）。别用它去指导工程决策，用它去理解问题的形状。