11.1、信赖域策略优化算法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相对于一般梯度下降法的改进

一般梯度下降法的缺点：

1. 更新步长难以选取
2. 数据采样效率低

TRPO的优点：

1. 使用了多个近似加速
2. 使用了重要性采样，提升了样本效率
3. 使用自然梯度法进行更新，解决了策略网络更新步长难以选取的问题

TRPO的缺点：

1. 无法处理大参数矩阵：尽管使用了共轭梯度法，TRPO仍然难以处理大的 Fisher矩阵，即使它们不需要求逆
2. 二阶优化很慢：TRPO的实际实现是基于约束的，需要计算上述Fisher矩阵，这大大减慢了更新过程
3. 我们不能利用一阶随机梯度优化器，例如ADAM
4. TRPO 很复杂：TRPO很难解释、实现和调试。当训练没有产生预期的结果时，确定如何提高性能可能会很麻烦

TRPO的改进：近端策略优化算法（PPO）

2、 TRPO常用变量定义

Return：回报U，可以理解为获得高奖励的可能，越大代表越可能获得高奖励。实际使用的是折扣回报，因为对于很远的奖励我们还需要考虑时间成本。对于一个随机的环境，在t时刻我们无法获得Ut的具体取值，因为我们不知道未来的奖励。
$$U_t=R_t+\gamma ?R_{t+1}+{\gamma }^2?R_{t+2}+{\gamma }^3?R_{t+3}+?$$

$\eta$：策略pi的性能评估，也就是折扣回报Ut在t=0的期望，直观的解释是用当前策略网络pi去玩游戏的表现：
$$\eta (\pi )=\mathbb{E}{s}_0,a_0,\dots \left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)\right]$$

Q(s,a)：动作价值函数，其输入为当前状态和要执行的动作，输出为该动作能带来多大的价值，因此，一种贪心的方法是选择能够使Q(s,a)最大动作执行。
$$Q_{\pi }(s_t,a_t)=\mathbb{E}{s}_{t+1},a_{t+1},\dots \left[\sum _{l=0}^{\infty }{\gamma }^{l}r(s_{t+l})\right]$$
Q(s,a)的维度等于动作空间的维度。打个简单的比方，假设我现在有两个动作，向北去捡芝麻，向南去捡西瓜。从最终获得的奖励来看，西瓜是大于芝麻的，但是如果芝麻就在我桌上，但是西瓜在20km以外，那可能我还是选择芝麻得了。那么动作价值函数可能就是（1，0.1）。1是捡芝麻的动作价值，0.1是捡西瓜的动作价值，虽说西瓜好吃，但是太远了，所以其动作价值打分特别低。

Q(s,a)和Ut关系：Q(s,a)是Ut的期望，期望可以理解为求积分，实际上Q是对Ut把所有t之后的时刻（t+1、t+2等等）当作变量求积分得到的。因此Q(s,a)可以直观反应当前状态s下执行各个动作的好坏。
$$Q_{\pi }(s_t,a_t)=\mathbb{E}[U_t\mid s_t,a_t]$$

V(s)：状态价值函数，是Q函数的期望。因为期望的积分动作消去了动作A，因此状态价值函数V可以用来直观的反应一个状态的好坏。其实际上是Q(s,a)对不同a的加权平均。
例如，自家高低三路被破，依据这个状态我们就知道现在的状态打分不太行。状态打分不行的原因是每个动作都不会带来太高的打分（都要输了）。
$$V_{\pi }(s_t)={\mathbb{E}}_{A_t}[Q_{\pi }(s_t,A_t)\mid s_t]$$

A：优势函数，其数值等于动作价值函数减去状态价值函数，相当于动作价值Q(s,a)减去了其baseline：
$$A_{\pi }(s,a)=Q_{\pi }(s,a)?V_{\pi }(s)$$

3、 TRPO的基本思路与TRPO的优化目标

之前提及，$\eta (\pi )$是TRPO算法中衡量策略网络$\pi$优劣的主要参数，假设$\tilde{\pi }$是网络$\pi$更新后的新策略，那么我们有朴素的愿望，那就是越更新越好，就是将$\eta (\tilde{\pi })$写为加法的形式，如：
$$\eta (\tilde{\pi })=\eta (\pi )+(\dots )$$
理论证明，这是确实可行的，$\eta (\tilde{\pi })$可以写为如下的形式（推导见【TRPO系列讲解】（五）TRPO_理论推导篇的8min）：
$$\eta (\tilde{\pi })=\eta (\pi )+\mathbb{E}{s}_0,a_0,\dots ～\tilde{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{A}_{\pi }(s_t,a_t)\right]$$
因此，简单来讲，只要每次更新的$\mathbb{E}{s}_0,a_0,\dots ～\tilde{\pi }\left[{\sum }_{t=0}^{\infty }{\gamma }^t{A}_{\pi }(s_t,a_t)\right]$大于0，那么每次更新一定会提升策略网络的性能；如果每次更新得到的$\mathbb{E}{s}_0,a_0,\dots ～\tilde{\pi }\left[{\sum }_{t=0}^{\infty }{\gamma }^t{A}_{\pi }(s_t,a_t)\right]=0$，那么可以认为该策略网络趋于收敛了。

对于离散的情况，可以将期望进行展开：
$$\eta (\tilde{\pi })=\eta (\pi )+\sum _{t=0}^{\infty }\sum _{s}P(s_t=s\mid \tilde{\pi })\sum _a\tilde{\pi }(a_t=a\mid s_t){\gamma }^t{A}_{\pi }(s_t,a_t)$$
简单交换一下求和的顺序：
$$\eta (\tilde{\pi })=\eta (\pi )+\sum _s\sum _{t=0}^{\infty }{\gamma }^{t}P(s_t=s\mid \tilde{\pi })\sum _a\tilde{\pi }(a_t=a\mid s_t)A_{\pi }(s_t,a_t)$$
定义${\sum }_{t=0}^{\infty }{\gamma }^{t}P(s_t=s\mid \tilde{\pi })$为折扣的访问频率（单纯为了简化式子的表达）：
$${\rho }_{\pi }(s)=\sum _{t=0}^{\infty }{\gamma }^{t}P(s_t=s\mid \pi )$$

由此$\eta (\tilde{\pi })$可以简写为：
$$\eta (\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\tilde{\pi }}(s)\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a)$$

上面这个函数非常简洁明了，但仍然有一些繁杂之处。我们在衡量新策略$\tilde{\pi }$的性能，观测其等式右边，需要得到两个涉及到新策略$\tilde{\pi }$的参数，分别是${\rho }_{\tilde{\pi }}(s)$和$\tilde{\pi }(a\mid s)$。对于$\tilde{\pi }(a\mid s)$，我们只需要对网络进行更新就可以得到，是非常容易的。然而，新策略的折扣的访问频率${\rho }_{\tilde{\pi }}(s)$需要我们在得到$\tilde{\pi }(a\mid s)$后再玩一局游戏才能得到（需要重新和环境交互），相当于需要有一次交互不更新策略网络只为了得到${\rho }_{\tilde{\pi }}(s)$。

为了解决这个问题，对${\rho }_{\tilde{\pi }}(s)$函数进行近似，使用旧策略的${\rho }_{\pi }(s)$来代替${\rho }_{\tilde{\pi }}(s)$，由此可以通过一次交互同时得到${\rho }_{\pi }(s)$和更新后的策略$\tilde{\pi }$：
$$L_{\pi }(\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\pi }(s)\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a)$$
该函数也是用来衡量新网络的表现优劣。为什么能进行替代呢？详细的数学推导过程见【TRPO系列讲解】（五）TRPO_理论推导篇的18min。

这种替代自然也是有条件的，那就是新旧策略网络的${\rho }_{(}s)$不能差太多，也就是新旧策略网络不能差的太多，新旧策略网络输出的实际上概率分布，而衡量两个概率分布之间差异的方法是KL散度。

由此，可以初步写出TRPO算法的优化式子了（当然，在原文中，使用了惩罚项，通过近似才得到了下面给出的式子的，详细的数学推导过程见【TRPO系列讲解】（五）TRPO_理论推导篇的19min）：
1、最大化策略pi的性能评估，近似前是$\eta (\tilde{\pi })$，近似后是$L_{\pi }(\tilde{\pi })$
2、新旧策略网络不能差的太多（保证近似可靠的条件），最大的区别要小于一定的常数

$$\begin{array}{rl}& ma{x}_{\theta }{L}_{{\theta }_{old}}\left(\theta \right)\\ & \text{subject?to?}{D}_{KL}^{max}\left({\theta }_{old},\theta \right)\le \delta \end{array}$$

然而，原文还进一步进行了近似，使用KL散度的期望代替最大的KL散度（不知道为啥），代替后直接蒙特卡洛近似就能之前求出来，因此表达式可以写为：
$$\begin{array}{rl}& ma{x}_{\theta }{L}_{{\theta }_{old}}\left(\theta \right)\\ & \text{subject?to?}{\bar{D}}_{KL}^{{\rho }_{\theta old}}\left({\theta }_{old},\theta \right)\le \delta \end{array}$$

4、 TRPO的替代优势函数与重要性采样的运用

我们$ma{x}_{\theta }{L}_{{\theta }_{old}}\left(\theta \right)$的主要目的是得到新的策略网络，因此在此式子之中，旧策略网络$\pi$的参数${\theta }_{old}$相当于是已知量，因此我们实际需要最大化的部分是下式的最右边的那一项：
$$L_{\pi }(\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\pi }(s)\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a)$$
也就是：
$$\sum _s{\rho }_{\pi }\left(s\right)\sum _a\tilde{\pi }(a\mid s)A_{\pi }\left(s,a\right)$$

上面这个式子实际上就是替代优势函数（surrogate advantage）$\mathcal{L}({\theta }_k,\theta )$的原型。为了计算上面的式子，我们需要使用蒙特卡洛方法，因此先将其写成期望的形势：
$$\mathcal{L}({\theta }_k,\theta )=\sum _s{\rho }_{\pi }\left(s\right)\sum _a\tilde{\pi }(a\mid s)A_{\pi }\left(s,a\right)={\mathrm{E}}_{s～{\rho }_{\pi },a～\tilde{\pi }}\left[A_{\pi }\left(s,a\right)\right]$$

但是，问题来了，注意观察期望分布的服从函数$s～{\rho }_{\pi },a～\tilde{\pi }$，可见状态的获取和动作的获取分别依赖于旧的策略$\pi$和新策略$\tilde{\pi }$，这就给采样带来了很大的困难。具体表现为，动作a服从的分布来自于新网络$\tilde{\pi }$，每更新一次网络，就需要服从更加新的网络的a来进行计算，因此每次采样的数据只能用于一次网络更新，效率非常低（一次采样数据无法使用batch多次训练）。

重要性采样的基本公式如下所示（可以更换期望服从的分布）：
$$\begin{array}{rl}{E}_{x～p(x)}[f(x)]& =\int p(x)f(x)dx\\ & =\int \frac{q(x)}{q(x)}p(x)f(x)dx\\ & =\int q(x)\frac{p(x)}{q(x)}f(x)dx\\ & =E_{x～q(x)}\left[\frac{p(x)}{q(x)}f(x)\right]\end{array}$$
由此可得：
$${\mathrm{E}}_{s～{\rho }_{\pi },a～\tilde{\pi }}\left[A_{\pi }\left(s,a\right)\right]=E_{s～{\rho }_{\pi },a～\pi }\left[\frac{\tilde{\pi }(a|s)}{{\pi }_{}(a|s)}{A}_{\pi }(s,a)\right]$$
由此，动作和状态都依赖与旧策略$\pi$，我们可以愉快的使用同一组数据多次对网络进行更新啦。

因此，最终得到的优化式子就是(使用了KL散度的期望代替最大的KL散度)：

$$\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}$$

5、 TRPO的迭代求解

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