深度强化学习之TRPO

TRPO要解决的问题

在VPG策略迭代方法中，由于策略非凸，在策略迭代过程中会出现震荡、梯度悬崖等情况，难以收敛。TRPO用KL散度对相邻的策略进行约束，防止策略变动过大造成不稳定；并且保证了策略迭代的单调上升。

TRPO的核心思路

TRPO是在Natural Policy Gradient的基础上改进而来，加入参数 $\alpha^j$ 改善了泰勒展开造成的误差，进一步约束了策略的变化范围。总体来看，TRPO的核心思路有以下几点

利用KL-divergence约束策略，使策略迭代不会非常剧烈；
给出了目标函数 $J(\theta)$ 的下界，以便利用Minorize-Maximization(MM)算法进行优化；
利用一阶泰勒展开近似目标函数 $L(\theta)$ (实际是MM算法中的代理函数surrogate function)，用二阶泰勒展开近似KL-divergence约束；
此时实际上问题已转换为凸优化问题，利用拉格朗日对偶性进行求解，得到 $\theta$ 的迭代公式
在 $\theta$ 的迭代公式中，存在矩阵求逆的运算，TRPO利用共轭梯度法求解线性方程 $Hx=\nabla_\theta J(\theta_k)$ ,化解掉逆运算
加入参数 $\alpha^j$ 对泰勒展开的误差可能导致约束失效的问题进行改善

TRPO过程推导

明确目标函数

在基于Policy Optimization的方法中，我们的目的是找到最优策略参数 $\theta^*$ 使得
$\theta^*=\arg\max_\theta E_{\tau\sim p_\theta(\tau)}[\sum_t r(s_t,a_t)]$
记
$J(\theta)=E_{\tau\sim p_\theta(\tau)}[\sum_t r(s_t,a_t)]$
是单个episode过程中得到的rewards累加和的期望(也可以加上衰减系数 $\gamma^t$ )，而在实际采样中，我们采用
$J(\theta)\approx \frac{1}{N} \sum_i \sum_t r(s_{(i,t)},a_{(i,t)})$
在TRPO中，我们要优化的目标函数为
$J(\theta)-J(\theta _k)$
其中， $\theta_k$ 为上一次迭代的参数。CS285-slide9证明了
$J(\theta)-J(\theta_k)=E_{\tau\sim p_{\theta}(\tau)}[\sum_t\gamma^tA^{\pi_{\theta_k}}(s_t, a_t)]$
其中，
$A^{\pi_{\theta_k}}(s_t, a_t)=r(s_t, a_t)+\gamma V^{\pi_{\theta_k}}(s_{t+1})-V^{\pi_{\theta_k}}(s_t)$
需要注意的是，上式中的期望是在 $\pi_{\theta}$ 策略下的，而我们想要的是在前面已知策略 $\pi_{\theta_k}$ 下的采样，对上式展开可得
$E_{\tau\sim p_{\theta}(\tau)}[\sum_t\gamma^tA^{\pi_{\theta_k}}(s_t, a_t)]=\sum_tE_{s_t\sim p_\theta(s_t)}[E_{a_t\sim \pi_{\theta}(a_t|s_t)}[\gamma^tA^{\pi_{\theta_k}}(s_t, a_t)]]$
采用重要性采样，上式可以写成
$E_{\tau\sim p_{\theta}(\tau)}[\sum_t\gamma^tA^{\pi_{\theta_k}}(s_t, a_t)]=\sum_tE_{s_t\sim p_\theta(s_t)}[E_{a_t\sim \pi_{\theta_k}(a_t|s_t)}[\frac{\pi_\theta(s_t, a_t)}{\pi_{\theta_k}(s_t, a_t)}\gamma^tA^{\pi_{\theta_k}}(s_t, a_t)]]$
slide9证明了把上式中的 $p_\theta$ 变成 $p_{\theta_k}$ 后，可以找到原目标函数的下界，通过MM算法可转换为一个由KL-divergence约束的优化问题。记
$\hat A(\theta)=\sum_tE_{s_t\sim p_{\theta_k}(s_t)}[E_{a_t\sim \pi_{\theta_k}(a_t|s_t)}[\frac{\pi_\theta(s_t, a_t)}{\pi_{\theta_k}(s_t, a_t)}\gamma^tA^{\pi_{\theta_k}}(s_t, a_t)]]$
则约束优化问题为
$\theta_{k+1}=\arg\max_{\theta}\hat A(\theta)$
$s.t.D_{KL}(\pi_{\theta}||\pi_{\theta_k)}\leq\epsilon$

利用泰勒展开对上述优化问题进行近似与简化

利用泰勒展开可化简为如下形式
$\theta_{k+1}=\arg\max_\theta \nabla_\theta J(\theta_k)^T(\theta-\theta_k)$
$s.t. \frac{1}{2}(\theta-\theta_k)^TH(\theta-\theta_k)\leq\epsilon$
其中， $H$ 为KL散度的Hessian阵，具体的推导可见slide9

利用拉格朗日对偶性进行求解

写出拉格朗日函数
$L(\theta)=\nabla_\theta J(\theta_k)^T(\theta-\theta_k)-\lambda(\frac{1}{2}(\theta-\theta_k)^TH(\theta-\theta_k))$
利用最优性条件(KKT)，即
$\nabla_\theta L(\theta)=0\\ \nabla_\lambda L(\theta)=0$
可解得
$\theta_{k+1}=\theta_k+\sqrt{\frac{2\epsilon}{\nabla_\theta J(\theta_k)^T H^{-1}\nabla_\theta J(\theta_k)}}H^{-1}\nabla_\theta J(\theta_k)$

利用共轭梯度法避免求逆

在上面的迭代公式中，出现了矩阵求逆的运算，这是我们不希望看到的。TRPO利用共轭梯度法求解线性方程组
$Hx=\nabla_\theta J(\theta_k)$
来简化计算。共轭梯度法只需迭代n次即可完成运算
$x=H^{-1}\nabla_\theta J(\theta_k)$
则迭代公式转化为
$\theta_{k+1}=\theta_k+\sqrt{\frac{2\epsilon}{x^T H x}}x$

加入 $\alpha$ 因子

在泰勒展开近似过程中会存在误差，为确保每次迭代的策略KL散度在约束范围内，TRPO额外加入了 $\alpha$ 因子，最终的迭代公式为
$\theta_{k+1}=\theta_k+\alpha^j \sqrt{\frac{2\epsilon}{x^T H x}}x$
其中 $\alpha \in(0,1)$ ， $j\in \{ 0,1,2,...\}$ 为使得KL散度在约束内且目标函数大于0（目标函数大于0，则本次迭代的策略比上次要好）的最小整数，这就是TRPO的核心迭代公式。

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

深度强化学习之TRPO

TRPO要解决的问题

TRPO的核心思路

TRPO过程推导

推荐阅读更多精彩内容