增强随机搜索（Augmented Random Search）论文阅读笔记

December 5 2020 300 机器学习(2)

简介

增强随机搜索（Augmented Random Search，ARS）是 2018 年由 California 和 Berkeley 的研究者提出。在深度强化学习（Deep Reinforcement Learning，DRL）领域，可以分为有模型和无模型两个方向，虽然无模型的强化学习有众多缺点，但是也受到了很大的关注。鉴于普通无模型（model-free）强化学习的低效和缺乏鲁棒性等缺点，研究者提出了一种解决持续控制问题的线性策略，这种算法至少比最快的无模型 RL 算法提高 15 倍的效率。

动机

该文章主要是有两个动机：

一：当前的无模型算法过于复杂，为了解决样本效率的问题复杂度不断增加，甚至到了不可复现的程度，本文致力于简化强化学习算法，同时提高样本效率的问题；

二：本文认为当前评估强化学习算法的 baseline 如视频游戏与连续控制问题过于复杂，并且没有一个最优 benchmark，让我们不知道我们的强化学习算法还有多少改进空间。

文章创新之处

针对如何简化强化学习算法，本文抛弃了基于微分的策略梯度方法，而采用无梯度（derivative-free）的策略梯度方法，即有限差分（finite difference，FD）方法，这个方法本质上是利用梯度和方向导数的关系，从多个方向导数的采样去近似梯度，所以没有求微分的过程，传统认为，这种方法的样本复杂度都要大于基于微分的方法，因为你每更新一步，都要去做 $2N$ 次 rollout 试验去得到 $N$ 个方向导数的近似，但是这篇文章的结果颠覆了这个看法。

ARS原理

强化学习问题

强化学习的目标是找到这样一个策略：以最大化代理在给定环境中遵循该策略后可能获得的期望奖励，形式如下：

$$ {\max}_{\theta \in \mathbb{R}^d} \mathbb{E}_{\xi} [r(\pi_{\theta}, \xi)]$$

其中 $\theta \in \mathbb{R}^n$ 是策略 $\pi_{\theta}: \mathbb{R}^n \to \mathbb{R}^p$ 的一个参数，随机变量 $\xi$ 代表了环境的随机性，值 $r(\pi_{\theta}, \xi)$ 为系统在生成的策略 $\pi_{\theta}$ 上获得的奖励，算法通过一系列迭代之后，期望得到最大平均回报 $\mathbb{E}_{\xi}$。

基础随机搜索算法（Basic Random Search，BRS）

BRS算法的思路很简单，对于给定的策略$\pi_{\theta}$，通过应用$+\nu\delta$和$-\nu\delta$来扰动参数$\theta$，其中$\nu<1$为一个实值，$\delta$为一个符合标准正态分布的向量。通过这种轻微扰动我们就可以获取到两个新的策略$\pi_{\theta+\nu\delta}$和$\pi_{\theta-\nu\delta}$以及行动应用策略后所得到的回报。接下来我们可以计算平均收益

$$ \Delta = \frac{1}{N} \sum_{k=1}^N [r(\pi_j, k, +) - r(\pi_j, k, -)]\delta_k$$

然后使用平均收益和学习率乘积，我们可以用以下公式来更新下一个参数$\theta_{j+1}$

$$ \theta_{j+1} = \theta_j + \alpha\Delta$$

算法流程如下： BRS算法流程

增强随机搜索算法（Augmented Random Search，ARS）

ARS算法是BRS算法的一个改进版本，主要是有以下三点改进。

使用标准差进行归一化

当迭代进行到后面时，扰动策略的回报值$r(\pi_j, k, +)$和$r(\pi_j, k, -)$之间的差距会越来越大。因为学习率$\alpha$是固定的，更新后的策略可能会产生比较大幅度的震荡。如当$\alpha=0.01$时，平均回报$\Delta=10$时更新幅度是$0.1$，而当平均回报$\Delta=1000$时更新幅度为$10$。这种大幅度的变化会打乱更新过程，记住我们的目标是要$\theta$朝着最大化回报方向收敛。

为了解决这种震荡，在收集完$2N$次回报之后计算其标准差$\sigma_{R}$，并将更新幅度$\alpha\Delta$除以该标准差。

这种改进作者称其为V1版本。

状态标准化

状态的标准化能够确保策略在对待状态的不同分量时一视同仁。例如假设一个状态的分量的值域区间为$[90, 100]$，另一个分量的值域区间为$[-1, 1]$，这样导致计算过程中，第一个状态分量将起主导决定，而第二个状态分量几乎没作用。

拿求平均值举例来说，假设$C_1 = 91, C_2=1$，则平均值$\frac{C_1 + C_2}{2} = 46$，现假设$C_2$快速下降到最小值，即$C_2 = -1$，则平均值为$45$。可以看到目标值对于$C_2$分量的急剧变化表现平缓，几乎没有影响。

现在使用标准化后，$N_{C_1} = \frac{91 - 90}{100 - 90} =0.1, N_{C_2} = \frac{1 - (-1)}{1 - (-1)} = 1$，重新计算后的平均值为$\frac{N_{C_1} + N_{C_2}}{2} = \frac{0.1 + 1}{2} = 0.55$。考虑$C_2$减小到$-1$，则标准化后的$C_2$为$N_{C_2} = \frac{-1 - (-1)}{1 - (-1)} = 0$，平均值为$\frac{N_{C_1} + N_{C_2}}{2} = \frac{0.1 + 0}{2} = 0.05$。至此可以看到标准化后的状态分量对目标值的影响程度是一致的。

对于ARS算法来说，状态的标准化可以看作是线性策略参数空间中非各向同性探索的一种形式。在计算时，策略权重$M$和扰动方向$\delta$，我们有

$$ (M+\nu \delta) \operatorname{diag}(\Sigma)^{-1 / 2}(x-\mu)=\left(\tilde{M}+\nu \delta \operatorname{diag}(\Sigma)^{-1 / 2}\right)(x-\mu) $$

其中$\tilde{M} = M\operatorname{diag}(\Sigma)^{-\frac{1}{2}}$。

这种改进作者称其为V2版本。

只取表现好的结果

在迭代时，我们都会进行$2N$次rollout实验并用于更新下一次参数$\theta_{j + 1}$，这样也会有一些问题，如拉低平均收益的方向，我们可以放弃它们，即保留$b<N$个最好的收益用于计算平均收益。

这也是版本V1-t和V2-t的来由。

最后看一下ARS算法的流程： ARS算法流程

实验结果

文章使用MuJoCo locomotion任务做实验（这个任务主要包括了hopper, ant, half_cheetah, walker2d, pusher, reacher, striker, swimmer, humanoid的实验，不同版本的gym里面的任务也不同，文章用的版本是都是V1的)，主要做了三组实验。

第一组

ARS各种变种与NG，TRPO对比，在每个任务上达到指定threshold所需要的平均episode个数

在三个随机种子上自己的几个算法变种和各种算法之间各种对比，包括TRPO, DDPG, NG, ES, PPO, SAC, SQL, A2C, CEM。这些方法的结果作者没有亲自做实验，直接拿别人论文里的结果做实验的（所以有可能不太公平，因为有些作者基于5个种子或6个种子做平均的），主要致力于对比样本效率。可以看出ARS V1就挺强的，除了Humanoid都能训出来，V2在样本效率上有很大提升，但在复杂任务上还是不敌gradient-based方法，V2-t又将样本效率进一步提高，样本效率全面超过其他算法。

和自己的对比