Lecture 7: 策略梯度 III 与模仿学习 —— GAE、单调改进、行为克隆与逆强化学习（Policy Gradients and Imitation Learning）

目录 · ← l6 · l8 →

Lecture 7: 策略梯度 III 与模仿学习 —— GAE、单调改进、行为克隆与逆强化学习（Policy Gradients and Imitation Learning）

对应材料：官方 lecture7pre.pdf / lecture7post.pdf（各 72 页；post 版为课后修订版，正文结构相同但在符号上与若干 Check-Your-Understanding 题干有差异——例如 post 在 PPO 一节把策略参数写作 $\omega$、目标写作 $\varepsilon_k\bar D_{KL}$，而 pre 用 $\theta$ 与 $\beta_k$；CYU 题干也有修订，如把 $\lambda=.99$ 改为 $\lambda=1$、把某选项的 bias 改为 variance。本笔记以 pre 的符号体系为准，两版冲突处以 pre 为主的讲义口径为准）｜Week 4 周三 Jan 28, 2026（A2 于 Feb 1 截止）｜参考阅读 Sutton & Barto Chp 13；Joshua Achiam 关于单调改进 / PPO / GAE 的讲义；Kakade & Langford (2002)、Schulman et al. (2015, TRPO)、Achiam et al. (2017)、Ross et al. (2011)、Ziebart et al. (2008) 一句话定位：本讲把「策略梯度」这条线收口——先用 GAE 解决优势函数怎么估的问题，再用单调改进理论回答「一步更新为什么不会让性能变差」，把 PPO/TRPO 从工程技巧升格为有理论保证的算法；随后转入本课程第三条主线模仿学习，讨论奖励难设计时如何直接从专家示范中学习策略（BC、DAgger）乃至反推奖励（MaxEnt IRL）。

7.1 概述

本讲要解决三件事，它们共同构成「策略梯度三部曲」的终章，并开启模仿学习的新篇章。

第一，优势函数到底怎么估（GAE）。 从 L5 的 REINFORCE 到 L6 的 PPO，策略梯度始终形如 $g = \mathbb{E}[\nabla_\theta \log \pi_\theta(a_t\vert s_t)\hat A_t]$。用 $G_t$ 估 $\hat A_t$（蒙特卡洛）方差极大，用 $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$（TD 残差）偏差极大。GAE（广义优势估计）用指数加权在两者之间连续插值，用一个超参数 $\lambda \in [0,1]$ 精确控制偏差–方差权衡，并且只需一次 $O(T)$ 的反向扫描。这是 PPO 在作业中必须实现的部分。

第二，一步更新为什么不会让性能崩溃（单调改进理论）。 策略梯度的病态在于：参数空间的距离不等于策略空间的距离。softmax 参数的一个微小改动可能让某个动作的概率从 0.99 掉到 0.01，性能一步崩盘且难以恢复。本讲的核心数学是性能差异引理（Performance Difference Lemma）——它把两个策略的性能差写成「新策略的状态分布 × 旧策略的优势函数」，由此导出替代目标（surrogate objective） $L_\theta(\theta^{\prime})$ 与相对性能界。把界当作目标函数去最大化，就得到保守策略迭代（Conservative Policy Iteration, CPI）与信任域策略优化（Trust Region Policy Optimization, TRPO），其核心是「用 KL 散度约束策略变化幅度」，并用自然梯度（natural gradient）预条件。

第三，没有奖励函数怎么办（模仿学习）。 讲义 p26 给出的动机链条很清楚：有些场景下存在非常好的决策策略，我们想把它自动化。一个直接想法是「让人类在 RL 算法做决策时提供奖励信号」——好处是监督形式简单、廉价，坏处是样本复杂度极高（人得盯着智能体的每一次尝试反复打分）。替代方案就是模仿学习。

讲义 p27–p28 进一步把问题定位到奖励塑形（reward shaping）：在时间上稠密的奖励能紧密引导智能体，但这样的奖励从哪来？手工设计往往很脆弱（often brittle）；另一条路是通过示范隐式地指定奖励（implicitly specify them through demonstrations）。讲义引用 Silver et al. 2010（复杂非结构化地形上的自主导航）与两个经典场景——模拟高速公路驾驶（Abbeel & Ng, ICML 2004；Syed & Schapire, NIPS 2007；Majumdar et al., RSS 2017）与停车场导航（Abbeel, Dolgov, Ng & Thrun, IROS 2008）。

讲义 p29 界定模仿学习的适用条件：专家提供一组示范轨迹（状态与动作的序列）；当「让专家演示期望行为」比「显式指定能产生该行为的奖励」或「直接指定期望策略」更容易时，模仿学习就有用。讲义 p30 给出问题设定：已知状态空间、动作空间、转移模型 $P(s^{\prime}\vert s,a)$ 与专家示范，但没有奖励函数 $R$；由此分出三条路线——行为克隆（能否直接用监督学习学出专家策略？）、逆 RL（能否恢复 $R$？）、经由逆 RL 的学徒学习（能否用恢复出的 $R$ 生成好策略？）。

本讲沿这三条路线展开：行为克隆（Behavior Cloning, BC） 直接把 $(s,a)$ 当监督学习；DAgger（Dataset Aggregation） 通过在线聚合专家标注，把 BC 的 $O(\epsilon T^2)$ 复合误差降到 $O(\epsilon T)$；逆强化学习（Inverse RL, IRL） 反过来从示范中恢复奖励函数，其中最大熵逆 RL（MaxEnt IRL） 用最大熵原理在无穷多可行奖励中挑出唯一解。

本讲的地位：向前它收束 L5–L6 的策略梯度主线（PPO 的最后一个拼图 GAE + 理论根基），向后它为 L8 的 RLHF/DPO（同样基于「示范与偏好」）和 L9–L12 的探索问题（奖励学习与偏好对）铺路。

7.2 核心概念的数学形式化

7.2.1 回顾：策略梯度的两个病态（讲义 p7）

策略梯度算法求解

讲义 p7 列出两个限制：样本效率差（每批数据用一次就丢），以及

距离在参数空间 $\neq$ 距离在策略空间！

严格定义：策略空间（policy space）在表格情形下是概率矩阵的集合

直观解释：参数 $\theta$ 是策略的「内部坐标」，而性能 $J$ 只依赖策略本身。参数空间是欧氏的、平坦的；策略空间是单纯形上的、弯曲的。沿参数空间的等长度步子，落到策略空间上可能极长也可能极短。

具体示例：二动作策略 $\pi_\theta(a=1) = \sigma(\theta)$、$\pi_\theta(a=2) = 1 - \sigma(\theta)$。在 $\theta = 5$ 处，$\sigma(5) \approx 0.993$；参数从 5 走到 3（变化 2），概率变成 $\sigma(3) \approx 0.953$（变化 0.04）。但在 $\theta = 0$ 处同样的参数变化 2 会让概率从 $0.5$ 变成 $0.881$（变化 0.38）——同样的参数步长，策略变化相差近 10 倍。这就是「步长难调」的根源，也是「性能崩溃」的机制。

与监督学习的对比：监督学习的损失对参数是光滑的，且数据分布固定；RL 中策略既决定损失又决定数据分布，一步坏更新会同时污染两者。

7.2.2 $n$ 步优势估计（讲义 p10）

严格定义：定义 TD 残差（TD residual）

则 $n$ 步优势估计为

推导（讲义 p10 所说的 telescoping sum）：

后一个和式逐项相消（telescoping），只剩 $-\gamma^0 V(s_t) + \gamma^n V(s_{t+n})$，即得结论。$\square$

直观解释：$n$ 步估计用真实奖励替换前 $n$ 步、用 critic 自举（bootstrap）剩下的部分。$n$ 越大越依赖真实回报（偏差小、方差大），$n$ 越小越依赖 $V$（偏差大、方差小）。

具体示例（本讲代码实验的 5 状态 MDP，$\gamma = 0.95$，精确 $V^\pi = [-0.6885, -0.6388, -0.3622, -0.0411, 0]$，$V(s_0) = -0.68853$）。实验脚本中打印的 $t=0$ 处数值为：$\hat A^{(1)}_0 = -0.015573$，$\hat A^{(2)}_0 = -0.030368$，$\hat A^{(3)}_0 = -0.044423$，$\hat A^{(5)}_0 = -0.070460$，$\hat A^{(10)}_0 = -0.095226$。可见随 $n$ 增大，估计值单调趋向 MC 优势（该轨迹的 $G_0 - V(s_0) = -0.274118$）。

与监督学习/前序方法的对比：$n=1$ 对应 L3 的 TD(0) 目标，$n \to \infty$ 对应 $G_t$（L5 的 REINFORCE）。GAE 的价值就在于把离散的 $n$ 变成连续的 $\lambda$。

7.2.3 广义优势估计 GAE（讲义 p11–p16）

严格定义：讲义把 GAE 定义为 $k$ 步估计的指数加权平均（权重 $(1-\lambda)\lambda^{k-1}$，$k = 1,2,\dots$）：

推导（讲义 p12 的代数化简，逐项按 $\delta$ 重新分组）：

这是讲义 p12 给出的最终形式，出自 Schulman et al., High-Dimensional Continuous Control Using Generalized Advantage Estimation, ICLR 2016。

递推实现（讲义 p16 的 PPO 用法）：由上式立得单次反向扫描的 $O(T)$ 形式

PPO 只用截断版：$\hat A_t = \sum_{l=0}^{T-t-1}(\gamma\lambda)^l\delta_{t+l}$。讲义 p16 指出其收益：只需在环境里跑 $T$ 步就能更新一次，且梯度估计更准。

$\lambda$ 的端点语义（讲义 p13–p15 的 Check Your Understanding L7N2）：

L7N2 答案（讲义 p14）：题目问 $GAE(\gamma,0)$ 与 $GAE(\gamma,1)$ 的性质。b 和 d 为真——(b) $GAE(\gamma,0)$ 是 TD(0) 回报的优势函数；(d) $GAE(\gamma,0)$ 的偏差很可能大于 $GAE(\gamma,1)$。注意 (a) 与 (c) 是反的：$GAE(\gamma,1)$ 是 MC 而非 TD(0)，且 $GAE(\gamma,0)$ 方差更小。

一个必须小心的细节（来自本讲代码的实测）：加权平均式 $(1-\lambda)\sum_{k\ge1}\lambda^{k-1}\hat A^{(k)}$ 只在 $0 \le \lambda < 1$ 时有定义；$\lambda = 1$ 时它是「$0 \times$ 发散级数」的未定式，必须按极限（$k\to\infty$ 的 MC 优势）理解。代码实验验证了这一点：$\lambda = 1$ 时递推式给出 $-0.274118$，与直接计算的 $G_0 - V(s_0) = -0.274118$ 相差 $2.78\times10^{-16}$；而 $\lambda = 0.99$ 时两种写法差 $2.19\times10^{-2}$，这纯粹是级数截断到 $K=400$ 项的尾巴（$\lambda^K = 0.0180$，同量级），把 $K$ 加大即消失。

7.2.4 性能差异引理（Performance Difference Lemma，讲义 p18、L6 p33）

严格定义：对任意两个策略 $\pi, \pi^{\prime}$，

其中 折扣状态访问分布（discounted state visitation distribution） 定义为

注意 $d^\pi$ 已按 $(1-\gamma)$ 归一化，故 $\sum_s d^\pi(s) = 1$，可当作概率分布。L6 讲义明确说明「CS234 HW2 要求你们证明这个引理」。

直观解释：新策略 $\pi^{\prime}$ 的价值 = 旧策略 $\pi$ 的价值 + 新策略实际走过的状态分布下、旧策略优势函数的期望。「性能差完全由新策略的访问分布来衡量旧策略的优势。」

具体示例（本讲代码的 5 状态 MDP，$\gamma = 0.95$，$\pi$ 取脚本中的固定策略）。精确量：$V^\pi = [-0.6885, -0.6388, -0.3622, -0.0411, 0]$，$Q^\pi(s_0,\cdot) = [-0.6663, -0.7041, -0.7041]$，故 $A^\pi(s_0,\cdot) = [+0.0222, -0.0156, -0.0156]$；折扣访问 $d^\pi = [11.0966, 4.2426, 1.0788, 0.5472, 0.1517]$（未归一化形式 $\sum_t\gamma^t P(s_t=s)$）。取 $\pi^{\prime} = \pi$ 时引理给出 $0 = 0$，是自洽性检验。

与监督学习的对比：监督学习的泛化误差由训练分布与测试分布共同决定，但测试分布不依赖模型；这里 $d^{\pi^{\prime}}$ 依赖新策略本身，使得「改进策略」与「评估策略」耦合——这正是单调改进理论要拆解的对象。

7.2.5 替代目标与相对性能界（讲义 p18–p19）

严格定义：引理中的期望仍然对 $s\sim d^{\pi^{\prime}}$ 取，无法用旧策略的数据估计。讲义 p18 的做法是用 $d^\pi$ 近似 $d^{\pi^{\prime}}$（「上节课就用 $d^{\pi^{\prime}}$ 近似 $d^\pi$，为什么可以？」），得到替代目标（surrogate objective）

讲义紧接着给出相对性能界（relative policy performance bound，Achiam et al. 2017）：

其中 $D_{KL}(\pi^{\prime}\vert \pi)[s] = \sum_{a\in\mathcal{A}}\pi^{\prime}(a\vert s)\log\frac{\pi^{\prime}(a\vert s)}{\pi(a\vert s)}$，$C$ 是与 $\gamma$ 和优势上界有关的常数。由此（讲义 p19）

直觉解释：替代目标只在 $\pi^{\prime}$ 与 $\pi$ 的 KL 距离小时才是好近似。上式给出一个下界：只要最大化右边，真实性能 $J(\pi^{\prime})$ 就保证不低于 $J(\pi)$。讲义称之为对真实目标 $J(\pi^{\prime})$（左边 LHS）的 majorize-maximize 算法，并强调 $L_\pi(\pi^{\prime})$ 与 KL 项都能用来自 $\pi$ 的样本估计（p19）。

具体示例：作业中你会看到，若 $\pi^{\prime} = \pi$ 则 $L_\pi(\pi) \propto \mathbb{E}{s,a\sim d^\pi,\pi}[A^\pi(s,a)] = 0$ 且 $D{KL} = 0$，右边恰为 0，下界退化为 $J(\pi) \ge J(\pi)$，紧。

教材补充（讲义本文未给出，为完整性列出）：上述界的显式系数版本见 Kakade & Langford (2002) 与 TRPO 论文，它用总变差（total variation, TV） 距离而非 KL：

其中 $D_{TV}(p\vert q) = \tfrac12\sum_x\vert p(x) - q(x)\vert $。这正是 CPI（保守策略迭代） 的界。

务必区分：讲义 slide 本身只给出上面的 $\sqrt{\text{KL}}$ 形式（p18 式 (6)），且没有展开常数 $C$ 的表达式。带显式系数 $\frac{2\gamma\epsilon}{(1-\gamma)^2}$ 的 TV 版本并不在 L7 讲义中，它是 CPI/TRPO 文献里的经典结果，此处列出是为了让你看清「界从哪来、系数怎么长出来」。考试与作业请以讲义写法为准。

两个版本的方向是一致的：由 Pinsker 不等式

可知 $\max_s D_{TV} \le \sqrt{\tfrac12\max_s D_{KL}}$，故 TV 界也可写成 $\sqrt{\text{KL}}$ 的形式（代价是常数变紧/变松，取决于是否已对 $s$ 取 max）。注意 $C$ 在讲义中未给出显式表达式，这是有意的——讲义 p22 正是从「$C$ 在 $\gamma$ 接近 1 时非常大、没有好用的显式值」出发，引出 TRPO 的约束形式。

7.2.6 单调改进定理与证明（讲义 p19–p21）

严格定义（单调改进迭代）：设 $\pi_{k+1}$ 由下式给出

定理（单调改进）：$J(\pi_{k+1}) \ge J(\pi_k)$。

证明（讲义 p21 的三行论证，完整还原）：

1. $\pi_k$ 是可行点（feasible point）。
2. 在 $\pi^{\prime} = \pi_k$ 处目标函数取值恰为 0： \(L_{\pi_k}(\pi_k) \propto \mathbb{E}_{s,a\sim d^{\pi_k},\pi_k}\big[A^{\pi_k}(s,a)\big] = 0, \qquad D_{KL}(\pi_k\vert \pi_k)[s] = 0 .\) 第一式为零是因为 $\mathbb{E}{a\sim\pi_k}[A^{\pi_k}(s,a)] = \mathbb{E}{a\sim\pi_k}[Q^{\pi_k}(s,a)] - V^{\pi_k}(s) = V^{\pi_k}(s) - V^{\pi_k}(s) = 0$。
3. 故最优值 $\ge 0$。
4. 由性能界（7.2.5 的下界），$J(\pi_{k+1}) - J(\pi_k) \ge 0$。$\square$

讲义 p21 特别强调：这个证明在把优化域限定到任意参数化策略类 $\Pi_\theta$ 时仍然成立，只要 $\pi_k \in \Pi_\theta$。

直观解释：这是一个「保守但安全」的迭代——它宁愿步子小，也绝不让性能退步。

讲义 p22 指出的问题：$C$ 在 $\gamma$ 接近 1 时非常大，导致 (7.2.6) 的步长小到不可用。两个补救方向：(a) 调 KL 惩罚系数（$\Rightarrow$ PPO）；(b) 改用 KL 约束（称为信任域 / trust region）（$\Rightarrow$ TRPO）。

7.2.7 信任域与自然梯度（TRPO）

严格定义（TRPO 的约束优化形式）：

直观解释：把「惩罚」换成「硬约束」——不再去调那个不靠谱的常数 $C$，而是直接规定「策略最多只能走 $\delta$ 这么远」。$\delta$ 是可直接解释的物理量（如平均 KL 不超过 0.01），远比 $C$ 好调。

自然梯度（natural gradient）：目标是在策略空间的度量下做最速上升，而非在参数空间的欧氏度量下。做法是用 Fisher 信息矩阵（Fisher information matrix, FIM） 的逆做预条件（preconditioning）：

TRPO 的更新（讲义引用 Schulman et al. 2015 的结论形式）：

其中 $\sqrt{2\delta/(g^\top F^{-1}g)}\,F^{-1}g$ 的范数（在 Fisher 度量下）恰为 $\sqrt{2\delta}$，即取到信赖域边界的最长步。实用实现用共轭梯度（conjugate gradient）+ 线搜索近似求解，避免显式构造 $\vert {\theta}\vert ^2$ 大小的 $F$。

直观解释（为什么 Fisher 是对的距离）：KL 的二阶泰勒展开为

即 Fisher 矩阵就是 KL 散度的局部二次型，因此它正是「策略空间距离」在参数坐标下的度量张量。用它做预条件，等于「按策略变化的真实幅度」而非「按参数变化的数值」来定步长——直接回应了 7.2.1 的病态。

与 PPO 的关系：PPO 的自适应 KL 惩罚用

近似实现 KL 约束（$\beta_k$ 按「实测 KL $> 1.5\delta$ 就加倍，$< \delta/1.5$ 就减半」自适应）；PPO 的裁剪目标则干脆用重要性比率的分段线性函数绕开 KL 计算，代价是不再有 TRPO 那样严格的理论保证。

7.2.8 行为克隆与复合误差（讲义 p31–p38）

严格定义（Behavior Cloning, BC）：给定专家示范数据集 $\mathcal{D} = \{(s_i,a_i)\}_{i=1}^{N}$，把模仿问题归约为标准监督学习：固定一个策略类（神经网络、决策树等），用监督学习估计 $\hat\pi$。

直观解释：把专家的状态当输入、动作当标签，做分类。讲义 p32 把它概括为「把问题归约为标准监督学习问题：固定一个策略类（神经网络、决策树等），从训练样本 $(s_0,a_0),(s_1,a_1),\dots$ 估计策略」。

历史案例（讲义 p32–p33）：BC 有两个早期著名成功案例——

• Pomerleau, NIPS 1989：ALVINN（Autonomous Land Vehicle In a Neural Network）。用一个神经网络，输入是车载摄像头图像与激光测距的低分辨率 30×32 像素栅格，输出是转向方向；它让一辆车在公路上以最高约 55 mph 自主行驶。讲义 p33 专门用一页展示 ALVINN 的结构图。这是「模仿学习能真正开上车」的最早证据，也第一次暴露了 BC 的典型脆弱性：训练时人开得平稳，模型只在「车道中央」附近见过数据，一旦偏离就进入陌生分布。
• Summut et al., ICML 1992：Learning to fly in flight simulator——把同一思路用到飞行模拟器。

直观解释（为什么 ALVINN 的教训至今成立）：ALVINN 的输入分布完全由「人类驾驶员的转向」决定，模型自己一旦转向失误，看到的图像就偏离了训练分布（见 7.2.8 的复合误差分析）。讲义 p34 补充说 BC 在实践中常常非常有效，尤其是使用 BCRNN（行为克隆循环神经网络），并引用 What Matters in Learning from Offline Human Demonstrations for Robot Manipulation（Mandlekar et al., CoRL 2021），指出它「在实践被广泛使用」（extensively used in practice）。

复合误差（compounding errors）的推导（讲义 p36–p38，这是本讲必须给出的分析）：

1. 监督学习假设 $(s,a)$ 对是 iid（独立同分布）的，忽略了时间结构。
2. 若误差在时间上独立（讲义 p36）：每步以概率 $\le \epsilon$ 犯错，则 \(\mathbb{E}[\text{总错误}] \le \epsilon T.\)
3. 但在 MDP 中误差不独立（讲义 p37，数据分布不匹配）： \(\text{训练时 } s_t \sim d^{\pi^*}, \qquad \text{测试时 } s_t \sim d^{\pi_\theta}.\)
4. 近似直觉（讲义 p38）：第 $t$ 步犯错概率为 $\epsilon$；一旦犯错，策略被推离专家分布，此后每步都可能继续错。误差会「滚雪球」：

具体数值（本讲代码实验三实测）：用「首次犯错后此后每步都错」的模型做 Monte Carlo（每格 20000 条轨迹），$\epsilon = 0.05$ 时：

$T$ 从 20 增到 80（4 倍）时，可恢复错误增长 4 倍（严格线性，$O(\epsilon T)$），不可恢复错误增长 7.9 倍（超线性，$O(\epsilon T^2)$ 界内）。注意 $\epsilon T(T+1)/2$ 是上界，在 $\epsilon$ 小时更紧（比值随 $\epsilon$ 减小而增大，趋向紧）。

与监督学习的对比：监督学习里训练与测试分布相同，误差不累积，泛化误差与 $T$ 无关；BC 的误差却随任务时域二次增长——这是 BC 最本质的弱点。讲义 p38 指出「真实结果需要更多形式化」，指向 Ross et al. 2011 Theorem 2.1。

7.2.9 DAgger：数据集聚合（讲义 p35, p39）

严格定义（DAgger, Dataset Aggregation）：迭代地用当前学习器诱导的状态分布向专家索取动作标注，并把新数据聚合（aggregate）进数据集。

算法（讲义 p39 的核心思想）：

DAgger
输入: 初始专家示范 D_0 = {(s,a)}; 专家策略 pi*（可查询）
输出: 策略 pi_hat
初始化 D <- D_0
for i = 1, 2, ..., N do
    在当前数据集 D 上训练策略 pi_i（监督学习）
    用 pi_i 在环境中滚动，得到它自己访问的状态序列 s_1, s_2, ..., s_T
    向专家询问这些状态下的动作: a_t = pi*(s_t)      # 关键：查询 pi_i 自己的分布
    D <- D ∪ {(s_t, a_t)}                            # 数据聚合
end for
返回在 D 上训练出的策略 pi_hat

直观解释：BC 只在专家走过的「窄走廊」上有标签；DAgger 主动去学「我一旦走偏了该怎么办」——它把标注预算花在学习器实际会去的状态上，从而消除分布不匹配。

出处说明（重要）：讲义 p39 对 DAgger 给出的只有定性表述——「沿着行为克隆得到的策略所走的路径，去获取更多专家动作的标注」，以及「在其诱导的状态分布下获得性能良好的平稳确定性策略」。讲义没有写出 $O(\epsilon T)$ 的具体界；p38 只是把 $O(\epsilon T^2)$ 标为「approximate intuition」，并指向 Ross et al. 2011 的 Theorem 2.1（含补充材料证明）。

下面的形式化陈述来自 Ross et al. 2011 原文，这里列出是为了说明「二次降到线性」的确切含义；考试若要求「讲义结论」，答定性表述即可。

理论保证（Ross et al. 2011 Theorem 2.1，非讲义原文）：存在 $i \in \{1,\dots,N\}$ 使得

其中 $\epsilon = \min_i \epsilon_i$ 是学习器在DAgger 分布上的分类错误率上界，$u$ 是所用在线学习算法的 no-regret 上界。与 BC 的 $\epsilon T^2$ 相比，代价从二次降到线性。

关键限制（讲义 p39 的 “Key limitation?”）：DAgger 每轮都要向专家实时查询（在线交互），这在很多场景不可行（专家是人、只能离线提供数据）；且需要能重置/回滚环境。此外 BC 不需要知道转移模型也不需要与环境交互，而 MaxEnt IRL 需要转移模型或模拟能力（讲义 p59）。

BC vs DAgger 对比表：

7.2.10 从示范中恢复奖励：特征化奖励与特征匹配（讲义 p40–p49）

严格定义（问题设定，讲义 p30 与 p41）：已知 $\mathcal{S}$、$\mathcal{A}$、转移模型 $P(s^{\prime}\vert s,a)$、专家示范 $\{(s_0,a_0,s_1,\dots)\}$（动作来自专家策略 $\pi^*$），没有奖励函数 $R$。目标：推断 $R$。假设专家策略最优。

Check Your Understanding L7N3（讲义 p42–p43）答案：问「使专家策略最优的 $R$ 是否唯一」。答案是选项 2 / 讲义 p43 的结论：「存在无穷多个 $R$」（an infinite set of $R$）。

严格定义（线性特征奖励，讲义 p44–p45）：

则策略 $\pi$ 的价值函数可写成权重与特征期望的内积：

其中 $\mu(\pi)(s)$ 是「从 $s_0$ 出发、按策略 $\pi$ 的折扣加权状态特征频率」。

严格定义（特征匹配 / feature matching，讲义 p48，Abbeel & Ng 2004）：若

则对所有满足 $\vert w\vert _\infty \le 1$ 的 $w$（用 Hölder 不等式）都有

直观解释：只要新策略的「特征期望」与专家足够接近，那么在任何 $\vert w\vert _\infty\le1$ 的奖励下，它的表现都不会比专家差太多。这把「性能匹配」转化为「特征计数匹配」——一个可用示范数据估计的统计量。

歧义性（ambiguity，讲义 p49）：存在无穷多个奖励函数有相同的最优策略；也存在无穷多个随机策略能匹配特征计数。所以必须回答：该选哪一个？ 讲义 p50 指出两条关键路线：MaxEnt IRL（Ziebart et al., AAAI 2008）与 GAIL（Ho & Ermon, NeurIPS 2016）。

7.2.11 最大熵逆 RL（讲义 p51–p59）

严格定义（轨迹特征计数，讲义 p52）：对单条轨迹 $\tau_j$ 定义

讲义特别注明「这与我们之前看到的定义略有不同」（之前是折扣加权，这里是未折扣的总计数）。

严格定义（最大熵原理，讲义 p54）：在匹配特征期望的约束下选择不含额外偏好（熵最大）的分布：

结论（讲义 p55，指数族）：其解为 Boltzmann 型分布

讲义 p55 的注解：「强偏好低代价路径，代价相同的路径等概率」（strong preference for low cost paths, equal cost paths are equally probable）。

随机 MDP（讲义 p56）：分布同时依赖奖励权重与随机动态：

学习 $w$（讲义 p57）：最大化示范对数似然

其梯度恰为期望特征计数之差（可用状态访问频率 $D(s_i)$ 表达）：

（等价地，最小化负对数似然时 $\nabla_w(-\mathcal{L}) = \sum_{s_i}D(s_i)x(s_i) - \tilde\mu$，即「学习器特征期望 $-$ 示范特征期望」。）讲义 p57 追问：计算上式需要知道转移模型吗？——需要（或需要能在世界里模拟采样），这是 MaxEnt IRL 的关键代价（p59 再次强调），也是它与 BC 的重要区别（BC 完全不需要模型）。

MaxEnt IRL 伪代码（讲义 p58「MaxEnt IRL Algorithm for Frequencies」的算法化还原）：

MaxEnt IRL（确定性 MDP / 已知模型的版本）
输入: 示范 {tau_j}; 特征 x(s); 折扣 gamma; 转移模型 P(s'|s,a)
输出: 奖励权重 w
初始化 w <- 0
for 迭代 = 1, 2, ..., K do
    # 1) 用当前 w 定义奖励
    R(s) <- w^T x(s)
    # 2) 计算配分函数与模型诱导的访问频率（前向后向消息传递）
    由 soft value iteration 求 V(s) = logsumexp_a( R(s) + gamma * E_{s'}[V(s')] )
    log Z(w) <- V(s_0)
    前向传播得到状态访问频率 D(s)
    # 3) 特征期望之差作为梯度
    grad <- D^T x  -  mu_bar          # 学习器特征期望 - 示范特征期望
    # 4) 梯度下降 / 上升
    w <- w - eta * grad               # 最小化负对数似然
end for
返回 w

从 IRL 到策略（讲义 p60）：IRL 只给奖励；要用它算出性能不低于专家的策略，一个做法是「拿到学到的奖励后，跑常规 RL」；讲义随后追问「能否更直接地学到策略？」——这正是 L8 的 RLHF/DPO 与 GAIL 的出发点。

7.2.12 $n$ 步优势与 GAE 的记号对照

7.3 算法伪代码与完整推导

7.3.1 PPO 回顾（讲义 p2–p9；仅回顾，L6 已完整推导）

PPO 是一族近似施加 KL 约束、无需计算自然梯度的方法，有两个变体。

变体 A：自适应 KL 惩罚（adaptive KL penalty）

惩罚系数 $\beta_k$ 在迭代间自适应，以近似满足 KL 约束（不是一个硬约束）。L6 讲义给出的自适应规则：若实测 $\bar D_{KL}(\theta_{k+1}\vert \theta_k) \ge 1.5\delta$ 则 $\beta_{k+1} = 2\beta_k$；若 $\le \delta/1.5$ 则 $\beta_{k+1} = \beta_k/2$。

变体 B：裁剪目标（clipped objective）——作业要实现的版本。令重要性比率

其中 $\epsilon$ 是超参数（讲义建议 $\epsilon = 0.2$），策略更新为 $\theta_{k+1} = \arg\max_\theta L^{CLIP}_{\theta_k}(\theta)$。

Check Your Understanding（讲义 p3–p4）：问左/右图哪个对应 $A>0$。答案：左图是 $A>0$、右图是 $A<0$（即选项 1）。理由：$A>0$ 时 $\min(rA, \mathrm{clip}(r)A)$ 在 $r > 1+\epsilon$ 处被削平为上界（不再奖励继续增大该动作概率，防止过度自信）；$A<0$ 时该目标在 $r < 1-\epsilon$ 处被削平为下界（不再惩罚继续降低该动作概率，因为已经惩罚够了）。讲义 p4 的解页只保留了这一条，排除选项 3（「取决于 $\epsilon$」）与选项 4。

PPO 在作业中的实现要点：

1. 数据收集：用当前策略 $\pi_{\theta_k}$ 采一批部分轨迹（partial trajectories）$D_k$，长度 $T$（而非整条 episode）。
2. 优势估计：用 GAE（本讲主题）估 $\hat A^{\pi_k}_t$，即 7.3.2 的截断版。
3. 多轮更新：在同一批 $D_k$ 上做 $K$ 轮小批量 SGD/Adam，每轮重新计算 $r_t(\theta)$（这一步是 PPO 样本效率的来源）。
4. $\epsilon$ 与截断：$\epsilon = 0.2$ 是默认值；$\epsilon \to 0$ 退化为「完全信任旧数据」（一步都不许走），$\epsilon$ 过大则退化为无约束的普通策略梯度。
5. 早期停止（可选）：若实测 KL 超过阈值 $1.5\delta$，提前终止这批数据的更新。
6. 优势归一化：在批内对 $\hat A_t$ 做标准化（减均值除标准差），显著提升稳定性。
7. PPO 总结（讲义 p23）：提升数据效率（可以在采新数据前做多次梯度步）；用裁剪或 KL 约束提高单调改进的可能性；收敛到局部最优；实现简单、极受欢迎，用于 ChatGPT 的调优。

7.3.2 GAE 的伪代码与计算效率

GAE（Generalized Advantage Estimation）—— 一次反向扫描，O(T)
输入: 轨迹上的奖励 r_0..r_{T-1}, 状态 s_0..s_T（s_T 为终止或自举状态）,
      值函数 V（critic）, 折扣 gamma, 权衡参数 lambda
输出: 优势估计 A_hat_0..A_hat_{T-1}

# 步骤 1: 计算 TD 残差（前向，O(T)）
for t = 0 .. T-1:
    delta_t <- r_t + gamma * V(s_{t+1}) - V(s_t)

# 步骤 2: 反向累积（这是关键的 O(T) 单次扫描）
A_next <- 0
for t = T-1 down to 0:
    A_hat_t <- delta_t + gamma * lambda * A_next
    A_next  <- A_hat_t

返回 A_hat

算法逻辑解说：步骤 2 的 A_next 保存的是 $\hat A_{t+1}$，因此每一步只做一次乘法加法。整个算法对长度 $T$ 的轨迹只需 $2T$ 次标量运算，无需按 $k$ 展开求和（朴素展开是 $O(T^2)$）。

数学推导：见 7.2.3，核心是 $\sum_{l=0}^{\infty}(\gamma\lambda)^l\delta_{t+l}$ 的递推。

与理论的对应：$\lambda$ 的作用是调节「自举深度」；$\gamma\lambda$ 是有效折扣因子（effective discount），它比 $\gamma$ 更快地衰减远期残差。讲义 p15 说「一般偏好 $\lambda\in(0,1)$ 以平衡偏差与方差」，典型取 $\lambda = 0.95$。

计算效率的实证：本讲代码对 $T = 10, 100, 1000, 10000$ 均用同一个单次反向循环处理。这正是 GAE 能被放进 PPO 内循环的原因（讲义 p16）。

7.3.3 单调改进的完整推导链

单调改进 / CPI / TRPO 的推导链
输入: 当前策略 pi_k（参数 theta_k）, 优势上界 eps = max_{s,a} |A^{pi}(s,a)|
输出: 保证不劣的新策略 pi_{k+1}

Step 1  性能差异引理（恒等式，无近似）
        J(pi') - J(pi) = 1/(1-gamma) * E_{s~d^{pi'}, a~pi'}[ A^{pi}(s,a) ]

Step 2  把 s ~ d^{pi'} 换成 s ~ d^{pi}（近似，KL 小时成立）
        J(pi') - J(pi) ~= L_pi(pi') = 1/(1-gamma) * E_{s~d^{pi}, a~pi}[ (pi'(a|s)/pi(a|s)) A^{pi}(s,a) ]

Step 3  量化近似误差（Achiam et al. 2017）
        | J(pi') - [J(pi) + L_pi(pi')] | <= C * sqrt( E_{s~d^{pi}}[ D_KL(pi'||pi)[s] ] )

Step 4  由 Step 3 得下界
        J(pi') - J(pi) >= L_pi(pi') - C * sqrt( E_{s~d^{pi}}[ D_KL(pi'||pi)[s] ] )

Step 5  取 argmax（保守策略迭代 CPI）
        pi_{k+1} = argmax_{pi'}  L_{pi_k}(pi') - C * sqrt( E_{s~d^{pi_k}}[ D_KL(pi'||pi_k)[s] ] )
        单调改进证明: pi_k 处目标 = 0 -> 最优值 >= 0 -> J(pi_{k+1}) >= J(pi_k)

Step 6  用 TV 距离的显式系数形式（Kakade-Langford / TRPO）
        J(pi') >= L_pi(pi') - 2*gamma*eps/(1-gamma)^2 * max_s D_TV(pi'||pi)

Step 7  TV-KL 关系（Pinsker 不等式）
        D_TV(p||q)^2 <= (1/2) D_KL(p||q) <= D_KL(p||q)

Step 8  由此得到 KL 形式的界与「信任域」约束优化
        J(pi') >= L_pi(pi') - (2*gamma*eps/(1-gamma)^2) * sqrt( bar D_KL )
        取约束优化:  max_theta L_{theta_k}(theta)  s.t.  bar D_KL(theta||theta_k) <= delta

Step 9  自然梯度: 用 Fisher 矩阵的逆做预条件
        F = E[ grad log pi * grad log pi^T ]
        theta_{k+1} = theta_k + sqrt(2*delta/(g^T F^{-1} g)) * F^{-1} g

7.3.4 MaxEnt IRL 的配分函数与梯度推导

推导：为什么梯度是特征期望之差。 对单条轨迹，

对 $w$ 求梯度：

对示范集求和（用 $\tilde\mu = \frac1m\sum_j\mu_{\tau_j}$）：

这就是讲义 p57 的公式：梯度 = 示范特征期望 $-$ 学习器特征期望。它有一个漂亮的解释：在最大似然意义上，学习过程就是「把模型诱导的特征期望推向示范的特征期望」——与 7.2.9 的特征匹配目标完全一致。

配分函数的计算：$\log Z(w) = V_{\text{soft}}(s_0)$，其中 soft value iteration 为

这里 $\log\sum_a\exp$ 就是「软最大」（soft-max），动作先验均匀时 $\pi_{\text{soft}}(a\vert s) = \mathrm{softmax}a Q(s,a)$。由它做前向传播即得状态访问频率 $D(s)$，进而 $\mathbb{E}{\tau\sim P}[\mu_\tau] = X^\top D$。

7.3.5 BC 与 DAgger 的伪代码

Behavior Cloning (BC)
输入: 专家示范 D = {(s_i, a_i)}, 策略类 Pi
输出: 策略 pi_hat
pi_hat <- argmin_{pi in Pi} sum_{(s,a) in D} loss( pi(s), a )   # 纯监督学习
返回 pi_hat
# 注意: 训练分布是 d^{pi*}，但部署时状态来自 d^{pi_hat} -> 分布不匹配

DAgger (Dataset Aggregation) —— 用 no-regret 在线学习
输入: 专家策略 pi*（可在线查询）, 初始示范 D_0, 在线学习算法 A, 轮数 N
输出: 策略 pi_hat
D <- D_0
for i = 1, 2, ..., N do
    pi_i <- A(D)                                  # 在当前数据集上训练
    # 关键步骤: 用 pi_i 自己诱导的状态分布去查询专家
    采样状态序列 s_1..s_T ~ d^{pi_i}（在环境中滚动 pi_i）
    D <- D ∪ { (s_t, pi*(s_t)) : t = 1..T }       # 聚合
end for
pi_hat <- A(D)
返回 pi_hat
# （以下界出自 Ross et al. 2011，非讲义原文）

算法逻辑解说：DAgger 唯一的改动是「在谁的分布上要标注」。BC 在 $d^{\pi^*}$ 上要，DAgger 在 $d^{\pi_i}$ 上要。这一个改动把错误的累积从二次降到线性。

与理论的对应：Ross et al. 2011 把模仿学习归约为 no-regret 在线学习（online learning with experts），因此可以借用在线学习的 regret 界 $u$。注意讲义本身只把它表述为 $O(\epsilon T)$ 量级、并指向原论文；具体 $u$ 的形式依赖所选在线学习器（如 Follow-The-Leader / 在线梯度下降），不宜脱离原文给出单一数值。

7.4 代码实现与实验分析

本讲提供三份可运行脚本（cs234/code/ 下）：L07_gae.py、L07_dagger.py、L07_maxent_irl.py。全部只用 numpy + matplotlib + 标准库，环境均为自写 GridWorld / 小型 MDP，不依赖 torch/gym/gymnasium/scipy。

7.4.1 实验一：GAE 的偏差–方差权衡与代数恒等式验证

代码做什么：构造一个 5 状态、3 动作的 episodic MDP（状态 4 为吸收终态，$\gamma = 0.95$），在一个固定策略 $\pi$ 上用线性方程组解析求出精确的 $V^\pi, Q^\pi, A^\pi, d^\pi$ 与精确策略梯度 $g^$（$\vert g^\vert = 0.367698$）。然后：(a) 数值验证讲义的两种 GAE 写法等价、$n$ 步展开的 telescoping 恒等式；(b) 用精确 $V^\pi$ 与人为有偏的 $\hat V = 0.65 V^\pi$ 两种 critic，对 6000 条轨迹测量每个 $\lambda$ 下梯度估计的偏差与方差；(c) 演示 PPO 用同一批 rollout 做 6 个 epoch 的裁剪目标更新。

import numpy as np
np.random.seed(0)

GAMMA = 0.95
S, A, TERMINAL = 5, 3, 4

# ---------- TD 残差：delta_t = r_t + gamma*V(s_{t+1}) - V(s_t) ----------
def delta_td(ss, rr, V):
    """末步的 s_{t+1} 取终态（V=0）。"""
    s_next = np.concatenate([ss[1:], [TERMINAL]])
    return rr + GAMMA * V[s_next] - V[ss]

# ---------- GAE：A_t = delta_t + gamma*lambda*A_{t+1}，单次反向扫描 O(T) ----------
def gae_recursive(ss, rr, V, lam):
    T = len(rr)
    d = delta_td(ss, rr, V)
    out = np.zeros(T)
    acc = 0.0
    for t in range(T - 1, -1, -1):
        acc = d[t] + GAMMA * lam * acc     # 讲义 p16 的递推式
        out[t] = acc
    return out

# ---------- 讲义 p11 的加权平均定义：(1-lam) sum_k lam^{k-1} A^(k)_t ----------
def n_step_advantage(ss, rr, V, k):
    """A^(k)_t = sum_{l<k} gamma^l r_{t+l} + gamma^k V(s_{t+k}) - V(s_t)"""
    T = len(rr)
    out = np.zeros(T)
    for t in range(T):
        acc = sum((GAMMA ** l) * rr[t + l] for l in range(k) if t + l < T)
        idx = min(t + k, T)
        v_next = V[ss[idx]] if idx < T else 0.0
        out[t] = acc + (GAMMA ** k) * v_next - V[ss[t]]
    return out

def gae_weighted_average(ss, rr, V, lam, K=400):
    T = len(rr)
    out = np.zeros(T)
    for k in range(1, K + 1):
        out += ((1.0 - lam) * lam ** (k - 1)) * n_step_advantage(ss, rr, V, k)
    return out

# ---------- 策略梯度样本估计 ----------
def gradient_estimate(pi, ss, aa, rr, weights):
    """g = sum_t gamma^t * score(s_t,a_t) * w_t  （score 为 softmax 的 score function）"""
    g = np.zeros((4, A))
    for t in range(len(rr)):
        score = -pi[ss[t]].copy()
        score[aa[t]] += 1.0
        g[ss[t]] += (GAMMA ** t) * score * weights[t]
    return g.ravel()

# ---------- 用精确 critic 与有偏 critic 分别测量偏差 / 方差 ----------
def measure(V, n_trials=6000, lams=(0.0, 0.3, 0.6, 0.9, 0.95, 0.99, 1.0)):
    rng = np.random.default_rng(11)
    samples = {l: [] for l in lams}
    for _ in range(n_trials):
        ss, aa, rr = sample_episode(pi, rng)
        for l in lams:
            samples[l].append(gradient_estimate(pi, ss, aa, rr,
                                                gae_recursive(ss, rr, V, l)))
    for l in lams:
        X = np.array(samples[l]); mean = X.mean(axis=0)
        bias = mean - g_star
        print("lam=%.2f  ||bias||=%.5f  trace(Var)=%.5f"
              % (l, np.linalg.norm(bias), np.trace(np.cov(X.T))))

RL 机制透视：这段代码把 GAE 的两个「身份」都实现了一遍。gae_weighted_average 是定义（讲义 p11 的指数加权），gae_recursive 是化简结果（讲义 p12/p16）。二者在 $0\le\lambda<1$ 时数值一致，正是代数化简的直接验证。偏差–方差测量则揭示了一个关键因果：当 critic 精确时，所有 $\lambda$ 都近似无偏（因为 $\delta_t$ 的期望恰为 $A^\pi$，任意线性组合都保持无偏）；只有 critic 有偏时，$\lambda$ 才真正成为偏差–方差的旋钮。这解释了为什么 GAE 的实践价值与 critic 质量绑定：critic 好时增大 $\lambda$ 几乎没有代价。

实验观察（脚本真实输出）：

• 代数恒等式验证：$n$ 步展开与 $\sum_l\gamma^l\delta_{t+l}$ 的最大绝对差为 $0$、$1.11\times10^{-16}$、$2.22\times10^{-16}$、$2.78\times10^{-16}$、$3.47\times10^{-16}$（对应 $k=1,2,3,5,10$）——到机器精度。两种 GAE 写法在 $\lambda = 0, 0.5, 0.9, 0.95$ 下最大差分别为 $0$、$3.33\times10^{-16}$、$1.44\times10^{-15}$、$1.50\times10^{-9}$；$\lambda=1$ 时递推值 $-0.274118$ 与直接计算的 MC 优势 $G_0 - V(s_0) = -0.274118$ 相差 $2.78\times10^{-16}$。
• 精确 critic（$V^\pi$）：$\vert bias\vert $ 对所有 $\lambda$ 都在 $0.008$–$0.015$ 的小范围内（MC 采样噪声）；trace(Var) 从 $\lambda=0$ 的 $0.09859$ 单调升到 $\lambda=1$ 的 $1.11233$——约 11 倍。
• 有偏 critic（$\hat V = 0.65V^\pi$）：$\vert bias\vert $ 随 $\lambda$ 从 $0.11405$（$\lambda=0$）单调降到 $0.01732$（$\lambda=1$），而 trace(Var) 从 $0.06312$ 升到 $1.45745$——偏差降 6.6 倍、方差升 23 倍，这就是讲义 p15 所说的权衡。
• PPO 多 epoch：同一批 10790 步 rollout（GAE 优势标准差 $0.3486$）被复用 6 次，损失 $L^{CLIP}$ 从 $-0.039565$ 稳步降到 $-0.040810$，而参数离旧策略的距离 $\vert \theta_{new} - \theta_{old}\vert $ 仅从 $0.011106$ 增到 $0.066977$——裁剪项确实把策略变化限制住了。

7.4.2 实验二：BC vs DAgger 的复合误差

代码做什么：在 $n\times n$ 的 GridWorld 上（专家 = 反应式「先右后下」最短路径策略，任务时域 $T = 2(n-1)$，环境有 15% 滑移），对比 BC 与 DAgger。关键设计：学习器是表格型策略且每个状态只取第一条标注，因此 BC 与 DAgger 拥有完全相同的同分布错误率 $\epsilon$（= 专家标注噪声 0.10）——两者的差别只来自状态分布。同时统计「早/中/晚各 1/3 时域」的每步错误率，作为复合误差的直接诊断。

import numpy as np
np.random.seed(0)

N_ACT, SLIP = 4, 0.15
DELTA = [(-1, 0), (1, 0), (0, -1), (0, 1)]      # up, down, left, right

def build_grid(n):
    """n×n 网格，撞墙留在原地。"""
    nxt = np.zeros((n * n, N_ACT), dtype=int)
    for s in range(n * n):
        r, c = divmod(s, n)
        for a, (dr, dc) in enumerate(DELTA):
            nxt[s, a] = min(max(r + dr, 0), n - 1) * n + min(max(c + dc, 0), n - 1)
    return nxt

def expert_policy(n):
    """反应式最短路径专家：先右后下，对任意状态都最优，T = 2(n-1)。"""
    pi = np.zeros(n * n, dtype=int)
    for s in range(n * n):
        r, c = divmod(s, n)
        pi[s] = 3 if c < n - 1 else (1 if r < n - 1 else 3)
    return pi

def noisy_label(s, pi_star, eps, rng):
    """专家标注带噪：以概率 eps 标错。"""
    return int(rng.integers(N_ACT)) if rng.random() < eps else int(pi_star[s])

class OneShotTable:
    """每状态只保留第一条标注；未标注状态回落到固定默认动作。"""
    def __init__(self, n, pairs, default=0):
        self.table = np.full(n * n, default, dtype=int)
        self.covered = np.zeros(n * n, dtype=bool)
        for s, a in pairs:
            if not self.covered[s]:
                self.table[s] = int(a); self.covered[s] = True
    def act(self, s, rng):
        return int(self.table[s])

def rollout(pol, nxt, goal, rng, budget, pi_star):
    """返回 (状态列表, 动作列表, 到达终点?, 错误动作数)。"""
    s, ss, aa = 0, [], []
    for _ in range(budget):
        if s == goal: break
        a = pol.act(s, rng); ss.append(s); aa.append(a)
        if rng.random() < SLIP: a = int(rng.integers(N_ACT))   # 滑移
        s = int(nxt[s, a])
    errs = sum(int(a != pi_star[st]) for st, a in zip(ss, aa))
    return ss, aa, (s == goal), errs

def collect_demos(n, nxt, goal, pi_star, eps, rng, n_traj, budget):
    """BC 示教：状态来自 d^{pi*}（专家按最优动作走），动作标注带噪。"""
    pairs = []
    for _ in range(n_traj):
        s = 0
        for _ in range(budget):
            if s == goal: break
            pairs.append((s, noisy_label(s, pi_star, eps, rng)))
            s = int(nxt[s, int(pi_star[s])])
    return pairs

def run_dagger(n, nxt, goal, pi_star, eps, rng, init_pairs, iters, traj, budget):
    """DAgger：在**学习器自己诱导的分布**上为新状态向专家要一次标注。"""
    agg, seen = list(init_pairs), set(s for s, _ in init_pairs)
    stall = 0
    for _ in range(iters):
        pol = OneShotTable(n, agg); new = 0
        for _ in range(traj):
            ss, _, _, _ = rollout(pol, nxt, goal, rng, budget, pi_star)
            for s in ss:
                if s not in seen:
                    agg.append((s, noisy_label(s, pi_star, eps, rng)))
                    seen.add(s); new += 1
        stall = stall + 1 if new == 0 else 0
        if stall >= 3: break
    return OneShotTable(n, agg)

RL 机制透视：这段代码把「复合误差」的因果链剥离得非常干净。因为学习器的 $\epsilon$ 被「每状态只标注一次」锁死，BC 与 DAgger 的同分布准确率相同；唯一变量是训练分布与部署分布的差距。BC 的标注只覆盖 $d^{\pi^*}$（一条窄通道），一旦滑移或误动作把智能体推到通道外，未标注状态上的固定默认动作就持续犯错；DAgger 则通过「在学习器自己的轨迹上要标注」把这些状态补进数据集，覆盖率从 BC 的 $0.09$–$0.32$ 提升到 $0.32$–$0.64$，错误率随之回落。

实验观察（脚本真实输出，每个网格 6 个随机种子平均；专家标注噪声 $\epsilon=0.10$，滑移 $0.15$，预算 $4T$）：

随时间演化的每步错误率（早/中/晚各 1/3 时域，$T=38$ 时）：BC 为 $0.175 \to 0.392 \to 0.531$，DAgger 为 $0.068 \to 0.169 \to 0.308$——BC 的错误率随时域单调上升（被推离 $d^{\pi^*}$ 的直接证据），DAgger 在晚期的错误率仍不到 BC 的 60%。

幂律拟合：BC 的累计错误步数 $\propto T^{1.21}$，DAgger $\propto T^{1.05}$；逐尺寸的错误步之比 BC/DAgger 为 $[1.41, 1.93, 1.73, 1.41, 1.57, 2.46]$，DAgger 在每一个尺寸上都更优。需要诚实说明：拟合指数低于理论值 $p=2$，因为（i）滑移为误差设定了下界，（ii）成功到达终点会重置错误累积。

实验二（DAgger 逐轮，$n=14$、$T=26$）：纯 BC 成功率 $0.485$、错误步 $27.19$、覆盖率 $0.133$；第 1 轮 DAgger 后跳到成功率 $0.743$、错误步 $19.49$、覆盖率 $0.286$；此后在 $0.695$–$0.767$、$18.70$–$20.93$、$0.286$–$0.388$ 之间小幅波动（新增标注从 30 迅速降到 0–4），第 12 轮为 $0.743 / 19.94 / 0.388$。第一轮涨幅最大（+25.8 个百分点），之后趋于平台——与理论预期一致（分布不匹配在首轮被消除，剩下的误差是不可约的标注噪声）。无噪声最优专家的上界为成功率 $1.000$、错误步 $0.00$。

实验三（讲义 p38 的解析验证）见 7.2.8 的表格：$T$ 增大 4 倍时，可恢复错误增长 4 倍（严格 $O(\epsilon T)$），不可恢复错误增长 7.9 倍（超线性，$O(\epsilon T^2)$ 界内）。

7.4.3 实验三：MaxEnt IRL 从专家轨迹恢复奖励

代码做什么：在 $5\times5$ GridWorld（起点 0，终点 24，陷阱 12 与 16，$\gamma=0.90$，滑移 0.10）上，用 3 维特征 $x(s) = [\mathbb{1}\{s=\text{goal}\}, \mathbb{1}\{s=\text{trap}\}, 1]$ 与真实权重 $w^* = [1.02, -0.98, -0.02]$ 定义奖励。先用真实奖励求最优策略 $\pi^*$ 并采 60 条示范（含 5% 动作噪声），再用梯度下降最小化负对数似然（梯度 = $\mu_{\text{learner}} - \mu_{\text{bar}}$）恢复 $w$，其中配分函数与访问频率由 soft value iteration + 前向传播算出。最后检验尺度对齐后的恢复质量、特征期望匹配、以及经典的正仿射不可辨识性。

import numpy as np
np.random.seed(0)

N, S, N_ACT, GAMMA, SLIP = 5, 25, 4, 0.90, 0.10
GOAL, START, TRAPS = 24, 0, [12, 16]

# 特征 x(s) = [1{s=goal}, 1{s=trap}, 1]
X = np.zeros((S, 3)); X[:, 2] = 1.0
X[GOAL, 0] = 1.0
for t in TRAPS: X[t, 1] = 1.0
W_TRUE = np.array([1.02, -0.98, -0.02])
R_TRUE = X @ W_TRUE

def soft_value_iteration(R, tol=1e-13, max_iter=5000):
    """V(s) = logsumexp_a Q(s,a)：Boltzmann 路径分布的 log 配分函数递推。"""
    V = np.zeros(S)
    for _ in range(max_iter):
        Q = R[:, None] + GAMMA * np.einsum('san,n->sa', P_TRANS, V)
        m = Q.max(axis=1)
        V2 = m + np.log(np.exp(Q - m[:, None]).sum(axis=1))
        if np.max(np.abs(V2 - V)) < tol: V = V2; break
        V = V2
    Q = R[:, None] + GAMMA * np.einsum('san,n->sa', P_TRANS, V)
    E = np.exp(Q - Q.max(axis=1, keepdims=True))
    return V, Q, E / E.sum(axis=1, keepdims=True)

def state_visitation(pi, tol=1e-14, max_iter=5000):
    """解 d(s) = mu(s) + gamma * sum_{s',a'} d(s') pi(a'|s') P(s|s',a')。"""
    mu = np.zeros(S); mu[START] = 1.0
    d = mu.copy()
    for _ in range(max_iter):
        dn = mu + GAMMA * np.einsum('s,sa,san->n', d, pi, P_TRANS)
        if np.max(np.abs(dn - d)) < tol: return dn
        d = dn
    return d

def model_expectation(w):
    """给定 w，返回 (mu_learner, logZ, pi_soft, d, V_soft)。"""
    V, Q, pi = soft_value_iteration(X @ w)
    d = state_visitation(pi)
    return X.T @ d, V[START], pi, d, V        # mu_learner = X^T d

def feature_counts(trajs):
    """mu_bar = (1/m) sum_j sum_{s in tau_j} x(s)，讲义 p52 的定义。"""
    mu = np.zeros(3)
    for tr in trajs:
        for s in tr: mu += X[s]
    return mu / len(trajs)

# ---------- 主循环：梯度下降最小化负对数似然 ----------
def maxent_irl(trajs, iters=120, lr=0.5):
    mu_bar, w = feature_counts(trajs), np.zeros(3)
    for it in range(iters):
        mu_learner, logZ, pi, d, V = model_expectation(w)
        grad = mu_learner - mu_bar            # 讲义 p57 的梯度（符号取负对数似然）
        w = w - lr * grad
    return w, mu_bar

def value_iteration(R, tol=1e-13, max_iter=5000):
    """标准值迭代（求确定性最优策略）。"""
    V = np.zeros(S)
    for _ in range(max_iter):
        Q = R[:, None] + GAMMA * np.einsum('san,n->sa', P_TRANS, V)
        V2 = Q.max(axis=1)
        if np.max(np.abs(V2 - V)) < tol: V = V2; break
        V = V2
    Q = R[:, None] + GAMMA * np.einsum('san,n->sa', P_TRANS, V)
    return V, Q, Q.argmax(axis=1)

def policy_value(pi_idx, R):
    """策略 pi 在奖励 R 下的 V^pi(s_0)：解线性方程组。"""
    Ppi = P_TRANS[np.arange(S), pi_idx]
    return np.linalg.solve(np.eye(S) - GAMMA * Ppi, R)[START]

RL 机制透视：这段代码的关键在于 soft value iteration 让访问频率 $D(s)$ 成为 $w$ 的可微函数——这是「梯度 = 特征期望之差」能成立的前提。若像最初写错的那样用「均匀随机策略」算 $D$，梯度就与 $w$ 无关，优化必然停滞（本讲开发过程中确实踩过这个坑，日志表现为 NLL 单调恶化、$w$ 发散到 $10^{2}$ 量级）。正确的做法是让 soft 策略 $\pi_{\text{soft}} = \mathrm{softmax}(Q)$ 随 $w$ 变化：$w$ 抬高某状态的奖励 → 该状态被更频繁访问 → 特征期望上升 → 梯度自动减小。这就是「最大似然把模型推向示范」的动力学。另一处关键细节是终点必须建成吸收自环，否则访问质量会在终点处无限回流，迭代发散（overflow encountered in add）。

实验观察（脚本真实输出）：

• 收敛性：平均 NLL 从第 1 轮的 $13.63923$ 单调降到第 120 轮的 $13.31621$；$\vert \nabla\vert $ 从 $0.85808$ 降到 $0.03439$；特征期望 L1 差距 $\vert \mu_{\text{learn}} - \mu_{\text{bar}}\vert _1$ 从 $1.17625$ 降到 $0.04200$。
• 学到的权重：$\hat w = [0.4640, -2.8102, 2.0000]$（真实 $w^* = [1.02, -0.98, -0.02]$）。符号结构正确：终点为正、陷阱为负（$\hat w_1 > 0$、$\hat w_2 < 0$）；但相对幅度与绝对尺度都不可辨识——这正是理论预期（正仿射等价类）。
• 奖励恢复：$\mathrm{corr}(R^, \hat R) = 0.8752$；尺度/平移对齐后 $R^ \approx 0.3872\hat R - 0.7522$，对齐后最大绝对误差 $0.7981$（主要集中在终点状态，因尺度被压到 0.387 后终点值 2.464 只映射到 0.202，而真值是 1.00）。关键结构全部恢复：终点 $\hat R = +2.464$（真实 $+1.00$，正奖励正确），陷阱 12 与 16 均为 $\hat R = -0.810$（真实 $-1.00$，负奖励正确），陷阱均值 $-0.810 <$ 普通状态均值 $+2.000$。
• 特征期望匹配（讲义 p48）：$\mu_{\text{bar}} = [1.0000, 0.0500, 10.0333]$，$\mu_{\text{learner}} = [0.9998, 0.0583, 10.0000]$，$\vert \cdot\vert _1 = 0.04186$、$\vert \cdot\vert _2 = 0.03436$——终点特征计数几乎完全匹配（$0.9998$ vs $1.0000$）。
• 从 IRL 到策略（讲义 p60）：用 $\hat R$ 做值迭代得到 $\pi_{\text{hat}}$，在真实奖励下 $V^{\pi_{\text{hat}}}(s_0) = 3.8525$ vs 专家 $V^{\pi^*}(s_0) = 3.8629$，性能比 $0.9973$（达到专家水平的 99.7%，与讲义「performance equals or exceeds the expert」的目标一致）。
• 不可辨识性验证：$R^+0.5$、$R^+5$、$R^-2$、$3R^$、$0.1R^$ 诱导的策略在真实奖励下的价值全部等于 $3.862931$（与 $\pi^$ 相同）——正仿射变换不改变最优策略。对 $\hat R$ 做 $7\hat R + 3$ 同样保持价值 $3.8525$。
• 示范条数 $m$ 的影响：$m = 5$ 时 $\mathrm{corr} = 0.5486$、性能比 $0.9303$；$m = 10$ 时 $\mathrm{corr} = 0.8825$、性能比 $0.9973$；$m \ge 10$ 后相关性与性能基本饱和（$0.879$–$0.891$、性能比恒为 $0.9973$），而 $\vert \nabla\vert $ 整体呈下降趋势（$0.6029 \to 0.3134 \to 0.1743$，中间有波动）——说明示范特征期望的蒙特卡洛误差是主要瓶颈，且少量示范（10 条）已足够恢复策略层面的性能。

7.5 评估指标与理论保证

本讲涉及的评估指标：

理论保证及其具体形式：

1. 单调改进（讲义 p19–p21）：若 $\pi_{k+1} = \arg\max_{\pi^{\prime}}\big[L_{\pi_k}(\pi^{\prime}) - C\sqrt{\mathbb{E}{s\sim d^{\pi_k}}[D{KL}(\pi^{\prime}\vert \pi_k)[s]]}\big]$，则 $J(\pi_{k+1}) \ge J(\pi_k)$，且该结论对任意参数化策略类成立（只要 $\pi_k$ 在类内）。
2. CPI/TRPO 的保守界：$J(\pi^{\prime}) \ge L_\pi(\pi^{\prime}) - \frac{2\gamma\epsilon}{(1-\gamma)^2}\max_s D_{TV}(\pi^{\prime}\vert \pi)$，$\epsilon = \max_{s,a}\vert A^\pi(s,a)\vert $。
3. 相对性能界（Achiam et al. 2017）：$\vert J(\pi^{\prime}) - [J(\pi) + L_\pi(\pi^{\prime})]\vert \le C\sqrt{\mathbb{E}{s\sim d^\pi}[D{KL}(\pi^{\prime}\vert \pi)[s]]}$。
4. BC 的复合误差（讲义 p38 明确标注为 approximate intuition，非严格定理）：$\mathbb{E}[\text{总错误}] \le \epsilon(T + (T-1) + \cdots + 1) \propto \epsilon T^2$。严格版本见 Ross et al. 2011 Theorem 2.1。
5. DAgger 的 no-regret 保证（Ross et al. 2011，非讲义原文）：存在 $i \le N$ 使 $J(\pi_i) \le J(\pi^*) + u\epsilon T$，$u$ 为在线学习器 regret 上界。
6. GAE 的无偏性：$V$ 精确时，$\mathbb{E}[\hat A_t^{GAE(\gamma,\lambda)}] = A^\pi(s_t,a_t)$ 对所有 $\lambda\in[0,1]$ 成立（因为 $\mathbb{E}[\delta_t] = A^\pi(s_t,a_t)$）。$V$ 有偏时，偏差随 $\lambda$ 减小而增大。
7. MaxEnt IRL 的恢复范围：$w$ 只能在正仿射等价类内被辨识；等价类内由最大似然唯一确定。
8. 特征匹配的充分条件：$\vert \mu(\pi) - \mu(\pi^)\vert _1 \le \epsilon \Rightarrow \vert w^\top\mu(\pi) - w^\top\mu(\pi^)\vert \le \epsilon$ 对所有 $\vert w\vert _\infty\le1$。

条件依赖分析：

• GAE：质量取决于 critic $V$ 的精度。critic 精确时偏好大 $\lambda$（消偏且几乎不增偏差）；critic 粗糙时必须用小 $\lambda$（牺牲偏差换方差）。此外 $\gamma\lambda$ 是有效折扣，$\lambda<1$ 会让远期信用分配更快衰减。
• PPO/TRPO：都强依赖「新旧策略足够接近」这一前提。PPO 的裁剪是启发式近似，可能偶发违反 KL；TRPO 的约束是硬的，但每步需要共轭梯度求解，计算更贵。
• BC：要求训练分布能覆盖部署分布，否则复合误差主导。离线、无需模型、无需交互是它的优势。
• DAgger：需要在线专家查询与环境可重置；专家查询成本是主要瓶颈。
• MaxEnt IRL：需要转移模型或能模拟采样（讲义 p57/p59 反复强调），这是它相对 BC 的最大额外要求；另需特征设计。

7.6 与其他讲次的关联

• L3–L4（TD/MC 与值函数逼近）：GAE 的 $n$ 步估计正是 L3 中 TD(0)（$n=1$）与 MC（$n\to\infty$）的统一；$\delta_t$ 就是 L3 的 TD 误差。本讲的偏差–方差讨论是 L3 中 TD 与 MC 对比的直接延续。
• L5（Policy Gradient I）：REINFORCE 用 $G_t$ 作 $\hat A_t$，等价于本讲 $\lambda = 1$ 的极端情形。本讲的 L7N1 复习题（讲义 p71–p72）正是对 L5 的回顾。
• L6（Policy Gradient II）：L6 给出了性能差异引理与替代目标 $L_\theta(\theta^{\prime})$、PPO 的裁剪目标；本讲把它升级为完整的单调改进理论（CPI/TRPO/自然梯度），并补上 L6 遗留的「PPO 里的优势怎么估」——GAE。讲义 p25 的 Outline 明确写「Monotonic Improvement Theory (next time)」，本讲即为该「next time」。
• L8（Imitation Learning / RLHF / DPO）：本讲的 BC 与 MaxEnt IRL 是 L8 的直接基础；讲义 p61 提到「只用偏好对 $(y_1 \succ y_2)$ 学习奖励」与「Dueling bandits」，并预告「我们很快会更多看到这个设定（以及作业 3）」——这正是 L8 的 RLHF/DPO 主线。讲义 p50 提到的 GAIL（Ho & Ermon 2016）也在 L8 展开。注意分工：本讲不涉及 Bradley-Terry 模型与 DPO 推导，留给 L8。
• L9–L12（Fast RL / Bandits）：讲义 p61 明确把「偏好对」与「Dueling bandits」连到 bandit 部分（L9–L10）。逆 RL 与偏好学习也是 L11–L12 中「奖励学习与探索结合」的前置。
• L13–L14（MCTS）：MCTS 的 UCB 树搜索需要值估计；PPO 与 MCTS 的结合（AlphaZero 式）是本讲算法在下游的典型用法。

7.7 关键要点

• GAE = 一个超参数 $\lambda$ 连续调节优势估计的偏差–方差：$\hat A_t^{GAE(\gamma,\lambda)} = \sum_{l\ge0}(\gamma\lambda)^l\delta_{t+l}$，$\lambda=0$ 是 TD(0) 残差（偏差大方差小），$\lambda=1$ 是 MC 优势（偏差小方差大），实践取 $\lambda\approx0.95$。实现只需一次 $O(T)$ 反向扫描：$A_t = \delta_t + \gamma\lambda A_{t+1}$。
• GAE 的无偏性依赖 critic 质量：$V$ 精确时任意 $\lambda$ 都无偏；$V$ 有偏时 $\lambda$ 才成为真正的偏差–方差旋钮。先修 critic，再调 $\lambda$。
• 策略梯度的病根是「参数空间距离 $\neq$ 策略空间距离」，因此需要以策略空间的度量来定步长。自然梯度用 Fisher 矩阵 $F$（KL 的二阶展开）做预条件，正是为此。
• 单调改进的推导链：性能差异引理（恒等式）→ 用 $d^\pi$ 近似 $d^{\pi^{\prime}}$ 得替代目标 $L_\pi(\pi^{\prime})$ → 用 KL/TV 量化近似误差得下界 → 最大化下界即 CPI → 把惩罚换成约束即 TRPO（信任域）→ 用自然梯度求解。证明的关键是「$\pi_k$ 处目标恰为 0」，因此最优值 $\ge0$。
• PPO 是 TRPO 的可扩展近似：裁剪目标 $L^{CLIP}$ 用重要性比率的分段线性化绕开 KL 与 Fisher 计算，$\epsilon=0.2$；代价是失去 TRPO 的严格单调保证，换来实现简单与经验上的成功（ChatGPT 调优即用 PPO）。
• 模仿学习的核心矛盾是分布漂移，不是分类精度：BC 的留出准确率可以很高，端到端成功率却很低（本讲实验中 BC 覆盖 0.09–0.32、成功率 0.20–0.64）。BC 的误差 $\propto\epsilon T^2$，DAgger $\propto\epsilon T$，差别只在于「在谁的分布上要标注」。
• 逆 RL 的奖励只能在正仿射等价类内辨识（$R+c$ 与 $kR$，$k>0$，不改变最优策略）。MaxEnt 原理用「匹配特征期望 + 最大熵」在等价类中挑出唯一解；其梯度就是示范特征期望与学习器特征期望之差。

7.8 常见误区与注意事项

误区 1：认为 $\lambda = 1$ 时 GAE 的加权平均定义 $(1-\lambda)\sum_k\lambda^{k-1}\hat A^{(k)}$ 可以直接代入计算。 错误。$\lambda = 1$ 时这是「$0\times$ 发散级数」的未定式，代码里直接代入会得到 0 或 NaN。正确认识：必须按极限理解——$\lambda\to1$ 的 GAE 就是 MC 优势 $G_t - V(s_t)$；用递推式 $\hat A_t = \delta_t + \gamma\lambda\hat A_{t+1}$ 计算则天然正确处理该端点（本讲实验中 $\lambda=1$ 的递推值与直接计算的 $G_0 - V(s_0)$ 相差 $2.78\times10^{-16}$）。另外 $\lambda=0.99$ 时用有限 $K$ 项的加权平均会有可观的截断误差（实测 $2.19\times10^{-2}$，与 $\lambda^K$ 同量级），不要误判为公式不一致。

误区 2：以为有偏 critic 下所有 $\lambda$ 都一样偏。 错误。正确认识：$\lambda$ 越小，$\hat A^{GAE}$ 越依赖 $V$，偏差越大、方差越小；$\lambda=1$ 时完全不用 $V$ 估计中间步骤（只用 $V(s_t)$ 作基线，不影响无偏性），偏差最小、方差最大。本讲实测：有偏 critic（$\hat V = 0.65V^\pi$）下 $\vert bias\vert $ 从 $\lambda=0$ 的 $0.11405$ 降到 $\lambda=1$ 的 $0.01732$，而方差从 $0.06312$ 升到 $1.45745$。反之，critic 精确时 $\lambda$ 不再是偏差旋钮（实测 $\vert bias\vert $ 全程在 $0.008$–$0.015$ 的采样噪声范围内）。

误区 3：把 PPO 的裁剪当作严格的 KL 约束，认为 PPO 也有 TRPO 的单调改进保证。 错误。正确认识：讲义 p2 说 PPO 是「approximately enforce KL constraint」——裁剪是启发式的分段线性近似，可能在单步内违反 KL；自适应 KL 惩罚同样只能近似约束（「some iterations may violate KL constraint, but most don’t」）。TRPO 的约束是硬约束且步长取到信赖域边界（$\sqrt{2\delta}$ 的 Fisher 范数），理论保证更强但计算更贵。PPO 的取舍是「用理论保证换实现简单与可扩展」。

误区 4：认为 BC 的失败是因为分类器不够强/数据不够多，于是不断加大模型与数据。 错误。正确认识：BC 的失败主因是训练分布与部署分布的漂移（$d^{\pi^*}$ vs $d^{\pi_\theta}$），这是结构性的。加大模型容量无法消除分布外状态上没有标签的事实——反而可能让策略更「自信」地外推。正确的补救是改变数据分布（DAgger）、或用保守/不确定性感知的方法。本讲实验中 BC 与 DAgger 的同分布 $\epsilon$ 完全相同，差距只来自分布覆盖（BC 覆盖 0.09–0.32 vs DAgger 0.32–0.64）。

误区 5：认为 $\epsilon T^2$ 是一个紧等式，可以用它预测具体错误步数。 错误。正确认识：讲义 p38 明确说这是「approximate intuition」，且「real result requires more formality」。$\epsilon T(T+1)/2$ 是上界，在 $\epsilon$ 小时更紧。本讲实测（$\epsilon=0.05$，$T=80$）：模拟值 $61.269$ vs 上界 $162.000$，比值只有 $0.38$。它的价值在于揭示标度关系（$T$ 翻倍错误约翻 4 倍），而不是给出精确数值。

误区 6：认为逆 RL 能恢复出「真实」奖励函数。 错误。正确认识：奖励只在正仿射等价类 $\{kR + c : k>0\}$ 内可辨识——本讲实验中 $R^+5$、$3R^$、$0.1R^$ 诱导的最优策略完全相同（在真实奖励下价值都等于 $3.862931$）。此外即便固定等价类，Check Your Understanding L7N3 的答案是「存在无穷多个 $R$ 使专家策略最优」。MaxEnt 原理的作用不是消除这个歧义，而是在等价类内用「最大熵/最大似然」给出一个有原则的选择。因此评估 IRL 应看「学到的奖励导出的策略有多好」（本讲实测性能比 $0.9973$），而不是看 $w$ 与 $w^$ 的逐分量距离。

误区 7：以为 MaxEnt IRL 不需要转移模型（把它当成 BC 一样省事）。 错误。正确认识：讲义 p57 追问「计算梯度需要知道转移模型吗？」并在 p59 明确给出答案——原始 MaxEnt 公式需要已知转移模型，或需要能在世界里模拟/行动以采样。这是因为 $D(s)$（状态访问频率）与配分函数 $Z(w)$ 都依赖 $P(s^{\prime}\vert s,a)$。相比之下，BC 完全不需要转移模型、也不需要与环境交互（讲义 p59 的反问正是要突出这一对比）。GAIL（Ho & Ermon 2016）与后续工作才放松了这一要求。

误区 8：认为单调改进理论保证「每一步都改进」，所以 TRPO/PPO 不会出现性能下降。 错误。正确认识：单调改进是对精确求解 $\arg\max$ 的定理。实践中 (i) 用样本估计 $L$ 与 KL，(ii) 用有限步 SGD 近似求解，(iii) 用函数逼近表达策略——三者都会破坏前提。所以实践中仍会看到性能波动。正确认识是：该定理告诉你「如果 KL 约束被满足，改进是可期的」，它把「调步长」从盲试变成了有指导的约束设计。PPO 用裁剪/KL 惩罚「help increase likelihood of monotonic improvement」——是 increase likelihood，不是 guarantee。

7.9 思考题（带答案）

题 1（推导题）：从性能差异引理推导替代目标，并证明单调改进定理。

答案：

第一步，性能差异引理（恒等式）。对任意 $\pi,\pi^{\prime}$，

证明思路：把 $A^\pi(s_t,a_t) = Q^\pi(s_t,a_t) - V^\pi(s_t)$ 代入右边，利用 $Q^\pi(s_t,a_t) = r_t + \gamma\mathbb{E}[V^\pi(s_{t+1})]$，得

第二个和式 telescoping 相消，只剩 $-\gamma^0 V^\pi(s_0) = -V^\pi(s_0)$。取期望后右边为 $\mathbb{E}[\sum_t\gamma^t r_t] - V^\pi(s_0) = J(\pi^{\prime}) - J(\pi)$。$\square$

第二步，替代目标。由 $d^\pi(s) = (1-\gamma)\sum_t\gamma^t P(s_t=s\vert \pi)$，引理可写成

把 $a\sim\pi^{\prime}$ 换成 $a\sim\pi$ 并加重要性比率（这一步是精确的，因为 $\pi^{\prime}(a\vert s) = \pi(a\vert s)\cdot\frac{\pi^{\prime}(a\vert s)}{\pi(a\vert s)}$）：

唯一障碍是 $s\sim d^{\pi^{\prime}}$。近似 $d^{\pi^{\prime}}\approx d^\pi$（KL 小时成立），得

第三步，量化近似误差并取 argmax。

令 $\pi_{k+1} = \arg\max_{\pi^{\prime}}\big[L_{\pi_k}(\pi^{\prime}) - C\sqrt{\mathbb{E}{s\sim d^{\pi_k}}[D{KL}(\pi^{\prime}\vert \pi_k)[s]]}\big]$。

第四步，证明最优值 $\ge0$。取 $\pi^{\prime} = \pi_k$（可行点）：

故目标函数在 $\pi_k$ 处取 0，最优值 $\ge 0$。

第五步，结论。把第四步代回下界：$J(\pi_{k+1}) - J(\pi_k) \ge L_{\pi_k}(\pi_{k+1}) - C\sqrt{\cdots} \ge 0$，即 $J(\pi_{k+1}) \ge J(\pi_k)$。$\square$

注：该证明对任意参数化策略类 $\Pi_\theta$ 成立，只要 $\pi_k\in\Pi_\theta$（讲义 p21）。

题 2（计算题）：给定一条 3 步轨迹与一个 critic，手算 GAE。

设定：$\gamma = 0.5$，$V(s_0) = 1$，$V(s_1) = 2$，$V(s_2) = 4$，$V(s_3) = 0$（$s_3$ 为终止）；奖励 $r_0 = 1$，$r_1 = 2$，$r_2 = 0$。求 $\lambda = 0$、$\lambda = 0.5$、$\lambda = 1$ 下的 $\hat A_t^{GAE}$（$t = 0,1,2$）。

答案：

先算 TD 残差 $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$：

• $\delta_0 = 1 + 0.5\times2 - 1 = 1$
• $\delta_1 = 2 + 0.5\times4 - 2 = 2$
• $\delta_2 = 0 + 0.5\times0 - 4 = -4$

用递推 $\hat A_t = \delta_t + \gamma\lambda\hat A_{t+1}$（从 $t=2$ 反向）：

$\lambda = 0$（即 $\hat A_t = \delta_t$）：$\hat A_2 = -4$，$\hat A_1 = 2$，$\hat A_0 = 1$。

$\lambda = 0.5$（$\gamma\lambda = 0.25$）： $\hat A_2 = -4$；$\hat A_1 = 2 + 0.25\times(-4) = 1$；$\hat A_0 = 1 + 0.25\times1 = 1.25$。

$\lambda = 1$（$\gamma\lambda = 0.5$）： $\hat A_2 = -4$；$\hat A_1 = 2 + 0.5\times(-4) = 0$；$\hat A_0 = 1 + 0.5\times0 = 1$。

交叉验证 $\lambda=1$ 应为 MC 优势：$G_0 = r_0 + \gamma r_1 + \gamma^2 r_2 = 1 + 1 + 0 = 2$，故 $G_0 - V(s_0) = 2 - 1 = 1$ ✓。 $G_1 = r_1 + \gamma r_2 = 2$，$G_1 - V(s_1) = 0$ ✓。 $G_2 = r_2 = 0$，$G_2 - V(s_2) = -4$ ✓。

要点：$\lambda$ 从 0 增到 1 时，$\hat A_0$ 从 1 变为 1.25 再回到 1（非单调，因中间残差符号不同）；$\lambda=1$ 的结果必须与 MC 优势完全一致。

题 3（分析题）：解释为什么 BC 的误差是 $O(\epsilon T^2)$ 而 DAgger 是 $O(\epsilon T)$，并说明 DAgger 的代价。

答案：

BC 的 $O(\epsilon T^2)$：BC 的训练集只在专家分布 $d^{\pi^}$ 上有标签。设学习器在同分布上的每步错误率为 $\epsilon$。在第 $t$ 步，若前 $t$ 步都正确，则 $s_t\sim d^{\pi^}$，犯错概率为 $\epsilon$；一旦某步犯错，智能体被推离专家分布，进入训练时从未见过的状态，此后每步的错误概率不再是 $\epsilon$ 而是接近 $1$（无标签可用）。于是

直观地：第 $t$ 步犯的错会「污染」此后所有步。本讲代码的 Monte Carlo 实测（$\epsilon=0.05$）：$T=20$ 时上界 $10.5$、模拟 $7.783$；$T=80$ 时上界 $162$、模拟 $61.269$；$T$ 增大 4 倍时模拟值增长 7.9 倍（超线性），而可恢复错误模型只增长 4 倍（严格线性）。

DAgger 的 $O(\epsilon T)$：DAgger 把标注预算花在学习器自己诱导的分布 $d^{\pi_i}$ 上。无论学习器走到哪里，那里的状态都会被专家标注，因此学习器在其实际访问的所有状态上都能达到 $\le\epsilon$ 的错误率。此时错误不再「污染后续」——每步独立地以 $\le\epsilon$ 出错，总错误 $\le\epsilon T$。Ross et al. 2011 进一步证明：存在 $i\le N$ 使 $J(\pi_i)\le J(\pi^*) + u\epsilon T$，其中 $u$ 是所用在线学习算法的 no-regret 上界。

DAgger 的代价：

1. 需要在线专家查询：每轮都要专家为学习器新访问的状态标注。若专家是人，这不可行（人只能离线提供数据）。
2. 需要环境可交互/可重置：必须能用当前策略在环境中滚动并采集状态轨迹（BC 只需静态数据集）。
3. 需要标准的模仿学习假设（如环境可控），且查询次数随轮数线性增长。
4. 理论保证是「存在某个 $\pi_i$ 好」而非「最终策略好」：需要对所有轮次的策略做验证以挑出最好的那个（或在实践中用验证集选择）。

本讲实验的定量印证：BC 与 DAgger 被刻意设计为共享同一个 $\epsilon$（每状态只标注一次，专家噪声均为 0.10），因此差距完全来自分布覆盖。结果是 DAgger 在全部 6 个任务时域上错误步数更低（比值 1.41–2.46 倍），覆盖率更高（如 $T=38$ 时 0.32 vs 0.09），成功率在 $T=17$ 时从 0.203 提到 0.737。

题 4（概念题）：L7N1 复习题——关于 REINFORCE，下列哪些为真？

(a) 加入基线项有助于降低策略梯度更新的方差 (b) 它会收敛到全局最优 (c) 若用合适步长，它可以被初始化在次优的确定性策略上并仍收敛到局部最优 (d) 若只走一步策略梯度，得到的策略在回报上可能比初始策略更差

答案：(a) 与 (d) 为真。

• (a) 真：这是 L6 的核心结论。基线不引入偏差（因 $\mathbb{E}_{a\sim\pi}[\nabla\log\pi(a\vert s)\cdot b(s)] = b(s)\nabla\sum_a\pi(a\vert s) = 0$），但能显著降方差。
• (b) 假：策略梯度是非凸优化，只保证收敛到局部最优。
• (c) 假：这是本题的陷阱。确定性策略的 score function $\nabla_\theta\log\pi_\theta(a\vert s)$ 在许多参数化下会退化——例如 softmax 策略在极端参数下概率饱和，梯度趋于 0；更本质地，确定性策略对未选中的动作概率为 0，「探索」完全消失，策略梯度无法获得关于其他动作的信息（这正是 L5/L6 强调需要随机策略与探索的原因）。因此 REINFORCE 通常不能从确定性策略出发有效学习。
• (d) 真：这正是本讲 7.2.1 的病态所在——参数空间的一步不等于策略空间的一小步；步长过大时性能可能崩溃且难以恢复（讲义 L6 p29–p31 的图）。这恰恰是 GAE/单调改进/TRPO 要解决的问题。

题 5（概念题）：MaxEnt IRL 的梯度为什么等于「示范特征期望 − 学习器特征期望」？它和学徒学习/特征匹配是什么关系？

答案：

梯度推导。MaxEnt 路径分布为 $P(\tau\vert w) = \exp(w^\top\mu_\tau)/Z(w)$，$Z(w) = \sum_\tau\exp(w^\top\mu_\tau)$。对单条轨迹

对 $w$ 求梯度，第二项是 log 配分函数的梯度，而它恰好等于模型分布下的期望特征计数：

（这正是指数族的经典性质：$\nabla\log Z = \mathbb{E}[\text{充分统计量}]$。）因此

对整个示范集求和除以 $m$ 即得

即讲义 p57 的「示范期望特征计数 $-$ 学习器期望特征计数」。用状态访问频率表达就是 $\tilde\mu - \sum_{s_i}D(s_i)x(s_i)$。

与特征匹配/学徒学习的关系。梯度为零的驻点条件是

即学习器诱导的特征期望等于示范的特征期望——这正是 Abbeel & Ng (2004) 的特征匹配（feature matching）条件，也是学徒学习（apprenticeship learning）的目标（讲义 p46–p48）。再由本讲 7.2.9 的 Hölder 不等式结论：若 $\vert \mu(\pi) - \mu(\pi^)\vert _1 \le \epsilon$，则对所有 $\vert w\vert _\infty\le1$ 有 $\vert w^\top\mu(\pi) - w^\top\mu(\pi^)\vert \le \epsilon$——即特征匹配充分保证性能匹配。

两者的区别在于如何选解：学徒学习通常在「$\mu$ 空间」里做投影/博弈，可能有多个解；MaxEnt IRL 则用「最大熵」在满足匹配约束的分布集合中选出唯一那个（熵最大的指数族分布），从而把问题化为一个凸的最大似然问题（负对数似然是凸函数），这也是它「hugely influential」的原因（讲义 p59）。

本讲实验印证：$\mu_{\text{bar}} = [1.0000, 0.0500, 10.0333]$，收敛后 $\mu_{\text{learner}} = [0.9998, 0.0583, 10.0000]$，$\vert \cdot\vert _1 = 0.04186$；用学到的奖励导出的策略在真实奖励下达到专家性能的 $0.9973$，验证了「特征匹配 $\Rightarrow$ 性能匹配」这一链条。

题 6（概念题）：为什么 MaxEnt IRL 需要转移模型，而行为克隆不需要？

答案：

MaxEnt IRL 为什么需要。它的目标函数是路径分布的对数似然，而这个分布同时依赖奖励权重与动态：

梯度 $\nabla_w\mathcal{L} = \tilde\mu - \sum_{s_i}D(s_i)x(s_i)$ 中的状态访问频率 $D(s_i)$ 必须通过对 $P(s^{\prime}\vert s,a)$ 做前向传播才能得到；而配分函数 $Z(w)$ 也需要在整个轨迹空间（或通过对 $P$ 的 soft value iteration）求和。这两处都要求已知转移模型，或者至少要能在环境中模拟采样（讲义 p59：需要「knowledge of the transition model or the ability to simulate/act in the world to gather samples of the transition model」）。这也是为什么 GAIL 等后续工作改用对抗式学习来绕开显式模型。

BC 为什么不需要。BC 把问题归约为标准监督学习：数据集是静态的 $(s,a)$ 对，学习目标是 $\hat\pi = \arg\min_\pi\sum_{(s,a)\in\mathcal{D}}\mathrm{loss}(\pi(s),a)$。整个过程中既不需要 $P(s^{\prime}\vert s,a)$，也不需要与环境交互——它甚至不需要知道任务是不是 MDP。

代价的转移。BC 用「不需要模型、不需要交互」换来了分布漂移（$O(\epsilon T^2)$ 复合误差）；MaxEnt IRL 用「需要模型或模拟能力」换来了奖励函数的可迁移性——学到的奖励可以配合任意 RL 算法求解，并能在环境/动力学变化时复用。讲义 p59 的反问「Check your understanding: was this needed in behavioral cloning?」正是要学生明确这一对比。

本讲小结（讲义 p61–p62、p70）：模仿学习能极大地减少学好策略所需的数据；挑战依然存在，一个激动人心的方向是把逆 RL / 从示范学习与在线强化学习结合。理论层面，本讲完成了从「策略梯度为什么病态」到「KL 约束 + 自然梯度如何治愈」的闭环（讲义 p70 的 Advanced Policy Gradients 总结：PPO ①近似约束策略步长 ②实现相对简单 ③经验效果好且被广泛使用）。Imitation Learning: What You Should Know —— 能定义行为克隆并说清它与强化学习的区别（讲义 p62）。