零基础速通 PPO 学习笔记

学习背景

最近陶瓷到了港科的一个 RA，组里在做 Agent 强化学习相关内容，听从学长的指导来学习 PPO 算法相关知识。

在强化学习中， $a_t$ 一般表示 $t$ 时刻 Agent 采取的动作（action）； $s_t$ 表示 $t$ 时刻 Agent 所处的状态（state）； $\pi$ 表示 Agent的策略函数（policy），输入状态，输入采取每个动作的概率分布 $\pi(a_t|s_t)$ ； $r_t$ 一边表示 $t$ 时刻 Agent 采取行动获得的奖励（Reward）； $\tau$ 表示轨迹（Trajectory），Episode 指一次完整的交互过程：从环境开始，到终止结束。Rollout 指按某个策略实际“跑出来”的一段轨迹数据。它不一定非得是完整的一局，也可以只是中间截取的一段。

$(s_0,a_0,s_1,a_1 \dots s_T)$

$s_{t+1} = f(s_t,a_t)$ 或者 $s_{t+1} = P(\cdot|s_t,a_t)$ 。

Return 一般表示回报，指从当前时间点到游戏结束时奖励的累积和或者加权累积和。

训练目标

训练一个 Policy 神经网络 $\pi$ ，在所有状态 $S$ 下，给出相应的 Action，得到的 Return 的期望最大。

$E (R(\tau))_{\tau \sim P_{\theta}(\tau)} = \sum\limits_\tau R(\tau)P_\theta(\tau)$

\begin{aligned} \nabla E(R(\tau))_{\tau \sim P_\theta(\tau)} &= \nabla \sum_\tau R(\tau)P_\theta(\tau)\\ &= \sum_\tau R(\tau)\nabla P_\theta(\tau)\\ &= \sum_\tau R(\tau)\nabla P_\theta(\tau) \cdot \dfrac{P_\theta(\tau)}{P_\theta(\tau)}\\ &= \sum_\tau P_\theta(\tau)R(\tau) \dfrac{\nabla P_\theta(\tau)}{P_\theta(\tau)}\\ &\approx \frac{1}{N}\sum\limits_{n=1}^N R(\tau^n)\dfrac{\nabla p_\theta(\tau^n)}{P_\theta(\tau^n)}\\ &= \frac{1}{N}\sum\limits_{n=1}^N R(\tau^n)\nabla \log P_\theta(\tau^n)\\ &= \frac{1}{N}\sum\limits_{n=1}^N R(\tau^n)\nabla \log \prod\limits_{t=1}^{T_n}P_\theta(a_n^t|s_n^t)\\ &= \frac{1}{N}\sum\limits_{n=1}^N R(\tau^n)\sum\limits_{t=1}^{T_n}\nabla \log P_\theta(a_n^t|s_n^t)\\ &= \frac{1}{N}\sum\limits_{n=1}^N \sum\limits_{t=1}^{T_n} R(\tau^n)\nabla \log P_\theta(a_n^t|s_n^t)\\ \end{aligned}

$Loss = -\frac{1}{N}\sum\limits_{n=1}^N \sum\limits_{t=1}^{T_n} R(\tau^n) \log P_\theta(a_n^t|s_n^t)$

$R(\tau^n) = \sum\limits_{t=t'}^{T_n} \gamma^{t-t'} r_{t'}^n = R_t^n$

Actor-Critic 演员-评论家算法

为了衡量每个动作的相对好坏的情况，我们令奖励 $R_t$ 减去一个基准值。

$\frac{1}{N} \sum\limits_{n=1}^N \sum\limits_{t=1}^{T_n} (R_t^n - B(s_t^n))\nabla \log P_\theta(a_t^n|s_t^n)$

但是， $R_t^n$ 都是一次随机采样，方差很大，训练不稳定。我们引入 $Q_\theta(s,a)$ ，表示在状态 $s$ ，下，做出动作 $a$ 后期望的回报，即动作价值函数。

令 $V_\theta(s)$ 在状态 $s$ 下期望的回报，即状态价值函数

$A_\theta(s,a) = Q_\theta(s,a) - V_\theta(s)$ 表示优势函数（Advantage Function），衡量在状态 $s$ 下，动作 $a$ 相对于平均水平的优势。

讲上述的公式改写为

$\dfrac{1}{N}\sum\limits_{n=1}^N \sum\limits_{t=1}^{T_n} A_\theta(s_t^n,a_t^n)\nabla \log P_\theta(a_t^n|s_t^n)$

Q_\theta(s_t, a) = r_t + \gamma V_\theta(s_{t+1}) \\ A_\theta(s_t, a) = r_t + \gamma V_\theta(s_{t+1}) - V_\theta(s_t)\\ V_\theta(s_{t+1}) \approx r_{t+1} + \gamma V_\theta(s_{t+2})

通过上述公式变化，关于 $A_\theta(s,a)$ 的推到公式仅剩一个相关变量，可以降低公式的复杂性。

之后再根据采样步数进行估算。采样越多，情况越多，整体估计的偏差就会偏小，同样的，碰到极值的概率越大，方差就越大。

A_\theta^1(s_t, a) = r_t + \gamma V_\theta(s_{t+1}) - V_\theta(s_t)\\ A_\theta^2(s_t, a) = r_t + \gamma r_{t+1} + \gamma^2 V_\theta(s_{t+2}) - V_\theta(s_t)\\ A_\theta^3(s_t, a) = r_t + \gamma * r_{t+1} + \gamma^2 * r_{t+2} + \gamma^3 V_\theta(s_{t+3}) - V_\theta(s_t)\\ \vdots \\ A_\theta^T(s_t, a) = r_t + \gamma * r_{t+1} + \gamma^2 * r_{t+2} + \gamma^3 * r_{t+3} + \cdots + \gamma^T * r_T - V_\theta(s_t)

为了让式子表示整洁，我们定义一个中间变量，令 $\delta_t$ 表示在第 $t$ 步采取特定动作带来的优势。

\delta_t^V = r_t + \gamma * V_\theta(s_{t+1}) - V_\theta(s_t)\\ \delta_{t+1}^V = r_{t+1} + \gamma * V_\theta(s_{t+2}) - V_\theta(s_{t+1})\\ A_\theta^1(s_t, a) = \delta_t^V\\ A_\theta^2(s_t, a) = \delta_t^V + \gamma \delta_{t+1}^V\\ A_\theta^3(s_t, a) = \delta_t^V + \gamma \delta_{t+1}^V + \gamma^2 \delta_{t+2}^V\\ \vdots

Generalized Advantage Estimation (GAE)

这时我们考虑，在运行时我们应该向后采样几步呢？GAE 的答案是，小孩子才做选择，我全都要！

GAE考虑全部的采样结果，并引入一个衰减因子 $\lambda$ 。

\begin{aligned} A_\theta^{GAE}(s_t, a) &= (1 - \lambda)(A_\theta^1 + \lambda * A_\theta^2 + \lambda^2 A_\theta^3 + \cdots) \quad\quad \lambda = 0.9: \quad A_\theta^{GAE} = 0.1A_\theta^1 + 0.09A_\theta^2 + 0.081A_\theta^3 + \cdots \\ &= (1 - \lambda)(\delta_t^V + \lambda * (\delta_t^V + \gamma \delta_{t+1}^V) + \lambda^2 (\delta_t^V + \gamma \delta_{t+1}^V + \gamma^2 \delta_{t+2}^V) + \cdots) \\ &= (1 - \lambda)(\delta_t^V (1 + \lambda + \lambda^2 + \cdots) + \gamma \delta_{t+1}^V * (\lambda + \lambda^2 + \cdots) + \cdots) \\ &= (1 - \lambda)\left(\delta_t^V \frac{1}{1 - \lambda} + \gamma \delta_{t+1}^V \frac{\lambda}{1 - \lambda} + \cdots\right) \\ &= \sum\limits_{b=0}^\infty (\gamma\lambda)^b \delta_{t+b}^V \end{aligned}

整理后发现其中有等比数列，利用等比数列求和得到最终的 GAE 优势函数的表达式。

GAE 优势函数平衡了采样不同步带来的方差和偏差的问题。

现在我们来看上面得之不易的三个表达式：

\delta_t^V = r_t + \gamma V_\theta(s_{t+1}) - V_\theta(s_t) \\ A_\theta^{GAE}(s_t, a) = \sum_{b=0}^{\infty} (\gamma\lambda)^b \delta_{t+b}^V \\ \frac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n} A_\theta^{GAE}(s_n^t, a_n^t)\, \nabla \log P_\theta(a_n^t|s_n^t)

这里的价值状态函数我们一般用一个神经网路进行拟合，一般可以和策略网络公用参数，只是最后一层不同。

Proximal Policy Optimization (PPO) 近邻策略优化算法

在经典的强化学习环境中，我们一般是一边采集数据，一边进行训练模型，采集完的数据用完就会丢掉。这导致我们采集的数据发生了一定的浪费，且模型训练的成本也会增高。但如果我们有一种方法，能让模型在其他模型的表现中学习自己的表现，参考其他数据就能实现自身的更新，这样我们的训练成本就会大大减少。

重要性采样

将 $f(x)$ 在分布 $p$ 下的期望改写为在另一分布 $q$ （proposal）下的期望，从而可用从 $q$ 采样的数据估计：

\begin{aligned} \mathbb{E}(f(x))_{x \sim p(x)} &= \sum_{x} f(x) \cdot p(x) \\ &= \sum_{x} f(x) \cdot p(x) \frac{q(x)}{q(x)} \\ &= \sum_{x} f(x) \frac{p(x)}{q(x)} \cdot q(x) \\ &= \mathbb{E}\left(f(x) \frac{p(x)}{q(x)}\right)_{x \sim q(x)} \\ &\approx \frac{1}{N} \sum_{n=1}^{N} f(x_n) \frac{p(x_n)}{q(x_n)}, \quad x_n \sim q(x) \end{aligned}

这样我们可以用重要性采样更新我们的目标函数的梯度公式，这样我们可以把 on-policy 的训练改为 off-policy 的训练。

Off-policy

记 $\theta'$ 为采集数据时的旧策略， $\theta$ 为当前要优化的策略；优势 $A_{\theta'}^{GAE}$ 由旧策略下的价值网络估计。利用恒等式 $\nabla \log f(x) = \dfrac{\nabla f(x)}{f(x)}$ ，可将策略梯度写成重要性采样比 $\dfrac{P_\theta}{P_{\theta'}}$ 的形式：

\nabla \log f(x) = \frac{\nabla f(x)}{f(x)}

\begin{aligned} &\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} A_\theta^{GAE}(s_n^t, a_n^t) \nabla \log P_\theta(a_n^t | s_n^t) \\ &= \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} A_{\theta'}^{GAE}(s_n^t, a_n^t) \frac{P_\theta(a_n^t | s_n^t)}{P_{\theta'}(a_n^t | s_n^t)} \nabla \log P_\theta(a_n^t | s_n^t) \\ &= \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} A_{\theta'}^{GAE}(s_n^t, a_n^t) \frac{P_\theta(a_n^t | s_n^t)}{P_{\theta'}(a_n^t | s_n^t)} \frac{\nabla P_\theta(a_n^t | s_n^t)}{P_\theta(a_n^t | s_n^t)} \\ &= \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} A_{\theta'}^{GAE}(s_n^t, a_n^t) \frac{\nabla P_\theta(a_n^t | s_n^t)}{P_{\theta'}(a_n^t | s_n^t)} \end{aligned}

对应地，极大化目标时可用如下损失（最小化时取负号）：

Loss = -\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} A_{\theta'}^{GAE}(s_n^t, a_n^t) \frac{P_\theta(a_n^t | s_n^t)}{P_{\theta'}(a_n^t | s_n^t)}

同时，你学习的目标模型不能和我们的差距过大，否则很难学到有用的经验和教训。

PPO-Penalty：在 surrogate 上加 KL 惩罚

如何给我们训练的策略和参考的策略增加相差不能过大这个约束呢？那就是加上 KL 散度的约束。KL 散度就是衡量两个分布差异大小的指标。两个分布差异越小，KL散度越小，分布差异越大，KL散度越大。通过因子 $\beta$ 来调整 KL 散度影响的大小。

Loss_{\text{ppo}} = -\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} A_{\theta'}^{GAE}(s_n^t, a_n^t) \frac{P_{\theta}(a_n^t|s_n^t)}{P_{\theta'}(a_n^t|s_n^t)} + \beta\,\mathrm{KL}(P_{\theta}, P_{\theta'})

PPO-Clip：截断重要性采样比

PPO 还有一种实现，是通过截断函数来替代 KL 散度，防止训练的策略和参考的策略偏差过大，可以看出它是由红色和蓝色两个部分构成，取两个部分的最小值。

其中红色部分是原始公式，蓝色部分是一个截断函数，截断函数内由三个部分组成。如果 $\frac{P_{\theta}(a_n^t|s_n^t)}{P_{\theta'}(a_n^t|s_n^t)}$ 的值介于 $1-\epsilon$ 到 $1+\epsilon$ 之间，就返回原值，否则返回其中更接近的一个。这就限制的参考模型和训练模型差异的值不能太大。

Loss_{\text{ppo2}} = -\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} \min\left(\textcolor{red}{A_{\theta'}^{GAE}(s_n^t, a_n^t) \frac{P_{\theta}(a_n^t|s_n^t)}{P_{\theta'}(a_n^t|s_n^t)}},\,\textcolor{skyblue}{\mathrm{clip}\left(\frac{P_{\theta}(a_n^t|s_n^t)}{P_{\theta'}(a_n^t|s_n^t)},\, 1-\epsilon,\, 1+\epsilon\right) A_{\theta'}^{GAE}(s_n^t, a_n^t)}\right)

参考资料

零基础学习强化学习算法：ppo