强化学习_PPO算法(Proximal Policy Optimization)

本文介绍强化学习中的PPO(Proximal Policy Optimization)算法。

PPO(Proximal Policy Optimization)是OpenAI使用的默认RL方法，PPO方法可以被理解为

Policy Gradient -> (On Policy -> Off Policy) -> (Add Constraint) -> PPO(Proximal Policy Optimization)

RL相关要素

强化学习是指智能体在给定环境中进行动作的选择，在动作选择并执行之后同环境交互获得新的状态，每一对State（状态）和Action（动作）可以得到相应的Reward（奖励），强化学习的目标就是最大化Reward。

状态，动作更替可以用Trajectory（迹）来表示：

$$Trajectory\ \tau = {s_1,a_1,s_2,a_2,…,s_T,a_T}\tag{1}$$

每一条Trajectory的概率为:

$$p_\theta(\tau) =p(s_1)p_\theta(a_1|s_1)p(s_2|s_1,a_1)p_\theta(a_2|s_2)p(s_3|s_2,a_2)…=p(s_1)\prod_{t=1}^{T}p_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)\tag{2}$$

在这个式子中我们可以看到，$p_\theta(a_t|s_t)$是Actor得出的，这个是我们可以控制的，但是$p(s_{t+1}|s_t,a_t)$是动作$a_t$在状态$s_t$下与环境交互转移到状态$s_{t+1}$的概率，这是由环境本身决定的，我们自己无法控制它。

在强化学习中一条Trajectory的Expected Reward为：

$$\overline R_\theta = \sum_{\tau}R(\tau)p_\theta(\tau)=E_{\tau\sim p_\theta(\tau)}[R(\tau)]\tag{3})$$

其中的$R(\tau)$为：

$$R(\tau) = \sum_{t=1}^{T} r_t\tag{4}$$

Policy Gradient

想要最大化Reward，在上一节我们又获得了$\overline R_\theta$的公式，此时我们对$\overline R_\theta$求梯度:

$$\nabla \overline R_\theta = \sum_{\tau}R(\tau)\nabla p_\theta(\tau)=\sum_{\tau}R(\tau)p_\theta(\tau)\frac{\nabla p_\theta(\tau)}{p_\theta(\tau)}\tag{5}$$

在上式中，$R(\tau)$不一定是需要可微的，它甚至可以是一个黑盒。

$$\nabla f(x) = f(x)\nabla logf(x)\tag{6}$$

接着将梯度公式(6)代入(5)中，得：

$$\nabla \overline R_\theta = \sum_{\tau}R(\tau)p_\theta(\tau)\nabla logp_\theta(\tau)= E_{\tau \sim p_\theta(\tau)}[R(\tau)\nabla logp_\theta(\tau)] \approx \frac{1}{N}\sum_{n=1}^{N}R(\tau^n)\nabla logp_\theta(\tau^n)$$

$$= \frac{1}{N}\sum_{n=1}^{N}\sum_{t=1}^{T_n}R(\tau^n)\nabla logp_\theta(a_t^n|s_t^n)\tag{7}$$

在式子(7)中，由于$\sum_{\tau}$和$p_{\theta}(\tau)$的存在，因此将它们写成期望$E_{\tau \sim p_\theta(\tau)}$的形式。$p_{\theta}(\tau)$相当于$\nabla logp_\theta(\tau)$的一个weight（权重）。并且在$p_\theta(\tau)$中，$\tau$相当于有两项，一项是来自环境本身（无法求梯度），另一项来自智能体Agent，因此将$\nabla logp_\theta(\tau)$更进一步写作$logp_\theta(a_t^n|s_t^n)$

因此的Policy Gradient的基本过程可以这样描述：在环境中取得数据，在给定的策略$\pi_\theta$下，获得不同的Trajectory，每个Trajectory拥有不同的状态，动作以及对应的奖励值，收集状态动作对之后，将其带入式(7)中，进行参数$\theta$的更新：$\theta \leftarrow \theta + \eta\nabla \overline R_\theta$,在更新之后对新的环境重新获取数据，循环往复，我们可以看到在这个流程中，在环境中取得的数据仅被使用了一次，因此Policy Gradient是一个严格的On-Policy算法。

Tip 1: Add a Baseline

在某些情况下，$\theta \leftarrow \theta + \eta\nabla \overline R_\theta$中的$R(\tau^n)$始终为正，如果采样数量足够多，即使是奖励都为正的动作，我们也可以按照奖励值的大小决定每个动作的优劣，并以此修改下个动作被选中的概率（好的动作增加被选中的概率，差的动作降低被选中的概率），但是在训练的环境下，总会有一些奖励为正的动作无法被采样，但是其他动作的奖励都为正，它们被选中的概率增加好，这就导致未被采样的动作的概率降低，哪怕未被采样的动作实质上优于一部分甚至全部被采样的动作。因此可以将式(7)进行如下修改：

$$\nabla \overline R_\theta = \frac{1}{N}\sum_{n=1}^{N}\sum_{t=1}^{T_n}(R(\tau^n)-b)\nabla logp_\theta(a_t^n|s_t^n)\tag{8}$$

在这里的b就是新增的baseline，通常$b \approx E[R(\tau)]$，这样就可以有效的降低未被采样的动作被“误杀”。

Tip 2: Assign Suitable Credit

在一条Trajectory中，每个动作如果只由总的R来反映权重是不合适的，比如在$(s_a,a_1),(s_b,a_2),(s_c,a_3)$中的单步奖励值分别为+5，+0，-2，R=5-2=+3 但是对于a2，a3这种并未对Reward结果最大化做出正向贡献的action反而也被赋予了值为+3的Reward作为权重，这是不合理的。我们应该让每一个action前的R值都正确的反映它在当前Trajectory中的作用，到底是好还是坏。我们可以把式(8)中的$R(\tau^n)$改写为$\sum_{t’=t}^{T_n}r_{t’}^{n}$:

$$\nabla \overline R_\theta \approx \frac{1}{N}\sum_{n=1}^{N}\sum_{t=1}^{T_n}(\sum_{t’=t}^{T_n}r_{t’}^{n}-b)\nabla p_\theta(a_t^n|s_t^n)\tag{9}$$

$\sum_{t’=t}^{T_n}r_{t’}^{n}$又可以进一步写为$\sum_{t’=t}^{T_n}\gamma^{t’-t} r_{t’}^{n}$，其中$\gamma$作为discount factor(折扣因子)并且$\gamma < 1$，因此可以得到：

$$\nabla \overline R_\theta \approx \frac{1}{N}\sum_{n=1}^{N}\sum_{t=1}^{T_n}(\sum_{t’=t}^{T_n}\gamma^{t’-t} r_{t’}^{n}-b)\nabla p_\theta(a_t^n|s_t^n)\tag{10}$$

On-policy v.s. Off-policy

On-policy：agent学习与交互的环境是相同的。On-Policy可以翻译为”同策略”
Off-policy：agent学习的环境和交互的环境并不相同。Off-Policy可以翻译为”异策略”

从On- policy转向Off-policy的分析

On-policy的情况下，Policy Gradient的公式为:

$$\nabla \overline R_\theta = E_{\tau \sim p_\theta(\tau)}[R(\tau)\nabla logp_\theta(\tau)]\tag{11}$$

在On-policy中，我们使用$\pi_{\theta}$去收集数据，当$\theta$被更新的时候，我们必须去重新采样训练数据。

我们现在的目标是：使用$\pi_{\theta’}$采样获得数据去训练$\theta$。$\theta’$是一个固定的值，因此我们可以重复利用采样的数据。

重要性采样

如果正常从p中进行采样获得x的期望值：

$$E_{x\sim p}[f(x)] \approx \frac{1}{N}\sum_{i=1}^{N}f(x^i)\tag{12}$$

但是现在我们不从p中采样，只能从q中采样呢？

$$E_{x\sim p}[f(x)] \approx \frac{1}{N}\sum_{i=1}^{N}f(x^i)=\int f(x)p(x)dx= \int f(x) \frac{p(x)}{q(x)}q(x)dx= E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]\tag{13}$$

通过这样的变换，我们就达到了从q中采样获取x期望值的效果。

重要性采样公式为：

$$E_{x\sim p}[f(x)]= E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]\tag{14}$$

On-policy->Off-policy

$$\nabla \overline R_\theta = E_{(s_t,a_t)\sim \pi_\theta}[A^\theta(s_t,a_t)\nabla logp_\theta(a_t^n|s_t^n)]=E_{(s_t,a_t)\sim \pi_\theta’}[\frac{P_\theta(s_t,a_t)}{P_\theta’(s_t,a_t)}A^{\theta’}(s_t,a_t)\nabla logp_\theta(a_t^n|s_t^n)]$$

$$=E_{(s_t,a_t)\sim \pi_\theta’}[\frac{p_\theta(a_t|s_t)}{p_\theta’(a_t|s_t)}\frac{p_\theta(s_t)}{p_\theta’(s_t)}A^{\theta’}(s_t,a_t)\nabla logp_\theta(a_t^n|s_t^n)]\tag{15}$$

由于我们假设$\theta$与$\theta’$是一样的，因此${p_\theta(s_t)}$和 $ p_\theta’(s_t)$这两个同环境相关的参数可以约掉，而${p_\theta(a_t|s_t)}$和${p_\theta’(a_t|s_t)}$是同动作选择相关，并没有假设它们的动作选择一致，因此不能约掉。因此我们得到：

$$J^{\theta’}(\theta) = E_{(s_t,a_t)\sim \pi_{\theta’}}[\frac{p_\theta(a_t|s_t)}{p_{\theta’}(a_t|s_t)}A^{\theta’}(s_t,a_t)]\tag{16}$$

Add Constraint

$\theta$和$\theta’$的区别是一个值得讨论的问题。在这里我们所说的区别并不是$\theta$和$\theta’$参数上的不同，而是说它们在表现上的不同的程度需要被限制，而想要这个区别被限制，就必须要使它可以被量化。因此，在PPO中，使用$KL(\theta,\theta’)$对$\theta$和$\theta’$在表现上的不同的程度进行量化。由此可以得到两个算法，即Proximal Policy Optimization(PPO)和TRPO(Trust Region Policy Optimization)：

Proximal Policy Optimization(PPO)

$$J_{PPO}^{\theta’}(\theta) = J^{\theta’}(\theta) - \beta KL(\theta,\theta’)\tag{17}$$

TRPO(Trust Region Policy Optimization)

$$J_{TRPO}^{\theta’}(\theta) = E_{(s_t,a_t)\sim \pi_{\theta’}}[\frac{p_\theta(a_t|s_t)}{p_{\theta’}(a_t|s_t)}A^{\theta’}(s_t,a_t)]\tag{18}$$

在TRPO中，$KL(\theta,\theta’)$以单独的限制存在，一般为$KL(\theta,\theta’)<\delta$.

因此，PPO算法的伪代码如下：

Initial policy parameters $\theta^0$
In each iteration:
- Using $\theta^k$ to interact with the environment to collect ${s_t,a_t}$ and compute advatage $A_{\theta^k}(st,at)$
- Find $\theta$ optimizing $J_{PPO}(\theta)$
- $J_{PPO}^{\theta^k} = J^{\theta^k}(\theta) - \beta \times KL(\theta,\theta^k)$ # Update parameters several times
与此同时，动态调整$\beta$:
- If $KL(\theta,\theta^k) > KL_{max}$,increase $\beta$
- If $KL(\theta,\theta^k) < KL_{min}$,decrease $\beta$

这就完成了 KL Penalty的建立。

第二种PPO算法

在这个PPO算法中，并不是使用KL函数，而是使用clip函数，所谓的clip函数是指$clip(\frac{p_\theta(a_t|s_t)}{p_\theta^k(a_t,s_t)},1-\epsilon,1+\epsilon)$，当$\frac{p_\theta(a_t|s_t)}{p_\theta^k(a_t,s_t)}$的值小于$1-\epsilon$时，它的值取$1-\epsilon$,当$\frac{p_\theta(a_t|s_t)}{p_\theta^k(a_t,s_t)}$的值大于$1+\epsilon$时，它的值取$1+\epsilon$.因此可得：

$$J_{PPO2}^{\theta^k}(\theta) \approx \sum_{(s_t,a_t)}min(\frac{p_\theta(a_t|s_t)}{p_\theta^k(a_t|s_t)}A^{\theta^k}(s_t,a_t),clip(\frac{p_\theta(a_t|s_t)}{p_\theta^k(a_t,s_t)},1-\epsilon,1+\epsilon)A^{\theta^k}(s_t,a_t))\tag{19}$$

$\frac{p_\theta(a_t|s_t)}{p_\theta^k(a_t|s_t)}$和$clip(\frac{p_\theta(a_t|s_t)}{p_\theta^k(a_t,s_t)},1-\epsilon,1+\epsilon)$的图像如图所示：

secondppo

PPO的网络结构

网络结构

一个actor网络，一个critic网络

actor网络的输入为状态，输出为动作概率$\pi(a_t|s_t)$(对于离散动作空间而言)或者动作概率分布参数（对于连续动作空间而言）
critic网络的输入为状态，输出为状态的价值。

显然，如果actor网络输出的动作能够使优势（$A^\theta(s_t,a_t)$）变大，那么就越好。如果critic网络输出的状态价值越准确，那么就越好。

产生experience的过程

已知一个状态$s_0$，通过actor网络得到所有动作的概率（图中以三个动作：$a,b,c$为例），然后依概率采样得到动作$a_0$，然后将$a_0$输入到环境中，得到$s_1$和$r_1$。状态价值$v(s_0)$是通过critic网络输出得到的，这样就得到一个experience：$(s_0,a_0,r_1,v(s_0),logP(a_0|s_0))$，然后将experience放入经验池中(当然之后还会计算$A(s_0,a_0))$以及$G_0$，经验池中也存放了这两个信息)。

注：虽然$v(s_0)$可以用一条轨迹的折扣回报得到，即：$v(s_0)=r_1+\gamma r_2+…+\gamma^{T}r_{T+1}+\gamma^{T+1}v(s_{T+1})$,但是轨迹末状态的下一状态$s_{T+1}$的$v(s_{T+1})$还是需要critic网络来估计，当然如果$s_{T+1}$是正常游戏结束，而不是达到了最大步长，那么令$v(s_{T+1}=0$)。与其这样，还不如直接用critic网络直接估计$v(s_0)$，而且值得注意的是，$v(s_0)=r_1+\gamma r_2+…+\gamma^{T}r_{T+1}+\gamma^{T+1}v(s_{T+1})$正是我们critic网络作为监督学习的真值

以上是离散动作的情况，如果是连续动作，就输出概率分布的参数（比如高斯分布的均值和方差），然后按照概率分布去采样得到动作$a_0$。

经验池存在的意义是更加方便的计算一条轨迹上状态的累积折扣回报$v(s_t)$以及优势$A(s_t,a_t)$而不是消除experience的相关性。

Actor网络的更新流程

对优势函数进行定义：

$$\hat A_t = \delta_t+(\gamma \lambda)\delta_{t+1}+…+…+(\gamma \lambda)^{T-t+1}\delta_{T-1},\tag{20}$$

$$where \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)\tag{21}$$

因为Actor网络需要输出的动作优势尽可能的大，所以它的训练需要用以下表达式作为Loss函数:

$$L^{CLIP}(\theta) = \hat {\mathbb E}_t[min(r_t(\theta)\hat A_t,clip(r_t(\theta),1-\epsilon,1+\epsilon)\hat A_t\tag{22}$$

其中$$r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}$$

值得注意的是： 和TD3算法的单步TD不同，PPO算法使用多步TD，因此它需要跑完一条轨迹后，才开始计算各个状态的累积回报和动作的优势。具体而言，状态价值，$v(s_0)$，$v(s_1)$ 是通过critic网络输出得到的，动作优势 $A(s_0,a_0)$ 是通过首先计算$ \delta_0=r_1+v(s_1)−v(s_0) $，然后用 $\gamma \lambda$作为折扣因子去计算动作优势 $A(s_0,a_0)$ ，具体可以看公式（20）。

因此训练actor网络的时候需要将经验池中的所有数据都拿出来，计算loss，然后用梯度上升法，多更新几步梯度。更新完成后即将经验池清空，等待下一个新的actor网络与环境互动去收集数据。

PyTorch 代码如下：

# train actor net
        all_pi_tensor = self.actor_net(state_tensor)
        pi_tensor = all_pi_tensor.gather(1, action_tensor.unsqueeze(1)).squeeze(1)
        surrogate_advantage_tensor = (pi_tensor / old_pi_tensor) *                 advantage_tensor
        clip_times_advantage_tensor = 0.1 * surrogate_advantage_tensor
        max_surrogate_advantage_tensor = advantage_tensor +                 torch.where(advantage_tensor > 0.,
                clip_times_advantage_tensor, -clip_times_advantage_tensor)
        clipped_surrogate_advantage_tensor = torch.min(
                surrogate_advantage_tensor, max_surrogate_advantage_tensor)
        actor_loss_tensor = -clipped_surrogate_advantage_tensor.mean()
        self.actor_optimizer.zero_grad()
        actor_loss_tensor.backward()
        self.actor_optimizer.step()

Critic网络的更新流程

Actor网络更新后，接着拿从经验池buffer中采出的数据进行Critic网络的更新（数据已经计算了状态价值，折扣回报$G_t$的计算是基于多步TD的方法，从那个状态开始，用每一步环境返回的奖励 R 与折扣因子相乘后累加，即：$G_t = r_{t+1} + \gamma r_{t+2} + … + \gamma^{T-t}r_{T+1} + \gamma^{T+1-t}v(s_{T+1})$，其中$v(s_{T+1})$为网络的估计值，更新方式即为：计算好的折扣回报 $G_T$与Critic网络预测当前状态价值 $v(s_t)$ 做差，用MSEloss作为Loss函数，对神经网络进行训练。

pytorch代码如下：

# train critic net
        pred_tensor = self.critic_net(state_tensor)
        critic_loss_tensor = self.critic_loss(pred_tensor, return_tensor)
        self.critic_optimizer.zero_grad()
        critic_loss_tensor.backward()
        self.critic_optimizer.step()

为什么说TRPO和PPO是On-policy的？

首先我们明确什么是on-policy，什么是off-policy？

on-policy：就是要训练的agent跟环境互动的agent是同一个agent,也就是我们采样的网络和要优化的网络是否是同一个网络。
off-policy：那肯定就是跟上面相反的。

那么进入正题，我们一般认为PPO是off-policy的原因就是因为PPO使用actor网络去sampler然后填充经验池，然后使用这个经验池中的数据去更新这个actor多个epoch，当更新到第二个epoch的时候那么actor就变成了actor1,然而经验池中的数据仍然是actor网络采样得到的，那么就造成了从更新第二个epoch开始采样的actor和要优化的actor不是同一个网络，那么可能就会认为它是off-pocliy的。

其实可以很简单的解释这个问题，根据off-policy的定义，采样的网络和要优化的网络不是一个网络，那么对于PPO来说，使用一批数据从更新actor的第二个epoch开始，数据虽然都是旧的actor采样得到的，但是我们并没有直接使用这批数据去更新我们的新的actor，而是使用imporance sampling先将数据分布不同导致的误差进行了修正。那么这个importance sampling的目的就是让这两者数据分布之间的差异尽可能的缩小，那么就可以近似理解成做了importance sampling之后的数据就是我们的更新（这里的更新指的是多个epoch更新的中间过程）后的actor采样得来的，这样就可以理解成我们要优化得actor和采样得actor是同一个actor，那么他就是on-policy的。

Conclusion[3]

We have introduced proximal policy optimization, a family of policy optimization methods that use multiple epochs of stochastic gradient ascent to perform each policy update.These methods have the stability and reliability of trust-region methods but are much simpler to implement**, requiring only few lines of code change to a vanilla policy gradient implementation, applicable in more general settings (for example, when using a joint architecture for the policy and value function), and have better overall performance.

我们介绍了近程策略优化，这是一系列策略优化方法，使用随机梯度上升的多个周期来执行每个策略更新。这些方法具有信任域方法的稳定性和可靠性，但实现起来要简单得多，只需要很少的代码行就可以改变成一个普通的策略梯度实现，适用于更一般的设置（例如，当使用策略和值函数的联合体系结构时），并且具有更好的整体性能。

参考文献

【DRL-16】Proximal Policy Optimization : https://zhuanlan.zhihu.com/p/142312072
为什么说TRPO和PPO是on-policy的？:https://zhuanlan.zhihu.com/p/387193698
Proximal Policy Optimization Algorithms:arXiv:1707.06347v2 [cs.LG] 28 Aug 2017