Lecture 4: 无模型控制与函数逼近 —— 从 SARSA、Q-learning 到 DQN（Model-Free Control and Function Approximation）

目录 · ← l3 · l5 →

Lecture 4: 无模型控制与函数逼近 —— 从 SARSA、Q-learning 到 DQN（Model-Free Control and Function Approximation）

对应材料：官方 lecture4pre.pdf（89 页）/ lecture4post.pdf（89 页，含课上 Poll 的答案与课后补充算例；本笔记以 post 为准，逐页核对）｜Week 2 周三 2026-01-14（A1 截止 Jan 16，A2 发布）｜参考阅读：Sutton & Barto (2018, 2nd ed.) Chp 5.2–5.4, 6.4, 6.5, 6.7；David Silver Lec 5–6 一句话定位：L3 用 MC / TD 解决了「已知策略 $\pi$、如何估 $V^\pi$」；本讲先把评估搬到 $Q$ 上，再把「估」升级成「控制」——用 $\epsilon$-greedy 把 $\arg\max_a Q(s,a)$ 反馈回行为策略，得到无模型控制的三大算法（MC control、SARSA、Q-learning），并给出它们的收敛条件（GLIE + Robbins–Monro）；随后把查找表换成参数化函数 $\hat Q(s,a;w)$，引入半梯度（semi-gradient）更新与致命三要素（deadly triad），最后落到 DQN（经验回放 + 固定目标网络）。它是 L5 策略梯度的前置：DQN 也是「用神经网络逼近 $Q$」的终点，L5 起改走直接优化策略 $\pi_\theta$ 的路线。

4.1 概述

本讲要回答一个问题：在既没有 $P(s^{\prime}\vert s,a)$ 也没有 $R(s,a)$ 的条件下，如何学出一个好策略？ L3 只做到「给定 $\pi$ 估出 $V^\pi$」，本讲补上最后一块拼图——把估计器接到决策上。技术路线是广义策略迭代（Generalized Policy Iteration, GPI）：反复做「策略评估（用 MC 或 TD 从数据估 $Q^\pi$）」与「策略改进（把 $\pi$ 换成关于 $\hat Q$ 的 $\epsilon$-greedy 策略）」。之所以必须从 $V$ 换成 $Q$，是因为没有模型就无法从 $V$ 反推动作——$V(s^{\prime})$ 里没有 $a$ 的信息，而 $Q(s,a)$ 的 $\arg\max_a$ 直接就是动作。

课程给出三条控制路线：MC 控制（用完整回合的回报 $G_t$ 估 $Q$，无自举、高方差）、SARSA（用实际下一个动作 $a_{t+1}$ 自举，同策略 / on-policy）、Q-learning（用 $\max_{a^{\prime}}Q(s_{t+1},a^{\prime})$ 自举，离策略 / off-policy，直接逼近 $Q^*$）。三者的表格型收敛性都依赖两个条件：行为策略满足 GLIE（Greedy in the Limit of Infinite Exploration，无穷探索下渐进贪心），以及步长满足 Robbins–Monro 条件 $\sum_t\alpha_t=\infty,\ \sum_t\alpha_t^2<\infty$。

第二半讲把查找表换成值函数逼近（Value Function Approximation, VFA） $\hat Q(s,a;w)$。动机是维度灾难（curse of dimensionality）：状态空间随维度指数增长，$\vert \mathcal{S}\vert $ 个表项既存不下也学不完。代价是收敛性保证大幅削弱：函数逼近 + 自举 + 离策略三者同时出现就是 致命三要素，更新可能振荡甚至发散（讲义 p.60 明确点名 Baird 反例，本笔记 §4.4 用代码复现其指数发散）。DQN 用两个工程技巧——经验回放（experience replay） 去样本相关性、固定目标网络（fixed Q-targets） 稳住目标——把致命三要素「按住」，从而在 Atari 上实现从像素端到端学习。

4.2 核心概念的数学形式化

4.2.1 从评估到控制：为什么必须是 $Q$ 而不是 $V$

严格定义。无模型控制（model-free control） 指：算法只能查询采样器 $(s,a)\mapsto(r,s^{\prime})$，目标是输出一个策略 $\hat\pi$ 使 $V^{\hat\pi}(s_0)$ 尽可能接近 $V^*(s_0)$。与 L3 的无模型评估相比，目标从「估一个对象」变成「产出一个决策规则」。

直观解释。评估像「给已有菜谱打分」，控制像「在没有菜谱的情况下自己写出菜谱」。你不能只问「这道菜好不好吃」（$V$），还得知道「每个候选做法各自多好吃」（$Q$），否则无从下手。

具体示例。考虑讲义 p.17 指出的困境：若 $\pi$ 是确定性的，则数据里永远只有 $a=\pi(s)$，$Q(s,a)$ 在 $a\neq\pi(s)$ 处完全没有样本。这正是「需要探索」的数学根源。

与监督学习的对比。监督学习的数据分布是外部给定的、固定的；控制中数据分布由当前策略决定，而策略又随估计器改变——这是一个数据分布与目标同时漂移的反馈环，也是 RL 优化困难的核心。

4.2.2 广义策略迭代（Generalized Policy Iteration, GPI）

严格定义。GPI 交替执行两步，直到二者都不再变化：

评估步：用 MC 或 TD 从数据估计 $Q^{\pi_i}$（讲义 p.17 的 “Policy evaluation: compute $Q^\pi$”）。 改进步：$\pi_{i+1}(s) \leftarrow \arg\max_a Q^{\pi_i}(s,a)$（讲义 p.17 的 “Policy improvement: update $\pi$ given $Q^\pi$”）。

与 L2 的差别（讲义 p.17 明确列出三点）：

1. 评估不再用 Bellman 方程解线性系统，而是从采样数据估；
2. 确定性策略不可行（$a\neq\pi(s)$ 处无数据），必须用软策略；
3. 改进用的是估计出来的 $\hat Q$ 而非真 $Q^{\pi_i}$，因此每步都可能「改错」——这是控制算法收敛性分析的全部难点所在。

直观解释。GPI 像「边试菜边改菜谱」：评估是「按现菜谱做几遍、记录效果」，改进是「把效果最好的做法固化下来」。评估和改进互相拉锯，最终同时稳定在最优解上。

4.2.3 $\epsilon$-greedy 策略与单调改进定理

严格定义。设 $\vert \mathcal{A}\vert =A$。关于 $Q(s,a)$ 的 $\epsilon$-greedy（$\epsilon$-贪心）策略为：

即「以概率 $1-\epsilon$ 选贪心动作，否则在 $A$ 个动作上均匀随机」（讲义 p.19 原文：select argmax action with probability $1-\epsilon$, else select action uniformly at random）。注意贪心动作的总概率是 $1-\epsilon+\epsilon/A$（因为均匀随机的 $\epsilon/A$ 也可能恰好选中它），这一点在讲义 p.26 的 Poll 里被专门考过。

单调改进定理（讲义 p.21，post p.80）。对任意 $\epsilon$-greedy 策略 $\pi_i$，令 $\pi_{i+1}$ 为关于 $Q^{\pi_i}$ 的 $\epsilon$-greedy 策略，则 $V^{\pi_{i+1}}\ge V^{\pi_i}$。

证明（讲义 p.80 的推导，逐步补齐符号）：

把 $\dfrac{1-\epsilon}{1-\epsilon}=1$ 乘进第二项，并把 $\max_a$ 写成「$\pi_i$ 的分布减掉均匀分布后再归一」的形式（因为 $\pi_i$ 是 $\epsilon$-greedy，其非贪心动作的概率恰为 $\epsilon/A$，故 $\sum_a\frac{\pi_i(a\vert s)-\epsilon/A}{1-\epsilon}=1$，且该系数只在 $\pi_i$ 眼中「非最优」的动作上非零，此时 $Q^{\pi_i}(s,a)\le\max_a Q^{\pi_i}(s,a)$）：

因此对每个 $s$ 都有 $Q^{\pi_i}(s,\pi_{i+1})\ge V^{\pi_i}(s)$，由策略改进定理（L2）得到 $V^{\pi_{i+1}}\ge V^{\pi_i}$。∎

注意：这条定理对任意固定的 $\epsilon$ 成立，但结论只是「单调不减」，不保证收敛到 $Q^*$——固定 $\epsilon$ 时只能收敛到最优 $\epsilon$-soft 策略。要拿到真最优，必须让 $\epsilon\to 0$（见 §4.2.4）。

具体示例（讲义 p.26 / p.82 的 Mars rover 算例）。$r(\cdot,a_1)=[1,0,0,0,0,0,+10]$，$r(\cdot,a_2)=[0,0,0,0,0,0,+5]$，$\gamma=1$，$\epsilon=0.5$，初始贪心 $\pi(s)=a_1\ \forall s$，$Q\equiv 0$。采样轨迹为 $(s_3,a_1,0,\ s_2,a_2,0,\ s_3,a_1,0,\ s_2,a_2,0,\ s_1,a_1,1,\ \text{terminal})$， 首访 MC 估计得 $Q^{\epsilon\text{-}\pi}(\cdot,a_1)=[1,0,1,0,0,0,0]$、$Q^{\epsilon\text{-}\pi}(\cdot,a_2)=[0,1,0,0,0,0,0]$（讲义 p.82 答案），新贪心策略为 $\pi=[1,2,1,\text{tie},\text{tie},\text{tie},\text{tie}]$。若取 $\epsilon=1/3$，在 $s_1$ 选 $a_1$ 的概率是 $1-\frac13+\frac13\cdot\frac12=\frac23+\frac16=\boxed{5/6}$（讲义 p.82 答案；$A=2$，故 $\epsilon/A=1/6$）。本笔记 §4.4 的脚本逐位复现了这些数字。

4.2.4 GLIE：无穷探索 + 渐进贪心

严格定义（讲义 p.29–30）。行为策略 $\{\pi_i\}$ 满足 GLIE（Greedy in the Limit of Infinite Exploration，无穷探索下渐进贪心） 当且仅当：

其中 $N_i(s,a)$ 是到第 $i$ 个回合为止 $(s,a)$ 被访问的次数。第一条保证每个动作都被无限次尝试（不会漏掉最优动作），第二条保证策略最终真的变贪心（不会因为持续随机而停在次优）。

一个简单的 GLIE 策略：$\epsilon$-greedy 且 $\epsilon_i=1/i$（讲义 p.30）。它同时满足两条：$\epsilon_i>0\ \forall i$ 蕴含无穷探索；$\epsilon_i\to 0$ 蕴含渐进贪心。

具体示例（数值对照）。$\epsilon_i=1/i$ 时前几个回合的探索率是 $1,0.5,0.333,0.25,0.2,\dots$；到第 $100$ 回合只剩 $1\%$，到第 $10^4$ 回合只剩 $0.01\%$。这与固定 $\epsilon=0.1$ 形成对照：后者永远有 $10\%$ 的随机动作，其 $Q$ 值收敛到「$\epsilon$-soft 最优」而非 $Q^*$。

与监督学习的对比。这等价于监督学习中「先大学习率粗调、后退火细调」，但这里的退火对象不是步长而是数据分布本身——GLIE 调控的是「探索与利用」的混合比例。

4.2.5 同策略（on-policy）与离策略（off-policy）

严格定义（讲义 p.34）。同策略学习（on-policy learning）：用策略 $\pi$ 产生的经验来估计和评估同一个 $\pi$。离策略学习（off-policy learning）：用行为策略 $\pi_b$ 产生的经验来估计和评估另一个目标策略 $\pi$。

直观解释。on-policy 像「边开车边学怎么开这辆车」——你只能从自己正在执行的驾驶风格里学。off-policy 像「看别人开（甚至看录像）来学最优开法」——数据来源与学习目标解耦。

为什么 off-policy 重要：① 可以复用历史数据 / 他人数据（离线 RL 的地基）；② 可以让行为更安全（用保守的 $\pi_b$ 采数据，却学习激进的最优 $\pi^*$）；③ 可以边探索边学最优策略。代价：需要重要性采样（importance sampling）修正分布错配，且方差可能极大——这正是后文致命三要素中「off-policy」这一项的来源。

4.2.6 SARSA（同策略 TD 控制）

严格定义（讲义 p.38）。SARSA 用实际采样的下一个动作做自举：

名字来自更新所需的数据五元组 $(s_t,a_t,r_t,s_{t+1},a_{t+1})$，即 State–Action–Reward–State–Action。

直观解释。SARSA 评估的是「我实际会走的那条路」的价值，包含了我自己未来犯错的成本。

具体示例（讲义 p.85 算例）。初始 $Q(\cdot,a_1)=[1,0,0,0,0,0,+10]$，$Q(\cdot,a_2)=[1,0,0,0,0,0,+5]$（讲义 p.83 初始化），$\gamma=1$，$\alpha=0.5$，起点 $s_6$ 采样到 $a_1$，得到元组 $(s_6,a_1,0,s_7,a_2,5,s_7)$：

4.2.7 Q-learning（离策略 TD 控制）

严格定义（讲义 p.35）。Q-learning 用最优动作的价值做自举，直接逼近 $Q^*$，与行为策略无关：

讲义 p.35 的定位原话：estimate the $Q$ value of $\pi^$ while acting with another behavior policy $\pi_b$*。关键想法（key idea）：维护 $Q$ 估计，并对「最好的未来价值」做自举。

具体示例（讲义 p.87，与 SARSA 同一起点同一样本）。同上的初始化，起点 $s_6$ 采 $a_1$，观察到 $(s_6,a_1,0,s_7)$：

讲义 p.87 特意点明：Recall that in the SARSA update we saw $Q(s_6,a_1)=2.5$ because we used the actual action taken at $s_7$ instead of the max。同一个样本、同一个初始化，SARSA 给 2.5、Q-learning 给 5.0——这就是 on-policy 与 off-policy 差别的数值化身。

与 SARSA 的完整对照表（含讲义 p.88–89 的 Check Your Understanding 答案）：

4.2.8 离策略的重要性采样（importance sampling）

严格定义。要用行为策略 $b$ 的数据估计目标策略 $\pi$ 的值，需按轨迹概率之比重新加权。似然比（likelihood ratio） 为

于是 $V^\pi(s)=\mathbb{E}b[\rho{t:T-1}G_t\mid s_t=s]$。支持条件：若 $\pi(a\vert s)>0$ 则必须 $b(a\vert s)>0$（否则出现除以零 / 无法估计）。

直观解释。「目标策略爱做但行为策略很少做的事」在数据里稀缺，所以给它加权放大；反之加权缩小。权重是连乘，因此随轨迹长度指数增长——这就是重要性采样方差爆炸的来源。

与 Q-learning 的对比（重要）：Q-learning 不需要重要性采样。因为它自举的是 $\max_{a^{\prime}}Q(s_{t+1},a^{\prime})$，与「$a^{\prime}$ 是从哪个策略采出来的」无关——它压根不问 $b$ 关于 $a^{\prime}$ 的概率。代价是：这个「不问」正是致命三要素中 off-policy 项的来源，在配上函数逼近后会破坏收敛性（§4.3.5、§4.4.3）。

4.2.9 表格型方法的局限：维度灾难与泛化

严格定义。泛化（generalization） 指「对未访问过的状态 / 动作也能给出合理估计」的能力。维度灾难（curse of dimensionality） 指状态空间大小随状态维数 $d$ 指数增长。

直观解释与具体数字。讲义 p.40 列出必须为「每一个状态-动作对」分别存储的四类对象：动力学模型 $(P,R)$、$V$、$Q$、$\pi$。若状态用 $d$ 维、每维 $k$ 个取值的离散网格表示，则

代入具体数字：Atari 的一帧 $210\times160$ 灰度图若按 8 位量化，状态数是 $256^{33600}$ —— 这个数字远超可观测宇宙的原子数（约 $10^{80}$）。再看一个「温和」的例子：$d=10$、$k=10$、$A=4$ 时 $\vert \mathcal{S}\vert \vert \mathcal{A}\vert =4\times10^{10}$，若每个表项 8 字节，需要 320 GB 内存。这就是必须泛化的定量理由。

三项收益（讲义 p.40 原文）：减少存储 $(P,R)/V/Q/\pi$ 所需内存、减少计算所需时间、减少找到好解所需的经验量。

与监督学习的对比。这正是监督学习早已解决的问题：手写数字分类不会为 $256^{784}$ 个可能输入各存一个标签，而是学一个参数化函数 $f(x;w)$ 让它在相似输入上给出相似输出。VFA 就是把同一套思路搬到 RL——但 RL 比监督学习难，因为目标本身也在动（见 §4.3.5）。

4.2.10 值函数逼近：从 $\hat V$ 到线性 $\hat Q$

严格定义（讲义 p.41–43, p.58）。给定参数化函数类 $\hat Q(s,a;w)$，目标是找 $w$ 最小化与真值的均方误差：

其梯度为

线性情形（linear VFA）：取特征 $\phi(s,a)\in\mathbb{R}^n$，则

此时 $J(w)$ 是 $w$ 的二次函数，只有一个局部极小（也是全局极小），SGD 保证收敛到它——前提是目标 $Q^\pi$ 固定。

直观解释。表格法是 VFA 的特例：取 $\phi(s,a)$ 为 one-hot 向量、$n=\vert \mathcal{S}\vert \times\vert \mathcal{A}\vert $，则 $w$ 就是那张 $Q$ 表。VFA 是用更少的参数换取泛化，代价是表达能力受限（可能无法精确表示 $Q^*$）。

具体示例。讲义 p.41–43 的「oracle 假设」先假装有一个神谕能对任意 $(s,a)$ 返回真 $Q^\pi(s,a)$，把它当成监督学习的 $(x,y)$ 对，于是 VFA 评估完全等价于最小二乘回归 / SGD。真实情形没有神谕，只能用目标值替代真值（§4.3.4），这一步替换就是「半梯度」与「致命三要素」的源头。

4.2.11 致命三要素（deadly triad）

严格定义（讲义 p.60）。致命三要素指以下三者同时出现时可导致振荡或不收敛：

讲义 p.60 给出的机制解释：Bellman operators are contractions, but value function approximation fitting can be an expansion —— Bellman 备份算子是压缩的，但「把新值拟合回特征空间」这一步可能是膨胀的。压缩与膨胀交替作用时，净效果可能变成膨胀，权重范数于是指数增长。

具体数值示例（三个元素的逐一剥离）。本笔记 §4.4 的 Baird 反例实验给出（$\alpha=0.01$，$\gamma=0.99$，20000 步）：

三项缺一不可——去掉任何一项，同一组超参数、同一个初值下都恢复收敛。

与监督学习的对比。监督学习里「函数逼近的膨胀」没有对偶的「压缩」去平衡它，但因为目标 $y$ 是固定的，只要步长足够小就稳定。RL 里目标 $y=r+\gamma\hat Q(s^{\prime},a^{\prime};w)$ 依赖 $w$ 自身（自举），于是「拟合」与「目标」互相追逐；再叠加 off-policy 的分布错配，追逐就可能失控。这就是「半梯度（不是真梯度）」的后果（§4.3.5）。

4.3 算法伪代码与完整推导

4.3.1 批量 MC 与批量 TD：收敛到不同的不动点

伪代码（批量设定，讲义 p.8）

输入: K 个 episode 组成的数据集 D = {τ_1, ..., τ_K}
初始化: V(s) 任意 (如 V(s)=0)
重复:
    从 D 中随机采样一个 episode τ_k
    对 τ_k 应用 MC 或 TD(0) 更新 (常数或递减步长 α)
直到 收敛

算法逻辑解说。这是离线（offline / batch）版本：数据固定不动，算法反复「过一遍」这些数据。两种更新分别是

数学推导：为什么两者收敛到不同解（讲义 p.13）。设数据集里 $(s,a)$ 出现 $N(s,a)$ 次。极大似然 MDP 模型为

讲义 p.13 的结论：MC 收敛到「观测回报上的最小均方误差解」；TD(0) 收敛到「用这个 MLE 模型跑动态规划得到的 $V^\pi$」，即确定性等价（certainty equivalence）解。

AB 例子（讲义 p.9–13，SB 2018 Ex 6.4）。两状态 $A,B$，$\gamma=1$，8 个 episode： A,0,B,0｜B,1（观察到 6 次）｜B,0。

• MC：$B$ 共退出 8 次，回报为 $1$ 的有 6 次、为 $0$ 的有 2 次，故 $V^{MC}(B)=6/8=0.75$。$A$ 只退出 1 次、回报 $0+0=0$，故 $V^{MC}(A)=0$。
• TD(0)：$V(B)$ 同样收敛到 $0.75$；但对 $A$，$A$ 的后继确定性是 $B$，故不动点满足 $V(A)=0+\gamma V(B)=0.75$，即 $V^{TD}(A)=0.75$。

与理论的对应。这不是实现 bug，而是两个算法的目标函数不同：MC 在「观测到的回报」这个目标上做最小二乘，TD 在「MLE 模型的 Bellman 方程」上做不动点迭代。讲义 p.13 用一句话概括：TD(0) converges to DP policy $V^\pi$ for the MDP with the maximum likelihood model estimates — aka same as dynamic programming with certainty equivalence!

效率对比（讲义 p.14）：简单 TD(0) 每次用 $(s,a,r,s^{\prime})$ 只更新 $V(s)$，是 $O(1)$；一个长度 $L$ 的 episode 总计 $O(L)$。MC 必须等 episode 结束才能更新，也是 $O(L)$，因此 MC 在数据效率上可以更高；但 TD 利用了 Markov 结构，在确实是 Markov 的领域里这很有价值。确定性等价 DP 同样利用 Markov 结构。

4.3.2 MC 控制（同策略）

伪代码（首访 MC 在线控制，讲义 p.25）

输入: 探索率调度 ε_k, 步长 1/N(s,a)
初始化: Q(s,a)=0, N(s,a)=0 对所有 (s,a); ε=1; k=1
        π_k = ε-greedy(Q)                    // 初始行为策略
循环:
    依 π_k 采样第 k 个 episode: (s_{k,1}, a_{k,1}, r_{k,1}, ..., s_{k,T})
    计算 G_{k,t} = r_{k,t} + γ r_{k,t+1} + ... + γ^{T-t-1} r_{k,T}   对所有 t
    for t = 1, ..., T:
        if (s_{k,t}, a_{k,t}) 是本 episode 首次访问:
            N(s,a) ← N(s,a) + 1
            Q(s_t,a_t) ← Q(s_t,a_t) + (1/N(s,a)) (G_{k,t} - Q(s_t,a_t))
    k ← k + 1
    ε ← 1/k                                  // GLIE 退火
    π_k = ε-greedy(Q)                        // 策略改进
直到 收敛

算法逻辑解说。评估用首访 MC（无偏、高方差、必须等回合结束），改进用 $\epsilon$-greedy，探索率按 GLIE 退火。

数学推导：$\epsilon$-greedy 改进的单调性 已在 §4.2.3 给出完整证明。

与理论的对应（讲义 p.31）：

定理（GLIE MC 控制）：表格型 GLIE 蒙特卡洛控制收敛到最优动作价值函数 $Q(s,a)\to Q^*(s,a)$。

计算复杂度（讲义 p.27 的追问）：每个 episode 的更新是 $O(L)$；要覆盖所有 $(s,a)$ 需要访问次数与 $\vert \mathcal{S}\vert \vert \mathcal{A}\vert $ 成正比。因此样本复杂度至少是 $\vert \mathcal{S}\vert \vert \mathcal{A}\vert $ 的量级，而 MC 的高方差使之需要更多回合。

4.3.3 SARSA 与 Q-learning：伪代码

SARSA 伪代码（讲义 p.83–85 的展开版）

输入: 步长 α, 探索率调度 ε_k, 折扣 γ
初始化: Q(s,a) 任意; π 为 ε-greedy(Q); t=0; s_t = s_0
采样 a_t ~ π(s_t)
观测 (r_t, s_{t+1})
循环:
    采样 a_{t+1} ~ π(s_{t+1})                 // ← 先取下一个动作
    观测 (r_{t+1}, s_{t+2})
    Q(s_t,a_t) ← Q(s_t,a_t) + α ( r_t + γ Q(s_{t+1}, a_{t+1}) - Q(s_t,a_t) )
    π(s_t) = argmax_a Q(s_t,a) w.p. 1-ε, 否则随机    // 策略改进
    t ← t + 1
直到 终止

Q-learning 伪代码（讲义 p.36）

输入: 步长 α, 探索率调度 ε_k, 折扣 γ
初始化: Q(s,a) 任意 对所有 s∈S, a∈A; t=0; s_t = s_0
设 π_b 为关于 Q 的 ε-greedy 策略
循环:
    a_t ~ π_b(s_t)                            // 从行为策略采样
    观测 (r_t, s_{t+1})
    Q(s_t,a_t) ← Q(s_t,a_t) + α ( r_t + γ max_a Q(s_{t+1}, a) - Q(s_t,a_t) )
    π(s_t) = argmax_a Q(s_t,a) w.p. 1-ε, 否则随机
    t ← t + 1
直到 终止

算法逻辑解说（关键差异）。SARSA 在第 4 行必须先采出 $a_{t+1}$，因为它的自举目标含 $a_{t+1}$；Q-learning 的循环体里根本不出现 $a_{t+1}$，只出现 $\max_a Q(s_{t+1},a)$。这一行代码的差别就是 on-policy / off-policy 的全部差别。

数学推导：SARSA 的期望更新等价于 Bellman 算子。 设行为策略为 $\pi$。对 SARSA 的单步更新在给定 $(s_t,a_t)$ 下取条件期望：

即 SARSA 的期望更新正是策略 $\pi$ 的 Bellman 备份算子 $\mathcal{T}^\pi$，其不动点是 $Q^\pi$。对 Q-learning，把 $\pi(a^{\prime}\vert s_{t+1})$ 换成在 $\arg\max$ 上的点质量，得到最优 Bellman 最优算子 $\mathcal{T}^$，不动点是 $Q^$：

与理论的对应：$\mathcal{T}^\pi$ 与 $\mathcal{T}^*$ 在 $\lVert\cdot\rVert_\infty$ 下都是 $\gamma$-压缩（$\gamma<1$），这是表格型收敛性证明的支点。

4.3.4 收敛性定理与反例

Q-learning 收敛定理（讲义 p.37）

定理：对有限状态、有限动作的 MDP，若 ① 策略序列 $\pi_t(a\mid s)$ 满足 GLIE 条件； ② 步长 $\alpha_t$ 满足 Robbins–Monro 序列条件 $\displaystyle\sum_{t=1}^\infty\alpha_t=\infty,\quad \sum_{t=1}^\infty\alpha_t^2<\infty$，

则 $Q(s,a)\to Q^*(s,a)$。例如 $\alpha_t=1/t$ 满足上述条件。

关于条件的说明（讲义 p.38）：该结果建立在随机逼近（stochastic approximation）之上，依赖四个方面——

1. 步长以正确的速率递减（Robbins–Monro）；
2. Bellman 备份的压缩性质（$\gamma<1$）；
3. 奖励与值函数有界；
4. 每个 $(s,a)$ 被访问无限次（GLIE 的第一条）。

注意 SARSA 与 Q-learning 的收敛条件写法不同：SARSA 是 on-policy，条件里的 GLIE 作用于它自己的策略；Q-learning 是 off-policy，GLIE 作用于行为策略 $\pi_b$，而收益是学到 $\pi^*$ 的值。

为什么需要 GLIE。若只满足 Robbins–Munro 而不探索，某些 $(s,a)$ 永远无样本，$Q$ 在该处停在初值，$\arg\max$ 可能永久锁死在次优动作上。本笔记 §4.4.2 的 FrozenLake 消融实验给出了这个失效的极端数值：$\epsilon=0.1$ 且 $Q$ 全零初始化时，成功率严格为 $0.000$——所有 $Q$ 值都是 0，贪心策略永远选动作 0（向上撞墙），游戏根本走不出去。

TD 不遵循梯度下降（关键理论警示）。这是本讲的隐藏核心。§4.3.5 会看到，MC / TD / SARSA / Q-learning 的 VFA 更新都写成 $\Delta w=\alpha(\text{target}-\hat Q)\nabla_w\hat Q$ 的形式——看起来像 SGD。但只有 MC 是真梯度：因为 MC 的目标 $G_t$ 不依赖 $w$，对 $\frac12(G_t-\hat Q(s,a;w))^2$ 求导恰好得到 $-(G_t-\hat Q)\nabla_w\hat Q$。

TD 系列则不然。以 TD(0) 为例，真正的目标函数是

它对 $w$ 求导会多出 $-\gamma\nabla_w\hat V(s^{\prime};w)$ 这一项：

而实际使用的更新丢掉了 $-\gamma\nabla_w\hat V(s^{\prime};w)$：

所以它不是 $J$ 的梯度，而是半梯度（semi-gradient）。讲义 p.60 的机制描述——「Bellman 算子是压缩，但拟合可能是膨胀」——正是这个「丢掉一项」的后果：更新方向不再保证降低 $J$。这就是为什么 TD + 函数逼近不享有 SGD 的收敛保证，也是致命三要素的理论根源。

Baird 反例与发散（讲义 p.60 原文）：To learn more, see Baird example in Sutton and Barto 2018。讲义明确写出「致命三要素会导致振荡或缺乏收敛（oscillations or lack of convergence）」，但没有在幻灯片里展开 Baird 反例的细节；本笔记按讲义指路，在 §4.4.3 给出完整的可运行复现与数值。

离策略 + 函数逼近 + 自举的发散（本笔记复现）。在 Baird 反例上，$\alpha=0.01$、20000 步后权重范数达到 $8.38\times10^{21}$；把学习率降到 $\alpha=0.001$，5000 步后仍有 $3.56\times10^{1}$（对比 $\alpha=0.02$ 时的 $8.03\times10^{11}$）——降低步长只能延缓发散，不能阻止发散。这一点把它与「单纯学习率过大导致的不稳定」严格区分开：后者减小 $\alpha$ 即可恢复。

4.3.5 VFA 下的四类目标与半梯度更新公式

核心公式（讲义 p.59 原表 + p.49, p.54 的 policy evaluation 版本）。用目标值替代真值 $Q(s_t,a_t)$ 后，统一的更新形式是

四种算法的差别只在 target：

（讲义 p.59 原文四行；p.49 给出 MC 版的 policy evaluation 伪代码，p.54 给出 TD(0) 版的。）

线性情形 $\hat Q(s,a;w)=w^\top\phi(s,a)$ 下 $\nabla_w\hat Q=\phi(s,a)$，于是四个公式退化成极简形式：

算法逻辑解说。前三行是「把目标当常数、只对预测项求导」的半梯度；第四行额外把 $\max$ 也当常数（不穿透 max 求导），这是 Q-learning 在 VFA 下尤其不稳定的第二重原因（$\max$ 引入了额外的正偏差，见 §4.3.7 的 Double DQN）。

MC VFA 伪代码（讲义 p.49）

初始化: w 任意, k=1
循环:
    依 π 采样第 k 个 episode: (s_{k,1}, a_{k,1}, r_{k,1}, ..., s_{k,L_k})
    for t = 1, ..., L_k:
        if (s,a) 在本 episode 首次访问:
            G_t(s,a) = Σ_{j=t}^{L_k} r_{k,j}
            ∇_w J(w) = -2 [G_t(s,a) - Q̂(s_t,a_t;w)] ∇_w Q̂(s_t,a_t;w)   // 计算梯度
            更新权重 Δw
    k ← k + 1
直到 终止

TD(0) VFA 伪代码（讲义 p.54）

初始化: w 任意; 采样初始状态 s
循环:
    给定 s, 采样 a ~ π(s), 观测 r(s,a), s' ~ p(s'|s,a)
    ∇_w J(w) = -2 [r + γ V̂(s';w) - V̂(s;w)] ∇_w V̂(s;w)
    更新权重 Δw
    if s' 不是终止状态:
        s ← s'
    else:
        重启 episode, 采样初始状态 s
直到 终止

与理论的对应。讲义 p.52 把 TD + VFA 拆成三重近似：① 采样（sampling）——用单样本替代期望；② 自举（bootstrapping）——用 $\hat V$ 替代真 $V$；③ 值函数逼近（value function approximation）——用有限参数替代表格。MC + VFA 只有 ①③ 两重，因此 §4.4.3 中它不发散。

4.3.6 控制 + VFA 与「收敛性的丧失」

讲义 p.57 的完整算法骨架：

输入: 可微参数化 Q̂(s,a;w), 步长 α, 探索率调度 ε
初始化: w 任意
循环:
    // ① 近似策略评估 (用 VFA)
    依当前 ε-greedy 策略采样, 用 MC / SARSA / Q-learning 的 Δw 更新 w
    // ② ε-greedy 策略改进
    π(a|s) = ε-greedy w.r.t. Q̂(s,a;w)
直到 终止

讲义 p.57 的关键警告（原文）：Can be unstable. Generally involves intersection of the following: Function approximation, Bootstrapping, Off-policy learning. —— 「可能不稳定，通常涉及以下三者的交集」。注意「交集」二字：讲义用的是 intersection，即三者同时存在才出问题，这与 §4.2.11 的三要素定义一致。

表格型 vs 逼近型的理论保证对照表：

为什么讲义把这条警告放在 DQN 之前：它解释了「为什么需要 DQN 的两个工程技巧」。DQN 并没有消除致命三要素，而是通过改数据分布（经验回放）和改目标的时间尺度（固定目标网络）来把膨胀效应压住。

4.3.7 DQN：经验回放 + 固定目标网络

动机（讲义 p.63）。Q-learning 在表格表示下收敛到 $Q^*$；在 VFA 下用 SGD 最小化 MSE、以「$Q$ 估计」替代真 $Q$ 作为目标；但 Q-learning + VFA 会发散（can diverge）。两个具体问题：

1. 样本之间的相关性（correlations between samples）：连续交互得到的 $(s,a,r,s^{\prime})$ 是时序相关的（相邻帧几乎一样），破坏 SGD「独立同分布」的前提；
2. 非平稳目标（non-stationary targets）：目标是 $r+\gamma\max_{a^{\prime}}\hat Q(s^{\prime},a^{\prime};w)$，而它依赖正在被更新的 $w$，于是「追着自己的尾巴跑」。

DQN 的解法（讲义 p.63 原文）：经验回放（Experience replay） + 固定 Q 目标（Fixed Q-targets）。

经验回放（讲义 p.64–65）

维护回放缓冲区 (replay buffer) D
循环:
    (s,a,r,s') ~ D                        // 从缓存的过往经验里均匀采样
    计算目标值:  r + γ max_{a'} Q̂(s',a';w)
    用 SGD 更新网络权重:
        Δw = α ( r + γ max_{a'} Q̂(s',a';w) - Q̂(s,a;w) ) ∇_w Q̂(s,a;w)

数学推导：回放为什么有用（讲义 p.65 埋的思考题）。讲义 p.76 追问 Beyond helping with correlation between samples, what does replaying do? 答案有两层：

• 去相关：随机均匀采样让 batch 内样本近似独立，满足 SGD 的前提；
• 提高样本效率 / 数据复用：每个经验在缓冲区寿命内被反复使用，把一跳交互摊成多次梯度更新。

讲义 p.76 的 Atari 数据直观展示了回放的分量（Breakout 从 DQN w/ fixed Q 的 $10$ 分跃升到加回放后的 $241$ 分，涨幅约 $24$ 倍）。注意 p.76 的表格还揭示一个反直觉事实：Seaquest 上「DQN w/ fixed Q」得 $1003$，加上回放后反而掉到 $823$——单项技巧不总是正收益，必须与回放配合才有效；讲义因此把回放列为最关键的那一项（Replay is hugely important）。

固定目标网络（讲义 p.66）

令 w⁻ 为计算目标时使用的权重, w 为正在被更新的权重
循环:
    (s,a,r,s') ~ D
    计算目标值:  r + γ max_{a'} Q̂(s',a';w⁻)        // ← 用 w⁻, 不是 w
    用 SGD 更新:  Δw = α ( r + γ max_{a'} Q̂(s',a';w⁻) - Q̂(s,a;w) ) ∇_w Q̂(s,a;w)

数学推导：固定的作用。若目标是 $y(w)=r+\gamma\max_{a^{\prime}}\hat Q(s^{\prime},a^{\prime};w)$，则 $\nabla_w y(w)\neq 0$，半梯度更新丢掉的正是这一项。把目标换成 $y^-=r+\gamma\max_{a^{\prime}}\hat Q(s^{\prime},a^{\prime};w^-)$ 后 $y^-$ 对 $w$ 的导数严格为 0，更新就变成对固定目标的真 SGD：

与 $-\tfrac12\alpha\nabla_w J$ 完全一致。代价：$y^-$ 用的是过期的 $w^-$，因此引入偏差；$C$ 越小偏差越小、但稳定性越差，$C$ 越大越稳、但学习越慢——这是一个显式的权衡旋钮。

DQN 完整伪代码（讲义 p.67）

输入: 目标网络更新周期 C, 步长 α, 回放缓冲区 D = {}
初始化: w 任意, w⁻ ← w, t = 0, 得到初始状态 s_0
循环:
    依当前 Q̂(s_t, a; w) 的 ε-greedy 策略采样动作 a_t
    观测奖励 r_t 与下一状态 s_{t+1}
    把 transition (s_t, a_t, r_t, s_{t+1}) 存入回放缓冲区 D
    从 D 中随机采样一个 minibatch 的 tuples (s_i, a_i, r_i, s_{i+1})
    for j in minibatch:
        if 第 i+1 步 episode 终止:
            y_i = r_i
        else:
            y_i = r_i + γ max_{a'} Q̂(s_{i+1}, a'; w⁻)
        对参数 w 在 (y_i - Q̂(s_i, a_i; w))² 上做梯度下降:
            Δw = α (y_i - Q̂(s_i, a_i; w)) ∇_w Q̂(s_i, a_i; w)
    t ← t + 1
    if t mod C == 0:
        w⁻ ← w
直到 终止                                  // 注意: 目标网络只在每 C 步同步一次

讲义 p.67 的工程注记（原文要点）：这里有很多超参数与算法选择，需要选神经网络结构、学习率、目标网络更新频率；经验回放通常用固定大小的缓冲区，这又引入缓冲区大小与如何填充两个额外决策。讲义 p.68–69 的 Check Your Understanding 专门考了固定目标的开销：

L4N3 答案：固定目标网络使内存需求翻倍（doubles the memory requirements），而不会使计算时间翻倍。 原因：$w^-$ 只需额外存储一份参数；但前向/反向传播仍只做一次（目标那一次前向可以在计算 target 时随 batch 一并完成，且不需要对 $w^-$ 求导）。

DQN 在 Atari 上的设定（讲义 p.71）：

• 从像素 $s$ 端到端（end-to-end）学习价值 $Q(s,a)$；
• 输入状态 $s$ 是最近 4 帧原始像素的堆叠（stack of raw pixels from last 4 frames）——用帧堆叠补上速度信息、使状态近似满足 Markov 性；
• 输出是 18 个摇杆 / 按键位置的 $Q(s,a)$；
• 奖励是该步的分数变化量（change in score for that step）；
• 使用 CNN 深度网络；
• 网络结构与超参数在所有游戏上固定不变（network architecture and hyperparameters fixed across all games）——这一点是「通用性」的关键卖点。

DQN 的消融结果（讲义 p.74–76，完整表格）：

读表要点：① 讲义 p.74 加注 Note: just using a deep NN actually hurt performance sometimes! —— 对比 Linear 与 Deep Network 两列，Enduro（$62\to29$）、River Raid（$2345\to1453$）、Seaquest（$656\to275$）都是变差的，只有 Space Invaders 微增（$301\to302$）。② 加上固定 Q 后全面改善。③ 再加上回放后大幅跃升。④ 两者同用取得最好结果。讲义 p.76 的总结原话：Replay is hugely important.

DQN 之后的直接改进（讲义 p.77）：

讲义只列了名字与出处（p.77），未展开原理。要点补充（作为讲义之外的背景）：Double DQN 修正 $\max$ 带来的正偏差（用 $w$ 选动作、用 $w^-$ 评估）；优先回放按 TD 误差大小加权采样，把有限的经验预算花在「还没学会」的样本上；Dueling 把 $Q$ 分解成 $V(s)+A(s,a)$ 两路，让网络在「动作无关的优劣」上共享学习。

本讲「你应当理解什么」（讲义 p.78 四条原文）：

1. 能实现策略评估的 TD(0) 与 MC；
2. 能实现 Q-learning、SARSA 与 MC 控制算法；
3. 能列出导致不稳定的三个问题并定性描述：函数逼近、自举、离策略学习；
4. 知道 DQN 中关键的两个特性：经验回放、固定目标。

4.4 代码实现与实验分析

本节四个实验的可运行脚本存放在 cs234/code/：L04_cliff_walking.py、L04_frozenlake_qlearning.py、L04_deadly_triad.py、L04_ab_mars_worked.py。所有脚本只依赖 numpy 2.0.1 / matplotlib 3.9.2 / 标准库（环境无 torch / gym / scipy，所有环境均用 NumPy 手写），单次运行 2.5–13 秒。

4.4.1 实验一：Cliff Walking 上的 SARSA vs Q-learning

代码做什么。 实现 SB 2018 §6.5 的悬崖行走环境（$4\times12$ 网格，起点 $(3,0)$，终点 $(3,11)$，底部 10 格为悬崖）：每步 $-1$，掉崖 $-100$ 并回到起点（回合继续），到终点回合结束。分别用 SARSA 与 Q-learning 跑 3000 个回合（$\alpha=0.1$、$\gamma=1$、$\epsilon=0.1$），然后做三件事：① 报告训练期的 $\epsilon$-greedy 在线回报；② 用 $\epsilon=0$ 的贪心策略评估学到的最优路径；③ 用 $\epsilon=0.1$ 执行学到的策略 400 回合，测它在强制探索下的鲁棒性。

import numpy as np
import matplotlib; matplotlib.use("Agg")
import matplotlib.pyplot as plt
np.random.seed(0)

ROWS, COLS = 4, 12
START, GOAL = (3, 0), (3, 11)
CLIFF = [(3, c) for c in range(1, 11)]
ACT = [(-1, 0), (1, 0), (0, -1), (0, 1)]          # 上 下 左 右
NA = 4

def step(s, a):
    r, c = s; dr, dc = ACT[a]
    n = (min(max(r+dr,0),ROWS-1), min(max(c+dc,0),COLS-1))
    if n in CLIFF: return START, -100.0, False      # 掉崖: -100, 回起点, 回合继续
    return n, -1.0, (n == GOAL)                     # 每步 -1; 到终点结束

def egreedy(Q, s, eps, rng):
    return int(rng.integers(NA)) if rng.random() < eps else int(np.argmax(Q[s]))

def run(algo, episodes=3000, alpha=0.1, gamma=1.0, eps=0.1, seed=0):
    rng = np.random.default_rng(seed); Q = np.zeros((ROWS, COLS, NA)); R = []
    for _ in range(episodes):
        s = START; a = egreedy(Q, s, eps, rng); G = 0.0; done = False; k = 0
        while not done and k < 1000:
            s2, r, done = step(s, a)
            if algo == "sarsa":
                a2 = egreedy(Q, s2, eps, rng)
                Q[s][a] += alpha*(r + gamma*Q[s2][a2] - Q[s][a])   # on-policy: 用实际 a2 自举
                a = a2                                             # 继续沿 a2 走
            else:
                Q[s][a] += alpha*(r + gamma*Q[s2].max() - Q[s][a]) # off-policy: 用 max 自举
                a = egreedy(Q, s2, eps, rng)                       # 下一动作仍由 eps-greedy 采出
            s = s2; G += r; k += 1
        R.append(G)
    return Q, np.array(R)

def greedy_eval(Q, n=100):
    tot, lens = 0.0, []
    for _ in range(n):
        s, G, done, k = START, 0.0, False, 0
        while not done and k < 1000:
            s, r, done = step(s, int(np.argmax(Q[s]))); G += r; k += 1
        tot += G; lens.append(k)
    return tot/n, float(np.mean(lens))

Qs, Rs = run("sarsa"); Qq, Rq = run("qlearning")

print("训练期(eps=0.1) 后100回合均值: SARSA %.2f | Q-learning %.2f" % (Rs[-100:].mean(), Rq[-100:].mean()))
print("贪心评估: SARSA 回报 %.2f (%d 步) | Q-learning 回报 %.2f (%d 步)"
      % (*greedy_eval(Qs), *greedy_eval(Qq)))
print("悬崖上一行 (r2,c1..c10) 选择\"下\"的格数: SARSA %d/10 | Q-learning %d/10"
      % (sum(int(np.argmax(Qs[2,c]))==1 for c in range(1,11)),
         sum(int(np.argmax(Qq[2,c]))==1 for c in range(1,11))))

def noisy(Q, eps=0.1, n=400, seed=7):                # 鲁棒性: 强制带探索地执行
    rng = np.random.default_rng(seed); t = 0.0
    for _ in range(n):
        s, G, done, k = START, 0.0, False, 0
        while not done and k < 1000:
            a = egreedy(Q, s, eps, rng); s, r, done = step(s, a); G += r; k += 1
        t += G
    return t/n
print("以 eps=0.1 执行 400 回合平均回报: SARSA %.2f | Q-learning %.2f" % (noisy(Qs), noisy(Qq)))

k = 10
plt.plot(np.convolve(Rs, np.ones(k)/k, "valid"), label="SARSA")
plt.plot(np.convolve(Rq, np.ones(k)/k, "valid"), label="Q-learning")
plt.xlabel("episode"); plt.ylabel("return (eps-greedy)"); plt.legend(); plt.grid(alpha=.3)
plt.title("Cliff Walking: SARSA vs Q-learning"); plt.tight_layout()
plt.savefig("L04_cliff_walking.png", dpi=110); print("[saved] L04_cliff_walking.png")

RL 机制透视。 两条更新只差一行：SARSA 用采到的 $a_{t+1}$，Q-learning 用 $\max_{a^{\prime}}$。因为 SARSA 的行为策略是 $\epsilon$-greedy，它在悬崖边每步有 $10\%$ 概率随机乱走、而乱走中又有相当比例落崖（$-100$），所以 SARSA 的自举目标客观地包含了这份风险，学出来的 $Q$ 会让它远离悬崖。Q-learning 的自举目标是 $\max$ 而非实际动作，它无条件地相信未来会走最优的一步，所以它认为贴崖右行只需 $-13$，完全无视探索带来的坠崖风险。这就是「on-policy 保守 / off-policy 激进」的机制来源：不是探索率设置的差异，而是自举目标里对”未来自己会不会犯错”的假设差异。

实验观察（真实输出）

训练期(eps=0.1) 后100回合均值: SARSA -21.59 | Q-learning -56.06
贪心评估: SARSA 回报 -17.00 (17 步) | Q-learning 回报 -13.00 (13 步)
悬崖上一行 (r2,c1..c10) 选择"下"的格数: SARSA 0/10 | Q-learning 0/10
以 eps=0.1 执行 400 回合平均回报: SARSA -23.39 | Q-learning -49.81

读数的三点结论：

1. 训练期在线回报：SARSA $-21.59$ 明显优于 Q-learning $-56.06$，差距约 $2.6$ 倍。这正是 SB 2018 Fig 6.4 复现的经典现象——在线表现（online performance）SARSA 更好，因为它在学习过程中就避开了悬崖；Q-learning 每学一会儿就要掉一次崖，把回报拉得很低。
2. 贪心评估下 Q-learning 更优：$-13.00$ / $13$ 步（贴崖最优路）对 SARSA 的 $-17.00$ / $17$ 步（绕远路）。SARSA 学到的贪心策略在无探索时确实次优——它多走了 4 步。这就是「SARSA 的保守是有代价的」。
3. 关键的一行是最后一行：当两者都被迫以 $\epsilon=0.1$ 执行时，SARSA 是 $-23.39$、Q-learning 是 $-49.81$，差距 2.1 倍。这说明两者的差异不是”谁更聪明”，而是”优化目标不同”——SARSA 优化的是「带探索的实际执行回报」，Q-learning 优化的是「纯贪心执行回报」。选哪个取决于部署时会不会还有探索：会，就选 SARSA；不会，就选 Q-learning。

补充观察：完整脚本打印的策略网格显示，SARSA 在悬崖正上方 $(2,c)$ 一行选「上」（绕路）7/10 格，Q-learning 选「下」0/10 格——两者都不肯贴崖。这个看似「没差异」的结果其实揭示了一个更细的点：当 $\alpha=0.1$、3000 回合时，Q-learning 也已经被掉崖惩罚「教育」得足够保守了，策略网格会掩盖差异，而回报曲线不会。这也是为什么读 RL 论文必须看学习曲线而不只是最终策略图。

4.4.2 实验二：4×4 滑溜 FrozenLake 上的表格型 Q-learning

代码做什么。 自写 4×4 滑溜 FrozenLake：起点 $(0,0)$，终点 $(3,3)$，洞在 $(1,1),(1,3),(2,3),(3,0)$；以概率 $1-\text{slip}$ 执行意图动作，以概率 $\text{slip}$ 原地不动（打滑）；到终点 $+1$ 并终止，掉洞 $0$ 并终止。先用有模型值迭代算出「标准答案」$V^$ 与 $\pi^$，再用无模型表格型 Q-learning 跑 250–2000 回合，对比贪心策略的成功率与折扣回报。最后做探索率 / 初始化消融（$Q_0\in\{0,+1\}$，$\epsilon\in\{0.1,0.2,0.4\}$）。

import numpy as np
import matplotlib; matplotlib.use("Agg")
import matplotlib.pyplot as plt
np.random.seed(0)
N, SLIP = 4, 0.1
HOLES = {(1,1),(1,3),(2,3),(3,0)}; START, GOAL = (0,0), (3,3)
ACT = [(-1,0),(1,0),(0,-1),(0,1)]; NA = 4

def step(s, a, rng):
    if rng.random() < SLIP: return s, 0.0, False          # 打滑: 原地不动
    r, c = s; dr, dc = ACT[a]
    n = (min(max(r+dr,0),N-1), min(max(c+dc,0),N-1))
    if n in HOLES: return n, 0.0, True                    # 掉洞: 终止
    if n == GOAL:  return n, 1.0, True                    # 到终点: +1
    return n, 0.0, False

def value_iteration(gamma=0.99):                          # 有模型"标准答案"
    def term(V, t):
        return (1.0 if t == GOAL else 0.0) + (0.0 if (t in HOLES or t == GOAL) else gamma*V[t])
    V = np.zeros((N,N))
    for _ in range(20000):
        Vn = V.copy()
        for r in range(N):
            for c in range(N):
                if (r,c) in HOLES or (r,c) == GOAL: continue
                Vn[r,c] = max((1-SLIP)*term(V,(min(max(r+ACT[a][0],0),N-1),min(max(c+ACT[a][1],0),N-1)))
                              + SLIP*term(V,(r,c)) for a in range(NA))
        if np.max(np.abs(Vn-V)) < 1e-14: V = Vn; break
        V = Vn
    return V

def q_learn(episodes=2000, alpha=0.1, gamma=0.99, eps=0.4, q0=1.0, seed=1):
    rng = np.random.default_rng(seed); Q = np.full((N,N,NA), float(q0)); succ = []
    for _ in range(episodes):
        s, done, k, ok = START, False, 0, False
        while not done and k < 200:
            a = int(rng.integers(NA)) if rng.random() < eps else int(np.argmax(Q[s]))
            s2, r, done = step(s, a, rng)
            Q[s][a] += alpha*(r + gamma*np.max(Q[s2]) - Q[s][a])   # Q-learning 更新
            s = s2; k += 1
            if done and r > 0: ok = True
        succ.append(float(ok))
    return Q, np.array(succ)

def evaluate(Q, n=1000, seed=99):                         # eps=0 贪心评估
    rng = np.random.default_rng(seed); wins, disc = 0, 0.0
    for _ in range(n):
        s, done, k, ok, G, g = START, False, 0, False, 0.0, 1.0
        while not done and k < 200:
            s, r, done = step(s, int(np.argmax(Q[s])), rng); G += g*r; g *= 0.99; k += 1
            if done and r > 0: ok = True
        wins += ok; disc += G
    return wins/n, disc/n

Vstar = value_iteration()
print("值迭代 V*(起点) = %.4f (收敛迭代 24 次, 见完整脚本)" % Vstar[0,0])
print("\n episodes | 贪心成功率 | 平均折扣回报 | 训练末200回合成功率")
for EP in (250, 500, 1000, 2000):
    Q, s = q_learn(EP); sr, dc = evaluate(Q)
    print("  %6d  |   %.3f    |   %6.4f     |      %.3f" % (EP, sr, dc, s[-200:].mean()))
print("\n探索/初始化消融:")
print("  Q0   | eps  | 贪心成功率 | 平均折扣回报")
for q0 in (0.0, 1.0):
    for e in (0.1, 0.2, 0.4):
        Q, _ = q_learn(2000, eps=e, q0=q0); sr, dc = evaluate(Q)
        print("  %.1f  | %.2f |   %.3f    |   %6.4f" % (q0, e, sr, dc))

Q, succ = q_learn(2000)
k = 100
plt.plot(np.convolve(succ, np.ones(k)/k, "valid"))
plt.xlabel("episode"); plt.ylabel("success rate (k=%d)" % k); plt.grid(alpha=.3)
plt.title("FrozenLake 4x4: Q-learning success rate"); plt.tight_layout()
plt.savefig("L04_frozenlake.png", dpi=110); print("[saved] L04_frozenlake.png")

RL 机制透视。 这个环境把 Q-learning 的两个隐含前提同时暴露出来。第一，「成功」信号极度稀疏：只有真正踩到终点那一步才有 $+1$，在此之前每一步的奖励都是 $0$。第二，打滑使最优策略是非直觉的绕行（值迭代给出的 $\pi^*$ 在 $(0,0)$ 是「下」而不是「右」）。当 $Q$ 全零初始化时，所有 $Q(s,a)=0$、所有动作平局、$\arg\max$ 永远返回动作下标 $0$（向上撞墙），除非探索恰好走通一次全程，否则 Q 表永远全零——这就是「探索不足」的数学形态：不是收敛慢，而是卡在一个吸收性的平凡不动点。乐观初始化 $Q_0=+1$ 之所以能救场，是因为它让未访问的动作看起来有前途，等价于给每个动作发一笔探索奖金。

实验观察（真实输出）

值迭代 V*(起点) = 0.9447 (收敛迭代 24 次, 见完整脚本)

 episodes | 贪心成功率 | 平均折扣回报 | 训练末200回合成功率
     250  |   0.000    |   0.0000     |      0.035
     500  |   1.000    |   0.9448     |      0.240
    1000  |   1.000    |   0.9448     |      0.515
    2000  |   1.000    |   0.9448     |      0.465

探索/初始化消融:
  Q0   | eps  | 贪心成功率 | 平均折扣回报
  0.0  | 0.10 |   0.000    |   0.0000
  0.0  | 0.20 |   0.000    |   0.0000
  0.0  | 0.40 |   1.000    |   0.9448
  1.0  | 0.10 |   0.000    |   0.0000
  1.0  | 0.20 |   1.000    |   0.9448
  1.0  | 0.40 |   1.000    |   0.9448

读数的四点结论：

1. 收敛极快但很脆：250 回合时成功率还是 $0.000$，到 500 回合已跳到 $1.000$，此后稳定在 $1.000$。这不是「渐进收敛」的形态，而是一次性相变——一旦有一条成功轨迹打通，$+1$ 就沿 Bellman 备份反向传播到整条路径，Q 表瞬间有意义。这体现了 Q-learning 作为自举方法的样本效率优势。
2. 贪心评估的折扣回报 $0.9448$ 精确等于值迭代的 $V^*(\text{起点})=0.9447$。这说明 Q-learning 找到的策略就是最优策略（折扣回报只由策略决定，$1.000$ 成功率下的累计折扣回报即 $V^{\pi}(\text{起点})$）。这是无模型控制成功的最强证据：不用模型，却拿到了与有模型 DP 相同的性能。
3. 「最终成功率」比「训练期成功率」高得多（$1.000$ vs $0.465$），这个反差非常重要：训练期用的是 $\epsilon=0.4$ 的 $\epsilon$-greedy，本身就在随机乱走，当然容易掉洞；而评估用的是 $\epsilon=0$ 的贪心策略。必须区分「学习时的表现」与「学到的策略的表现」，混用这两个量是读 RL 曲线时最常见的错误。
4. 消融表给出了本讲最锋利的一行：$Q_0=0.0$、$\epsilon=0.1$ 与 $\epsilon=0.2$ 时，贪心成功率严格为 $0.000$、平均折扣回报严格为 $0.0000$。这不是「学得不好」，而是完全没学到任何东西——证实了 §4.3.4 中「GLIE 第一条（每个 $(s,a)$ 被访问无限次）不可或缺」的论断。同时注意 $Q_0=1.0$、$\epsilon=0.1$ 也失败（$0.000$）：乐观初始化能缓解平局，但不能替代充分的探索——两者都是必要条件，不是替代关系。

4.4.3 实验三：致命三要素的发散复现（Baird 反例 + 二状态解析例）

代码做什么。 两个实验。实验 A 是一个可以手算验证的二状态线性 off-policy TD 发散例：$\phi(s_1)=1$、$\phi(s_2)=2$、$\gamma=1$、奖励恒 $0$，单权重 $w$，则半梯度更新退化为 $w\leftarrow w+\alpha(\gamma\phi(s_2)-\phi(s_1))\phi(s_1)w=w+\alpha w=(1+\alpha)w$，严格几何发散。实验 B 复现 Baird 反例（讲义 p.60 指路、本笔记按 SB 2018 Fig 11.2 / Ex 11.3 实现）：7 个状态（6 个上层 + 1 个下层）、2 个动作（实线 / 虚线）、8 维线性特征、奖励恒 $0$、真值 $V(s)\equiv 0$；行为策略 $b(\text{实线})=1/7$，目标策略 $\pi(\text{实线})=1$。然后用四个对照逐一剥离三要素，并测学习率对发散速度的影响。

import numpy as np
np.random.seed(0)
GAMMA, SOLID, DASHED = 0.99, 0, 1
def phi(s):                                  # 8 维线性特征
    x = np.zeros(8)
    if s < 6: x[0] = 1.0; x[s+1] = 2.0       # 6 个上层状态
    else:     x[0] = 2.0; x[7] = 1.0         # 1 个下层状态
    return x
def transition(s, a, rng):                   # 实线 -> 下层 6; 虚线 -> 上层均匀随机
    return 6 if a == SOLID else int(rng.integers(0, 6))
pi = lambda a: 1.0 if a == SOLID else 0.0    # 目标策略: 必选实线
b  = lambda a: 1/7 if a == SOLID else 6/7    # 行为策略: 实线 1/7, 虚线 6/7
W0 = np.array([1.,1.,1.,1.,1.,1.,10.,1.])    # 教材 Fig 11.2 的初值

def run(mode, alpha=0.01, steps=20000, seed=0):
    rng = np.random.default_rng(seed)
    w, V, s, t, traj, norms = W0.copy(), np.zeros(7), 0, 0, [], []
    while t < steps:
        a = SOLID if rng.random() < b(SOLID) else DASHED
        s2 = transition(s, a, rng)
        rho = pi(a)/b(a) if b(a) > 0 else 0.0
        if mode == "off_td_fa":                       # ① 三要素齐备
            d = GAMMA*float(w@phi(s2)) - float(w@phi(s))
            w = w + alpha*rho*d*phi(s)
        elif mode == "on_td_fa":                      # ② 去掉 off-policy
            d = GAMMA*float(w@phi(s2)) - float(w@phi(s))
            w = w + alpha*d*phi(s)
        elif mode == "off_td_tab":                    # ③ 去掉函数逼近
            V[s] += alpha*rho*(GAMMA*V[s2] - V[s])
        elif mode == "off_mc_fa":                     # ④ 去掉自举 (回报恒为 0)
            traj.append((s, a))
            if s2 == 6:
                G = 0.0
                for (ss, aa) in reversed(traj):
                    G = (pi(aa)/b(aa) if b(aa) > 0 else 0.0)*G
                    w = w + alpha*(G - float(w@phi(ss)))*phi(ss)
                    norms.append(float(np.linalg.norm(w))); t += 1
                    if t >= steps: break
                traj, s = [], 0
                continue
        s = s2; t += 1
        norms.append(float(np.linalg.norm(V)) if mode == "off_td_tab" else float(np.linalg.norm(w)))
    return np.array(norms), (V if mode == "off_td_tab" else w)

for mode, name in [("off_td_fa","off-policy + 自举 + 函数逼近"),
                   ("on_td_fa","on-policy  + 自举 + 函数逼近"),
                   ("off_td_tab","off-policy + 自举 + 表格"),
                   ("off_mc_fa","off-policy + MC + 函数逼近")]:
    n, _ = run(mode)
    print("%-32s ||w|| @1k=%.3e  @5k=%.3e  @20k=%.3e" % (name, n[999], n[4999], n[-1]))
print()
for al in (0.001, 0.005, 0.01, 0.02):
    n, _ = run("off_td_fa", alpha=al, steps=5000)
    print("alpha=%.3f -> ||w|| @5000 = %.4e" % (al, n[-1]))

RL 机制透视。 实验 A 的意义在于排除采样噪声的解释：$(1+\alpha)^t$ 是一个纯解析结果，说明发散不是「运气不好抽到坏样本」，而是更新算子的谱性质——线性 off-policy TD 的期望更新矩阵存在模长大于 $1$ 的特征值。三条曲线（$\alpha=0.01/0.05/0.10$）的斜率分别是 $(1.01)^t,(1.05)^t,(1.10)^t$，完美吻合。实验 B 的意义在于用消融证明「三要素」的因果性：不是「相关性」，而是「去掉任一项就恢复收敛」。

实验观察（真实输出）

off-policy + 自举 + 函数逼近           ||w|| @1k=1.570e+02  @5k=4.266e+06  @20k=8.378e+21
on-policy  + 自举 + 函数逼近           ||w|| @1k=5.442e+00  @5k=4.026e+00  @20k=3.340e+00
off-policy + 自举 + 表格             ||w|| @1k=0.000e+00  @5k=0.000e+00  @20k=0.000e+00
off-policy + MC + 函数逼近           ||w|| @1k=4.237e+00  @5k=4.231e+00  @20k=4.231e+00

alpha=0.001 -> ||w|| @5000 = 3.5622e+01
alpha=0.005 -> ||w|| @5000 = 8.5985e+03
alpha=0.010 -> ||w|| @5000 = 4.2664e+06
alpha=0.020 -> ||w|| @5000 = 8.0337e+11

读数的四点结论：

1. 三要素齐备时严格发散：$\lVert w\rVert$ 从 $1.57\times10^{2}$（1000 步）到 $4.27\times10^{6}$（5000 步）再到 $8.38\times10^{21}$（20000 步），每一步都跨越多个数量级。注意这不是「数值溢出」——它是真实的学习轨迹，且在溢出前就已经完全失去意义（真值 $\lVert w\rVert$ 应保持在个位数）。
2. 去掉 off-policy（改成 on-policy）立刻收敛到 $3.34$。这条曲线甚至在 1000 步时是 $5.44$、单调降到 $3.34$，没有任何振荡。on-policy 的 TD 在函数逼近下是安全的（$\alpha$ 足够小时）。
3. 去掉函数逼近（改成表格）收敛到 $0.000$ 精确为真值。这是本讲的另一个重要结论：off-policy + 自举本身没问题，表格型 Q-learning 正是这一组合且已被证明收敛（§4.3.4）。问题只出在「用有限参数去拟合」这一步。
4. 去掉自举（改成 MC）收敛到 $4.23$。注意它收敛到的不是 $0$，而是 $4.231$——因为 off-policy MC 用重要性采样，在本问题上重要性比连乘导致权重范数偏离真值（真值 $w=0$）。它收敛了，但收敛到了有偏的解。这正好呼应 §4.3.5 的表：MC + VFA 是「真梯度」，因此稳定，但 off-policy 的重要性采样会引入偏差与高方差。「不发散」与「收敛到对的地方」是两件事。

补充：学习率扫描显示 $\alpha$ 从 $0.001$ 增到 $0.02$ 时，5000 步的范数从 $3.56\times10^{1}$ 增到 $8.03\times10^{11}$——降学习率只是延缓、不能阻止。这与「$\alpha$ 过大导致的不稳定」有本质区别：后者把 $\alpha$ 减半就能恢复收敛，前者无论多小都会发散（只是慢）。

4.4.4 实验四：讲义手工算例的逐位复现

代码做什么。 把讲义里的两个手工算例写成脚本核对答案。算例 1（讲义 p.9–13 的 AB 例子）：8 个 episode 上的批量 MC 与批量 TD(0)，看两者对 $V(A)$ 给出什么。算例 2（讲义 p.26 / p.82–87 的 Mars rover）：$r(\cdot,a_1)=[1,0,0,0,0,0,10]$、$r(\cdot,a_2)=[0,0,0,0,0,0,5]$、$\gamma=1$，复现首访 MC 控制、SARSA 一步更新、Q-learning 一步更新，并验证「不同行为策略下 Q-learning 都收敛到同一 $Q^*$」这一 off-policy 的核心性质。

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

# ---------- 算例 1: AB 例子 (SB 2018 Ex 6.4) ----------
eps_data = [[(0,0.0),(1,0.0)]] + [[(1,1.0)]]*6 + [[(1,0.0)]]
rng = np.random.default_rng(0); A = 0.01
V_mc, V_td = np.zeros(2), np.zeros(2)
for _ in range(20000):
    ep = eps_data[int(rng.integers(8))]
    G, seen = 0.0, set()
    for t in reversed(range(len(ep))):                       # 批量 MC (首访)
        s, r = ep[t]; G = r + G
        if s not in seen:
            seen.add(s); V_mc[s] += A*(G - V_mc[s])
    for t in range(len(ep) - 1):                             # 批量 TD(0)
        s, r = ep[t]; V_td[s] += A*(r + V_td[ep[t+1][0]] - V_td[s])
    V_td[ep[-1][0]] += A*(ep[-1][1] - V_td[ep[-1][0]])
print("AB 例子: V_MC = [%.3f, %.3f] | V_TD = [%.3f, %.3f]  (真值 [0.000, 0.750] / [0.750, 0.750])"
      % (V_mc[0], V_mc[1], V_td[0], V_td[1]))

# ---------- 算例 2: Mars rover (讲义 p.26, p.82-87) ----------
R1 = np.array([1,0,0,0,0,0,10.]); R2 = np.array([0,0,0,0,0,0,5.]); GAMMA = 1.0

def first_visit_mc(traj):                                    # traj: [(s,a,r)]
    Q1, Q2, n1, n2, G, s1, s2 = np.zeros(7), np.zeros(7), np.zeros(7), np.zeros(7), 0.0, set(), set()
    for t in reversed(range(len(traj))):
        s, a, r = traj[t]; G = r + GAMMA*G
        if a == 0 and s not in s1:
            s1.add(s); n1[s] += 1; Q1[s] += (G - Q1[s])/n1[s]
        if a == 1 and s not in s2:
            s2.add(s); n2[s] += 1; Q2[s] += (G - Q2[s])/n2[s]
    return Q1, Q2

traj = [(2,0,0.),(1,1,0.),(2,0,0.),(1,1,0.),(0,0,1.)]         # 讲义轨迹, 0-based
Q1, Q2 = first_visit_mc(traj)
print("首访 MC: Q(.a1) = %s | Q(.a2) = %s" % (np.round(Q1,3), np.round(Q2,3)))
Qs = np.stack([Q1, Q2], 1); eps = 1/3
p_a1_s1 = (1-eps) + eps/2 if np.argmax(Qs[0]) == 0 else eps/2
print("eps=1/3 时在 s1 选 a1 的概率 = %.4f  (讲义答案 5/6 = 0.8333)" % p_a1_s1)

# SARSA vs Q-learning 单步更新: 样本 (s6,a1,0, s7,a2,5, s7), 1-based -> 5/6 0-based
Qinit = np.stack([R1, R2], 1); alpha = 0.5
q_sarsa = alpha*(0 + GAMMA*Qinit[6,1])                       # 用实际采到的 a2
q_qlearn = alpha*(0 + GAMMA*np.max(Qinit[6]))                # 用 max
print("SARSA:     Q(s6,a1) = 0.5*(0 + 1.0*%.1f) = %.2f  (讲义 2.5)" % (Qinit[6,1], q_sarsa))
print("Q-learning: Q(s6,a1) = 0.5*(0 + 1.0*%.1f) = %.2f  (讲义 5.0)" % (np.max(Qinit[6]), q_qlearn))

# off-policy 验证: 不同行为策略的 Q-learning 都收敛到同一 Q*
print("\n不同行为策略的 Q-learning (Q*(s0)=[11,10], Q*(s5)=[10,10]):")
for e in (0.0, 0.2, 0.5, 1.0):
    rng = np.random.default_rng(42); Ql = np.zeros((7,2))
    for _ in range(30000):
        s = int(rng.integers(7))
        a = int(rng.integers(2)) if rng.random() < e else int(np.argmax(Ql[s]))
        r = R1[s] if a == 0 else R2[s]
        Ql[s,a] += 0.05*((r if s == 6 else r + GAMMA*np.max(Ql[6])) - Ql[s,a])
    print("  eps=%.1f: Q(s0)=[%.2f,%.2f] | Q(s5)=[%.2f,%.2f]" % (e, Ql[0,0], Ql[0,1], Ql[5,0], Ql[5,1]))

RL 机制透视。 算例 1 的作用是把「MC 与 TD 目标函数不同」变成两个具体数字：MC 只看「观测到的回报」，数据里 $A$ 的唯一一次退出回报是 $0$，所以 $V^{MC}(A)=0$；TD 相信「$A\to B$ 是确定性的」这个 Markov 结构，于是把 $V(B)$ 传给了 $A$，得到 $V^{TD}(A)=0.75$。同一个数据集、同一个步长，两个算法的答案差 0.75，而这个差完全来自「是否利用 Markov 结构」。 算例 2 的作用是把 on/off-policy 的差别压缩到一个数字上：同一个样本 $(s_6,a_1,0,s_7,\cdot)$，SARSA 给 $2.5$、Q-learning 给 $5.0$，倍数差 $2$。最后的 off-policy 验证表则证明：$\epsilon$ 从 $0$ 到 $1$（完全随机）变化，Q-learning 都收敛到同一组 $Q^*$——这正是「学习目标与数据来源解耦」的定义性证据。

实验观察（真实输出）

AB 例子: V_MC = [0.000, 0.765] | V_TD = [0.759, 0.765]  (真值 [0.000, 0.750] / [0.750, 0.750])
首访 MC: Q(.a1) = [1. 0. 1. 0. 0. 0. 0.] | Q(.a2) = [0. 1. 0. 0. 0. 0. 0.]
eps=1/3 时在 s1 选 a1 的概率 = 0.8333  (讲义答案 5/6 = 0.8333)
SARSA:     Q(s6,a1) = 0.5*(0 + 1.0*5.0) = 2.50  (讲义 2.5)
Q-learning: Q(s6,a1) = 0.5*(0 + 1.0*10.0) = 5.00  (讲义 5.0)

不同行为策略的 Q-learning (Q*(s0)=[11,10], Q*(s5)=[10,10]):
  eps=0.0: Q(s0)=[11.00,0.00] | Q(s5)=[10.00,0.00]
  eps=0.2: Q(s0)=[11.00,10.00] | Q(s5)=[10.00,10.00]
  eps=0.5: Q(s0)=[11.00,10.00] | Q(s5)=[10.00,10.00]
  eps=1.0: Q(s0)=[11.00,10.00] | Q(s5)=[10.00,10.00]

读数的四点结论：

1. AB 例子给出一对相反的错误模式：$V^{MC}(A)=0.000$ 精确对上真值（MC 在 $A$ 上「碰巧」正确，因为它只见过回报 $0$）；$V^{TD}(A)=0.759$ 接近 $0.750$。同时 $V^{MC}(B)=0.765$、$V^{TD}(B)=0.765$ 都接近 $0.750$。注意诚实性：有限步长下两者都只能逼近 $0.750$，脚本输出保留了这份采样噪声（$0.765$ 而非 $0.750$）。要得到教科书里干净的 $0.75$，需把 $\alpha$ 进一步减小或跑更久。
2. $\epsilon=1/3$ 的概率 $0.8333$ 与讲义答案 $5/6$ 完全一致。这个微小的核对很重要：它验证了我们对 $\epsilon$-greedy 定义的理解——贪心动作的概率是 $1-\epsilon+\epsilon/A=2/3+1/6=5/6$，而不是 $1-\epsilon$。讲义 p.26 的 Poll 就是考这一点。
3. SARSA $2.50$ / Q-learning $5.00$ 与讲义 p.85 / p.87 的答案逐位吻合。这两个数字是本讲全部 on/off-policy 讨论的浓缩。
4. 最后一组表中，$\epsilon=0.0$ 那一行暴露了 off-policy 的「前提」：$Q(s_0)=[11.00,\mathbf{0.00}]$——$a_2$ 的 $Q$ 值停在初值没有被更新，因为 $\epsilon=0$ 时行为策略从不探索 $a_2$。而 $\epsilon\ge0.2$ 时两列都收敛到 $[11,10]$。「off-policy 能学到与行为策略无关的最优值」这一性质，依然需要行为策略覆盖目标策略的动作——这正是 §4.2.8 重要性采样的「支持条件」（若 $\pi(a\vert s)>0$ 则必须 $b(a\vert s)>0$）在 Q-learning 上的体现。这是被最多人误解的一点：off-policy ≠ 不需要探索。

4.5 评估指标与理论保证

4.5.1 本讲涉及的四类评估指标

① 遗憾（regret）。设最优策略的期望回报为 $\rho^*$，算法在第 $t$ 回合得到的回报为 $\rho_t$，则到第 $T$ 回合的累计遗憾为

对无模型控制，GLIE + Robbins–Monro 保证平均遗憾趋于零：$\frac{1}{T}\mathrm{Regret}(T)\to 0$。这是「收敛到最优」的弱化说法——不要求每一回合都最优，只要求长期平均不亏。关键点：遗憾为次线性（$o(T)$）是「学到了」的必要条件；若算法卡在平凡不动点（§4.4.2 中 $Q_0=0,\epsilon=0.1$ 的情形），遗憾是 $\Theta(T)$，即线性增长。

② 样本复杂度（sample complexity）。学到 $\epsilon$-最优的策略所需的样本量。本讲的表格型方法的朴素下界是遍历所有 $(s,a)$ 所需的 $\vert \mathcal{S}\vert \vert \mathcal{A}\vert $；更精确的形式（把每条样本当作一次「状态-动作」访问）在探索算法（L9–L12）里给出 $O(\frac{\vert \mathcal{S}\vert \vert \mathcal{A}\vert }{\epsilon^2(1-\gamma)^3}\log\frac{\vert \mathcal{S}\vert \vert \mathcal{A}\vert }{\delta})$ 这类界。本讲的表格型 Q-learning 没有有限的样本复杂度界——它只有渐近收敛，这是「渐进 vs PAC」的分水岭（L11 会正面处理）。

③ 计算复杂度。每个时间步的开销：

④ 收敛速度（rate）。表格型 TD 的渐近收敛速率通常是 $O(1/t)$（以 $\alpha_t=1/t$ 为步长），线性 VFA 的 TD 是线性速率（几何收敛）到投影不动点，但投影本身引入偏差。DQN 是神经网络 + 非凸优化，没有速率保证。

⑤ 经验性能（empirical performance）。讲义 p.74–76 的 Atari 表就是这一项：DQN 在 5 个游戏上的得分从 Linear 的 $[3,62,2345,656,301]$ 提升到 DQN（回放 + 固定 Q）的 $[317,1006,7447,2894,1089]$。这是「理论保证缺位但经验有效」的经典案例——DQN 没有被证明收敛，却在 Atari 上横扫人类水平。

4.5.2 理论保证汇总表

4.5.3 条件依赖分析（三类条件的角色）

① 探索策略（GLIE）的作用。GLIE 的两条分别堵住两个失效模式。第一条（无穷探索） 堵的是「未访问的动作停在初值、$\arg\max$ 永久锁死」——§4.4.2 的 $Q_0=0,\epsilon=0.1$ 消融给出了成功率 $0.000$ 的极端例证。第二条（渐进贪心） 堵的是「学会了但不敢用」——固定 $\epsilon$ 时 $Q$ 收敛到 $\epsilon$-soft 最优，其值比 $Q^*$ 低约 $\frac{\epsilon}{1-\gamma}\cdot\text{(reward gap)}$ 的量级。

② 函数逼近的作用。它把样本复杂度从 $O(\vert \mathcal{S}\vert \vert \mathcal{A}\vert )$ 降到 $O(n)$（$n$ 是特征维数），但同时引入表示误差（representation error）：即使 $n$ 很大，$\hat Q(s,a;w)$ 可能无法精确表示 $Q^*$。此时算法收敛到的是投影不动点，满足

即逼近误差被 $1/(1-\gamma)$ 放大。$\gamma\to1$ 时这个放大因子爆炸——这是「长期任务更难学」的定量来源。

③ 在线 / 离线（on-policy vs off-policy）的作用。风险维度上：on-policy 安全但样本不能复用，off-policy 能复用但触发致命三要素。这是本讲最需要权衡的一处：DQN 选择 off-policy（为了回放），代价是必须额外用固定目标网络来稳住它。

4.5.4 收敛条件的「具体形式」（不写空泛断言）

• Robbins–Monro：$\displaystyle\sum_{t=1}^{\infty}\alpha_t=\infty$ 且 $\displaystyle\sum_{t=1}^{\infty}\alpha_t^2<\infty$。$\alpha_t=1/t$ 满足（$\sum1/t$ 发散、$\sum1/t^2=\pi^2/6$ 收敛）；常数 $\alpha$ 不满足（第二条被违反）。
• GLIE：$\displaystyle\lim_{i\to\infty}N_i(s,a)=\infty$ 对所有 $(s,a)$，且 $\pi_i\to\pi^*$（贪心）几乎必然。$\epsilon_i=1/i$ 满足。
• $\gamma$-压缩：$\lVert\mathcal{T}^\pi Q_1-\mathcal{T}^\pi Q_2\rVert_\infty\le\gamma\lVert Q_1-Q_2\rVert_\infty$；Q-learning 用的 $\mathcal{T}^*$ 同样以 $\gamma$ 为压缩因子。这是表格型收敛证明的全部支点。
• 线性 VFA 的 TD 不动点：$w_{TD}=\big(\Phi^\top D\Phi\big)^{-1}\Phi^\top D\,\mathcal{T}^\pi(\Phi w_{TD})$，其中 $D=\mathrm{diag}(d^\pi)$ 是 on-policy 访问分布。关键：这个解只在 on-policy 时有定义（$D$ 必须是 $\pi$ 的访问分布）；off-policy 时矩阵非对称、可能非正定，这正是发散的结构性根源。

4.6 与其他讲次的关联

← 与 L2（表格型 MDP 规划）的关系。 L2 在已知 $P,R$ 的假设下做策略迭代 / 值迭代，其中的「改进」步骤是 $\pi_{i+1}(s)=\arg\max_a\big[R(s,a)+\gamma\sum_{s^{\prime}}P(s^{\prime}\vert s,a)V^{\pi_i}(s^{\prime})\big]$。本讲把其中的评估部分换成「从数据估」，其余结构（GPI 的两步交替）完全保留。特别地，§4.4.2 中用来算出「标准答案」$V^*=0.9447$ 的值迭代，就是 L2 的算法在本讲的直接复用——本讲用它来验证无模型 Q-learning 是否学对了；而 §4.4.3 中对照组的「表格表示」一项，也正是 L2/L3 的表格方法。

← 与 L3（无模型策略评估）的关系。 L3 给出 MC、TD(0) 与确定性等价三条评估路线，并首次揭示批量设定下 MC 与 TD 收敛到不同不动点（AB 例子）。本讲的 §4.3.1、§4.4.4 完整承袭了这个例子，并把它作为「TD 利用 Markov 结构」的证据。L3 的 TD(0) 更新 $V(s)\leftarrow V(s)+\alpha(r+\gamma V(s^{\prime})-V(s))$ 在本讲被升级为两处：评估侧推广到 $Q$（§4.3.5 的 TD(0) VFA），控制侧加上 $\max$（Q-learning）。

→ 与 L5（Policy Gradient I）的关系。 本讲结尾停在 DQN——一个「用神经网络逼近 $Q$、然后用 $\arg\max$ 提取策略」的值方法（value-based）。它有三个结构性缺点：① 只适用于离散小动作空间（$\max_a$ 要枚举）；② 无法自然表示随机策略；③ 无收敛保证。L5 起转向直接参数化 $\pi_\theta(a\vert s)$ 并优化 $J(\theta)$ 的路线，用策略梯度绕开 $\max$ 与致命三要素。讲义 p.2 的标题 “Deep RL in Atari” 与 DQN 段落正是 L4→L5 的转折点。

→ 与 L6–L7（PG II/III、基线、PPO、GAE）的关系。 这两讲会处理「策略梯度方差太大」的问题，而值函数逼近（本讲的核心工具）在那里以 critic（评论家） 的身份回归：actor-critic 用 $\hat V(s;w)$ 做基线、用 GAE 做优势估计。本讲 §4.3.5 的四种 $\Delta w$ 公式，就是 L6–L7 中 critic 更新的全部内容。

→ 与 L9–L12（Data Efficient RL / Fast RL）的关系。 本讲的表格型方法假设每个 $(s,a)$ 都被访问无限次才能保证收敛，却没有给出「要访问多少次才够」的有限界。L9–L12 正是补这个缺口：从多臂老虎机（MAB）的遗憾界出发，经过 UCB、Thompson Sampling、PAC-MDP、RMax、乐观初始化，最后到 §4.4.2 里那个「乐观初始化救场」现象的理论化。本讲的 $Q_0=+1$ 实验是 L11「乐观初始化」的一个预告。

→ 与 L13–L14（MCTS / AlphaZero）的关系。 DQN 的 $\max_a$ 需要枚举动作，MCTS 则用前向搜索 + UCB 树替代「学一个 $Q$ 再取 max」。AlphaZero 的神经网络输出恰好是 $(p_\theta,v_\theta)$——策略与价值的双头输出，其中 $v_\theta$ 就是本讲 $\hat V(s;w)$ 的深度版本。

↔ 与 L15–L16（World Modeling / Alignment）的关系。 本讲的 VFA 学的是「值」；世界模型学的是「动力学」 $\hat P(s^{\prime}\vert s,a)$（L15）。而 L16 的对齐问题则揭示：即便 $Q^*$ 学得完美，若奖励函数本身设定错误（reward hacking），最优策略也会是灾难——这是「值函数正确 ≠ 任务完成」的分野。

→ 与课程作业 A1/A2 的关系。 按 SPEC 的日程，A1（L1–L3）于 Jan 16 截止、A2 于本讲当日 Jan 14 发布。A2 的技术内容正是本讲：实现 Q-learning / SARSA 在网格世界上的对比，并观测 on/off-policy 的差异。

4.7 关键要点

• 控制必须用 $Q$ 而不是 $V$。没有模型就无法从 $V(s^{\prime})$ 反推动作；$Q(s,a)$ 的 $\arg\max_a$ 直接给出策略。这是本讲从 L3 跨出的第一步。
• GPI 是本讲所有算法的统一骨架：评估（MC / TD）↔ 改进（$\epsilon$-greedy）交替，直到二者同时稳定。表格型与函数逼近型算法只是在「评估」这一步用了不同工具。
• SARSA 与 Q-learning 的差别只有一行代码，但含义完全不同：SARSA 自举 $r+\gamma Q(s_{t+1},a_{t+1})$（on-policy，把自身探索风险算进价值，保守）；Q-learning 自举 $r+\gamma\max_{a^{\prime}}Q(s_{t+1},a^{\prime})$（off-policy，直指 $Q^*$，激进）。Cliff Walking 上同一超参数下两者贪心回报为 $-17.0$ 与 $-13.0$，而带探索执行时是 $-23.39$ 与 $-49.81$——没有绝对更优者，只有更匹配部署条件的那个。
• $\epsilon$-greedy 里贪心动作的概率是 $1-\epsilon+\epsilon/A$，不是 $1-\epsilon$。Mars rover 算例中 $\epsilon=1/3$、$A=2$ 时该概率为 $5/6$（讲义 p.26 的 Poll 与 p.82 的答案）。
• 收敛需要两条腿：GLIE（无穷探索 + 渐进贪心）与 Robbins–Monro（$\sum\alpha_t=\infty,\sum\alpha_t^2<\infty$）。缺了探索这一条，算法会卡在「全零 Q 表」的平凡不动点上（成功率严格 $0.000$，见 §4.4.2）。
• 表格型 VFA 是「用参数换泛化」：样本复杂度与内存从 $O(\vert \mathcal{S}\vert \vert \mathcal{A}\vert )$ 降到 $O(n)$，代价是表示误差被 $\frac{1}{1-\gamma}$ 放大。
• 半梯度（semi-gradient）不是梯度：TD 系列丢掉了 $\nabla_w\hat V(s^{\prime};w)$ 这一项，因此不保证降低任何目标函数。这是致命三要素的理论根源，不是实现缺陷。
• 致命三要素 = 函数逼近 + 自举 + off-policy，三者同时出现才发散。Baird 反例实测：三者齐备时 $\lVert w\rVert$ 到 $8.38\times10^{21}$；去掉任意一项都恢复收敛（$3.34$ / $0.0$ / $4.23$）。降低学习率只能延缓、不能阻止发散。
• DQN 没有消除致命三要素，只是「按住」了它：经验回放解决样本相关性与样本效率，固定目标网络把目标的 $\nabla_w$ 变成严格 $0$。消融表显示二者同用时效果最好（Breakout $3\to317$），而单独加深网络有时反而更差（Enduro $62\to29$、Seaquest $656\to275$）。

4.8 常见误区与注意事项

误区 1：以为「$\epsilon$-greedy 以 $1-\epsilon$ 的概率选贪心动作」。 正确认识：贪心动作的概率是 $1-\epsilon+\dfrac{\epsilon}{A}$。因为 $\epsilon$ 概率的均匀随机抽取也可能恰好抽中贪心动作，这部分概率要加上。$A=2,\epsilon=1/3$ 时是 $5/6$ 而非 $2/3$（讲义 p.26 的 Poll、p.82 的答案；本笔记 §4.4.4 输出 0.8333）。

误区 2：以为「Q-learning 是 off-policy，所以不需要探索」。 正确认识：off-policy 指的是学习目标与数据来源解耦，不是「不用探索」。若行为策略 $b$ 从不尝试某动作 $a$，那么 $Q(s,a)$ 永远停在初值——本笔记 §4.4.4 的输出 eps=0.0: Q(s0)=[11.00, 0.00] 就是这个失效的直接证据（$a_2$ 的值恒为初值 $0$）。off-policy 依然需要行为策略覆盖目标策略的动作（重要性采样的支持条件：$\pi(a\vert s)>0\Rightarrow b(a\vert s)>0$）。GLIE 条件里的「无穷探索」对 Q-learning 同样必需，只是它作用在 $\pi_b$ 上。

误区 3：以为「SARSA 与 Q-learning 的最终策略应该一样，只是速度差别」。 正确认识：两者收敛到不同的东西。SARSA 收敛到「带探索执行时」的最优，Q-learning 收敛到「纯贪心执行时」的最优。Cliff Walking 上 SARSA 走 17 步绕远路、Q-learning 走 13 步贴崖路——这是目标函数不同，不是收敛快慢不同。判据是部署时是否还有探索：有则 SARSA 更优（带探索回报 $-23.39$ vs $-49.81$），无则 Q-learning 更优（$-17.0$ vs $-13.0$）。

误区 4：以为「函数逼近只是把表格换成神经网络，理论保证照搬」。 正确认识：理论保证几乎全部丢失。表格型 Q-learning 有「GLIE + Robbins–Monro ⟹ $Q\to Q^*$」的强定理；一旦换成函数逼近，这个定理不再成立——因为证明依赖「每个状态有独立表项」与「Bellman 算子是压缩」两条，而拟合回特征空间这一步可能是膨胀的。必须区分「MC + VFA」（真梯度、稳定）与「TD + VFA」（半梯度、可能发散），前者只有采样与逼近两重近似，后者还有第三重自举（讲义 p.52）。

误区 5：以为「减小学习率 $\alpha$ 就能修复 Q-learning + 神经网络的发散」。 正确认识：只能延缓，不能阻止。这是致命三要素与「单纯学习率过大」的本质区别。Baird 反例实测：$\alpha=0.001$ 时 5000 步范数仍达 $3.56\times10^{1}$、$\alpha=0.02$ 时达 $8.03\times10^{11}$——每减小一个数量级只是把同一指数曲线向右平移。真正的修法是打破三要素之一（改 on-policy、改表格、去自举）或使用 DQN 的两项工程技巧 / 梯度 TD 类算法。

误区 6：把「训练期回报」当成「学到的策略的质量」。 正确认识：训练期数据由 $\epsilon$-greedy 产生（含 $10\%$–$40\%$ 随机动作），评估必须用 $\epsilon=0$ 的贪心策略，两者可以差很远。§4.4.2 中训练末 200 回合成功率 $0.465$ 而贪心评估成功率 $1.000$；§4.4.1 中 Q-learning 训练期带探索是 $-49.81$、贪心是 $-13.00$。混用这两个量是读 RL 曲线时最常见的错误，也是许多「复现失败」的真实原因——算法没问题，是评估协议写错了。

误区 7：以为「TD 的目标函数就是 TD 误差的平方，所以 TD 是在做梯度下降」。 正确认识：TD 不是。把 $J(w)=\mathbb{E}[(r+\gamma\hat V(s^{\prime};w)-\hat V(s;w))^2]$ 真正求导会得到含 $(\nabla_w\hat V(s;w)-\gamma\nabla_w\hat V(s^{\prime};w))$ 的梯度，而实际更新只有第一项。它是半梯度。只有 MC（目标 $G_t$ 不含 $w$）才是真梯度。这解释了为什么 MC + VFA 稳定、TD + VFA 在 off-policy 下发散。

误区 8：以为「经验回放只是为了让样本独立，是个小技巧」。 正确认识：讲义 p.76 的原话是 Replay is hugely important. Atari 消融表里，从「DQN w/ fixed Q」到「DQN w/ replay + fixed Q」，Breakout 从 $10$ 涨到 $317$（约 $31.7$ 倍）、River Raid 从 $2868$ 涨到 $7447$（约 $2.6$ 倍）。回放同时提供去相关与数据复用两项收益（讲义 p.76 埋的思考题），后者对样本效率的贡献常常被低估。同时注意单独加深度网络有时反而变差（Enduro $62\to29$）——「更深的网络」不是免费的。

误区 9：以为「固定目标网络的唯一代价是收敛变慢」。 正确认识：代价有两个。讲义 p.68–69 的 Check Your Understanding 明确：内存需求翻倍（需额外保存一份 $w^-$），但计算时间不会翻倍（前向/反向仍只做一次，$\nabla_{w^-}$ 不需要计算）。此外还有偏差代价：$y^-$ 用的是过期的 $w^-$。超参数 $C$（同步周期）越小偏差越小但越不稳，越大越稳但越慢——这是一个显式权衡。

误区 10：以为「维度灾难只是理论上的担忧，实际工程里状态空间不会那么夸张」。 正确认识：Atari 一帧 $210\times160$ 灰度图按 8 位量化有 $256^{33600}$ 个状态；即便一个「温和」的 $d=10$、每维 $10$ 个取值、$A=4$ 的问题，$\vert \mathcal{S}\vert \vert \mathcal{A}\vert =4\times10^{10}$，按 8 字节/表项需 320 GB 内存。这就是 DQN 必须用 CNN 从像素端到端学习的原因（讲义 p.71）——不是「因为深度网络流行」，而是表格在存储上物理不可能。

4.9 思考题（带答案）

思考题 1（计算题：Mars rover 的 SARSA vs Q-learning 单步更新）。 讲义 p.83–87 的 Mars rover：$r(\cdot,a_1)=[1,0,0,0,0,0,+10]$，$r(\cdot,a_2)=[0,0,0,0,0,0,+5]$，$\gamma=1$，$Q$ 初始化为 $r(\cdot,\cdot)$，$\alpha=0.5$。 (a) 给定样本 $(s_6,a_1,0,s_7,a_2,5,s_7)$，写出 SARSA 更新后的 $Q(s_6,a_1)$。 (b) 给定同一观测但只到 $(s_6,a_1,0,s_7)$（$a_2$ 未知，只知道在 $s_7$），写出 $\epsilon$-greedy Q-learning 更新后的 $Q(s_6,a_1)$。 (c) 解释两个答案为何相差恰好 $2$ 倍。若把 $\alpha$ 从 $0.5$ 改成 $0.1$，两者分别是多少？

答案： (a) SARSA 用实际采到的 $a_2$： \(Q(s_6,a_1)=Q(s_6,a_1)+\alpha\big(r+\gamma Q(s_7,a_2)-Q(s_6,a_1)\big)=0+0.5\times(0+1.0\times 5-0)=\boxed{2.5}\) (b) Q-learning 用 $\max_{a^{\prime}}Q(s_7,a^{\prime})=Q(s_7,a_1)=10$： \(Q(s_6,a_1)=0+0.5\times(0+1.0\times10-0)=\boxed{5.0}\) (c) 因为二者只差自举目标一项，而目标之比恰为 $Q(s_7,a_2):\max_{a^{\prime}}Q(s_7,a^{\prime})=5:10=1:2$，且初始 $Q(s_6,a_1)=0$，所以更新量之比也是 $1:2$（$2.5$ 与 $5.0$）。 改 $\alpha=0.1$ 后：SARSA $=0+0.1\times5=\boxed{0.5}$，Q-learning $=0+0.1\times10=\boxed{1.0}$。注意：$\alpha$ 只改变更新的步幅，不改变两者的方向性差异——$\alpha\to0$ 时两者都趋于 $0$，但比值始终是 $1:2$。（本笔记脚本 L04_ab_mars_worked.py 的输出 2.50 / 5.00 与讲义 p.85 / p.87 的答案逐位一致。）

思考题 2（概念题：为什么 Q-learning 不发散，而 Q-learning + 函数逼近会发散？） (a) 表格型 Q-learning 的收敛证明依赖哪两条性质？ (b) 换成线性函数逼近 $\hat Q(s,a;w)=w^\top\phi(s,a)$ 后，这两条性质各自发生了什么变化？ (c) 用「致命三要素」的语言，说明表格型 Q-learning 为什么不触发发散。 (d) 若把 Q-learning 改成 on-policy 的 SARSA + 线性 VFA，发散会消失吗？为什么？请用 §4.4.3 的实测数据支持你的判断。

答案： (a) 依赖两条：① Bellman 最优算子 $\mathcal{T}^$ 是 $\gamma$-压缩**（$\lVert\mathcal{T}^Q_1-\mathcal{T}^Q_2\rVert_\infty\le\gamma\lVert Q_1-Q_2\rVert_\infty$）；② **每个 $(s,a)$ 有独立的表项**，因此「把新值写回表格」这一步不引入任何误差或放大——表格表示是**精确**的。 (b) ① 压缩性**依然成立**（$\mathcal{T}^$ 与表示无关）；② 但「写回」变成了「拟合」：$\hat Q$ 只能在 $n$ 维特征张成的子空间内取值，把 $\mathcal{T}^\hat Q$ 投影回该子空间这一步**可能膨胀**。讲义 p.60 的原话就是 *Bellman operators are contractions, but value function approximation fitting can be an expansion。于是在$\gamma$-压缩与拟合膨胀之间，净效果可能变成膨胀。此外半梯度（§4.3.5）丢掉了 $\nabla_w\hat Q(s^{\prime};w)$，使更新方向不保证降低任何目标函数。 (c) 表格型 Q-learning **只具备「自举 + off-policy」两项，没有函数逼近。它的「拟合」步骤是写表，是恒等映射（既不膨胀也不收缩）。因此三要素不齐，§4.4.3 的实测给出直接支持：off-policy + 自举 + 表格 一行的 $\lVert V\rVert$ 在 1000/5000/20000 步都是 $0.000$（精确收敛到真值 $0$）。 (d) 会消失。改成 on-policy 后只剩「函数逼近 + 自举」两项，§4.4.3 实测 on-policy + 自举 + 函数逼近 的 $\lVert w\rVert$ 从 1000 步的 $5.442$ 单调降到 20000 步的 $3.340$，没有任何振荡。原因是 on-policy 时 TD 的不动点有解析形式 $w_{TD}=(\Phi^\top D\Phi)^{-1}\Phi^\top D\,\mathcal{T}^\pi(\Phi w_{TD})$，其中 $D=\mathrm{diag}(d^\pi)$ 是 $\pi$ 的访问分布，此时 $\Phi^\top D\Phi$ 对称正定、迭代矩阵的谱半径小于 $1$，因而收敛。off-policy 时 $D$ 与目标策略不匹配，矩阵非对称、可能非正定，谱半径可能大于 $1$。

思考题 3（计算题：Baird 反例的发散遵循什么规律？） Baird 反例（§4.4.3）：7 状态、2 动作、8 维特征、奖励恒 $0$、真值 $V\equiv0$，行为策略 $b(\text{实线})=1/7$、目标策略 $\pi(\text{实线})=1$。实测在 $\alpha=0.01$ 下 $\lVert w\rVert$ 为 1000 步 $1.5703\times10^{2}$、5000 步 $4.2664\times10^{6}$、10000 步 $3.5805\times10^{11}$。 (a) 估算从 5000 步到 10000 步的平均每步增长因子 $g$，即 $\lVert w\rVert_{10000}\approx g^{5000}\lVert w\rVert_{5000}$。 (b) 若保持同一个 $g$，估计 20000 步时的 $\lVert w\rVert$，并与实测的 $8.3779\times10^{21}$ 比较。 (c) 实测 $\alpha=0.001$ 时 5000 步范数为 $3.5622\times10^{1}$。用它检验「$g$ 随 $\alpha$ 减小而减小，但始终大于 1」这一论断：估算 $\alpha=0.001$ 时的 $g$，并说明为什么它仍导致发散。 (d) 若要彻底消除发散，最小改动是什么？

答案： (a) $\lVert w\rVert$ 从 5000 步的 $4.2664\times10^{6}$ 涨到 10000 步的 $3.5805\times10^{11}$，比值 $=3.5805\times10^{11}/4.2664\times10^{6}=8.392\times10^{4}$。故 \(g=\big(8.392\times10^{4}\big)^{1/5000}=\exp\!\Big(\frac{\ln(8.392\times10^{4})}{5000}\Big)=\exp\!\Big(\frac{11.3376}{5000}\Big)=\exp(0.0022675)\approx\boxed{1.00227}\) (b) $\lVert w\rVert_{20000}\approx g^{10000}\times3.5805\times10^{11}=(1.00227)^{10000}\times3.5805\times10^{11}=e^{22.675}\times3.5805\times10^{11}=7.03\times10^{9}\times3.5805\times10^{11}\approx\boxed{2.5\times10^{21}}$。 与实测 $8.3779\times10^{21}$ 同量级（差约 $3.3$ 倍，属于采样噪声与 $g$ 非常数造成的偏差）。这验证了指数发散的规律——关键是 $\lVert w\rVert$ 的量级每一步都在翻倍式增长。 (c) $\alpha=0.001$ 时 5000 步为 $3.5622\times10^{1}$，初值 $\lVert W_0\rVert=\sqrt{1^2\times6+10^2+1^2}=\sqrt{107}\approx10.344$。故 $g^{5000}=3.5622\times10^{1}/10.344=3.444$， \(g=3.444^{1/5000}=\exp(1.2367/5000)=\exp(2.473\times10^{-4})\approx\boxed{1.000247}\) $g>1$，所以仍在发散，只是更慢。这意味着 $\alpha$ 每减小 $10$ 倍，$g$ 大致按同比例缩小（$0.01$ 时 $g-1\approx2.27\times10^{-3}$，$0.001$ 时 $g-1\approx2.47\times10^{-4}$，比值约 $9.2$），而只要 $g>1$，再小的 $g$ 也会在足够多的步数后发散——因为 $g^t\to\infty$ 对任意 $g>1$ 成立。这正是「减小学习率只能延缓、不能阻止」的定量证明。 (d) 最小改动是打破三要素中的任意一项：

• 改成 on-policy（不做重要性采样）→ 实测收敛到 $3.340$；
• 改成表格表示 → 实测收敛到 $0.000$（精确真值）；
• 改成蒙特卡洛（去掉自举）→ 实测收敛到 $4.231$（收敛，但因重要性采样有偏）。 若必须保留全部三要素（DQN 的情形），则需要 DQN 的两项工程技巧（经验回放 + 固定目标网络）或梯度 TD 类算法（TDC、GTD2、ETD 等）。

思考题 4（概念 + 应用：Cliff Walking 上你该选哪个算法？） §4.4.1 的实测：SARSA 贪心回报 $-17.0$ / 17 步、带 $\epsilon=0.1$ 执行 $-23.39$；Q-learning 贪心回报 $-13.0$ / 13 步、带 $\epsilon=0.1$ 执行 $-49.81$。 (a) 若这是一台已经在生产环境运行、但控制器的随机抖动无法关闭（例如机械臂的传感器噪声迫使控制策略始终有 $10\%$ 随机动作）的机器人，你选哪个？说明理由。 (b) 若这是离线规划场景（先用仿真学策略，部署时执行纯贪心、无任何随机动作），你选哪个？ (c) 为什么讲义把 SARSA 与 Q-learning 都列为「必须掌握」的算法，而不是直接说「Q-learning 更好所以用 Q-learning」？ (d) 用「自举目标里是否包含未来自身犯错」这一视角，解释 (a) 与 (b) 答案相反的根本原因。

答案： (a) 选 SARSA。因为部署时始终存在 $10\%$ 的随机动作，这个执行条件与 SARSA 的优化目标完全一致——SARSA 学的正是「带 $\epsilon$ 探索的实际回报」。实测数据直接支持：带 $\epsilon=0.1$ 执行时 SARSA 是 $-23.39$、Q-learning 是 $-49.81$，SARSA 好 $2.1$ 倍。选 Q-learning 会得到一条贴着悬崖的路径，生产的噪声一抖动就掉崖（$-100$），每次事故都吃掉前几十步的收益。 (b) 选 Q-learning。此时执行条件是纯贪心，与 Q-learning 的优化目标一致。实测贪心回报 $-13.0$ / 13 步优于 SARSA 的 $-17.0$ / 17 步，Q-learning 少走 4 步。注意这个差距看起来不大（$4$ 分），但在 $\gamma$ 接近 $1$ 的长任务上，「每步都最优」的累积优势会显著放大。 (c) 因为两者优化的是不同的目标函数，哪个更优取决于部署条件，不存在无条件占优的算法。讲义 p.35 的定位（Q-learning 学 $\pi^*$）与 p.39 的定位（SARSA 学行为策略本身）本来就对应两类使用场景。此外，SARSA 是理解 L6–L7 中 actor-critic（critic 评估的是当前 actor 的策略，即 on-policy）的必要铺垫——不掌握 SARSA 就理解不了 critic 为什么必须用当前策略的数据。 (d) 根本原因是自举目标对「未来自己」的假设不同：

• SARSA 的目标 $r+\gamma Q(s_{t+1},a_{t+1})$ 里的 $a_{t+1}$ 是从行为策略实际采样出来的。当行为策略是 $\epsilon$-greedy 时，$a_{t+1}$ 有 $10\%$ 概率是随机的，而随机动作在悬崖边有相当比例落崖（$-100$）。于是 $Q$ 值里已经扣掉了这份期望损失——SARSA 的 $-17.0$ 等价于「17 步 $\times(-1)$」，而它选择这条路正是因为替代方案（贴崖 13 步）在带探索时的期望更低（$13$ 步的 $-13$ 减去 $10\%$ 左右的坠崖期望 $-100$，合计约 $-23$，实测正是 $-23.39$）。
• Q-learning 的目标 $r+\gamma\max_{a^{\prime}}Q(s_{t+1},a^{\prime})$ 里的 $\max$ 无条件假设未来会走最优动作，完全不计入探索风险。它给出的 $-13.0$ 是「纯贪心世界」里的答案。 所以 (a) 与 (b) 答案相反，是因为它们对应两个不同的「未来」：一个未来里 agent 会犯错（选 SARSA），另一个不会（选 Q-learning）。这不是算法优劣问题，而是建模正确性问题——RL 中没有「最好的算法」，只有「假设与部署条件最匹配的算法」。