[TRPO] Trust Region Policy Optim

作者: 超级超级小天才 | 来源:发表于2021-06-07 14:20 被阅读0次

论文链接：http://proceedings.mlr.press/v37/schulman15
引用：Schulman J, Levine S, Abbeel P, et al. Trust region policy optimization[C]//International conference on machine learning. PMLR, 2015: 1889-1897.

概述

Trust Region Policy Optimization (TRPO) 算法是一个 model-free、policy-based、on-policy、Mento Carlo 的算法，且支持连续的状态空间和连续的动作空间，也支持高维输入、神经网络作为函数approximator。

主要的特点

最小化某个替代的损失函数以保证策略能够被单调地改进
在理论上合理地对算法进行一系列近似

主要的近似过程

首先，对于policy gradient或者policy-based的更新算法，最重要的系数之一是步长 ${\alpha}$ ，如果它非常小，则我们无法有效地更新策略；或者如果它非常大，那么学习可能会变得非常不稳定，甚至越来越差。
然后文章介绍了 Kakade & Langford (2002) 的一个公式：

${\eta}(\tilde{\pi})={\eta}({\pi})+E_(s_0,a_0,s_1,a_1…)[\sum_{t=0}^{\infty}{{\gamma}^t A_{\pi} (s_t,a_t)}]={\eta}({\pi})+\sum_s{{\rho}_{\tilde{\pi}}(s) \sum_a{\tilde{\pi} (a│s) A_{\pi}(s,a)}}$

这个式子着我们可以给原始的成本函数（cost function）后添加一个附加项, 如果这个项 $\sum_s{{\rho}_{\tilde{\pi}}(s) \sum_a{\tilde{\pi} (a│s) A_{\pi}(s,a)}}$ 是一个负值，则这一步可以保证降低成本函数 ${\eta}$ 。
然后将等式的右侧定义为 $L_{\pi} (\tilde{\pi})$ , 这就是优化的主要目标。
然后第一个近似值来了：由于新策略下 $\tilde{\pi}$ 的状态分布很难得到，因此将新策略近似地替换为旧策略，即忽略策略变化导致的每个状态访问次数的密度的变化：

$L_{\pi} (\tilde{\pi})={\eta}({\pi})+\sum_s{{\rho}_{\pi} (s) \sum_a{\tilde {\pi} (a│s) A_{\pi} (s,a)}}$

请注意，现在，我们对状态访问分布使用了旧的策略 ${\pi}$ 。
另有一个已经证明的理论说明了：只要如下的这个更新 $L_{{\pi}_{{\theta}_{old}}}$ 的步骤足够小： ${\pi}_{{\theta}_0} \rightarrow {\pi}$ ，那他就也能够提升 ${\eta}$ 本身（具体过程可看原文）
然后基于保守策略迭代（conservative policy iteration）理论：
${\pi}_{new}(a│s)=(1−{\alpha}){\pi}_{old} (a│s)+{\alpha}{\pi}^′(a|s)$

以及 Kakade 和 Langford 已经证明了的如下结果:

${\eta}({\pi}_{new}) \leq L_{{\pi}_{old}} ({\pi}_{new})+\frac{2\epsilon{\gamma}}{(1−{\gamma}(1−{\alpha}))(1−{\gamma})}{\alpha}^2$

引出了第二个近似值：假设这里的步长满足 $\alpha \ll 1$ ，那么就可以将上述不等式近似为：

${\eta}({\pi}_{new} )≤L_({\pi}_{old} ) ({\pi}_{new} )+\frac{2{\epsilon}{\gamma}}{(1−{\gamma})^2} {\alpha}^2$
目前为止，步长 $\alpha$ 是最重要的一个系数，本文也主要是针对此进行的研究，那么第三个近似值来了：用 $\pi$ 和 $\tilde{\pi}$ 之间的距离度量来代替 $\alpha$ ，这里的距离衡量的量被定为总方差散度（total variance divergence：

${\alpha}=D_{TE}^{max}({\pi}_{old},{\pi}_{new})$
${\epsilon}=max_s⁡|E_(a{\backsim}{\pi}^′(a│s) )[A_{\pi} (s,a)]|$
然后第四个近似值来了：根据KL散度和总方差散度之间存在的不等关系，用KL散度替换总方差散度：

${\alpha}=D_{KL}^{max}({\pi}_{old},{\pi}_{new})$
现在问题的主要目标就变为了：

$min_{\theta} [L_{{\theta}_{old}} ({\theta})+CD_{KL}^{max}({\theta}_{old},{\theta})]$
接下来，第五个近似值来了：把上面公式的右边部分改成一个硬值约束：

$min_{\theta} [L_{{\theta}_{old}}({\theta})]$
$s.t. D_{KL}^{max}({\theta}_{old},{\theta})≤{\delta}$
最后，因为 $max$ 算子使优化变得很困难，所以第六个近似值来了：使用平均的KL散度而不是最大值进行计算：

$min_{\theta} [L_{{\theta}_{old}}({\theta})]$
$s.t. \bar{D}_{KL}^{{\rho}_{{\theta}_{old}}} ({\theta}_{old},{\theta}) \leq {\delta}$
现在已经有了理论公式，但在实践中，需要对其进行进一步的近似，因此他们使用了重要性采样。 最后（第七个）的近似值变为：

$min_{\theta}⁡{E_{s{\backsim}{\rho}_{{\theta}_{old}},a{\backsim}q} [\frac{{\pi}_{\theta} (a│s)}{q(a│s)} Q_{{\theta}_{old}}(s,a)]}$
$s.t. E_{s{\backsim}{\rho}_{{\theta}_{old}}}[D_{KL} ({\pi}_{{\theta}_{old}} (\cdot│s)||{\pi}_{\theta} (\cdot|s))]≤{\delta}$

两种算法实现方式

Single Path：从 $s_0$ 的分布中采样若干个 $s_0$ ，然后对每一个 $s_0$ 起始进行simulate，往下进行 $N$ 步，从而可以计算 $Q$ 值
Vine：从 $s_0$ 开始往后进行多个state，然后从这些state开始，每个state根据动作的分布rollout若干个的动作（分支）

具体的例子如下图所示：

single path and vine approach

[TRPO] Trust Region Policy Optim

概述

主要的特点

主要的近似过程

两种算法实现方式

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读