RBO：鲁棒的黑盒优化算法

在利用结构化随机正交矩阵对演化策略的梯度进行高效近似之后，Krzysztof等人提出RBO，该方法利用鲁棒的回归方法学习梯度流方式使黑盒优化算法拥有off-policy更新的能力。

黑盒优化算法

黑盒优化方法的优化形式为
$$
\begin{aligned}
\underset{\theta\in\mathbb{R}^d}{max}F(\theta)
\end{aligned}\tag{1}
$$
式(1)中$\theta$编码一个策略$\pi_{\theta}:\mathcal{S}\to\mathcal{A}$，$F$为$\theta$到累积期望奖励的映射。其中，累积期望奖励为$\pi_{\theta}$与环境交互获得。

其中，黑盒是指不透明的物理仿真器或机器人硬件交互的动力学未知的真实环境。因此，函数$F$只能进行点估计，无法确切的计算梯度。

确切的说，黑盒优化算法，也称为无导数优化，通过各种各样的随机搜索技术最大化$F$，且避免梯度计算。在每个epoch，策略参数向量$\theta$的更新方式为
$$
\begin{aligned}
\theta\leftarrow \theta+\eta\hat{\nabla F}(\theta),~where~\hat{\nabla F}(\theta)\approx\frac{1}{l}\sum_{j=1}^l w(\theta,g_i)g_i
\end{aligned}\tag{2}
$$
函数$F$在$\theta$处的梯度可通过估计在特定扰动方向$g_i$下估计$F$值获得。函数$w:\mathbb{R}\rightarrow\mathbb{R}$把通过扰动策略获得的奖励转化为权重，$\eta$为步长。例如：$w(\theta,g)=\frac{1}{h}[F(\theta+hg)-F(\theta)]$对应着有限差分梯度估计器。

黑盒优化算法的优势与劣势

尽管没有采用RL问题的内部结构，黑盒优化方法仍然与策略梯度方法拥有相当的性能，同时更简单且并行化实施能力强。同时，该类方法也可以处理复杂的、不可微分的策略参数、非马尔可夫的奖励结构和非平滑的混合动力学。

另一方面，黑盒方法需要大量的交互数据。这是因为它们是on-policy方法且只能从样本中抽取相对少量的信息。与之不同，无模型强化学习利用潜在结构推导更新，且off-policy方法可再利用之前收集的数据。同时，许多理论表基于梯度的优化器与基于函数估计的方法之间存在着很大的差距，尤其是存在噪音的场景。它们面对噪音很脆弱，且奖励有噪音可能学习失效。

一种关于梯度估计的正则化回归视角

对于给定黑盒函数$F$，其高斯平滑为
$$
\begin{aligned}
F_{\sigma}(\theta)=\mathbb{E}_{g\in\mathcal{N}(0,I_d)}[F(\theta+\sigma g)](2\pi)^{-\frac{d}{2}}\int_{\mathbb{R}^d}F(\theta+\sigma g)e^{-\frac{\Vert g\Vert^2}{2}}dg
\end{aligned}\tag{3}
$$
演化策略的更新可被写为
$$
\begin{aligned}
\theta\leftarrow \theta+\eta\hat{\nabla}_{MC} F_{\sigma}(\theta)
\end{aligned}\tag{4}
$$
式(4)中$\hat{\nabla}_{MC} F_{\sigma}(\theta)$为梯度MC估计器。

由于梯度$\nabla_{MC}F_{\sigma}(\theta)$是关于高斯分布的期望，即$\nabla F_{\sigma}(\theta)=\frac{1}{\sigma}\mathbb{E}_{g\sim\mathcal{N}(0,I_{d})}[F(\theta+\sigma g_i)g]$，因此MC估计器可通过采样$k$个独立高斯扰动$\sigma g_i$，且在扰动后的点上估计得到。对于MC估计器有许多降低方差的无偏估计器，作者们利用前向有限差表达式
$$
\begin{aligned}
\hat{\nabla}_{MC}^{AT} F_{\sigma}(\theta)=\frac{1}{k\sigma}\sum_{i=1}^k(F(\theta+\sigma g_i)-F(\theta))g_i
\end{aligned}\tag{5}
$$
根据式(5)，可得$\frac{F(\theta + \sigma g_i)-F(\theta)}{\sigma}$可被解释为点积$\nabla F(\theta)^T g_i$，即通过估计在扰动$\sigma g_i$下的$F(\theta+\sigma g_i)$值等价于收集有噪音的估计$\nabla F(\theta)^T g_i$。

这种把黑盒函数梯度估计视为回归问题的视角，有两个优势。第一个是：与MC方法相比，它使黑盒优化方法能够通过正则化回归方法更精确的恢复梯度；第二个是：对于在优化的不同迭代中样本选择，放松了独立条件，从而允许之前迭代的样本被重复利用，从而提高样本效率。同时，作者们表明方差缩减的正交化方法可被解释为基于回归方法的初始化。

基于回归的算法

给定标量$\{F(\theta + \mathbf{z}_i)\}_{i=1}^k$，通过把$\{\mathbf{z}_1,\ldots,\mathbf{z}_k\}$作为输入向量，其目标值为$y_i=F(\theta + \mathbf{z}_i)-F(\theta)$。那么，回归问题为
$$
\begin{aligned}
\hat{\nabla}_{RBO}F(\theta)=\underset{\mathbf{v}\in\mathbb{R}^d}{argmin}\frac{1}{2k}\Vert \mathbf{y}-\mathbf{Z}\mathbf{v}\Vert_p^p+\alpha\Vert\mathbf{v}\Vert_q^q
\end{aligned}\tag{6}
$$
式(6)中$p,q\ge1,\mathbf{Z}\in\mathbb{R}^{k\times d}$的第$i$行为扰动$\mathbf{z}_i$的编码。确切的说，$\mathbf{Z}$的每个行从多变量分布$\mathbb{P}\in\mathcal{P}(\mathbb{R}^d\times\ldots\mathbb{R}^d)$采样，且$\alpha\gt0$为正则化参数。也就是说，$\mathbf{z}_i$不需要从高斯多变量分布中采样，也不需要互相独立。

利用off-policy样本

通过回归问题构建的梯度可用于ES优化器。此外，对于任何给定迭代$t$，ES优化器可以再利用之前点$\theta_{t-1}+\sigma g_i^{(t-1)}$的估计，其与$\theta_t$最接近。因此，回归差值可超越独立样本的框架。由此，形成的算法可见算法1.

注： 算法1笔者也不是完全理解，例如：为什么$\mathbf{u}_{t+1}$不应该就是$\theta_{t+1}$吗？欢迎指点。

通俗的理解，基于回归插值的方式近似梯度，可再利用与$\theta_t$距离最近的之前样本，从而降低了采样量，提高了样本效率。

回归 vs 利用正交MC估计器的ES

简单来说，这一部分主要讲解了利用$k=d$个正交样本再正则化的正交Monte-Carlo估计器与$p=q=2$的RBO估计器的特殊子类一致。

最后，作者们还对算法1进行了提升，不在估计单个$\theta_t$的梯度值，而是估计$\theta_t$邻域的梯度值，详情可见论文。同时，还证明了该算法可鲁棒的恢复梯度。