37.2° Blog

1.Policy Gradient 变种

1.1 Value-based RL vs. Policy-base RL

在价值函数优化里面主要有deterministic policy。当学习了Q table后，会直接取argmax对应的动作，采取行为。

$$a_t = \underset{a}{arg~max~}Q(a, s_t)$$

但是在策略优化中，有机会得到stochastic policy（随机策略） output。从这个策略函数输出，会得到一个概率，从给出的概率里面采样就可以得出需要采取的行为。

对于策略函数优化，优化的objective function定义如下：

$$J(\theta)=E_{\tau \sim \pi_\theta}[R(\tau)]$$

通过让策略函数与环境进行交互，产生了轨迹 $\tau$，reward function会输出它会得到多少奖励。我们希望这条轨迹尽可能多的得到奖励。

policy gradient(REINFORCE)算法：

$$\begin{align} \nabla_\theta J(\theta) & = E_{\pi_\theta}[G_t \nabla_\theta log \pi_\theta(s,a)] \\ & \approx \frac{1}{N} \sum_{i=1}^{N} G_t^i \nabla_\theta log \pi_\theta(s_i, a_i) \end{align}$$

计算$J(\theta)$的梯度，得到policy gradient，由return reward 和策略函数的score function组合起来的，然后用MC近似的方法产生很多轨迹，产生很多score function的likelihood，从而近似实际的gradient，用这个gradient可以优化策略函数的参数$\theta$.

然后我们希望进一步改进policy gradient的variance，使得variance尽可能小，使得策略优化的训练更稳定。

定义了函数advantage function：

$$A^{\pi}(s,a)=Q^{\pi}(s,a) - V^{\pi}(s)$$

由两部分组成，一部分是Q function，另一部分是对应的baseline，因为$V^{\pi}(s)$是Q函数动作的平均，因此可以作为Q天然的baseline。

把policy gradient改进成advantage actor-critic ($score function \times advantage function$)

$$\nabla_\theta J(\theta) = E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a) A^{\pi_\theta}(s,a)]$$

advantage actor-critic是后面最新强化学习的基础。算advantage function的时候，是由两个方程组成的，因为如果状态很多的话，我们只能用近似的方法。所以对于Q函数，我们只能用近似函数，对于价值函数V我们也需要一个近似函数。

所以我们需要两组参数，对于价值函数的近似函数我们需要有一组$v$ :

$$V_v(s) \approx V^{\pi}(s )$$

对于Q函数我们需要有$w$ 这个参数来拟合

$$Q_w(s,a) \approx Q^{\pi}(s,a)$$

所以我们同时优化这两种参数，使用TD的算法或者MC的方法。

1.2 Advantage actor-critic

我们可以进一步改写，对于Q函数我们可以用另一种形式来写 —— bootstrapping TD target的方法（由两部分组成，实际得到的reward，和他做bootstrapping得到下一个状态的价值）。于是我们可以写成TD error $\delta^{\pi\theta}$的形式

$$\delta^{\pi_\theta}=r(s,a) + \gamma V^{\pi_\theta}(s') - V^{\pi_\theta}(s)$$

对$\delta^{\pi\theta}$进行简单的变换，就又可以进行反算得到advantage function，所以这两者是近似的关系，是它的估计。

$$\begin{align} E_{\pi_\theta}[\delta^{\pi_\theta}|s,a] & = E_{\pi_\theta}[r + \gamma V^{\pi_\theta}(s') | s, a] - V^{\pi_\theta}(s ) \\ & = Q^{\pi_\theta}(s,a) - V^{\pi_\theta}(s) \\ & = A^{\pi_\theta}(s,a) \end{align}$$

所以我们可以把policy gradient的TD error重写：

$$\nabla_\theta J(\theta) = E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a) \delta^{\pi_\theta}]$$

这样重写的好处是只需要取拟合它的价值函数就可以。

$$\delta_v=r+ \gamma V_k(s') - V_k(s)$$

比如这里只需要拟合价值函数$V$，它的函数的参数是 $\kappa$，这样就只用去估计一组critic的参数，就省了很多参数的估计，这样就可以使得价值函数的训练更稳定。

1.3 Critic at different Time-Scales

对于这个参数不同的优化办法也会得到不同的update，$V_k(s) = \psi(s)^T k$ 价值价值函数approximator(线性的拟合函数）当状态涉及特征$\psi(s)$，再乘以$κ$ ($κ$ 的意义是对状态的特征进行线性的组合），这样就可以回归它的价值函数。

如果选取的更新方式是基于MC的更新方式：

$$\Delta k = \alpha({\color{red}G_t} - V_k(s)) \psi(s )$$

• TD error就会变成实际得到的return $G_t$ 再去减去价值函数作为$κ$ 去优化

如果选取更新的优化方式是TD(0) 的方法

$$\Delta k = \alpha({\color{red} r+ \gamma V_k(s') } - V_k(s)) \psi(s )$$

• 可以直接带入TD target减去价值函数

我们甚至可以用多步的return：

$$\Delta k = \alpha({\color{red} \sum_{i=0}^{k} \gamma^i r_{t+i} + \gamma^k V_k(s_t+k) } - V_k(s)) \psi(s )$$

• 比如走三步再bootstrapping价值函数，然后可以把公式中红色部分作为critic函数的参数估计

不同的函数参数估计方法会得到不同的critic parameter

1.4 Actors at Different Time-Scales

同样对于actor 策略函数，我们算策略函数的gradient $J(\theta)$，同样对于不同的方法可以得到不同的policy gradient。

$$\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a) A^{\pi \theta}(s,a)]$$

用蒙特卡洛的方法去算MC actor-critic对于actor policy 的gradient：

$$\nabla_\theta J(\theta) = \alpha (G_t - V_k(s_t)) \nabla_\theta log \pi_\theta(s_t, a_t)$$

• 将$G_t - V_k(s_t)$作为更新乘以score function

如果优化方法选取的TD方法：

$$\nabla_\theta J(\theta) = \alpha (r + \gamma V_k(s_{t+1}) - V_k(s_t)) \nabla_\theta log \pi_\theta(s_t, a_t)$$

如果优化方法选取 k-step return：

$$\nabla_\theta J(\theta) = \alpha (\sum_{i=0}^{k} \gamma^i r_{t+1} + \gamma^k V_k(s_{t+k}) - V_k(s_t))\nabla_\theta log \pi_\theta(s_t, a_t)$$

• 让（k-step走到k步的return，再去bootstrapping对应的价值函数，再减去现有状态的价值函数）作为估计。

1.5 Policy gradient算法总结

基于不同的policy gradient方法可以得到不同的policy gradient：

$$\begin{align} \nabla_\theta J(\theta) & = E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a) {\color{red}G_t}] -- REINFORCE \\ & = E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a) {\color{red}Q^w(s,a)}] -- Q Actor-Critic\\ & = E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a) {\color{red}A^w(s,a)}] -- Advantage Actor-Critic\\ & = E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a) {\color{red} \delta }] -- TD Actor-Critic\\ \end{align}$$

• 如果采取的纯粹MC的方法，即通过采取轨迹后，把轨迹每个点的score function(likelihood)计算下来，算每个点的return。这样就会得到$G_t$作为它的量，乘以score function，这样就会得到REINFORCE；
• 这里采取的reward是用Q函数作为reward，Q函数和$G_t$有一个对应关系， $G_t$相当于是Q函数的一个采样，于是可以得到对于Q函数的actor-critic；
• 如果进一步减去baseline，用价值函数作为baseline，就可以推导出advantage actor- critic算法；
• 如果进一步采取简化的办法，用TD target作为reward function，就会变成TD actor-critic。
• 所以有如上几种actor-critic的方法，基于最后得到的奖励函数的不同，可以用不同的优化方法去优化。

对应的critic，对应了policy evaluation（选取MC或者TD learning的优化方法）会去不同估计它们的参数。

2.The State of the Art RL Methods

两条主线介绍策略优化的方法：

1. Policy Gradient → Natural Policy Gradient/TRPO → ACKTR → PPO
2. Q-learning → DDPG → TD3 → SAC

Paper：

Policy Gradient→Natural PG/TRPO→ACKTR→PPO

TRPO: Trust region policy optimization. Schulman, L., Moritz, Jordan, Abbeel. 2015

ACKTR: Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation. Y. Wu, E. Mansimov, S. Liao, R. Grosse, and J. Ba. 2017

PPO: Proximal policy optimization algorithms. Schulman, Wolski, Dhariwal, Radford, Klimov. 2017

TRPO：通过数学证明保证了策略优化的稳定性以及单调递增的特性。

ACKTR：对TRPO有了改进，数值上算Fisher Information Matrix用了K-FAC的方法，使得用于更广泛的用途中，效率也得到提升。

PPO：对之前的TRPO有了更简化的改进，使得算法更加易懂且容易实现。

Q-learning→DDPG→TD3→SAC

DDPG: Deterministic Policy Gradient Algorithms, Silver et al. 2014

TD3: Addressing Function Approximation Error in Actor-Critic Methods, Fujimoto et al. 2018

SAC: Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, Haarnoja et al. 2018

3.First lines of works on SOTA policy optimization

3.1 Policy Gradient

问题1：Policy Gradient的sample efficiency非常低

sample efficiency意思是我们需要去采取的样本，即我们需要让正在优化的策略和环境进行交互，这个交互的过程称为sample collection/data collection，这个交互的过程多少就决定了sample efficiency的多少。因为policy gradient是一种on-policy learning，即只有一种policy，优化的policy和采集数据的policy是同一个policy。

$$\nabla_\theta J(\theta) = E_{a \sim \pi_\theta}[\nabla_\theta log \pi_\theta(s,a) r(s,a)]$$

问题2：训练过程非常不稳定

只要policy update出了一些错误，或者step-size有一些问题，就会使训练的过程变得很不稳定，以至于导致训练过程崩溃。这和强监督学习，标记图片训练分类器是很不一样的。因为对于强监督学习方法，样本之间关联是非常低的，我们给的假设都是iid的假设，样本之间并没有相关度。意思是假设这批样本质量很差也没关系，下一批好就行了，这样就导致就算样本里面有些噪声，但是整个训练是没有问题的。但是在强化学习里面这就不成立了，这个iid假设就不成立了。在强化学习里面，采集到的数据（和环境交互得到的数据）之间有很高的相关度，这就导致策略本身对采集到的数据影响非常大；

所以说如果某一步的更新程度(policy gradient)，或者step-size不是这么对，这样就产生了很错误的policy gradient；然后用这个错误的policy gradient去更新我们当前的policy，就会得到很差的policy；用这个很差的policy又去和环境交互，又采集一些数据，就会得到很糟糕的一堆数据；用很糟糕的数据计算新一轮的policy gradient，又产生很差的gradient，这样形成一个错误的循环，整个训练过程变得越来越糟；这样就很难从一个错误的policy里面恢复，就导致整个训练过程就崩溃。

上图无论加不加normalization都会发现训练过程很不稳定；横轴是训练的时间，纵轴是当前策略的表现。这种不稳定性就是由于policy gradient的更新和data collection是耦合起来的。 所以我们在改进policy gradient的时候就希望能改进这两个policy gradient的问题。

改进思路

对于第一点，我们希望把on-policy的进一步扩展成off-policy的。我们可以引入importance sampling（重要性采样）的方法，这也是在TRPO中使用了的。

对于第二点，我们希望整个训练变得更稳定。这里可以用到的方法就是在训练过程中引入Trust region（信赖域）的机制，也就是说它采取的gradient总是在一个安全的范围里面更新策略函数；另外也可以用natural policy gradient的办法，这是一个二阶的优化方式，我们直到SGD是一阶的近似，这样算出来的gradient其实并不准。

3.2 Natural policy gradient / TRPO

（1）Natural Policy Gradient

我们之前算的policy gradient就直接对于policy function算它的优化。这里得到的gradient是在 参数空间(parameter space) 里面上升的最快的gradient，假设参数空间里面是一个欧几里得的量(Euclidean metric)：

$$d^*=\nabla_\theta J(\theta) = \underset{\epsilon \rightarrow0}{lim} \frac{1}{\epsilon} arg~max~J(\theta+d) ~~~~ s.t. || d|| <= \epsilon$$

• 比如说在参数空间里面的增量d ，d 是类似于欧几里得空间的一个球，现在需要找一个方向去优化这个d 使得整个公式极大化。这样我们找到这个d 是在参数空间里面steepest ascend（最陡上升）。
• 但是这里有一个问题就是：我们这样算出来的$d^*$是对我们策略函数采取怎样的参数化形式比较敏感。如果policy function是用高斯的拟合函数或softmax的拟合都会对算出来的d 产生影响，这样就会导致当我们把d 加到参数上面后，这个价值函数的输出（一个概率）和参数更新并没有联系起来。

所以我们这里提出了另一种方法：我们想从steepest ascend in distribution space(policy output space) 考虑优化这个参数。

$$d^*=\nabla_\theta J(\theta) = arg~max~J(\theta+d),~~ s.t. KL(\pi_\theta || \pi_{\theta+d})=c$$

• output就是${\pi}_{\theta}$它实际的output，这里希望它实际的output和变化之前的output变化尽可能的小，在这个尽可能小的空间里面去优化d，参数空间找到d使得下一步更新出来的策略的输出（概率： ${\pi}_{\theta+d}$尽可能的小)。
• 我们这里衡量两个策略的近似距离用的KL-divergence（KL散度）。我们希望KL-divergence等于一个固定的比较小的数，我们把constraint（限制）加进去过后，整个优化过程算它的梯度的时候就可以使得d让最后输出的空间能够变得尽量的连续，并且和curvature（曲率）没有关系。curvature在代数几何里面对于概率函数是如何参数化它有非常大的联系的。所以我们想使整个策略过程，和采取怎样的策略函数的参数形式没有关联。

（2）KL-Divergence as Metric for Two Distributions

KL散度（相对熵）是来衡量两个分布之间的相关度以及近似程度。

$$KL(\pi_\theta || \pi_{\theta '}) = E_{\pi_\theta}[log \pi_\theta] - E_{\pi_\theta}[log \pi_{\theta '}]$$

虽然KL散度并不是一个真实的度量，因为它不是不满足三角不等式的，并且它是非对称的。但是当d足够小的时候，它也可以近似成一个对称的形式，所以当策略函数优化的neighborhood足够小的时候，KL可以当成一个度量，我们这里可以进一步进行一个简单的推导，把KL-divergence作为一个泰勒展开(Taylor expansion)：

$$KL(\pi_\theta || \pi_{\theta+d}) \approx \frac{1}{2} d^TFd$$

可以知道KL-divergence的一阶导数其实是0，这里保留的其实是它的二阶导数（泰勒展开对应的二阶数）。

这里的F 在概率里面叫做Fisher Information Matrix（费雪信息矩阵），关于KL散度的二阶导数。

所以现在面临一个优化问题，使得我们去优化d使得满足条件：$s.t. KL(\pi_\theta || \pi_{\theta+d})=c$ 即使得更新过后策略的输出与更新前的策略的差异度尽可能的小，小于或等于c。所以我们可以把这两个优化条件整合起来：

$$d^*=arg~max~J(\theta+d),~~ s.t. KL(\pi_\theta || \pi_{\theta+d})=c$$

我们可以把它写成Lagrangian form（拉格朗日形式）

$$d^*= \underset{d} {arg~max~}J(\theta+d) - \lambda (KL[\pi_\theta || \pi_{\theta+d}]-c) \\ \approx \underset{d} {arg~max~} + \nabla_\theta J(\theta)^Td - \frac{1}{2} \lambda d^TFd + \lambda c$$

就可以让第一个条件再组合第二个条件，这里λ 是一个参数，使得在解这个优化问题的时候让两个问题都满足。 然后对优化的函数做泰勒展开，就会得到它是由四部分组成的：第一部分 argmax和d 其实并没关系，第二部分是$J(\theta)$函数的梯度乘以d ，第三部分是KL散度的拆开（一阶导数为0，只保留到二阶导数的形式），第四部分$\lambda c$.

然后我们再对这个展开的形式求导。因为第一部分和第四部分和d 没有关系，对第二、三部分做简单的部分，得到natural policy gradient：

$$d=\frac{1}{\lambda} F^{-1} \nabla_\theta J(\theta)$$

由两部分组成：一部分是F 矩阵，Fisher Information Matrix（费雪信息矩阵），对它求逆；再乘以原来的policy gradient。

这样我们就得到了natural policy gradient的一个概念。这样我们就可以得到如下参数更新化的形式：

$$\theta_{t+1} = \theta_t + \alpha {\color{red} F^{-1} } \nabla_\theta J(\theta)$$

这个形式相对于最早的policy gradient就多了$F^{-1}$这一项。Fisher Information Matrix（费雪信息矩阵）是可以直接用score function算出来的，当我们采集到likelihood function后，算它的score function，再乘以它的transfer(转置)再把它加起来，这样就得到了fisher information matrix。它就相当于second-order derivative of the KL-divergence。

$$F = E_{\pi_\theta}(s,a)[\nabla log \pi_\theta(s,a) \nabla log \pi_\theta(s,a)^T]$$

这里F 有明确的几何定义：在测量相对于模型参数的曲率（curvature of the policy(distribution))。

除以F就相当于我们用某一种参数化的策略函数形式，直接去除以它的curvature，就可以把curvature去掉，这样就使得整个参数优化形式和采取怎样的策略优化独立开了。

所以natural policy gradient的核心就在于让这个优化过程跟它的策略函数（采取怎样的优化形式）无关，这样可以使得整个优化过程变得更稳定，这样可以使得不管你采取怎样的策略函数参数化形式，策略函数的output（这个概率）都会尽可能小的变化。

natural gradient的进一步理解： https://wiseodd.github.io/techblog/2018/03/14/natural-gradient/

缺点：必须计算Fisher Information Matrix。

（3）Policy Gradient with Importance Sampling

另外一个方面是我们想把policy gradient方法改成off-policy的方法，我们知道off-policy learning自身有很多好处，我们可以用另一种算法在环境里面去探索(explore)，采集到很多激进的数据，这样来喂给优化的策略。

这里采取方法是Importance sampling(重要性采样)：Importance sampling在采样过程里面也是用的比较广泛的，它的简单概念是：我们现在假设要去估计一个函数的期望，比如说要估算$f(x)$这个值，x 是从p分布里面采样出来的；有时候我们不知道怎么去p 分布里面采样，比如说p分布的形式非常奇怪，没法去直接采样，我们只能从如uniform distribution或者Gaussian distribution里面采样，那么我们怎么去根据一个不知道怎么采样的p 估计这个$f(x)$参数呢？

$$E_{x \sim p}[f(x)] = \int p(x)f(x)dx=\int q(x) \frac{p(x)}{q(x)}f(x)dx = E_{x\sim q} [\frac{p(x)}{q(x)}f(x)]$$

通过简单的变换，$f(x)$针对p 的期望，变换成另一种期望的形式，这样x 就可以从另外一个分布里面采样了。采样很多的x后再取平均。

Importance sampling和策略优化有什么联系呢？对于策略优化这个函数也可以做一个简单的变换：

$$J(\theta)=E_{\color{red} a \sim \pi_\theta}[r(s,a)]=E_{\color{red}a \sim \hat \pi}[\frac{\pi_\theta(s,a)}{\hat \pi(s,a)}r(s,a)]$$

比如说策略优化的objective function是$J(\theta) = E_{\alpha～\pi\theta}[r(s,a)]$是优化的策略里面产生的，假设我们现在优化函数没法对它采样，就可以从另外一个策略函数里面对它采样，比如从$\hat{\pi}$ 里面去采样action，通过importance sampling去乘以ratio来近似。这里变化就是我们可以用behavior policy $\hat{\pi}$去产生实际的轨迹。

（4）Increasing the Robustness(鲁棒性) with Trust Regions(信赖域)

所以这样就可以把策略函数改写成基于之前另外一个策略的一个优化函数，另外一个策略最简单的办法是可以用之前的这个策略，在Deep Q learning中有两个策略函数，behavior policy是用的之前的策略函数，因为之前的策略函数产生的数据我们也可以放到这个replay buffer里面，所以就可以重用之前采到的数据。

所以现在的代价函数$J_{ {\theta}_{old} }$包含了${\theta}_{old}$,${\theta}_{old}$表示之前一些比较老的策略函数的参数，我们就可以用${\theta}_{old}$与环境进行交互采集到的data，让用data来优化现在这个policy gradient，唯一需要做的就是乘以一个ratio，让奖励函数的优化无偏。

$$\theta=\underset{\theta}{arg~max~} J_{\theta_{odd} }(\theta)=\underset{\theta}{arg~max~} E_t[\frac{\pi_\theta(a_t | s_t)}{\pi_{\theta_{odd} }}R_t]$$

但是这里存在一个问题，这里的ratio $\pi_\theta/{\pi}{ {\theta}_{old} }$有可能会非常大，如果 $\pi_{\theta_{odd} }$这个值如果非常小的话，ratio这个权重就会非常大，就会使得整个优化过程变得非常不稳定。

所以这里我们希望进一步引入一个constraint(限制)使得ratio尽可能的小，即更新后新一轮的policy和老的policy的变化尽可能的小。那么这里就面临一个问题，怎么衡量两个策略的相似度呢？

那么就可以引用前面提到的Kullbeck-Leiler(KL) divergence，KL散度就可以用来衡量两个策略之间的相似程度。

$$KL(\pi_{\theta_{odd} } || \pi_\theta) = - \sum_a \pi_{\theta_{odd} }(a|s) log \frac{\pi_\theta(a|s)}{\pi_{\theta_{odd} }}$$

比如我们想衡量当前优化函数和之前策略函数之间的距离，就可以用KL散度的形式来度量。

这里就可以引入TRPO（Trust Regions Policy Optimization)的优化函数。

优化函数由两部分组成，第一部分是包含了importance sampling这样重写一下的代价函数:

$$J_{\theta_{odd} }(\theta)=E_t[\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{odd} }(a_t|s_t)} R_t]$$

第二部分是加的一个优化过程中的限定，限定使得优化的 ${\pi}_{\theta}$和上一个 $\pi_{\theta_{odd} }$之间的距离尽可能的小。可以想象成一个球，空间内叫做trust region（信赖域）。

如上图，之前如果不加这个限制，直接用gradient ascent，使得一直往上走，但是存在的问题是有可能有一步的更新非常大或者step-size步数没有设定好，就很有可能冲出悬崖了，那整个优化过程就掉到悬崖里面去了，就再也不可以恢复出来；

所以我们加了这个限制的话，就类似于在每一步加了个圆圈，圆圈区域里面对应的就是trust region，每次优化过程只能在这个圆圈里面（安全的区域）选择一个方向，这样就可以使得这个训练尽可能的稳定，这样也使得它的概率输出和上一步的概率输出的步数尽可能的小，随着训练过程也可以使得trust region缩的越来越小，更新也会变得越来越小，整个过程也会变得越来越稳定。

（5）Trust Region Optimization

对Trust Region Optimization进行进一步的推导，对价值函数做泰勒展开，展开如下：

$$J_{\theta_t} \approx g^T(\theta - \theta_t) \\ KL(\theta_t||\theta) \approx \frac{1}{2}(\theta - \theta_t)^TH(\theta - \theta_t) \\ where ~g = \nabla_\theta J_{\theta_t}(\theta) ~and~ H=\nabla_\theta^2 KL(\theta_t || \theta) ~and~ \theta_t ~is ~ the ~ old ~ policy~parameter$$

泰勒展开后，objective变为：

$$\theta_{t+1} = \underset{\theta}{arg~max~}g^T(\theta-\theta_t) \\ s.t. \frac{1}{2}(\theta-\theta_t)^T H(\theta - \theta_t) <= \delta$$

我们要优化下一步${\theta}_{t+1}$，我们希望${\theta}_{t+1}$满足两个条件：一是argmax(尽可能大）；二是使得新出来的$θ$是满足限制式子（小于 $\delta$的。

我们解上式优化形式的时候，可以把quadratic equation（二次方程）写成Natural gradient(自然梯度）。

$$\theta_{t+1}=\theta_t+\sqrt{\frac{2 \delta}{g^T H^{-1}g} }H^{-1}g$$

其中H 是Fisher Information Matrix(FIM)(费雪信息矩阵)，前面用的F 表示：

$$H=\nabla_\theta^2(\pi_{\theta_t} || \pi_\theta)=E_{a,s \sim \pi_{\theta_t} }[\nabla_\theta log \pi_\theta(a,s)\nabla_\theta log \pi_\theta(a,s)^T]$$

H是对应KL散度的二阶导数，可以通过score function的变换直接求出来。

我们的更新形式${\theta}_{t+1}$并没有$\alpha$ step size，这里用来控制step-size的是$\delta$(learning rate)。

$$KL(\pi_{\theta_{odd} }(·|s_t) || \pi_\theta(·|s_t)) <= \delta$$

$δ$是直接在限制更新之后的policy和之前的policy的近似程度 ，也就是说做了这个推导过后$\delta$和learning rate直接联系起来了。这也是TRPO推导非常好的地方，不需要设定step-size，只需要指定trust region的大小，即更新后的策略和之前的策略输出距离多少，然后用距离去推出step-size。可以使得trust region设的很小，这样就使得更新非常稳定。

$\delta$可以使得参数更新不会策略函数概率输出的程度，不会产生剧烈的变化。

所以TRPO是对natural policy gradient的更进一步的推导。

Sham Kakade. “A Natural Policy Gradient.” NIPS 2001

TRPO是在natural policy gradient的基础上加了importance sampling。

（6）Trust Region Policy Optimization(TRPO)

TRPO还提出了怎么近似计算FIM(费雪信息矩阵)。

我们计算Fisher Information Matrix的$H$，就相当于natural policy gradient 要对这个矩阵求逆$x=H^{-1}g$。当矩阵维度很大的时候，矩阵求逆的计算量（复杂度）非常大，所以TRPO就提出了不要矩阵求逆，而是转化成解线性方程的形式$Hx = g$，解$Ax=b$的形式。

因为：

$$f'(x)=Ax-b=0$$

所以我们可以转换成quadratic equation去解：

$$x=\underset{x}{arg~max~}f(x) = \frac{1}{2} x^TAx -b^Tx$$

因此我们现在要去优化这个quadratic equation（二次方程）

$$\underset{x}{min~}\frac{1}{2}x^THx-g^Tx$$

解这个的方法是conjugate gradient method(共轭梯度法），与gradient ascent非常像但是迭代次数更少。

TRPO完整算法，可以当成natural policy gradient更进化的版本

算法中有用CG（conjugate gradient共轭梯度法）去解优化的过程；最终得到θ \thetaθ更新的形式，就可以用二阶的gradient去更新它的函数，这样就把trust region的限制加到了优化过程中，使得训练过程变得更稳定。

（7）Result and Demo of TRPO

Demo video is at ：https://www.youtube.com/watch?v=KJ15iGGJFvQ

（8）Limitation of TRPO

计算量非常大。虽然用了conjugate gradient method(共轭梯度法），但是对于每一步每个policy都要算H 。

在近似H 的时候，H 本身是个期望，但是我们在近似这个期望的时候是用样本近似，需要很多样本。

$$H=E_{s,a \sim \pi_{\theta_t} }[(\nabla_\theta log \pi_\theta(s,a))^T(\nabla_\theta log \pi_\theta(s,a))]$$

conjugate gradient(CG)的优化本身也是一个复杂的过程。

TRPO在有些领域没有DQN好

3.3 ACKTR

（1）ACKTR: Calculating Natural Gradient with KFAC

Y. Wu, et al. “Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation”. NIPS 2017.

ACKTR的核心思想是想提升TRPO的计算效率。在TRPO里面有一步是算Fisher information matrix(FIM) $H^{-1}$，在矩阵维度很大的时候求逆计算量非常大。因此，ACKTR提出用Kronecker-factored approximation curvature(K-FAC) 方法来加速求逆。

$$F=E_{x \sim \pi_{\theta_t} }[(\nabla_\theta log \pi_\theta(x))^T(\nabla_\theta log \pi_\theta(x))]$$

可以被替换为：

（2）Optimizing Neural Networks with Kronecker-factored Approximate Curvature

思想来自Martens et al.ICML’15：https://arxiv.org/pdf/1503.05671.pdf

在优化神经网络的时候，最常用的优化办法是SGD（Stochastic Gradient Descend，随机梯度下降），SGD是一阶优化方法，所以不是很准确；因此提出了用Natural Gradient Descend进一步优化它，Natural Gradient Descend涉及了二阶的优化，并且考虑了loss function本身的curvature（曲率），所以它的优化效率比一阶的更高。二阶优化Natural Policy Gradient的形式：

$$\theta_{t+1} = \theta_t + \alpha {\color{red}F^{-1} } \nabla_\theta J(\theta)$$

其中：

$$F=E_{\pi_\theta}(s,a)[\nabla log ~\pi_\theta(s,a) \nabla log~ \pi_\theta(s,a)^T]$$

需要算Fisher Information Matrix求逆，所以当F非常大的时候，比如模型参数很多，是神经网络，这样直接求Natural Policy Gradient的效率就很低。

所以这篇论文就提出用K-FAC近似Fisher Information Matrix。

它的大致思想是把Fisher Information Matrix做分解。神经网络是由多层结构组成的；F这个矩阵写成diagonal block的形式，每一个block对应了某一层的参数，这某一层的参数只与层内的参数相关，所以本身这个矩阵实在diagonal（对角线）上的矩阵；对于每一个对角线上的矩阵都可以做kronecker product的分解，分解后对这个矩阵求逆就等于对分解出来的矩阵求逆。所以这篇论文就利用了这个思想来加速训练。

蓝色的线是对SGD优化，横轴是它的training iteration，效率是非常低的，因为它是first-order的优化；换成K-FAC natural gradient的方法后，loss降得非常快，training iteration可能是它的十倍的效率提升。

ACKTR方法就是把natural gradient里面算Fisher Information Matrix这一步，用kronecker product做了个近似，提升了算法的效率。

对比实验结果

3.4 PPO

（1）PPO

TRPO的简化版本，把里面的优化过程做了更简单的优化。

$$maximize ~ \theta ~ E_t[\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{odd} }(a_t|s_t)}A_t] \\ suject~ to~ E_t[KL[\pi_{\theta_{odd} }(·|s_t), \pi_\theta(·|s_t)]] <= \delta$$

更新的policy和原来的policy之间的KL散度距离小于提前定的trust region的范围。

上式写unconstrained的形式：

$$maximize ~ \theta ~ E_t[\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{odd} }(a_t|s_t)}A_t] - \beta E_t[KL[\pi_{\theta_{odd} }(·|s_t), \pi_\theta(·|s_t)]]$$

用$\beta$参数把两个条件同时组合起来，这样相当于得到了一个objective function。使得整个joint loss极大化后，第一项使得带了importance sampling的gradient极大化，$\beta$也是正数，所以相当于使得第二部分极小，这样就可以让两个条件同时满足。

PPO的思想就是用了unconstrained form重新把两个条件结合起来，所以就可以在优化本身的客观函数的同时，也把条件考虑进去。

PPO的算法同时还做了Adaptive KL Penalty。

根据实际的情况大小，$\beta$会做一个对应的调整。当更新的policy比之前的policy较大的时候，比如大于$1.5\delta$的时候，我们就会让它的penalty变得更大，${\theta}_{k+1}$中第二项就会被考虑的更多；

当KL-divergence小于$\delta/1.5$的时候，就减小penalty的影响，使得算法做更大的更新。所以把 ${ {\beta}_{k}/2}$, 也就是说算法对KL-divergence有一个自适应(adaptive)的过程来调整penalty这一项的强度。

PPO可以取得和TRPO类似的效果，但优势是速度要快很多，因为PPO本身优化的过程是利用first-order optimization(SGD，一阶优化) 优化的，所以优化效率比二阶的TRPO快很多，因为PPO的算法过程中并没有去计算KL-divergence或者Fisher information matrix。

（2）PPO with clipping

在PPO中有probability ratio(概率比)$r_t(\theta)$，当前策略与之前策略输出的对比。

$$r_t(\theta)=\frac{\pi_\theta(a_t |s_t)}{\pi_{\theta_{odd} }(a_t|s_t)}$$

根据形式不同有各种形式的优化函数。

• PG算法(没有trust region)：直接用advantage function × reward。

$$L(\theta)=r_t(\theta) \hat A_t$$

• 加入KL constraint : TPRO的情况，要满足constraint去优化它。

$$L_t(\theta)=r_t(\theta) \hat A_t \\ s.t. ~ KL[\pi_{\theta_{odd} }, \pi_\theta] <= \delta$$

• KL penalty : KL用β \betaβ写进去，PPO的创新点，KL会adaptive（自适应）这个算法。

$$L_t(\theta)=r_t(\theta) \hat A_t - \beta KL[\pi_{\theta_{odd} }, \pi_\theta]$$

PPO提供了第二种方式是把objective function自身带了clipping，所以它提出了更复杂一些的形式来处理本身loss的优化情况。

$$L_t(\theta)=min(r_t(\theta) \hat A_t, clip(r_t(\theta), 1-\epsilon, 1+\epsilon)\hat A_t)$$

设定了clipping函数，clipping会根据你当前的probability ratio的大小。如果大于$1+\epsilon$或小于 $1-\epsilon$ ，就会把它clip掉。使得$r_t(\theta)$ 保持在 $1-\epsilon$和$1+\epsilon$之间。

通常 $\epsilon$设定为0.2。这样就奠定了ratio的更新情况。

（3）How the clipping works

Clipping函数形式做简单的分解

$$L^{CLIP}(\theta)=min(\frac{\pi_\theta(a_t |s_t)}{\pi_{\theta_{odd} }(a_t|s_t)} \hat A_t, clip(\frac{\pi_\theta(a_t |s_t)}{\pi_{\theta_{odd} }(a_t|s_t)}, 1-\epsilon, 1+\epsilon)\hat A_t)$$

看成两种情况，当advantage是正数的时候，我们就需要去鼓励当前采取的行为。

$$L(\theta; \theta_{odd})=min(\frac{\pi_\theta(a_t |s_t)}{\pi_{\theta_{odd} }(a_t|s_t)}, (1+\epsilon)) \hat A_t$$

min取ratio和$1+\epsilon$更小的那个数来作为weight；

如果ratio很大的话，如果没有这个min它就会取很大，所以加了个clip使得它最大不能超过 $1+\epsilon$。这样就使得policy output本身不会有太激进的变化。

另一种条件形式，如果advantage是负数的时候，说明我们当前的行为并不会带来很大的奖励，所以我们需要discourage，让agent不要做出这样的行为，去减少它。

$$L(\theta; \theta_{odd})=max(\frac{\pi_\theta(a_t |s_t)}{\pi_{\theta_{odd} }(a_t|s_t)}, (1+\epsilon)) \hat A_t$$

这里做了max的操作，当ratio特别小的时候，max operator就可以起作用，这样就使得更新不会变得特别小，也是限制了更新策略函数最小的值。

PPO的形式：

大部分PPO算法都是用了Clipped Objective的形式，因为Clipped Objective非常容易写出来，pytorch写loss形式的时候，可以把clipped写出来就可以用简单的SGD去优化它了。

PPO相对于TRPO和policy gradient的效率以及安全性更高，且实现非常容易。只需要加入几行代码，去限制它的loss function就可以实现，就可以把vanilla policy gradient(VPG，普通策略梯度算法)改写成PPO的形式。

（4）Result of PPO

连续控制问题(MuJuCo) : https://gym.openai.com/envs/mujoco

紫线是PPO，随着training增长非常快，效率相对于其他算法更稳定。

Demo of PPO at : https://blog.openai.com/openai-baselines-ppo/

Emergence of Locomotion Behaviours in Rich Environments by DeepMind (Distributed PPO) : https://www.youtube.com/watch?v=hx_bgoTF7bs

（5）Code of PPO

Paper link of PPO : https://arxiv.org/abs/1707.06347

Code example : https://github.com/cuhkrlcourse/DeepRLTutorials/blob/master/14.PPO.ipynb

def compute_loss(self,sample):
...
  surr1 = ratio * adv_targ#之前的情况
  surr2 = torch.clamp(ratio,1.0-self.clip_param,1.0+self.clip_param)*adv_targ#加上clipping后
  action_loss = -torch.min(surr1,surr2).mean()#取min
...

通过这几行代码就可以把之前policy gradient变成PPO的形式，而其他不用做改变，这就是为什么PPO用的这么广泛，可以加入几行代码使得效率和稳定性都上一个台阶。

4.Second lines of works on SOTA policy optimization

另一条主线，从价值函数优化的进展，从Q-learning开始。

4.1 DDPG

全称Deep Deterministic Policy Gradient(DDPG)，虽然名字是policy gradient，但是是对DQN的扩展。

DQN算法在学到Q network后输出是离散的，action是取得argmax，只能输出唯一的离散的输出。DDPG提出动机是能够使得DQN扩展到连续的动作空间。比如之前的MuJuCo这样环境是连续控制的问题，所以需要连续控制的强化学习算法。

DDPG本身是和DQN非常像的，可以看作DQN的连续空间的版本。

$$DQN：a^* = \underset{a}{arg~max~}Q^*(s,a)$$

当学出Q network后，我们会取argmax，得到唯一的action。

$$DDPG：a^* = \underset{a}{arg~max~}Q^*(s,a) \approx Q_\phi(s,\mu_\theta(s))$$

DDPG让离散的动作空间变成连续的。

这里取得的action是从deterministic policy ${\mu}_{\theta}(s)$直接出来的， ${\mu}_{\theta}(s)$本身我们可以当作一个policy，也就是说当我们把一个状态放进去后 ${\mu}_{\theta}(s)$就会直接输出一个连续的值。当得到 ${\mu}_{\theta}(s)$后，值可以直接放到Q network里面去，就可以得到Q的值。

因为action $a$是连续的，所以我们假设Q function对于$Q_{\phi}(s,a)$也是可以直接求导的，这样就可以把policy gradient的优化和value function的优化两者结合起来。

DDPG优化函数

它也利用了target network和policy network，所以有两个network：target network以及它正在优化的organization network。

Q-target：它的policy network也是有两个版本，有一个target network以及它正在优化的那个network，所以对于policy network和Q network都有两个网络。

$$y(r, s', d) = r + \gamma(1-d)Q_{\phi_{targ} }(s', \mu \theta_{targ}(s))$$

Q function：所以它这里Q function的优化和之前value function优化是差不多的，从replay buffer里面直接采样tuples放到Q-function函数中优化。

$$min~E_{s,r,s',d\sim D} [Q_\phi(s,a) - y(r, s',d)]$$

policy：当得到Q函数后，对策略函数policy进行优化的形式是：

$$\underset{\theta}{max~}E_{s \sim D}[Q_\phi(s, \mu_\theta(s))]$$

固定$Q_{\phi}$去优化$\theta$，$\theta$是deterministic policy它的参数，这样就使得policy极大化。

DDPG也和DQN类似，用了replay buffer的思想，以及target network的思想。对于它的value network和policy network都有target network。

DDPG example code (using the sampe codebase for TD3): https://github.com/sfujim/TD3/blob/master/DDPG.py

4.2 TD3

（1）Twin Delayed DDPG (TD3)

DDPG中的Q函数有时会overestimate Q-values（过估计）。实际的Q value和Q network输出的Q value进行了对比。

实际的Q value是用MC的方法去算的。举个例子，给定了policy，去产生1000条轨迹，就会得到return $G_t$，取平均后就会得到Q实际对应得 $G_t$的值。用Q network输出的值和实际的G 的平均值做对比，发现Q network输出远比实际值高，说明Q network估计的网络做了overestimate，这样就使得整个训练变得不稳定。

TD3针对DDPG提出了三种改进：

1. Clipped Double-Q Learning. 用了两个Q-network。
2. “Delayed” Policy Updates. 用了"Delayed"的思想，对于策略函数的更新的速度是要慢于Q network的，这样就可以使得Q network的更新和策略函数的更新两者解耦，关联度降低，这样可以克服overestimate。
3. Target Policy Smoothing. 引入smoothing的思想。

TD3有两个Q函数，$Q_{\phi_1}$， $Q_{\phi_2}$所以它在算Q-target的时候用了min operator

$$y(r, s', d) = r + \gamma(1-d) \underset{\color{red}i=1,2}{~min~}Q_{\phi_{i, targ} }(s', {\color{red}a_{TD3}(s')})$$

对于两个Q network取更小的那个值作为它的Q network。假设有两个人在同时estimate，现在估计算的Q-target，算法采用的是估计的更小的那个值，这样可以减弱这两个估计overconfident的可能性。

对于policy smoothing也引入了clipping的思想。

$${\color{red}a_{TD3(s')} } = clip(\mu \theta_{targ}(s') + clip(\epsilon, -c, c),a_{low}, a_{high}), \epsilon \sim N(0, \sigma)$$

对$\epsilon$本身进行clipping， epsilon是从normal distribution里面采用出来的，使得引入了一些噪声clip，噪声加到输出${\mu}_{\theta,targ}(s')$上面，相当于加入了一些扰动。

加入噪声起到了regularize（规则化）的目的。

（2）实验结果

有意思的是自己的DDPG和官方的DDPG差异很大，说明DDPG本身对于初始化或者调参是十分敏感的。TD3对参数并不是那么敏感。

TD3和SAC是当前最好的强化学习算法之一，但是有意思的是在这篇TD3的论文中TD3比SAC好，但是在SAC的论文中显示SAC比TD3好。说明强化学习算法对参数是十分敏感的，这也是强化学习本身困难的原因。

TD3 paper: Fujimoto, et al. Addressing Function Approximation Error in Actor-Critic Methods. ICML’18 : https://arxiv.org/pdf/1802.09477.pdf

Author’s Pytorch implementation (very clean implementation!): https://github.com/sfujim/TD3/

这是个非常好的代码库，强烈推荐！

4.3 SAC

（1）Soft Actor-Critic(SAC)

提出了entropy regularization（熵正则化）的思想。

Entropy是一个量度，度量一个随机变量对概率函数自身的无序程度

$$H(P) = E_{x\sim P}[-log~P(x)]$$

Entropy-regularized RL : 让我们策略优化的时候，让expected return和entropy两者做一个权衡，所以它的loss function 是可以写成这样一个joint loss function:

$$\pi^*=arg~max~E_{\tau \sim \pi}[\sum \gamma^t(R(s_t, a_t, s_{t+1})+ \alpha H(\pi(·|s_t)))]$$

第一部分是它本身的expected return，第二部分是entropy。因为算法本身是希望对未知空间尽可能多的探索，这样就有可能获取得到更多奖励的行为。所以就做了这样一个trade-off（权衡），同时去优化，在保证得到算法policy多样性的情况下，也能得到expected return极大化。

Value function就把这个entropy写到Value functon里面去了，增加了个entropy bonus(熵加成) $\alpha H(\pi(.|s_t))$在极大化objective function的时候，让entropy也极大化。

$$V^\pi(s)=E_{\tau \sim \pi}[\sum \gamma^t(R(s_t, a_t, s_{t+1})+ \alpha H(\pi(·|s_t))) | s_0 =s]$$

在推导Bellman equation的时候也写进了entropy，对entropy进行展开，Q函数就会变成如下形式：

$$Q^\pi(s,a) = E_{s' \sim P, a' \sim \pi}[R(s,a,s') + \gamma (Q^\pi(s', a') + \alpha H(\pi(·|s')))] \\ = E_{s' \sim P, a' \sim \pi}[R(s,a,s') + \gamma (Q^\pi(s', a') - \alpha log ~\pi(a'|s'))]$$

采用sample update，Q函数就会进一步写成如下形式：

$$Q^\pi(s,a) \approx r+ \gamma (Q^\pi(s', \hat a') - \alpha log ~\pi(\hat a'|\hat s'), \hat a' \sim \pi(·|s')$$

SAC也TD3比较类似的是也用了两个Q functions， $Q_{\phi_1}$，$Q_{\phi_2}$。最早两个Q function的思想其实是在Duel Q network里面，可以消除Q network的overestimate。

与TD3一样，target取了极小的输出，再把entropy regularization(熵正则化) $\alpha log{\pi}_{\theta}(\hat{a'}|s')$也写进去 。

$$L(\phi_i, D) = E[(Q_\phi(s,a) - y(r,s',d))^2]$$

$$y(r, s', d) = r + \gamma(1-d)( \underset{\color{red}j=1,2}{~min~}Q_{\phi_{targ, j} }(s', \hat s') - \alpha log ~\pi(\hat a'|\hat s')), \hat a' \sim \pi(·|s')$$

优化的时候$V^{\pi}(s)$的时候也加了entropy$\alpha log\pi(a|s)$

$$V^\pi(s)=E_{\tau \sim \pi}[Q^pi(s,a)+ \alpha H(\pi(·|s_t))] \\ =E_{\tau \sim \pi}[Q^pi(s,a) - \alpha ~ log(\pi(·|s_t))]$$

SAC算法还用了 reparameterization(重参数) 的方法。

$$\hat a_\theta(s, \epsilon) = tanh(\mu_\theta(s) + \sigma_\theta(s) ~·~ \epsilon), \epsilon \sim N(0,1)$$

之前是为了更新action，action本身包含了$\epsilon$，$\epsilon$是从normal distribution$N(0,1)$里面采样的。网络输出mean ${\mu}_{\theta}(s$)和 ${\sigma}_{\theta}(s)$乘以随机的 $\epsilon$，加和起来后随机性是从 $\epsilon$来的。

这样就可以使得expectation(期望)本来a是针对于policy function ${\pi}_{\theta}$的采样，变成跟参数 $\theta$没有关系的采样。

$$E_{\tau \sim \pi_\theta}[Q^{\pi_\theta}(s,a)- \alpha ~ log \pi_\theta (a|s) \\ =E_{\tau \sim N}[Q^{\pi_\theta}(s,\hat a_\theta)- \alpha ~ log \pi_\theta (\hat a_\theta(s,\epsilon)|s)$$

策略优化函数可以写成：

$$\underset{\theta}{max} E_{s\sim D, \epsilon \sim N}[\underset{j=1,2}{min} Q_{\phi_j}(s, \hat a_\theta(s, \epsilon)) - \alpha log \pi_\theta(\hat a_\theta(s, \epsilon)|s)]$$

与TD3差异是有了entropy term 和reparameterization(重参数) trick。

（2）Reparameterization Trick介绍

很多时候我们需要对$f(x)$采样估计一个期望后算一个针对于$\theta$的gradient，问题是期望也是和 $\theta$相关，所以就比较难算gradient

$$\color{red} \nabla_\theta E_{x \sim p\theta(x)} [f(x)]$$

所以我们引入 $\epsilon$ 的思想

ϵ是从一个独立的分布采样出来的（uniform distribution或高斯分布）

$$\epsilon \sim q(\epsilon)$$

采样出 $\epsilon$后，把 $\epsilon$放到某一个new network去产生$x$

$$x=g_\theta(\epsilon)$$

就可以让原来的gradient做一个简单的变化，让expectation是针对与 $\epsilon$的

$$\nabla_\theta E_{x \sim p\theta(x)}[f(x)] = \nabla_\theta E_{\epsilon ~ q(\epsilon)}[f(g_\theta(\epsilon))] \\ = E_{\epsilon ~ q(\epsilon)}[\nabla_\theta f(g_\theta(\epsilon))]$$

就相当于用$\epsilon$来Reparameterize x ，这样就可以把$g_{\theta}(\epsilon)$写成：

$$g_\theta(\epsilon)=\mu_\theta + \epsilon \sigma_\theta ~ where~ \epsilon \sim N(0,1)$$

带参的 $\theta$就放到$\mu$和 $\sigma$里面去了，就和 $\epsilon$随机性没有关系。

Reparameterization Trick和REINFORCE有关系，都是通过参数sampling的方法规避求导的问题。 http://stillbreeze.github.io/REINFORCE-vs-Reparameterization-trick/

（3）SAC算法实现

https://github.com/pranz24/pytorch-soft-actor-critic/blob/master/sac.py

SAC is known as SOTA for robot learning:

• Learning to Walk in the Real World with Minimal Human Effort. https://arxiv.org/pdf/2002.08550.pdf
• https://www.youtube.com/watch?v=cwyiq6dCgOc