【DataWhale导读】李宏毅老师的深度强化学习之PPO（近端策略优化）部分内容。

1. 概念/关键词

名称	解释
On-Policy	学习的agent和与环境互动的agent是同一个（自己打王者）
Off-Policy	学习的agent和与环境互动的agent不是同一个（学习主播打王者）
$A^{\theta }\left(s_t,a_t\right)$	Advantage Function
importance sampling	使用另外一种数据分布，来逼近所求分布的一种方法，在强化学习中通常和蒙特卡罗方法结合使用

2. from on-policy to off-policy

上一篇文章讲的是Policy Gradient, 这是一种on-policy的做法，因为这个算法是一边跟环境互动，一边按照Policy Gradient的公式来更新$\pi$的参数。

off-policy就是让当前agent学习另外一个agent经历过的轨迹，从而学习到策略，这个过程中可以重复利用采样得到的数据。

Importance Sampling(重要性采样)

重要性采样是蒙特卡洛积分的一种采样策略，详解：https://zhuanlan.zhihu.com/p/41217212

简单解释一下，下面是一个普通的期望，$x^i$是从p(x)中采样的，可以获取到的。
$$\begin{gathered} E_{x\sim p}[f(x)]\approx \frac{1}{N}\sum _{i=1}^{N}f(x^i) \\ {x}^i\text{is sampled from }p(x) \end{gathered}$$
添加一个约束，这里只有从q(x)中采样得到的$x^i$（无法直接从p(x)中获取），那么如何计算这个期望呢？这就要用到重要性采样。
$$\begin{gathered} E_{x\sim p}[f(x)]=\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)}] \end{gathered}$$
通过引入$\frac{p(x)}{q(x)}$这个weight，就可以将从p中sample数据的问题转化为从q中sample数据的问题。

ISSUE: 存在问题

虽然$E_{x\sim p}[f(x)]=E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]$, 但是两者的方差不同，如果两者$\frac{p(x)}{q(x)}$差距过大，这样估计出来的结果方差过大，无法正常使用。

将重要性采样引入Policy Gradient

上一篇讲的Policy Gradient公式:
$$\nabla \overline{R_{\theta }}=E_{\tau \sim p_{\theta }(\tau )}[R(\tau )\nabla log{p}_{\theta }(\tau )]$$

这种模式是让$\theta$和环境去做互动，然后sample得到Trajectory，计算对应梯度。

为了将on-policy打造成off-policy方法，进行如下修改：
$$\nabla \overline{R_{\theta }}=E_{\tau \sim p_{\theta }^{\prime }(\tau )}[\frac{p_{\theta }(\tau )}{p_{{\theta }^{\prime }(\tau )}}R(\tau )\nabla log{p}_{\theta }(\tau )]$$
也就是说，数据来源于$p_{{\theta }^{\prime }}$中获取的，而不是$p_{\theta }$。

这种模型不需要$\theta$和环境互动，存在另外一个policy ${\theta }^{\prime }$, 其工作就是和环境做互动，sample得到Trajectory就可以供$\theta$学习。

详细推导

Gradient for update
$$\nabla \bar{J}=E_{\left(s_t,a_t\right)\sim {\pi }_{\theta }}\left[A^{\theta }\left(s_t,a_t\right)\nabla \log p_{\theta }\left(a_t^n|s_t^n\right)\right]$$
然后引入重要性采样：
$$=E_{\left(s_t,a_t\right)\sim {\pi }_{{\theta }^{\prime }}}\left[\frac{P_{\theta }(s_t,a_t)}{P_{{\theta }^{\prime }}(s_t,a_t)}{A}^{{\theta }^{\prime }}\left(s_t,a_t\right)\nabla \log p_{\theta }\left(a_t^n|s_t^n\right)\right]$$
注意A的角标也应该变成${\theta }^{\prime }$。然后展开重要性weight：
$$=E_{\left(s_t,a_t\right)\sim {\pi }_{{\theta }^{\prime }}}\left[\frac{p_{\theta }(a_t|s_t)p_{\theta }(s_t)}{p_{{\theta }^{\prime }}(a_t|s_t)p_{{\theta }^{\prime }}(s_t)}{A}^{{\theta }^{\prime }}\left(s_t,a_t\right)\nabla \log p_{\theta }\left(a_t^n|s_t^n\right)\right]$$
其中$\frac{p_{\theta }(s_t)}{p_{{\theta }^{\prime }}(s_t)}$可以消去，因为出现state的概率和$\theta$是没有关系的，和environment有关系，所以有$p_{\theta }(s_t)=p_{{\theta }^{\prime }}(s_t)$。消去后得到：
$$\nabla J=E_{\left(s_t,a_t\right)\sim {\pi }_{\theta }}\left[\frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^{\prime }}(a_t|s_t)}{A}^{{\theta }^{\prime }}\left(s_t,a_t\right)\nabla \log p_{\theta }\left(a_t^n|s_t^n\right)\right]$$
可以通过$\nabla f(x)=f(x)\nabla \log f(x)$反推目标函数，由于过程太多，不便用markdown书写，具体过程如下图所示：

推到结果如下：
$$J^{{\theta }^{\prime }}(\theta )=E_{\left(s_t,a_t\right)\sim {\pi }_{{\theta }^{\prime }}}\left[\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^{\prime }}\left(a_t|s_t\right)}{A}^{{\theta }^{\prime }}\left(s_t,a_t\right)\right]$$
$J^{{\theta }^{\prime }}(\theta )$中的$\theta$代表的是需要去optimize的参数，$\theta ’$代表真正跟环境互动的agent，通过${\theta }^{\prime }$sample 到的轨迹来让$\theta$学习。到这一步，就可以将on-policy替换成off-policy，但是需要满足一个条件，分子分母不能相差太多，如何让他们相差不多呢？PPO算法就是用来解决这个问题。

3. PPO/TRPO

上面已经得到了目标函数，在此基础上，PPO添加了一个正则项。
$$\begin{gathered} J_{PPO}^{{\theta }^{\prime }}(\theta )=J^{{\theta }^{\prime }}(\theta )-\beta KL(\theta ,{\theta }^{\prime }) \\ {J}^{{\theta }^{\prime }}(\theta )=E_{\left(s_t,a_t\right)\sim {\pi }_{{\theta }^{\prime }}}\left[\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^{\prime }}\left(a_t|s_t\right)}{A}^{{\theta }^{\prime }}\left(s_t,a_t\right)\right] \end{gathered}$$
可以看到区别在于$\beta KL(\theta ,{\theta }^{\prime })$, KL代表的是KL divergence散度，KL散度是用来衡量两个分布的相似程度，越相似，loss越小。
$$KL(p,q)=\sum _{i=1}^{n}p(x_i)log(\frac{p(x_i)}{q(x_i)})$$
目标是最大化$J_{PPO}^{{\theta }^{\prime }}(\theta )$，那就要最小化$KL(\theta ,{\theta }^{\prime })$,也就是说两者分布越接近越好。KL散度衡量的不是参数上的距离，而是行为上的距离，对action的space距离进行衡量。

TRPO

TRPO是PPO的前身：
$$\begin{array}{r}{J}_{TRPO}^{{\theta }^{\prime }}(\theta )=E_{\left(s_t,a_t\right)\sim {\pi }_{{\theta }^{\prime }}}\left[\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^{\prime }}\left(a_t|s_t\right)}{A}^{{\theta }^{\prime }}\left(s_t,a_t\right)\right]\\ \\ \mathrm{K}\mathrm{L}\left(\theta ,{\theta }^{\prime }\right)<\delta \end{array}$$
不同之处在于TRPO将KL散度作为约束条件，这种方法很难处理的，很难算（属于二次规划问题吧），最好还是使用PPO来求解，两者达到的效果差不多。

3.1 PPO-Penalty

算法流程如上，先收集s,a组成的pair, 然后计算advantage function(具体如何计算不是很清楚目前，具体算法可能不一样)，最后根据PPO更新目标函数即可，$\beta$是一个超参数，可以通过以上式子进行动态控制。

3.2 PPO-Clip

也就是视频中提到的PPO2, 如下公式所示：
$$\begin{array}{rl}{J}_{PPO2}^{{\theta }^k}(\theta )\approx \sum _{\left(s_t,a_t\right)}\min & (\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)}{A}^{{\theta }^k}\left(s_t,a_t\right),\\ & \mathrm{clip}\left(\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)},1-\epsilon ,1+\epsilon \right)A^{{\theta }^k}\left(s_t,a_t\right))\end{array}$$
首先理解这个部分：
$$\mathrm{clip}\left(\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)},1-\epsilon ,1+\epsilon \right)$$

上图的横轴是 $\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)}$，纵轴是 clip function 的输出。

• 如果 $\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)}$ 大于$1+\epsilon$，输出就是 $1+\epsilon$。
• 如果小于 $1-\epsilon$， 它输出就是 $1-\epsilon$。
• 如果介于 $1+\epsilon$ 跟 $1-\epsilon$ 之间， 就是输入等于输出。

• $\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)}$ 是绿色的线；
• $\mathrm{clip}\left(\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)},1-\epsilon ,1+\epsilon \right)$ 是蓝色的线；
• 在绿色的线跟蓝色的线中间，要取一个最小的。假设前面乘上的这个 term A，它是大于0 的话，取最小的结果，就是红色的这一条线。

可以得到结论：这个式子想要做的事情就是希望 $p_{\theta }(a_t|s_t)$ 跟 $p_{{\theta }^k}(a_t|s_t)$，也就是你拿来做 demonstration 的 model 跟你实际上 learn 的 model，在 optimize 以后不要差距太大

怎么让它做到不要差距太大呢？

• 如果 A > 0，也就是某一个 s，a 的 pair 是好的，那希望增加这个pair 的概率， $p_{\theta }(a_t|s_t)$ 越大越好，但跟 $p_{{\theta }^k}(a_t|s_t)$ 的比值不可以超过 $1+\epsilon$。
  • 如果超过 $1+\epsilon$ 的话，就没有 benefit 了。在 train 的时候，当 $p_{\theta }(a_t|s_t)$ 被 train 到 $\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)}>1+\epsilon$ 时，它就会停止。
  • 假设 $p_{\theta }(a_t|s_t)$ 比 $p_{{\theta }^k}(a_t|s_t)$ 还要小，并且这个 advantage 是正的。这个 action 是好的，当然希望这个 action 被采取的概率越大越好，希望 $p_{\theta }(a_t|s_t)$ 越大越好。所以假设 $p_{\theta }(a_t|s_t)$ 还比 $p_{{\theta }^k}(a_t|s_t)$ 小，那就尽量把它挪大，但只要大到 $1+\epsilon$ 就好。
• 如果 A < 0，也就是某一个 s，a pair 是不好的，希望把 $p_{\theta }(a_t|s_t)$ 减小。如果 $p_{\theta }(a_t|s_t)$ 比 $p_{{\theta }^k}(a_t|s_t)$ 还大，那你就尽量把它压小，压到 $\frac{p_{\theta }\left(a_t|s_t\right)}{p_{{\theta }^k}\left(a_t|s_t\right)}$ 是 $1-ϵ$ 的时候就停了，就不要再压得更小。

4. 参考

https://www.bilibili.com/video/BV1MW411w79n?p=2

https://datawhalechina.github.io/leedeeprl-notes/#