这一篇我们来讲一些目前RL的SOTA的方法，也是两条线，value-based和policy-based，其实两条线最后的发展渐渐都统一到actor-critic上去了，逻辑就按照周老师课件中所列：
首先再回顾下policy gradient的公式（我用的是MC版的）：
\[\nabla_{\theta}J(\theta)=E_{\pi(\theta)}[\sum_{t=0}^{T-1}G_t\nabla_{\theta}\log \pi_{\theta}(a_t|s_t)]\]这里面就包含了policy gradient的两个问题，第一个就是：PG是on-policy learning，它是用要优化的策略去和环境交互采样的，无法利用已经存在的轨迹（poor sample efficiency）。
第二个问题它的训练非常不稳定，造成这个问题的原因除了它自身的方差很大之外，还有几个方面的原因（当然这几个原因也是相互影响的）：
- 数据和学习的过程不是独立的
- step too far —> bad policy —> bad data collection
- 一旦进入一个bad policy，可能无法从其中恢复，一坏再坏，直接训崩
那如何去解决这两个问题呢？
- 用Importance Sampling使得policy gradient变成off-policy learning
- 针对训练不稳定，使用natural gradient
Natural Policy Gradient
接下来我们介绍一下Natural policy gradient，我看完觉得和Newton迭代很像，也是想利用二阶导的信息，表达式也是多了一个矩阵的逆，但是它不是直接去求目标函数$J(\theta)$的二阶导（可能这个比较难求？），而且通过限制更新后策略和原来策略分布之间的KL-divergence来导出了结果，我们下面来看看它是怎么做的。
Policy gradient is the steepest ascend in parameter space with Euclidean metric:
\[d^*=\nabla_{\theta}J(\theta)=\lim_{\epsilon\to0}\frac{1}{\epsilon}\arg\max J(\theta+d)~~~~s.t.~~||d||\leq\epsilon\]因为上面的邻域限制是在参数空间中的欧氏距离，所以它有一个缺点是它对于我们是如何参数化policy function是比较敏感的（sensitive to the parameterization of the policy function）。
而Natural policy gradient的思想就是我不考虑在参数空间中的限制，而直接考虑两个policy function $\pi_{\theta}$和$\pi_{\theta+d}$的差异，而这其实就是两个分布之间的差异。
这两者之间的差别有一个例子可以很形象地解释，例子来自这篇博客Natural Gradient Descent，之后的一些证明的截图也是参考这篇博客。
上下两张图分别是两个不同的正态分布，都是均值不同，但是上面的两个分布的方差比下面的两个大。我们可以看到如果是考虑参数$\mu$之间的差异，那么按照欧氏距离上下两幅图都是4，但是如果是考虑分布之间的差异，用KL-divergence的话，上面的就要比小面的要小了，所以只在参数空间做限制的话不能将分布的信息给考虑进去。
所以Natural policy gradient的目标就变成了：
\[d^*=\arg\max J(\theta+d)~~~~s.t.~~~KL(\pi_{\theta}||\pi_{\theta+d})=c\]通过限制KL-divergence为一个常数c，可以确保我们是在分布空间里以一个常速度在移动，而且也不需要去关心我的policy function是如何参数化的（robust to the parametrization of the model as we only care about the distribution induced by the parameter）。
下面就是关于具体要如何计算了，会涉及到一些数学推导和证明。
首先要推导一下：Fisher Information Matrix $F$是$KL(p(x|\theta)||p(x|\theta’))$的Hessian矩阵，其中$F=E_{x\sim p(x|\theta)}[\nabla\log p(x|\theta)\nabla\log p(x|\theta)^T]$，如果不知道什么是Fisher Information Matrix的话，可以继续看上面那篇博客的前面一篇去了解，它的定义就是score function的方差。
接下来就是要用的万能的泰勒展开了，第一步我们先计算KL-divergence的近似：
\[KL(\pi_{\theta}||\pi_{\theta+d}) \approx KL(\pi_{\theta}||\pi_{\theta}) + E_{\theta}(\nabla _{\theta}\log \pi_{\theta})^Td + \frac{1}{2}d^TFd \approx \frac{1}{2}d^TFd\]然后再对$J(\theta+d)$做一阶泰勒展开，整个带约束的优化问题写成拉格朗日的形式就变成了：
\[d^*=\arg\max_d J(\theta+d) - \lambda (KL(\pi_{\theta}||\pi_{\theta+d}) - c) \approx \arg \max_d (J(\theta) + \nabla_{\theta} J(\theta)^Td - \frac{1}{2}\lambda d^TFd + \lambda c)\]再对d求导令其等于0就得到d的表达式了：
\[\begin{gather} 0 = \frac{\partial}{\partial d}(J(\theta) + \nabla_{\theta} J(\theta)^Td - \frac{1}{2}\lambda d^TFd + \lambda c) = \nabla_{\theta} J(\theta) - \lambda Fd \\ d = \frac{1}{\lambda}F^{-1}\nabla_{\theta} J(\theta) \end{gather}\]在更新的时候，$\lambda$可以被吸收进学习率中，所以Natural policy gradient的更新规则是：$\theta_{t+1}=\theta+\alpha F^{-1} \nabla_{\theta} J(\theta)$
可以看到Natural policy gradient实际上是一个second-order optimization。（注意这里的$F$并不是$J(\theta)$的Hessian矩阵，这也是natural gradient与牛顿迭代的区别）
- $F=E_{\pi_{\theta}}[\nabla \log \pi_{\theta}(s,a) \nabla \log \pi_{\theta}(s,a)^T]$是Fisher information matrix，也是KL-divergence的二阶导矩阵
- F刻画了policy distribution的曲率（curvature of the policy distribution relative to the parameter $\theta$）
Importance Sampling
之前在将Q-learning时也提到过Importance Sampling，这里再重新介绍一遍。
IS calculates the expected value of $f(x)$ where $x$ has a data distribution $P$。如果这个分布的概率密度求积分很难求的话，我们就可以利用另外一个分布$Q$来做积分，然后使用probability ratio去校正这个结果：
\[E_{x\sim p(x)}[f(x)]=\int p(x)f(x)dx=\int q(x)\frac{p(x)}{q(x)}f(x)dx=E_{x\sim q(x)}[\frac{p(x)}{q(x)}f(x)]\]我们这里使用IS的目的是为了利用已经存在的轨迹数据，考虑一下我们的目标函数：
\[J(\theta)=E_{a \sim \pi(\theta)}[\sum_t r(s_t,a_t)]\]为了方便说明我们就不考虑对$t$求和，这个式子就是我们要对reward求期望，然后action是来自policy $\pi(\theta)$，那如果我们想利用其他策略采集到的数据来训练的话，就可以将其改写成：
\[J(\theta)=E_{a \sim \pi(\theta)}[ r(s,a)]=E_{a \sim \hat{\pi}}[\frac{\pi_{\theta}(s,a)}{\hat{\pi}(s,a)}r(s,a)]\]这样就可以使用已用的轨迹进行训练了，$\hat{\pi}$称作behavior policy，而$\pi_{\theta}$是target policy，这就是off-policy。
Increase the Robustness with Trust Regions
由于引入了behavior policy，因此我们的目标函数就变成了：
\[\theta = \arg \max_{\theta} J_{\theta_{old}}(\theta)=\arg \max_{\theta}E_{\theta_{old}}[\frac{\pi_{\theta}(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}r(s_t, a_t)]\]这个值可能会变的非常大，当$\frac{\pi_{\theta}}{\pi_{\theta_{old}}}$很大的时候，而且当两个分布差异很大的时候这很可能发生。要想缓解这个问题，可行的做法就是限制两个分布的差异，KL-divergence又可以上场了。
我们的目标就变成了最大化：
\[J_{\theta_{old}}(\theta)=E_{\theta_{old}}[\frac{\pi_{\theta}(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}r(s_t, a_t)]~~~~s.t.~~~KL(\pi_{\theta_{old}}||\pi_{\theta}) \leq \delta\]就和前面Natural policy gradient类似了，Trust Region直观的解释就放一张图：
走一遍和前面一样的流程
Trust Region Policy Optimization（TRPO）
TRPO: Trust region policy optimization. Schulman, L., Moritz, Jordan, Abbeel. 2015
因为Fisher Information Matrix的逆的计算开销非常大，TRPO通过解线性方程组$Hx=g$来得到估计值$x=H^{-1}g$。
而解$Hx=g$是等价于minimize$\frac{1}{2}x^THx-g^Tx$，所以就把这个问题转化成一个optimize the quadratic equation了，文章中使用conjugate gradient来解的（这一块我还没有好好看，也就是知道个名字，没动手操作过）。
文章还有一个贡献，就是证明了通过TRPO iteration是可以得到一个更优的policy：
这样每次最大化$M_t$，可以保证真实的目标$J$是non-decreasing的，而这其实是一种Minorize-Maximization（MM）算法。
Limitations of TRPO
直接放图了
Proximal Policy Optimization (PPO)
Proximal policy optimization algorithms. Schulman, Wolski, Dhariwal, Radford, Klimov. 2017
PPO也是要限制新老策略的KL-divergence，但是它不算二阶导，怎么做呢，首先，将目标函数写成如下形式（$A_t$是advantage function）：
\[\max_{\theta} E_t[\frac{\pi_{\theta}(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}A_t] - \beta E_t[KL(\pi_{\theta_{old}}(\cdot|s_t), \pi_{\theta}(\cdot|s_t))]\]其中$\beta$是需要动态调节的，通过adpative KL penalty来稳定更新，意思就是如果算出来的KL距离大于某个给定的阈值，那么就将$\beta$增大，反之小于某个阈值时，就将$\beta$减小。
PPO with clipping
在PPO的论文中还提出了一种操作非常简单，但是效果很不错的控制方法，先回顾一下我们已经讲过的一些方法：
文章中提出的限制方法是简单粗暴的：直接对概率比进行裁剪：
\[L_t(\theta)=\min(r_t(\theta)\hat{A_t},~~~clip(r_t(\theta),~1-\epsilon, ~1+\epsilon)\hat{A_t})\]$\epsilon$在文章的模拟中用的是0.2。
我觉得其实公式最外面的求min是设计得挺巧妙的，它并不仅仅考虑了要把概率比给限制在$(1-\epsilon, 1+\epsilon)$里，同时还考虑了Advantage function的符号。如果Advantage function是正的，我们是要鼓励action使得$\pi_{\theta}(a_t|s_t)$变大，但是又不能变得过大，这里再引用一下OpenAI Spinning Up里说的：the new policy does not benefit by going far away from the old policy.
于是上面的公式变成了：
\[L_t(\theta)=\min(\frac{\pi_{\theta}(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}，1+\epsilon)\hat{A_t}\]而当Advantage function是负的，对应的action我们是希望它的概率$\pi_{\theta}(a_t|s_t)$要小的，但是又不能变得太小：
\[L_t(\theta)=\max(\frac{\pi_{\theta}(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}，1-\epsilon)\hat{A_t}\]
在PPO之前，policy gradient的方法大都因为太不稳定没有什么好的应用，TRPO虽然利用trust region稳定了训练，但是计算二阶矩阵的过程比较繁琐，而PPO的出现既保有了trust region思想带来的稳定性，同时在实现上也非常简单，只需要在传统的vanilla policy gradient上改动几行就OK了（周老师课件上是这么说的，但是我想说其实并不是，clip这步确实很简单，但是首先你得解决off-policy的问题，写过你就懂了）。从此以后，policy-based RL才算真正和value-based RL分庭抗礼。
Pytorch 代码
'''
在这个github仓库里
https://github.com/leyuanheart/Reinforcement_Learning_Algorithms/tree/main/pytorch/PPO
'''
The 2022 ICLR Blog Track中有一篇博客专门介绍PPO算法的implementation detail，感兴趣的同学可以参考The 37 Implementation Details of Proximal Policy Optimization.
接下来介绍一下从value-based的角度发展起来的一些最新的算法。
Deep Deterministic Policy Gradient (DDPG)
Deterministic Policy Gradient Algorithms, Silver et al. ICML 2014
DDPG提出的动机是想把DQN给扩展到连续的动作空间，为什么之前的DQN不能用于连续的动作空间呢？因为在DQN中有一步：
\[a^* = \arg \max_a Q^*(s,a)\]如果是离散的动作空间，这个过程是一个通过枚举法选出最佳的动作。但是如果动作空间是连续的，那么可选动作集合是无穷，没办法枚举。一种做法是从动作集合中进行抽样，得到一个候选动作集${a_1, \ldots,a_N}$，然后从中选出一个使Q value最大的，这种做法虽然可行，但是无法得到全局的最优；另一种方法就是把$Q^*(s,a)$看成$a$的函数，然后去求解这样一个优化问题，比如用梯度上升（假设可导），但是这样意味着在训练Q-network的过程中，每次遇到选action时还要再解一个优化问题， 这是不太现实的，而DDPG是通过设计网络结构来让这个优化过程变得简单。
DQN中的policy $\pi$是由“greedy on Q”来确定的，而DDPG的思路是先假设有一个deterministic 策略$\mu$可以使得$Q(s, \mu(s))$最大化，然后将这个$\mu$给参数化成$\mu_{\theta}$，从而将$\arg \max Q$的过程转变成优化$\mu_{\theta}$的过程。
上面这张图其实有些歧义，其实应该是$\max_a Q(s, a) \approx Q(s, \mu_{\theta}(s))$并且$a^*=\mu_{\theta}(s)$。
然后借鉴DQN中fixed target的思想，DDPG中关于$Q$和$\mu$各自都有train和target两套网络。
上图就是DDPG的各个部分的目标，梳理一下这个流程就是：通过policy network $\mu_{\theta}(s)$产生动作 $a$，作为使$Q_{\phi}(s, a)$最大的那个动作，利用$Q_{\phi_{target}}(s’, \mu_{\theta_{target}}(s’))$来计算Q-target（其中$d$是“done”的意思），$Q_{\phi}$的目标就是最小化TD-error，对于$\mu_{\theta}$来说，其目标就是使$Q_{\phi}(s, \mu_{\theta})$尽可能的大。
这其实也是Actor-Critic的思想，我们可以对比一下从policy-based方法走到Actor-Critic和从value-based方法走到Actor-Critic有什么区别和联系。
回忆一下，policy-based方法中，它的主体是policy gradient，然后因为其中 $G_t$的方差很大，所以引入了Q-network去近似它；而value-based方法中，主体是Q value，但是$\max_a Q(s,a)$这一步对于连续动作空间很困难，所以引入了policy-network去解决它。但二者最后是殊途同归。
还有一个关于Actor-Critic（从policy-based方法发展过来的）和DDPG很重要的区别：Actor-Critic使用的是stochastic policy，而DDPG用的是deterministic policy，拿连续动作空间来说明，Actor-Critic是将policy建模成一个Gaussian分布，然后通过从中抽样来获得action，而DDPG则是直接输出一个确定的action（其实如果用的是Actor-Critic的建模方式，但是最后输出的是Gaussian分布均值作为action的话，也可以算是deterministic policy）。
Pytorch 代码
'''
在这个github仓库里
https://github.com/leyuanheart/Reinforcement_Learning_Algorithms/tree/main/pytorch/DDPG
'''
Twin Delayed DDPG (TD3)
Addressing Function Approximation Error in Actor-Critic Methods, Fujimoto et al. ICML 2018
DDPG也会有和DQN一样的问题，就是会overestimate Q value，而且就算是换成Actor-Critic variants of Double DQN也依然会存在这个问题。
TD3提出了3个改进的方法（也可以叫做tricks）：
- Clipped Double Q learning：学习两个Q网络（这就意味着包括它俩各自的target网络一共有4个Q网络），选择值较小的那个构造target
- “Delayed” Policy Updates：更新policy的频率要慢于更新Q-function。论文中推荐one policy update for every two Q-function updates。文中的解释是因为如果Q-function训练的误差很大的话，那么在policy update的时候（因为是要$\max_{\theta}Q(s,\mu_{\theta}(s))$），所以得到的policy就很差，反过来训练Q-function时也会造成overestimation的问题。所以TD3的做法是在更新policy前先多训练几步Q-function，让其误差小一些，再用来更新policy。
- Target Policy Smoothing：TD3给target action增加noise，从而降低Q-function对action变动的敏感性（原文中的话是”make it harder for the policy to exploit Q-function errors by smoothing out Q along changes in action”），相当于引入了一些随机性，增加policy的探索性，作为一个regularizer（和Dropout的思想类似）
具体的做法是对于target的构造：
而对于target action的smoothing：
先对噪声做一个truncate，然后加到target action上，再将值限制在action的取值范围之内，就完成了smoothing的操作。
Pytorch 代码
必须强烈推荐这个github: sfujim/TD3
'''
在这个github仓库里
https://github.com/leyuanheart/Reinforcement_Learning_Algorithms/tree/main/pytorch/TD3
'''
Soft Actor-Critic (SAC)
SAC optimizes a stochastic policy in an off-policy way, which unifies stochastic policy optimization and DDPG-style approaches（SAC是将随机策略优化和DDPG-type的方法统一到一起的一种方法）
SAC引入了entropy regularization.
Entropy是用来刻画不确定性的量，$H(P)=E_{x \sim P}[-\log P(x)]$，熵越大，随机性越大。
Entropy-regularized RL的思想是：policy不仅要能最大化累计收益，还要具有一定的随机性，这样能保持它的探索性，用数学表达就是：
Value function的定义也要相应地做修改，在每一步都要加上一个entropy的项：
因此，每一步的迭代表达式为：
和TD3一样，SAC也学习两个Q-function，但是SAC只学习一个policy，并且是stochastic的。Q-target的构造和TD3类似：
然后Q-function的更新就最小化TD error：
\[L(\phi_i)=E[(Q_{\phi_i}(s,a)-y(r,s',d))^2]\]policy的更新在原来最大化期望收益的基础上再加了一项entropy，也就是最大化新定义下的$V^{\pi}(s)$：
这里在求期望时有一个麻烦的问题，就是分布是依赖于策略的参数$\theta$的，所以SAC利用了重参数化的技巧， reparameterize $a$ as sample from a squashed Gaussian policy：
这样一来，求期望的分布就不依赖于参数了：
再结合Q-function的部分，policy的优化目标为：
关于重参数化，本来是为了解决深度学习中梯度反向传播的问题，求期望的分布依赖于参数之所以会有问题，是因为我们是通过从分布中采样，用样本均值来近似期望的，但是在神经网络中，抽样这步操作是不可导的，这就导致梯度在这里无法反向传播，而经过重参数化之后，抽样的分布是和参数无关的，和参数相关的操作只是一些求和，所以梯度是可以回传的。这里放一张介绍Reparameterization Trick的简要介绍。
补充内容
关于SAC的action，这里补充一些内容。为了应对连续动作空间，SAC使用了Gaussian分布参数化策略。但是高斯分布的定义域是正负无穷，而现实问题往往动作的取值是有上下限的，因此需要做一些校正。贴一张截取自论文的图片。
然后spinning up中计算$\log \pi(a|s)$是对上面的（21）式做了变换，使得计算结果更加数值稳定，相关的推导见下图。
至此，一些目前SOTA的RL方法就介绍完了（也不知道现在还能不能叫SOTA了…），这里再放一张周博磊老师的总结slide。
再谈谈我自己的体会，首先，从policy gradient出发采用的是stochastic策略，也不是只能用于离散动作空间了，恰恰相反的是policy gradient最开始就是为了解决连续动作空间的问题。还有一点就是由于policy gradient是一种on-policy learning，所以要想进行off-policy learning就需要借助Importance Sampling，但是计算density ratio的方差很大，所以在off-policy这一角度上来说，还是使用Q-learning的这一支更有优势（得益于Q-Learing天然的可以看成off-policy），但是也可能是因为我policy gradient这一支学习得不够，像前面的TRPO我就没有很深入地去研究，代码也没写过，留坑待填吧。
距离上一篇文章隔了将近半年吧，与最新的研究成果之间的距离又被拉大了，虽然紧迫感和焦虑感都与日俱增，但急也不是办法，还是得稳扎稳打。
