关于CEM算法

基本概念

  • CEM (cross entropy method) 算法是一种无梯度的优化算法。对于一般的优化问题,我们可以认为问题给定了优化的目标$S(M)$,其中$M$是我们想要优化的参数,即整个优化过程就是为了求解:对于许多优化问题,尤其是凸优化问题,我们能够用梯度优化算法求解得到$M^*$。而CEM算法不同于梯度算法,他不借助问题的结构(这里指目标函数$S(·)$的表达式),而是将把目标函数$S(·)$作为黑盒求解。

求解过程

  • CEM的整个求解过程实际上是在维护参数$M$的一个分布$f$,算法起初初始化一个分布$f0$,之后迭代得到最终分布$f{T}$。从$f_0$到$f_T$的区别在于初始化的$f_0$可能是很差的(从$f_0$分布很难采样得到最优参数$M^$),而从$f_0$到$f_T$的迭代过程可以理解为让分布越来越好(使得从分布中采样得到$M^$的概率逐渐增大,或者说采到好样本的概率逐渐增大)。

  • 另外还有一个细节是,不管是初始化$f0$,还是从$f_t$到$f{t+1}$的迭代,我们实际上都得先假设一个分布类$\mathcal{F}$。这是什么意思?事实上,对分布进行调整往往都是对分布的参数进行调整(例如调整高斯分布的均值和方差),而对分布进行初始化,我们也得先确定分布类,然后初始化分布参数。在实际应用CEM算法的过程中,我们常常一般高斯分布。

  • 具体的算法过程如下(以高斯分布作为$\mathcal{F}$为例):

    • 初始化采样数$n$和筛选因子$\rho$(含义后续介绍),确定初始分布$f_0$的参数。

    • 在第$t$轮时,依据分布$f_{t-1}$采样得到$n$个样本${M_1, M_2, …, M_n}$,计算相应的目标函数值$S(M_i), 1\leq i\leq n$,选取其中最大的前$\lfloor \rho n\rfloor$个样本,得到样本索引$I \subseteq {1, 2, …, n}$。进行如下更新:

    • 注意:在更新公式中,$(M_i - \mu_t)$项增加了转置,因为参数$M_i$大概率是个向量。

CEM算法和强化学习

  • CEM是一种无梯度优化算法,它并不局限于具体的任务或场景。对于强化学习而言,若对policy进行参数化表示,那么配合某种policy evaluation算法即利用CEM对policy的参数进行优化。
  • 实践中证明,在强化学习任务中直接使用CEM算法很容易收敛到局部最优,因此一般使用noisy cross entropy method,它和CEM算法的区别在于:NCEM在对分布参数进行迭代更新时额外加上一个噪声,以此避免过早地陷入局部最优。

AK