前沿专题 · 强化学习理论基础：从一般 MDP 到策略梯度

前置要求：第3章的概率与期望记号（条件期望、全期望公式），以及第11章 · 后训练与对齐中「生成过程是 MDP」小节的生成 MDP 特例记号（$G_t$、TD 残差 ${\delta }_t$、概率比）。未读过第11章也能顺序读完本页，但对照着读，两边的记号会互相点亮。

第11章把一次生成写成了 MDP 的特例：状态是前缀、动作是下一个 token、转移确定、奖励只在序列结束时给一次、$\gamma =1$。它同时声明「动态规划网格世界和 DQN 留在原书」。本页就是那一半：一般 MDP 理论——形式化、Bellman 方程与价值迭代、TD 估计谱系、策略梯度定理的一般形式，以及 AlphaGo 一系的搜索与专家迭代。读完本页，第11章里「critic 的 $V$、GAE、PPO 概率比各是哪个量」的每个对象都能在一般层找到它的定理编号。

本页的一般理论框架与多处讲法顺序吸收自 Ernest K. Ryu 的研究生课程 RL of LLMs (Spring 2025) Chapter 1（Deep RL）；课程页面公开提供讲义与 Cliff Walk 示例的链接。本仓只保留链接与归属，正文用自己的话重述，不复制其文本、图或代码。

边界声明：本页不实现 token 级 PPO——那是第12章 · DeepSeek 架构专题的 GRPO toy（python/llm_core/deepseek_toys.py 的 grpo_policy_update）与第11章 PPO 目标的知识边界所在。本页的动手实验停留在表格 RL：一个网格世界上的蒙特卡洛评估、价值迭代、线性代数精确解与表格 REINFORCE（见 python/llm_core/rl_basics.py）。表格 REINFORCE 是本课唯一一个「真的在跑的策略梯度训练循环」的最小版本；想自己从零写一遍这套流程，走 clean-room 第 9 模块 clean_room/tabular_rl.py（空接口 + 冻结签名，合同见 clean_room/contracts.json 的 tabular-rl 条目）。

---

本页目标

学完后你能做到：

• 写出一般 MDP 的五元组，并解释终态吸收化技巧为什么是后续一切推导的记号地基（随机终止时刻 $T$ 上的期望号交换坑）。
• 复述 Bellman 期望方程与最优性方程的证明结构，特别是「不动点存在唯一」与「不动点恰为最优」分开证明的两段式顺序。
• 说明 $\gamma =1$ 的三种病态，以及「奖励只在终止时给一次」为什么让 RL-LLM 的 $\gamma =1$ 合法。
• 沿 MC → 一步 TD → k-step TD 谱系解释偏差与方差的交换，指出 stop-gradient（PyTorch 的 .detach()）在 TD 目标上切断的是什么。
• 按无偏性逐级验证的顺序复述策略梯度定理的四个方差缩减增强，并解释没有 baseline 时 softmax 归一化在「硬推」什么。
• 讲出 AlphaGo 四步训练中每一步「为什么还不够」，以及 test-time compute 的一句话数学辩护。
• 在 Cliff Walk 上跑通五级实验：MC 评估 → 价值迭代 → 线性代数精确解 → 带 baseline 的表格策略梯度 → REINFORCE。

---

阶段 0：只有一个状态的赌场——bandit

（本阶段的叙事装置与知识框架源自 Pramod Goyal 的 Reinforcement Learning from scratch #1（2026）；知识点对应 Sutton & Barto 第 2 章，正文全部用自己的话重述。）

先交代它在整页里的位置。k 臂老虎机 (k-armed bandit) 是 MDP 的单状态退化情形——只有一个状态、$k$ 个动作可选、每个动作吐出一个奖励样本，没有「下一步到了哪」这回事。它同时是通往完整 MDP 的最缓坡道：估计、探索、利用这些核心难题在这里以最裸的形态出现，却还不背转移概率的包袱。把本阶段放在一切之前还有一个直接动机：第11章会把「terminal-only 奖励」的 LLM 生成设定称为 contextual bandit（上下文老虎机——状态由 prompt 给出的 bandit 变体）；读完这里，那个命名里的每个词就都有了着落。

1. 问题：k 台老虎机，真实均值未知

赌场里排着 $k$ 台老虎机。每台机器 $a$ 有一个未知的真实价值

$$q_{\ast }(a)=\mathbb{E}[R_t\mid A_t=a],$$

即在机器 $a$ 上拉一次所得奖励的期望（$A_t$：第 $t$ 次拉杆选中的动作；$R_t$：那次得到的奖励）；每次拉杆得到的是 $R_t$ 的一个样本——期望相同，单次结果有起伏。若首次见 $\mathbb{E}[\cdot ]$：它是「长期反复取平均」的记号——均匀骰子的点数期望是 $3.5$，但没有任何一次能掷出 $3.5$；期望描述平均水位，不预言单次取值。

若 $q_{\ast }$ 已知，选择毫无悬念：永远拉均值最高的那台。困难在于它未知——智能体手里只有估计值 $Q_t(a)$，以及「拉一次、看一个样本、改一次估计」的学习回路。本阶段的每个装置都被这同一个缺口逼出。

2. 增量估计：一行公式的前世

最朴素的 $Q_t(a)$ 是样本均值：把动作 $a$ 上收到过的奖励全部存下、求平均。它正确，但每来一个新奖励都要重算整个和，而且「记住全部历史」在无限长的奖励流上不可行。均值其实可以只用两个数维护——当前估计与新样本。设动作 $a$ 上前 $n-1$ 次奖励的平均为 $Q_n$，第 $n$ 次拉杆得 $R_n$，新的平均是

$$Q_{n+1}=\frac{R_1+\cdots +R_n}{n}=\frac{(n-1)Q_n+R_n}{n}=Q_n+\frac{1}{n}(R_n-Q_n).$$

第二步「乘除 $n-1$、把前 $n-1$ 项之和认成旧估计 $(n-1)Q_n$」是唯一的技巧——ML 论文常跳过这步推导，值得亲手走一遍。走完之后，均值从「存全部历史再求和」变成「只存当前估计，朝新证据挪一小步」。

最后一行的形状值得盯住，它有一般形式：

$$\text{NewEstimate}\leftarrow \text{OldEstimate}+\text{StepSize}[\text{Target}-\text{OldEstimate}].$$

估计永远朝「目标与旧估计之差」修正一小步。把 Target 取为即时奖励、StepSize 取 $1/n$，就是上面的样本均值；把 Target 换成「即时奖励加对下一状态的折扣估值」、StepSize 换成常量，就得到阶段三的 TD 更新——那行更新不是新发明，是这里的一行公式换了目标。

3. 探索与利用：ε-greedy

估计有噪声，每个时刻于是都站在岔路口。只拉当前 $Q_t$ 最高的那台（利用 (exploitation)），可能永远锁死在「看起来最好、实际次优」的机器上；转去试其他机器（探索 (exploration)），又把筹码撒进当前估计偏弱的选项。这个两难没有根治、只有定价，而最便宜的定价方式可以先把动机想成一段独白：「要是永远只拉估计最高的那台，我可能一直错把第二好当最好；可每次都乱试，又在给差机器送钱——那这样：绝大多数时候贪心，偶尔（比如十次里一次）随机换一台？」这就是 ε-greedy：以概率 $1-\epsilon$ 贪心选 $\arg \underset{a}{max}{Q}_t(a)$（贪心 = 只认当前估计；若首次见 $\arg \underset{a}{max}f(a)$：返回让 $f$ 最大的那个输入 $a$，并列时任取其一——注意它交还的是「选项」而非最大值本身），以概率 $\epsilon$ 在全部 $k$ 台里等概率随机选。$\epsilon$ 是探索量的旋钮：调小，平均回报趋稳但可能困在次优；调大，找到好机器更快、但持续为差机器付学费。样本均值配上 ε-greedy 还有一个温和的保证：只要 $\epsilon >0$，每台机器终将被无限次拉到，$Q_t(a)$ 随之收敛到 $q_{\ast }(a)$——探索不只为了碰运气，它在把估计本身修对；估计修对之后，剩下那 $1-\epsilon$ 的利用自然落在真正最好的机器上。

4. optimistic initial values：用初值垫出探索

样本均值需要一个初值 $Q_1$。把它设成显著高于一切真实均值的数（比如一切 $q_{\ast }(a)\le 1$ 时设 $Q_1=+5$），贪心规则会自动变成一台探索机器：任何被试过的机器，第一次真实奖励几乎必然低于初值，估计随之下跌；而未试过的机器还挂在高位——贪心规则总会先去「还没让我失望过」的那台。于是开局若干步自然铺满全探索，不需要任何显式的探索机制。它的局限同样清楚：这只解决「开头」。探索量由初值一次性预付、不随反馈调节；在会漂移的世界里（第 6 小节），这份乐观很快耗尽。

5. UCB：按不确定性下注

ε-greedy 的探索是盲目的——随机等概率，不看哪台「还欠了解」。另一条思路同样可以先想再命名：「与其随机试，不如给『被试得少、还没把握』的机器发一点加成——估计分加加成分，谁高拉谁；被试多了，加成自然衰减。」形式化为置信上界 (upper confidence bound, UCB)：

$$A_t=\arg \underset{a}{max}[Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}],$$

逐项读：$Q_t(a)$ 是利用项；$c>0$ 是探索强度旋钮；$N_t(a)$ 是到时刻 $t$ 为止动作 $a$ 已被选的次数，它待在分母上——被选得越少加成越大，从未被选过（$N_t(a)=0$）的机器视为最优候选；$\ln t$ 随总时长增长，若首次见 $\sqrt{\ln t}$：先取自然对数再开方，$t=100$ 时约 $2.1$、$t=\mathrm{10,000}$ 时也才约 $3.0$——自变量涨一百倍，它只涨四成。这个慢增长是设计的一部分：即便某台机器被反复选中，其加成仍随 $t$ 缓慢爬升，长期看每台机器终将被无限次尝试——乐观面对不确定性；而确定性积累起来之后，探索自然让位于利用。

6. 非平稳：常量步长 α

样本均值的 $1/n$ 隐含一个假设：$q_{\ast }(a)$ 从不改变。若机器被人调过——均值在漂移——$1/n$ 让每个新奖励的权重越来越小，估计对新世界的反应越来越迟钝，最终停在旧平均上不肯更新。修法是把步长从 $1/n$ 换成常数 $\alpha \in (0,1]$：

$$Q_{n+1}=Q_n+\alpha (R_n-Q_n),$$

展开后是指数加权的滑动平均：越近的奖励权重越大，按 $(1-\alpha )$ 几何衰减——「最近的样本最重要」。代价是估计不再收敛到定值、永远带一点抖动；$\alpha$ 越大跟得越紧、也抖得越狠。它与阶段三 TD 更新的亲缘关系在第 2 小节已经点过：TD 继承的正是常量 $\alpha$ 这一支。

7. 从一台到一组：通往 MDP

收拢本阶段的四个装置：

装置	一句话机制	代价
ε-greedy	以小概率 $\epsilon$ 随机探索	探索盲目，与「欠了解」程度无关
optimistic initial values	高初值垫出开局全探索	只管开头，非平稳世界后劲不足
UCB	按不确定性发探索加成	要额外记每台的拉杆次数，最优性论证依赖奖励分布条件
常量 $\alpha$	指数加权跟踪漂移	估计不收敛到定值，永远轻微抖动

现在给每个状态配上它自己的一组老虎机，就得到了 MDP——这正是下一阶段要做的事。新增的只有两块拼图：拉哪个动作会决定下一步站在哪组机器前（转移），以及奖励跨步累积成回报（折扣 $\gamma$ 登场）。第11章的 contextual bandit 设定与此直接对号入座：prompt 是状态、回答是一个动作、奖励只在序列结束时给一次——没有跨状态转移要规划的单步决策，正是本阶段知识的直系后代。

---

阶段一：一般 MDP——状态、动作、轨迹与吸收态

1. 五元组与轨迹

马尔可夫决策过程 (Markov Decision Process, MDP) 由五个对象构成：

成分	记号	含义
状态空间	$\mathcal{S}$（另设 ${\mathcal{S}}^{+}=\mathcal{S}\cup \{⟨\text{term}⟩\}$）	环境可能处的全部情形，$⟨\text{term}⟩$ 是终止状态
动作空间	$\mathcal{A}$	智能体每步可选项
初始分布	$s_0\sim p_0$	回合起点的随机性
转移核	$(r_t,s_{t+1})\sim p(\cdot ,\cdot \mid s_t,a_t)$	给定状态与动作，奖励和下一状态的联合分布
时间指标	$t=0,1,\dots ,T$	$T$ 由 $s_T=⟨\text{term}⟩$ 定义

马尔可夫性的含义就写在转移核里：下一步的分布只依赖 $(s_t,a_t)$，不依赖更早的历史。策略 (policy) $\pi (a\mid s)$ 是状态到动作分布的映射；平稳策略不显式依赖 $t$。轨迹 (trajectory) 是

$$\tau =(s_0,a_0,r_0,s_1,a_1,r_1,\dots ,s_T),$$

其概率按链式法则分解为「初始分布 × 每步策略 × 每步转移」的连乘。回报 (return) 从时刻 $t$ 起算：

$$G_t=\sum _{k=0}^{T-t}{\gamma }^k{r}_{t+k},\gamma \in [0,1].$$

$T<\mathrm{\infty }$ 的回合叫 episodic task；$T=\mathrm{\infty }$ 叫 continual task。$\gamma <1$ 在无限时长下保证几何级数收敛。

2. 终态吸收化：先于一切推导的记号工程

一个容易被略过、但每份严谨推导都会撞上的记号坑：$T$ 是随机变量（由首次到达终态定义的停时），因此

$$\mathbb{E}[\sum _{t=0}^T(\cdot )]\ne \sum _{t=0}^T\mathbb{E}[(\cdot )].$$

左边是一个「求和项数本身随机」的对象，右边假装 $T$ 是固定的——两者根本不是同一个量。处理随机终止时刻的每次交换、求导、取期望，都得重新论证一遍。

工程上一次性解决这个麻烦的办法是吸收态 (absorbing state) 化：约定一旦 $s_t=⟨\text{term}⟩$，则 $r_t=0$、且 $s_{t+1}=⟨\text{term}⟩$ 以概率 1 成立。此后名义上 $T=\mathrm{\infty }$，但终态之后贡献恒为零，所有「有限求和」都可以改写成「无限求和 + 尾项为零」，期望号的搬运回到常规轨道。同时硬性约定 $V^{\pi }(⟨\text{term}⟩)=0$。

这个技巧在第11章的生成 MDP 上直接兑现：生成过程在采样出 <EOS> 时终止，终止时刻是随机的——「把终止时刻的随机性吸收进状态」正是那里的记账方式（讲法源自 Ernest Ryu, RL of LLMs (Spring 2025) Chapter 1）。

3. 状态与观测：LLM 为什么没有这个问题

一般 MDP 假设全观测：智能体精确知道 $s_t$。当智能体只能看到观测 $o_t$ 而非真实状态时（经典的例子：老虎暂时躲到树后，「当前看不见」不等于「当前安全」），问题升级为部分可观测 MDP (POMDP)，难度显著上升。这里的预埋桥是：LLM 的生成 MDP 不受此困扰——模型能看到全部对话历史，「历史即状态」，因此是全观测的。这条性质在第11章把「整个前缀」定义为状态时已经用上了。

4. 模仿学习与分布偏移：为什么 SFT 之后还需要 RL

模仿学习 (imitation learning) 的最简形式是行为克隆 (behavior cloning)：收集专家的状态-动作对 $D_{\text{expert}}=\{(s^i,a^i)\}$，做监督学习

$$\underset{\theta }{min}\sum _i{\ell }_{\text{CE}}({\pi }_{\theta }(\cdot \mid s^i),a^i).$$

下一 token 预测本质上就是行为克隆：专家数据是语料，动作是下一个 token。SFT 也是行为克隆——对指令-回答对做条件化的下一 token 预测。

行为克隆的软肋是分布偏移 (distribution shift)：训练数据来自专家（或旧策略）到访的状态分布，而部署时智能体用自己的策略行动，一旦走进专家没到过的状态，模型在该状态下没有任何监督信号，误差逐步累积。驾驶是这个机制的具象版：专家司机偶然轻微偏航时，一次熟练的方向盘修正就回到车道；行为克隆策略从未在「偏航状态」上见过示范，一旦漂出专家轨迹，没有任何信号告诉它如何恢复，误差像滚雪球一样放大。理论入口是：RL 中训练数据本身依赖策略——在别的策略（或旧的自己）产生的数据上训练叫 off-policy，在当前策略产生的数据上训练叫 on-policy；行为克隆是前者。DAgger 一类的算法试图用「让专家在 learner 的状态分布上补标注」来修复偏移，但让标注者覆盖模型实际会走到的所有状态，在 LLM 场景里基本不可行。更深一层的别扭在标注端：问人类「此刻你会把方向盘打几度」不是自然的示范方式；LLM 版同理——接续别人写了一半的段落也不是人类自然的写作方式。但「让模仿学习尽量 on-policy」的思想没有就此消失：RLHF 在当前策略的采样上训练、expert iteration（阶段五）让网络模仿被搜索增强后的自己，都是这一思想在后续范式里的回归。

为什么「观察会了」不等于「做会了」？Ernest Ryu 在该课程 Prologue 里给过一个体育类比（此处为转述）：看会一个过人动作与亲自练出这个动作之间，隔着一个反馈回路——示范数据只记录了可见的动作序列，让动作成功的隐含前置步骤不会出现在数据里；只有带着环境反馈去试错，才能发现并修正这类被示范掩盖的缺失环节。具体版本：模仿球星「快速运球过人上篮」的整套动作，防守者却总跟得上；反复上场试错才发现，起手处的眼神假动作才是让过人成立的关键组件——仅靠观察示范，这一步不会自己显形。这是「SFT 记忆、RL 泛化」的直觉版：模仿复制可见行为，试错发现被掩盖的因果结构，也是从 SFT 走向 RL 的动机起点。

---

阶段二：Bellman 方程、压缩映射与两种迭代

1. 值函数：$V^{\pi }$ 与 $Q^{\pi }$

给定策略 $\pi$，状态价值函数与动作价值函数定义为

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_0\mid s_0=s],Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_0\mid s_0=s,a_0=a],$$

约定 $V^{\pi }(⟨\text{term}⟩)=0$。平稳策略给出时间平移不变性：从 $t$ 时刻的状态 $s$ 出发的期望剩余回报等于 $V^{\pi }(s)$。最优值函数 $V^{\star }(s)=\underset{\pi }{max}{V}^{\pi }(s)$；最优策略不必唯一，但所有最优策略产生同一个值函数。

2. Bellman 期望方程：压缩映射与不动点

对固定 $\pi$，定义 Bellman 算子

$$({\mathcal{B}}^{\pi }V)(s)={\mathbb{E}}_{a\sim \pi (\cdot \mid s),(r,s^{\prime })\sim p(\cdot ,\cdot \mid s,a)}[r+\gamma V(s^{\prime })].$$

在 $\gamma \in (0,1)$、状态空间有限、奖励有界的条件下，${\mathcal{B}}^{\pi }$ 在上确界范数下是 $\gamma$-压缩映射 (contraction mapping)：对任意 $U,V$ 有 $\parallel {\mathcal{B}}^{\pi }U-{\mathcal{B}}^{\pi }V{\parallel }_{\mathrm{\infty }}\le \gamma \parallel U-V{\parallel }_{\mathrm{\infty }}$（逐状态做差、放缩、公共因子 $\gamma$ 提出）。Banach 不动点定理说：完备度量空间上的压缩映射有唯一不动点，且从任意初值起迭代收敛。于是 Bellman 期望方程

$$V^{\pi }(s)=\mathbb{E}[r+\gamma V^{\pi }(s^{\prime })\mid s]$$

的解存在、唯一、且恰为 $V^{\pi }$——先按定义展开 $V^{\pi }$ 再用时间平移性收缩一步，就得到它。

把压缩性那一拍的放缩链拆成四步看全（对任意 $U,V$ 与任意状态 $s$）：

$$\begin{array}{rlrl}|({\mathcal{B}}^{\pi }U)(s)-({\mathcal{B}}^{\pi }V)(s)|& =|\mathbb{E}[\gamma (U(s^{\prime })-V(s^{\prime }))\mid s]|& & \text{① 两式取差，奖励项相消}\\ & =\gamma |\mathbb{E}[U(s^{\prime })-V(s^{\prime })\mid s]|& & \text{② }\gamma \text{ 是常数，提到期望外}\\ & \le \gamma \mathbb{E}[|U(s^{\prime })-V(s^{\prime })|\mid s]& & \text{③ }|\mathbb{E}[\cdot ]|\le \mathbb{E}|\cdot |\\ & \le \gamma \parallel U-V{\parallel }_{\mathrm{\infty }}& & \text{④ 逐点差放大到上确界}\end{array}$$

①靠的是同一 $(s,a)$ 下奖励分布相同（平稳环境）；②是线性；③是绝对值与期望的次序交换；④把「对 $s^{\prime }$ 的逐点差」统一抬到最坏情况——走完四步后仍留在系数上的那个 $\gamma$，就是折扣买来的全部收敛性。

3. Bellman 最优性方程：两段式诚实

把算子里的「对 $\pi$ 取期望」换成「对动作取 max」，得到最优 Bellman 算子 ${\mathcal{B}}^{\star }$ 与最优性方程

$$V^{\star }(s)=\underset{a\in \mathcal{A}}{max}\mathbb{E}[r+\gamma V^{\star }(s^{\prime })\mid s,a].$$

这一步的证明顺序值得原样学走（讲法源自 Ernest Ryu, RL of LLMs (Spring 2025) Chapter 1）：先用辅助引理 $|\underset{a}{max}u(a)-\underset{a}{max}v(a)|\le \underset{a}{max}|u(a)-v(a)|$ 证明 ${\mathcal{B}}^{\star }$ 同样是 $\gamma$-压缩，于是有唯一不动点——但此刻还不知道这个不动点是不是「最优值函数」，讲义在此处特意标注了这个悬念。补上第二段的是单调性：${\mathcal{B}}^{\pi }\le {\mathcal{B}}^{\star }$（逐状态），且 ${\mathcal{B}}^{\star }$ 保序，于是任意策略满足夹逼链

$$V^{\pi }={\mathcal{B}}^{\pi }{V}^{\pi }\le {\mathcal{B}}^{\star }{V}^{\pi }\le {\mathcal{B}}^{\star 2}{V}^{\pi }\le \cdots \to V^{\star },$$

所以 $V^{\pi }\le V^{\star }$ 对一切 $\pi$ 成立——不动点确实是最优。「不动点存在唯一」与「不动点恰为最优」是两件事，分开证明、不倒果为因；$Q$ 版本 $Q^{\star }(s,a)=\mathbb{E}[r+\gamma \underset{a^{\prime }}{max}{Q}^{\star }(s^{\prime },a^{\prime })\mid s,a]$ 与 $\underset{a}{max}{Q}^{\star }(s,\cdot )=V^{\star }$ 同理。最优策略从值函数免费提取：${\pi }^{\star }(s)\in \arg \underset{a}{max}{Q}^{\star }(s,a)$。

4. 价值迭代与策略迭代：两个「概念框架」

价值迭代 (value iteration, VI) 就是不动点迭代 $V^{k+1}={\mathcal{B}}^{\star }{V}^k$。压缩性直接给出几何收敛速率 $\parallel V^k-V^{\star }{\parallel }_{\mathrm{\infty }}\le {\gamma }^k\parallel V^0-V^{\star }{\parallel }_{\mathrm{\infty }}$；$\gamma =1$ 时压缩性消失，不保证收敛。换个视角看这场收敛（涟漪比喻化用自 Pramod Goyal 的 RL 教程）：每个好状态的好消息每轮向外多传播一格，像水面涟漪，直到每个格子都知道自己离出口多远。

策略迭代 (policy iteration, PI) 交替两步：策略评估（精确解出 $V^{{\pi }_k}$ 或 $Q^{{\pi }_k}$）与策略改进（贪心 ${\pi }_{k+1}(s)=\arg \underset{a}{max}{Q}^{{\pi }_k}(s,a)$）。Policy improvement 定理保证 $V^{{\pi }_{k+1}}\ge V^{{\pi }_k}$，且有限 MDP 上有限步后到达 $V^{\star }$。

这两种迭代在深度 RL 里通常不以精确形式实现，但它们是两族实用算法的概念框架：VI 的「逐步对最优 Bellman 算子做一步展开」孕育了 Q-learning/DQN 一系；PI 的「评估-改进交替」孕育了 TRPO/PPO 一系（第11章的 PPO 目标是它的近似后裔）。本页阶段四会从 PI 这条线走到 PPO 的门口。

5. $\gamma =1$ 的三种病态，与 terminal-only 的合法性

折扣不是数学装饰。$\gamma =1$（无折扣）时分三种情形：

情形	设定	结果
1	有限 MDP，且每个策略的 $V^{\pi }$ 有限良定——例如奖励只在回合结束时给一次	没有病态，$\gamma =1$ 合法
2	存在正奖励环：某状态自环且 $r>0$	$V^{\pi }=+\mathrm{\infty }$，一切比较失去意义
3	回报序列不可和（如 $+1,-1,+1,-1,\dots$）	总回报没有定义

情形 2 有一个经典的游戏化样例：平台游戏里反复踩同一只龟壳即可无限得分、无限加命——只要存在一条能无限重复收割正奖励的回路，无折扣回报就是 $+\mathrm{\infty }$，「刷分」与「通关」在同一把尺子上失去比较意义。

情形 1 正是第11章生成 MDP 的位置：无 KL 惩罚的 RL-LLM 设定（terminal-only 奖励的 episodic MDP）在 $\gamma =1$ 下良定。带 KL 惩罚的变体把 $\beta D_{\text{KL}}$ 项吸收进逐 token 的中间奖励后，出现了每步非零的奖励项——合法性论证要在改写后的奖励上重做，而 KL 项本身把策略拴在参考分布附近，恰好压制了「靠无限长回答刷奖励」这类情形 2 式的病态（古德哈特定律与 KL 安全绳在第11章有完整讨论）。

三种情形之外，工程实践的通行次序是：先在 $\gamma <1$ 下完成严格分析——压缩性、存在唯一性、收敛速率全部有定理可用；分析闭合后，再把结论外推到 $\gamma =1$ 的良定情形。外推这一步本身不是证明，情形 2、3 的边界条件必须逐一核对；但在情形 1 的保证之内，这是通行的工程折中（课程将其作为实践建议给出，此处为中性转述）。

本页到此的地图如下——精确算法、采样估计与概念框架的关系：

---

阶段三：从蒙特卡洛到时序差分——估计的谱系

第11章只需要一步 TD 残差（为 GAE 服务）；本节把整条谱系铺开。

读谱系之前先装一个评审镜头（课程反复使用、此处显式提炼）：本节每个估计器都会推两遍——第一遍是理想化版本，数学性质干净（无偏、与 Bellman 方程精确一致），但依赖未知的 $V^{\pi }$，不可执行 (not actionable)；第二遍把 $V^{\pi }$ 换成当前近似 $V_{\varphi }$，得到可执行但有偏的版本。谱系上的每个成员都能按「理想化形式是什么 / 可执行形式是什么 / 偏差从哪一步进入」三问归档；下文读到「拿它做估计，等于用被估计量自己估计自己」时，那里正标注着一次从第一遍到第二遍的换轨。

1. 蒙特卡洛评估

最直接的估计：对每个状态采 $N$ 条完整回合，用经验回报均值逼近期望回报，

$$V^{\pi }(s)\approx \frac{1}{N}\sum _{i=1}^N{G}_0^{(i)}.$$

无模型 (model-free)、无偏，但每条样本要等回合跑完，且方差随回合长度增长。神经网络版把 $V_{\varphi }:\mathcal{S}\to \mathbb{R}$ 拟合到这些目标上（MSE 损失 + SGD），终态价值硬编码为 0、不进网络。

2. TD 与自举

Bellman 期望方程给出另一个估计途径：$V^{\pi }(s)=\mathbb{E}[r+\gamma V^{\pi }(s^{\prime })\mid s]$。它只有在 $V^{\pi }$ 已知时才可计算——拿它做估计，等于用被估计量自己估计自己。出路是用当前近似 $V_{\varphi }$ 顶替 $V^{\pi }$，只展开一步就回收：

$$\hat{V}(s_t)=r_t+\gamma V_{\varphi }(s_{t+1}).$$

这个「用自身近似回填尾部」的动作叫自举 (bootstrapping)。它不必等回合结束、方差低，代价是目标里带上了 $V_{\varphi }$ 的误差。

3. stop-gradient：半梯度的实现级含义

用 SGD 拟合 TD 目标时，想要的梯度是两个标量的乘积：

$$g=(r+\gamma V_{\varphi }(s^{\prime })-V_{\varphi }(s)){\mathrm{\nabla }}_{\varphi }{V}_{\varphi }(s),$$

即只对被评估的 $V_{\varphi }(s)$ 求导，TD 目标里的 $V_{\varphi }(s^{\prime })$ 当常数。若让链式法则扫过目标里的 $V_{\varphi }(s^{\prime })$，得到的是另一个（错误的）梯度方向。数学上引入 stop-gradient 算子 $\mathrm{sg}[\cdot ]$，把损失写成

$$\ell (\varphi )=\frac{1}{2}(r+\gamma \mathrm{sg}[V_{\varphi }(s^{\prime })]-V_{\varphi }(s){)}^2,$$

PyTorch 里就是 target.detach()——前向数值照常参与，反向图在此剪断。第12章 GRPO toy 里冻结参考策略的做法、第11章 PPO 的旧策略概率比，都是同一个算子的不同宿主。

这一行真写进 PyTorch 时有三种候选写法，课程对三者逐一给过判定（此处转述）：

写法	判定	依据
Option 1：把 TD 误差当标量系数，手动实现 $g=(\cdot ){\mathrm{\nabla }}_{\varphi }{V}_{\varphi }(s)$（系数与梯度分开算再相乘）	正确但繁琐	数值上就是想要的更新，但要手工拆排计算图，代码与内存都不省
Option 2：对 $(r+\gamma V_{\varphi }(s^{\prime })-V_{\varphi }(s){)}^2$ 整体反向传播	错误	链式法则同时扫过两处 $V_{\varphi }$，比 $g$ 多出一项含 $\gamma {\mathrm{\nabla }}_{\varphi }{V}_{\varphi }(s^{\prime })$ 的方向，回不到想要的更新
Option 3：对目标里的 $V_{\varphi }(s^{\prime })$ 套 $\mathrm{sg}[\cdot ]$（即 .detach()）	社区标准	前向数值照常参与，反向图在目标处剪断，恰好实现 $g$

stop-gradient 在策略梯度侧同样在场（实现级细节，课程口述，此处转述）：actor 的更新方向里，${\hat{Q}}_t$ 与 baseline $b(s_t)$ 都以常数身份出现——对它们套 $\mathrm{sg}[\cdot ]$ 后，梯度只从 $\log {\pi }_{\theta }(a_t\mid s_t)$ 一路反传，一次 backward 调用完成。还有一个符号细节：PyTorch 的优化器默认做最小化，而策略梯度是上升方向，实现上把目标取负再交给 optimizer。读第11/12章的 PPO 与 GRPO 实现时，可以带着这两个约定去对照。

4. k-step 谱系与 $k=5$ 经验法则

MC 与一步 TD 之间是一条回望窗口的插值轴。k-step TD 目标取 $k$ 步真实奖励加自举尾项：

$${\hat{V}}^{\text{TD}(k)}(s_t)=\sum _{i=0}^{k-1}{\gamma }^i{r}_{t+i}+{\gamma }^k{V}_{\varphi }(s_{t+k}).$$

$k=1$ 是一步 TD，$k=\mathrm{\infty }$（尾项消失）是 MC。权衡是：训练早期 $V_{\varphi }$ 不准，自举把错误当目标，偏稳态但偏差大；训练后期 $V_{\varphi }$ 已准，等整段回合结束才更新则浪费，纯 MC 方差又大。实践的经验缺省值是 $k=5$（讲法源自 Ernest Ryu, RL of LLMs (Spring 2025) Chapter 1）——一个少见的敢给默认数的讲法，本页沿用这个缺省值并保留它的出处。

5. 诚实注脚：半梯度可证明不是梯度下降

TD + 近似 SGD 的组合叫半梯度 (semi-gradient) 方法。「半」不是修辞：可以证明它不是任何目标函数的梯度下降（Barnard, 1993）——存在它时，你找不到一个 $\ell (\varphi )$ 使 ${\mathrm{\nabla }}_{\varphi }\ell$ 恰好等于那个更新方向。直接最小化 Bellman 误差的「全梯度」方法 (gradient TD, Sutton 等 2008/2009) 理论上更纯洁，实证上反而表现更差。理论性质与工程效果在这里正面冲突，诚实的处理是把冲突摆上台面、按工程效果选边，同时保留理论标签——本课对 GRPO 偏置（第12章）的讨论沿用同样的纪律。

6. 为什么 DQN 不在本课主线里

Q-learning / DQN 学 $Q_{\varphi }\approx Q^{\star }$，策略隐式藏在 $\arg \underset{a}{max}{Q}_{\varphi }$ 里。它被本课与 RL-LLM 主线共同排除，理由是结构性的（讲义在此给出三条事实推出的完整选型逻辑）：其一，LLM 的动作空间是有限词表，不是连续控制，DDPG/TD3/SAC 那一系没有用武之地；其二，强预训练初始策略至关重要，从零开始的 tabula rasa 训练不工作——方法必须能有效利用预训练好的 ${\pi }_{\theta }$，而 DQN 的「先学好 $Q_{\varphi }$ 再贪心」没有好办法把一个现成策略作为起点；其三，在 DQN/SAC 系里奖励只通过 $Q_{\varphi }$ 间接影响 ${\pi }_{\theta }$，PPO 系里奖励直接进入策略梯度的更新方向。这条选型逻辑在第11章的 PPO 目标处回收。

---

阶段四：策略梯度定理与四步方差缩减

第11章推导的是序列级 REINFORCE 特例；本节给一般形式，并按每一步先证无偏、再谈方差的顺序走完四个增强（讲法顺序源自 Ernest Ryu, RL of LLMs (Spring 2025) Chapter 1）。

1. 一般形式

目标 $J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[G_0]$。对轨迹概率的连乘分解取对数再求导，环境项（$p_0$ 与转移核）不含 $\theta$ 而消失，只剩策略项，得到策略梯度定理：

$${\mathrm{\nabla }}_{\theta }J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[\sum _t{\gamma }^t{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)Q^{{\pi }_{\theta }}(s_t,a_t)].$$

最粗的蒙特卡洛估计拿整段回报 $G_0$ 顶替 $Q^{{\pi }_{\theta }}(s_t,a_t)$——无偏，但一条样本同时乘到所有时刻上，方差大到几乎不可用。四个增强都是在不动无偏性的前提下削方差。

2. 增强 #1：去掉过去奖励

时刻 $t$ 之前发生的奖励 $r_0,\dots ,r_{t-1}$ 不受动作 $a_t$ 影响（因果），而 ${\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$ 只关乎「$a_t$ 的采样概率怎么变」。把 $G_0$ 换成未来奖励 $\sum _{t^{\prime }\ge t}{\gamma }^{t^{\prime }-t}{r}_{t^{\prime }}$：

$${\mathrm{\nabla }}_{\theta }J(\theta )=\mathbb{E}[\sum _t{\gamma }^t{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)\sum _{t^{\prime }\ge t}{\gamma }^{t^{\prime }-t}{r}_{t^{\prime }}].$$

过去奖励在这一项里的条件期望为零，只贡献多余方差；严格化用全期望公式（tower property）逐项验证。这正是第11章「REINFORCE 的 $R(y)$ 可以逐步拆开乘」的一般形式。

3. 增强 #2：baseline

减去一个只依赖状态的基线 (baseline) $b(s_t)$：

$$\mathbb{E}[\sum _t{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)b(s_t)]=0.$$

每一项在给定 $s_t$ 时对动作取期望为零（$b$ 与动作无关，提出来乘上 ${\mathbb{E}}_{a\sim \pi }[{\mathrm{\nabla }}_{\theta }\log \pi ]=0$），期望保持无偏，方差下降。这就是第11章「advantage 记账」里 baseline 的一般定理。

4. 增强 #3：Q 估计统一定理与最优 baseline

两步增强可以合成一个定理：若 ${\hat{Q}}_t$ 满足条件期望齐性 $\mathbb{E}[{\hat{Q}}_t\mid {\tau }_t,a_t]=Q^{{\pi }_{\theta }}(s_t,a_t)$，则

$${\mathrm{\nabla }}_{\theta }J(\theta )=\mathbb{E}[\sum _t{\gamma }^t{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)({\hat{Q}}_t-b(s_t))].$$

增强 #1 的未来奖励、增强 #2 的 baseline 都是它的特例。Rao–Blackwell 定理（对更多变量取条件期望，无偏性不变、方差不增）说明 $Q^{{\pi }_{\theta }}(s_t,a_t)$ 本身——把 $a_t$ 之后的一切随机性都平均掉——正是「对的形状」的估计。理论上最优的 baseline 是逐状态的加权条件均值 $b^{\star }(s)$，但它在实践里不可用，于是用 $b=V_{\varphi }\approx V^{{\pi }_{\theta }}$ 做合理代理；注意无论 $V_{\varphi }$ 拟合得多差都不破坏无偏性——偏差只在把 ${\hat{Q}}_t$ 也换成近似时才进入。

「不可用」三个字值得展开看（讲法源自同一课程的口述，此处转述）：把 $b^{\star }(s)$ 的公式真正写出来，分子分母都会出现 $\mathbb{E}[({\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }{)}^2]$ 与 $\mathbb{E}[({\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }{)}^{2}Q]$ 这类量——策略梯度推导里从未出现过的新对象，每一个都需要新的学习机制与额外计算。讲义在此的处理是把公式里的这些权重显式划掉：划掉之后剩下的恰好是条件均值，也就是 $V$，于是 $b=V_{\varphi }$。讲者对这一步的自评是「这不是正确的计算，但作为一个启发式，道德上不算太冒犯」——理论最优不可得时，退到理论上次优、实证上被广泛检验的代理，并把这次妥协摆在明面上。这与阶段三「半梯度可证明不是梯度下降」的诚实注脚是同一种纪律：理论到工程的每一步显式让步都标注出处与代价，而不是假装没有让步。

5. 没有 baseline 时，softmax 在「硬推」什么

许多 MDP 只有非负奖励。没有 baseline 时，${\hat{Q}}_t\ge 0$ 意味着每个被采到的动作都在被推高——梯度的符号与「这个动作好不好」无关，唯一的相对信号来自 softmax 归一化：每个动作按自己的 $\mathrm{\nabla }\log \pi \cdot Q$ 被推，好动作被推得比坏动作狠，靠分母的重新归一化挤下别的动作。这是「没有 baseline 硬推」的机制。有 baseline 后才有干净的符号信号：优势函数 (advantage)

$$A^{\pi }(s,a)=Q^{\pi }(s,a)-V^{\pi }(s)$$

度量「该动作比该状态的平均水平好多少」：$A>0$ 提概率，$A<0$ 压概率，且 ${\mathbb{E}}_{a\sim \pi }[A^{\pi }(s,a)]=0$。本页动手实验的故障注入一节会让这个机制现出原形。

6. 增强 #4：k-step TD 与 actor-critic 谱系

统一定理要求精确 $Q^{{\pi }_{\theta }}$——不可行动。第四步拿阶段三的 k-step 目标顶替：

$${\hat{Q}}_t=\sum _{i<k}{\gamma }^i{r}_{t+i}+{\gamma }^k{V}_{\varphi }(s_{t+k}).$$

只需学一个 $V_{\varphi }$；即使 $V_{\varphi }$ 初始全错，前 $k$ 步真实奖励仍携带关于 $a_t$ 质量的信息。这笔冷启动账可以记细一点：随机初始化的 $V_{\varphi }(s_{t+k})$ 对「状态好坏」完全不含信息，但它的错误贡献在估计器里乘着 ${\gamma }^k$ 进入——前 $k$ 步真实奖励是无偏信号、全权重在场；自举尾项的错误不含信息、却以折扣价在场。「可以冷启动」说的就是这笔不对称的账。到这一步，偏差正式进入——四个增强里唯一牺牲无偏性的一步，换来的是可实现性；bias-variance 的让步在无偏性框架内被精确定价。当 MDP 本身是 $\gamma =1$ 的 terminal-only 设定（RL-LLM 正是），还可以人为在估计器内部引入 $\tilde{\gamma }<1$——「估计器折扣」引偏差降方差，多数深度 RL 实践运行在这个约定上。

从一条轨迹到 SGD 的更新序列，还有一个实现层的选样问题，课程在 A2C 出场前先做了这组三方对比：

方案	无偏性	代价
整条轨迹随机抽一个时刻的梯度项做一步更新	无偏（严格 SGD）	每步只消耗一个样本，其余梯度信息全部浪费
全轨迹梯度求和后一次更新	无偏	更新稀疏——类比 full-batch SGD，样本利用率低
沿轨迹的循环序（$t=0,1,\dots$）逐步更新	有偏（后段梯度在参数已被前段更新改变后计算）	更新频繁、样本高效

A2C 的更新结构取第三方案：用「有偏」换「频繁」，与上一步「偏差换可实现性」属于同一笔交易的两个条款。

于是得到演员-评论家 (actor-critic) 结构：策略 ${\pi }_{\theta }$ 是演员 (actor)，价值 $V_{\varphi }$ 是评论家 (critic)。A3C（异步优势演员-评论家，Mnih 等 2016）用多个并行 worker 异步推送梯度；A2C 是去掉异步的同步版。本页对 A2C/A3C 停在正文级——不实现深度版；动手实验里的「表格 baseline 版」保留它的思想骨架。

7. 通向 PPO 的桥：surrogate 与 clip 的悲观界读法

A2C 一条轨迹只够做一轮更新。想从同一批采样里学更多，把目标改写成重要性采样形式（对旧策略 ${\pi }_{{\theta }_0}$ 下的期望加概率比），得到代理目标 (surrogate objective)

$$\mathcal{K}(\theta ;{\theta }_0)={\mathbb{E}}_{\tau \sim {\pi }_{{\theta }_0}}\left[\sum _t\frac{{\pi }_{\theta }(a_t\mid s_t)}{{\pi }_{{\theta }_0}(a_t\mid s_t)}{\hat{A}}_t\right]\approx J(\theta )-J({\theta }_0)+C,$$

近似只在 $\theta \approx {\theta }_0$ 时成立，且概率比离 1 太远时重要性采样失准——两个独立理由都要求信任域 (trust region)。TRPO 用 KL 约束加二阶优化求解。PPO 的替代走法可以先把动机想成一段独白：「KL 约束的解太贵，而失控只发生在概率比被推得太远的时候——那把『继续推远的激励』本身拆掉：概率比一旦越出 $1\pm \epsilon$ 的带子，无论优势多大，再多推也不给一分好处，会怎样？」把这段直觉写成式子就是 clip——回到一阶 SGD，用截断隐式实现信任域：

$$L^{\text{clip}}(\theta )={\mathbb{E}}_t[min({\rho }_t{\hat{A}}_t,\mathrm{clip}({\rho }_t,1-\epsilon ,1+\epsilon ){\hat{A}}_t)],{\rho }_t=\frac{{\pi }_{\theta }(a_t\mid s_t)}{{\pi }_{{\theta }_k}(a_t\mid s_t)}.$$

读法是悲观下界：$min$ 在「未截断的代理项」与「截断后的最坏情况」之间取更保守者—— Advantage 为正时收益封顶在 $1+\epsilon$ 倍，为负时损失封底在 $1-\epsilon$ 倍；把概率比推得再远也没有额外激励，消除了把 $\theta$ 移离 ${\theta }_k$ 太远的动力。另一条独立的推导路径把 PPO 读作「近似策略迭代」：policy advantage 最小化 + 近似的贪心改进同样需要 proximal 机制兜底。完整的 PPO 目标（KL 惩罚、value head、entropy bonus）留在第11章；本页只修这座桥。

---

阶段五：AlphaGo、MCTS 与专家迭代

0. 自博弈的数学执照：minimax 优化的不稳定谱系

第 1 小节的第 2 步「自己和自己下」不是拿来即用的做法，它前面有两层论证：先说明朴素的双智能体训练为什么不稳，再证明单策略自博弈在什么条件下合法（讲法源自 Ernest Ryu, RL of LLMs (Spring 2025) Chapter 1）。

朴素方案为什么不稳。 双人零和博弈的目标是 $\underset{{\theta }_1}{max}\underset{{\theta }_2}{min}J({\theta }_1,{\theta }_2)$。最直接的并行实现是双方同时对各自参数走梯度（simultaneous gradient ascent-descent，下文简称 SimGAD）：player 1 沿上升方向、player 2 沿下降方向。石头剪刀布是这个动力学的最小反例——它变成一台「针对对方的针对」的机器：我针对你的布加强剪刀，你针对我的剪刀加强石头，我再针对你的石头加强布；每一轮反制都在放大上一轮的偏差，策略概率的振荡逐轮加剧直至发散，动力学里没有任何内建阻尼。GAN 训练的不稳定属于同一族现象，「多智能体 RL 比单智能体更难稳定」是这一支的普遍经验。修复谱系主要有两支：extragradient 先想象双方各走一步、在那个展望点取梯度、再回到当前参数提交更新；anchoring（常与 weight decay 配合）把参数持续向锚点拉回，为振荡添加阻尼。两支都能恢复收敛。这族经验沉淀出一条工程直觉：监督学习天然稳定，把 RL 的组件尽量改造成监督学习的形态，是稳定训练的通用处方——后训练管线普遍从 SFT 起步再进入 RL（第11章的顺序），可以视作这条处方的执行。

反对称支付：为什么一个策略就够。 零和博弈的支付结构是反对称 (antisymmetric) 的：交换视角后，同一局面-动作序列的支付变号——对我有利的局面必然对对手不利，轮到谁走就按谁的视角计值。在这个结构下，若对称点 $({\theta }^{\star },{\theta }^{\star })$ 是 Nash 均衡，则把 SimGAD 中 player 2 的参数固定为 ${\theta }_2={\theta }_1=\theta$ 后，双智能体更新坍缩为单智能体对 $J(\theta ,\theta )$ 的普通自梯度上升——player 2 就是 player 1 的一份拷贝，不需要第二个网络，也不需要第二套优化器。适用边界：围棋黑白双方的规则对称，一个网络打两边成立；规则本身高度不对称的游戏——例如双方的动作集都不同——才需要为每个玩家单独训练策略。

在这两条论证的光下，第 1 小节表格里第 2 步「与历史版本池对弈」是一个稳定化设计：对手取历史版本 ${\theta }^{-}$ 而非当前参数，构成一个延迟稳定机制——对手稍弱、更新滞后，恰好为「针对对方的针对」的振荡提供了阻尼，与 anchoring 属于同一类工程手段。

动手对照（纯 numpy 可写，写清思路即可，不必追求工程完整）：用 softmax 参数化石头剪刀布的双方策略（各三个 logits），按 SimGAD 更新——一方最大化、一方最小化各自的期望支付——记录三个动作概率随迭代的变化，预期看到振荡幅度逐轮放大；再实现一版带 anchoring 的更新（每步将 logits 向初始值拉回一个小系数），预期振荡被抑制、双方概率都收敛到 $(1/3,1/3,1/3)$——正是反对称支付下的 Nash 均衡。发散版与锚定版两条曲线并排，就是本小节全部抽象结论的最小可执行版本。

1. 四步训练，每一步都还不够

AlphaGo（Silver 等，2016）的训练是四步递进，每一步都解决了上一步的不足、又各自留下新的不足（叙事源自 Ernest Ryu, RL of LLMs (Spring 2025) Chapter 1）：

步骤	做什么	结果与不足
1. 监督策略网络 ${\pi }_{\theta }^{\text{IL}}$	人类棋谱上学预测下一手（交叉熵）	水平显著，尚不能击败人类专家——行为克隆的天花板
2. 自博弈策略网络 ${\pi }_{\theta }^{\text{RL}}$	与历史版本池对弈，胜负 $z=\pm 1$ 做无折扣、无 baseline 的策略梯度 $g=z\sum _t{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$	对 ${\pi }^{\text{IL}}$ 胜率约 80%，仍不敌人类顶尖。理论上算力足够时应收敛到完美，实际预算下不够
3. 价值网络 $V_{\varphi }$	对最强策略做 MC 策略评估，拟合局面胜率	只提供评估，不产生动作。围棋转移是确定的 $s^{\prime }=f(s,a)$，故 $Q^{\star }(s,a)=-V^{\star }(f(s,a))$（负号因为轮到对手）——学 $V$ 而不是 $Q$ 是这个结构的利用
4. 快速走子 ${\pi }_{\psi }^{\text{fast}}$	轻量策略网络，单步推理快约三个数量级	为搜索叶节点提供低成本的 rollout 评估

单靠任何一步都不行：裸网络原则上可用天价算力胜人类（换算经验律：棋力每 +120 ELO 约对应训练算力或测试时搜索算力翻倍；照此粗估，裸网络胜人类顶尖约需千倍训练算力，胜过含搜索的完整 Zero 级系统约需十万倍——经验律转述自课程引用的 Noam Brown 估计），纯 minimax 树搜索不需学习但随深度指数爆炸。人类棋手的参照恰好是两者相加：直觉给出候选与局面感（System 1，网络），审慎推演验证后果（System 2，搜索）——AlphaGo 用网络引导搜索聚焦相关区域，两个系统互为放大器。

2. MCTS 三原则

蒙特卡洛树搜索 (Monte Carlo Tree Search, MCTS) 在算力预算内组织这场协作，三条原则：

1. 逐步扩张：树随算力预算逐步加宽加深，每轮迭代选中一条路径改进它；
2. 控宽度：只深入「好」动作——先验概率高、评估价值高、或尚未深思过的；动作选择用 UCT 型规则，形如 $Q_{\varphi }(s,a)+\rho \pi (a\mid s)/\sqrt{N(s,a)}$（探索项随访问次数衰减）；
3. 控深度：前瞻有限步截断，叶节点价值由价值网络 $V_{\varphi }$ 与快速走子 rollout 各半加权估计。

这三条原则形式化的对象是人类棋手深思时的一份典型剧本，课程口述里带有具体数字（此处转述）：看到局面凭直觉列出约五个候选——控宽度的来源；对每个候选想象对手的几种可能回应，并清楚不可能穷举——逐步扩张时保留谁的选择压力；心中模拟 10–30 步而非推演到终局——控深度的来源；最后停在某个中间局面，凭局面感评估「走到这里是好是坏」——叶节点由 $V_{\varphi }$ 与 rollout 加权估值的对应。上一小节的 System 1 / System 2 映射在这份剧本里逐条落了地。

回溯给根节点各动作赋强度，提交最优的一步——考虑许多未来步，但只提交一步；到下一步重新规划。消融实验确认四个组件（IL 策略、RL 策略、价值网络、走子）全部必要：没有 ${\pi }^{\text{IL}}$ 的热启动，RL 阶段毫无进展。

3. AlphaGo Zero 与专家迭代

AlphaGo Zero（2017）去掉人类棋谱依赖：残差网络共享底座、双头输出 $f_{\theta }(s)=({\pi }_{\theta }(s),V_{\theta }(s))$；训练数据由带搜索的策略自己产生。核心循环叫专家迭代 (expert iteration)：

$$M_n\stackrel{\text{搜索增强}}{\to }{M}_n^{+}\stackrel{M_{n+1}\text{ 模仿 }{M}_n^{+}}{\to }{M}_{n+1}\cdots$$

给定网络，用「网络 + 搜索」增强它，再让下一代网络模仿增强后的策略。MCTS 的动作强于裸网络，所以每一次模仿都在向更强的教师学习；这个循环可视为模仿学习与策略迭代的双重推广，比纯策略梯度学得快得多（名称出自 Anthony 等 2017 的 "Thinking Fast and Slow with Deep Learning and Tree Search"）。第12章的 test-time compute 讨论是这个循环在推理任务上的回声。

4. test-time compute 的一句话数学辩护

为什么「推理时多花算力」能换来「训练时天文数字算力才买得到」的能力？因为两个问题的规模不同：预训练策略必须应对所有可能到达的局面——找到完美策略等于预先解完整盘棋；树搜索只处理从当前局面可达的局面子集——解一个严格更小的子问题。搜索在部署时把「全空间问题」折叠成「当前可达子空间问题」，这就是 test-time scaling 的性价比来源。

---

动手实验：Cliff Walk 五级阶梯

Cliff Walk 是经典 4×12 网格世界：起点在角上，终点在其同排另一端，两者之间沿边排布一段悬崖；每走一步奖励 $-1$，坠崖重罚并回到起点，到达终点结束（网格尺寸与奖励的具体数值以 CliffWalkEnv 的定义为准）。最短安全路径恰好贴着悬崖边缘走 13 步——所以起点的 $V^{\star }=-13$，这是 python/tests/test_rl_basics.py 的确定性断言。本节用 python/llm_core/rl_basics.py 的四个入口（CliffWalkEnv / value_iteration / policy_evaluation_exact / reinforce_train）走完五级：前三级是精确端，后两级是采样端。参数名与返回结构的权威定义以该模块的 docstring 与其测试为准；以下片段给出调用形状。

先跑通整条链的最小命令（Windows PowerShell 与 bash 通用写法）：

cd <仓库根目录>
PYTHONPATH=python python -m pytest python/tests/test_rl_basics.py -q

第 1 级：表格蒙特卡洛评估

目标：不动任何迭代理论，先用最朴素的方式估计「随机策略下每个状态值多少」。

# PYTHONPATH=python python -c "..."
from llm_core.rl_basics import CliffWalkEnv

env = CliffWalkEnv()
# 对每个起始状态采 N 条完整回合，用经验回报均值估计 V^pi(随机策略)。
# 预期信号：悬崖邻域状态价值明显更负（随机策略有概率坠崖）。

观察点：MC 估计无偏但抖——同一状态换 seed 重跑，估计值的波动直观展示「方差大」不是修辞。

第 2 级：价值迭代

# PYTHONPATH=python python -c "..."
from llm_core.rl_basics import CliffWalkEnv, value_iteration

env = CliffWalkEnv()
V_star = value_iteration(env, gamma=1.0)
# 预期信号：起点 V*(start) = -13；对 V* 逐状态贪心提取的策略
# 恰好沿悬崖边缘走最短安全路径。

terminal-only 奖励结构（每步 $-1$ 只在有限步内累积）让 $\gamma =1$ 落在阶段二情形 1——VI 收敛不需要折扣。换一个 $\gamma <1$ 重跑，收敛更快但最优路径可能变短视，这是折扣的偏置直观。

第 3 级：线性代数精确解对拍

固定（贪心）策略 $\pi$ 下，Bellman 期望方程是线性方程组 $V^{\pi }=r_{\pi }+\gamma P_{\pi }{V}^{\pi }$，精确解为

$$V^{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$

（对非终态子矩阵求解）。policy_evaluation_exact 给出这个解析值，用它对拍第 1 级的 MC 估计与第 2 级 VI 收敛值：MC 估计应在精确解附近抖动，VI 序列应单调逼近。迭代算法的正确性由一个不迭代的算法裁决——这是本课「对拍」纪律在 RL 上的用法。

第 4 级：表格策略梯度——baseline 的作用（A2C 思想骨架）

深度 A2C 用神经网络扮演 actor 与 critic；表格版把两者都退化为查表：策略是每状态的 softmax 概率行，critic 是每状态的价值标量。更新循环即阶段四的公式直译——沿回合逐步算未来奖励，减去 baseline $b(s_t)$，乘 ${\mathrm{\nabla }}_{\theta }\log \pi$ 推表格 logits。reinforce_train 的带 baseline 用法就是这一级（课程 notebook 在同位置留了一行注释掉的「去掉 baseline」损失，邀请学生亲手复现失败——下一节故障注入做同一件事）。

第 5 级：REINFORCE 完整训练循环

# PYTHONPATH=python python -c "..."
from llm_core.rl_basics import CliffWalkEnv, reinforce_train

env = CliffWalkEnv()
report = reinforce_train(env, episodes=3000, seed=42)
# 预期信号：固定 seed 下，训练后期望回报显著优于随机初始化策略，
# 学到的路径趋向悬崖边缘的最短安全路径（与 V* 对应的 -13 同方向）。

这是本课唯一一个「真的在跑的策略梯度训练循环」：采样、算回报、减 baseline、推 logits、重复。它与第12章的 grpo_policy_update 共享策略梯度定理的数学结构，但不共享优化景观——表格 Cliff Walk 的收敛数字不能外推到 LLM 规模的 PPO/GRPO 训练动态。

---

故障注入与预期信号

两处注入分别攻击阶段四与阶段二的两根支柱。

注入 1：关掉 baseline

把第 4/5 级更新里的 baseline 项去掉（reinforce_train 为此提供的无 baseline 用法，参数见模块 docstring），固定 seed 重跑同样轮数。

• 预期信号：期望回报相对带 baseline 版明显退化——曲线更抖、收敛更慢，甚至在低回报区长期徘徊。课程讲义对同一实验的标注是「没有 baseline，这训练不动——目标方差太大」（Ernest Ryu, RL of LLMs (Spring 2025) Chapter 1 对 Cliff Walk 设定的原话转述）。机制即阶段四第 5 小节：全负奖励下每个被采到的动作都被压概率，只剩 softmax 归一化的相对挤压在提供信号。
• 对照：同样的无 baseline 更新放到「奖励有正有负」的环境上，退化会减轻——符号信号部分回来了。

注入 2：正奖励环上的价值迭代

手搓一个两状态 MDP：状态 $s_0$ 上有动作保持自环且奖励 $+1$。对它跑价值迭代：

• $\gamma =1$：预期信号为 $V(s_0)$ 逐轮线性增长、不封顶，数值上以溢出或 inf 告终——压缩性消失，Banach 定理的前提整个不成立。这正是阶段二情形 2 的可执行版本。
• $\gamma =0.9$ 对照组：收敛到解析值 $1/(1-\gamma )=10$。折扣把无限累积折成有限几何级数，病态消失。

故障矩阵

注入场景	攻击的机制	预期失败信号	对应理论
关 baseline	方差缩减增强 #2 被移除	固定 seed 下回报退化、曲线抖动加剧	策略梯度定理 + softmax 归一化硬推
正奖励环 + $\gamma =1$ 的 VI	压缩映射前提被移除	$V$ 逐轮增长至 inf/溢出	Banach 不动点；阶段二情形 2
正奖励环 + $\gamma =0.9$（对照）	折扣恢复压缩	收敛到 $1/(1-\gamma )$	几何级数
MC 评估换 seed 重跑	高方差的无偏估计	同一状态的估计值显著波动	Rao–Blackwell 论证「平均掉更多随机性」的动机

---

追遗：跑得快的地方（Loose Ends）

（本节的补遗结构装置源自 Pramod Goyal 的 Reinforcement Learning from scratch #1（2026）；三笔补遗对应 Sutton & Barto 第 4 章。）

正文为了推进速度略过的严格性，集中补三笔欠账。

VI 为什么收敛。 一句话回指：${\mathcal{B}}^{\star }$ 是 $\gamma$-压缩映射，Banach 不动点定理保证从任意初值起的几何收敛——阶段二第 2、3 小节已完整证明。补一个几何注脚：每轮全状态扫掠让最优 Bellman 算子多展开一步动态。在 terminal-only 奖励、$\gamma =1$ 的网格设定里可以精确地说——离终态 $k$ 步以内的状态在第 $k$ 轮后已拿到精确值；一般情形则是「离得越近越先定型，误差按 ${\gamma }^k$ 收缩」。每轮扫掠把最优性向外传播一格，涟漪一圈一圈扩到每个格子（阶段二涟漪比喻的格数版）。

policy improvement 定理。 阶段二第 4 小节引用了它（「Policy improvement 定理保证 $V^{{\pi }_{k+1}}\ge V^{{\pi }_k}$」），这里补上论证。定理：若 ${\pi }^{\prime }$ 在每个状态都满足 $q_{\pi }(s,{\pi }^{\prime }(s))\ge v_{\pi }(s)$——「按 $\pi$ 的价值表看，${\pi }^{\prime }$ 选的动作不差」——则 $v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$ 处处成立。贪心改进自动满足前提，因为平均不超过最大：

$$v_{\pi }(s)=\sum _a\pi (a\mid s)q_{\pi }(s,a)\le \underset{a}{max}{q}_{\pi }(s,a)=q_{\pi }(s,{\pi }_{\text{greedy}}(s)).$$

紧凑三行论证收尾：其一，贪心动作的 $q$ 值是全部动作 $q$ 值的 $\pi$ 加权平均的上界（上式）；其二，从 $s$ 出发先走一步 ${\pi }^{\prime }(s)$、之后处处交回 $\pi$，这个混合回路的期望已不低于 $v_{\pi }(s)$，对后续状态逐个套用同一不等式即得 $v_{{\pi }^{\prime }}\ge v_{\pi }$；其三，有限 MDP 的确定性策略只有有限个，每次非最优的改进都严格抬升 $V$——严格抬升的链条有限步内必停，停点满足 Bellman 最优性方程 $v_{\pi }=\underset{a}{max}{q}_{\pi }(s,a)$，故 $v_{\pi }=V^{\star }$。

GPI（generalized policy iteration，广义策略迭代）。 把「评估」与「改进」看成两个同时在场的过程：改进改的是 $\pi$，评估赖以做加权平均的权重随之换底；评估改的是 $V$，改进赖以贪心的那张表也随之换底——两个过程互为对方改地面，唯一的共同稳定点是「一个对自己的值函数贪心的策略」，在那里两个过程同时静止。policy iteration 与 value iteration 是这个连续谱的两个端点：前者每轮把评估跑到底，后者每轮只让评估扫一遍；中间任何截断比例都合法，而实践形态几乎总在中间。这里补阶段二欠下的点睛句：策略评估与价值迭代只差一行——把 Bellman 期望方程里的「$\pi$ 加权平均」换成 $max$，评估循环就翻成最优性循环。此后几乎每个 RL 算法都是 GPI 的某个版本：actor-critic（阶段四）是两个过程的网络化并发，expert iteration（阶段五）是把「改进」这一半交给搜索的 GPI。

---

本页验收

能解释终态吸收化解决的期望号交换坑与它在生成 MDP 上的兑现

能复述 Bellman 最优性方程两段式证明各自证明什么

能说出 γ=1 三种病态与 terminal-only 奖励的合法性论证

能沿 MC→TD→k-step 谱系讲偏差-方差交换与 k=5 缺省值

能解释 stop-gradient 在 TD 目标上切断什么与 .detach() 的对应

能按无偏性逐级验证顺序复述四个方差缩减增强

能解释没有 baseline 时 softmax 归一化的硬推机制

能讲出 AlphaGo 四步每步为什么还不够与 test-time compute 的一句话辩护

能在 Cliff Walk 上跑通五级实验并复现两个故障注入的预期信号

闭卷口试题（每题 5–10 分钟自测）：

1. $T$ 是随机变量时 $\mathbb{E}\sum _{t=0}^T(\cdot )\ne \sum _{t=0}^T\mathbb{E}(\cdot )$ 错在哪一步？吸收态技巧如何让生成 MDP 的 <EOS> 终止复用同一套记账？
2. Bellman 最优性方程的证明为什么必须分两段？第一段结束时我们知道什么、还不知道什么？夹逼链 $V^{\pi }\le {\mathcal{B}}^{\star k}{V}^{\pi }\to V^{\star }$ 用了 ${\mathcal{B}}^{\star }$ 的哪两条性质？
3. 列举 $\gamma =1$ 的三种病态。为什么「奖励只在终止时给一次」让无 KL 惩罚的 RL-LLM 在 $\gamma =1$ 下合法？KL 惩罚吸收进逐 token 奖励后，这个论证要在哪个对象上重做？
4. 半梯度为什么「可证明不是梯度下降」？.detach() 在 TD 目标上切断的是前向计算还是反向图？切断错了会得到什么？
5. 四个方差缩减增强中，哪几步保持无偏、哪一步引入偏差？引入偏差的那一步换来了什么？$V_{\varphi }$ 拟合得差为什么不破坏统一定理的无偏性？
6. 全正奖励、无 baseline 的策略梯度更新里，「好动作被推高」的信号从哪来？构造一个直觉反例说明「全正 $C_a$ 却把最优动作概率推低」为何可能发生。
7. PPO 的 clip 目标按「悲观下界」怎么读？为什么说它「消除了把 $\theta$ 移得太远的激励」，这与信任域是什么关系？
8. AlphaGo 四步训练中，第 2 步的无 baseline 策略梯度为什么在围棋上能工作，而第 4/5 级 Cliff Walk 实验里去掉 baseline 会退化？（提示：$z=\pm 1$ 的对称奖励 vs 全负的步惩罚。）
9. 用「预先解整盘棋 vs 只解当前可达子集」解释 test-time compute 的性价比；这个论证对第12章的多数投票与更长 CoT 各对应哪一半？
10. 4×4 网格世界，出口在左上角与右下角，每步奖励 $-1$、$\gamma =1$、转移确定；随机游走策略（四方向等概率）下某格的 $v_{\pi }=-14$，其正下方一格 $v_{\pi }=-6$（下方更靠近出口）。站在该格，「先刻意向下走一步、之后一切交回随机游走」这条路的第一步值多少？它与全程随机游走的 $-14$ 相比说明什么？（答案：$q_{\pi }(s,\downarrow )=-1+1\times (-6)=-7$，一步前瞻法——即时奖励加 $\gamma$ 倍下一状态值；$-7$ 远高于 $-14$，对当前价值表贪心一步即可大幅优于策略平均水平，正是追遗节 policy improvement 的单步版本。）

---

论文与延伸

• 教科书：Sutton & Barto, Reinforcement Learning: An Introduction（第二版, 2018）——MC/TD/表格方法的百科全书，官方免费全文。Zhao, Mathematical Foundations of Reinforcement Learning（2025, Springer）——第11章值函数记号的来源，Bellman 与动态规划一章可作本页阶段二的对照读物。
• 课程：Ernest K. Ryu, RL of LLMs (Spring 2025)——本页一般理论与全部讲法顺序的来源；Chapter 1 讲义与 Cliff Walk notebook 的公开链接在课程页。
• 策略梯度与 actor-critic：A3C, Mnih 等, ICML 2016, arXiv:1602.01783。
• PPO 谱系：TRPO, Schulman 等, ICML 2015, arXiv:1502.05477；GAE, Schulman 等, ICLR 2016, arXiv:1506.02438；PPO, Schulman 等, 2017, arXiv:1707.06347。
• RL-LLM 侧的承接：GRPO/DeepSeekMath, Shao 等, 2024, arXiv:2402.03300；DPO, Rafailov 等, NeurIPS 2023, arXiv:2305.18290——两篇分别在第12章与第11章展开。
• 博弈与搜索：DQN, Mnih 等, Nature 2015, Human-level control through deep reinforcement learning（本页排除它的理由见阶段三）；AlphaGo, Silver 等, Nature 2016, Mastering the game of Go with deep neural networks and tree search；AlphaGo Zero, Silver 等, Nature 2017, Mastering the game of Go without human knowledge；expert iteration, Anthony 等, NeurIPS 2017, arXiv:1705.08439。

---

资源 / 成本 / 隐私

本页动手实验全部为 CPU 上的表格计算：五级实验与两个故障注入合计运行时间在秒级，网络带宽与费用为 0。python/llm_core/rl_basics.py 及其测试不依赖任何外部服务； Cliff Walk 环境参数（网格尺寸、奖励数值）以该模块定义为准。

---

Evidence

学习者提交模板（待填写，不是当前机器证据）

复制下面模板并填写自己的真实运行结果。所有 <...> 都是未填写状态；actual 必须替换为本次运行的真实记录。

schema: learn-llm.evidence.v1
module: rl-foundations
commit: <learner-commit-sha>
verified_at: <iso-date>
environment: <sanitized-python-device>
seed: 42
commands:
  - PYTHONPATH=python python -m pytest python/tests/test_rl_basics.py -q
metrics:
  - name: cliff_walk_v_star_start
    expected: -13
    actual: <recorded-value>
  - name: vi_matches_exact_solution
    expected: true
    actual: <recorded-value>
  - name: reinforce_beats_random_init
    expected: true
    actual: <recorded-value>
  - name: no_baseline_degrades_return
    expected: true
    actual: <recorded-value>
  - name: gamma_one_loop_diverges
    expected: inf-or-overflow
    actual: <recorded-value>
artifacts:
  - python/llm_core/rl_basics.py
cost:
  gross_usd: 0
  credit_usd: 0
licenses:
  - source: Ernest K. Ryu, RL of LLMs (Spring 2025), Chapter 1
    license: link-only-attribution
  - source: Pramod Goyal, Reinforcement Learning from scratch #1 (2026)
    license: link-only-attribution
known_failures:
  - none

表格 Cliff Walk 的收敛数字只描述固定 seed 下的本仓库 fixture，不外推到 token 级 PPO/GRPO 训练动态；两者共享数学结构（策略梯度定理、Bellman 算子），不共享优化景观。

---

下一步

一般理论就位后，两条路都已铺好：回到第11章，把 PPO 目标、GAE 与 KL 安全绳逐项挂到本页的定理编号上；或直接进第12章，在 grpo_policy_update 的 toy 循环里认出本页的策略梯度结构——再往后，第22章 Capstone 的验证式自提升正等着 expert iteration 的回声。