# Reinforcement Learning

Author: Fanyi Pu

Published: 2024-10-16

Updated: 2026-09-12

Canonical: <https://pufanyi.com/blog/ml/ml-revisit/rl>

RL 学习笔记：policy gradient、actor-critic、TRPO、PPO、DPO 与 GRPO，以及 human feedback 和 binary rewards 的一些推导。

[Berkeley CS285](https://rail.eecs.berkeley.edu/deeprlcourse/) / [Stanford CS224R](https://cs224r.stanford.edu/) / [Yezhen 学长推荐嘟](https://zhuanlan.zhihu.com/p/7461863937) / [Li Bo 学长推荐嘟](https://hijkzzz.notion.site/Jian-Hu-s-Blogpost-147d9a33ecc980d89400c3006d4173c2)

## Definition

我们把 $\langle s_t,a_t\rangle$ 打包起来，在 Markov 环境和只依赖当前 state 的策略下，其实它就构成了一个 Markov chain。记一条轨迹为 $\tau=(s_1,a_1,\ldots,s_T,a_T,s_{T+1})$：

$$
p_\theta(\tau)
=p(s_1)\prod_{t=1}^T
\pi_\theta(a_t\mid s_t)\mathbb{P}(s_{t+1}\mid s_t,a_t).
$$

这里 $\pi_\theta(a_t\mid s_t)$ 是策略，$\mathbb P$ 是环境转移；初始状态分布与环境转移不依赖 $\theta$。后文也把整条轨迹的分布 $p_\theta(\tau)$ 简记为 $\pi_\theta(\tau)$。

对于 learning objective：

$$
\theta^*=\arg\max_\theta\mathcal J(\theta)
=\arg\max_\theta\mathbb E_{\tau\sim\pi_\theta}[r(\tau)].
$$

我们定义我现在在 $s_t$，做了 action $a_t$，然后按照 $\pi$ 所得到的期望总 reward 为

$$
\mathcal Q^\pi(s_t,a_t)
=\mathbb E_\pi\left[
\sum_{t'=t}^T r(s_{t'},a_{t'})\mid s_t,a_t
\right].
$$

然后我们定义 $\mathcal V$ 表示现在我在 $s_t$ 的时候遵循 $\pi$ 所得到的期望总 reward：

$$
\begin{aligned}
\mathcal V^\pi(s_t)
&=\mathbb E_\pi\left[\sum_{t'=t}^T r(s_{t'},a_{t'})\mid s_t\right]\\
&=\mathbb E_{a_t\sim\pi(\cdot\mid s_t)}[\mathcal Q^\pi(s_t,a_t)].
\end{aligned}
$$

先考虑有限时域、不打折的 return；有限时域中把剩余时间也视为 state 的一部分，并令终止状态的 value 为 $0$。后面再引入 discount factor。

## Types of Algorithms

- **Policy Gradients**：跟往常一样，就是求导然后去做优化。
- **Value-based**：去估计最优的 $\mathcal Q$ 或 $\mathcal V$，然后通过这个推出 $\pi$。
- **Actor-critic**：通过估计当前策略的 $\hat{\mathcal Q}$ 和 $\hat{\mathcal V}$，然后用它们指导策略优化。
- **Model-based RL**：学习或使用环境的转移、reward 模型，再借助模型规划或优化策略。

## Policy Gradient Algorithms

### Direct policy differentiation

记整条轨迹的总 reward 为 $r(\tau)=\sum_{t=1}^T r(s_t,a_t)$，我们想最大化它在当前策略下的期望：

$$
\mathcal{J}(\theta)
=\mathbb{E}_{\tau\sim\pi_\theta}[r(\tau)]
=\int\pi_\theta(\tau)r(\tau)\,\mathrm{d}\tau.
$$

采样得到一条 $\tau$ 后，很容易觉得：既然有它的概率 $\pi_\theta(\tau)$，又有它的 reward $r(\tau)$，那就直接最大化两者的乘积。这里漏掉了积分：**$\pi_\theta(\tau)r(\tau)$ 只是被积函数在这条轨迹上的取值，目标 $\mathcal J(\theta)$ 是对所有轨迹的积分。** 如果能算出整个积分，直接对 $\mathcal J$ 求导当然可以；但只拿到一条采样轨迹时，直接对这个乘积求导，并不能给出整个目标梯度的无偏估计。

实际训练通常无法遍历所有轨迹，只能按当前策略采样。我们希望每条样本给出一个梯度，平均起来就能无偏地估计整个目标的梯度。**下面推导的目的，就是把 $\nabla_\theta\mathcal J(\theta)$ 写成一个可以用采样估计的期望，从而确定每条样本应该贡献什么梯度。**

沿用环境与 reward 不依赖 $\theta$ 的假设，在积分与求导可以交换的条件下，利用 $\nabla_\theta\log\pi_\theta(\tau)=\nabla_\theta\pi_\theta(\tau)/\pi_\theta(\tau)$，得到 REINFORCE ([Williams, 1992](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-williams1992simple)) 的梯度表达式：

$$
\begin{aligned}
\nabla_\theta \mathcal{J}(\theta)
&= \int r(\tau)\nabla_\theta\pi_\theta(\tau)\,\mathrm{d}\tau \\
&= \int \pi_\theta(\tau)\frac{\nabla_\theta\pi_\theta(\tau)}{\pi_\theta(\tau)}r(\tau)\,\mathrm{d}\tau \\
&= \mathbb{E}_{\tau\sim\pi_\theta}\left[
r(\tau)\nabla_\theta\log\pi_\theta(\tau)
\right].
\end{aligned}
$$

这就告诉我们，对 $\tau\sim\pi_\theta$，$r(\tau)\nabla_\theta\log\pi_\theta(\tau)$ 是所需的无偏梯度估计。为了用反向传播得到它，取下面的 loss ([Achiam, 2018](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-spinningup2018))，求导时固定采到的轨迹和 reward：

$$
\begin{aligned}
\ell_\theta(\tau)&=-r(\tau)\log\pi_\theta(\tau),\\
-\nabla_\theta\ell_\theta(\tau)
&=r(\tau)\nabla_\theta\log\pi_\theta(\tau).
\end{aligned}
$$

负号用于把最大化写成梯度下降。使用 $\log\pi_\theta(\tau)$ 的理由就在这里：**这个 loss 的负梯度，在采样所用的策略参数处，是目标梯度的无偏估计。**

实现时，由于初始状态分布和环境转移与 $\theta$ 无关，有

$$
\nabla_\theta\log\pi_\theta(\tau)
=\sum_{t=1}^T\nabla_\theta\log\pi_\theta(a_t\mid s_t).
$$

因此，对一条轨迹，把实际采到的各步 action 的 log probability 相加，再乘总 reward 即可：

```python
trajectory_log_prob = action_log_probs.sum()
loss = -trajectory_return.detach() * trajectory_log_prob
```

这里 `trajectory_return` 是总奖励，求导时作为常量；`action_log_probs` 保留策略参数的计算图。对一个 batch，再平均各条轨迹的 loss。这个估计虽然无偏，但 variance 很高，接下来考虑怎么减小它。

### Reduce Variance

仔细观察这个式子，其实这玩意儿是 MLE 那个梯度对 $r(s_t,a_t)$ 加权了：

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

当前我们是有：$\Psi_t=\sum_{t'=1}^T r(s_{t'},a_{t'})$

### Don't Let the Past Distract You

一种简单的方法来减小 variance，是我们令 $\Psi_t=\sum_{t'=t}^T r(s_{t'},a_{t'})$

因为其实对于 $a_t$ 来说，他做啥对于 $t$ 之前的 reward 来说是不具有参考价值的。因此我们主要考虑后面的 reward。这玩意儿直觉上挺清楚的，但数学上想了半天才想明白为啥是对的。主要参考了[这篇文章](https://spinningup.openai.com/en/latest/spinningup/extra_pg_proof1.html) ([Achiam, 2018](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-spinningup2018))。

证明的不造为啥让我想起了 MLE。主要用到的就是一个叫做 EGLP lemma 的东西（其实好像用这个 lemma 需要积分和导数的可交换性，貌似 ([Hogg et al., 2013](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-hogg2013introduction)) 里写挺详细的）：

$$
\begin{aligned}
\mathbb{E}_{x\sim\mathbb{P}_\theta}\left[\nabla_\theta\log\mathbb{P}_\theta(x)\right]
&= \int\mathbb{P}_\theta(x)\nabla_\theta\log\mathbb{P}_\theta(x)\,\mathrm{d}x \\
&= \int\mathbb{P}_\theta(x)\frac{\nabla_\theta\mathbb{P}_\theta(x)}{\mathbb{P}_\theta(x)}\,\mathrm{d}x \\
&= \nabla_\theta\int\mathbb{P}_\theta(x)\,\mathrm{d}x=0
\end{aligned}
$$

其实跟 MLE 是一样的嘛：

$$
\mathbb{E}\left[\frac{\partial}{\partial\theta}\log\mathcal{L}(x\mid\theta)\right]=0
$$

其实我们是要证明嘟是：

$$
\mathbb{E}_{\tau\sim\pi_\theta}\left[
\sum_{t=1}^T\sum_{t'<t}r(s_{t'},a_{t'})\nabla_\theta\log\pi_\theta(a_t\mid s_t)
\right]=0
$$

也就是要证明当 $t'<t$ 这个时候：

$$
\mathbb{E}_{s_t,a_t,s_{t'},a_{t'}\sim\pi_\theta}\left[
r(s_{t'},a_{t'})\nabla_\theta\log\pi_\theta(a_t\mid s_t)
\right]=0
$$

那么中心思想其实就是咋来区分 $t'<t$ 捏，我们考虑 $t'<t$ 是先 reward，再选择：

$$
\mathbb{E}_{s_{t'},a_{t'}\sim\pi_\theta}\left[
r(s_{t'},a_{t'})\cdot
\mathbb{E}_{s_t,a_t\sim\pi_\theta(\cdot\mid s_{t'},a_{t'})}\left[
\nabla_\theta\log\pi_\theta(a_t\mid s_t)\mid s_{t'},a_{t'}
\right]
\right]
$$

关键是先固定过去的历史，再对当前 action 取条件期望：给定 $s_t$，有 $\mathbb E_{a_t\sim\pi_\theta(\cdot\mid s_t)}[\nabla_\theta\log\pi_\theta(a_t\mid s_t)]=0$。过去的 reward 可以和当前 state 相关，但不会由之后采样的 action 改写。

所以说最终结果是整个期望 $0$。

### Introducing Baselines

另一个优化是我们考虑加入 baseline。这个直觉就更对了。就是我们考虑把 $r(s,a)$ 替换成 $r(s,a)-b$。这里减去的是梯度估计器中的 baseline，不是在改环境的 reward；baseline 不依赖当前 action 时，它乘上 score gradient 的期望为零。

当然从数学上来讲也是 EGLP 用用易证的，这里就不多写了。但是我们 baseline 设多少最好呢？从直觉上来讲，是这个 $b$ 让整个 $r$ 尽量居中。接下来我们从数学上进行考虑。

我们考虑

$$
\nabla_\theta\mathcal{J}(\theta)
= \mathbb{E}_{\tau\sim\pi_\theta}\left[
\nabla_\theta\log\pi_\theta(\tau)\cdot(r(\tau)-b)
\right]
$$

的方差（对于向量梯度，这里取各分量方差之和）

$$
\begin{aligned}
\sigma^2
&= \mathbb{E}_{\tau\sim\pi_\theta}\left[
\left\|\nabla_\theta\log\pi_\theta(\tau)\cdot(r(\tau)-b)\right\|^2
\right] \\
&\quad -\left\|\mathbb{E}_{\tau\sim\pi_\theta}\left[
\nabla_\theta\log\pi_\theta(\tau)\cdot(r(\tau)-b)
\right]\right\|^2 \\
&= \mathbb{E}_{\tau\sim\pi_\theta}\left[
\left\|\nabla_\theta\log\pi_\theta(\tau)\cdot(r(\tau)-b)\right\|^2
\right] \\
&\quad -\left\|\mathbb{E}_{\tau\sim\pi_\theta}\left[
\nabla_\theta\log\pi_\theta(\tau)\cdot r(\tau)
\right]\right\|^2
\end{aligned}
$$

我们解

$$
\frac{\partial}{\partial b}\sigma^2
= \frac{\partial}{\partial b}\mathbb{E}_{\tau\sim\pi_\theta}\left[
\left\|\nabla_\theta\log\pi_\theta(\tau)\cdot(r(\tau)-b)\right\|^2
\right]=0
$$

可以得到

$$
b=\frac{
\mathbb{E}_{\tau\sim\pi_\theta}\left[\left\|\nabla_\theta\log\pi_\theta(\tau)\right\|^2\cdot r(\tau)\right]
}{
\mathbb{E}_{\tau\sim\pi_\theta}\left[\left\|\nabla_\theta\log\pi_\theta(\tau)\right\|^2\right]
}
$$

这啥捏，这其实是 reward 的加权期望。

但其实这个 baseline 挺难算的，所以我们通常不会用这个最优的 baseline。而是去找一个相对比较好的。

### Off-Policy Policy Gradients

之前我们做的都是 on-policy 的。但真实在训练的时候，我们很难做到稍稍改一点 $\theta$，就重新生成一堆新的 $\tau$。这样是非常 inefficient 的。

所以现在可能的问题是，我们没有关于 $\tau\sim\pi_\theta$ 的数据，但是我们可能有一个其他的 distribution，通过这个 distribution 来 sample 出的数据。也就是 $\tau\sim\overline{\pi}$。

我们需要使用的一个 trick 叫做 importance sampling：

$$
\begin{aligned}
\mathbb{E}_{x\sim p(x)}[f(x)]
&= \int p(x)f(x)\,\mathrm{d}x \\
&= \int q(x)\frac{p(x)}{q(x)}f(x)\,\mathrm{d}x \\
&= \mathbb{E}_{x\sim q(x)}\left[\frac{p(x)}{q(x)}f(x)\right]
\end{aligned}
$$

所以说我们的 RL objective 可以改成：

$$
\begin{aligned}
\mathcal{J}(\theta)
&= \mathbb{E}_{\tau\sim\overline{\pi}}\left[
\frac{\pi_\theta(\tau)}{\overline{\pi}(\tau)}r(\tau)
\right] \\
&= \mathbb{E}_{\tau\sim\overline{\pi}}\left[
\frac{p(s_1)\prod_{t=1}^T\pi_\theta(a_t\mid s_t)p(s_{t+1}\mid s_t,a_t)}
{p(s_1)\prod_{t=1}^T\overline{\pi}(a_t\mid s_t)p(s_{t+1}\mid s_t,a_t)}
r(\tau)
\right] \\
&= \mathbb{E}_{\tau\sim\overline{\pi}}\left[
r(\tau)\prod_{t=1}^T\frac{\pi_\theta(a_t\mid s_t)}{\overline{\pi}(a_t\mid s_t)}
\right]
\end{aligned}
$$

所以说我们可以推导梯度

$$
\begin{aligned}
\nabla_\theta\mathcal{J}(\theta)
&= \mathbb{E}_{\tau\sim\overline{\pi}}\left[
\frac{\pi_\theta(\tau)}{\overline{\pi}(\tau)}\nabla_\theta\log\pi_\theta(\tau)r(\tau)
\right] \\
&= \mathbb{E}_{\tau\sim\overline{\pi}}\left[
\left(\prod_{t=1}^T\frac{\pi_\theta(a_t\mid s_t)}{\overline{\pi}(a_t\mid s_t)}\right)
\left(\sum_{t=1}^T\nabla_\theta\log\pi_\theta(a_t\mid s_t)\right)
\left(\sum_{t=1}^T r(s_t,a_t)\right)
\right] \\
&= \mathbb{E}_{\tau\sim\overline{\pi}}\Biggl[
\sum_{t=1}^T\nabla_\theta\log\pi_\theta(a_t\mid s_t)
\left(\prod_{t'=1}^t\frac{\pi_\theta(a_{t'}\mid s_{t'})}{\overline{\pi}(a_{t'}\mid s_{t'})}\right) \\
&\qquad\qquad\cdot\left(
\sum_{t'=t}^T r(s_{t'},a_{t'})
\prod_{t''=t+1}^{t'}\frac{\pi_\theta(a_{t''}\mid s_{t''})}{\overline{\pi}(a_{t''}\mid s_{t''})}
\right)
\Biggr]
\end{aligned}
$$

## Actor Critic Methods

### General Idea

我们回到式子

$$
\nabla_\theta\mathcal J(\theta)
\approx\frac1N\sum_{i=1}^N\sum_{t=1}^T
\Psi_{i,t}\nabla_\theta\log\pi_\theta(a_{i,t}\mid s_{i,t}).
$$

我们观察这个 $\Psi_t$（先不考虑 baseline）：$\Psi_t=\sum_{t'=t}^T r(s_{t'},a_{t'})$。

我们发现一件事情，就是它其实是在估计 $\mathcal Q^\pi(s_t,a_t)$。也就是我做了这个 action，之后继续按照 $\pi$，会得到一个什么样的结果。这个和是 $\mathcal Q^\pi(s_t,a_t)$ 的一个无偏估计。

于是我们可以尝试 $\Psi_t=\mathcal Q^\pi(s_t,a_t)$。我的理解是，如果能算出这个条件期望，就可以去掉后续轨迹采样带来的部分噪声。

然后我们考虑 baseline。我们大概这么想，就是某个操作比我现在的平均效果好，那么 $\Psi_t$ 要大于 $0$，让它的概率增大。如果比我现在的 $\pi$ 还要垃圾，就减小这个 action 的概率。

所以我们考虑 $b=\mathcal V^\pi(s_t)$，于是我们定义：

$$
\mathcal A^\pi(s_t,a_t)
=\mathcal Q^\pi(s_t,a_t)-\mathcal V^\pi(s_t).
$$

也就是做了这个操作，相比当前策略的平均表现能好多少。然后

$$
\nabla_\theta\mathcal J(\theta)
\approx\frac1N\sum_{i=1}^N\sum_{t=1}^T
\mathcal A^\pi(s_{i,t},a_{i,t})
\nabla_\theta\log\pi_\theta(a_{i,t}\mid s_{i,t}).
$$

在采样策略就是 $\pi=\pi_\theta$、advantage 使用真值或条件无偏估计的情况下，这东西是无偏的。那我们考虑怎么算这个 $\mathcal A^\pi(s_t,a_t)$。

我们考虑

$$
\mathcal Q^\pi(s_t,a_t)
=r(s_t,a_t)+\mathbb E_{s_{t+1}\sim\mathbb P(\cdot\mid s_t,a_t)}
[\mathcal V^\pi(s_{t+1})].
$$

所以说

$$
\mathcal A^\pi(s_t,a_t)
=\mathbb E_{s_{t+1}\sim\mathbb P(\cdot\mid s_t,a_t)}
[r(s_t,a_t)+\mathcal V^\pi(s_{t+1})-\mathcal V^\pi(s_t)].
$$

也就是说，$r(s_t,a_t)+\mathcal V^\pi(s_{t+1})-\mathcal V^\pi(s_t)$ 是对 $\mathcal A^\pi(s_t,a_t)$ 的一个条件无偏估计。这里需要真实的 $\mathcal V^\pi$；换成学出来的近似值后，一般会引入 bias。

也就是我们现在的问题来到了怎么搞这个 $\mathcal V^\pi$，最直接的方法是大力去做，然后求平均。

当然，更成熟的想法是我们可以训一个模型 $\phi$ 去预测这个 $\mathcal V^\pi$。我们考虑 loss，一种直接的方法是：

$$
\mathcal L(\phi)
=\frac12\sum_{i=1}^N\sum_{t=1}^T
\left\|
\hat{\mathcal V}_\phi^\pi(s_{i,t})
-\sum_{t'=t}^T r(s_{i,t'},a_{i,t'})
\right\|^2.
$$

但是我们考虑有没有方差更低一些的方法，就是用 $r(s_t,a_t)+\hat{\mathcal V}_\phi^\pi(s_{t+1})$ 来代替整个求和。这就变成了 TD error 的平方：

$$
\mathcal L(\phi)
=\frac12\sum_{i=1}^N\sum_{t=1}^T
\left\|
\hat{\mathcal V}_\phi^\pi(s_{i,t})
-\operatorname{sg}\!\left[
r(s_{i,t},a_{i,t})+\hat{\mathcal V}_\phi^\pi(s_{i,t+1})
\right]
\right\|^2.
$$

这里 $\operatorname{sg}$ 表示 stop-gradient：当前更新把 bootstrap target 当作固定目标。它降低了对完整 Monte Carlo return 的依赖，但 target 本身的估计误差也会传过来。

### Introducing Discount Factors

有时候我们会考虑 $T\to\infty$ 的情况。为了在 reward 有界时让总 return 也是有穷的，我们可以取 $0\le\gamma<1$，增加一个 discount factor。这个其实是比较直觉的，因为现在给你一块钱和以后给你一块钱，肯定选马上要。

$$
r(\tau)=\sum_{t=1}^T\gamma^{t-1}r(s_t,a_t).
$$

那么我们就需要稍稍改一改式子。此时 $\mathcal V^{\pi,\gamma}$ 从当前时刻开始计算折扣 return：

$$
\mathcal A^{\pi,\gamma}(s_t,a_t)
=\mathbb E_{s_{t+1}\sim\mathbb P(\cdot\mid s_t,a_t)}
\left[r(s_t,a_t)+\gamma\mathcal V^{\pi,\gamma}(s_{t+1})
-\mathcal V^{\pi,\gamma}(s_t)\right].
$$

这时候其实我们在估计导数的时候，要小心折扣的位置。直接用整条轨迹的 return，可以写成：

$$
\nabla_\theta\mathcal J(\theta)
\approx\frac1N\sum_{i=1}^N
\left(\sum_{t=1}^T\gamma^{t-1}r(s_{i,t},a_{i,t})\right)
\left(\sum_{t=1}^T\nabla_\theta\log\pi_\theta(a_{i,t}\mid s_{i,t})\right).
$$

利用 reward-to-go，也可以使用下面的估计量：

$$
\hat g
=\frac1N\sum_{i=1}^N\sum_{t=1}^T
\gamma^{t-1}\nabla_\theta\log\pi_\theta(a_{i,t}\mid s_{i,t})
\left(\sum_{t'=t}^T\gamma^{t'-t}r(s_{i,t'},a_{i,t'})\right).
$$

外层的 $\gamma^{t-1}$ 与 return 内的 $\gamma^{t'-t}$ 作用不同，不能直接漏掉。两种估计量的期望相同，同一批轨迹上算出的数值不必相同。Thomas ([Thomas, 2014](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-thomas2014bias)) 专门讨论了 discount 与 policy gradient bias 的问题，有空填坑。

### Implementation Details

在真正写代码的时候，我们需要构造一个能产生 policy gradient 的 surrogate。和前面 REINFORCE 的 loss 一样，考虑一个看似无意义的函数：

$$
\widetilde{\mathcal J}(\theta)
=\frac1N\sum_{i=1}^N\sum_{t=1}^T
\operatorname{sg}\!\left[\hat{\mathcal A}_\phi(s_{i,t},a_{i,t})\right]
\log\pi_\theta(a_{i,t}\mid s_{i,t}).
$$

求导时，采到的 state、action 和 $\hat{\mathcal A}_\phi$ 都作为常量，所以这个 $\nabla_\theta\widetilde{\mathcal J}(\theta)$ 就是相应的 actor gradient 估计。也就是说，我们其实是借助自动求导程序去计算前面推出来的更新。它的数值不是 $\mathcal J(\theta)$；critic 若有误差，也不能直接声称这个梯度无偏。对于前面从初始状态定义的 discounted objective，还要给第 $t$ 项乘上 $\gamma^{t-1}$。

也就是说我们要训练两个网络 $\theta$ 和 $\phi$。用当前策略采到的数据集 $\mathcal D_k$，一轮更新里的两个目标可以写成：

$$
\begin{aligned}
\mathcal L_V(\phi)
&=\widehat{\mathbb E}_{(s,a,r,s')\in\mathcal D_k}
\left[\frac12\left\|
\operatorname{sg}[r+\gamma\hat{\mathcal V}_\phi(s')]
-\hat{\mathcal V}_\phi(s)\right\|^2\right],\\
\mathcal L_\pi(\theta)
&=-\widehat{\mathbb E}_{(s,a)\in\mathcal D_k}
\left[\operatorname{sg}[\hat{\mathcal A}_\phi(s,a)]
\log\pi_\theta(a\mid s)\right].
\end{aligned}
$$

两者都用梯度下降；actor loss 前面的负号对应最大化 surrogate。这里沿用不额外写外层时间权重的实现记法，具体采样与折扣约定仍要和目标一致。

## Generalized Advantage Estimation

Actor-critic 用 advantage 判断一个 action 比当前策略的平均表现好多少。实际训练时，真实的 $\mathcal Q$ 和 $\mathcal V$ 都未知，我们需要从采到的轨迹和 critic 的预测中构造 $\hat{\mathcal A}_t$。

我们需要决定观察多少步真实 reward，再让 critic 预测剩下的收益。只观察一步，估计很依赖 critic；一直观察到终点，又会混入后续 action 和环境带来的随机性。Schulman 等人提出的 **Generalized Advantage Estimation（GAE）** ([Schulman et al., 2015](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-schulman2015high)) 把不同步数的估计结合起来，用 $\lambda$ 调节两者的取舍。

### From one step to multiple steps

固定采样策略 $\pi$ 和 discount factor $\gamma$，记 $r_t=r(s_t,a_t)$，把 critic 对 $\mathcal V^{\pi,\gamma}(s_t)$ 的预测简记为 $v_t=\hat{\mathcal V}_\phi(s_t)$。在同一条轨迹上，我们可以在不同位置交给 critic 接手：

从一步到多步：逐渐推迟 bootstrap 的位置

三行分别展示一步、两步和三步 advantage 估计。实线框表示实际观察到的折扣 reward，虚线框表示由 critic 预测的剩余收益；每一行最后都减去当前状态的 value。向下看时，实际 reward 覆盖的时间变长，交给 critic 接手的位置变晚。

已观察到的 reward

critic 预测剩余收益

$\hat{\mathcal A}_t^{(1)}=$

$r_t$

$+$

$\gamma^{1}v_{t+1}$

$-v_t$

$\hat{\mathcal A}_t^{(2)}=$

$\gamma r_{t+1}$

$\gamma^{2}v_{t+2}$

$\hat{\mathcal A}_t^{(3)}=$

$\gamma^{2} r_{t+2}$

$\gamma^{3}v_{t+3}$

向下：用更多实际 reward 替换对未来的预测

[View diagram in the original article](https://pufanyi.com/blog/ml/ml-revisit/rl)

每行都是“已观察的收益 + 预测的剩余收益 − 当前状态的 baseline”。GAE 接下来会把这些不同长度的估计加权平均。

观察 $n$ 步后，前半段用实际 reward，后半段用 $v_{t+n}$ 补足。这种用估计值预测尚未观察到的收益的做法叫做 bootstrap。再减去当前状态的 baseline $v_t$，得到 $n$-step advantage estimate：

$$
\hat{\mathcal A}_t^{(n)}
=\underbrace{\sum_{l=0}^{n-1}\gamma^l r_{t+l}}_{\text{observed rewards}}
+\underbrace{\gamma^n v_{t+n}}_{\text{bootstrap}}
-v_t.
$$

$n=1$ 时，它就是 TD residual：

$$
\delta_t=r_t+\gamma v_{t+1}-v_t.
$$

增加 $n$，就是用更多实际发生的 reward 替换 critic 对未来的预测。这样通常能减少 bootstrap 误差的影响，但也纳入了更多后续轨迹的随机性。

### Mixing the horizons

GAE 为这些不同长度的估计分配指数衰减的权重。先考虑 $0\le\lambda<1$：

$$
\hat{\mathcal A}_t^{\mathrm{GAE}(\gamma,\lambda)}
=(1-\lambda)\sum_{n=1}^{\infty}
\lambda^{n-1}\hat{\mathcal A}_t^{(n)}.
$$

这些权重之和为 $1$。较小的 $\lambda$ 把权重集中在短步数估计上；较大的 $\lambda$ 让长步数估计参与得更多。对于已经终止的 episode，可以把终止后的 reward 和 value 都延拓为 $0$。

把各个 $n$-step estimate 展开并合并，GAE 就变成了 TD residual 的折扣和：

$$
\hat{\mathcal A}_t^{\mathrm{GAE}(\gamma,\lambda)}
=\sum_{l=0}^{\infty}(\gamma\lambda)^l\delta_{t+l}
=\delta_t+\gamma\lambda\delta_{t+1}
+(\gamma\lambda)^2\delta_{t+2}+\cdots.
$$

前一个式子说明 GAE 如何结合不同步数的估计，后一个式子更方便计算。$\lambda=1$ 时使用后一个表达式，或取前一个表达式在 $\lambda\to1$ 时的极限。

从 n-step average 到 TD residual sum

把 TD residual 展开后，中间的 value 项相消：

$$
\hat{\mathcal A}_t^{(n)}
=\sum_{l=0}^{n-1}\gamma^l\delta_{t+l}
=\sum_{l=0}^{n-1}\gamma^l r_{t+l}
+\gamma^n v_{t+n}-v_t.
$$

$\delta_{t+l}$ 出现在所有 $n\ge l+1$ 的估计里，因此它在加权平均中的系数是

$$
(1-\lambda)\gamma^l\sum_{n=l+1}^{\infty}\lambda^{n-1}
=(\gamma\lambda)^l.
$$

若只采到后续 $H$ 步，有限长度版本把剩余权重交给最长的估计：

$$
\begin{aligned}
\hat{\mathcal A}_t^{\mathrm{GAE},H}
&=(1-\lambda)\sum_{n=1}^{H-1}\lambda^{n-1}\hat{\mathcal A}_t^{(n)}
+\lambda^{H-1}\hat{\mathcal A}_t^{(H)}\\
&=\sum_{l=0}^{H-1}(\gamma\lambda)^l\delta_{t+l}.
\end{aligned}
$$

其中 $H=1$ 时只有 $\hat{\mathcal A}_t^{(1)}$。最长那一项仍可以在采样边界使用 critic 的预测。

### What λ controls

| $\lambda$     | 使用的信息                                                | 主要取舍                      |
| ------------- | ---------------------------------------------------- | ------------------------- |
| $0$           | 一步 reward 和下一状态的 value，$\hat{\mathcal A}_t=\delta_t$ | 通常方差较低，更依赖 critic 的准确性    |
| $0<\lambda<1$ | 不同步数估计的加权平均                                          | 在 bootstrap 误差和轨迹采样噪声之间折中 |
| $1$           | 若采到真正终止，使用完整 discounted return 减去 $v_t$              | 后续收益完全来自采样，通常方差较高         |

Bootstrap 可能把 critic 的预测误差带入 policy gradient。若 critic 恰好等于真实的 $\mathcal V^{\pi,\gamma}$，一步 TD 就已经是 advantage 的条件无偏估计；在同样的采样与边界条件下，其他 $\lambda$ 也不会额外引入这种 bias。

$\gamma$ 和 $\lambda$ 的作用不同：$\gamma$ 定义本节要估计的 discounted return；固定 $\gamma$ 后，$\lambda$ 调节估计这个量时观察多长的轨迹。改变 $\lambda$ 不会改变真实 advantage 的定义。

Advantage bias 与 policy-gradient bias

GAE 最终要放进 actor 的梯度里，因此还要区分 advantage 数值的误差与它给 policy gradient 带来的 bias。原论文把满足下面条件的估计量称为 $\gamma$-just：

$$
\mathbb E\left[\hat{\mathcal A}_t\nabla_\theta\log\pi_\theta(a_t\mid s_t)\right]
=\mathbb E\left[\mathcal A^{\pi_\theta,\gamma}(s_t,a_t)
\nabla_\theta\log\pi_\theta(a_t\mid s_t)\right].
$$

当 $v_t=\mathcal V^{\pi,\gamma}(s_t)$ 时，

$$
\mathbb E[\delta_t\mid s_t,a_t]
=\mathcal A^{\pi,\gamma}(s_t,a_t).
$$

此时一步估计已经满足要求。使用近似 critic 并且 $\lambda<1$ 时，bootstrap 误差一般会传入 policy gradient。

记完整的 discounted return 为 $G_t$。当 $\lambda=1$ 且采到真正终止时，$\hat{\mathcal A}_t=G_t-v_t$。即使 $v_t$ 不准确，$G_t$ 仍是 discounted $\mathcal Q$ 的条件无偏估计，而 $v_t$ 是不依赖当前 action 的 baseline，所以这个估计量仍是 $\gamma$-just。但它的条件期望是 $\mathcal Q^{\pi,\gamma}(s_t,a_t)-v_t$，未必等于真实 advantage。

这里固定采样策略，并把 critic 当作给定的函数。$\gamma$-just 讨论的是 discounted policy-gradient 项；对于前文从初始状态定义的 discounted objective，仍沿用相应的外层时间权重。

### Computing GAE on a rollout

实际收集到的轨迹是有限的。设最后一个 action 是 $a_T$，下一状态为 $s_{T+1}$。从后往前计算即可：

$$
\hat{\mathcal A}_t
=\delta_t+\gamma\lambda\hat{\mathcal A}_{t+1},
\qquad \hat{\mathcal A}_{T+1}=0.
$$

这里的 $\hat{\mathcal A}_{T+1}=0$ 表示没有更多已采样的 TD residual；未来收益仍通过最后一个 $\delta_T$ 中的 $v_{T+1}$ 进入估计。边界 value 按轨迹停止的原因确定：

- **真正终止**：未来没有 reward，令 $v_{T+1}=0$。
- **rollout 收集结束或外部 time limit 截断**：任务本可继续，使用停止前最后一个状态的 critic 预测作为 $v_{T+1}$。

Spinning Up 的 [PPOBuffer 实现](https://spinningup.openai.com/en/latest/_modules/spinup/algos/pytorch/ppo/ppo.html) 就通过最后一个 value 处理这两种情况。Gymnasium ([Farama Foundation, n.d.](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-faramahandlingtimelimits)) 用 `terminated` 和 `truncated` 区分真正终止与外部截断；任务本身定义的有限时域终点属于前者。

有限 rollout 下，即使 $\lambda=1$，仍有

$$
\hat{\mathcal A}_t
=\sum_{l=0}^{T-t}\gamma^l r_{t+l}
+\gamma^{T-t+1}v_{T+1}-v_t.
$$

采到真正终止时，边界项为零，才得到纯 Monte Carlo return 减 baseline；截断时则保留 bootstrap。

下面用普通列表实现单段 rollout 的计算。`rewards` 长度为 $T$，`values` 长度为 $T+1$，最后一个元素已经按上面的规则设置。它们都是采样时记录并固定下来的数值。

```python
def gae(rewards, values, gamma, lam):
    assert len(values) == len(rewards) + 1
    advantages = [0.0] * len(rewards)
    carry = 0.0
    for t in reversed(range(len(rewards))):
        delta = rewards[t] + gamma * values[t + 1] - values[t]
        carry = delta + gamma * lam * carry
        advantages[t] = carry
    return advantages
```

多条 episode 应分别计算；截断后 reset 得到的新初始状态也不属于上一段轨迹，不能把它的 value 或 advantage 接到上一段。

例如，一条三步后终止的轨迹只有最后一步得到 reward。取 $\gamma=0.9$、$\lambda=0.8$，因此 $\gamma\lambda=0.72$，并设终止状态 $v_4=0$：

| $t$ | $r_t$ | $v_t$ | $\delta_t$ | $\hat{\mathcal A}_t$ |
| --- | ----- | ----- | ---------- | -------------------- |
| $1$ | $0$   | $0.4$ | $0.05$     | $0.28616$            |
| $2$ | $0$   | $0.5$ | $0.04$     | $0.328$              |
| $3$ | $1$   | $0.6$ | $0.4$      | $0.4$                |

从最后一步开始，先得到 $\hat{\mathcal A}_3=0.4$，再算 $\hat{\mathcal A}_2=0.04+0.72\times0.4=0.328$，最后得到 $\hat{\mathcal A}_1=0.05+0.72\times0.328=0.28616$。终点的信息通过这次反向递推传到更早的 action。

训练 actor 时，把算好的 advantage 当作固定权重，代入前面的 policy-gradient loss 或后面的 PPO objective。GAE 负责构造这个权重；接下来的 TRPO 和 PPO 则控制策略如何利用它更新。

## Trust Region Policy Optimization

TRPO ([Schulman, Levine, et al., 2015](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-schulman2015trust)) / [Spinning Up tutorial](https://spinningup.openai.com/en/latest/algorithms/trpo.html) ([Achiam, 2018](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-spinningup2018))。

$$
\begin{aligned}
\theta_{k+1}&=\arg\max_\theta\mathcal L_{\theta_k}(\theta)\\
\text{s.t.}\quad
\overline D_{\mathrm{KL}}(\theta_k\|\theta)&\le\delta.
\end{aligned}
$$

其中

$$
\mathcal L_{\theta_k}(\theta)
=\mathbb E_{(s,a)\sim\pi_{\theta_k}}\left[
\frac{\pi_\theta(a\mid s)}{\pi_{\theta_k}(a\mid s)}
\hat{\mathcal A}^{\pi_{\theta_k}}(s,a)\right],
$$

$$
\overline D_{\mathrm{KL}}(\theta_k\|\theta)
=\mathbb E_{s\sim\pi_{\theta_k}}\left[
D_{\mathrm{KL}}\!\left(
\pi_{\theta_k}(\cdot\mid s)\|\pi_\theta(\cdot\mid s)
\right)\right].
$$

这里的 state 分布来自旧策略的访问分布；一轮优化中，采样数据、旧策略与 advantage estimates 都固定。

## Proximal Policy Optimization

PPO paper ([Schulman et al., 2017](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-schulman2017proximal)) / [OpenAI tutorial](https://spinningup.openai.com/en/latest/algorithms/ppo.html) ([Achiam, 2018](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-spinningup2018)) / [Hugging Face tutorial](https://huggingface.co/blog/deep-rl-ppo) ([Simonini & Sanseviero, 2023](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-deep-rl-course))。

TRPO 这么复杂，主要是因为它的限制和 $\mathcal L$ 是分开的。文章提出了两种把更新限制放进 surrogate objective 的方法：PPO-Penalty 和 PPO-Clip。

### PPO-Clip

我们对式子略加修改。先记概率比

$$
\rho_\theta(s,a)=\frac{\pi_\theta(a\mid s)}{\pi_{\theta_k}(a\mid s)}.
$$

那么

$$
\theta_{k+1}=\arg\max_\theta
\mathbb E_{(s,a)\sim\pi_{\theta_k}}\left[
\min\left\{
\rho_\theta(s,a)\hat{\mathcal A}(s,a),
\operatorname{clip}(\rho_\theta(s,a),1-\epsilon,1+\epsilon)
\hat{\mathcal A}(s,a)
\right\}\right].
$$

其中

$$
\operatorname{clip}(x,l,u)=
\begin{cases}
l,&x<l,\\
x,&l\le x\le u,\\
u,&x>u.
\end{cases}
$$

大概感性理解是这样的：$\hat{\mathcal A}>0$ 时，我们希望增大这个 action 的概率；$\hat{\mathcal A}<0$ 时，希望减小它的概率。但是当概率比沿着有利方向变化太多，就不再继续奖励这个变化。具体地，正 advantage 在 $\rho_\theta>1+\epsilon$ 时截平，负 advantage 在 $\rho_\theta<1-\epsilon$ 时截平。

它不是把所有概率比硬限制在区间里；共享参数下，其他样本的梯度仍可能继续改变这个 action 的概率。

### PPO-Penalty

非常直觉的式子：

$$
\theta_{k+1}=\arg\max_\theta\left\{
\mathbb E_{(s,a)\sim\pi_{\theta_k}}\left[
\rho_\theta(s,a)\hat{\mathcal A}(s,a)\right]
-\beta\overline D_{\mathrm{KL}}(\theta_k\|\theta)
\right\}.
$$

但是捏，固定一个 $\beta$ 不一定合适。我们既想优化前面那部分，又想控制每一步离旧策略多远。那咋搞呢，就是让 $\beta$ 动起来。跑一段优化，就去康康这个

$$
d=\widehat{\mathbb E}_{s\sim\pi_{\theta_k}}\left[
D_{\mathrm{KL}}(\pi_{\theta_k}(\cdot\mid s)\|\pi_\theta(\cdot\mid s))
\right].
$$

直觉上就是这玩意儿如果大了，就说明太远了，那我们得稍微调高一下 $\beta$；如果太小，就可以把 $\beta$ 搞低，允许更大的更新。

所以说我们可以定一个阈值 $d_{\mathrm{targ}}$：

$$
\beta\leftarrow
\begin{cases}
\beta/2,&d<d_{\mathrm{targ}}/1.5,\\
\beta,&d_{\mathrm{targ}}/1.5\le d\le1.5d_{\mathrm{targ}},\\
2\beta,&d>1.5d_{\mathrm{targ}}.
\end{cases}
$$

### Learning to summarize from human feedback

Learning to summarize from human feedback ([Stiennon et al., 2020](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-stiennon2020summarize)) / [demo](https://openai.com/index/learning-to-summarize-with-human-feedback/)。

TL;DR dataset ([Völske et al., 2017](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-volske-etal-2017-tl))：一个 summarize 任务，主要是对 Reddit 的帖子生成摘要。

Reward model $r_\phi(x,y)$ 只对最终的结果给 reward。这里可以取 $\gamma=1$，不额外折扣后面的 token；终点给 reward 本身并不意味着 $\gamma$ 永远没有影响。Reward model 的数据是一大堆 preference data $\langle x,y_0,y_1\rangle$，其中 $y_0$ 更被喜欢。

$$
\mathcal L(\phi)
=-\mathbb E_{(x,y_0,y_1)\sim\mathcal D}\left[
\log\sigma(r_\phi(x,y_0)-r_\phi(x,y_1))\right].
$$

最终我们训练模型的时候，用 PPO 优化的 reward 里加入相对 reference policy 的 KL penalty：

$$
R_\theta(x,y)=r(x,y)
-\beta\log\frac{\pi_\theta(y\mid x)}{\pi_{\mathrm{ref}}(y\mid x)}.
$$

这个 reference penalty 和 PPO 控制单次更新时相对旧策略的限制不是同一个东西。

然后我们就发现，这个 $\mathbb E_{y\sim\pi_\theta}[\log(\pi_\theta(y\mid x)/\pi_{\mathrm{ref}}(y\mid x))]$ 外面的期望咋被吞掉了。其实上面写的是一条 sampled response 的 reward，整体目标还要对 $y\sim\pi_\theta$ 取期望：

$$
\begin{aligned}
\mathcal R(\theta)
&=\mathbb E_{x\sim\mathcal D,\,y\sim\pi_\theta(\cdot\mid x)}
\left[r(x,y)-\beta\log\frac{\pi_\theta(y\mid x)}{\pi_{\mathrm{ref}}(y\mid x)}\right]\\
&=\mathbb E_{x\sim\mathcal D,\,y\sim\pi_\theta(\cdot\mid x)}[r(x,y)]\\
&\quad-\beta\mathbb E_{x\sim\mathcal D}
\left[D_{\mathrm{KL}}(\pi_\theta(\cdot\mid x)\|\pi_{\mathrm{ref}}(\cdot\mid x))\right].
\end{aligned}
$$

对于这个 reward model，可以联想到 Bradley–Terry model ([Bradley & Terry, 1952](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-bradley1952rank))。这个在 DPO 那篇文章里提了很多。这个 [Stanford STATS 200 notes](https://web.stanford.edu/class/archive/stats/stats200/stats200.1172/Lecture24.pdf) 写的感觉非常好。

$n$ 个球队，每个球队有个 strength $\beta_i$，$i$ 跟 $j$ 打的赢率为

$$
p_{ij}=\frac{e^{\beta_i-\beta_j}}{1+e^{\beta_i-\beta_j}}
=\frac{e^{\beta_i}}{e^{\beta_i}+e^{\beta_j}}.
$$

但是有时候主客场之类的位置不是可交换嘟，所以说还可以加一个位置效应：

$$
p_{ij}=\frac{e^{\alpha+\beta_i-\beta_j}}{1+e^{\alpha+\beta_i-\beta_j}}.
$$

当然咱这儿没有 $\alpha$。其实这个 $r$ 预测的就是这个 $\beta$ 嘛。

### InstructGPT

InstructGPT ([Ouyang et al., 2022](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-ouyang2022training))。

对于 reward model，它把两个改成了 $K$ 个。就是让人排 $K$ 个 $y$，再从这个排序构造 $\binom K2$ 对偏好。这样的话，对每个 prompt 的这些 pair 取平均：

$$
\mathcal L(\phi)
=-\mathbb E_{(x,\{y_j\}_{j=1}^K)\sim\mathcal D}\left[
\frac1{\binom K2}\sum_{y_w\succ y_l}
\log\sigma(r_\phi(x,y_w)-r_\phi(x,y_l))
\right].
$$

然后 RL 部分，待续。

### Implementation

Implementation Matters ([Engstrom et al., 2020](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-engstrom2019implementation)) / The N Implementation Details of RLHF with PPO ([Huang et al., 2024](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-huang2024n)) / The N+ Implementation Details of RLHF with PPO ([Huang, Noukhovitch, et al., 2024](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-huang2024nplus))。

实现笔记待续。

## Direct Preference Optimization

DPO paper ([Rafailov et al., 2023](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-rafailov2024direct)) / [HF docs](https://huggingface.co/docs/trl/main/en/dpo_trainer) / [HF tutorial](https://huggingface.co/blog/dpo-trl)。

### Key Ideas

[DPO 概览图：论文 Figure 1](https://arxiv.org/html/2305.18290v3#S1.F1)。

我的大概猜测是，作者主要有两个 key observations：

1. Preference data 本身可以体现一种 reward function（BT model）。
2. 给定 reference policy 和 $\beta$，最优 $\pi$ 可以对应到一类 reward；这类 reward 只相差一个依赖 prompt 的常数 $c(x)$，会导出同一个最优 policy。

整条线大概是 $\pi\leftrightarrow[r]\to p_\succ\to\mathcal L$，其中 $[r]$ 表示上面这个等价类。

也就是说，我们其实可以通过调整 $\pi$，来让对应的隐式 reward 去吻合 preference data。

具体的 learning objective 推导待续。

### Paper Details

待续。

### Other Details

In eq. 12，把最大化 reward 加 KL penalty 的目标换成等价的最小化形式：

$$
\begin{aligned}
&\min_\pi\mathbb E_{x\sim\mathcal D}\mathbb E_{y\sim\pi(\cdot\mid x)}
\left[\log\frac{\pi(y\mid x)}{\pi_{\mathrm{ref}}(y\mid x)}
-\frac1\beta r(x,y)\right]\\
={}&\min_\pi\mathbb E_{x\sim\mathcal D}\mathbb E_{y\sim\pi(\cdot\mid x)}
\left[\log\frac{\pi(y\mid x)}{\pi_{\mathrm{ref}}(y\mid x)e^{r(x,y)/\beta}}\right]\\
={}&\min_\pi\mathbb E_{x\sim\mathcal D}\mathbb E_{y\sim\pi(\cdot\mid x)}
\left[\log\frac{\pi(y\mid x)}{Z(x)^{-1}\pi_{\mathrm{ref}}(y\mid x)e^{r(x,y)/\beta}}
-\log Z(x)\right].
\end{aligned}
$$

While

$$
Z(x)=\sum_y\pi_{\mathrm{ref}}(y\mid x)e^{r(x,y)/\beta}.
$$

这里假设 $\beta>0$、$Z(x)$ 有限，且 policy 在 reference 的 support 内。比较有意思的点是，它把外面的 $r(x,y)/\beta$ 强行塞进了 $\log$ 里面，构造一个新的 policy：

$$
\pi^*(y\mid x)
=\frac1{Z(x)}\pi_{\mathrm{ref}}(y\mid x)e^{r(x,y)/\beta}.
$$

酱紫的话，里面的 $\log(\pi(y\mid x)/\pi^*(y\mid x))$ 就构成了一个新的 KL：

$$
\begin{aligned}
&\mathbb E_{x\sim\mathcal D}\mathbb E_{y\sim\pi(\cdot\mid x)}
\left[\log\frac{\pi(y\mid x)}{\pi^*(y\mid x)}\right]\\
={}&\mathbb E_{x\sim\mathcal D}
\left[D_{\mathrm{KL}}(\pi(\cdot\mid x)\|\pi^*(\cdot\mid x))\right].
\end{aligned}
$$

## Reward Hacking

[Lilian Weng: Reward Hacking in Reinforcement Learning](https://lilianweng.github.io/posts/2024-11-28-reward-hacking/)。阅读笔记待续。

## Group Relative Policy Optimization

DeepSeekMath ([Shao et al., 2024](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-shao2024deepseekmath))。

对于同一个 prompt $x$，从旧策略采样 $G$ 个回答。先记每个 token 的 probability ratio：

$$
\rho_{i,t}(\theta)
=\frac{\pi_\theta(y_{i,t}\mid x,y_{i,<t})}
{\pi_{\theta_{\mathrm{old}}}(y_{i,t}\mid x,y_{i,<t})}.
$$

原来的目标可以整理为

$$
\mathcal J(\theta)
=\mathbb E_{x\sim\mathcal D,\,\{y_i\}_{i=1}^G\sim\pi_{\theta_{\mathrm{old}}}}\left[
\frac1G\sum_{i=1}^G\frac1{|y_i|}\sum_{t=1}^{|y_i|}
\left(f(\rho_{i,t}(\theta),\hat{\mathcal A}_{i,t})
-\beta D_{i,t}(\theta)\right)
\right],
$$

其中

$$
f(w,A)=\min\{wA,\operatorname{clip}(w,1-\epsilon,1+\epsilon)A\},
$$

$$
D_{i,t}(\theta)
=D_{\mathrm{KL}}\!\left(
\pi_\theta(\cdot\mid x,y_{i,<t})\|
\pi_{\mathrm{ref}}(\cdot\mid x,y_{i,<t})
\right).
$$

这里把 KL 项写成条件分布之间的散度来说明目标；原论文实现使用相应的逐 token 估计量。

欸为啥看着这么像 offline learning 捏。冷静分析发现，式子里居然有 $\pi_{\theta_{\mathrm{old}}}$ 和 $\pi_{\mathrm{ref}}$ 两个东西。所以它其实是一轮从旧策略采样，再沿 surrogate 的梯度更新：

$$
\theta_{\mathrm{new}}
\leftarrow\theta_{\mathrm{old}}
+\left.\eta\nabla_\theta\mathcal J(\theta;\theta_{\mathrm{old}})
\right|_{\theta=\theta_{\mathrm{old}}}.
$$

这是最大化 $\mathcal J$ 的一步梯度上升；实际可以在一批旧数据上做若干次更新，再重新采样。通常从 reference 初始化 policy，但之后 $\theta_{\mathrm{old}}$ 会更新，$\theta_{\mathrm{ref}}$ 保持固定。这俩确实应该是不一样的。

所以它想控制两个事情：

1. $\theta_{\mathrm{old}}\to\theta_{\mathrm{new}}$：单轮更新不要偏得太多，用 clip 抑制继续改善已过界样本的 surrogate。
2. $\theta_{\mathrm{ref}}\to\theta_{\mathrm{new}}$：不要过度偏离 reference，用 KL penalty 约束。

那这个 clip 和直接修改 learning rate 有啥区别呢？Learning rate 缩放整次参数更新，clip 则让某些样本在有利方向上超过阈值后不再贡献这部分改进梯度。因此两者不能互相替代，clip 也不保证所有 action 的概率比都留在区间内。

如果是 outcome supervision，advantage 就方便多了：同一个回答中的所有 tokens 共用这个回答的归一化 reward，**仍然使用逐 token 的 probability ratio**。

$$
\hat{\mathcal A}_{i,t}=\hat{\mathcal A}(x,y_i)
=\frac{r(x,y_i)-\bar r}{\sigma_r},\qquad
\bar r=\frac1G\sum_{j=1}^G r(x,y_j).
$$

所以对应的目标是

$$
\mathcal J(\theta)
=\mathbb E_{x,\{y_i\}\sim\pi_{\theta_{\mathrm{old}}}}\left[
\frac1G\sum_{i=1}^G\frac1{|y_i|}\sum_{t=1}^{|y_i|}
\left(f(\rho_{i,t}(\theta),\hat{\mathcal A}(x,y_i))
-\beta D_{i,t}(\theta)\right)
\right].
$$

如果是 process supervision，论文会先归一化各个 reasoning step 的 reward，再把当前 token 之后的 step rewards 累加成 $\hat{\mathcal A}_{i,t}$，而不是只使用当前位置的一项 reward。

### DeepSeek R1

DeepSeek-R1 ([Guo et al., 2025](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-guo2025deepseek))。阅读笔记待续。

### GRPO with Binary Rewards

Mroueh ([Mroueh, 2025](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-mroueh_2025)) 从 binary rewards 理解 GRPO。也就是说 $r(y)\in\{0,1\}$。

他的结论大概是说，GRPO 会根据模型整体回答的好坏，对正确和错误回答赋予不同的相对权重。

不过其实有点没咋搞懂的是，他直接把 advantage 看成了

$$
\hat{\mathcal A}(x,y)
=\frac{r(x,y)-\mathbb E_{y'\sim\pi_{\theta_{\mathrm{old}}}(\cdot\mid x)}[r(x,y')]}
{\sqrt{\operatorname{Var}_{y'\sim\pi_{\theta_{\mathrm{old}}}(\cdot\mid x)}(r(x,y'))}}.
$$

但有限 group 的均值、标准差本来都是随机变量，这里把它们换成了总体统计量。因此下面是总体近似下的分析，不能直接当成有限 group estimator 的等式。

但是确实感性上还是有一定道理的。如果 $r(x,y)\sim\operatorname{Bernoulli}(p)$，其中 $0<p<1$，我们就可以方便地代进去得到

$$
\hat{\mathcal A}(x,y)
=\frac{r(x,y)-p}{\sqrt{p(1-p)}}
=\begin{cases}
\sqrt{\dfrac{1-p}{p}},&\text{if correct},\\
-\sqrt{\dfrac p{1-p}},&\text{if incorrect}.
\end{cases}
$$

以下固定一个 prompt $x$，并按这篇笔记使用整条回答的概率比 $\rho(y)=\pi_\theta(y\mid x)/\pi_{\theta_{\mathrm{old}}}(y\mid x)$ 作简化分析；它与上面的逐 token 训练目标要区分开。

辣么

$$
\begin{aligned}
f(\rho,y)
&=\min\{\rho\hat{\mathcal A}(y),
\operatorname{clip}(\rho,1-\epsilon,1+\epsilon)\hat{\mathcal A}(y)\}\\
&=\begin{cases}
\min\{\rho,1+\epsilon\}\sqrt{\dfrac{1-p}{p}},&\text{if correct},\\
-\max\{\rho,1-\epsilon\}\sqrt{\dfrac p{1-p}},&\text{if incorrect}.
\end{cases}
\end{aligned}
$$

所以说，下面的期望都按 $y\sim\pi_{\theta_{\mathrm{old}}}(\cdot\mid x)$ 取：

$$
\begin{aligned}
\mathbb E[f(\rho(y),y)]
&=\mathbb E\left[
\begin{cases}
\min\{\rho(y),1+\epsilon\}\sqrt{\dfrac{1-p}{p}},&r(y)=1,\\
-\max\{\rho(y),1-\epsilon\}\sqrt{\dfrac p{1-p}},&r(y)=0
\end{cases}\right]\\
&=\mathbb E\left[\min\{\rho(y),1+\epsilon\}\mathbf1_{r(y)=1}\right]
\sqrt{\frac{1-p}{p}}\\
&\quad-\mathbb E\left[\max\{\rho(y),1-\epsilon\}\mathbf1_{r(y)=0}\right]
\sqrt{\frac p{1-p}}.
\end{aligned}
$$

所以说，如果 $p$ 比较小，这个问题模型很难回答，那么单个正确回答的正权重更大。也就是说，它会更「乐观」，更倾向于表扬少见的正确做法。如果 $p$ 很大，也就是模型很容易回答，单个错误回答的负权重绝对值更大，这时候就会更加「严苛」，去批评那些做得不好的回答。这里比较的是每个样本的系数，不是说某一类在总梯度里一定占主导；采样频率和 score gradient 也会影响结果。

有限 group 若全对或全错，会出现 $\sigma_r=0$，实现中需要显式处理，不能直接代入除法。

原文好像又往下推了一点。其实没理解还要干啥，我觉得前面的式子已经足够解释这两个权重了。

继续展开裁剪项

记 $p_{\mathrm{old}}(y)=\pi_{\theta_{\mathrm{old}}}(y\mid x)$、$p_\theta(y)=\pi_\theta(y\mid x)$，并定义两个概率阈值

$$
\ell(y)=(1-\epsilon)p_{\mathrm{old}}(y),\qquad
u(y)=(1+\epsilon)p_{\mathrm{old}}(y).
$$

那么

$$
\begin{aligned}
\mathbb E[f(\rho(y),y)]
&=\mathbb E\left[\rho(y)\mathbf1_{\{r(y)=1,\,p_\theta(y)<u(y)\}}\right]
\sqrt{\frac{1-p}{p}}\\
&\quad+(1+\epsilon)\mathbb E\left[\mathbf1_{\{r(y)=1,\,p_\theta(y)\ge u(y)\}}\right]
\sqrt{\frac{1-p}{p}}\\
&\quad-\mathbb E\left[\rho(y)\mathbf1_{\{r(y)=0,\,p_\theta(y)>\ell(y)\}}\right]
\sqrt{\frac p{1-p}}\\
&\quad-(1-\epsilon)\mathbb E\left[\mathbf1_{\{r(y)=0,\,p_\theta(y)\le\ell(y)\}}\right]
\sqrt{\frac p{1-p}}.
\end{aligned}
$$

### Reinforcement Learning from Verifiable Rewards

Tülu 3 ([Lambert et al., 2024](https://pufanyi.com/blog/ml/ml-revisit/rl#bib-lambert2024t))。阅读笔记待续。

## Q Learning

之前其实我们都显式维护一个 $\pi_\theta$，也可能通过 $\mathcal V$ 和 $\mathcal Q$ 来指导这个 policy 的更新。

那其实我们能不能直接根据 $\mathcal Q$ 来选 action？比如先选定一个最大值对应的 action $a^*(s)\in\arg\max_{a'}\mathcal Q(s,a')$，有并列时用固定规则处理，再定义

$$
\pi(a\mid s)=\begin{cases}
1,&a=a^*(s),\\
0,&\text{otherwise}.
\end{cases}
$$

后面的 Q-learning 更新与推导待续。

## References

Achiam, J. (2018). *Spinning Up in Deep Reinforcement Learning*. [spinningup.openai.com](https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html "https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html")

Bradley, R. A., & Terry, M. E. (1952). Rank analysis of incomplete block designs: I. The method of paired comparisons. *Biometrika*, *39*(3/4), 324–345. [doi.org](https://doi.org/10.1093/biomet/39.3-4.324 "https://doi.org/10.1093/biomet/39.3-4.324")

Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., & Madry, A. (2020). Implementation matters in deep rl: A case study on ppo and trpo. *International Conference on Learning Representations*. [openreview.net](https://openreview.net/forum?id=r1etN1rtPB "https://openreview.net/forum?id=r1etN1rtPB")

Farama Foundation. (n.d.). *Handling Time Limits*. [gymnasium.farama.org](https://gymnasium.farama.org/tutorials/gymnasium_basics/handling_time_limits/ "https://gymnasium.farama.org/tutorials/gymnasium_basics/handling_time_limits/")

Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., & others. (2025). DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. *arXiv Preprint arXiv:2501.12948*. [arxiv.org](https://arxiv.org/abs/2501.12948 "https://arxiv.org/abs/2501.12948")

Hogg, R. V., McKean, J. W., & Craig, A. T. (2013). *Introduction to Mathematical Statistics* (7th ed.). Pearson. [scholarworks.wmich.edu](https://scholarworks.wmich.edu/books/176/ "https://scholarworks.wmich.edu/books/176/")

Huang, S., Liu, T., & Von Werra, L. (2024). The n implementation details of rlhf with ppo. *The Third Blogpost Track at ICLR 2024*. [iclr-blogposts.github.io](https://iclr-blogposts.github.io/2024/blog/the-n-implementation-details-of-rlhf-with-ppo/ "https://iclr-blogposts.github.io/2024/blog/the-n-implementation-details-of-rlhf-with-ppo/")

Huang, S., Noukhovitch, M., Hosseini, A., Rasul, K., Wang, W., & Tunstall, L. (2024). The N+ Implementation Details of RLHF with PPO: A Case Study on TL; DR Summarization. *arXiv Preprint arXiv:2403.17031*. [arxiv.org](https://arxiv.org/abs/2403.17031 "https://arxiv.org/abs/2403.17031")

Lambert, N., Morrison, J., Pyatkin, V., Huang, S., Ivison, H., Brahman, F., Miranda, L. J. V., Liu, A., Dziri, N., Lyu, S., & others. (2024). Tülu 3: Pushing Frontiers in Open Language Model Post-Training. *arXiv Preprint arXiv:2411.15124*. [arxiv.org](https://arxiv.org/abs/2411.15124 "https://arxiv.org/abs/2411.15124")

Mroueh, Y. (2025). *GRPO with Binary Rewards Is an Adaptive Weighted Contrastive Loss*. [ymroueh.me](https://ymroueh.me/media/GRPO.pdf "https://ymroueh.me/media/GRPO.pdf")

Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P. F., Leike, J., & Lowe, R. (2022). Training language models to follow instructions with human feedback. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, & A. Oh (Eds.), *Advances in Neural Information Processing Systems* (Vol. 35, pp. 27730–27744). Curran Associates, Inc. [proceedings.neurips.cc](https://proceedings.neurips.cc/paper_files/paper/2022/file/b1efde53be364a73914f58805a001731-Paper-Conference.pdf "https://proceedings.neurips.cc/paper_files/paper/2022/file/b1efde53be364a73914f58805a001731-Paper-Conference.pdf")

Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., & Finn, C. (2023). Direct preference optimization: Your language model is secretly a reward model. *Advances in Neural Information Processing Systems*, *36*. [papers.nips.cc](https://papers.nips.cc/paper_files/paper/2023/hash/a85b405ed65c6477a4fe8302b5e06ce7-Abstract-Conference.html "https://papers.nips.cc/paper_files/paper/2023/hash/a85b405ed65c6477a4fe8302b5e06ce7-Abstract-Conference.html")

Schulman, J., Levine, S., Moritz, P., Jordan, M., & Abbeel, P. (2015). Trust region policy optimization. *Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37*, 1889–1897. [proceedings.mlr.press](https://proceedings.mlr.press/v37/schulman15.html "https://proceedings.mlr.press/v37/schulman15.html")

Schulman, J., Moritz, P., Levine, S., Jordan, M., & Abbeel, P. (2015). High-dimensional continuous control using generalized advantage estimation. *arXiv Preprint arXiv:1506.02438*. [arxiv.org](https://arxiv.org/abs/1506.02438 "https://arxiv.org/abs/1506.02438")

Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017). Proximal policy optimization algorithms. *arXiv Preprint arXiv:1707.06347*. [arxiv.org](https://arxiv.org/abs/1707.06347 "https://arxiv.org/abs/1707.06347")

Shao, Z., Wang, P., Zhu, Q., Xu, R., Song, J., Bi, X., Zhang, H., Zhang, M., Li, Y., Wu, Y., & others. (2024). Deepseekmath: Pushing the limits of mathematical reasoning in open language models. *arXiv Preprint arXiv:2402.03300*. [arxiv.org](https://arxiv.org/abs/2402.03300 "https://arxiv.org/abs/2402.03300")

Simonini, T., & Sanseviero, O. (2023). The Hugging Face Deep Reinforcement Learning Class. In *GitHub repository*. GitHub. [github.com](https://github.com/huggingface/deep-rl-class "https://github.com/huggingface/deep-rl-class")

Stiennon, N., Ouyang, L., Wu, J., Ziegler, D. M., Lowe, R., Voss, C., Radford, A., Amodei, D., & Christiano, P. F. (2020). Learning to summarize from human feedback. *Advances in Neural Information Processing Systems*, *33*, 3008–3021. [arxiv.org](https://arxiv.org/abs/2009.01325 "https://arxiv.org/abs/2009.01325")

Thomas, P. (2014). Bias in natural actor-critic algorithms. *International Conference on Machine Learning*, 441–448. [proceedings.mlr.press](https://proceedings.mlr.press/v32/thomas14.html "https://proceedings.mlr.press/v32/thomas14.html")

Völske, M., Potthast, M., Syed, S., & Stein, B. (2017). TL;DR: Mining Reddit to Learn Automatic Summarization. In L. Wang, J. C. K. Cheung, G. Carenini, & F. Liu (Eds.), *Proceedings of the Workshop on New Frontiers in Summarization* (pp. 59–63). Association for Computational Linguistics. [doi.org](https://doi.org/10.18653/v1/W17-4508 "https://doi.org/10.18653/v1/W17-4508")

Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. *Machine Learning*, *8*(3–4), 229–256. [doi.org](https://doi.org/10.1007/BF00992696 "https://doi.org/10.1007/BF00992696")