11.2、信赖域策略优化算法TRPO强化学习-约束优化求解

基于LunarLander登陆器的TRPO强化学习（含PYTHON工程）

TRPO强化学习算法主要分为3个部分，分别介绍其理论、细节、实现

本文主要介绍TRPO的优化式子的求解

TRPO系列（TRPO是真的复杂，全部理解花费了我半个月的时间嘞，希望也能帮助大家理解一下）：
11.1、信赖域策略优化算法TRPO强化学习-从理论到实践
11.2、信赖域策略优化算法TRPO强化学习-约束优化求解
11.3、信赖域策略优化算法TRPO强化学习-运用实践

只需要代码请直接到11.3、信赖域策略优化算法TRPO强化学习-运用实践

其他算法：
07、基于LunarLander登陆器的DQN强化学习案例（含PYTHON工程）

08、基于LunarLander登陆器的DDQN强化学习（含PYTHON工程）

09、基于LunarLander登陆器的Dueling DQN强化学习（含PYTHON工程）

10、基于LunarLander登陆器的Dueling DDQN强化学习（含PYTHON工程）

11、基于LunarLander登陆器的A2C强化学习（含PYTHON工程）

参考：【TRPO系列讲解】（五）TRPO_理论推导篇

1、 TRPO的优化式子

11.1、信赖域策略优化算法TRPO强化学习-理论分析中详细介绍了TRPO的理论以及如何将TRPO强化学习问题转化为数学的优化式子的求解问题，要求解的式子为：
$$\begin{array}{l}{\max }_{\theta }E{}_{s～{\rho }_{{\theta }_{old}},a～{\theta }_{old}}\left[\frac{{\pi }_{\theta }(a\mid s)}{{\pi }_{{\theta }_{old}}(a\mid s)}{A}_{{\theta }_{old}(s,a)}\right]\\ subjectto{E}_{s～{\rho }_{{\theta }_{old}}}\left[D_{KL}({\pi }_{{\theta }_{old}}(?\mid s)\parallel {\pi }_{\theta }(?\mid s))\right]\le \delta \end{array}$$
这实际上是一个优化问题，我们可以使用迭代法进行求解。

2、 优化式子的泰勒展开

定义优化式子为（单纯为了减少书写）：
$$\begin{array}{l}{\max }_{\theta }{L}_{{\theta }_{old}}(\theta )={\max }_{\theta }E{}_{s～{\rho }_{{\theta }_{old}},a～{\theta }_{old}}\left[\frac{{\pi }_{\theta }(a\mid s)}{{\pi }_{{\theta }_{old}}(a\mid s)}{A}_{{\theta }_{old}(s,a)}\right]\\ subjectto{E}_{s～{\rho }_{{\theta }_{old}}}\left[D_{KL}({\pi }_{{\theta }_{old}}(?\mid s)\parallel {\pi }_{\theta }(?\mid s))\right]\le \delta \end{array}$$

此处需要使用泰勒展开对优化式子进行近似，泰勒公式的基本形式如下（Rn为无穷小项）：

$$\begin{array}{r}f(x)=f(x_0)+\frac{f^{\prime }(x_0)}{1!}(x?x_0)+\frac{f^{\prime \prime }(x_0)}{2!}(x?x_0{)}^2+?+\frac{f^{(n)}(x_0)}{n!}(x?x_0{)}^n+R_n\\ R_n(x)=o[(x?x_0{)}^n]\end{array}$$

首先对优化式子的第一个式子$L_{{\theta }_{old}}(\theta )$在${\theta }_{old}$进行一阶的泰勒展开（由于此处是最大化问题，第一项为常数可以忽略掉）：
$$L_{{\theta }_{old}}(\theta )\to {?}_{\theta }{L}_{{\theta }_{old}}(\theta ){|}_{\theta ={\theta }_{old}}(\theta ?{\theta }_{old})$$
对于第二行的不等式约束，我们对其使用二阶泰勒展开（证明参考自然梯度Natural Policy）：
$$\begin{array}{r}\overline{D_{KL}^{{\rho }_{old}}}({\pi }_{old},{\pi }_{new})\to \frac{1}{2}(\theta ?{\theta }_{old}{)}^{T}A({\theta }_{old})(\theta ?{\theta }_{old})\\ \\ H=A({\theta }_{old})={?}_{\theta }^2\overline{D_{KL}^{{\rho }_{old}}}({\pi }_{old},{\pi }_{new})\end{array}$$

由此，整个问题被再次近似（此处的$A({\theta }_{old})$和$H$是等价的，都代表在$\theta ={\theta }_{old}$的二阶泰勒展开的导数，证明见自然梯度Natural Policy）：
$$\begin{array}{rl}& ma{x}_{\theta }\left[{?}_{\theta }{L}_{{\theta }_{old}}(\theta ){|}_{\theta ={\theta }_{old}}?(\theta ?{\theta }_{old})\right]\\ & \text{subject?to}\frac{1}{2}(\theta ?{\theta }_{old}{)}^{T}A({\theta }_{old})(\theta ?{\theta }_{old})\le \delta \end{array}$$

为了方便书写，我们把求导的项用新变量代替：
$$g^T={?}_{\theta }{L}_{{\theta }_{old}}(\theta ){|}_{\theta ={\theta }_{old}}$$

此外，对max函数取负号，将其转化为求min(一般优化求解都是求min)：
$$\begin{array}{r}\underset{{\theta }^{\prime }}{\min }?g^T({\theta }^{\prime }?\theta )\\ s.t.\frac{1}{2}({\theta }^{\prime }?\theta {)}^{T}H({\theta }^{\prime }?\theta )?\delta <0\end{array}$$

3、 约束方程的拉格朗日求解

对于约束的最小化求解问题，此处使用拉格朗日乘子法（高数学过），将其进行转换，转换的详细理论参考：拉格朗日乘子法（二）：不等式约束与KKT条件。转换后的方程变为：
方程：
$$\mathcal{L}(\theta ,\lambda )=?g^T({\theta }^{\prime }?\theta )+\lambda (\frac{1}{2}({\theta }^{\prime }?\theta {)}^{T}H({\theta }^{\prime }?\theta )?\delta )$$
KKT约束：
$$?\begin{array}{l}\frac{?\mathcal{L}}{?\theta }=?g^T+\lambda ({\theta }^{\prime }?\theta )H=0\\ \lambda \ge 0\\ \lambda \left(\frac{1}{2}{({\theta }^{\prime }?\theta )}^{T}H({\theta }^{\prime }?\theta )?\delta \right)=0\\ \frac{1}{2}({\theta }^{\prime }?\theta {)}^{T}H({\theta }^{\prime }?\theta )?\delta \le 0.\end{array}$$

对上述的约束条件进行求解，即可得到TRPO的更新表达式：
$${\theta }^{\prime }=\sqrt{\frac{2\delta }{g^T{H}^{?1}g}}{H}^{?1}g+\theta$$

4、共轭梯度法求解$H^{?1}g$

$H^{?1}g$非常难求，又需要求逆矩阵还需要和g相乘，在此使用共轭梯度法进行求解。共轭梯度法实际上是求解最小化二次函数的，如：
$$?(x)=\frac{1}{2}{x}^{T}Ax?x^{T}b$$
其中 $b,x\in {\mathbb{R}}^n,A\in {\mathbb{R}}^{n\times n}$且假设矩阵$A$是对称正定的（SPD）。该函数的最小值$x^{?}$可以根据一阶最优条件得到，即导数为零
$$??(x^{?})=A{x}^{?}?b=0$$
这也意味着最小化$?(x)$等价于求解线性方程$Ax=b$。此外，在TRPO算法中，由于二次函数的Hessian矩阵是半正定的，该解具有唯一性。

注意，这边求解的x实际上就是$H^{?1}g$（b=g，A=H）。共轭梯度法求解的详细过程参考我的另一个博客：最速下降法、梯度下降法、共轭梯度法—理论分析与实践

5、Line Search确定步长

不知道兄弟们发现没有，在TRPO的策略网络的更新中，我们居然没有定义学习率唉。这是因为在训练过程中，学习率是已经给定了，以TRPO的更新式子为例：
$${\theta }^{\prime }=\sqrt{\frac{2\delta }{g^T{H}^{?1}g}}{H}^{?1}g+\theta$$
实际上TRPO使用的思路和自然梯度法类似，自然梯度法的更新式子如下：
$$\begin{array}{rl}{\widetilde{?}}_{\theta }\mathcal{L}(\theta )& =F^{?1}{?}_{\theta }\mathcal{L}(\theta )\\ & \\ \theta & =\theta ?\alpha {\widetilde{?}}_{\theta }\mathcal{L}(\theta )\end{array}$$
因此，在TRPO算法中，其学习率lr为：
$$\alpha =\sqrt{\frac{2\delta }{g^T{H}^{?1}g}}$$
但是，我们此处使用了太多的近似，理论的方程并不一定是最好的，那我们我们该如何做呢？我们可以选择小于 $\alpha$的学习率多次尝试（如$0.9^1\alpha$、$0.9^2\alpha$、$0.9^3\alpha$、$0.9^4\alpha$…），直到找到一个能够提升替代优势$L_{{\theta }_{old}}(\theta )$的学习率。

当然，此处的回溯衰减因子和最大的回溯次数都是超参数，在上面的例子中，回溯衰减因子为0.9，如果定义最大的回溯次数是5，那么我们最多尝试到$0.9^5\alpha$，如果还是无法带来替代优势的提升，就跳过这一次更新了。

这个尝试的过程，被称为Line Search。

6、全部流程图

参考：Trust Region Policy Optimization

7、代码解析和基于LunarLander登陆器的TRPO强化学习

…
11.3、信赖域策略优化算法TRPO强化学习-运用实践