[TRPO] Trust Region Policy Optimization

论文链接：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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 227,283评论 6赞 530
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 97,947评论 3赞 413
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 175,094评论 0赞 373
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 62,485评论 1赞 308
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 71,268评论 6赞 405
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 54,817评论 1赞 321
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 42,906评论 3赞 440
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 42,039评论 0赞 285
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 48,551评论 1赞 331
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 40,502评论 3赞 354
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 42,662评论 1赞 366
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 38,188评论 5赞 356
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 43,907评论 3赞 345
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 34,304评论 0赞 25
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 35,563评论 1赞 281
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 51,255评论 3赞 389
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 47,637评论 2赞 370

[TRPO] Trust Region Policy Optimization

概述

主要的特点

主要的近似过程

两种算法实现方式

推荐阅读更多精彩内容