【论文解读】解读TRPO论文,深度强化学习结合传统优化方法
共 5245字,需浏览 11分钟
· 2021-01-05
![](https://filescdn.proginn.com/9faee294ffd480d767273636a0e9422c/06722d0adce88dcbfea7b5368325be35.webp)
导读:本论文由Berkeley 的几位大神于2015年发表于 JMLR(Journal of Machine Learning Research)。深度强化学习算法例如DQN或者PG(Policy Gradient)都无法避免训练不稳定的问题:在训练过程中效果容易退化并且很难恢复。针对这个通病,TRPO采用了传统优化算法中的trust region方法,以保证每一步迭代能够获得效果提升,直至收敛到局部最优点。
本篇论文涉及到的知识点比较多,不仅建立在强化学习领域经典论文的结论:Kakade & Langford 于2002 年发表的 Approximately Optimal Approximate Reinforcement Learning 关于优化目标的近似目标和重要性采样,也涉及到传统优化方法 trust region 的建模和其具体的矩阵近似数值算法。读懂本论文,对于深度强化学习及其优化方法可以有比较深入的理解。本论文附录的证明部分由于更为深奥和冗长,在本文中不做具体讲解,但是也建议大家能够仔细研读。
阅读本论文需要注意的是,这里解读的版本是arxiv的版本,这个版本带有附录,不同于 JMLR的版本的是,arxiv版本中用reward函数而后者用cost函数,优化方向相反。
arxiv 下载链接为 https://arxiv.org/pdf/1502.05477.pdf
0. 论文框架
本论文解决的目标是希望每次迭代参数能保证提升效果,具体想法是利用优化领域的 trust region方法(中文可以翻译成置信域方法或信赖域方法),通过参数在trust region范围中去找到一定能提升的下一次迭代。
本论文框架如下
首先,引入Kakade & Langford 论文 Approximately Optimal Approximate Reinforcement Learning 中关于近似优化目标的结论。(论文第二部分)
基于 Kakade 论文中使用mixture policy保证每一步效果提升的方法,扩展到一般随机策略,引入策略分布的total variation divergence作为约束。(论文第三部分)
将total variation divergence约束替换成平均 KL divergence 约束,便于使用蒙特卡洛方法通过采样来生成每一步的具体优化问题。(论文第四,五部分)
给出解决优化问题的具体算法,将优化目标用first order来近似,约束项用second order 来近似,由于second order涉及到构造Hessian matrix,计算量巨大,论文给出了 conjugate gradient + Fisher information matrix的近似快速实现方案。(论文第六部分)
从理论角度指出,Kakade 在2002年提出的方法natrual policy gradient 和经典的policy gradient 都是TRPO的特别形式。(论文第七部分)
评价TRPO在两种强化学习模式下的最终效果,一种是MuJoCo模拟器中能得到真实状态的模式,一种是Atari游戏环境,即观察到的屏幕像素可以信息完全地表达潜在真实状态的模式。(论文第八部分)
本文下面的小结序号和论文小结序号相同,便于对照查阅。
1. 介绍
TRPO 第一次证明了最小化某种 surrogate 目标函数且采用non-trivial的步长,一定可以保证策略提升。进一步将此 surrogate 目标函数转换成trust region约束下的优化问题。TRPO是一种on-policy 的算法,因为每一步迭代,需要在新的策略下通过采样数据来构建具体优化问题。
2. 已有理论基础
第二部分主要回顾了 Kakade & Langford 于2002 年的论文 Approximately Optimal Approximate Reinforcement Learning 中的一系列结论。
先来定义几个重要概念的数学定义
是策略 的目标,即discounted reward 和的期望。
![](https://filescdn.proginn.com/bc87d5f9bdc9775c93b1ca55de9f7333/9b12f3076858995543fe124c3a8fbadc.webp)
然后是策略的Q值和V值
![](https://filescdn.proginn.com/3522e47560b409e7cec358d2ce8ff9d6/ce28bf6f38462ee6215f756f95ba5ec9.webp)
最后是策略的advantage函数
![](https://filescdn.proginn.com/68bb0d4fa5458fb05ef18e92ea14fc13/b0304bb7085f880cceaf3eadc15217f2.webp)
接着,开始引入 Kakade & Langford 论文结论,即下式(公式1)。
![](https://filescdn.proginn.com/c7bddd38660938680042637cecb8bab9/7722472d42999a8a3eded2db6eba7c4c.webp)
公式1表明,下一次迭代策略的目标可以分解成现有策略的目标 和现有advantage 函数在新策略trajectory分布下的期望。
公式1可以很容易从trajectory分布转换成新策略在状态的访问频率,即公式2
![](https://filescdn.proginn.com/66739eaa9159d08f77c436b46fbed57b/fa17d296f2e65e165735cf6121790f99.webp)
状态的访问频率或稳定状态分布定义成
![](https://filescdn.proginn.com/601e9173e935b1620272c78e1753a18b/41261dcd0286766cbb073467a9676442.webp)
注意到公式2中状态的期望依然依赖于新策略 的稳定状态分布,不方便实现。原因如下,期望形式有利于采样来解决问题,但是由于采样数据源于 on-policy 而非 ,因此无法直接采样未知的策略 。
幸好,Kakade 论文中证明了,可以用 的代替 并且证明了这种代替下的近似目标函数 是原来函数的一阶近似
即满足
![](https://filescdn.proginn.com/40d78cae25d623847f32d01e4c915943/0a8b3bb1e7e964f17ac472b205c053c7.webp)
具体定义表达式为
![](https://filescdn.proginn.com/ae7c8ef084f74848ff6aee6678aa306f/d393b85a0e5c7fccdc7afe035235c8d2.webp)
是一阶近似意味着在小范围区域中一定是可以得到提升的,但是范围是多大,是否能保证 的提升?Kakade的论文中不仅给出了通过mix新老策略的提升方式,还给出了这个方式对原目标 较 的提升下届。
策略更新规则如下
![](https://filescdn.proginn.com/83144bc5945d4af8d9eac7ebd3840dbd/f3d60644d0e4e5a0e614a0c1cc0851f6.webp)
公式6为具体提升下届为
![](https://filescdn.proginn.com/40d26721469124c8d85b7a7433f5489c/aab117de9ae12b61f5465465e9f371b7.webp)
3. 扩展到随机策略
论文的这一部分将Kakade的mix policy update 扩展到一般的随机策略,同时依然保证每次迭代能得到目标提升。
首先,每次策略迭代必须不能和现有策略变化太大,因此,引入分布间常见的TV divergence,即 total variation divergence。
![](https://filescdn.proginn.com/b7b57dedb8f6464d35588fafaff0b6a9/ad09ea8d3a05287da269cb42a6470807.webp)
有了两个分布距离的定义,就可以定义两个策略的距离。离散状态下,一个策略是状态到动作分布的 map 或者 dict,因此,可以定义两个策略的距离为所有状态中最大的动作分布的 ,即
![](https://filescdn.proginn.com/b037246cd5c12e6ed877f05b573921dc/1ba1350085287f74064f8ef9437fa5d3.webp)
至此,可以引出定理一:在一般随机策略下,Kakade 的surrogate函数较原目标的提升下届依然成立,即公式8在新的定义下可以从公示6推导而来。
![](https://filescdn.proginn.com/0be149c6515712cc3b9e9ebee873eb79/d5e7e52f97679122b99ca846da9d0d9d.webp)
进一步将 TV divergence 转换成 KL divergence,转换成KL divergence 的目的是为了后续使用传统且成熟的 trust region 蒙特卡洛方法和 conjugate gradient 的优化近似解法。
![](https://filescdn.proginn.com/210e637e87d9c9d31c5f2b0105001d7e/4ba72765336978d751e2dedf34a7d942.webp)
由于上面两种距离的大小关系,可以推导出用KL divergence表示的 较 的提升下届
![](https://filescdn.proginn.com/6f9969956c0ffa44438be2bfe6588cbd/e169dce5d59318dfee1ffdc9e7764cc3.webp)
根据公式9,就可以形成初步的概念上的算法一,通过每一步形成无约束优化问题,同时保证每次迭代的 对应的 是递增的。
![](https://filescdn.proginn.com/93cf74886d0266a0a5bb8a2b49885a5a/69be79593e66212cd484fd388cdccc69.webp)
4. Trust Region Policy Optimization
看到这里已经不容易了,尽管算法一给出了一个解决方案,但是本论文的主角TRPO 还未登场。TRPO算法的作用依然是近似!
算法一对于下面的目标函数做优化,即每次找到下一个 最大化下式, 每一步一定能得到提升。
问题是在实践中,惩罚系数 会导致步长非常小,一种稳定的使用较大步长的方法是将惩罚项变成约束项,即:
![](https://filescdn.proginn.com/ca1b445dc694842edceed554e6accd9e/cae58e76f4407bcaea4fc9032e9562e5.webp)
将 放入约束项中符合trust region 这种传统优化解法。
关于 约束,再补充两点
的定义是两个策略中所有状态中最大的动作分布的 ,因此它约束了所有状态下新老策略动作分布的KL散度,也就意味着有和状态数目相同数量的约束项,海量的约束项导致算法很难应用到实际中。
约束项的 trust region 不是参数 的空间,而是其KL散度的空间。
基于第一点,再次使用近似法,在约束项中用KL期望 来代替各个状态下的KL散度,权重为on-policy 策略的分布
![](https://filescdn.proginn.com/dbfab73b3f2d0e94cca1b3253b8e71e1/1d72442ede9c0621d3aabb2cd110cb7f.webp)
最终,得到TRPO在实际中的优化目标(12式):
![](https://filescdn.proginn.com/640970aed28ae452940ae67cb0722f0d/63049fecee4163c1bc0c6aed2da3d330.webp)
5. 用采样方法来Trust Region约束优化
论文第五部分,将TRPO优化目标12式改写成期望形式,引入两种蒙特卡洛方法 single path 和 vine 来采样。
具体来说, 由两项组成
第一项是常量,只需优化第二项,即优化问题等价为13式
![](https://filescdn.proginn.com/6bf9971036408e17026a5290e58b4b37/4d9c6753fcca4b9b93ed1d6e125c2ef9.webp)
随后,为了可以适用非 on-policy 的动作分布来任意采样,引入采样的动作分布 ,将13式中的 部分通过重要性采样改成以下形式:
![](https://filescdn.proginn.com/150dec7eac3f7b084892b5c13934809c/3214619825c5f5ced6ff1e07b83f1f81.webp)
再将13式中的 改成期望形式 ,并将 改成 值,得14式。
![](https://filescdn.proginn.com/218a39e91cc4dbf3c084a6119e4a3f04/a56d3834b893db98fdb03d8d25051c49.webp)
至此,我们得到trust region优化的期望形式:优化目标中期望的状态空间是基于 on-policy ,动作空间是基于任意采样分布 ,优化约束中的期望是基于 on-policy 。
5.1 Single path采样
根据14式,single path 是最基本的的蒙特卡洛采样方法,和REINFORCE算法一样, 通过on-policy 生成采样的 trajectory数据:,然后代入14式。注意,此时 ,即用现有策略的动作分布直接代替采样分布。
![](https://filescdn.proginn.com/c5aa7e54429efb39c5c5a6b323c9fd66/af423171d8b783e40871ee87f8db36f0.webp)
5.2 Vine 采样
虽然single path方法简单明了,但是有着online monte carlo方法固有的缺陷,即variance较大。Vine方法通过在一个状态多次采样来改善此缺陷。Vine的翻译是藤,寓意从一个状态多次出发来采样,如下图, 状态下采样多个rollouts,很像植物的藤长出多分叉。当然,vine方法要求环境能restart 到某一状态,比如游戏环境通过save load返回先前的状态。
![](https://filescdn.proginn.com/3d199661cb41bc41a7a4b380b521e4e7/ef67a220484eaf1dbcd7e29c2f6165ae.webp)
具体来说,vine 方法首先通过生成多个on-policy 的trajectories来确定一个状态集合 。对于状态集合的每一个状态 采样K个动作,服从 。接着,对于每一个 再去生成一次 rollout 来估计 。试验证明,在连续动作空间问题中, 直接使用 on-policy 可以取得不错效果,在离散空间问题中,使用uniform分布效果更好。
6. 转换成具体优化问题
再回顾一下现在的进度,12式定义了优化目标,约束项是KL divergence空间的trust region 形式。14式改写成了等价的期望形式,通过两种蒙特卡洛方法生成 state-action 数据集,可以代入14式得到每一步的具体数值的优化问题。论文这一部分简单叙述了如何高效但近似的解此类问题,详细的一些步骤在附录中阐述。我们把相关解读都放在下一节。
7. 和已有理论的联系
7.1 简化成 Natural Policy Gradient
再回到12式,即约束项是KL divergence空间的trust region 形式
![](https://filescdn.proginn.com/640970aed28ae452940ae67cb0722f0d/63049fecee4163c1bc0c6aed2da3d330.webp)
对于这种形式的优化问题,一般的做法是通过对优化目标做一阶函数近似,即
并对约束函数做二阶函数近似,因为约束函数在 点取到极值,因此一阶导为0。
12式的优化目标可以转换成17式
![](https://filescdn.proginn.com/c11fef40084f8a1f268fa2c59366ac16/e7022eece7169904185c79e265d0c1b7.webp)
对应参数迭代更新公式如下
![](https://filescdn.proginn.com/55f121848496ba231a6265fe9e92fe26/0fc3f193b6194d1510db2259576ceeb0.webp)
这个方法便是Kakade在2002年发表的 natrual policy gradient 论文。
7.2 简化成 Policy Gradient
注意,的一阶近似的梯度
即PG定理
因此,PG定理等价于的一阶近似的梯度在 空间 约束下的优化问题,即18式
![](https://filescdn.proginn.com/b356f8445099a60b3b78a05603eea4f2/5f5dc56b8b8cd9c1116e21b62ae035fe.webp)
7.3 近似数值解法
这里简单描述关于17式及其参数更新规则中的大矩阵数值计算近似方式。
二阶近似中的 是 Hessian 方形矩阵,维度为 个数的平方。
![](https://filescdn.proginn.com/0575d9d118c8358f03f3b047dcf593cb/2452cc45a8e78982b9e7b8197a4aafb7.webp)
直接构建 矩阵或者其逆矩阵 都是计算量巨大的, 注出现在natural policy update 更新公式中, 。
一种方法是通过构建Fisher Information Matrix,引入期望形式便于采样
另一种方式是使用conjugate gradient 方法,通过矩阵乘以向量快速计算法迭代逼近 。
8. 试验结果
在两种强化学习模式下,比较TRPO和其他模型的效果。模式一是在MuJoCo模拟器中,这种环境下能得到真实状态的情况。
![](https://filescdn.proginn.com/770232aba7150928bc691000f56d8489/649f5ab5ed96d191e131d4df55c845f7.webp)
另一种模式是完全信息下的Atari游戏环境,这种环境下观察到的屏幕像素可以信息完全地表达潜在真实状态。
![](https://filescdn.proginn.com/2e61c3dfbca927ea079bb1618a948e19/19bb366e73e9c8e72493c654479e8c0f.webp)
往期精彩回顾
获取本站知识星球优惠券,复制链接直接打开:
https://t.zsxq.com/qFiUFMV
本站qq群704220115。
加入微信群请扫码: