演化策略作为强化学习的一种可扩展替代方案
演化策略属于一类黑盒优化算法,可作为基于MDP框架的强化学习技术的替代方案。与RL相比,演化策略拥有扩展性强、对动作频率和延时奖励不变的特性、容忍极长时间窗口、以及不需要时序折扣或价值函数近似的优势。然而,该方法对较为困难的RL问题并不是非常有效。同时,作者们发现:
- 虚拟batch normalization和神经网络的重参数化可极大的提升演化策略的可靠性。
- 通过引入基于常用随机数的通信方法,演化策略可扩展到数千台机器,且可实现线性加速。
- 演化策略的数据效率很好,利用3倍到10倍的数据可实现与A3C同等性能。这种数据效率的减少可被不需要执行反向传播和计算价值函数而部分抵消。
- 与策略梯度方法相比,演化策略可展现更好的探索行为。
- 演化策略拥有很好的鲁棒性,只需要利用固定超参数就可以实现较好的性能。
演化策略
演化策略是受到自然演化启发的搜索过程。在每次迭代,一个参数向量的族群被扰动且目标函数被评估,然后最高分数的参数向量被重新结合形成新的族群,该过程被持续的迭代直到目标被完全的优化。在该类算法中,主要的不同之处在于表示族群和执行变换与重新结合的不同。
对于自然演化策略,若利用$F$表示参数为$\theta$的目标函数,族群利用关于参数的分布$p_{\psi}(\theta)$表示,那么目标为利用随机梯度上升搜索$\psi$最大化整个族群的目标价值函数估计器$\mathbb{E}_{\theta\sim p_{\psi}}F(\theta)$。确切的说,自然演化策略的梯度估计器为
$$
\begin{aligned}
\nabla_{\psi}\mathbb{E}_{\theta\sim p_{\psi}}F(\theta)=\mathbb{E}_{\theta\sim p_{\psi}}\{F(\theta)\nabla_{\psi}logp_{\psi}(\theta)\}
\end{aligned}\tag{1}
$$
对于RL问题,$F(\cdot)$为环境提供的随机回报,$\theta$为确定性或随机性策略$\pi_{\theta}$参数,用于描述智能体在环境中的行动。
RL算法的创新主要聚焦在处理环境或策略倒数的存在或不可获取,从而产生不平滑。ES处理不平滑可通过初始化族群分布$p_{\psi}$为均值$\psi$的各项同性多变量高斯分布和固定协方差矩阵$\sigma^2 I$,那么$\mathbb{E}_{\theta\sim p_{\psi}}F(\theta)=\mathbb{E}_{\epsilon\sim N(0,1)}F(\theta+\sigma\epsilon)$。在该设置下,随机目标可被视为原始目标函数$F$的高斯扰动版,其不会受到环境或动作引入的非平滑影响。在$\theta$定义下的目标,分数函数估计器为
$$
\begin{aligned}
\nabla_{\theta}\mathbb{E}_{\epsilon\sim N(0,1)}F(\theta+\sigma\epsilon)=\frac{1}{\sigma}\mathbb{E}_{\epsilon\sim N(0,I)}\{F(\theta+\sigma\epsilon)\epsilon\}
\end{aligned}\tag{2}
$$
由此,可得算法1

扩展与并行化演化策略
ES非常适合扩展到许多并行workers,这是因为:
- ES在整个episodes上运行,因此不需要高频的通信。
- 若在优化之前worker之间同步彼此的随机种子,那么每个worker只需要获得episode的回报值。
- 不需要价值函数近似。对于RL来说,若要在给定策略下,价值函数获得足够的信号进行多次更新才能使价值函数估计与策略匹配。
ES的并行版本可见算法2

在训练的开始,作者们对每个worker初始化一个大block的高斯噪音,然后在每次迭代对这些噪音变量增加随机噪音子集的方式扰动参数。虽然这意味着每次扰动并不是严格独立的,但是在实践中未发现任何问题。
为了减少方差,作者们在ES算法中采用了镜像采样,即每次评估噪音$\epsilon,-\epsilon$扰动。同时,作者们也发现在计算每个参数更新前对回报利用秩变换可重塑平滑性。这种方式也减少了族群中异常值的影响和收敛到局部最小点的影响。除此之外,为了防止参数增长比扰动大,作者们还对网络参数利用了权重衰减。由于在训练过程中,作者们没有发现自使用$\sigma$带来的益处,因此把它视为固定的超参数。
网络参数化的影响
对于RL,通过从随机策略采样动作的方式进行探索,演化策略通过对参数扰动的方式进行探索。因此,高斯扰动向量$\epsilon$偶尔导致新的单个$\theta+\sigma\epsilon$实现更好回报很重要。然而,在Atari的特定环境中,作者们发现随机扰动参数导致策略倾向于输出特定的动作。同时,作者们发现虚拟batch normalization使策略对输入微小变动很敏感,有很大的影响。
参数空间的平滑与动作空间的平滑
RL困难根本原因是缺乏策略性能的极具信息的梯度,这种梯度可能由于环境或策略的非平滑,或者只在高方差估计时可获得。确切的说,若在执行动作序列$a=\{a_1,\ldots,a_T\}$之后获得奖励$R(a)$,其中动作可被确定性或随机策略函数$a_t=\pi(s;\theta)$确定,那么优化目标为
$$
\begin{aligned}
F(\theta)=R(a(\theta))
\end{aligned}\tag{3}
$$
为了使问题变得平滑且有一种估计梯度的方式,那么需要加入噪音。策略梯度方法在动作空间加入噪音,而进化策略在参数空间加入噪音。
演化策略性能优于策略梯度的条件
两种方式的选择取决于决策问题的结构和Monte-Carlo估计器估计梯度的类型。假设回报与单个动作之间的相关性很低,利用MC进行梯度估计,那么
$$
\begin{aligned}
Var[\nabla_{\theta}F_{PG}(\theta)]\approx Var[R(a)]Var[\nabla_{\theta}logp(a;\theta)] \\
Var[\nabla_{\theta}F_{ES}(\theta)]\approx Var[R(a)]Var[\nabla_{\theta}logp(\tilde{\theta};\theta)] \\
\end{aligned}\tag{4}
$$
若两种方法的探索量相似,那么$Var[R(a)]$几乎无差别。由于$\nabla_{\theta}logp(a;\theta)=\sum_{t=1}^T\nabla_{\theta}logp(a_t;\theta)$为$T$个相关项的和,那么策略梯度估计器的方差几乎随着$T$线性的增长。演化策略的对应项大小与$T$无关。因此,在长episodes中,进化策略因此比策略梯度有优势。
问题维度
演化策略的梯度估计可被解释为在高纬空间随机有限差的方法。若利用$\mathbb{E}_{\epsilon\sim N(0,I)}\{F(\theta)\epsilon/\sigma\}=0$,那么
$$
\begin{aligned}
\nabla_{\theta}\eta(\theta)=\mathbb{E}_{\epsilon\sim N(0,I)}\{F(\theta+\sigma\epsilon)\epsilon/\sigma\}=\mathbb{E}_{\epsilon\sim N(0,I)}\{(F(\theta+\sigma\epsilon)-F(\theta))\epsilon/\sigma\}
\end{aligned}\tag{5}
$$
由于ES可被视为在随机选择方向计算一个有限差导数的估计,那么随着参数$\theta$的扩展性很差。然而,作者们表明其扩展性与优化问题的困难程度或内在维度更有关。在实践中,作者们还观测到了利用参数多神经网络拥有更好的效果,可能是因为深度神经网络拥有更少的局部最优点,可见Deep Learning without Poor Local Minima
不计算梯度的优势
除了容易并行化以及对长动作序列和延时奖励有优势,黑盒优化算法与RL相比还有其它优势。ES算法只需要在进程之间传递回报标量和随机种子,因此需要更低的通信预算。由于ES只需要利用整个episode的回报和,而别的方法利用利用的是单个奖励和精确的计时,因此ES更能应对最大化的稀疏和延时奖励。
由于不需要反向传播,黑盒优化减少了每个episode$\frac{2}{3}$的计算量,内存需求也降低了很多。同时,由于不需要计算确切的解析梯度,因此避免了梯度爆炸的问题。在极端情况下,ES允许把非可微元素包含到架构中,例如硬注意力。由于不需要计算梯度,因此黑盒优化方法非常适合深度学习的低精度硬件。
通过扰动参数空间,而不是动作空间,黑盒优化器对智能体在环境中行动的频率具有不变性。
总结
该篇论文的主要贡献是演示了演化策略在较难RL问题上,可展现与RL算法具有同等竞争力的性能,且该方式可扩展到很多并行机器上。
版权: 本篇博文采用《CC BY-NC-ND 4.0》,转载必须注明作者和本文链接