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 使用的函数逼近方法。这条路径同时回答两个问题：

为什么 Bellman equation 在小环境中可直接求解
精确求解方法对于 LLM 来说存在什么问题

Tabular Learning

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

Tabular Learning with Matrix Solve

对于离散状态空间来说，我们可以将 value iteration 算法中的 Bellman Equation 写为如下的矩阵形式

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}

可以看到，上面这个其实是一个线性方程组，即

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

对于这个线性方程组，我们可以用矩阵求逆或者迭代解法求解。精确算法如下所示

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}$
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$

下面是两种算法在不同规模下对应的求解时间变化曲线

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_0\sim p_0$ , $\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_0\sim p_0$
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$

接下来我们来分析一下算法的正确性。首先， $\overline{V}_t$ 被称为 TD target 的原因为

\begin{aligned} |V_{t+1}(s_t)-\overline{V}_t(s_t)| &= |V_t(s_t) - \alpha_t(s_t)\delta_t-\overline{V}_t(s_t)|\\ &= |1-\alpha_t(s_t)||V_{t}(s_t)-\overline{V}_t(s_t)|\\ &< |V_{t}(s_t)-\overline{V}_t(s_t)| \end{aligned}

可以看到函数序列 $\{V_t\}$ 收敛到 $\overline{V}_t$ . 另一方面，我们有

\begin{aligned} \mathbb{E}[\delta_t\mid S_t=s_t] &= \mathbb{E}[V^{\pi}(S_t)-\left(r_t + \gamma V^{\pi}(s_{t+1})\right)\mid S_t=s_t]\\ &= V^{\pi}(s_t) - \mathbb{E}[r_t + \gamma V^{\pi}(s_{t+1})\mid S_t=s_t]\\ &=0 \end{aligned}

因此 TD error $\delta_t$ 衡量了当前的估计 $V_t$ 与 $V^\pi$ 之间的差距。

算法的正确性由如下定理给定

Theorem: Convergence of TD Learning

给定策略 $\pi$ , 基于 TD learning algorithm, 对任意 $s\in\mathcal{S}$ , 如果 $\sum_t\alpha_t(s)=\infty$ , $\sum_t\alpha_t^2(s)<\infty$ , 则 $V_t(s)$ $a.s.$ 收敛到 $V^{\pi}(s)$ , $t\to\infty$ .

Proof:

See Theorem 7.1 of Mathematical Foundations of Reinforcement Learning for more details.

Tabular Learning Experiments

我们在不同 vocab size 下对比 matrix solve, MC 和 TD. 对于 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 binary reward、固定超参数和误差指标下，MC 比 TD 更快达到目标误差。当 vocab size 超过 30 后，两者在 rollout budget 内都很难观察到足够多的正样本。

这里暴露出两个不同的问题：

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$ 表示策略 $\pi$ 在 rollout 中诱导的状态访问分布，我们使用 mean squared value (MSE) 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_0 \sim p_0$ , $t = 0$ , $\tau=[]$ .
while $s_t \neq \langle\text{term}\rangle$ $s_{t} \neq = ⟨ term ⟩$ :
- $a_t \sim \pi(\cdot \mid s_t)$
- $(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)$
- $\tau.\mathrm{append}((s_t,r_t))$
- $t \gets t + 1$
Set $T = t$ .
For every $t=0,\ldots,T-1$ , compute $G_t=\sum_{k=t}^{T-1}\gamma^{k-t}r_k$ .
$g\gets\frac{1}{T}\sum_{t=0}^{T-1} (V_\phi(s_t)-G_t)\nabla_\phi V_\phi(s_t)$ .
Update $\phi$ using $g$ with an optimizer.

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].

对应的数学更新为：

Algorithm: Value function approximation with TD (not correct)

While not converged:

$s_0 \sim p_0$ , $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 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.

我们来看一下上述算法对应的 PyTorch 实现：

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] = \begin{cases} x & \text{forward pass} \\ 0 & \text{backward pass} \end{cases}

对应的梯度就是：

\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 代码为：

pred = V_phi(s0)
target = r + gamma * V_phi(s1)
td_error = pred - target.detach()  # stop-gradient operator
loss = 0.5 * td_error ** 2
loss.backward()

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

Algorithm: Value function approximation with TD

While not converged:

$s_0 \sim p_0$ , $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:

$s_0 \sim p_0$ , 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-function, 我们也可以和 value function 一样设计类似的算法。对于 MC, 有：

Q^{\pi}(s_0, a_0) =\mathbb{E}^{\pi}\left[\sum_{t=0}^{T-1}\gamma^t r_t\mid s_0,a_0\right] \approx\frac{1}{M}\sum_{i=1}^{M}\sum_{t=0}^{T^{(i)}-1}\gamma^t r_t^{(i)}.

当使用函数来近似时，目标函数为：

\mathcal{L}(\phi) = \mathbb{E}_{s \sim d^\pi,\,a\sim\pi(\cdot\mid s)} \left[\frac{1}{2}\left(Q_{\phi}(s,a)-Q^{\pi}(s,a)\right)^2\right].

对应的梯度：

\nabla_{\phi} \mathcal{L}(\phi) =\mathbb{E}^{\pi}\left[ \left(Q_{\phi}(s_t,a_t)-G_t\right)\nabla_{\phi}Q_{\phi}(s_t,a_t) \right].

对应的算法如下

Algorithm: Q-function approximation with MC

while not converged:

$s_0 \sim p_0$ , set $t = 0$ , $\tau=[]$ .
while $s_t \neq \langle\text{term}\rangle$ $s_{t} \neq = ⟨ term ⟩$ :
- $a_t \sim \pi(\cdot \mid s_t)$
- $(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)$
- $\tau.\mathrm{append}((s_t,a_t,r_t))$
- $t \gets t + 1$
Set $T = t$ .
For every $t$ , compute $G_t=\sum_{k=t}^{T-1}\gamma^{k-t}r_k$ .
$g=\frac{1}{T}\sum_{t=0}^{T-1} (Q_\phi(s_t,a_t)-G_t)\nabla_\phi Q_\phi(s_t,a_t)$ .
Update $\phi$ using $g$ with an optimizer.

Return $Q_\phi$

对于 TD learning, 我们的目标函数为

\mathcal{L}(\phi) = \mathbb{E}_{s \sim d^\pi,\,a\sim\pi(\cdot\mid s)} \left[\frac{1}{2}\left(Q_{\phi}(s,a)-r-\gamma Q^\pi(s',a')\right)^2\right],

其中非终止状态下 $a'\sim\pi(\cdot\mid s')$ . 与 value function 类似，使用 bootstrap target 可以得到 on-policy 的 Expected SARSA/SARSA 风格 policy evaluation：

Algorithm: Q-function approximation with TD

While not converged:

$s_0 \sim p_0$ , $a_0 \sim \pi(\cdot \mid s_0)$ , $(r_0, s_1) \sim p(\cdot, \cdot \mid s_0, a_0)$ .
$y = \begin{cases} r_0 + \gamma \, \mathrm{sg}[Q_{\phi}(s_1, a_1)], \quad a_1\sim\pi(\cdot\mid s_1), & \text{if } s_1 \neq \langle\text{term}\rangle, \\ r_0, & \text{otherwise}. \end{cases}$
$g = \left(Q_{\phi}(s_0, a_0) - y\right) \nabla_{\phi} Q_{\phi}(s_0, a_0)$ .
Update $\phi$ using $g$ with an optimizer.

Return $Q_\phi$

Algorithm: Q-function approximation with k-step TD

While not converged:

$s_0 \sim p_0$ , set $t = 0$ .
For $t = 0, \ldots, k-1$ $t = 0, \dots, k - 1$ , stopping early on termination:
- $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.
If $s_n$ $s_{n}$ is non-terminal
1. sample $a_n\sim\pi(\cdot\mid s_n)$
2. set $y=\sum_{t=0}^{n-1}\gamma^t r_t+\gamma^n\mathrm{sg}[Q_\phi(s_n,a_n)]$ ;
Else
1. set $y=\sum_{t=0}^{n-1}\gamma^t r_t$ .
$g = (Q_{\phi}(s_0, a_0) - y) \nabla_{\phi} Q_{\phi}(s_0, a_0)$
Update $\phi$ using $g$ with an optimizer.

Return $Q_\phi$

Policy Iteration Methods

介绍完 policy evaluation 之后，我们可以设计 policy iteration 算法，其基本思想是交替进行 policy evaluation 和 policy improvement:

\begin{aligned} &\text{Compute } V^{\pi^k} \text{ and } Q^{\pi^k} &\quad&\text{(Policy evaluation)} \\ &\pi^{k+1}(s) = \arg\max_{a \in \mathcal{A}} \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V^{\pi^k}(s') \mid s, a\right] &\quad&\text{(Policy improvement)} \end{aligned}

算法的正确性由如下定理保证

Theorem:

Theorem: 考虑上述 policy iteration 算法，假设 $\gamma \in (0, 1)$ , $|\mathcal{S}| < \infty$ , $|\mathcal{A}| < \infty$ 以及 $|r| \leq R < \infty$ , a.s. 那么：

V^{\pi^{k+1}} \geq V^{\pi^k}, \quad k = 1, 2, \dots

并且存在 $K \in \mathbb{N}$ 满足 $V^{\pi^K} = V^*$ . 也就是说，有限步之后就可以得到最优策略.

Proof:

由 $\pi^{k+1}$ 的 greedy 定义，对每个状态 $s$ 都有

(\mathcal T^{\pi^{k+1}}V^{\pi^k})(s) =(\mathcal T^*V^{\pi^k})(s) \geq(\mathcal T^{\pi^k}V^{\pi^k})(s) =V^{\pi^k}(s).

反复应用单调的 Bellman operator $\mathcal T^{\pi^{k+1}}$ ，并利用其 contraction 性质，得到

V^{\pi^{k+1}} =\lim_{n\to\infty} (\mathcal T^{\pi^{k+1}})^nV^{\pi^k} \geq V^{\pi^k}.

有限 MDP 只有有限个 deterministic policies. 若 value 尚未最优，policy improvement 会产生严格改进；采用一致的 tie-breaking 后不会在等价 policy之间循环。因此有限次迭代后到达满足 Bellman optimality equation 的 policy, 其 value 即为 $V^*$ .

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\to0\quad} \text{k-step TD} \xrightarrow{\quad k\to T\quad} \text{MC}.

Takeaway

LLM generation 的 state 是 (prompt, token prefix), 状态空间随 horizon (context length) 指数增长
Matrix solve 和 dynamic programming 能提供小规模环境 ( $< 20$ ) 的精确基线，但无法扩展到真实 LLM 的场景下 ( $\sim15k$ )
MC 使用完整 return, low bias, high variance; TD 使用 bootstrap, low variance, high bias; k-step return 在两者之间实现一个 trade off.
Function approximation 让不同 prefix 共享信息，一条 rollout 可以监督多个 prefix
在 binary verifier reward 下， $V^\pi(x,y_{<t})$ 可以解释为当前 policy 最终通过 verifier 的概率
Policy evaluation 解决的是“当前 policy 有多好”；下一步 policy improvement 才解决“如何让 policy 变得更好”

Value Based Methods

在 Policy Evaluation 一节中，策略 $\pi$ 是固定的，我们只估计 $V^\pi$ 或 $Q^\pi$ . Value-based methods 更进一步：学习能够区分动作优劣的 value function，并据此改进策略。

一种直接思路是寻找 optimal value function $V^*$ 或 optimal Q function $Q^*$ ，再从中恢复最优策略。这也是 value based methods 的核心思想：

求解得到 optimal value function $V^*$ 或者 optimal Q function $Q^*$ , 再得到 optimal policy $\pi^*$ .

Value Iteration

Value iteration 的基本思路为：通过 Bellman optimality operator 迭代求解 $V^*$ 和 $Q^*$ , 然后得到最优策略。根据 BOE Theorem 的证明， $\mathcal{T}^*$ 是一个 contraction mapping, 因此我们可以构造函数序列：

V, \mathcal{T}^* V, (\mathcal{T}^*)^2 V, \cdots

由不动点定理，该序列收敛到 $V^*$ . 这就是 value iteration algorithm:

\begin{aligned} V^{k+1} &= \mathcal{T}^* V^k \\ V^{k+1}(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 + \gamma V^k(s_{t+1}) \mid S_t=s_t, A_t=a_t\right] \end{aligned}

类似地，我们还有 Q value iteration algorithm:

\begin{aligned} Q^{k+1} &= \mathcal{T}^* Q^k \\ Q^{k+1}(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^k(s_{t+1}, a_{t+1}) \mid S_t=s_t,A_t=a_t\right] \end{aligned}

最终，我们的最优策略为

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

其中 $Q^*=\lim_{k\to\infty}Q^k$ .

本节将 value iteration 的思想与函数逼近、TD learning 等技术结合，得到实用的 value-based 算法.

Tabular Learning

当 state 和 action space 足够小时，我们可以直接维护一张 Q-table.

在 Model-Free 设定下，我们无法直接计算转移概率 $\mathbb{E}_{s' \sim p}$ . 此时，我们必须通过与环境交互产生的轨迹样本 $(s, a, r, s', a')$ 来更新价值。

SARSA

SARSA 的核心在于它的更新动作 $a'$ 严格来自于当前的 $\epsilon$ -greedy 策略：

$\boxed{Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma Q(s', a') - Q(s, a) \right]}$

Q-Learning (Off-Policy TD Control)

与 SARSA 不同，Q-Learning 在估计未来价值时，直接贪心地选择最优动作，而不受当前探索策略的影响：

$\boxed{Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a' \in \mathcal{A}} Q(s', a') - Q(s, a) \right]}$

Function Approximation

当状态空间较大或连续时，我们需要使用函数逼近，与上一节类似，我们用 $V_{\phi}$ 近似 $V^{\pi}$ :

J(\phi) = \mathbb{E}_{s}\left[\frac{1}{2}\left(V^{\pi}(s) - V_{\phi}(s)\right)^2\right]

目标函数的梯度为：

\nabla_{\phi} J(\phi) = -\mathbb{E}_{s}\left[(V^{\pi}(s) - V_{\phi}(s))\nabla_{\phi} V_{\phi}(s)\right]

随机梯度下降的更新形式为：

\phi_{k+1} = \phi_k + \alpha_k (V^{\pi}(s) - V_{\phi}(s))\nabla_{\phi} V_{\phi}(s)

$V^{\pi}(s)$ 可以通过两种方式来近似：

MC 近似: $V^{\pi}(s) = \mathbb{E}^{\pi}[G_0 \mid s_0 = s] \approx G_0$
TD 近似: $V^{\pi}(s) \approx r_t + \gamma V_{\phi}(s_{t+1})$

Deep Q-Network (DQN)

将 function approximation 与 Q-learning 结合，可以用 neural network 逼近 optimal Q function。DQN 进一步引入 replay buffer 和 target network 来改善训练稳定性：

\mathcal{L}(\phi) = \mathbb{E}_{(s,a,r,s') \sim \mathcal{D}} \left[ \frac{1}{2} \left( r + \gamma \max_{a'} Q_{\phi^-}(s', a') - Q_{\phi}(s, a) \right)^2 \right]

其中 $\phi^-$ 为**目标网络（Target Network）**的参数，用于切断数据自举（Bootstrapping）带来的训练正反馈爆炸。为了保证求导时 Target 的稳定性，我们必须在代码或公式里明确使用 stop-gradient 算子：

$y = r + \gamma \max_{a'} \mathrm{sg}\left[Q_{\phi^-}(s', a')\right]$

DQN 针对 optimal policy 应用了 TD learning, 其目标函数为：

\min_{\phi} \mathcal{L}(\phi) = \mathbb{E}_{(s, a, r, s') \sim \mathcal{D}}\left[\frac{1}{2}\left(Q_{\phi}(s, a) - \left(r + \gamma \max_{a'} Q_{\phi}(s', a')\right)\right)^2\right]

这里 $\mathcal{D}$ 是 replay buffer, 存储了过去的 transition $(s, a, r, s')$ .

DQN 的两个关键技术：

Experience Replay: 使用 replay buffer 存储过去的 transitions，从中随机采样进行训练。这打破了数据之间的相关性，提高了样本效率.
Target Network: 使用一个独立的 target network $Q_{\phi^{-}}$ 来计算 TD target, 其参数 $\phi^{-}$ 定期从 $\phi$ 复制（或通过 Polyak averaging 更新）。这稳定了训练过程.

带有 target network 和 stop-gradient 的 DQN 目标函数为：

\mathcal{L}(\phi) = \mathbb{E}_{(s, a, r, s') \sim \mathcal{D}}\left[\frac{1}{2}\left(Q_{\phi}(s, a) - \left(r + \gamma \, \max_{a'} \mathrm{sg}[Q_{\phi^{-}}(s', a')]\right)\right)^2\right]

对应的 Python 实现：

# Compute current Q-values
q_values = Q_phi(states).gather(1, actions)

# Compute target Q-values with target network
with torch.no_grad():
    next_q_values = Q_target(next_states).max(1)[0]
    targets = rewards + gamma * next_q_values * (1 - dones)

# Compute loss
loss = 0.5 * (q_values - targets) ** 2
loss = loss.mean()

Algorithm: DQN with Experience Replay

Initialize replay buffer $\mathcal{D}$ with capacity $N$ .
Initialize Q-network $Q_{\phi}$ with random weights.
Initialize target network $Q_{\phi^{-}}$ with weights $\phi^{-} = \phi$ .
for episode = $1, \dots, M$ $1, \dots, M$ :
- $s_0 \sim p_0$ .
- for $t = 0, \dots, T-1$ $t = 0, \dots, T - 1$ :
  - Select action with $\epsilon$ -greedy: $a_t = \begin{cases} \arg\max_a Q_{\phi}(s_t, a), & \text{with prob } 1 - \epsilon \\ \text{random action}, & \text{with prob } \epsilon \end{cases}$
  - $(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)$ .
  - Store $(s_t, a_t, r_t, s_{t+1})$ in $\mathcal{D}$ .
  - Sample random minibatch $\{(s_i, a_i, r_i, s'_i)\}$ from $\mathcal{D}$ .
  - Compute target: $y_i = \begin{cases} r_i + \gamma \max_{a'} Q_{\phi^{-}}(s'_i, a'), & \text{if not terminal} \\ r_i, & \text{if terminal} \end{cases}$
  - Update Q-network: $\mathcal{L} = \frac{1}{|\text{batch}|} \sum_i \frac{1}{2} (Q_{\phi}(s_i, a_i) - y_i)^2, \quad \phi \gets \phi - \alpha \nabla_{\phi} \mathcal{L}$
  - Every $C$ steps: $\phi^{-} \gets \phi$ .

Why LLMs Usually Do Not Use DQN

Value-based control 建立了从 Bellman optimality equation 到可训练算法的桥梁，但 DQN 通常不是 LLM post-training 的最终选择：

LLM action space 是整个 vocabulary，每个 prefix 都要对大量 token 计算并比较 $Q(s,a)$
$\arg\max_a Q(s,a)$ 产生的 greedy policy 不等于我们希望保留和微调的 autoregressive policy distribution
LLM reward 常在完整 response 后给出，早期 token 的 Q target 具有严重的 credit-assignment 和 exploration 问题
预训练 LLM 已经提供了强 policy prior，直接优化 $\pi_\theta$ 通常比从 Q function 重新构造生成策略更自然

因此，本章的主要作用是解释 evaluation 如何变成 control, 并为 TD, off-policy learning 和 bootstrap 建立直觉。下一章将转向 policy-based methods：直接对 LLM policy 的 expected return 求梯度。

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，计算和内存开销更小.