Reinforcement Learning for Large Language Models: An Overview

Introduction

本文围绕一个核心问题展开：

我们是如何使用强化学习来提高大语言模型的能力上限的？

为了解决这个问题，我们需要回答：

强化学习是如何建模的？
强化学习有哪些算法？哪些强化学习算法适用/不适用于大语言模型？这些算法背后的原理是什么？
现代大语言模型使用的强化学习算法是什么？

我们将按照下面的学习路径组织：

Foundations：我们将从基本的定义 (MDP, return) 出发，建立 LLM generation 与 RL 的对应关系，再用 Bellman Equation 将长期回报转化为递推问题。
Evaluation and Improvement：这一部分，我们先回答“当前 policy 有多好” (policy evaluation), 再介绍 value-based methods, 该部分会解释为什么 Q-learning/DQN 对理解 RL 很重要，但通常不是优化 LLM policy 的最终选择。
Policy Optimization：这一部分，我们从 policy gradient methods 逐步过渡到 actor-critic methods, 在这个过程中，我们将逐步优化 policy model 和 value model 的训练与使用。这也是后续 PPO 算法的核心。
Modern RL Algorithms for LLM：我们将从 TRPO 开始, 逐步介绍 PPO, GRPO 所做的改进，到这一步，我们就接触到了现代 RL 算法的核心部分。

前两部分建立后续推导所需的共同语言；如果读者已经熟悉经典 RL，可以先阅读 LLM as an MDP，再从 Policy Evaluation 进入算法主线。

Acknowledgements

这个 tutorial 主要参考了以下两位老师的课程和材料：

西湖大学赵世钰老师的 Mathematical Foundations of Reinforcement Learning
UCLA Ernest K. Ryu 老师的 Reinforcement Learning of Large Language Models

RL Basics

本章的目标是建立全文统一使用的语言：我们先用 MDP 描述 agent 与 environment 的交互，再定义 trajectory, return 和优化目标。最后我们把 auto-regressive generation 写成一个 token-level MDP. 后续章节我们会一直使用这里定义的 LLM state, action 和 reward.

RL 的基本思想是让 agent 通过与环境交互，学习能够最大化期望回报的策略。 其定义为：

强化学习是一个通过构建可以与 environment 进行交互的 agent 来解决控制和决策任务的学习框架，交互的方式为 agent 执行 action, 然后 environment 给予反馈。

RL 的执行过程如下所示

RL 的数学建模依赖于 Markov Decision Process, 下面我们先介绍相关概念。

Markov Decision Process (MDP)

Definition: Markov Decision Process

MDP 是一个可以用于描述强化学习的数学模型，形式化为：

状态 (State): $s_t \in \mathcal{S}$ , $\mathcal{S}$ 为状态空间。
动作 (Action): $a_t \in \mathcal{A}$ , $\mathcal{A}$ 为动作空间。
奖励 (Reward): $r_t \in \mathbb{R}$ , 环境对 agent 执行动作 $a_t$ 的反馈。
终止时间 (Terminal Time): $T$ ，且定义 $s_T = \langle\text{term}\rangle$ 为终止状态。
初始状态分布 (Initial State): $s_0 \sim p_0$ .
状态转移概率 (Transition Probability): $(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)$ .
马尔可夫性 (Markov Property):

\htmlId{markov_property}{\begin{equation} p(s_{t+1} \mid s_t, a_t, \ldots) = p(s_{t+1} \mid s_t, a_t),\ p(r_t \mid s_t, a_t, \ldots) = p(r_t \mid s_t, a_t). \end{equation}}

为了简化，我们采用以下约定：

当 $r_t$ 完全由 $(s_t,a_t)$ 决定时，记为 $r_t = r(s_t, a_t)$ .
状态转移函数是平稳的 (stationary), 即 $p_t(r,s'\mid s,a) = p(r,s'\mid s,a)$ .
$a_t$ 由策略 $\pi$ 决定，确定性策略记为 $a_t = \pi(s_t)$ , 随机策略记为 $a_t \sim \pi(\cdot \mid s_t)$ .
通常我们使用神经网络表示策略，即 $\pi = \pi_\theta$ , 其中 $\theta$ 为网络参数。
我们用 $S_t$ , $A_t$ 代表 $t$ 时刻的状态和动作，这是一个随机变量，用 $S_t=s_t$ , $A_t=a_t$ 代表当前状态为 $s_t$ ，当前动作为 $a_t$ .

Trajectory

接下来，我们介绍 trajectory, 也就是 RL 算法所需要的数据的定义

Definition: Trajectory

Trajectory (rollout) 定义为 agent 与环境完整的一次交互过程：

\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots, s_{T-1}, a_{T-1}, r_{T-1}, s_T)

其概率分布为

p(\tau \mid s_0, \pi, p) = p_0(s_0) \prod_{t=0}^{T-1} \pi(a_t \mid s_t) \, p(r_t, s_{t+1} \mid s_t, a_t)

轨迹的概率分布由初始状态分布、策略以及环境模型共同决定，记为 $\tau \sim (p_0, \pi, p)$ .
轨迹的概率分布使用了 Markov property.
本教程仅考虑 finite horizon MDP, 即 $T < \infty$ .

Return

接下来，我们介绍 RL 算法的优化目标 (discounted) return.

Definition: Discounted Return

一条 trajectory 上的 (discounted) return 定义为：

R(\tau) = \sum_{t=0}^{T-1} \gamma^t r_t

其中 $\gamma \in (0, 1]$ 是 discount factor，用于将未来的奖励折现到当前时刻。

从时刻 $t$ 开始的 return 记为：

G_t = \sum_{k=t}^{T-1} \gamma^{k-t} r_k

$G_t$ 存在如下递推关系：

G_t = r_t + \gamma G_{t+1}

易知

R(\tau) = G_0.

Objective of RL

RL 的最终目标为最大化 expected return, 形式化为：

\htmlId{rl_objective}{\begin{equation} \max_{\pi} \quad \mathbb{E}_{\tau \sim (p_0, \pi, p)} \, R(\tau) = \max_{\pi} \quad \mathbb{E}_{\tau \sim (p_0, \pi, p)} \left[ \sum_{t=0}^{T-1} \gamma^t r_t \right] \end{equation}}

这里期望 $\mathbb{E}^\pi$ 对应的随机变量为 $a_t \sim \pi(\cdot \mid s_t)$ , $(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)$ .

这个目标函数源于强化学习的核心假设

Reward Hypothesis: 所有的目标都可以被描述为最大化 expected return.

由于实际问题中，初始状态 $s_0$ 和状态转移函数 $p$ 一般保持不变，因此我们一般省略目标函数中的 $s_0$ 和 $p$ , 将目标函数简化为

\max_{\pi} \quad \mathbb{E}_{\tau\sim\pi} \, R(\tau)

Connection with LLM

这一节我们介绍如何用 RL 的定义来建模 auto-regressive LLM. LLM 定义如下：

y_t \sim \mathrm{LLM}(\cdot \mid y_{<t}, x)

其中 $x$ 是输入的 prompt, $y_{<t}$ 是已经生成的部分 (generated prefix), $y_t$ 是下一个要生成的 token.

RL 和 LLM 的对应关系如下 (Shen et al., 2026)：

RL	LLM	Description
initial state $s_0$	$x$	prompt
state $s_t$	$s_t=(y_{<t}, x)$	prompt and generated prefix
action $a_t$	$y_t$	next token selected from vocabulary
policy $\pi(a_t\mid s_t)$	$\mathrm{LLM}(y_t \mid s_t)$	next token prediction distribution
trajectory $\tau$	$(y_{1:T},x)$	complete prompt-response pair
Return $R(\tau)$	$R(x,y)$	reward model or verifier score
transition $P(s_{t+1}\mid s_t,a_t)$	$s_{t+1} = \mathrm{concat}(y_t, s_t)$	deterministic string concatenation

Running Example: ToyLLM

为了让后续公式可以被直接计算和实验验证，我们使用一个 finite-horizon episodic MDP ToyLLM 作为示例。它保留 autoregressive generation 的核心结构，同时将 vocabulary 和最大生成长度控制在可以枚举的范围内。

给定一个固定 prompt $x$ , 最大 response 长度 $T$ 和 target response $y^*=(y_0^*,\ldots,y_{L-1}^*)$ , 其中 $L\leq T$ . 对于普通 token 词表 $\overline{\mathcal V}$ , 我们令 $\mathcal V=\overline{\mathcal V}\cup\{\langle\mathrm{eos}\rangle\}$ .

时刻 $t$ 的 state 是 prompt 和已经生成的 prefix, action 是下一个 token：

s_t=(x,y_{<t}),\quad y_{<t}=(a_0,\ldots,a_{t-1}),\quad a_t=y_t\in\mathcal V.

普通 token 会被确定性地追加到 prefix；生成 <eos> 或已经生成 $T$ 个普通 token 时，episode 终止。去掉 <eos> 后的完整 response 记为 $y$ ，环境只在 episode 结束时给出 exact-match reward：

R(y)=\begin{cases} 1,&\text{if }y=y^*,\\ 0,&\text{otherwise}. \end{cases}

对这个固定 prompt, action space 和非终止状态空间分别为

\mathcal A=\mathcal V,\qquad \mathcal S_{\mathrm{non-terminal}}=\bigcup_{t=0}^{T-1}\{x\}\times\overline{\mathcal V}^{\,t}.

令 $K=|\overline{\mathcal V}|$ . 如果所有结束后的 response 共用一个 terminal state, 则状态总数为

S:=|\mathcal S|=1+\sum_{t=0}^{T-1}K^t.

因此，即使 transition 是确定性的，prefix state space 仍然随 horizon 指数增长。真实 LLM 的 vocabulary 通常包含数万到数十万个 token, 使 action space 也非常大。

ToyLLM 还有一个重要性质：初始状态的 value 存在解析解。令成功所需的 action sequence 为

a^*= \begin{cases} (y_0^*,\ldots,y_{L-1}^*,\langle\mathrm{eos}\rangle),&L<T,\\ (y_0^*,\ldots,y_{T-1}^*),&L=T, \end{cases}

并令 $m=|a^*|$ . 如果 reward 在最后一个 action 后产生，则

V^\pi(s_0) =\gamma^{m-1}\prod_{t=0}^{m-1} \pi(a_t^*\mid x,a_{<t}^*).

这个解析解可以作为后续 matrix solve, Monte Carlo 和 temporal-difference learning 实现的 ground truth. 若 policy 接近 uniform distribution, 成功概率大致按 $|\mathcal V|^{-m}$ 下降，也直接展示了 terminal verifier reward 带来的 sparse-reward 问题。

ToyLLM 的 exact-match reward 是 verifier 的最简单形式。真实 RLVR 通常从 prompt distribution $x\sim\mathcal D$ 采样问题，并用 $\operatorname{Verifier}(x,y)$ 接受多种等价的正确答案。 ToyLLM 暂时固定一个 prompt 和 target，以便隔离并研究 policy evaluation 与 policy improvement.

在 Policy Evaluation 一章中，我们将比较依赖完整环境模型的精确解法、只依赖 rollout 的 MC/TD 方法，以及能够在不同 prefix 之间共享信息的 function approximation.

Takeaway

RL 的基础是 MDP, 其核心假设是 Markov property, 即未来的状态和奖励只与当前状态和动作有关，与历史无关。
trajectory return 是随机变量；RL 目标是最大化它在 policy 和环境随机性下的期望。
从 RL 角度看，LLM 本身是一个 policy, 其初始状态为 prompt, 动作空间为 vocabulary 中的 token index, 奖励由多方面给定，environment 仅对 token 进行简单拼接。
ToyLLM 将作为贯穿示例，帮助我们把 Bellman equation、policy evaluation 和 policy optimization 映射回 token generation。
虽然 action space 和 state space 是离散的，但是其数量级非常大，因此我们通常使用函数逼近来近似 value function 和 Q-function.

Shen, J., Luo, S., Li, Y., Liu, J., Qu, W., Zhang, Y., Huang, Z., Li, T., Hu, M., Liu, X., Chen, Y., & He, J. (2026). A First-Principles Derivation of LLM Policy Optimization: From Expected Reward to GRPO and Its Structural Extensions. https://arxiv.org/abs/2606.16733

Bellman Equation Theorem

Bellman equation 将 return 的递推结构转化为 value function 的递推结构。本章我们先研究固定 policy 的 value function, 再研究 optimal policy 中的 optimal value function, 前者通向 policy evaluation, 后者通向 value based methods.

Why Bellman Equation?

在强化学习中，我们关心的是 agent 从当前状态出发，在未来持续决策后能够获得的 expected return. 但是，expected return 依赖于整条未来轨迹：后续会到达什么状态、采取什么动作、获得什么奖励，都是随机的。

直接分析完整 trajectory 的 expected return 往往比较困难。本节将建立关于 policy value 的基本定理，后续算法可以据此只处理相邻时间步之间的关系。本节的核心思想在于：

将长期回报写成”当前一步的收益 + 下一状态的未来价值”，把一个全局问题转化为递推问题。即

\text{long-term return} = \text{immediate reward} + \text{discounted future return}

Value Function and Q function

首先，我们介绍两个基本概念，分别是 value function $V^{\pi}(s_t)$ 和 Q function $Q^{\pi}(s_t, a_t)$ .

Definition: Value Function

我们定义 value function 如下：

V^{\pi}(s_t) = \mathbb{E}^{\pi}[G_t \mid S_t = s_t]

value function 的具体含义为：agent 从当前状态 $s_t$ 出发，一直遵循当前策略 $\pi$ ，最后获取到的 return.

Definition: Q Function

Q function (state-action value function) 定义如下：

Q^{\pi}(s_t, a_t) = \mathbb{E}^{\pi}[G_t \mid S_t=s_t, A_t=a_t]

其具体含义为：agent 从当前状态 $s_t$ 出发，先执行 action $a_t$ ，再遵循当前策略 $\pi$ ，最后获取到的 return.

为了方便，我们令 $V^{\pi}(\langle\text{term}\rangle) = 0$ , $Q^{\pi}(\langle\text{term}\rangle, a) = 0, \forall a \in \mathcal{A}$ .

Value function 和 Q function 存在如下关系：

Proposition: Relationship between value function and Q function

V^{\pi}(s_t) = \mathbb{E}_{a \sim \pi(\cdot \mid s_t)}[Q^{\pi}(s_t, a)]

即 value function 是 Q function 关于 action $a_t$ 的期望。

Proof:

由全概率公式，我们有：

\begin{aligned} V^{\pi}(s_t) &= \mathbb{E}^{\pi}[G_t \mid S_t = s_t] \\ &= \sum_{a \in \mathcal{A}} \mathbb{E}^{\pi}[G_t \mid S_t = s_t, A_t = a] \, \pi(a \mid s_t) \\ &= \sum_{a \in \mathcal{A}} Q^{\pi}(s_t, a) \, \pi(a \mid s_t) = \mathbb{E}_{a \sim \pi(\cdot \mid s_t)}[Q^{\pi}(s_t, a)] \end{aligned}

Value function 和 Q function 存在如下递推关系：

Proposition: Iterative property of Value function and Q function

\boxed{ \begin{aligned} V^{\pi}(s_t) &= \mathbb{E}_{a_t \sim \pi(\cdot \mid s_t), \, (r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}[r_t + \gamma V^{\pi}(s_{t+1}) \mid S_t=s_t] \\ Q^{\pi}(s_t, a_t) &= \mathbb{E}_{(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t), \, a_{t+1} \sim \pi(\cdot \mid s_{t+1})}[r_t + \gamma Q^{\pi}(s_{t+1}, a_{t+1}) \mid S_t=s_t, A_t=a_t] \end{aligned} }

Proof:

我们以 value function 为例：

\begin{aligned} V^{\pi}(s_t) &= \mathbb{E}^{\pi}[G_t \mid S_t = s_t] \\ &= \mathbb{E}^{\pi}[r_t + \gamma G_{t+1} \mid S_t = s_t] \\ &= \mathbb{E}_{a_t \sim \pi(\cdot \mid s_t), \, (r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[\mathbb{E}^{\pi}[r_t + \gamma G_{t+1} \mid s_t, a_t, r_t, s_{t+1}] \mid S_t = s_t\right] \\ &= \mathbb{E}_{a_t \sim \pi(\cdot \mid s_t), \, (r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r_t + \gamma \mathbb{E}^{\pi}[G_{t+1} \mid s_{t+1}] \mid S_t = s_t\right] \\ &= \mathbb{E}_{a_t \sim \pi(\cdot \mid s_t), \, (r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r_t + \gamma V^{\pi}(s_{t+1}) \mid S_t = s_t\right] \end{aligned}

这里第四个等式使用了 Markov property，即 $G_{t+1}$ 在已知 $s_{t+1}$ 的条件下与 $s_t, a_t, r_t$ 无关。

Q function 的证明类似，略过。

Bellman Equation Theorem

上面的递推关系说明了 value function 和 Q function 满足一个递推关系，接下来， Bellman Equation Theorem 证明了满足这个递归关系的函数一定是 value function/Q function.

Theorem: Bellman Equation Theorem (Value Function)

令 $\pi$ 为一个策略，假设 $\gamma \in (0, 1)$ , $|\mathcal{S}| < \infty$ 以及 $|r| \leq R < \infty$ , 几乎处处成立 ( $a.s.$ ). 那么 $\pi$ 对应的 value function $V^{\pi}: \mathcal{S} \to \mathbb{R}$ 存在，且满足 Bellman equation:

\htmlId{BE_value_function}{\begin{equation} V^{\pi}(s_t) = \mathbb{E}_{a_t \sim \pi(\cdot \mid s_t), \, (r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r_t + \gamma V^{\pi}(s_{t+1}) \mid S_t=s_t\right] \end{equation}}

反之，如果存在函数 $V: \mathcal{S} \to \mathbb{R}$ 满足 Bellman equation, 则 $V = V^{\pi}$ .

Proof:

由 iterative property 我们知道 value function 满足 Bellman equation，接下来我们证明唯一性.

假设存在函数 $V: \mathcal{S} \to \mathbb{R}$ 满足 Bellman equation. 我们定义 Bellman 算子 $\mathcal{T}^{\pi}$ 为：

\htmlId{bellman_operator}{\begin{equation} (\mathcal{T}^{\pi} V)(s_t) := \mathbb{E}_{a_t \sim \pi(\cdot \mid s_t), \, (r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r_t + \gamma V(s_{t+1}) \mid S_t=s_t\right] \end{equation}}

我们证明该算子是一个 contraction mapping, 考虑范数 $\|V\|_{\infty} = \max_{s \in \mathcal{S}} |V(s)|$ :

\begin{aligned} \left|(\mathcal{T}^{\pi} V_1)(s_t) - (\mathcal{T}^{\pi} V_2)(s_t)\right| &= \left|\mathbb{E}_{a_t \sim \pi(\cdot \mid s_t), \, (r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[\gamma V_1(s_{t+1}) - \gamma V_2(s_{t+1})\right]\right| \\ &\leq \gamma \, \mathbb{E}_{a_t \sim \pi(\cdot \mid s_t), \, (r, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left|V_1(s_{t+1}) - V_2(s_{t+1})\right| \\ &\leq \gamma \max_{s \in \mathcal{S}}\left|V_1(s) - V_2(s)\right| \\ &= \gamma \left\|V_1 - V_2\right\|_{\infty} \end{aligned}

上式对任意 $s \in \mathcal{S}$ 成立，因此：

\left\|\mathcal{T}^{\pi} V_1 - \mathcal{T}^{\pi} V_2\right\|_{\infty} \leq \gamma \left\|V_1 - V_2\right\|_{\infty}

由于 $\gamma < 1$ , 因此 $\mathcal{T}^{\pi}$ 是一个 contraction mapping.

根据不动点定理，已知 $V^{\pi}$ 是一个不动点（满足 Bellman equation），而不动点唯一，因此 $V = V^{\pi}$ .

对于 Q function, 我们也有相同的结论：

Theorem: Bellman Equation Theorem (Q Function)

令 $\pi$ 为一个策略，假设 $\gamma \in (0, 1)$ , $|\mathcal{S}| < \infty$ , $|\mathcal{A}| < \infty$ 以及 $|r| \leq R < \infty$ , 几乎处处成立 ( $a.s.$ ). 那么 $\pi$ 对应的 Q function $Q^{\pi}: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ 存在，且满足 Bellman equation:

\boxed{ Q^{\pi}(s_t, a_t) = \mathbb{E}_{(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t), \, a_{t+1} \sim \pi(\cdot \mid s_{t+1})}\left[r_t + \gamma Q^{\pi}(s_{t+1}, a_{t+1}) \mid S_t=s_t, A_t=a_t\right] }

反之，如果存在函数 $Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ 满足 Bellman equation, 则 $Q = Q^{\pi}$ .

Proof:

证明与 value function 的证明类似，略过。

Bellman Optimality Equation Theorem

上一节我们介绍了针对一般 policy 的 Bellman equation, 这一节我们给出针对 optimal policy 的 Bellman Optimal Equation.

我们首先给出 optimal policy 的定义

Definition: Optimal Policy

如果策略 $\pi^*$ 满足：

V^{\pi^*}(s) \geq V^{\pi}(s), \quad \forall s \in \mathcal{S}, \, \forall \pi

则称策略 $\pi^*$ 是 optimal policy. 对应的 $V^{\pi^*}$ 和 $Q^{\pi^*}$ 分别称为 optimal value function 和 optimal Q function, 简记为 $V^* = V^{\pi^*}$ , $Q^* = Q^{\pi^*}$ .

optimal policy 通常依赖于状态 $s$ ，并且可能不唯一；但所有 optimal policy 对应同一个 optimal value function $V^*$ .

与 value function $V^\pi$ 和 Q function $Q^\pi$ 之间存在联系一样，optimal value function $V^{*}$ 和 optimal Q function $Q^{*}$ 也存在类似关系

Proposition: Relationship between optimal value function and optimal Q function

\boxed{V^*(s_t) = \max_{a \in \mathcal{A}} Q^*(s_t, a)}

即 $V^*$ 就是 $Q^*$ 的最优动作对应的 return.

Proof:

我们先证左边小于等于右边：

V^*(s_t) = \mathbb{E}_{a \sim \pi^*(\cdot \mid s_t)}[Q^*(s_t, a)] \leq \mathbb{E}_{a \sim \pi^*(\cdot \mid s_t)}[\max_{a \in \mathcal{A}} Q^*(s_t, a)] = \max_{a \in \mathcal{A}} Q^*(s_t, a)

再证右边小于等于左边：

令 $a^* \in \arg\max_{a} Q^*(s_t, a)$ , 令策略 $\pi'$ 为确定性策略 $\pi'(a^* \mid s_t) = 1$ , 则：

\max_{a \in \mathcal{A}} Q^*(s_t, a^*) = Q^{\pi'}(s_t, a^*) = V^{\pi'}(s_t) \leq V^*(s_t)

因此两边相等。

接下来，我们给出关于 optimal value function $V^*$ 对应的 Bellman optimality equation.

Theorem: Bellman Optimality Equation Theorem (value function)

假设 $\gamma \in (0, 1)$ , $|\mathcal{S}| < \infty$ , $|\mathcal{A}| < \infty$ 以及 $|r| \leq R < \infty$ , 几乎处处成立 (a.s.). 那么 optimal value function $V^*:\mathcal{S} \to \mathbb{R}$ 存在，且满足 Bellman optimality equation:

\boxed{ V^*(s_t) = \max_{a \in \mathcal{A}} \mathbb{E}_{(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r_t + \gamma V^*(s_{t+1}) \mid S_t=s_t,A_t=a_t\right] }

反之，如果存在函数 $V: \mathcal{S} \to \mathbb{R}$ 满足 Bellman optimality equation, 则 $V = V^*$ .

最后，我们可以给出一个 optimal deterministic policy:

\htmlId{optimal_deterministic_policy}{\begin{align} \pi^*(s_t) &= \arg\max_{a \in \mathcal{A}} \mathbb{E}_{(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r_t + \gamma V^*(s_{t+1}) \mid S_t=s_t, A_t=a_t\right]\\ &= \arg\max_{a \in \mathcal{A}} Q^*(s_t, a) \end{align}}

证明需要用到下面的引理

Lemma: Monotonicity of Bellman operator

令 $\pi$ 为一个策略， $\mathcal{T}^{\pi}$ 和 $\mathcal{T}^*$ 分别是 Bellman operator 和 Bellman optimality operator, 其中 Bellman optimality operator 定义为

\htmlId{bellman_optimality_operator}{\begin{equation} (\mathcal{T}^* V)(s_t) := \max_{a \in \mathcal{A}} \mathbb{E}_{(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r_t + \gamma V(s_{t+1}) \mid S_t=s_t, A_t=a_t\right] \end{equation}}

我们有：

对任意 $V: \mathcal{S} \to \mathbb{R}$ , 有 $\mathcal{T}^{\pi} V(s) \leq \mathcal{T}^* V(s), \, \forall s \in \mathcal{S}$ .
对任意 $U, V: \mathcal{S} \to \mathbb{R}$ , 如果 $U \leq V$ , 则 $\mathcal{T}^* U(s) \leq \mathcal{T}^* V(s), \, \forall s \in \mathcal{S}$ .

证明如下

Proof:

我们首先证明 Bellman optimality operator $\mathcal{T}^*$ 是一个 contraction mapping: 对任意 $V_1, V_2$ :

\begin{aligned} \left|(\mathcal{T}^* V_1)(s_t) - (\mathcal{T}^* V_2)(s_t)\right| &= \left|\max_{a} \mathbb{E}[r_t + \gamma V_1(s_{t+1})] - \max_{a} \mathbb{E}[r_t + \gamma V_2(s_{t+1})]\right| \\ &\leq \max_{a} \left|\mathbb{E}[r_t + \gamma V_1(s_{t+1})] - \mathbb{E}[r_t + \gamma V_2(s_{t+1})]\right| \\ &= \gamma \max_{a} \left|\mathbb{E}[V_1(s_{t+1}) - V_2(s_{t+1})]\right| \\ &\leq \gamma \|V_1 - V_2\|_{\infty} \end{aligned}

这里第一个不等式使用了 $|\max_s v(s) - \max_s u(s)| \leq \max_s |u(s) - v(s)|$ .

因此 $\|\mathcal{T}^* V_1 - \mathcal{T}^* V_2\|_{\infty} \leq \gamma \|V_1 - V_2\|_{\infty}$ , $\mathcal{T}^*$ 是 contraction mapping.

根据不动点定理， $\mathcal{T}^*$ 存在唯一不动点 $V^*$ .

我们定义：

\pi^*(s_t) = \arg\max_{a \in \mathcal{A}} \mathbb{E}_{(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r + \gamma V^*(s_{t+1}) \mid S_t=s_t, A_t=a_t\right]

此时，我们有 TODO

\begin{aligned} V^*(s_t) &= \mathbb{E}^{\pi^*}\left[r_t+\gamma V^*(s_{t+1})\mid s_t\right]\\ &= \mathbb{E}^{\pi^*}\left[r_t+\gamma \mathbb{E}^{\pi^*}\left[r_{t+1}+\gamma V^*(s_{t+2})\mid s_{t+1}\right]\mid s_t\right]\\ &= \mathbb{E}^{\pi^*}\left[\mathbb{E}^{\pi^*}\left[r_t+\gamma (r_{t+1}+\gamma V^*(s_{t+2}))\mid s_{t+1}\right]\mid s_t\right]\\ &= \mathbb{E}^{\pi^*}\left[r_t+\gamma r_{t+1}+\gamma^2 V^*(s_{t+2})\mid s_t\right]\\ &= \mathbb{E}^{\pi^*}\left[r_t+\gamma r_{t+1}+\gamma^2r_{t+2}+\cdots\mid s_t\right]= V^{\pi^*}(s_t) \end{aligned}

即 $V^*=V^{\pi^*}$ , 这里第四个等式使用了 Law of Total Expectation.

现在我们证明 $\pi^*$ 是最优策略，令 $\pi$ 为任意一个策略，我们有

V^\pi=\mathcal{T}^{\pi}V \le \mathcal{T}^*V \leq (\mathcal{T}^*)^2(V^\pi) \leq \cdots \leq (\mathcal{T}^*)^k(V^\pi) \xrightarrow[k\to\infty]{\text{fixed-point / contraction}} V^*.

即 $V^\pi\leq V^*$ , 这里第一个等式和第二个等式利用了 Lemma, 由于 $V^\pi$ 是任意的，我们有 $V^*=V^{\pi^*}$ .

对于 optimal Q function $Q^*$ , 我们也有类似的结论。

Theorem: Bellman Optimality Equation Theorem (Q function)

假设 $\gamma \in (0, 1)$ , $|\mathcal{S}| < \infty$ , $|\mathcal{A}| < \infty$ 以及 $|r| \leq R < \infty$ , 几乎处处成立 (a.s.). 那么 optimal Q function $Q^*: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ 存在，且满足 Bellman optimality equation:

\boxed{ Q^*(s_t, a_t) = \mathbb{E}_{(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)}\left[r + \gamma \max_{a_{t+1} \in \mathcal{A}} Q^*(s_{t+1}, a_{t+1}) \mid S_t=s_t, A_t=a_t\right] }

反之，如果存在函数 $Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ 满足 Bellman optimality equation, 则 $Q = Q^*$ .

Proof:

证明与 value function 类似，略过。

下一章我们将从这个精确但不可扩展的起点出发，逐步引入 sampling 和 function approximation 来完成 policy evaluation.

Takeaway

$G_t=r_t+\gamma G_{t+1}$ 使 return 可以递归分解；对它取条件期望便得到 Bellman equation.
Bellman equation 回答“固定 policy 的价值是什么”，Bellman optimality equation 回答“所有 policy 中的最优价值是什么”。
对 LLM，value 描述从 (prompt, token prefix) 继续生成后的期望最终得分； Bellman recursion 则承担将稀疏 terminal reward 传回早期 token 的 credit assignment.

Policy Evaluation

在 Bellman Equation Theorem 一节中，我们看到 $V^\pi$ 是 Bellman operator $\mathcal T^\pi$ 的唯一不动点。 Bellman optimality equation 直接寻找最优价值，而本章先解决一个更基础的 evaluation 问题：

给定一个策略 $\pi$ ，如何高效求解策略 $\pi$ 对应的 value function $V^\pi$ ?

我们将先从完整 MDP 模型的精确解法，逐步过渡到只依赖 rollout 的 MC/TD 方法和现代 RL 使用的函数逼近方法。本章始终固定 $\pi$ ：无论更新 Q-table 还是 neural network，改变的都只是对这个策略的价值估计，生成动作的规则不变。我们依次回答三个问题：

已知完整环境模型，如何精确计算 $V^\pi$ ？
只能采样 rollout 时，如何用 MC/TD 估计 $V^\pi$ ？
状态太多时，如何用函数逼近在不同 prefix 之间共享信息？

如何利用这些估计改变策略，将留到下一章 Value Based Methods。

Running Example: Evaluating a Frozen ToyLLM

沿用 ToyLLM，取普通词表 $\{A,B\}$ 、最大生成长度 $T=2$ 、target response $y^*=(B,A)$ ，并令 $\gamma=1$ 。动作空间还包含 <eos>；提前结束或生成其他 response 均获得零奖励。假设当前固定策略满足

\pi(A\mid x)=0.6,\quad \pi(B\mid x)=0.3,\quad \pi(\langle\mathrm{eos}\rangle\mid x)=0.1,\qquad \pi(A\mid x,B)=0.5.

在 prefix $B$ 之后，其余动作共享剩下的 $0.5$ 概率，具体分配不影响下面的计算。由于只有 response $BA$ 成功，

V^\pi(x,B)=0.5,\qquad Q^\pi(x,B)=0.5,\qquad Q^\pi(x,A)=Q^\pi(x,\langle\mathrm{eos}\rangle)=0,

V^\pi(x)=0.3\times0.5=0.15.

这里 $V^\pi(x,B)$ 表示到达 prefix $B$ 后的价值，而 $Q^\pi(x,B)$ 表示在初始状态 $x$ 选择动作 $B$ 的价值；二者在这个零中间奖励、 $\gamma=1$ 的例子中相等。无论使用哪种 evaluation 方法，我们的目标都是恢复这些数值。 即使已经知道动作 $B$ 比 $A$ 更好，本章也不会修改 $\pi(B\mid x)=0.3$ 。

一般 finite-horizon MDP 的价值还依赖剩余时间，可以把时间并入 state。 ToyLLM 的 prefix 长度已经包含这一信息，终止状态的 value 统一设为零。以下 contraction 论证使用 $0<\gamma<1$ ；ToyLLM 在 $\gamma=1$ 时仍可按 prefix 长度做有限步 backward induction，不能直接套用严格 contraction 的论证。

Tabular Learning

这一节我们介绍针对离散小空间场景下的求解和优化方案。

Tabular Learning with Matrix Solve

对于有限状态空间，固定策略的 Bellman Equation 可以写成线性方程组。这里计算的是 $V^\pi$ ，不是 value iteration 所寻找的 $V^*$ ：

V_{\pi} = R_{\pi} + \gamma P_{\pi} V_{\pi}

其中

\begin{aligned} V_\pi &= [V_{\pi}(s_1),\dots, V_{\pi}(s_S)]^T\in\mathbb{R}^S\\ R_\pi &=[R_{\pi}(s_1),\dots, R_{\pi}(s_S)]^T\in\mathbb{R}^S\\ P_\pi &=[P_\pi(s_j\mid s_i)]\in\mathbb{R}^{S\times S} \end{aligned}

其中 $R_\pi(s)=\mathbb E[r\mid s,a\sim\pi]$ ， $P_\pi$ 对动作按固定策略求平均。我们只编号非终止状态，因此转移到 terminal 的概率质量不写入 $P_\pi$ ，其行和可以小于 1。于是

(\mathbf{I}_S - \gamma P_{\pi})V_{\pi} = R_{\pi}

实现时使用线性求解器 SOLVE，不必显式计算逆矩阵。下面的 STEP(s,a) 伪代码针对 ToyLLM 这样的确定性 reward/transition；随机环境需要枚举并加权所有可能的 $(r,s')$ ，单次 STEP 样本不能给出精确模型。这里 $\mathcal S$ 在算法输入中指非终止状态集合。精确算法如下所示

Algorithm: Value function Matrix Exact Solve

Input: policy $\pi$ , discount factor $\gamma$ , state space $\mathcal{S}$ with size $S$

assign index $i(s)$ for $s\in\mathcal{S}, i=1,\dots,S$
$P=\mathbf{0}_{S\times S}$ , $R=\mathbf{0}_{S}$
For each $s\in\mathcal{S}$ $s \in S$
1. $i\gets i(s)$
2. For each $a\in\mathcal{A}$ $a \in A$
  - $(s', r, \mathrm{done}) \gets \mathrm{STEP}(s, a)$
  - $R[i]\gets R[i]+\pi(a\mid s)\cdot r$
  - If NOT $\mathrm{done}$ $done$
    - $j\gets i(s')$
    - $P[i,j]\gets P[i,j]+\pi(a\mid s)$
$V\gets \mathrm{SOLVE}(I_S-\gamma P, R)$
return $V$

迭代算法则是给定随机初始化的 $V_0$ , 我们通过迭代计算得到序列 $\{V_k\}$ , 其中 $V_{k+1}=R_{\pi} + \gamma P_{\pi}V_k$ , 我们可以证明这个序列收敛到 $V_{\pi}$ .

Algorithm: Value function Matrix Iterative Solve

Input: policy $\pi$ , discount factor $\gamma$ , convergence threshold $\theta$ , state space $\mathcal{S}$

$V(s)=0, s\in\mathcal{S}$ , $\Delta=\infty$ .
While $\Delta > \theta$ $Δ > θ$ :
1. $\Delta\gets0$
2. For each $s\in\mathcal{S}$ $s \in S$
  1. $v\gets0$
  2. For each $a\in\mathcal{A}$ $a \in A$
    - $(s', r, \mathrm{done}) \gets \mathrm{STEP}(s, a)$
    - If $\mathrm{done}$ $done$
      - $v \gets v + \pi(a|s) \cdot r$
    - Else
      - $v \gets v + \pi(a|s) \cdot (r + \gamma \cdot V(s'))$
  3. $\Delta ← max(\Delta, |v − V(s)|)$
  4. $V(s) \gets v$
return $V$

对 ToyLLM 的有限生成树，还可以按 prefix 长度倒序计算，避免稠密矩阵求解；但这仍需要访问所求解的状态。下面是两种已有实现的求解时间变化曲线

Comparison of matrix solve and iterative solve

可以看到，由于稠密线性方程组的直接求解通常需要 $\mathcal{O}(S^3)$ 时间和 $\mathcal{O}(S^2)$ 空间，随着状态数 $S$ 的增加，其所需时间急剧上升。而迭代解法虽然比矩阵直接求解效率更高，但是仍然需要枚举全部状态，当状态空间增大之后，迭代解法的时间也无法接受。因此，我们需要计算更加高效的算法。

Tabular Learning with MC

由 $V^{\pi}$ 定义，我们有：

V^{\pi}(s_0) = \mathbb{E}^{\pi}\left[R(\tau) \mid s_0\right]

由于 return 是一个随机变量，我们可以利用 Monte Carlo (MC) 方法得到一个 Unbiased Estimator，即从 $s_0$ 出发，独立随机采样 (i.i.d.) $M$ 条轨迹：

\{\tau^{(i)} = (s_0, a_0^{(i)}, r_0^{(i)}, \dots, a_{T^{(i)}-1}^{(i)}, r_{T^{(i)}-1}^{(i)}, s_{T^{(i)}}^{(i)})\}, \quad i = 1, \dots, M

然后我们使用样本平均 (sample mean) 来近似期望：

V^{\pi}(s_0) = \mathbb{E}^{\pi}[R(\tau) \mid s_0] \approx \frac{1}{M} \sum_{i=1}^{M} R(\tau^{(i)})

对应的算法如下所示

Algorithm: Tabular Learning with MC

Input: policy $\pi$ , discount factor $\gamma$ , episodes $M$ , state space $\mathcal{S}$ , initial state distribution $p_0$

$V(s)=0, \mathrm{ReturnSum}(s)=0, \mathrm{ReturnCount}(s)=0, s\in\mathcal{S}$
For $\mathrm{episode}=1,2,\dots,M$ $episode = 1, 2, \dots, M$ :
1. $s\sim p_0$ , $\mathrm{done}=\mathrm{false}$ , $\tau=[]$
2. While not $\mathrm{done}$ $done$ :
  - $a\sim\pi(\cdot\mid s)$
  - $(s', r, \mathrm{done}) \gets \mathrm{STEP}(s, a)$
  - $\tau.\mathrm{append}((s,r))$
  - $s\gets s'$
3. $\mathrm{Returns}=[]$ , $G\gets0$
4. For $(s,r)$ $(s, r)$ in $\mathrm{reversed}(\tau)$ $reversed (τ)$
  - $G\gets r + \gamma G$
  - $\mathrm{Returns}.\mathrm{prepend}((s,G))$
5. $\mathrm{Visited}=\emptyset$
6. For $(s,G)$ $(s, G)$ in $\mathrm{Returns}$ $Returns$
  - If $s\not\in \mathrm{Visited}$ $s \neq \in Visited$
    - $\mathrm{Visited}.\mathrm{add}(s)$
    - $\mathrm{ReturnSum}(s) \gets \mathrm{ReturnSum}(s) +G$
    - $\mathrm{ReturnCount}(s) \gets \mathrm{ReturnCount}(s)+ 1$
    - $V(s)\gets \mathrm{ReturnSum}(s) / \mathrm{ReturnCount}(s)$
return $V$

上面的伪代码使用了 First-Visit MC：在一个 episode 内，同一个状态可能出现多次，但我们只用它第一次出现位置之后的 return 来更新该状态。

Tabular Learning with TD

MC 的优点是 estimator 是一个 unbiased estimator, 其缺点在于我们必须完整采样完一条轨迹才能得到这个估计，对于 long-horizon task, MC 方法效率很低。

为了解决这个问题，我们可以使用 Temporal difference (TD) learning 方法。 Temporal difference (TD) learning 通过相邻两步的转换关系来近似 value function. 其核心思想在于

通过新的信息和新的预测来更新旧的预测

注意到：

V^{\pi}(s_t) = \mathbb{E}^{\pi}[r_t + \gamma V^{\pi}(s_{t+1}) \mid S_t=s_t]

我们首先定义 TD target 和 TD error 如下

Definition: TD target and TD error

给定当前 estimator $V_t$ ，我们定义 one-step TD target 为

\overline{V}_t = \begin{cases} r_t,&\text{if }s_{t+1}\text{ is terminal},\\ r_t+\gamma V_t(s_{t+1}),&\text{otherwise}. \end{cases}

定义 TD error 为

\delta_t = \overline{V}_t - V_t(s_t).

接下来，我们基于 TD error 更新 $V_t$ ：

V_{t+1}(s) = \begin{cases} V_t(s_t) + \alpha_t(s_t)\delta_t,&\text{if }s=s_t,\\ V_t(s),&\text{otherwise}. \end{cases}

其中 $\alpha_t(s_t) \in (0, 1)$ 是 learning rate.

TD learning 对应的算法如下所示

Algorithm: Tabular Learning with TD

Input: policy $\pi$ , discount factor $\gamma$ , learning rate $\alpha$ , episodes $M$ , state space $\mathcal{S}$ , initial state distribution $p_0$

$V(s)=0, s\in\mathcal{S}$
For $\mathrm{episode}=1,2,\dots,M$ $episode = 1, 2, \dots, M$ :
1. $s\sim p_0$ , $\mathrm{done}=\mathrm{false}$
2. While not $\mathrm{done}$ $done$ :
  - $a\sim\pi(\cdot\mid s)$
  - $(s', r, \mathrm{done}) \gets \mathrm{STEP}(s, a)$
  - If $\mathrm{done}$ $done$
    - $y\gets r$
  - Else
    - $y \gets r + \gamma \cdot V(s')$
  - $V(s)\gets V(s) + \alpha\cdot(y-V(s))$
  - $s\gets s'$
return $V$

一次 TD 更新可以写成

V_{t+1}(s_t)=(1-\alpha_t)V_t(s_t)+\alpha_t\overline V_t.

因此，当 $0<\alpha_t<1$ 时，新估计向本次 sampled target 移动。但是 $\overline V_t$ 本身随采样和 $V_t$ 改变，向当前 target 靠近不等于已经证明收敛。给定采样前的历史 $\mathcal F_t$ （其中包含 $V_t$ 和 $s_t$ ），on-policy 采样满足

\mathbb E[\delta_t\mid\mathcal F_t] =(\mathcal T^\pi V_t)(s_t)-V_t(s_t).

也就是说，TD error 的条件期望是当前估计的 Bellman residual。当 $V_t=V^\pi$ 时，这个期望为零，但单次 TD error 仍可能非零；它不是已知的 $V^\pi-V_t$ 。

Theorem: Convergence of Tabular TD (discounted case)

对有限 MDP、固定策略 $\pi$ 、有界奖励和 $0<\gamma<1$ ，若所有待估计的非终止状态均被无限次访问，并且每个状态按自身访问次数编号的步长满足

\sum_{n=1}^{\infty}\alpha_n(s)=\infty,\qquad \sum_{n=1}^{\infty}\alpha_n(s)^2<\infty,

则标准 on-policy tabular TD(0) 的估计几乎必然收敛到 $V^\pi$ 。未被访问的状态不享有这一保证；常数步长实验也不满足上述递减步长条件。

回到 ToyLLM：若所有 value 初始化为零，一次成功的 $BA$ rollout 会让 MC 同时更新初始状态和 prefix $B$ 。按时间顺序更新的 one-step TD 则先用尚为零的 $V(x,B)$ 更新初始状态，再从 terminal reward 更新 $V(x,B)$ ；之后再次访问时，奖励信息才继续向前传播。这解释了为什么在这个小例子中，MC 可能比 TD 更快，而不意味着 MC 在所有任务中都更高效。

Tabular Learning Experiments

这里保留不同 vocab size 下 matrix solve、MC 和 TD 的已有实验图。需要先区分代码中的两种环境配置：旧版 benchmark 使用成功 $+1$ 、失败 $-1$ ，target 包含 <EOS>；本章手算例子采用成功 $1$ 、失败 $0$ ，匹配时忽略 EOS。因此，旧图中的 value error 是期望回报的误差，不能直接解释为成功概率误差。当 $\gamma=1$ 时，旧奖励对应 $V^\pi=2p_{\mathrm{success}}-1$ ；当 $\gamma<1$ 且结束时间可变时，还必须计入结束时间的折扣。

代码中 scripts/benchmark.py 默认使用 max_len=4、gamma=0.9、uniform policy，并对重复运行取中位数。具体复现应保留命令参数，不能仅凭图片恢复所有实验配置。对于 MC 和 TD, 我们将 episodes 设置为 $10,000$ , TD 的 learning rate 设置为 $0.1$ . 结果如下图所示

可以看到，matrix exact/iterative solve 每次都需要枚举状态，而 MC/TD 的单条数据成本主要由 rollout 长度决定，因此我们可以在不枚举整个状态空间的情况下更新被访问的状态。不过，固定 rollout budget 并不保证所有状态都得到充分访问，因此随着状态空间的增大，MC/TD 方法的误差也逐渐增高。

我们采样成功的概率为

p_{\mathrm{success}}=\prod_{t=0}^{m-1}\pi(a_t^*\mid a_{<t}^*).

如果 policy 接近均匀分布，该概率大致按 $|\mathcal V|^{-m}$ 下降。因此，我们额外统计不同 vocab size 下，MC 和 TD 达到指定误差所需的 episodes. 我们将 maximum episodes 设置为 $100,000$ ，目标 error 设置为 $0.01$ ，结果如下：

Number of rollouts required to reach the target error

可以看到，在这组 terminal +1/-1 reward、固定超参数和误差指标下，MC 比 TD 更快达到目标误差。图中的叉号表示在预算内未达到误差阈值：TD 在词表大小为 20 和 30 时未达标，MC 在 30 时未达标。稀疏成功轨迹是可能的瓶颈，但仅凭该图不能确定具体原因。

解释这类实验时，需要同时报告 horizon、固定策略、value 初始化、误差在哪些状态上计算，以及多个随机种子的结果。在本章的 0/1 reward 版本中，大量失败 prefix 的真实 value 为零，因此不能仅由全状态平均误差很小推断成功路径已经被学会。旧图使用 +1/-1 reward，未访问状态的零初始化也可能与真实的负 value 有较大误差；两种配置需要分别解释。将全状态误差与初始状态误差、成功路径上的误差分别报告，会更容易区分覆盖不足和估计不准。

这里需要区分两个问题：

tabular learning 方法不能在相似 prefix 之间共享信息
稀疏 verifier reward 导致有效样本极少。

函数逼近主要缓解前一个问题；后一个问题还需要更好的 exploration, reward shaping 或更强的初始 policy.

Function Approximation

上面我们介绍了 MC 和 TD 两种 value function 估计方法，但是当动作空间和状态空间特别大时，tabular learning 仍然存在扩展性问题。为了解决这个扩展性不足的问题，当状态空间 $\mathcal{S}$ 较大或连续时，我们可以使用函数逼近的方法来近似 $V^{\pi}$ .

这里我们使用 $V_{\phi}:\mathcal{S}\to\mathbb{R}$ 近似 $V^{\pi}$ ，其中 $\phi$ 是参数。令 $d^\pi$ 为固定策略在 rollout 中诱导的状态访问分布。将非终止状态的期望访问次数归一化，可写为

d^\pi(s)=\frac{\mathbb E_{\tau\sim\pi}[\sum_{t=0}^{T(\tau)-1}\mathbf 1\{s_t=s\}]}{\mathbb E_{\tau\sim\pi}[T(\tau)]}.

它对应按 transition 加权，而不是每条 episode 权重相同。我们使用 mean squared value error:

\mathcal{L}(\phi) = \mathbb{E}_{s \sim d^\pi}\left[\frac{1}{2}\left(V_{\phi}(s) - V^{\pi}(s)\right)^2\right].

$V^\pi(s)$ 满足 $V^\pi(s)=\mathbb E^\pi[G\mid S=s]$ , 因此：

\begin{aligned} \nabla_{\phi} \mathcal{L}(\phi) &= \mathbb{E}_{s \sim d^\pi} \left[\left(V_{\phi}(s)-V^\pi(s)\right)\nabla_{\phi}V_{\phi}(s)\right]\\ &= \mathbb{E}_{s \sim d^\pi,\,G\sim\pi(\cdot\mid s)} \left[\left(V_{\phi}(s)-G\right)\nabla_{\phi}V_{\phi}(s)\right]. \end{aligned}

Function Approximation with MC

现在我们可以使用 MC 方法来估计梯度：

\nabla_{\phi} \mathcal{L}(\phi) \approx g := \frac{1}{M}\sum_{i=1}^{M} \left(V_{\phi}(s^{(i)})-G^{(i)}\right)\nabla_{\phi}V_{\phi}(s^{(i)}).

结合 MC 和 SGD 的算法如下：

Algorithm: Value function approximation with MC

While not converged:

从固定策略的状态访问分布采样非终止状态 $s\sim d^\pi$ 。
从这个状态开始，固定 $\pi$ ，采样一条新的 continuation，直到 terminal。
计算该 continuation 的 discounted return $G$ 。
$g\gets(V_\phi(s)-G)\nabla_\phi V_\phi(s)$ 。
使用 $g$ 做 gradient descent，更新 $\phi$ 。

上面将“选训练状态”和“从该状态采样 return”分开，以明确条件期望。实际训练也可以像 tabular MC 一样复用完整 rollout 的每个 prefix，并把各自的 $G_t$ 当作监督信号。批处理时应明确按 transition 还是按 episode 加权；变长 episode 下，二者一般对应不同的训练目标。

Function Approximation with TD

如果能够访问真实的 $V^\pi(s')$ ，我们可以将一步 TD target 当作监督信号：

\mathcal{L}(\phi) = \mathbb{E}_{s \sim d^\pi}^\pi \left[\frac{1}{2}\left(V_{\phi}(s)-\left(\textcolor{red}{r+\gamma V^{\pi}(s')}\right)\right)^2\right].

对应的梯度为：

\nabla_{\phi} \mathcal{L}(\phi) =\mathbb{E}_{s \sim d^\pi}^{\pi} \left[\left(V_{\phi}(s)-r-\gamma \textcolor{red}{V^{\pi}(s')}\right) \nabla_{\phi}V_{\phi}(s)\right].

这里梯度包含了一个未知量 $V^{\pi}(s')$ . 为了解决这个问题，一个自然的想法是使用当前的 value function $V_{\phi}(s')$ 来进行代替：

g:=\mathbb{E}_{s \sim d^\pi}^{\pi} \left[\left(V_{\phi}(s)-r-\gamma V_{\phi}(s')\right) \nabla_{\phi}V_{\phi}(s)\right].

这里的 $g$ 只沿当前预测求导。若直接把 bootstrap target 写入普通平方损失，autograd 会产生不同的梯度。下面先以一个非终止 transition 展示这个实现陷阱：

pred = V_phi(s0)
target = r + gamma * V_phi(s1)
td_error = pred - target
loss = 0.5 * td_error ** 2
loss.backward()

可以看到，我们实际上求的梯度是：

\begin{aligned} &\nabla_{\phi}\left[\frac{1}{2}\left(V_{\phi}(s) - (r + \gamma V_{\phi}(s'))\right)^2\right] \\ &= (V_{\phi}(s) - (r + \gamma V_{\phi}(s'))) (\nabla_{\phi} V_{\phi}(s) - \gamma\nabla_{\phi} V_{\phi}(s'))\\ &\neq g \end{aligned}

为了解决这个问题，我们可以使用 stop-gradient 技巧来避免 $V_{\phi}(s')$ 参与反向传播，此时目标函数变为：

\mathcal{L}(\phi)=\frac{1}{2}\left(V_{\phi}(s) - (r + \gamma \, \mathrm{sg}[V_{\phi}(s')])\right)^2

其中 $\mathrm{sg}[\cdot]$ 是 stop-gradient operator, 满足：

\mathrm{sg}[x]=x\quad\text{(forward)},\qquad \frac{\partial\,\mathrm{sg}[x]}{\partial x}=0\quad\text{(autograd)}

对应的梯度就是：

\nabla_{\phi}\left[\frac{1}{2}\left(V_{\phi}(s) - (r + \gamma \, \mathrm{sg}[V_{\phi}(s')])\right)^2\right] = (V_{\phi}(s) - (r + \gamma V_{\phi}(s')))\nabla_{\phi} V_{\phi}(s) = g

对应的 Python 代码为：

# Single transition; terminal targets do not bootstrap.
pred = V_phi(s0)
with torch.no_grad():
    target = r if terminated else r + gamma * V_phi(s1)
loss = 0.5 * (pred - target).square()
loss.backward()

最终，正确的 TD 算法如下：

Algorithm: Value function approximation with TD

While not converged:

从固定策略的 rollout 中采样非终止起点 $s_0\sim d^\pi$ ，再采样 $a_0\sim\pi(\cdot\mid s_0)$ 和 $(r_0,s_1)\sim p(\cdot,\cdot\mid s_0,a_0)$ 。
compute TD target $y = \begin{cases} r_0 + \gamma \, \mathrm{sg}[V_{\phi}(s_1)], & \text{if } s_1 \neq \langle\text{term}\rangle \\ r_0, & \text{otherwise} \end{cases}$
$g = (V_{\phi}(s_0) - y) \nabla_{\phi} V_{\phi}(s_0)$ .
Update $\phi$ using $g$ with an optimizer.

上述做法是 semi-gradient method：bootstrap target 依赖当前参数，但更新时不对 target 求导。因此它一般不是某个固定监督损失的完整梯度。若不使用 stop-gradient，得到的是 sampled Bellman-residual loss 的梯度；它对应另一个目标，而且对随机 transition 的 Bellman residual 构造无偏梯度通常还会遇到 double-sampling 问题。

k-step TD

实际上，我们可以进一步推广 TD 到多步场景，注意到：

\begin{aligned} V^{\pi}(s_0) &= \mathbb{E}^{\pi}[r_0 + \gamma V^{\pi}(s_1) \mid s_0] \\ &= \mathbb{E}^{\pi}[r_0 + \gamma \mathbb{E}^{\pi}[r_1 + \gamma V^{\pi}(s_2) \mid s_1] \mid s_0] \\ &= \mathbb{E}^{\pi}[r_0 + \gamma r_1 + \gamma^2 V^{\pi}(s_2) \mid s_0]. \end{aligned}

因此：

V^{\pi}(s_0) = \mathbb{E}^{\pi}[r_0 + \gamma r_1 + \gamma^2 V^{\pi}(s_2) \mid s_0]

重复这个过程 $k$ 次，我们就可以得到 $k$ step TD:

V^{\pi}(s_0) = \mathbb{E}^{\pi}\left[\sum_{i=0}^{k-1} \gamma^i r_i + \gamma^k V^{\pi}(s_k) \mid s_0\right]

基于 k-step transition ，我们可以构建对应的目标函数并应用 stop-gradient：

Algorithm: Value function approximation with k-step TD

while not converged:

从固定策略的 rollout 中采样非终止起点 $s_0\sim d^\pi$ ，set $t=0$ 。
for $t = 0, \ldots, k-1$ $t = 0, \dots, k - 1$ , stopping early if the episode terminates:
- $a_t \sim \pi(\cdot \mid s_t)$
- $(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)$
Let $n\leq k$ be the number of collected transitions and compute $y = \begin{cases} \sum_{t=0}^{n-1} \gamma^t r_t + \gamma^n \, \mathrm{sg}[V_{\phi}(s_n)], & \text{if } s_n \neq \langle\text{term}\rangle, \\ \sum_{t=0}^{n-1} \gamma^t r_t, & \text{otherwise}. \end{cases}$
$g \gets (V_{\phi}(s_0) - y) \nabla_{\phi} V_{\phi}(s_0)$ .
Update $\phi$ using $g$ with an optimizer.

Q-Function Evaluation

$Q^\pi(s,a)$ 与 $V^\pi(s)$ 的区别只是额外固定当前动作。后续仍遵循同一个 $\pi$ ，因此不必重新推导一套训练方法。将网络输入从 $s_t$ 换成 $(s_t,a_t)$ ，MC target 仍是 $G_t$ ；one-step TD target 为

y_t^Q=\begin{cases} r_t,&s_{t+1}\text{ is terminal},\\ r_t+\gamma\,\mathrm{sg}[Q_\phi(s_{t+1},a_{t+1})], \quad a_{t+1}\sim\pi(\cdot\mid s_{t+1}),&\text{otherwise}. \end{cases}

采用相同的 semi-gradient 更新：

\phi\gets\phi-\alpha\bigl(Q_\phi(s_t,a_t)-y_t^Q\bigr)\nabla_\phi Q_\phi(s_t,a_t).

也可以将采样的 $Q_\phi(s_{t+1},a_{t+1})$ 替换为 $\sum_{a'}\pi(a'\mid s_{t+1})Q_\phi(s_{t+1},a')$ ，对下一动作显式求期望。前者是 sampled SARSA-style evaluation，后者是 Expected SARSA-style evaluation；这里只借用其 backup 形式，策略仍固定。 k-step target 同样是累计前 $k$ 步奖励，再接上剩余状态动作的 bootstrap value，并在提前终止时去掉 bootstrap。

这里下一动作来自固定 $\pi$ ，不能随手把它换成 $\arg\max_{a'}Q_\phi(s',a')$ 。一旦把“按当前策略取平均”换成“选择价值最大的动作”，我们就在改变 backup 的目标，进入下一章的 control 问题。

MC v.s. TD

MC 必须等待 episode 结束，然后用真实 return 监督每个已访问状态。对固定状态而言，sample return 是 $V^\pi$ 的无偏估计，但长轨迹中的 variance 可能很高。

TD 使用 $V_\phi(s_{t+1})$ bootstrap，不需要等待完整 episode，通常 variance 更低，但 target 会受到当前 value approximation error 的影响。这里所谓的 “TD 有偏” 主要是指有限训练阶段的 bootstrap target；在满足收敛条件的 tabular on-policy 场景中，TD 仍然可以收敛到真实的 $V^\pi$ .

k-step TD 在两者之间插值：

\text{TD(0)} \xleftarrow{\quad k=1\quad} \text{k-step TD} \xrightarrow{\quad k\geq T-t\quad} \text{MC}.

Reproduce the Evaluation Example

配套代码位于 ToyLLM 项目。在仓库根目录运行：

uv sync
uv run python scripts/run_tutorial_control.py --episodes 10000 --seeds 5 --output outputs/tutorial_control.json

脚本显式使用 failure_reward=0.0, strip_eos=True，其中代码的 <BOS> 对应本文的固定 prompt 初始状态 $x$ ，<EOS> 对应数学记号中的终止 token。 hand_example 同时报告 backward evaluation 与 matrix solve 的精确值；两者都应得到初始 value $0.15$ 。 evaluation 部分按 seed 报告 MC/TD 的初始状态估计、初始状态绝对误差和全状态 MAE，整个过程中固定策略的动作概率不变。 TD 使用常数步长 $0.1$ ，所以有限步结果可能波动，不应要求每个 seed 都精确等于解析值。

现有 make_bow_feature_extractor 可用于线性函数逼近实验，但 bag-of-tokens 不保留顺序：例如 prefix A B 和 B A 会有相同表示。在更长的 exact-match 任务中，它们可能有不同的真实 value，因此该表示可能无法拟合所有状态。函数逼近提供共享能力，也会引入表示误差。

Takeaway

Policy evaluation 始终固定 $\pi$ ；更新的是 $V^\pi$ 或 $Q^\pi$ 的估计。
完整模型允许精确求解，MC/TD 则用 rollout 替代对整个环境的枚举。
MC 使用完整 return；TD 使用 bootstrap；k-step TD 在等待奖励和依赖估计之间提供选择。
Function approximation 可以让不同 prefix 共享表示，但不保证自动解决稀疏奖励或状态覆盖问题。
当 $\gamma=1$ 且只有 terminal binary reward 时， $V^\pi$ 是当前策略最终成功的概率；有 discount 或其他奖励项时，应解释为相应的期望回报。

回到本章开头，我们现在可以估计出 $V^\pi(x)=0.15$ 和 $Q^\pi(x,B)=0.5$ ，但策略依旧以 $0.6$ 的概率选择无法成功的首 token $A$ 。下一章的问题因此很自然：既然已经知道动作的好坏，怎样利用这些价值改进策略？

Value Based Methods

上一章的 Policy Evaluation 固定策略 $\pi$ ，研究如何估计 $V^\pi$ 或 $Q^\pi$ 。本章转向 control：如何利用价值估计，得到更好的策略？

Evaluation 回答“按当前策略行动，未来能得到多少奖励”；control 则进一步问“知道各个动作的价值后，应该怎样改变行动规则”。 Value-based methods 根据 value/Q-function 选择动作，由价值估计间接决定策略。

本章不再重复 MC、TD 和函数逼近的推导，而是沿着四个问题展开：

已经知道 $Q^\pi$ ，如何改进 $\pi$ ？——policy improvement 与 policy iteration。
每次改进前，必须把价值完全算准确吗？——value iteration。
只有采样数据、没有完整模型时，如何改进策略？——SARSA 与 Q-learning。
Q-table 太大时，如何训练神经网络来做 control？——DQN。

Policy Improvement

固定策略的价值满足

V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a).

这个平均值不超过最好的动作价值。因此，一个自然的改进是让新策略选择当前 $Q^\pi$ 最大的动作：

\pi_{\mathrm{new}}(s)\in\arg\max_a Q^\pi(s,a),\qquad Q^\pi(s,\pi_{\mathrm{new}}(s))\geq V^\pi(s).

这里有一个需要解释的跳跃： $Q^\pi$ 假设当前动作之后继续遵循旧策略 $\pi$ ，但新策略会在后续每个状态也做 greedy improvement。这样反复改变未来的行为，还能保证 value 不下降吗？

Theorem: Policy Improvement

在有限状态、有限动作、有界奖励且 $0<\gamma<1$ 的 MDP 中，若策略 $\pi'$ 在每个状态满足

\sum_a\pi'(a\mid s)Q^\pi(s,a)\geq V^\pi(s),

则 $V^{\pi'}(s)\geq V^\pi(s)$ 对所有状态成立。基于精确 $Q^\pi$ 的 greedy policy 是满足该条件的一种选择。

Proof: Repeated improvement of the continuation

由条件可得 $\mathcal T^{\pi'}V^\pi\geq V^\pi$ 。利用 Bellman operator 的单调性，

V^\pi\leq\mathcal T^{\pi'}V^\pi \leq(\mathcal T^{\pi'})^2V^\pi \leq\cdots\longrightarrow V^{\pi'}.

最后一步使用固定策略 Bellman operator 的 contraction 性质。因此，把未来更多步骤替换成 $\pi'$ 不会降低 value。对于包含时间信息的 finite-horizon MDP， $\gamma=1$ 时可用有限步 backward induction 得到同样结论。

ToyLLM: From a Better First Token to a Better Policy

继续使用上一章的两步 ToyLLM：target 为 $BA$ ， $\gamma=1$ ，旧策略在初始状态选择 $B$ 的概率为 $0.3$ ，在 prefix $B$ 后选择 $A$ 的概率为 $0.5$ 。于是

V^\pi(x)=0.15,\qquad Q^\pi(x,B)=0.5, \qquad Q^\pi(x,A)=Q^\pi(x,\langle\mathrm{eos}\rangle)=0.

如果只把第一个动作改成必选 $B$ ，随后仍用旧策略，则成功概率从 $0.15$ 变为 $0.5$ 。如果在每个 prefix 都对 $Q^\pi$ 做 greedy improvement，那么在 prefix $B$ 后也会必选 $A$ ，因为这个终止动作的 Q-value 为 1，其他动作为 0。因此新策略确定性地生成 $BA$ ，有

V^{\pi_{\mathrm{new}}}(x)=1.

这个例子区分了三个量：旧策略的 value 为 $0.15$ ，只改当前动作时的 value 为 $0.5$ ，改进整条后续策略后的 value 为 $1$ 。前两者属于 evaluation，最后一步才使用价值信息完成 control。这里一步就得到最优策略是这个小例子的性质，一般问题需要多次迭代。

Policy Iteration Methods

改进策略后，旧的 $Q^\pi$ 不再描述新的后续行为。因此我们重新评估新策略，再继续改进：

\pi_k\xrightarrow{\text{evaluation}}V^{\pi_k},Q^{\pi_k} \xrightarrow{\text{improvement}}\pi_{k+1}.

Algorithm: Exact Policy Iteration

Initialize a deterministic policy $\pi_0$ .
For $k=0,1,\ldots$ $k = 0, 1, \dots$ :
- Evaluation: compute $V^{\pi_k}$ with the known environment model, then compute $Q^{\pi_k}(s,a)=\mathbb E[r+\gamma V^{\pi_k}(s')\mid s,a].$
- Improvement: for every non-terminal state, $\pi_{k+1}(s)\in\arg\max_a Q^{\pi_k}(s,a).$ Keep the old action if it is already a maximizer; otherwise use a fixed tie-breaking rule.
- Stop if $\pi_{k+1}=\pi_k$ .
Return $\pi_k$ .

在上述 finite discounted MDP 条件下，policy improvement 保证 value 单调不降。若策略尚未最优，至少一个状态的 value 严格提高；deterministic policies 的数量有限，因此精确 policy iteration 在有限次改进后到达最优策略。停止时 $V^{\pi_k}=\mathcal T^*V^{\pi_k}$ ，也就是满足 Bellman optimality equation。

这一保证依赖精确 evaluation。用有限样本或 neural network 得到的 $\hat Q$ 可能排错动作顺序，greedy improvement 不再自动保证真实 return 提高。实际 control 算法必须同时面对价值估计误差和探索不足。

Value Iteration

Policy iteration 每轮都要完成一次 evaluation，代价可能很大。能不能只做少量 backup，就立即改进动作选择？

先比较两个更新：

\begin{aligned} (\mathcal T^\pi V_k)(s) &=\sum_a\pi(a\mid s)\mathbb E[r+\gamma V_k(s')\mid s,a],\\ (\mathcal T^*V_k)(s) &=\max_a\mathbb E[r+\gamma V_k(s')\mid s,a]. \end{aligned}

第一行对动作按固定策略取平均，目标是 $V^\pi$ ；第二行在每次 backup 中选择最佳动作，目标是 $V^*$ 。令 $V_{k+1}=\mathcal T^*V_k$ ，就得到 value iteration。这可以理解为把 evaluation 和 improvement 紧密交替进行；中间的 $V_k$ 不必是某个策略已经评估准确的 value。

Algorithm: Value Iteration with a Known Model

Initialize $V_0(s)$ for non-terminal states; set terminal value to zero.
For $k=0,1,\ldots$ $k = 0, 1, \dots$ :
- For every non-terminal state, compute a synchronous backup: $V_{k+1}(s)=\max_a\mathbb E[r+\gamma V_k(s')\mid s,a].$
- Stop when $\|V_{k+1}-V_k\|_\infty$ is below a chosen tolerance.
Extract a greedy policy using the final value estimate: $\hat\pi(s)\in\arg\max_a\mathbb E[r+\gamma V_{k+1}(s')\mid s,a].$

由 Bellman Optimality Equation， $0<\gamma<1$ 时有

\|V_{k+1}-V^*\|_\infty\leq\gamma\|V_k-V^*\|_\infty,

因此迭代收敛到 $V^*$ 。有限误差下提取的是近似策略；达到不动点时得到最优策略。对 ToyLLM，若从零初始化并做同步更新，第一轮先学到 prefix $B$ 的最优 value 为 1，第二轮才把这一价值传到初始状态。这也是 $\gamma=1$ 、有限生成树下 backward induction 的直观过程。

同样可以直接迭代 Q-function：

Q_{k+1}(s,a)=\mathbb E\left[r+\gamma\max_{a'}Q_k(s',a')\mid s,a\right],

其中 terminal 的 bootstrap 项为零。这个形式已经非常接近 Q-learning；剩下的问题是如何用样本替代对环境的期望。

From Evaluation to TD Control

完整模型通常不可用，但我们可以执行动作，收集 $(s,a,r,s',d)$ ，其中 $d$ 表示本次 transition 是否终止。上一章已经介绍 TD 更新，本节沿用

Q(s,a)\gets Q(s,a)+\alpha\bigl(y-Q(s,a)\bigr).

新增的问题是：target $y$ 应该评估哪一种后续行为？ 此外，若总选择当前估计最大的动作，未尝试的好动作可能永远无法被发现。一种简单的 behavior policy 是 $\epsilon$ -greedy：以 $1-\epsilon$ 的概率选当前 greedy action，以 $\epsilon$ 的概率在动作空间均匀探索。

SARSA

SARSA 从当前 behavior policy 采样下一动作 $a'$ ，并用它构造 target：

y_{\mathrm{SARSA}}=\begin{cases} r,&d=1,\\ r+\gamma Q(s',a'),\quad a'\sim\pi_k(\cdot\mid s'),&d=0. \end{cases}

如果 $\pi_k$ 固定，这就是上一章的 Q-function evaluation。作为 control 算法，我们根据更新后的 Q-table 不断调整 $\epsilon$ -greedy 策略，使高价值动作更容易被选择。因此 SARSA 将 evaluation 与 improvement 交织在每次交互中，而不是等待完整 evaluation 收敛。它是 on-policy 的，因为 target 使用的下一动作正是数据采集策略选出的动作。

Algorithm: SARSA Control

Initialize Q-table and exploration schedule $\epsilon_k$ .
For each episode:
- Sample $s\sim p_0$ and $a\sim\epsilon_k\text{-greedy}(Q(s,\cdot))$ .
- Repeat:
  1. Execute $a$ , observe $(r,s',d)$ .
  2. If terminal, set $y=r$ ; otherwise sample $a'\sim\epsilon_k\text{-greedy}(Q(s',\cdot))$ and set $y=r+\gamma Q(s',a')$ .
  3. Update $Q(s,a)\gets Q(s,a)+\alpha(y-Q(s,a))$ .
  4. If terminal, end the episode; otherwise set $(s,a)\gets(s',a')$ .

算法名称来自更新所用的五元组 $(S,A,R,S',A')$ 。 $\epsilon$ -greedy 是这里选择的探索方式，不是 SARSA 的定义要求。固定的非零 $\epsilon$ 会持续影响它所评估的后续行为；不能因此直接宣称它学到的是完全 greedy 的最优策略。

Q-Learning (Off-Policy TD Control)

另一种选择是：采集数据时继续探索，但 target 假设下一步选当前估计中价值最大的动作：

y_{\mathrm{Q}}=\begin{cases} r,&d=1,\\ r+\gamma\max_{a'}Q(s',a'),&d=0. \end{cases}

这就是 Q-learning，它是 Q-value iteration 的 sampled backup。给定当前 Q-table 和 $(s,a)$ ，target 对环境采样取期望后等于 Bellman optimality backup；它不是已知的 $Q^*(s,a)$ ，也不是当前 behavior policy 的 $Q^\pi(s,a)$ 的直接样本。

Algorithm: Q-Learning Control

Initialize Q-table.
For each episode:
- Sample $s\sim p_0$ .
- Repeat:
  1. Select $a$ with an exploratory behavior policy, such as $\epsilon$ -greedy with respect to Q.
  2. Execute $a$ , observe $(r,s',d)$ .
  3. Set $y=r$ if terminal; otherwise set $y=r+\gamma\max_{a'}Q(s',a')$ .
  4. Update $Q(s,a)\gets Q(s,a)+\alpha(y-Q(s,a))$ .
  5. If terminal, end the episode; otherwise set $s\gets s'$ .

Q-learning 是 off-policy 的，因为 behavior policy 可以探索，而 target 对应 greedy 的后续动作。这不意味着数据覆盖不重要：有限 discounted MDP 中的 tabular 收敛结论仍要求所有状态动作对被充分访问、有界奖励以及每个状态动作对的步长满足随机逼近条件。一份缺少关键动作的固定数据集，并不能自动恢复 $Q^*$ 。

The Same Transition, Different Targets

考虑 ToyLLM 中首 token 为 $B$ 的 transition：当前 reward 为 0，下一状态是 prefix $B$ 。假设当前 Q-table 在该 prefix 上对动作 $A$ 的估计为 $0.8$ ，对 $B$ 和 <eos> 的估计均为 0，而 behavior policy 恰好探索并选择了 <eos>。当 $\gamma=1$ 时，

y_{\mathrm{SARSA}}=0+Q((x,B),\langle\mathrm{eos}\rangle)=0, \qquad y_{\mathrm{Q}}=0+\max_{a'}Q((x,B),a')=0.8.

二者对同一条 transition 给出不同 target，因为它们对未来行为的假设不同。 SARSA 的这个样本计入了探索导致的失败；Q-learning 则沿当前估计中的最佳后续动作传播价值，即使这次实际上没有选它。这里 $0.8$ 是当前估计，并不是环境给出的额外奖励。

Deep Q-Network (DQN)

当 Q-table 太大时，我们用 $Q_\phi(s,a)$ 表示 Q-function。函数逼近和 semi-gradient 的推导见上一章，这里的变化是训练 target 使用 $\max_{a'}Q(s',a')$ ，朝 optimal Q-function 推进。

但是，将 tabular Q-learning 换成 neural network，并不会保留原来的收敛保证。一个参数更新可能同时改变许多状态的预测，bootstrap 又依赖这些预测；加上 off-policy 数据，训练可能不稳定。 DQN 引入两项重要机制：

Experience replay：将 transitions 存入 buffer，再随机抽取 minibatch，减弱相邻样本的相关性并复用历史数据。它不能补出从未采集过的动作结果。
Target network：用暂时固定的 $Q_{\phi^-}$ 构造 bootstrap target，隔一段时间才从 $\phi$ 复制参数，减缓 target 随训练移动的速度。它改善稳定性，但不构成一般的收敛保证。

对 replay buffer $\mathcal B$ 中的一条 transition，定义

y=\begin{cases} r,&d=1,\\ r+\gamma\max_{a'}Q_{\phi^-}(s',a'),&d=0. \end{cases}

训练时将 target 当作常数：

\mathcal L(\phi)=\mathbb E_{(s,a,r,s',d)\sim\mathcal B} \left[\frac12\left(Q_\phi(s,a)-\mathrm{sg}[y]\right)^2\right].

下面展示一个 minibatch 的更新，所有被选中的 Q-value 和 target 都保持为 shape [B]：

# actions: int64 [B]; rewards: float [B]; terminated: bool [B]
# Q_phi(states) and Q_target(next_states): [B, num_actions]
q_values = Q_phi(states).gather(1, actions[:, None]).squeeze(1)

with torch.no_grad():
    next_values = Q_target(next_states).max(dim=1).values
    next_values = next_values.masked_fill(terminated, 0.0)
    targets = rewards + gamma * next_values

loss = 0.5 * (q_values - targets).square().mean()
optimizer.zero_grad()
loss.backward()
optimizer.step()

这里 terminated 表示 MDP 真正终止。ToyLLM 的 EOS 和定义中的最大生成长度都属于终止；若只是外部采样器暂时截断一个仍会继续的任务，则需要另外处理 bootstrap。 terminal 的 next_states 应使用网络可接受的占位输入，其预测随后被 mask 掉。

Algorithm: DQN Training Loop

Initialize $Q_\phi$ , copy $\phi^-\gets\phi$ , and create replay buffer $\mathcal B$ .
Collect transitions with an $\epsilon$ -greedy policy derived from $Q_\phi$ ; store $(s,a,r,s',d)$ , resetting the environment after termination.
Once enough data are available, sample minibatches from $\mathcal B$ and update $\phi$ using the loss above.
Every $C$ optimizer steps, copy $\phi^-\gets\phi$ .
Repeat collection and training; evaluate the greedy policy separately from the exploratory behavior policy.

注意 target network 和 stop-gradient 的作用不同：前者控制 target 多久变化一次，后者控制本次更新的 梯度沿哪条路径传播。

Why LLMs Usually Do Not Use DQN

ToyLLM 展示了 value-based control 确实可以改进 token generation，但不能据此认为 vanilla DQN 就适合真实 LLM post-training。更关键的区别是策略的表示与学习目标：

预训练 LLM 已经提供了 $\pi_\theta(y_t\mid x,y_{<t})$ 。直接优化这个分布可以沿用已有的生成能力；从 Q-function 提取 greedy policy 需要另一套价值学习和动作选择机制。
Vanilla DQN 的 greedy rule 选择最大 Q-value 的动作，并不直接学习希望保留和调整的完整生成分布。价值方法也可以扩展到随机或正则化策略，但需要额外设计。
巨大的 prefix space、稀疏 terminal reward 和对未充分访问动作的 Q 估计，使可靠的 control 很困难。词表大本身不是“不适用”的证明：policy model 同样需要处理整个词表。
在 ToyLLM 中，精确 Q 可以指导 greedy improvement；在真实任务中，错误的高 Q 估计也可能被 $\max$ 放大。模型必须有足够的探索与数据支持这些价值判断。

因此，学习本章的目的不是把 DQN 当作 LLM 训练配方，而是理解 评价策略与改进策略是两个不同的任务。下一章的 Policy Based Methods 将直接更新参数化策略；之后的 actor-critic 会重新使用 policy evaluation，让 critic 评估当前 actor 的回报，并帮助 actor 更新。其中 critic 通常估计 $V^{\pi_\theta}$ 或 $Q^{\pi_\theta}$ ，而不是独立求解 $Q^*$ 。

Reproduce the Control Example

与上一章共用 scripts/run_tutorial_control.py。同一份 JSON 的 hand_example 应给出：policy iteration 的初始状态 value 从 $0.15$ 到 $1$ ，从零初始化的同步 value iteration 则依次为 $0,0,1$ 。前者使用完整的策略评估结果再改进；后者每轮只做一次 optimality backup。

control 部分分别运行 SARSA 和 Q-learning，并把以下指标分开报告：

学到的 $\max_a Q(x,a)$ ，它仍然是一个估计。
对学到的 greedy policy 做精确 evaluation 得到的成功概率。
对保留 $\epsilon=0.2$ 探索的策略做精确 evaluation 得到的成功概率。
最后 1,000 个训练 episode 的经验成功率。

在这个两步例子中，如果 greedy policy 已经确定性地生成 $BA$ ，它的成功率为 1；但每步在三个动作上保留 $\epsilon=0.2$ 的均匀探索后，成功率为

\left(1-0.2+\frac{0.2}{3}\right)^2=\frac{169}{225}\approx0.7511.

因此训练期间仍有失败 episode，并不说明 greedy policy 没有学会任务。同样，SARSA 的 estimated Q 与 Q-learning 不完全一致，也可能反映了二者不同的后续行为目标，而不一定是实现错误。精确 evaluation 只用于这个可枚举小环境中的诊断；采样控制算法本身不调用精确模型。

Takeaway

Value-based control 用价值信息改变动作选择；仅训练一个 value network 仍可能只是 evaluation。
Policy iteration 交替执行 evaluation 和 improvement；value iteration 在每次 optimality backup 中交织二者。
SARSA 的 target 跟随 behavior policy 的下一动作，Q-learning 的 target 使用 greedy 下一动作。
DQN 将 Q-learning 与函数逼近结合，replay buffer 和 target network 用于缓解训练不稳定。
对 LLM 而言，这些方法建立了 control 的共同语言，后续我们会把策略改进交给显式的 autoregressive policy。

Policy Based Methods

Value-based methods 先学习 $Q^*$ ，再通过 $\arg\max_a Q^*(s,a)$ 间接得到策略。对 LLM 而言，我们已经有一个参数化的 autoregressive policy $\pi_\theta(y_t\mid x,y_{<t})$ , 因此更自然的选择是直接调整 $\theta$ ，提高高回报 response 的生成概率。这就是 policy-based methods 的核心思想。

使用 policy $\pi_\theta$ 生成 trajectory, 通过 trajectory reward 构造 gradient estimator，再直接改进当前策略 $\pi_\theta$ .

根据采样策略 (behavior policy) 的不同，policy-based methods 一般会被分为两类：

on-policy: 采集数据的 policy 和训练更新的 policy 一致
off-policy: 采集数据的 policy 和训练更新的 policy 不一致

这两者的核心区别在于：我们更新模型所使用的数据是否由当前模型产生？如果是，则说明算法是 On-policy, 反之则说明是 Off-policy.

on-policy 和 off-policy 对比如下表所示

Category	on-policy	off-policy
examples	PPO, GRPO	DQN, DDPG
sampled from	current policy	behavior policy
data exploration	controlled by current policy	controlled by behavior policy
infra efficiency	low (needs to generate new sample)	high
training stability	sensitive to policy update size	sensitive to distribution shift
compute cost	high	low
best for	fresh rollout and direct policy optimization	reusing past or external data

目前，主流针对 LLM 的 RL 算法基本都是

Objective

我们的目标与前面一致，仍然是最大化 return, 问题形式为

\max_{\pi}\mathcal{J}(\theta)=\mathbb{E}_{\tau\sim\pi_\theta}\left[G_0(\tau)\right]

Policy Gradient Theorem

我们先来求解目标函数的梯度，梯度由下面的 policy gradient theorem 给出。

Theorem: Policy Gradient Theorem

目标函数最大化 return 的梯度为

\nabla_\theta \mathcal{J}(\theta) = \mathbb{E}_{\tau\sim\pi_\theta}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)G_0(\tau)\right]

Proof:

由 trajectory definition, trajectory $\tau$ 的概率分布可以写为

p_\theta(\tau) = p_0(s_0)\prod_{t=0}^{T-1} p(r_t,s_{t+1}\mid s_t,a_t)\pi_\theta(a_t\mid s_t)

对 $p_\theta(\tau)$ 求梯度得到

\begin{aligned} \nabla_\theta p_\theta(\tau)&=p_\theta(\tau)\nabla_\theta \log p_\theta(\tau)\\ &= p_\theta(\tau)\nabla_\theta \log \left[p_0(s_0)\prod_{t=0}^{T-1} p(r_t,s_{t+1}\mid s_t,a_t)\pi_\theta(a_t\mid s_t)\right]\\ &= p_\theta(\tau)\sum_{t=0}^{T-1}\log\pi_\theta(a_t\mid s_t) \end{aligned}

这样，目标函数的梯度为

\begin{aligned} \nabla_\theta \mathcal{J}(\theta)&=\nabla_\theta\mathbb{E}_{\tau\sim\pi_\theta}\left[G_0(\tau)\right]\\ &= \sum_\tau G_0(\tau)\nabla_\theta p_\theta(\tau)\\ &= \sum_\tau G_0(\tau)p_\theta(\tau)\sum_{t=0}^{T-1}\log\pi_\theta(a_t\mid s_t) \\ &= \mathbb{E}_{\tau\sim\pi_\theta}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)G_0(\tau)\right] \end{aligned}

证毕。

注意 policy gradient theorem 将梯度也写成了期望的形式，这方面我们使用 MC 方法来进行估计和优化。

Vanilla Policy Gradient Methods

接下来，我们介绍最简单的 policy gradient methods, 令

\hat{g} := \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)G_0(\tau)

由 policy gradient theorem, 我们知道 $\hat{g}$ 是 $\nabla_\theta \mathcal{J}(\theta)$ 的一个无偏估计。

基于 MC 思想，我们可以得到最简单的 policy gradient algorithm, 也就是 REINFORCE 算法

Algorithm: Policy Gradient with MC (REINFORCE)

Initialize: policy parameters $\theta_0$ .

For $k=0,1,\dots$ :

Sample $M$ trajectories $\{\tau_i\}$ according to policy $\pi_{\theta_k}$ .
Estimate the gradient via MC: $\hat{g}=\frac{1}{M}\sum_{i=1}^M\sum_{t=0}^{T_i-1}\nabla_\theta\log\pi_{\theta_k}(a_t\mid s_t)G_0(\tau_i)$
Update $\theta_k$ using $\hat{g}$ with an optimizer.

Return $\pi_{\theta_k}$

Variance Reduction

虽然 $g$ 是 $\nabla_\theta \mathcal{J}(\theta)$ 的一个无偏估计，但是使用 $g$ 作为估计会出现比较大的方差，TODO

因此我们本节主要介绍如何减少 $g$ 作为估计的方差，即 variance reduction.

我们首先介绍 policy gradient 的 baseline invariance 性质。

Baseline Invariance

Proposition: Baseline Invariance of Policy Gradient

针对 policy gradient theorem, 我们有如下等式

\begin{aligned} &\mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)\sum_{t=0}^{T-1}r(s_t)\right] \\ =& \mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)\left(\sum_{t=0}^{T-1}r(s_t)-b(s_t)\right)\right] \end{aligned}

其中 $b(s_t)$ 是一个仅与状态有关的函数或者常数，我们将其称为 baseline.

Proof:

我们证明

\mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[b(s_t)\nabla_\theta \log p_\theta(a_t\mid s_t)\right]=0

注意到

\begin{aligned} \mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[b(s_t)\nabla_\theta \log p_\theta(a_t\mid s_t)\right] &= \mathbb{E}_{s_0\sim p_0}\left[b(s_t)\mathbb{E}_{a_t\sim\pi_\theta(\cdot\mid s_t)}\left[\nabla_\theta \log \pi_\theta(a_t\mid s_t)\right]\right]\\ &= \mathbb{E}_{s_0\sim p_0}\left[b(s_t)\sum_{a}\nabla_\theta \pi_\theta(a\mid s)\right]\\ &= \mathbb{E}_{s_0\sim p_0}\left[b(s_t)\nabla_\theta \sum_{a}\pi_\theta(a\mid s)\right]\\ &= \mathbb{E}_{s_0\sim p_0}\left[b(s_t)\nabla_\theta 1\right]\\ &=0 \end{aligned}

因此，policy gradient 满足 baseline invariance property.

另一方面，Rao–Blackwell Theorem 说明了我们可以通过构造一个新的无偏估计，这个新的无偏估计相对于原始的无偏估计，有更小的方差。

Theorem: Rao-Blackwell Theorem

令 $X$ 和 $Y$ 为随机变量，令 $\hat{I}_1(X,Y)$ 为 $I$ 的一个无偏估计，即

I = \mathbb{E}_{XY}[\hat{I}_1(XY)]

令 $\hat{I}_2(Y)=\mathbb{E}_{X\mid Y}[\hat{I}_1(X,Y)\mid Y]$ , 则 $\hat{I}_2$ 也是 $I$ 的一个无偏估计，并且

\mathrm{var}[\hat{I}_2]\leq\mathrm{var}[\hat{I}_1]

$\hat{I}_2$ 被称为 $\hat{I}_1(X,Y)$ 的Rao-Blackwellized estimator.

Proof:

由 Expectation 中的 law of total expectation, 我们有

\mathbb{E}_{XY}[\hat{I}_2(XY) ]=\mathbb{E}_{Y}[\mathbb{E}_{X\mid Y}[\hat{I}_1(X,Y)\mid Y]]=\mathbb{E}_{XY}[\hat{I}_1(XY) ]=I

其次，我们有

\begin{align} \mathrm{var}[\hat{I}_2]&=\mathbb{E}_{Y}[(I-\hat{I}_2(Y))^2]\\ &= \mathbb{E}_{Y}[\left(\mathbb{E}_{X\mid Y}\left[I-\hat{I}_1(X,Y)\mid Y\right]\right)^2]\\ &\leq\mathbb{E}_{Y}[\left(\mathbb{E}_{X\mid Y}\left[(I-\hat{I}_1(X,Y))^2\mid Y\right]\right)]\\ &= \mathbb{E}_{Y}[(I-\hat{I}_1(X,Y))^2]\\ &=\mathrm{var}[\hat{I}_1] \end{align}

这里不等式使用了 Jensen’s inequality. 证毕。 $\blacksquare$

基于 Rao–Blackwell Theorem, 我们可以通过改变 $b(s_t)$ 来调整 policy gradient 的 variance.

Reward to Go

Reward to go 的基本思想为

对于时刻 $t$ , 过去的轨迹 $s_0,r_0,\dots,r_{t - 1}$ 不应该被考虑，因为它们都已经固定了,加入它们会产生额外的 variance, 此时，我们对应的 $b(s_t)$ 定义为

其定义的 baseline 如下所示

b(s_t) = \sum_{k=0}^{t}\gamma^k r_k

此时，我们的 policy gradient 为

\nabla_\theta \mathcal{J}(\theta)=\mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)\sum_{k=t}^{T-1}r(s_{k})\right]

对应的 REINFORCE 算法改进版本为

Algorithm: Policy Gradient with MC and reward to go (REINFORCE)

Initialize policy parameters $\theta_0$ .
for $k=0,1,\dots$ $k = 0, 1, \dots$ :
- Sample $M$ trajectories $\{\tau_i\}$ according to policy $\pi_{\theta_k}$ .
- Estimate the gradient via MC: $\hat{g}=\frac{1}{M}\sum_{i=1}^M\nabla_\theta\log\pi_{\theta_k}(a_t\mid s_t)\gamma^tG_t(\tau_i)$
- Update $\theta_k$ using $\hat{g}$ with an optimizer.

Optimal Baseline

我们可以从理论上推导出最优 baseline.

Lemma:

令 $s$ 和 $a$ 为随机变量， $w(s,a)$ , $Q(s,a)$ , $b(s)$ 为函数，则

b^* = \arg\min_{b(\cdot)} \mathbb{E}_{a,s}\left[w^2(s,a)\left(Q(s,a)-b(s)\right)^2\right]

其中

b^*(s) = \frac{\mathbb{E}_{a\mid s}\left[w^2(s,a)Q(s,a)\mid s\right]}{\mathbb{E}_{a\mid s}\left[w^2(s,a)\mid s\right]}

Proof:

对目标函数进行展开得到

\begin{aligned} \mathbb{E}_{a,s}\left[w^2(s,a)\left(Q(s,a)-b(s)\right)^2\right]&= \mathbb{E}_{a,s}\left[w^2(s,a)\left(Q(s,a)-b^*(s)+b^*(s)-b(s)\right)^2\right]\\ &= \mathbb{E}_{a,s}\left[w^2(s,a)\left(Q(s,a)-b^*(s)\right)^2\right]+\mathbb{E}_{a,s}\left[w^2(s,a)\left(b^*(s)-b(s)\right)^2\right]\\ &+2\mathbb{E}_{a,s}\left[w^2(s,a)\left(Q(s,a)-b^*(s)\right)\left(b^*(s)-b(s)\right)\right]\\ &= \mathbb{E}_{a,s}\left[w^2(s,a)\left(Q(s,a)-b^*(s)\right)^2\right]+\mathbb{E}_{a,s}\left[w^2(s,a)\left(b^*(s)-b(s)\right)^2\right]\\ &\geq \mathbb{E}_{a,s}\left[w^2(s,a)\left(Q(s,a)-b^*(s)\right)^2\right] \end{aligned}

其中第三个等式用到了

\begin{aligned} \mathbb{E}_{a,s}\left[w^2(s,a)\left(Q(s,a)-b^*(s)\right)\left(b^*(s)-b(s)\right)\right]&= \mathbb{E}_{s}\left[\mathbb{E}_{a\mid s}\left[w^2(s,a)\left(Q(s,a)-b^*(s)\right)\left(b^*(s)-b(s)\right)\right]\mid s\right]\\ &= \mathbb{E}_{s}\left[\left(\mathbb{E}_{a\mid s}\left[w^2(s,a)Q(s,a)\mid s\right] - \mathbb{E}_{a\mid s}\left[w^2(s,a)\mid s\right]b^*(s)\right)\left(b^*(s)-b(s)\right)\right]\\ &=0 \end{aligned}

证毕。 $\blacksquare$

基于上述引理，我们可以得到关于 baseline invariance 中的最优 baseline:

b^*(s) =\frac{\mathbb{E}_{a_t\sim\pi_\theta(\cdot\mid s_t)}\left[(\nabla_\theta\log\pi_\theta(a_t\mid s_t))^2Q^{\pi_\theta}(s,a)\mid s\right]}{\mathbb{E}_{a_t\sim\pi_\theta(\cdot\mid s_t)}\left[\nabla_\theta\log\pi_\theta(a_t\mid s_t))^2\mid s\right]}

Advantage

理论上我们可以使用 $b^*(s_t)$ 作为 baseline,但是实际上由于其表达式太复杂，我们一般使用其简化版本。简化版本移除了 $b^*(s)$ 中的 $\nabla_\theta\log\pi_\theta(a_t\mid s_t)$ , 这样我们的估计就是

b(s) = \frac{\mathbb{E}_{a_t\sim\pi_\theta(\cdot\mid s_t)}\left[Q^{\pi_\theta}(s,a)\mid s\right]}{\mathbb{E}_{a_t\sim\pi_\theta(\cdot\mid s_t)}\left[1\mid s\right]} = V^{\pi_\theta}(s)

$b(s)=V^{\pi_\theta}(s)$ 并不是最优 baseline, 但是其性质比较好。

我们将 $b(s)=V^{\pi_\theta}(s)$ 带入到目标函数中就得到经典的 policy gradient 表达式

\nabla_\theta \mathcal{J}(\theta)=\mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)\left(Q^{\pi_\theta}(s_t,a_t)-V^{\pi_\theta}(s_t)\right)\right]

我们定义

\boxed{ A^{\pi_\theta}(s_t,a_t) := Q^{\pi_\theta}(s_t,a_t)-V^{\pi_\theta}(s_t) }

为 $a_t$ 在 $s_t$ 处的 advantage. 注意到 $V^{\pi_\theta}(s_t)$ 评估了当前状态下沿着策略 $\pi_\theta$ 所能够获得的 discounted return, 因此 advantage 说明了 action $a_t$ 对于 $\pi_\theta$ 的平均好坏程度：

如果 $A^{\pi_\theta}(s_t,a_t) >0$ , 则说明 $a_t$ （平均意义下）相对于 $\pi_\theta$ 来说是一个更好的 action
反之如果 $A^{\pi_\theta}(s_t,a_t) <0$ , 则说明 $a_t$ （平均意义下）相对于 $\pi_\theta$ 来说是一个更坏的 action

实际场景下，由于 $V^{\pi_\theta}(s_t)$ 未知，使用前面的 value iteration 方法，我们可以使用估计

\hat{A}^{\pi_\theta}(s_t,a_t) := Q^{\pi_\theta}(s_t,a_t)-V^{\phi}(s_t)

来代替。

对于最优策略 $\pi^*$ ，我们有

A^{\pi^*}(s_t,a_t) := Q^{\pi^*}(s_t,a_t)-V^{\pi^*}(s_t)\leq 0

证明也很简单，注意到 $V^{\pi^*}(s_t)=\max_{a}Q^{\pi^*}(s_t,a_t)$ 即可。

最后，我们的 REINFORCE 算法改进如下

Algorithm: Policy Gradient with MC and value function (REINFORCE)

Initialize policy parameters $\theta_0$ .
for $k=0,1,\dots$ $k = 0, 1, \dots$ :
- Sample $M$ trajectories $\{\tau_i\}$ according to policy $\pi_{\theta_k}$ .
- Estimate the gradient via MC: $\hat{g}=\frac{1}{M}\sum_{i=1}^M\nabla_\theta\log\pi_{\theta_k}(a_t\mid s_t)\gamma^t(Q^{\pi_\theta}(s_t,a_t)-V^{\phi}(s_t))$
- Update $\theta_k$ using $\hat{g}$ with an optimizer.

Overview

最后，我们把前面的 basline 使用统一的公式进行表示，记

\nabla_\theta \mathcal{J}(\theta)=\mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[\Psi(\tau)\nabla_\theta \log p_\theta(\tau)\right]=\mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[\sum_{t=0}^T\Psi_t(\tau)\nabla_\theta \log p_\theta(\tau)\right]

则不同的方法对应的表达式如下

Method	Expression
Vallinna	$\Psi_t(\tau)=G_0(\tau)=Q^\pi(s_t,a_t)$
Return to go	$\Psi_t(\tau)=\sum_{k=t}^T\gamma^{k-t}r_k$
Advantage	$\Psi_t(\tau)=A^{\pi}(s_t,a_t)=Q^\pi(s_t,a_t)-V^\pi(s_t)$

Experiments

TODO

Value-Based Methods v.s. Policy-Based Methods

	Value-Based	Policy-Based
核心思想	学习 value/Q-function, 间接得到策略	直接优化策略参数
代表算法	DQN, Double DQN, Dueling DQN	REINFORCE, PPO, TRPO
策略形式	隐式 (从 Q 值推导)	显式 (参数化策略)
适用场景	离散动作空间	离散/连续动作空间
收敛性	较好	需要基线/advantage 降低方差

Actor Critic Methods

上一节使用完整 trajectory return 构造 REINFORCE gradient。这个 estimator 不需要学习 value function，但在长序列和稀疏 reward 下通常具有较高 variance。 baseline invariance 允许我们用 advantage 替代原始 return，而不改变期望梯度。

本节把前面的 policy evaluation 与 policy gradient 合并：actor $\pi_\theta$ 负责生成和更新策略，critic $V_\phi$ 或 $Q_\phi$ 负责估计 return/advantage。对 LLM 而言，两者分别对应需要优化的语言模型和训练期间使用的 value estimator。

Actor-Critic

我们首先考虑最简单的 actor-critic algorithm, 注意到

\nabla_\theta \mathcal{J}(\theta) = \mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)Q^{\pi_\theta}(s_t,a_t)\right]

因此，其对应的 policy gradient methods 为

\theta_{k+1} = \theta_k + \alpha \mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)Q^{\pi_\theta}(s_t,a_t)\right]

在前面的章节中，我们介绍了基于 MC 和 TD 两种方式来估计 $Q^{\pi_\theta}(s_t,a_t)$ 。据此可以区分：

如果 $Q^{\pi_\theta}(s_t,a_t)$ 由 MC 来进行估计，则我们将其称为 REINFORCE 或者 Monte Carlo policy gradient.
如果 $Q^{\pi_\theta}(s_t,a_t)$ 由 TD learning 来进行估计，则我们将其称为 actor-critic, 这是我们本节的重点介绍内容

最简单的 actor-critic algorithm 如下所示

Algorithm: Q Actor-Critic

Initialize policy parameters $\theta_0$ , value function parameters $\phi_0$ .
for $t = 0, 1, \dots, T-1$ $t = 0, 1, \dots, T - 1$ :
- $a_t \sim \pi_{\theta}(\cdot \mid s_t)$ , $r_t, s_{t+1} \sim p(\cdot, \cdot \mid s_t, a_t)$ , $a_{t+1} \sim \pi_{\theta}(\cdot \mid s_{t+1})$ .
- (ACTOR) policy update: $\theta_{t+1} = \theta_t + \alpha_{\theta} \nabla_{\theta} \log \pi_{\theta}(a_t \mid s_t) \, Q^{\phi_t}(s_t, a_t)$
- (CRITIC) value update: $\phi_{t+1} = \phi_t + \alpha_{\phi} \left[r_t + \gamma Q^{\phi_t}(s_{t+1}, a_{t+1}) - Q^{\phi_t}(s_t, a_t)\right] \nabla_{\phi} Q^{\phi_t}(s_t, a_t)$

Advantage Actor-Critic (A2C)

在上一节中，我们介绍了 QAC, 但实际上我们用的更多的是 advantage actor-critic, 其梯度如下所示

\nabla_\theta \mathcal{J}(\theta)=\mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[ \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t)A^{\pi_\theta}(s_t,a_t)\right]

注意到

A^{\pi_\theta}(s_t,a_t)=Q^{\pi_\theta}(s_t,a_t)-V^{\pi_\theta}(s_t) = \mathbb{E}^{\pi_\theta}\left[r_t + \gamma V^{\pi_\theta}(s_{t+1})-V^{\pi_\theta}(s_t)\mid s_t, a_t\right]

因此我们可以用 TD error 来进行近似：

\hat{A}_t= r_t + \gamma V_{\phi_t}(s_{t+1})-V_{\phi_t}(s_t)

这样我们就得到了 A2C 算法

Algorithm: Advantage Actor-Critic (A2C)

Initialize policy parameters $\theta_0$ , value function parameters $\phi_0$ .
for $t = 0, 1, \dots, T-1$ $t = 0, 1, \dots, T - 1$ :
- $a_t \sim \pi_{\theta}(\cdot \mid s_t)$ , $r_t, s_{t+1} \sim p(\cdot, \cdot \mid s_t, a_t)$ .
- Advantage estimation: $\hat{A}_t \approx r_t + \gamma V_{\phi_t}(s_{t+1}) - V_{\phi_t}(s_t)$
- (ACTOR) policy update: $\theta_{t+1} = \theta_t + \alpha_{\theta} \nabla_{\theta} \log \pi_{\theta}(a_t \mid s_t) \, \hat{A}_t$
- (CRITIC) value update: $\phi_{t+1} = \phi_t + \alpha_{\phi} \, \hat{A}_t \, \nabla_{\phi} V^{\phi_t}(s_t)$

GAE

在上一节中，我们介绍了我们可以用 1-step TD error 来近似 advantage,

对比结果如下表所示

Method	bias	variance
TD error	can be biased	low variance
MC estimate	unbiased	high variance

为了实现更好的 bias-variance trade-off, GAE (Schulman et al., 2016) 提出了使用一个参数 $\lambda\in[0,1]$ 来控制 bias 和 variance 之间的权重，其表达式如下所示

\hat{A}_t^{GAE(\gamma,\lambda)} = \sum_{\ell=0}^{\infty}(\gamma\lambda)^{\ell}\delta_{t+\ell}

其中

\delta_t = r_t + \gamma V_{\phi_t}(s_{t+1})-V_{\phi_t}(s_t)

我们可以探究不同的 $\lambda$ 对应的估计：

当 $\lambda=0$ 时，我们有

\hat{A}_t^{GAE(\gamma,0)} = (\gamma\cdot0)^0\delta_t=\delta_t

此时，GAE 就退化成了 one-step TD error estimate,

当 $\lambda=1$ 时，我们有

\hat{A}_t^{GAE(\gamma,1)} = \sum_{\ell=0}^{\infty}\gamma^{\ell}\delta_{t+\ell}=\sum_{\ell=0}^{\infty}\gamma^{\ell}\left(r_t + \gamma V_{\phi_t}(s_{t+1})-V_{\phi_t}(s_t)\right)

如果我们假设这里使用的是真实的 value function 的话，那么我们有

\hat{A}_t^{GAE(\gamma,1)} \approx \sum_{\ell=0}^{\infty}\gamma^{\ell}r_{t+\ell+1}-V(s_t)=Q^{\pi_\theta}(s_t,a_t)-V(s_t)

当 $0<\lambda<1$ 时， $GAE$ 是 TD error estimate 与 MC estimate 的一个插值， $\lambda$ 越大，estimate 越依赖 long term reward information, 其 bias 越低，但是相应的 variance 越高。 $\lambda$ 越小，estimate 月依赖于当前的 value function estimate, 其 variance 越低，但是相应的其 bias 越高

实际计算过程中，我们使用如下方法来进行计算

Algorithm: Generalized Advantage Estimation (GAE)

Given policy parameters $\theta$ , value function parameters $\phi$ .
Sample a trajectory $\tau \sim (p_0, \pi_{\theta}, p)$ .
for $t = 0, 1, \dots, T-1$ $t = 0, 1, \dots, T - 1$ :
- Compute TD errors: $\delta_t = r_t + \gamma V_{\phi}(s_{t+1}) - V_{\phi}(s_t)$
Initialize $\hat{A}_{T}^{\mathrm{GAE}} = 0$ .
for $t = T-1, \dots, 0$ $t = T - 1, \dots, 0$ :
- Iterate backward: $\hat{A}_t^{\mathrm{GAE}} = \delta_t + \gamma\lambda \, \hat{A}_{t+1}^{\mathrm{GAE}}$

GAE 的主要优点在于其相对于 MC estimate 可以大幅度降低 variance, 从而提高训练的稳定性以及效率

Why actor critic

comparison with value-based methods:

无法处理高维或者连续动作空间，actor-critic 中 actor 可以输出一个连续值的概率分布，直接从分布中采样就能得到动作，不需要遍历动作空间
无法学习到随机策略： value-based methods 只能推导出确定性策略，使用 $\epsilon$ greedy 之后，也只是随机探索，而不是有策略的随机探索。Actor 可以参数化策略，学习到任意概率分布的随机策略
学习到的策略更平滑：value-based methods 动作选择依赖于 greedy strategy, 导致 Q function 微小变化导致策略发生剧烈跳变。而 actor-critic 通过 policy gradient 解决了这个问题

comparison with policy-based methods

policy-based methods 依赖完整的 rollout 的 return 来更新，对于 long-term tasks, 最后的 return 方差很大，训练难以收敛。 actor-critic 通过引入 critic 来估计期望收益，计算 advantage, 来降低整体法国差，同时用 TD error 代替回合更新，加速训练。

Schulman, J., Moritz, P., Levine, S., Jordan, M., & Abbeel, P. (2016). High-Dimensional Continuous Control Using Generalized Advantage Estimation. Proceedings of the International Conference on Learning Representations (ICLR).

TRPO

前面的 policy gradient 和 actor-critic 给出了更新方向，但没有回答一个关键问题： 一次可以把 policy 更新多远？ 如果新旧 policy 差异过大，旧 policy 生成的 trajectory 很快失效，近似目标也可能不再可靠。

TRPO (Trust Region Policy Optimization) (Schulman et al., 2015) 使用旧策略 $\pi_{\theta_{\mathrm{old}}}$ 的 rollout 构造 surrogate objective，并通过 KL constraint 限制新旧策略的距离。它仍然主要是 on-policy 方法；重点不是把 policy gradient 变成一般的 off-policy learning，而是在一个受控的 trust region 内安全地复用当前批次。

这一思想对 LLM 尤其重要：生成 rollout 成本很高，但在同一批 rollout 上执行过多 gradient steps 又会造成 policy drift。TRPO 首先形式化这一稳定性约束，后续 PPO 会给出更容易实现的一阶近似。

我们的目标函数为

\max_{\pi}\mathcal{J}(\theta)=\mathbb{E}_{s_0\sim p_0}\left[V^{\pi_\theta}(s_0)\right]

我们假设有两个 policy 的参数, $\theta$ 和 $\theta_{old}$ , 我们分析一下两个 policy 对应的目标函数之间的 difference:

\begin{aligned} \mathcal{J}(\theta) -\mathcal{J}(\theta_{old}) &= \mathcal{J}(\theta) - \mathbb{E}_{s_0\sim p_0}\left[V^{\pi_{\theta_{old}}}(s_0)\right]\\ &= \mathcal{J}(\theta) - \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p)}\left[V^{\pi_{\theta_{old}}}(s_0)\right]\\ &= \mathcal{J}(\theta) - \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p)}\left[\sum_{t=0}^{T-1}\gamma^tV^{\pi_{\theta_{old}}}(s_t)-\sum_{t=1}^{T-1}\gamma^tV^{\pi_{\theta_{old}}}(s_t)\right]\\ &= \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p)}\left[\sum_{t=0}^{T-1}\gamma^t r_t\right] + \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p)}\left[\sum_{t=0}^{T-1}\gamma^t\left(\gamma V^{\pi_{\theta_{old}}}(s_{t+1})-V^{\pi_{\theta_{old}}}(s_t)\right)\right]\\ &= \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p)}\left[\sum_{t=0}^{T-1}\gamma^t\left(r_t+\gamma V^{\pi_{\theta_{old}}}(s_{t+1})-V^{\pi_{\theta_{old}}}(s_t)\right)\right]\\ &= \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p)}\left[\sum_{t=0}^{T-1}\gamma^t\left(\gamma Q^{\pi_{\theta_{old}}}(s_{t}, a_t)-V^{\pi_{\theta_{old}}}(s_t)\right)\right]\\ &= \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p)}\left[\sum_{t=0}^{T-1}\gamma^t A^{\pi_{\theta_{old}}}(s_t,a_t)\right]\\ \end{aligned}

我们进一步展开得到

\begin{align} \mathcal{J}(\theta) -\mathcal{J}(\theta_{old}) &= \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p)}\left[\sum_{t=0}^{T-1}\gamma^t A^{\pi_{\theta_{old}}}(s_t,a_t)\right]\\ &= \mathbb{E}_{s_0\sim p_0, a_0\sim\pi_\theta(\cdot\mid s_0)}\left[A^{\pi_{\theta_{old}}}(s_0,a_0)+\mathbb{E}^{\pi_\theta}\left[\sum_{t=1}^{T-1}\gamma^t A^{\pi_{\theta_{old}}}(s_t,a_t)\mid s_0, a_0\right]\right]\\ &= \mathbb{E}_{s_0\sim p_0, a_0\sim\pi_\theta(\cdot\mid s_0),a_0'\sim \pi_{\theta_{old}}(\cdot\mid s_0)}\left[\frac{\pi_{\theta}(a_0'\mid s_0)}{\pi_{\theta_{old}}(a_0'\mid s_0)}A^{\pi_{\theta_{old}}}(s_0,a_0')+\mathbb{E}^{\pi_\theta}\left[\sum_{t=1}^{T-1}\gamma^t A^{\pi_{\theta_{old}}}(s_t,a_t)\mid s_0, a_0\right]\right]\\ &=\dots (\text{keep enrolling the summation})\\ &= \mathbb{E}_{\tau\sim (p_0,\pi_\theta, p),a_t'\sim \pi_{\theta_{old}}(\cdot\mid s_t)}\left[\sum_{t=0}^{T-1}\gamma^t \frac{\pi_{\theta}(a_t'\mid s_t)}{\pi_{\theta_{old}}(a_t'\mid s_t)}A^{\pi_{\theta_{old}}}(s_t,a_t')\right]\\ \end{align}

因此，我们有

\mathcal{J}(\theta) = \mathbb{E}_{\tau\sim(p_0,\textcolor{red}{\pi_\theta}, p),a_t'\sim\pi_{\theta_{old}}(\cdot\mid s_t)}\left[\sum_{t=0}^{T-1}\gamma^t\frac{\pi_\theta(a_t'\mid s_t)}{\pi_{\theta_{old}}(a_t'\mid s_t)}A^{\pi_{\theta_{old}}}(s_t,a_t')\right]+C

但是，现在我们的更姓还是依赖于 $\pi_\theta$ , 这很难处理。因此 TRPO 的思想就是，当 $\pi_\theta$ 与 $\pi_{\theta_{old}}$ 充分接近时，使用 $\pi_{\theta_{old}}$ 来替换 $\pi_\theta$ , 这样，上面目标函数就变成了

\begin{align} \max_{\theta}\ &\mathcal{K}(\theta;\theta_{old}) = \mathbb{E}_{\tau\sim(p_0,\pi_{\theta_{old}}, p),a_t'\sim\pi_{\theta_{old}}(\cdot\mid s_t)}\left[\sum_{t=0}^{T-1}\gamma^t\frac{\pi_\theta(a_t'\mid s_t)}{\pi_{\theta_{old}}(a_t'\mid s_t)}A^{\pi_{\theta_{old}}}(s_t,a_t')\right]\\ \mathrm{s.t.}\ &\pi_{\theta_{old}}\approx \pi_\theta \end{align}

我们可以证明

\nabla \mathcal{J}(\theta)\mid _{\theta=\theta_{old}} = \nabla_\theta \mathcal{K}(\theta;\theta_{old})\mid _{\theta=\theta_{old}}

这就是 TRPO 的核心改进，在实际求解时，我们将上面的问题规范为如下形式

\begin{align} \max_{\theta}\ &\mathcal{K}(\theta;\theta_{old}) = \mathbb{E}_{\tau\sim(p_0,\pi_{\theta_{old}}, p),a_t'\sim\pi_{\theta_{old}}(\cdot\mid s_t)}\left[\sum_{t=0}^{T-1}\gamma^t\frac{\pi_\theta(a_t'\mid s_t)}{\pi_{\theta_{old}}(a_t'\mid s_t)}A^{\pi_{\theta_{old}}}(s_t,a_t')\right]\\ \mathrm{s.t.}\ &\max_{s\in\mathcal{S}}\mathrm{KL}(\pi_{\theta_{old}}(\cdot\mid s)\mid\mid \pi_\theta(\cdot\mid s))\leq \delta \end{align}

这里 $\delta>0$ 为一个超参数。

现在我们可以采样多条轨迹 $\tau^{(i)}\sim (p_0,\pi_{\theta_{old}}, p)$ 再使用 MC 方法来估计目标函数 $\mathcal{K}(\theta;\theta_{old})$

\mathcal{K}(\theta;\theta_{old}) = \mathbb{E}_{\tau\sim(p_0,\pi_{\theta_{old}}, p),a_t\sim\pi_{\theta_{old}}(\cdot\mid s_t)}\left[\sum_{t=0}^{T-1}\gamma^t\frac{\pi_\theta(a_t\mid s_t)}{\pi_{\theta_{old}}(a_t\mid s_t)}A^{\pi_{\theta_{old}}}(s_t,a_t)\right]\approx \frac{1}{N}\sum_{i=1}^N\sum_{t=0}^{T^{(i)}-1}\gamma^t\frac{\pi_\theta(a_t^{(i)}\mid s_t^{(i)})}{\pi_{\theta_{old}}(a_t^{(i)}\mid s_t^{(i)})}\hat{A}_t

这里 $\hat{A}_t\approx A^{\pi_{\theta_{old}}}(s_t,a_t)$ 是一个 advantage estimator. 注意上面的 estimator 当 $N$ 变大以及 $\pi_{\theta}\approx \pi_{\theta_{old}}$ 时比较准确。

Gamma Trick

在实际实现中，由于 discount factor $\gamma < 1$ , 远期 advantage 对梯度的贡献会指数级衰减。为了提高效率，TRPO 中常常使用 $\gamma = 1$ 来简化计算，但此时需要另外一种形式的约束来保证目标函数的有界性。这被称为 gamma trick：通过适当选择 $\gamma$ 的值来平衡 bias 和 variance.

更具体地，当 $\gamma < 1$ 时：

远期奖励对当前决策的影响被衰减，这在经济学中是合理的（现值概念）.
有助于减少远期估计的方差（远期的 $V^{\pi}$ 估计不确定性更大）.
在 TRPO 的 derivation 中， $\gamma$ 出现在目标函数的 discount 和中，使用较小的 $\gamma$ 可以使 $\pi_{\theta} \approx \pi_{\theta_{old}}$ 的近似更准确.

Overview

我们把上面的结果整理为如下算法

Algorithm: TRPO MC

Initialize policy parameters $\theta_0$ , value function parameters $\phi_0$ . Set hyperparameter $\delta > 0$ .
for $k = 0, 1, \dots$ $k = 0, 1, \dots$ :
- Sample $N$ trajectories $\{\tau_i\}$ according to $(p_0, \pi_{\theta_k}, p)$ .
- Solve the constrained optimization: $\begin{aligned} \max_{\theta_{k+1}} \quad &\frac{1}{N} \sum_{i=1}^{N} \sum_{t=0}^{T^{(i)}-1} \frac{\pi_{\theta_{k+1}}(a_t^{(i)} \mid s_t^{(i)})}{\pi_{\theta_k}(a_t^{(i)} \mid s_t^{(i)})} \hat{A}_t \\ \mathrm{s.t.} \quad &\max_{s \in \mathcal{S}} \mathrm{KL}(\pi_{\theta_{k}}(\cdot \mid s) \mid\mid \pi_{\theta_{k+1}}(\cdot \mid s)) \leq \delta \end{aligned}$
- Compute $\hat{R}_t^{(i)} = \gamma^{t'-t} r_{t'}^{(i)}$ for $i = 1, \dots, N$ , $t = 1, \dots, T^{(i)}-1$ .
- Update the value model: $\min_{\phi} \frac{1}{N} \sum_{i=1}^{N} \frac{1}{T^{(i)}} \sum_{t=0}^{T^{(i)}-1} \frac{1}{2} \left(V_{\phi}(s_t^{(i)}) - \hat{R}_t^{(i)}\right)^2$

关于这个优化问题的解法可以参考后续 discussion 章节

Experiments

Discussion

Connection with TRO

我们将目标函数和约束进行泰勒展开得到

\begin{align} \mathcal{K}(\theta;\theta_{old}) &\approx g^T(\theta-\theta_k) \\ \mathrm{KL}(\theta\mid\mid \theta_k)&\approx \frac12(\theta-\theta_k)^TH(\theta-\theta_k) \end{align}

这样我们的优化目标就近似为

\begin{align} \max_{\theta}\ & g^T(\theta-\theta_k)\\ \mathrm{s.t.}\ & \frac12(\theta-\theta_k)^TH(\theta-\theta_k)\leq\delta \end{align}

这个目标函数与 TRO (trust region methods) 一致，因此我们可以使用类似的做法来解决，我们可以得到上面问题的准确表达式

\theta_{k+1} = \theta_k + \sqrt{\frac{2\delta}{g^TH^{-1}g}}H^{-1}g

但是，由于我们使用了 Taylor 展开，实际上我们的更新并不一定满足 KL divergence 的约束，TRPO 对此进行了改进，即在更新时加入了 line search 来使得 $\theta_{k+1}$ 满足 KL divergence 约束。

\theta_{k+1} = \theta_k + \alpha^j\sqrt{\frac{2\delta}{g^TH^{-1}g}}H^{-1}g

其中 $\alpha\in(0,1)$ 是 backtracking line search 的参数， $j$ 是使得 $\theta_{k+1}$ 满足 KL divergence 约束的最小正整数 $k$ .

Drawbacks

虽然 TRPO 的理论形式非常简单，但是实际上实现起来很麻烦。其根本原因在于这个约束比较难以满足，原始论文中使用了 line search 来解决这个问题，但是当状态空间大了之后，速度会显著下降，这也是 PPO 的核心贡献之一。

Schulman, J., Levine, S., Moritz, P., Jordan, M. I., & Abbeel, P. (2015). Trust Region Policy Optimization. Proceedings of the 32nd International Conference on Machine Learning (ICML).

PPO

在上一节中，我们介绍了 TRPO 算法，TRPO 算法是一个二阶算法，TRPO 大幅度提高了 sample efficiency, 但是其问题在于计算/优化太过复杂。因此，PPO 就通过 clip 等技巧保留了 TRPO 思想并降低了计算难度。

在 TRPO 算法中，我们的优化问题形式为：

\begin{align} \max_{\theta}\ &\mathcal{K}(\theta;\theta_{old}) = \mathbb{E}_{\tau\sim(p_0,\pi_{\theta_{old}}, p),a_t'\sim\pi_{\theta_{old}}(\cdot\mid s_t)}\left[\sum_{t=0}^{T-1}\frac{\pi_\theta(a_t'\mid s_t)}{\pi_{\theta_{old}}(a_t'\mid s_t)}A^{\pi_{\theta_{old}}}(s_t,a_t')\right]\\ \mathrm{s.t.}\ &\max_{s\in\mathcal{S}}\mathrm{KL}(\pi_{\theta_{old}}(\cdot\mid s)\mid\mid \pi_{\theta}(\cdot\mid s))\leq \delta \end{align}

TRPO 的核心思想为，当 $\pi_{\theta}$ 和 $\pi_{\theta_{old}}$ 比较接近时，我们的目标函数 $\mathcal{K}(\theta;\theta_{old})$ 与 policy gradient 的目标函数 $\mathcal{J}(\theta)$ 梯度误差比较小。

PPO 针对这一点核心观点进行了扩展，我们可以通过另一种形式来约束 $\pi_{\theta}$ 和 $\pi_{\theta_{old}}$ 比较接近，即

r_t(\theta) := \frac{\pi_\theta(a_t'\mid s_t)}{\pi_{\theta_{old}}(a_t'\mid s_t)} \approx 1

基于这个思想，我们可以丢弃 TRPO 的约束，直接对 $r_t(\theta)$ 进行约束，这个约束可以使用 $\mathrm{clip}$ 函数来实现，此时优化的目标函数就变成了

\mathcal{J}(\theta) = \mathbb{E}_{(q,a)\sim\mathcal{D},o_{\leq t}\sim \pi_{\theta_{old}}(\cdot\mid q)}\left[ \mathrm{clip}\left(r_t(\theta), 1-\epsilon, 1+\epsilon\right)\hat{A}_t \right]

这里 $\epsilon>0$ 是一个超参数，类似于 TRPO 中的 $\delta$ .

\mathrm{clip}(x,\ell, r)=\begin{cases} \ell, &\text{ if }x\leq \ell\\ x, &\text{ if }\ell<x<r\\ r, &\text{ if }x \geq r \end{cases}

现在我们已经通过 $\mathrm{clip}$ 抛弃了 TRPO 复杂的约束了。我们来分析一下目标函数的性质，我们将不同的结果总结为下表

$\hat{A}_t$	$r_t$	objective	gradient	description
$>0$	$r>1+\epsilon$	$(1+\epsilon)\hat{A}_t$	0	好动作，比 old policy 概率更大，不更新
$>0$	$[1-\epsilon,1+\epsilon]$	$r_t\hat{A}_t$	$\nabla_\theta r_t\hat{A}_t$	好动作，与 old policy 概率差不多，更新
$>0$	$r<1-\epsilon$	$(1-\epsilon)\hat{A}_t$	0	好动作，比 old policy 概率更小，不更新
$<0$	$r>1+\epsilon$	$(1+\epsilon)\hat{A}_t$	0	坏动作，比 old policy 概率更大，不更新
$<0$	$[1-\epsilon,1+\epsilon]$	$r_t\hat{A}_t$	$\nabla_\theta r_t\hat{A}_t$	坏动作，比 old policy 概率差不多，更新
$<0$	$r<1-\epsilon$	$(1-\epsilon)\hat{A}_t$	0	坏动作，比 old policy 概率差更小，不更新

从结果中我们可以看出，只有当 $r_t\approx 1$ 时，我们才会更新我们的模型，对于 $\hat{A}_t>0, r_t<1-\epsilon$ 和 $\hat{A}_t<0, r_t<1-\epsilon$ 这两种应该更新的情况，我们并没有更新，我们的 sample efficiency 很低。为了解决这个问题，我们在 $\mathrm{clip}$ 的基础上，进一步加入一个 $\min$ 函数来进行控制，这样，我们就得到了 PPO 的目标函数：

\mathcal{J}_{\mathrm{PPO}}(\theta) = \mathbb{E}_{(q,a)\sim\mathcal{D},o_{\leq t}\sim \pi_{\theta_{old}}(\cdot\mid q)}\left[ \min\left(r_t(\theta)\hat{A}_t,\mathrm{clip}\left(r_t(\theta), 1-\epsilon, 1+\epsilon\right)\hat{A}_t\right) \right]

此时，我们再对目标函数进行分析，就得到

$\hat{A}_t$	$r_t$	objective	gradient	description
$>0$	$>1+\epsilon$	$(1+\epsilon)\hat{A}_t$	$0$	好动作，比 old policy 概率更大，不需要更新
$>0$	$\leq1+\epsilon$	$r_t\hat{A}_t$	$\nabla_\theta r_t\hat{A}_t$	好动作，与 old policy 概率差不多或更小，需要更新
$<0$	$\geq1-\epsilon$	$r_t\hat{A}_t$	$\nabla_\theta r_t\hat{A}_t$	坏动作，比 old policy 概率更小，不需要概率
$<0$	$<1-\epsilon$	$(1-\epsilon)\hat{A}_t$	$0$	坏动作，与 old policy 概率差不多或更高，概率

可以看到，此时 PPO 的目标函数就解决了 sample efficiency 过低的问题了。

PPO in RLHF

其中

r_t(\theta) = \frac{\pi_{\theta}(o_t\mid q, o_{< t})}{\pi_{\theta_{old}}(o_t\mid q, o_{< t})}

$(q,a)$ 是从数据集 $\mathcal{D}$ 采样的 QA pair， $\epsilon>0$ 是一个超参数， $\hat{A}_t$ 是 $t$ 时刻的优势估计 (advantage estimator). 给定 value function $V$ 以及 reward function $R$ , $\hat{A}_t$ 通过计算 GAE 得到：

\hat{A}_t^{\mathrm{GAE}(\gamma, \lambda)}=\sum_{k=0}^{\infty}(\gamma\lambda)^k\delta_{t+k}

其中

\delta_k = R_k + \gamma V(s_{k+1})-V(s_k),\quad 0\leq \gamma,\lambda\leq 1

Implementation

TODO

GRPO

GRPO (Group Relative Policy Optimization) 是 DeepSeek 提出的 RL 算法，相比于 PPO，GRPO 不依赖于 value function（因此也不需要 reward model 来训练 critic），而是通过同一 prompt 下的多组输出来估计 advantage.

Motivation

PPO 需要维护一个 value function $V_{\phi}$ 来估计 advantage $A_t$ :

\hat{A}_t^{\mathrm{GAE}} = \sum_{k=0}^{\infty} (\gamma\lambda)^k \delta_{t+k}, \quad \delta_k = r_k + \gamma V_{\phi}(s_{k+1}) - V_{\phi}(s_k)

但是在 LLM 场景下，训练 value function 会带来额外的计算和内存开销：

需要额外训练一个与 policy model 规模相当的 critic model
需要 reward model 提供的 token-level reward（而很多 verifier 只提供 outcome-level reward）

GRPO 的核心思想：用同一 prompt 下的一组输出来估计 baseline（即群体级别的相对奖励），从而避免训练 value function.

Algorithm

给定 QA pair $(q, a)$ , 从 $\pi_{\theta_{old}}$ 中采样 $G$ 个输出 $\{o_i\}_{i=1}^G$ , 并获取对应的 reward $\{R_i\}_{i=1}^G$ .

Advantage Estimation：

GRPO 使用 group-level 归一化来估计 advantage:

\hat{A}_{i,t} = \frac{R_i - \mathrm{mean}(\{R_i\}_{i=1}^G)}{\mathrm{std}(\{R_i\}_{i=1}^G)}

这里 advantage $\hat{A}_{i,t}$ 与时间步 $t$ 无关（仅与 group 中的 reward 排名相关），这使得 GRPO 能够直接使用 outcome-level reward.

直观理解：同一 prompt 下的 $G$ 个 response 中，高于平均奖励的 response 获得正的 advantage, 低于平均奖励的 response 获得负的 advantage. 这与 PPO 中 $A_t = Q_t - V_t$ 的思想一致： $V_t$ 是”平均意义上的 expected return”, 起到 baseline 的作用.

GRPO Objective:

GRPO 的训练目标与 PPO 类似，但在分组上进行了归一化：

\mathcal{J}_{\mathrm{GRPO}}(\theta) = \mathbb{E}_{(q, a) \sim \mathcal{D}, \, \{o_i\}_{i=1}^G \sim \pi_{\theta_{old}}(\cdot \mid q)}\left[ \frac{1}{G} \sum_{i=1}^G \frac{1}{|o_i|} \sum_{t=1}^{|o_i|} \min\left(r_{i,t}(\theta) \hat{A}_{i,t}, \; \mathrm{clip}\left(r_{i,t}(\theta), 1 - \epsilon, 1 + \epsilon\right) \hat{A}_{i,t}\right) \right]

其中:

r_{i,t}(\theta) = \frac{\pi_{\theta}(o_{i,t} \mid q, o_{i,<t})}{\pi_{\theta_{old}}(o_{i,t} \mid q, o_{i,<t})}

是 importance sampling ratio，衡量新旧策略在 token $o_{i,t}$ 处的概率比.

GRPO 中 $\hat{A}_{i,t}$ 对所有 token 使用相同的 advantage 值（基于 outcome reward）。这与 PPO 使用 GAE 得到 per-token advantage 不同.

GRPO v.s. PPO

	PPO	GRPO
Value function	需要训练 $V_{\phi}$	不需要
Advantage estimation	GAE (per-token)	Group-level 归一化 (per-response)
Reward 要求	Token-level reward (需要 reward model)	Outcome-level reward (verifier 即可)
计算开销	更高 (需训练 critic)	更低
采样效率	较高	需要更多样本 ( $G$ 个 response per prompt)
KL 正则化	通常使用 KL penalty	通常直接使用 reward shaping

KL Divergence Regularization

在实际的 RLHF/GRPO 训练中，通常会在 reward 中减去一个 KL 惩罚项，以防止模型偏离 reference model 太远:

R_i = R_{\mathrm{task}}(o_i) - \beta \, \mathrm{KL}(\pi_{\theta} \| \pi_{\mathrm{ref}})

其中 $\beta > 0$ 是超参数， $\pi_{\mathrm{ref}}$ 是 reference model (通常是 SFT 后的模型).

常用的 KL 估计方式包括：

Kullback-Leibler divergence: $\mathrm{KL}(\pi_{\theta} \| \pi_{\mathrm{ref}}) = \mathbb{E}_{o \sim \pi_{\theta}}\left[\log\frac{\pi_{\theta}(o \mid q)}{\pi_{\mathrm{ref}}(o \mid q)}\right]$
Unbiased KL estimator: DeepSeek 使用的低方差估计，形式为： $\mathrm{KL}(\pi_{\theta} \| \pi_{\mathrm{ref}}) = \frac{\pi_{\mathrm{ref}}(o_{i,t} \mid q, o_{i,<t})}{\pi_{\theta}(o_{i,t} \mid q, o_{i,<t})} - \log\frac{\pi_{\mathrm{ref}}(o_{i,t} \mid q, o_{i,<t})}{\pi_{\theta}(o_{i,t} \mid q, o_{i,<t})} - 1$

Training Pipeline

GRPO 的典型训练流程如下：

Algorithm: GRPO Training

Input: Dataset $\mathcal{D}$ of prompts, reference model $\pi_{\mathrm{ref}}$ , group size $G$ .
Initialize: policy $\pi_{\theta} = \pi_{\mathrm{ref}}$ .

for each training iteration:

Sample a batch of prompts $\{q\}$ from $\mathcal{D}$ .
For each prompt $q$ , sample $G$ responses $\{o_i\}$ from $\pi_{\theta}$ : $o_i \sim \pi_{\theta}(\cdot \mid q), \quad i = 1, \dots, G$
Compute reward for each response: $R_i = R_{\mathrm{task}}(o_i) - \beta \, \mathrm{KL}(\pi_{\theta} \| \pi_{\mathrm{ref}})$
Compute group-level advantage: $\hat{A}_i = \frac{R_i - \mathrm{mean}(\{R\})}{\mathrm{std}(\{R\})}$
Update $\pi_{\theta}$ using GRPO objective: $\mathcal{L} = \frac{1}{G} \sum_{i=1}^{G} \frac{1}{|o_i|} \sum_{t=1}^{|o_i|} \min\!\left(r_{i,t}(\theta) \hat{A}_i, \; \mathrm{clip}\!\left(r_{i,t}(\theta), 1 - \epsilon, 1 + \epsilon\right) \hat{A}_i\right)$
(Optional) Update $\pi_{\mathrm{ref}}$ periodically.

Why GRPO Works for LLM

无需求解 value function: 在 LLM 场景下，action space (词表) 和 state space (上下文) 极大，训练 value function 是非常困难且昂贵的。GRPO 通过 group 比较自然避免了这一问题.
Outcome-level reward 友好: 许多 LLM 任务（如数学推理、代码生成）只有最终的 outcome reward (答案正确与否)。GRPO 可以直接利用 outcome reward，无需 reward model 提供 token-level reward.
简单高效: GRPO 的实现相对简单，无需维护 critic network，计算和内存开销更小.