Reinforcement Learning for Large Language models: An Overview

RL Basics

RL 的基本思想是让 agent 通过与环境交互，学习到最优策略。

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

RL 的执行过程如下所示

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

Markov Decision Process (MDP)

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): $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)$ .

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

当 $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$ 为网络参数。

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)$ .
本教程仅考虑 finite horizon MDP, 即 $T < \infty$ .

Expected Return

Expected (discounted) return 定义为：
$R(\tau) = \sum_{t=0}^{T-1} \gamma^t r_t$
其中 $\gamma \in (0, 1]$ 是 discount factor, 用于将未来的奖励折现到当前时刻。

我们还会使用另一个符号 $G_0$ 来表示 expected return：

G_0 = \sum_{t=0}^{T-1} \gamma^t r_t

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

G_0 = r_0 + \gamma G_1

Objective of RL

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

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

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

这里期望 $\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)$ .

Connection with LLM

LLM 的建模方式：

y_i \sim \mathrm{LLM}(\cdot \mid y_{<i}, x)

其中 $x$ 是输入的 prompt, $y_{<i}$ 是已经生成的部分， $y_i$ 是下一个要生成的 token.

RL 和 LLM 的对应关系如下：

RL	LLM
policy $\pi$	LLM $\mathrm{LLM}(\cdot \mid y_{<i}, x)$
initial state $s_0$	prompt $x$
action $a_t$	current token $y_i$
state $s_t$	context $(y_{<i}, x)$

注意到我们并没有对 environment 和 reward 进行建模，可以这样理解：

LLM 中的 environment 仅仅是对 token 进行简单拼接： $s_{t+1} = \mathrm{concat}(y_i, s_t)$ .
Reward 由 verifier, reward model (PRM, ORM) 或者 human feedback 给定.

Action Space and State Space for LLM

action = token index $y_i$ $\Rightarrow$ Action space = vocabulary of the LLM
state = context $(y_{<i}, x)$ $\Rightarrow$ State space = all possible contexts of the LLM

模型类别	模型名称	词表大小
商业闭源	GPT-5	$\sim$ 200,000
	Claude Sonnet 3.7	$\sim$ 100,000
	Gemini 3.0	$\sim$ 256,144
主流开源	Qwen 3	151,936
	DeepSeek-V3	129,280
	MiniMax-M2.5	200,064
	GLM-5	154,880

LLM 中，action space ( $|V|$ ) 非常大，state space ( $|V|^i$ ) 更大。

Classification

state and observation

State 包含了当前进行决策所需要的所有信息（环境信息，历史信息，agent 自身信息），此时 MDP 的 Markov 性质成立。如果 agent 获取的只是部分信息 (observation), 此时 MDP 特化为 Partially Observable Markov Decision Process (POMDP).

对于 LLM 来说，我们可以获取历史状态的所有信息，因此 RL for LLM 可视为一个 MDP 问题。

action space

Action space $\mathcal{A}$ 可以是离散的（如上下左右），也可以是连续的（如方向盘角度）。

episodic and continuing

根据任务的终止时间 $T$ ，分为 episodic task ( $T < \infty$ ) 和 continuing task ( $T = \infty$ )，如游戏 vs 股票预测。

为了方便分析，我们将 episodic MDP 转化为等价的不会停止的 MDP：

MDP never stops, 即 $T = \infty$ .
$s_t \in \mathcal{S} \cup \{\langle\text{term}\rangle\}$ , $\langle\text{term}\rangle$ 是一个 absorbing state.
当 $s_t = \langle\text{term}\rangle$ 时， $r_t = 0$ , $s_{t+1} = \langle\text{term}\rangle$ .
$\pi(\cdot \mid \langle\text{term}\rangle)$ 不产生任何影响.

Takeaway

RL 的基础是 MDP, 其核心假设是 Markov property, 即未来的状态和奖励只与当前状态和动作有关，与历史无关。
RL 通过 Reward Hypothesis, 将目标转化为最大化 expected return.
从 RL 角度看，LLM 本身是一个 policy, 其初始状态为 prompt, 动作空间为 vocabulary 中的 token index, 奖励由多方面给定，environment 仅对 token 进行简单拼接。
虽然 action space 和 state space 是离散的，但是其数量级非常大，因此我们通常使用函数逼近来近似 value function 和 Q-function.

Bellman Equations

Why Bellman Equation?

在强化学习中，我们关心的不是某一步立即得到的 reward，而是 agent 从当前状态出发，在未来持续决策后能够获得的 expected return.

但是，expected return 依赖于整条未来轨迹：后续会到达什么状态、采取什么动作、获得什么奖励，都是随机的。直接分析 expected return 往往比较困难。

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

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

Value Function and Q-Function

Definition: Value Function

我们定义 value function 如下：

V^{\pi}(s) = \mathbb{E}^{\pi}[G_0 \mid s_0 = s]

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

Definition: Q Function

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

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

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

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

Relationship between Value Function and Q-Function

由全概率公式，我们有：

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

即 value function 是 Q-function 的期望。

证明：

\begin{aligned} V^{\pi}(s) &= \mathbb{E}^{\pi}[G_0 \mid s_0 = s] \\ &= \sum_{a \in \mathcal{A}} \mathbb{E}^{\pi}[G_0 \mid s_0 = s, a_0 = a] \, \pi(a \mid s) \\ &= \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \, \pi(a \mid s) = \mathbb{E}_{a \sim \pi(\cdot \mid s)}[Q^{\pi}(s, a)] \end{aligned}

Iterative Property

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

\boxed{ \begin{aligned} V^{\pi}(s) &= \mathbb{E}_{a \sim \pi(\cdot \mid s), \, (r, s') \sim p(\cdot, \cdot \mid s, a)}[r + \gamma V^{\pi}(s') \mid s] \\ Q^{\pi}(s, a) &= \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a), \, a' \sim \pi(\cdot \mid s')}[r + \gamma Q^{\pi}(s', a') \mid s, a] \end{aligned} }

证明（以 value function 为例，利用 Markov property 和重期望定理）：

\begin{aligned} V^{\pi}(s) &= \mathbb{E}^{\pi}[G_0 \mid s_0 = s] \\ &= \mathbb{E}^{\pi}[r_0 + \gamma G_1 \mid s_0 = s] \\ &= \mathbb{E}_{a \sim \pi(\cdot \mid s), \, (r, s') \sim p(\cdot, \cdot \mid s, a)}\left[\mathbb{E}^{\pi}[r_0 + \gamma G_1 \mid s_0, a_0, r_0, s_1] \mid s_0 = s\right] \\ &= \mathbb{E}_{a \sim \pi(\cdot \mid s), \, (r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r_0 + \gamma \mathbb{E}^{\pi}[G_1 \mid s_1] \mid s_0 = s\right] \\ &= \mathbb{E}_{a \sim \pi(\cdot \mid s), \, (r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r_0 + \gamma V^{\pi}(s_1) \mid s_0 = s\right] \end{aligned}

这里第四个等式使用了 Markov property，即 $G_1$ 在已知 $s_1$ 的条件下与 $s_0, a_0, r_0$ 无关。

Q-function 的证明类似，略过.

Fixed Point Theorem (Background)

在证明 Bellman equation 的唯一性之前，我们先回顾不动点定理。

Definition: Contraction Mapping

对于函数 $f: \mathbb{R}^n \to \mathbb{R}^n$ , 如果存在点 $x^* \in \mathbb{R}^n$ 满足 $f(x^*) = x^*$ , 则称 $x^*$ 是 $f$ 的 fixed point.

如果存在 $\gamma \in (0, 1)$ 满足：

\|f(x_1) - f(x_2)\| \leq \gamma \|x_1 - x_2\|, \quad \forall x_1, x_2 \in \mathbb{R}^n

则我们称 $f$ 是一个 contraction mapping.

对于 contraction mapping, 其满足如下的不动点定理。

Theorem: Fixed Point Theorem

Fixed Point Theorem：给定函数 $f: \mathbb{R}^n \to \mathbb{R}^n$ , 如果 $f$ 是一个 contraction mapping, 则：

Existence: 存在 fixed point $x^*$ 满足 $f(x^*) = x^*$ .
Uniqueness: fixed point $x^*$ 唯一.
Algorithm: 对任意 $x_0 \in \mathbb{R}^n$ , 使用迭代 $x_{k+1} = f(x_k)$ 产生的序列 $\{x_k\}_{k=1}^{\infty}$ 收敛到 $x^*$ , 且收敛速度为指数级.

Bellman Equation Theorem (Value 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:

\boxed{ V^{\pi}(s) = \mathbb{E}_{a \sim \pi(\cdot \mid s), \, (r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V^{\pi}(s') \mid s\right] }

反之，如果存在函数 $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}$ 为：

(\mathcal{T}^{\pi} V)(s) := \mathbb{E}_{a \sim \pi(\cdot \mid s), \, (r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V(s') \mid s\right]

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

\begin{aligned} \left|(\mathcal{T}^{\pi} V_1)(s) - (\mathcal{T}^{\pi} V_2)(s)\right| &= \left|\mathbb{E}_{a \sim \pi(\cdot \mid s), \, (r, s') \sim p(\cdot, \cdot \mid s, a)}\left[\gamma V_1(s') - \gamma V_2(s')\right]\right| \\ &\leq \gamma \, \mathbb{E}_{a \sim \pi(\cdot \mid s), \, (r, s') \sim p(\cdot, \cdot \mid s, a)}\left|V_1(s') - V_2(s')\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}$ . $\blacksquare$

Bellman Equation Theorem (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, a) = \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a), \, a' \sim \pi(\cdot \mid s')}\left[r + \gamma Q^{\pi}(s', a') \mid s, a\right] }

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

Proof:

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

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 policy 对应的 optimal value function 是同一个.

Relationship between $V^*$ and $Q^*$ :

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

证明：

先证左边 $\leq$ 右边：

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

再证右边 $\leq$ 左边：令 $a^* \in \arg\max_{a} Q^*(s, a)$ , 令策略 $\pi'$ 为确定性策略 $\pi'(a^* \mid s) = 1$ , 则：

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

因此两边相等. $\blacksquare$

Bellman Optimality Equation Theorem

假设 $\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) = \max_{a \in \mathcal{A}} \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V^*(s') \mid s, a\right] }$
反之，如果存在函数 $V: \mathcal{S} \to \mathbb{R}$ 满足 Bellman optimality equation, 则 $V = V^*$ .

最后，可以给出一个 optimal deterministic policy:
$\pi^*(s) = \arg\max_{a \in \mathcal{A}} \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V^*(s') \mid s, a\right] = \arg\max_{a \in \mathcal{A}} Q^*(s, a)$

证明（概要）：

定义 Bellman optimality operator:

(\mathcal{T}^* V)(s) := \max_{a \in \mathcal{A}} \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V(s') \mid s, a\right]

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

\begin{aligned} \left|(\mathcal{T}^* V_1)(s) - (\mathcal{T}^* V_2)(s)\right| &= \left|\max_{a} \mathbb{E}[r + \gamma V_1(s')] - \max_{a} \mathbb{E}[r + \gamma V_2(s')]\right| \\ &\leq \max_{a} \left|\mathbb{E}[r + \gamma V_1(s')] - \mathbb{E}[r + \gamma V_2(s')]\right| \\ &= \gamma \max_{a} \left|\mathbb{E}[V_1(s') - V_2(s')]\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) = \arg\max_{a \in \mathcal{A}} \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V^*(s') \mid s, a\right]

然后可以验证 $V^* = V^{\pi^*}$ (通过展开递推), 且 $\pi^*$ 是最优策略 (对任意 $\pi$ , 有 $V^{\pi} \leq V^* = V^{\pi^*}$ ). $\blacksquare$

辅助 Lemma（省略证明）：

令 $\pi$ 为一个策略， $\mathcal{T}^{\pi}$ 和 $\mathcal{T}^*$ 分别是 Bellman operator 和 Bellman optimality operator:

对任意 $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}$ .

Bellman Optimality Equation (Q-Function Version)

假设 $\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, a) = \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma \max_{a' \in \mathcal{A}} Q^*(s', a') \mid s, a\right] }$
反之，如果存在函数 $Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ 满足 Bellman optimality equation, 则 $Q = Q^*$ .

证明与 value function 类似，略过.

Value Iteration

根据 BOE 定理的证明， $\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) &= \max_{a \in \mathcal{A}} \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V^k(s') \mid s, a\right] \\ \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^k(s') \mid s, a\right] \end{aligned}

类似地，还有 Q-value iteration:

\begin{aligned} Q^{k+1} &= \mathcal{T}^* Q^k \\ Q^{k+1}(s, a) &= \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma \max_{a' \in \mathcal{A}} Q^k(s', a') \mid s, a\right] \\ \pi^{k+1}(s) &= \arg\max_{a \in \mathcal{A}} Q^k(s, a) \end{aligned}

Summary

我们介绍了 value function 和 Q-function 的定义以及它们之间的联系，这是强化学习的核心概念.
我们介绍了 Bellman equation 和 Bellman optimality equation，BOE 定理是后续各种算法的核心.
我们基于 BOE 定理给出了 value iteration algorithm, 这是强化学习的基本算法，后续会对其进行改进.

Policy Evaluation

Why Policy Evaluation?

在强化学习中，我们通常希望回答一个基本问题：

给定一个策略 $\pi$ ，它到底”好不好”？

更具体地说，我们希望知道 agent 在不同状态下遵循该策略时，未来能够获得多大的长期回报.

这个问题本质上对应于求解策略 $\pi$ 的 value function $V^{\pi}$ . 虽然我们上一节已经知道 $V^{\pi}$ 满足 Bellman equation，并且，我们可以使用一个迭代解法来求解，但当状态空间较大、动作空间较大时，直接进行精确求解往往计算代价较高.

在本节中，我们将要介绍如何高效求解 value function $V^{\pi}$ . 核心思想：利用 Bellman equation、采样和函数逼近，高效地估计或拟合给定策略对应的 value function $V^{\pi}$ .

Monte Carlo

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

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

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

\{\tau^{(i)} = (s_0^{(i)}, 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, N

然后使用样本平均来近似期望：

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

如果 $\mathcal{S}$ 比较小，我们可以遍历 $s \in \mathcal{S}$ 来估计 $V^{\pi}$ . 但是，如果 $\mathcal{S}$ 比较大，这种方法的计算复杂度较高.

优点: 简单、直观、无需环境模型
缺点: 必须等轨迹结束后才能得到一次完整的估计

Objective of Value-Based Methods

当状态空间 $\mathcal{S}$ 较大或连续时，我们可以使用函数逼近的方法来近似 $V^{\pi}$ . 这里我们使用 $V_{\phi}$ 来近似 $V^{\pi}$ , 其中 $\phi$ 是函数的参数，使用最小二乘误差作为损失函数：

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

对目标函数求导：

\begin{aligned} \nabla_{\phi} \mathcal{L}(\phi) &= \mathbb{E}_{s_0 \sim p_0}\left[\left(V_{\phi}(s_0) - V^{\pi}(s_0)\right)\nabla_{\phi} V_{\phi}(s_0)\right] \\ &= \mathbb{E}_{s_0 \sim p_0}\left[\left(V_{\phi}(s_0) - \mathbb{E}^{\pi}[G_0 \mid s_0]\right)\nabla_{\phi} V_{\phi}(s)\right] \\ &= \mathbb{E}_{s_0 \sim p_0}\left[\mathbb{E}^{\pi}\left[\left(V_{\phi}(s_0) - G_0\right)\nabla_{\phi} V_{\phi}(s_0) \mid s_0\right]\right] \\ &= \mathbb{E}_{s_0 \sim p_0}^{\pi}\left[\left(V_{\phi}(s_0) - G_0\right)\nabla_{\phi} V_{\phi}(s_0) \mid s_0\right] \end{aligned}

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

\nabla_{\phi} \mathcal{L}(\phi) \approx g := \frac{1}{N}\sum_{i=1}^{N} \left(V_{\phi}(s^{(i)}) - R(\tau^{(i)})\right)\nabla_{\phi} V_{\phi}(s^{(i)})

结合 MC 和 SGD 的算法如下：

Algorithm: Value function approximation with MC

while not converged:

$s_0 \sim p_0$ , set $t = 0$ .
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)$
- $t \gets t + 1$
Set $T = t$ .
$g \gets \left(V_{\phi}(s_0) - \sum_{t=0}^{T-1} \gamma^t r_t\right)\nabla_{\phi} V_{\phi}(s_0)$ .
Update $\phi$ using $g$ with an optimizer.

Temporal Difference Learning

MC 的优势是可以得到一个无偏估计，但是其劣势在于我们必须完整采样完一条轨迹才能得到这个估计，对于 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]

Definition: TD Learning

TD learning 是一个通过新的信息和新的预测来更新旧的预测的学习范式. 对于 value function, 我们定义 TD target 为:

\overline{V}_t = r_t + \gamma V^{\pi}(s_{t+1})

定义 TD error 为

\delta_t = V^{\pi}(s_t) - \left(r_t + \gamma V^{\pi}(s_{t+1})\right)

当 $\mathcal{S}$ 比较大或连续时，我们构造损失函数：

\min_{\phi} \mathcal{L}(\phi) = \mathbb{E}_{s_0 \sim p_0}\left[\frac{1}{2}\left(V_{\phi}(s_0) - r_0 - \gamma V^{\pi}(s_1)\right)^2\right]

TODO: explain why we use TD error as objective

对应的梯度为：

\nabla_{\phi} \mathcal{L}(\phi) = \mathbb{E}_{s_0 \sim p_0}^{\pi}\left[\left(V_{\phi}(s_0) - r_0 - \gamma \boxed{V^{\pi}(s_1)}\right)\nabla_{\phi} V_{\phi}(s_0) \mid s_0\right]

这里使用了 $V^{\pi}(s_1)$ , 但这个值是未知的. 因此一个做法是使用当前的 value function $V_{\phi}$ 来进行代替：

\nabla_{\phi} \mathcal{L}(\phi) \approx \mathbb{E}_{s_0 \sim p_0}^{\pi}\left[\left(V_{\phi}(s_0) - r_0 - \gamma V_{\phi}(s_1)\right)\nabla_{\phi} V_{\phi}(s_0) \mid s_0\right]

这样，我们就得到了一个结合 TD 和 SGD 的 naive 算法：

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)$ .
computer 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) - \nabla_{\phi} V_{\phi}(s'))\\ &\neq g \end{aligned}

这显然与 $g$ 不相等.

为了解决这个问题，我们可以使用 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)$ .
computer 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 methods, 这类方法在参数更新时，只计算部分梯度。虽然这种方法牺牲了严格的梯度下降性质，但是其能够保证更好的表现.

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}[\mathbb{E}^{\pi}[r_0 + \gamma r_1 + \gamma^2 V^{\pi}(s_2) \mid s_1] \mid s_0] \end{aligned}

由 Law of total expectation：

\mathbb{E}^{\pi}[\mathbb{E}^{\pi}[X \mid s_1] \mid s_0 = s] = \mathbb{E}^{\pi}[X \mid s_0]

因此：

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

重复这个过程 k 次，我们就可以得到 k 步展开：

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$ :
- $a_t \sim \pi(\cdot \mid s_t)$
- $(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)$
compute k-step TD target $y = \begin{cases} \sum_{t=0}^{k-1} \gamma^t r_t + \gamma^k \, \mathrm{sg}[V_{\phi}(s_k)], & \text{if } s_k \neq \langle\text{term}\rangle \\ \sum_{t=0}^{k-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.

一般来说， $k = 5$ 是一个常用的选择.

MC v.s. TD

方法	特点
MC	需要完整的一次采样，无偏但 variance 高
TD	通过 bootstrap 提高采样效率，有偏但 variance 低

TD 本质上是 bootstrap: 当需要使用 $V^{\pi}$ 时，用 $V_{\phi}$ 来代替. 当 $V_{\phi}$ 与 $V^{\pi}$ 差距较大时，bootstrap 会导致训练不稳定，而 MC 则相对稳定.

Q-Function Evaluation

对于 Q-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}{N} \sum_{i=1}^{N} \sum_{t=0}^{T^{(i)}-1} \gamma^t r_t^{(i)}

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

\min_{\phi} \mathcal{L}(\phi) = \mathbb{E}_{s_0 \sim p_0, \, a_0 \sim \pi(\cdot \mid s_0)}\left[\frac{1}{2}\left(Q_{\phi}(s_0, a_0) - Q^{\pi}(s_0, a_0)\right)^2\right]

对应的梯度：

\nabla_{\phi} \mathcal{L}(\phi) = \mathbb{E}_{s_0 \sim p_0, \, a_0 \sim \pi(\cdot \mid s_0)}^{\pi}\left[\left(Q_{\phi}(s_0, a_0) - \sum_{t=0}^{T-1} \gamma^t r_t\right)\nabla_{\phi} Q_{\phi}(s_0, a_0)\right]

对应的算法如下

Algorithm: Q-function approximation with MC

while not converged:

$s_0 \sim p_0$ , $a_0 \sim \pi(\cdot \mid s_0)$ , set $t = 0$ .
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)$
- $t \gets t + 1$
Set $T = t$ .
$g = \left(Q_{\phi}(s_0, a_0) - \sum_{t=0}^{T-1} \gamma^t r_t\right) \nabla_{\phi} Q_{\phi}(s_0, a_0)$ .
Update $\phi$ using $g$ with an optimizer.

对于TD learning, 与 value function 的算法类似，我们也由对应版本的算法：

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)$ , $a_1 \sim \pi(\cdot \mid s_1)$ .
$y = \begin{cases} r_0 + \gamma \, \mathrm{sg}[Q_{\phi}(s_1, a_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.

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$ :
- $a_t \sim \pi(\cdot \mid s_t)$
- $(r_t, s_{t+1}) \sim p(\cdot, \cdot \mid s_t, a_t)$
$y = \sum_{t=0}^{k-1} \gamma^t r_t + \gamma^k \, \mathrm{sg}[Q_{\phi}(s_k, a_k)]$
$g = (Q_{\phi}(s_0, a_0) - y) \nabla_{\phi} Q_{\phi}(s_0, a_0)$
Update $\phi$ using $g$ with an optimizer.

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:

TODO

Value-Based Methods

TODO

Q-learning
SARSA
DQN

Value-based methods 的核心思想是：给当前策略 $\pi$ 一个引导，让 agent 学会执行能达到更有价值的 states 的策略。

在 Bellman Equation 中，我们介绍了 value iteration 的基本思路：通过 Bellman optimality operator 迭代求解 $V^*$ 和 $Q^*$ . 本节将 value iteration 的思想与函数逼近、TD learning 等技术结合，得到实用的 value-based 算法.

From Value Iteration to Function Approximation

Value iteration 的更新公式为：

\begin{aligned} V^{k+1}(s) &= \max_{a \in \mathcal{A}} \mathbb{E}_{(r, s') \sim p(\cdot, \cdot \mid s, a)}\left[r + \gamma V^k(s') \mid s, a\right] \\ \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^k(s') \mid s, a\right] \end{aligned}

当状态空间较大或连续时，我们需要使用函数逼近. 用 $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})$

DQN (Deep Q-Network)

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()

DQN Algorithm

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

Extensions of DQN

Double DQN: 解决 DQN 中 max operator 导致的价值高估 (overestimation) 问题. 使用 online network 选择 action, target network 评估 value:

y_i = r_i + \gamma \, Q_{\phi^{-}}\left(s', \arg\max_{a'} Q_{\phi}(s', a')\right)

Dueling DQN: 将 Q-function 分解为 value function 和 advantage function:

Q(s, a) = V(s) + \left(A(s, a) - \frac{1}{|\mathcal{A}|}\sum_{a'} A(s, a')\right)

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 降低方差

Connection with LLM

对于 LLM，action space 很大 (词表大小 $\sim 10^5$ ), 直接应用 value-based 方法中的 $\max_{a'} Q(s', a')$ 操作计算代价极高. 因此，在 RL for LLM 中，policy-based methods (如 PPO, GRPO) 更为常用. 但 value-based 方法的思想（如 advantage estimation, TD learning）仍然是 policy-based 方法的重要组成部分.

Policy Based Methods

policy-based methods 的 motivation 很好理解，我们想要找到一个 optimal policy, 那我们就直接对当前 policy 进行优化。

我们基于某个策略采集一些数据，通过直接优化的方法来不停改进当前策略 $\pi$ , 直到当前策略达到最优

根据采样策略的不同，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, TRPO	DQN, DDPG
sampled from	current policy	arbitrary policy
exploration	yes	no
infra efficiency	low (needs to generate new sample)	high
training stability	unstable	more stable
compute cost	high	low
best for	exploration is needed	reused past experiences

Policy Gradient Theorem

我们的目标与前面一致，仍然是最大化累计奖励，目标函数为

\max_{\pi}\mathcal{J}(\theta)=\mathbb{E}_{s_0\sim p_0}\left[V^{\pi_\theta}(s_0)\right]=\mathbb{E}_{s_0\sim p_0}^{\pi_\theta}\left[\sum_{t=0}^{T-1}\gamma^tr_t\right]

我们首先将采集到的轨迹数据 $\tau$ 进行展开

\tau = (s_0,a_0,r_0,\dots,s_{T-1}, a_{T-1}, r_{T-1}, s_T)

$\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)

我们使用 cumulative return 的定义，就得到

\mathcal{J}(\theta)=\mathbb{E}_{s_0\sim p_0}^\pi\left[\sum_{t=0}^{T-1}\gamma^tr_t\right] = \mathbb{E}_{s_0\sim p_0,a_t\sim\pi_\theta(\cdot\mid s_t), (r_t,s_{t+1})\sim p(\cdot,\cdot\mid s_t,a_t)}^\pi\left[\sum_{t=0}^{T-1}\gamma^tr_t\right] = \mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[G_0(\tau)\right]

此时，目标函数的梯度为

\begin{align} \nabla_\theta \mathcal{J}(\theta)&=\nabla_\theta\mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[G_0(\tau)\right]\\ &= \sum_\tau G_0(\tau)\nabla_\theta p_\theta(\tau)\\ &= \sum_\tau p_\theta(\tau)G_0(\tau) \nabla_\theta \log p_\theta(\tau)\\ &= \mathbb{E}_{\tau\sim(p_0,\pi_\theta, p)}\left[G_0(\tau)\nabla_\theta \log p_\theta(\tau)\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)G_0(\tau)\right] \end{align}

这里我们使用了如下不等式

\nabla_\theta p_\theta(\tau)=p_\theta(\tau)\nabla_\theta \log p_\theta(\tau)

以及

\nabla_\theta \log 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] = \sum_{t=0}^{T-1}\log\pi_\theta(a_t\mid s_t)

一些教材上还有另一种表达形式，使用了 Q-function, 即

\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(s_t,a_t)\right]

我们可以对其进行证明，证明需要用到 Expectation 中的全概率公式。注意到

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

这里第三个等式使用了全概率公式，第四个等式是因为 $\nabla_\theta \log\pi_\theta(a_t\mid s_t)$ 相对于 $\tau_{:t}$ 来说是一个常数，第五个等式是因为 Markov property, 最后一个等式使用了 Q-function 的定义。

Vanilla Policy Gradient Methods

令

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

由 $\nabla_\theta \mathcal{J}(\theta)$ 定义，我们知道 $\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$ $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.

Variance Reduction

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

我们本节主要介绍如何减少 $g$ 作为估计的方差，这里需要用到 policy gradient baseline invariance 的性质

Baseline Invariance

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

: Baseline Invairance of Policy Gradient

我们有如下等式

\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$ 是一个仅与状态有关的函数或者常数。

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 invairance property.

上述等式说明我们可以通过改变 $b$ 来调整 policy gradient 的 variance, 我们将 $b(s_t)$ 称为 baseline.

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 中的最优 basline:

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

理论上我们可以使用 $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.

Rao–Blackwell Theorem

我们在前面介绍了不同的降低 variance 的方法，但是我们还没有在理论上回答为什么可以降低 variance, 本节我们将基于 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 说明了我们可以通过构造一个新的无偏估计，这个新的无偏估计相对于原始的无偏估计，有更小的方差。

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

Actor Critic Methods

在上一节中，我们介绍了经典的 policy gradient 形式，并基于 policy gradient 构建了经典的 REINFORCE 算法，我们还使用了 baseline invariance 性质来降低 policy gradient 的 variance, 并得到了最终的 advantage 形式。

在本节中，我们将要针对 advantage 进行进一步探讨，介绍如何将 value based methods 和 policy based methods 结合起来得到 actor-critic methods.

TODO

actor-critic
A2C/A3C
GAE

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 methods 的 sample efficiency.

在上一节中介绍的 REINFORCE 算法中，我们每次都需要基于当前策略 $\pi_\theta$ 来进行采样。因此，算法的效率受策略 $\pi_\theta$ 采样效率影响。

一个自然的想法是，我们能否利用已有的数据集来进行训练，也就是 off-policy 版本的 policy gradient algorithm. 这就是 Trust Region Policy Optimization (TRPO) (Schulman et al., 2015) 算法的核心。

我们的目标函数为

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