TRPO是OpenAI提出的一种策略单调提升的算法,关于其论文以及解读见我的另一篇论文笔记之TRPO这篇文论文解读将TRPO的重点以及细节都指明了,但是关于目标函数的优化部分由于篇幅原因只是简单说明了以下,具体细节将放在这里进行说明。
参考目录:
①优化理论相关书籍
②TRPO论文
③TRPO论文推导
④TRPO的补充
⑤TRPO讲解
⑥TRPO与NPG的联系或英文原版
TRPO论文优化部分理解
看过TRPO论文的都知道作者采用共轭梯度+线性搜索来迭代求出关于目标函数的最优解θ∗\theta^*θ∗。
因此接下来我将详细分析作者是如何利用CG和一维搜索来应用于RL算法的。
Note:
关于共轭梯度下降和线性搜索的基础知识就不讲解了,这部分内容不清楚的最好去参考优化理论的书籍,做个详细的了解。
首先给出整个优化过程的伪代码,有2个版本,一个是简化版,一个是基于共轭梯度下降的版本:
简化版:基于CG版:
为了便于分析,接下来基于CG版本进行讲解。2个红框中标出的是TRPO论文算法比标准CG算法多出来的地方,分别是对学习率αk\alpha_kαk进行修正且进行一维搜索得到最佳学习率;另一部分是利用Hessian-Free技术去避免求解Hessian矩阵的问题。
面对以上伪代码,应该有四个问题,接下来将一一解答:
Q1Q1Q1:如何将RL目标函数转成共轭梯度算法需要的二次型问题。Q2Q2Q2:为何要修正α\alphaα?如何去修正呢?Q3Q3Q3:如何进行线性搜索呢?Q4Q4Q4:如何使用Hessian-Free技术。
TRPO优化需要解决的四个问题
二次型转换泰勒展开无约束的转换学习率修正线性搜索Hessian-Free总结首先给出我们要优化的目标,也就是TRPO论文中的公式(14):
maximizeθEs∼ρθold,a∼q[πθ(a∣s)q(a∣s)Qθold(s,a)]s.t.Es∼ρθold[DKL(πθold(⋅∣s)∣∣πθ(⋅∣s))]≤δ.\mathop{maximize}\limits_\theta\mathbb{E}_{s\sim\rho_{\theta_{old}},a\sim q}[\frac{\pi_\theta(a|s)}{q(a|s)}Q_{\theta_{old}}(s,a)]\\ s.t.\,\,\,\mathbb{E}_{s\sim\rho_{\theta_{old}}}[D_{KL}(\pi_{\theta_{old}}(\cdot|s)||\pi_\theta(\cdot|s))]\leq\delta. θmaximizeEs∼ρθold,a∼q[q(a∣s)πθ(a∣s)Qθold(s,a)]s.t.Es∼ρθold[DKL(πθold(⋅∣s)∣∣πθ(⋅∣s))]≤δ.我们将其简化成:
maximizeθf(θ)s.t.−kl(θ)≥−δ.\mathop{maximize}\limits_\theta f(\theta)\\ s.t.\,\,\,-kl(\theta)\ge-\delta. θmaximizef(θ)s.t.−kl(θ)≥−δ.
二次型转换
Q1Q1Q1:如何将RL目标函数转成共轭梯度算法需要的二次型问题?
共轭梯度下降算法的目标函数是二次型函数,但对于一般非线性函数,我们是通过泰勒定理将其转为近似二次型。在这里我将分两步走来解决这个问题。
泰勒展开
首先我们要做的就是在θold\theta_{old}θold处对f(θ)、kl(θ)f(\theta)、kl(\theta)f(θ)、kl(θ)做泰勒展开。
对于目标函数,省去二阶项以及后面的高阶项:
f(θ)≈f(θold)+gT⋅(θ−θold)f(\theta)\approx f(\theta_{old})+g^T\cdot(\theta-\theta_{old}) f(θ)≈f(θold)+gT⋅(θ−θold)对于约束条件,同样省去常数项、一阶项以及后面的高阶项:
kl(θ)≈12(θ−θold)TF(θold)(θ−θold)kl(\theta)\approx\frac{1}{2}(\theta-\theta_{old})^TF(\theta_{old})(\theta-\theta_{old}) kl(θ)≈21(θ−θold)TF(θold)(θ−θold)Note:
g=(∂f∂θ)T∣θ=θoldg=(\frac{\partial{f}}{\partial{\theta}})^T|_{\theta=\theta_{old}}g=(∂θ∂f)T∣θ=θold。目标函数第一项为常数项,我们将其忽略,故f(θ)≈gT⋅(θ−θold)f(\theta)\approx g^T\cdot(\theta-\theta_{old})f(θ)≈gT⋅(θ−θold)。约束条件第一项为0,第二项通过展开进行一定数学推算也可以化为0(具体可见这里)。FFF为Hessian矩阵
(在这里也可以叫费雪信息矩阵FIM),展开为∂2kl(θ)∂θ2∣θ=θold\frac{\partial^2{kl(\theta)}}{\partial{\theta^2}}|_{\theta=\theta_{old}}∂θ2∂2kl(θ)∣θ=θold。黑塞矩阵在二次项函数中是常数矩阵,但是在非线性函数中对于每一次迭代都需要计算一次,计算量和存储量都很大,因此后续我们才要去消除它的计算。可以看到再TRPO里面,我们将目标函数做了一阶近似,对约束条件做了二阶近似。
因此我们的优化目标就变成了:
maximizeθgT⋅(θ−θold)s.t.12(θ−θold)TF(θold)(θ−θold)≤δ\mathop{maximize}\limits_\theta g^T\cdot(\theta-\theta_{old})\\ s.t.\,\,\,\frac{1}{2}(\theta-\theta_{old})^TF(\theta_{old})(\theta-\theta_{old})\le\delta θmaximizegT⋅(θ−θold)s.t.21(θ−θold)TF(θold)(θ−θold)≤δ
无约束的转换
共轭梯度算法是一种无约束优化算法,因此有必要将上述约束型转为无约束,这里我们使用拉格朗日乘子法
。
添加拉格朗日乘子λ\lambdaλ,则上式转为:
maximizeL(θ,λ)=gT(θ−θold)−λ2[(θ−θold)TF(θ−θold)−δ]KKT条件:{12(θ−θold)TF(θold)(θ−θold)≤δλ≥0λ(12(θ−θold)TF(θold)(θ−θold)−δ)=0maximize\,\,L(\theta,\lambda)=g^T(\theta-\theta_{old})-\frac{\lambda}{2}[(\theta-\theta_{old})^TF(\theta-\theta_{old})-\delta]\\ KKT条件:\begin{cases} \frac{1}{2}(\theta-\theta_{old})^TF(\theta_{old})(\theta-\theta_{old})\le\delta\\ \lambda\ge0\\ \lambda(\frac{1}{2}(\theta-\theta_{old})^TF(\theta_{old})(\theta-\theta_{old})-\delta)=0 \end{cases} maximizeL(θ,λ)=gT(θ−θold)−2λ[(θ−θold)TF(θ−θold)−δ]KKT条件:⎩⎪⎨⎪⎧21(θ−θold)TF(θold)(θ−θold)≤δλ≥0λ(21(θ−θold)TF(θold)(θ−θold)−δ)=0这样一来约束问题就转为了无约束问题。但在正式运用之前,还需要将目标函数变个型,令s=θ−θolds=\theta-\theta_{old}s=θ−θold,则
maximizeL(θ,λ)=−λ2sTFs+gTs+λ2δmaximize\,\,L(\theta,\lambda)=-\frac{\lambda}{2}s^TFs+g^Ts+\frac{\lambda}{2}\delta maximizeL(θ,λ)=−2λsTFs+gTs+2λδ这就是转化之后的二次型了!
Note:
这个sss就是学习率和搜索方向的乘积s=α⋅ds=\alpha\cdot ds=α⋅d,其中α\alphaα为学习率,ddd为共轭方向,也是共轭梯度算法中的搜索方向。TRPO做的这个近似通过拉格朗日乘子法转成的拉格朗日函数LLL还提供了一个重要信息:由于仍是对函数做优化,所以其一阶导数应该为0,故有∂L∂s=0\frac{\partial{L}}{\partial{s}}=0∂s∂L=0,展开之后就是:s=1λF−1gs=\frac{1}{\lambda}F^{-1}gs=λ1F−1g。这个式子的意义在于,TRPO可以通过共轭梯度法,不断迭代求得的sss来代替Natural Policy Gradient中计算费雪信息矩阵FFF的逆矩阵的步骤,因为FIM的计算成本是非常高的,这也是TRPO在NPG上的一个改进(这也就是为什么上述第一个简化版本伪代码中出现了F−1gF^{-1}gF−1g)。换句话说,我们可以利用CG算法来近似F−1gF^{-1}gF−1g,从而减少NPG算法的复杂度。
学习率修正
Q2Q2Q2:为何要修正α\alphaα?如何去修正呢?
为何要修正α\alphaα呢,因为我们在转无约束的时候,多了一个KKTKKTKKT条件:λ(12(θ−θold)TF(θold)(θ−θold)−δ)=0\lambda(\frac{1}{2}(\theta-\theta_{old})^TF(\theta_{old})(\theta-\theta_{old})-\delta)=0λ(21(θ−θold)TF(θold)(θ−θold)−δ)=0,我们接下来对这个式子进行处理:
因为根据共轭梯度算法的流程,有θ=θold+α⋅d(k),α∈R\theta=\theta_{old}+\alpha\cdot d^{(k)},\alpha\in\mathbb{R}θ=θold+α⋅d(k),α∈R,所以
12(θ−θold)TF(θold)(θ−θold)−δ=12(αd)TF(αd)−δ=12α2(dTFd)−δ\frac{1}{2}(\theta-\theta_{old})^TF(\theta_{old})(\theta-\theta_{old})-\delta\\ =\frac{1}{2}(\alpha d)^TF(\alpha d)-\delta\\ =\frac{1}{2}\alpha^2(d^TFd)-\delta 21(θ−θold)TF(θold)(θ−θold)−δ=21(αd)TF(αd)−δ=21α2(dTFd)−δ又因为理论上最好的优化区域并不是在置信区域内,而是在置信边界上,在TRPO论文的补充材料中,作者也指出了这一点:
。即λ>0\lambda>0λ>0,这样一来12(θ−θold)TF(θold)(θ−θold)−δ≡0\frac{1}{2}(\theta-\theta_{old})^TF(\theta_{old})(\theta-\theta_{old})-\delta\equiv021(θ−θold)TF(θold)(θ−θold)−δ≡0,故可以得出以下结论:
α=2δdTFd\alpha=\sqrt{\frac{2\delta}{d^TFd}} α=dTFd2δ这样一来就解决了如何去修正α\alphaα对的问题,也就是说当我们在TRPO算法中使用共轭梯度下降的时候,就不能用标准的α\alphaα公式了,而是要用上式这个经过KKTKKTKKT修正过的。
线性搜索
Q3Q3Q3:如何进行线性搜索呢?
根据标准的共轭梯度算法,其会在nnn步迭代就收敛,其α\alphaα其实就是用一维搜索方法进行优化的。但是Q2Q2Q2中已经将算法进行了改变,故收敛性无法得到保证,那么如何挽回呢?也就是说现在的问题就是如何获得一个更好的学习率α∗\alpha^*α∗,使得这一步的α\alphaα是一个不错的学习率,这又是一个优化问题:输入是学习率α∈R\alpha\in\mathbb{R}α∈R,输出目标函数L∈RL\in\mathbb{R}L∈R,R→R\mathbb{R}\to\mathbb{R}R→R的问题我们采用线性搜索(即一维搜索)
来做,比如常见的黄金分割、斐波那契、二分法、牛顿法、割线法等等。作者在这里简单的采用了指数式下降来搜寻最佳的学习率α\alphaα,类似于Armijo划界法
,也就是说从一开始最大的学习率α(0)\alpha^{(0)}α(0)开始,接下来每一个学习率都在上一个备选值的基础上乘以缩减因子τ=0.5\tau=0.5τ=0.5,这样就构成ak=τma(0)a_k=\tau^ma^{(0)}ak=τma(0),相当于构成了一个序列,我们要在这个序列中找出使得目标函数提升的最大学习率a∗a^*a∗。
Hessian-Free
Q4Q4Q4:如何使用Hessian-Free技术。
我们在伪代码中看出我们需要计算一个Hessian矩阵,黑塞矩阵在二次项函数中是常数矩阵,但是在非线性函数中对于每一次迭代都需要计算一次,计算量和存储量都很大,因此我们必须要消除它。理论上的消除办法有3种,这里我介绍一种,即论文中作者采用的Hestenes-Stiefel公式,它用来消除FFF的原理是什么呢?
我们发现共轭梯度的算法流程中,Hessian矩阵总以matrix-vector products
的形式出现。因此我们可以直接带走他们。
具体来说:
对于二次型:f=12θTFθ−bTθf=\frac{1}{2}\theta^TF\theta-b^T\thetaf=21θTFθ−bTθ来说:
已知θk+1=θk+αkdk\theta^{k+1}=\theta^{k}+\alpha_kd^{k}θk+1=θk+αkdk,等式两侧同时左乘Hessian矩阵FFF并减去常数向量bbb:F⋅θk+1−b=F⋅θk+αkFdk−bF\cdot\theta^{k+1}-b=F\cdot\theta^{k}+\alpha_kFd^{k}-bF⋅θk+1−b=F⋅θk+αkFdk−b,又因为gk=∂f∂θk=F⋅θk−bg^k=\frac{\partial{f}}{\partial{\theta^k}}=F\cdot\theta^k-bgk=∂θk∂f=F⋅θk−b,带入之后:gk+1=gk+αkFdkg^{k+1}=g^k+\alpha_kFd^kgk+1=gk+αkFdk,所以可得以下结论:
Fdk=gk+1−gkαkFd^k=\frac{g^{k+1}-g^k}{\alpha_k} Fdk=αkgk+1−gk从这个式子可以看出,有关要计算FdkFd^kFdk的地方我们以后都只需要计算2个梯度值就行了,而这两个梯度值在共轭梯度算法里本来就需要算的,因此并没有增加额外的算法负担。
所以β\betaβ就变成了:
βk=(gk+1)T⋅[gk+1−gk](dk)T[gk+1−gk]\beta_k=\frac{(g^{k+1})^T\cdot[g^{k+1}-g^k]}{(d^k)^T[g^{k+1}-g^k]} βk=(dk)T[gk+1−gk](gk+1)T⋅[gk+1−gk]