EvoRL(二)：EPO算法

之前，《EvoRL(一)：为什么要演化算法与RL结合？》描述了演化算法与RL的结合是为了提升智能体的探索能力。接下来，介绍一下两者结合的《Evolutionary Policy Optimization》算法。

智能体选择的演化算法

根据生物演化，初始化智能体群$(\{\pi_k\}_{k=1}^K)$，每个智能体拥有一个隐式编码$(\{\pi_k\}_k^K)$。智能体共享同样的actor-critic网络架构，分别被参数化为$\theta,\psi$，两者的输入均为当前状态和隐式编码。为了简洁性，master智能体为$\pi_1(\theta,\psi,\phi_1)$。那么，演化算法框架为：

selection：根据相对fitness分数成比例的幸存概率，决定存活在下一代的智能体。确切的说，top排序的$x\in[2,K]$作为非master智能体形成集合$X$，作为下一代智能体集合$Y$。

crossover：从$X$中随机选择两个智能体$\pi_i(\theta,\psi,\phi_i),\pi_j(\theta,\psi,\phi_j)\in X$，对其隐变量求均值$\{{\phi}^{'}=\frac{1}{2}\times(\phi_i,\phi_j)\}$。

mutation：对${\phi}'$增加高斯噪音，即${\phi}''={\phi}'+\epsilon,\epsilon\in\mathcal{N}(0,\sigma^2)$。那么，智能体$\pi(\theta,\psi,{\phi}'')$添加到下一代$Y$。

其中，fitness值可为累积奖励和成功率。

值得注意的是：该演化算法框架是建立在PPO基础上。更确切的说，参数$(\theta,\psi,\{\phi_k\}_{k=1}^K)$基于混合策略算法SAPG进行更新。

演化更新的时间

对于复杂的任务，策略需要很长时间才能获得有意义的表现，执行过早的演化更新是不高效的。确切的说，只有fitness分数超过中位数的特定比例才进行演化，即
$$
max\{f_k\}_{k=2}^K-min\{f_k\}_{k=2}^K\gt\gamma\cdot median(f_k)_{k=2}^{K}
$$
式中$f_k$为智能体$\pi_k$的fitness分数。
另一种方法是：固定时间间隔之后，应用selection, crossover, 和mutation。

为什么是SAPG?

与off-policy相比，on-policy算法样本效率低，但可拟合到更高的渐进表现，这也是PPO在控制领域大行其道的原因之一。然而，随着环境数量的增加，即batch-size增加到一定程度后，PPO的表现会处于饱和。这主要是因为数据采样机制使每个环境执行的策略均在高斯分布的均值附近，从而导致许多环境执行相似的动作，产生相关性较高的数据，最终导致环境的增加不会一直提升性能。

为了解决该问题，SAPG把环境分成blocks，每个block优化独立的策略，从而允许数据的多样性。接下来，再利用off-policy结合所有策略产生的数据，更新master策略。这种方式可同时拥有ppo的稳定性和锁定高奖励轨迹。

由此可知，SAPG智能体分为两层，与演化算法框架天然的匹配。或者说，该演化算法就是在SAPG基础上提出的。这种方式可结合PPO算法的稳定性和渐进表现和演化算法的探索能力，甚至off-policy算法的样本效率。

混合策略优化

不同的智能体收集到的数据显著不同，为了master智能体利用所有可获得数据，EPO采用了SAPG的off-policy方式aggregate数据。确切的说，先从智能体$\{\pi_k\}_{k=2}^K$收集到的数据$\cup_{k=2}^KS_k$采样$\vert S_1\vert$个转换，得到${S}'_1$。
为了更新master智能体，off-policy损失被定义为
$$
\begin{aligned}
L_{off}(\pi_1,{S}'_1)=\frac{1}{\vert{S}'_1\vert}\underset{(s,a)\sim{S}'_1}{\mathbb{E}}[min(r_{\pi_1}(s,a)A^{\pi_1,old}(s,a),\\
clip(r_{\pi_1}(s,a),\mu(1-\epsilon),\mu(1+\epsilon))A^{\pi_1,old}(s,a))]
\end{aligned}\tag{1}
$$

式中$r_{\pi_1}(s,a)=\frac{\pi_1(s,a)}{\pi_k(s,a)}$为重要性采样比率，$\mu=\frac{\pi_{1,old}(s,a)}{\pi_k(s,a)}$为off-policy纠正项

on-policy损失被定义为：
$$
\begin{aligned}
L_{on}(\pi_{\theta})=\underset{\pi_{old}}{\mathbb{E}}[min(r_t(\pi_{\theta})A_t^{\pi_{old}},clip(r_t(\pi_{\theta}),1-\epsilon,1+\epsilon)A_t^{\pi_{old}})]
\end{aligned}\tag{2}
$$

式中$r_t(\theta)=\frac{\pi_{\theta}(a_t\vert s_t)}{\pi_{old}(a_t\vert s_t)}$，$\epsilon$为clip超参数，$\pi_{old}$为策略收集的on-policy数据

final policy loss被定义为：
$$
\begin{aligned}
L(\pi_1)=L_{on}(\pi_1)+\lambda\cdot L_{off}(\pi_1,{S}'_1)
\end{aligned}\tag{3}
$$

混合数据的critic更新

对于on-policy数据，critic的目标值的n-steps回报更新：
$$
\begin{aligned}
\hat{V}^{target}_{on,\pi_k}(s_t)=\sum_{m=t}^{t+2}\gamma^{m-t}r_m+\gamma^3V_{\pi_k,old}(s_{t+3})
\end{aligned}\tag{4}
$$
其损失函数为：
$$
\begin{aligned}
L_{on}^{critic}(\pi_k)=\underset{(s,a)\sim\pi_k}{\mathbb{E}}[(V_{\pi_k}(s)-\hat{V}_{on,\pi_k}^{target}(s))^2]
\end{aligned}\tag{5}
$$

对于off-policy数据，近似1-step回报：
$$
\begin{aligned}
\hat{V}_{off,\pi_1}^{target}({s}'_t)=r_t+\gamma V_{\pi_1,old}({s}'_{t+1})
\end{aligned}\tag{6}
$$
其损失函数为
$$
\begin{aligned}
L_{off}^{critic}(\pi_1,{S}'_1)=\frac{1}{\vert {S}'_1\vert}\underset{(s,a)\sim{S}'_1}{\mathbb{E}}[V_{\pi_1}(s)-\hat{V}_{off,\pi_1}^{target}(s)]^2
\end{aligned}\tag{7}
$$

final critic loss被定义为：
$$
\begin{aligned}
L^{critic}(\pi_1)=L_{on}^{critic}(\pi_1)+\lambda\cdot L_{off}^{critic}(\pi_1,{S}'_1)
\end{aligned}\tag{8}
$$
除了master智能体$\pi_1$，其它智能体均利用on-policy损失更新，即式(2)和(5)，从而确保了智能体更新的稳定性。
EPO算法可见算法$1$

One-More Thing

SAPG的Aggregate数据的方法还有对称和Leader-Follower Aggregation，感兴趣读者可阅读论文。