有了的理论基础，再看第二部分，就会简单很多。所谓的Deep Reinforcement Learning，无非是Deep Neural Network和Reinforcement Learning的结合，也就是用DNN作为Value Estimator和Policy Function。有了DNN的加持，我们发现RL在很多问题上的表现有了质的飞跃。

在所有机器学习算法中，DRL最接近于生物大脑的学习方式(除了Backpropagation)；在与人类智力较量的棋牌电竞等游戏中，横扫人类最顶尖的选手，可以说是相当震撼，引用职业九段围棋选手段柯洁的话说：

人类数千年的实战演练进化，计算机却告诉我们人类全都是错的。我觉得，甚至没有一个人沾到围棋真理的边。

Deep Q Learning

DQN可谓是DRL的开山之作，发表于2013年的NIPS；稍作修改后，即在2015年投向Nature，这篇也是较早出圈，投中顶级学术期刊的文章之一。

最原始的版本称之为DQN，算法如下:

DQN Algorithm

1. Initialise Q network $Q_\theta$ and its copy target Q network $Q_{\theta'}$, an empty replay buffer $\mathcal{R}$ with capacity $C$
2. For each episode:
   1. For each time-step $t$:

      1. Use $\epsilon$-greedy policy to get action $a_t$ from $Q_\theta(s_t)$, get next state $s_{t+1}$ and reward $r_t$, check if it is terminal $d_t$, push transition tuple $<s_t, a_t, r_t, d_t, s_{t+1}>$ into replay memory $\mathcal{R}$

      2. Periodically update, if $t\bmod T = 0$, then sample a batch of $N$ transition tuples $\{s_i, a_i, r_i, d_i, s_i'\}$, and calculate:

         1. Target Q value $q_i = r_i + \gamma(1-d_i)\max_{a'}Q_{\theta'}(s_i', a')$
         2. TD Error loss $L(\theta) = N^{-1}\sum_i(Q_\theta(s_i) - q_i)^2$

         Update Q network: $\theta \leftarrow \theta - \alpha \nabla_\theta L(\theta)$

      3. Periodically update, if $t \bmod T' = 0$:

         synchronise target Q network $\theta' \leftarrow \theta$

文章用的DNN其实并不深，只有两层convolution和两层dense，只是参数数量相对很久之前的作品较大：

在算法上，我们注意到DQN用了两个网络：一个policy Q network用来算Q值，一个target Q network用来算目标Q值且周期性与policy Q network同步。文中解释用两个网络的原因是为了减少在计算TD Error时Bellman Equation两边的相关性。文中指出，$s_t$其实是四个连续image frames stack组成，这就使得$s_t$和$s_{t+1}$ 非常相似。在training早期，Q network其实并不能很好的区分$s_{t+1}$和$s_t$，如果在计算TD Error时都只用policy Q network，很容易产生错误的gradient，进而使得learning的目标(RHS of Bellman Equation)变得非常不稳定，致使training的过程也不稳定。一旦我们固定target Q network，learning的目标就会稳定，因为reward的存在，在学习过程中总会使得被更新后的policy Q network变得比target Q network更好。

另外，文中没有提到的是，在计算TD Error Loss的时候，作者使用的是smooth版的L2 Loss，也被称之为Huber Loss：

显然$\max \nabla_x L_\delta = 1$，使用huber loss会使DNN在learning中更加数值稳定。

第三，算法使用了RMS-prop optimiser来计算gradient。其目的在于，对gradient进行element-wise normalisation，使得在training过程中gradient不至于过大或者过小，而导致学习失败。

通过以上三点，我们注意到，DQN算法对稳定性要求极高，对超参特别敏感。原因是什么呢？我认为是RL学习样本的特殊性。在DNN普通分类任务的学习中，一般来说样本是均匀分布(Uniform Distribution)的，因此每个batch的样本都具有相当高的随机一致性，这也使得每一次计算的gradient都具有相当高的可信度；而RL的任务中，因为reward的稀疏性，在一个batch中，只有少数样本有reward信息(大部分reward为0)，甚至有些batch毫无reward信息，这就使得这个batch算出的gradient的可信度并不高，如果gradient过大，会直接让使用$\epsilon$-greedy采样的policy变得非常不稳定，采出的样本更差(含reward信息更少)，陷入恶性循环。我们将看到，针对RL的稀疏奖励(sparse reward)问题，诸多论文从不同角度给出了不同的解决方案。

在DQN算法中，我们使用Bellman Optimal Equation来计算TD Error:

在对$Q(s', a')$进行估算时，我们使用了DNN，这就意味着，$Q(s',a')$与其真实值存在偏差，且此偏差有正有负。因此，$\max_{a'} Q(s',a')$这一操作总会使得我们估算的偏差飘向正值。也就是说，在对$Q(s,a)$的估值时，我们总会存在高估(overestimation)。而这种高估是会累积的，最终会使得我们估算的$Q(s,a)$偏离真实值太多；又因为我们用DNN做estimator，过高的估值很容易造成gradient过大，导致更新后的policy变得非常不稳定，从而学习失败。

Double DQN

为了对抗这种高估，Double DQN使用如下公式：

相比于DQN算法中计算TD Error的公式：

double DQN在求optimal action时使用的是policy network，而据此action取optimal value时却使用的是target network。如果DNN对$Q(s',a')$估值的偏差是随机分布的话，两者同时高估的可能性就大大降低了，如此即可稍微对抗下高估问题。

Duelling DQN

Dueling DQN考虑从网路结构方面解决这一问题:

相对于DQN的网络，Dueling DQN的网络在结尾有两个stream，最后合并为一个head，对应的公式如下:

对应到上图中bottom的network，uppper stream是$V(s)$，bottom stream是$A(s, a)$。很明显，因为$A(s,a) \leq \max_{a'}A(s,a')$, 所以 $Q(s,a) \leq V(s)$，如此，相当于给$Q(s,a)$的估值增加了一个负向的偏移，以抵消$\max_{a'} Q(s', a')$带来的正向偏移。

Dueling DQN在实验中给出计算$Q(s,a)$ 的另一种形式的公式:

而且给出了基础attention map的解释：

如上图，作者认为，value stream和advantage stream的saliency map不同，代表两个stream分别attend到不同的content，从而实现更好的performance，对于这种sample based explanation，我只能持保留意见。不过，作者在文中给出的另一种解释倒是挺有意思：

Furthermore, the differences between Q-values for a given state are often very small relative to the magnitude of Q. For example, after training with DDQN on the game of Seaquest, the average action gap (the gap between the Q values of the best and the second best action in a given state) across visited states is roughly 0.04, whereas the average state value across those states is about 15. This difference in scales can lead to small amounts of noise in the up- dates can lead to reorderings of the actions, and thus make the nearly greedy policy switch abruptly.

主要是讲，Double DQN输出的$Q(a;s)$的action gap的平均值小到0.04（action gap是指中Q values的最大值和次大值之间的差值），而不同states之间value的平均差值大约为15。这两者的scale差别太大了，对应的noise scale也不一样。如DQN那般混在一起，state value的noise很容易淹没action gap，造成greedy policy的失效。采用Duelling DQN，policy其实只取决于advantage stream，如此即可避免state value的噪音的影响。

Prioritised Replay Memory

Prioritised Experience Replay这篇文章的思路很简单，文章针对的问题，还是RL的reward的稀疏性所带来loss不稳定性。我们回忆下Bellman Optimal Equation

因为reward的稀疏性，大部分的情况下$r(s,a)=0$，这种情况下DQN的TD error $\Delta =Q_\theta(s, a) - \gamma \max_{a'}Q_{\theta'}(s', a')$ 会较小；反之在$r(s, a) \neq 0$时DQN的TD error就会很大。如此plot出来的loss就会是这样：

相应的，loss较小的样本，对应的gradient就会小，对训练过程的贡献就不大，而这部分样本又占了replay中的多数，如果随机采样的话，就会拖慢学习速度。至此，文章的思路就呼之欲出了：

改变随机采样的策略，让样本被采样到的概率与其对应TD error正相关。

因为replay buffer的size都是million级别的，如果采用一般的sampling函数，会导致采样非常缓慢，作者给出的解决方案是使用segment tree。然而，如果cuda升级到了11.0之后，用GPU采样的话，就没有以上问题了。我们知道，在training早期，DNN给出的Q value approximation的error是很大的，这会让error较大的样本更容易被采样到，为了平衡这个问题，作者用一个参数$\alpha$来控制uniform sampling到prioritized sampling的过度：$P(i) = e_i^\alpha / \sum_k e_k^\alpha$，我们看到$\alpha = 0$时sampling是uniform，而$\alpha=1$时是prioritized；文中作者采用$\alpha = 0.5$做均衡。

另外，因为replay buffer的采样策略的改变，会使我们据此算出的$Q^\pi(s, a)$与其真实值有偏差，也就是说，我们从replay采样到的样本分布，与policy产生的样本的分布不相符。这就涉及到上一篇提到的importance sampling的概念了。为了对抗这种偏差，作者给每个样本一个weight：$w_i = (NP(i))^{-\beta}$；当$\beta = 1$时，较高概率被采样到的样本，会贡献较小的gradient；当$\beta = 0$时，相当于无视这种偏差。在文中，作者用一个linear annealing的scheduler让$\beta$在训练中从0.4降1.0，因为他认为前期这种偏差可以忽略不计，只有在后期这种偏差才会导致训练的不稳定性。

Deep Deterministic Policy Gradient

DQN及其变种主要针对的是discrete action space的情况。DDPG这篇文章则是相似的算法，针对continuous action space的情况的适应:

DDPG Algorithm:

1. Randomly initialize Q netowrk $Q_\theta(s, a)$ and policy network $\mu_\phi(s)$, and their copies $Q_{\theta'}, \mu_{\phi'}$ as target networks, an empty replay buffer $\mathcal{R}$, exploration noise level $\sigma$
2. For each episode:
   1. For each time-step $t$:

      1. Sample an action $a_t \sim \mathcal{N}(\mu_\phi(s_t), \sigma^2)$, get next state $s_{t+1}$, reward $r_t$, terminal flag $d_t$, push $<s_t, a_t, r_t, d_t, s_{t+1}>$ into replay $\mathcal{R}$

      2. Sample a batch of $N$ transitions $\{s_i, a_i, r_i, d_i, s_i'\}$, calculate:

         target Q value $q_i = r_i + \gamma (1-d_i)Q_{\theta'}(s_i', \mu_{\phi'}(s_i'))$

         critic loss $L(\theta)=N^{-1}\sum_i(Q_\theta(s_i, a_i)- q_i)^2$

         policy gradient: $\nabla_\phi J(\phi) = N^{-1}\sum_i \nabla_\phi Q_\theta(s_i,\mu_\phi(s_i))$

      3. Update Q network: $\theta \leftarrow \theta - \alpha \nabla_\theta L(\theta )$

         Update policy network: $\phi \leftarrow \phi + \beta \nabla_\phi J(\phi)$

         Update target networks:

         $$\theta' \leftarrow \tau\theta' + (1-\tau)\theta \\ \phi' \leftarrow \tau\phi' + (1-\tau)\phi$$

我们知道，DQN网络输出是长度为$|\mathcal{A}|$的vector，这个vector的每一个value即是对应action的Q value $Q(s, a)$；这显然对$|\mathcal{A}|=\infty$的continous action space无法实现，所以想到用分开的policy network和Q network是很自然的(其实最早的DQN的idea就是这样的)。文中的理论基础在Deterministic policy gradient有阐述，有兴趣可以自行了解，所谓的deterministic policy是相对于stochastic policy而言，其论证过程参考了Policy gradient for RL with function approximator，二者的根本区别在于：

In the stochastic case, the policy gradient integrates over both state and action spaces, whereas in the deterministic case it only integrates over the state space.

以数学形式表达这句话，deterministic policy的objective是

而stochastic policy的objective是

这里，deterministic policy $\mu_\phi(s)$给出的是action，而stochastic policy $\mu_\phi(s, a)$给出的是probability density。

我的理解，DDPG实际上是套用DQN和DPG的结合，Q network的更新很好理解，主要是理解DPG：

也就是说，我们调整policy network的参数$\phi$，使之输出的action $a = \mu_\phi(s)$能提升其对应的action value $Q(s, a)$。

Twin Delayed DDPG

TD3 是Double DQN的思路在DDPG上面的应用。我们前面提到，Double DQN主要解决的$Q(s,a)$的function approximation在计算bellman optimal equation时遇到的over-estimation的问题。那么在DDPG中，over-estimation是如何产生的呢？

我们在之前说过，policy gradient $\nabla_\phi J(\phi)$ 的调整方向总是会提升$Q(s, a)$，一个必然的结果是我们对$Q(s, \mu_\phi(s))$的估值会高于其真实值，也就是说$\mathbb{E}[Q^\mu(s, \mu_\phi(s))] \le \mathbb{E}[Q_\theta(s, \mu_\phi(s))]$，我们设$\Delta = \nabla_\phi J(\phi)$，那么当$\Delta \rightarrow 0$，总会有

为什么？因为当gradient足够小时，$\mathbb{E}[Q_\theta(s, \mu_{\phi+\Delta}(s))]$是local maximum。

确立了以上观点，那么解决方案也很简单了，我们来看TD3算法:

TD3 Algorithm:

1. Randomly initialise two Q network $Q_{\theta_1}(s, a), Q_{\theta_2}(s, a)$ and policy network $\mu_\phi(s)$, and their copies $Q_{\theta_1'}, Q_{\theta_2'},\mu_{\phi'}$ as target networks, an empty replay buffer $\mathcal{R}$, exploration noise level $\sigma$
2. For each episode:
   1. For each time-step $t$:

      1. Sample an action $a_t \sim \mathcal{N}(\mu_\phi(s_t), \sigma^2)$, get next state $s_{t+1}$, reward $r_t$, terminal flag $d_t$, push $<s_t, a_t, r_t, d_t, s_{t+1}>$ into replay $\mathcal{R}$

      2. Sample a batch of $N$ transitions $\{s_i, a_i, r_i, d_i, s_i'\}$, calculate:

         target Q1 value $q_{i, 1} = Q_{\theta_1'}(s_i', \mu_{\phi'}(s_i'))$

         target Q2 value $q_{i, 2} = Q_{\theta_2'}(s_i', \mu_{\phi'}(s_i'))$

         target Q value $q_i = r_i + \gamma (1 - d_i)\min(q_{i,1}, q_{i,2})$

         critic loss $L(\theta_1, \theta_2)=N^{-1}\sum_i((Q_{\theta_1}(s_i, a_i)- q_i)^2 + (Q_{\theta_2}(s_i, a_i)- q_i)^2)$

         policy gradient $\nabla_\phi J(\phi) = N^{-1}\sum_i \nabla_\phi Q_{\theta_1}(s_i,\mu_\phi(s_i))$

      3. update value networks:

         $$\theta_1 \leftarrow \theta_1 - \alpha \nabla_{\theta_1}L(\theta_1, \theta_2) \\ \theta_2 \leftarrow \theta_2 - \alpha \nabla_{\theta_2}L(\theta_1, \theta_2)$$

      4. if $t \bmod T = 0$:

         update policy network

         $$\phi \leftarrow \phi + \beta \nabla_\phi J(\phi )$$

         update target networks

         $$\theta_{1}' \leftarrow \tau\theta_{1}' + (1-\tau)\theta_1 \\ \theta_{2}' \leftarrow \tau\theta_{2}' + (1-\tau)\theta_2 \\ \phi' \leftarrow \tau\phi' + (1-\tau)\phi$$

我们看到，作者用了两个Q network来estimate target Q value，且取用Q值较小的那一个，以此减轻Q值被高估的问题。另外，作者降低policy network被更新的频率，以此来与twin value network更新同步。

文章idea虽然简单易懂，但是作者花了大量篇幅论证over estimation error的存在，有兴趣的读者可以仔细阅读。

Soft Actor Critic

Soft Actor Critic 这篇文章的核心思路在于

我们重点理解stochastic policy及entropy这两个概念。

我们前面提到的DDPG和TD3，其policy network输出的是fixed value，此所谓deterministic policy。而SAC的policy输出的却是一个概率分布，具体来讲，其policy network输出的是一个multivariate Gaussian distribution的mean和log standard derivation。如此则

我们设随机变量$x$的概率密度函数为$f(x)$，则其熵

我们将其代入SAC的目标函数，则有

要理解以上目标函数，就必须理解熵(entropy)的概念。

在热力学中，一个孤立系统熵衡量着其有序性：越混乱，平庸，低能态的系统，其熵越高；越有序，罕见，高能态的系统，其熵越低；所以熵的增加，代表着该系统从有序走向无序，从罕见走向平庸，从高能态走向低能态。热力学第二定律告诉我们，一个孤立系统的熵会自发增加，比如墨滴入水，火药爆炸，食物腐烂；熵增的过程，一般伴随着系统内部一些高能态物质释放能量转为低能态，从而使系统的平均温度得到提升。

熵这个概念被香农(Shannon Entropy)引到信息论中，则可以衡量一个分布的随机性。比如对于Bernoulli Distribution

其熵

在 $p = 0.5$ 时取最大值 $\log 2$，而在 $p=0$ 或 $p=1$ 时取最小值 $0$。

再比如，对Gaussian Distribution

显然方差越大的分布，其熵越大。我们回到SAC算法中，刚刚提到，policy network的输出是multivariate Gaussian distribution $\mathcal{N}$，我们假设每个variable互相独立，那么policy的熵无非是every single variable的Gaussian distribution的entropy的总和

我们看到SAC的目标函数的第一项与原始RL相同，而其第二项则是policy的entropy的期望值。所以SAC的目标函数想要表达的意思是，我们的policy要拿到更高的exptected total return的同时，其分布的方差也要更大才好。

更大方差的policy，代表着对噪音的robustness，代表着action可以更随机一点，代表着exploration可以更多一点。从RL的角度讲，这样的policy确实更好。

同理，我们有

结合我们之前介绍的TD3算法，我们给出以下SAC算法:

SAC Algorithm:

1. Randomly initialise two Q network $Q_{\theta_1}(s, a), Q_{\theta_2}(s, a)$ and policy network $\pi_\phi(s) =\mathcal{N}(\mu_\phi(s), \sigma_\phi(s))$, and Q network copies $Q_{\theta_1'}, Q_{\theta_2'}$ as target networks, an empty replay buffer $\mathcal{R}$, a learnable temperature $\alpha = 1$, target entropy $\hat{H}$
2. For each episode:
   1. For each timestep $t$:

      1. Sample an action $a_t \sim \pi_\phi(s_t)$, get next state $s_{t+1}$， reward  $r_t$, terminal flag $d_t$, push $<s_t, a_t, r_t, d_t, s_{t+1}>$ into replay $\mathcal{R}$

      2. Sample a batch of $N$ transitions $\{s_i, a_i, r_i, d_i, s_i'\}$, calculate:

         target actions $a_i' \sim \pi_\phi(s_i')$

         target Q1 value $\hat{q}_{i, 1} = Q{\theta_1'}(s_i', a_i')$

         target Q2 value $\hat{q}_{i, 2} = Q{\theta_2'}(s_i', a_i')$

         target Q value $\hat{q}_i = r_i + \gamma (1 - d_i)(\min(\hat{q}_{i,1}, \hat{q}_{i,2})- \alpha \log \pi\phi(s_i', a_i'))$

         critic loss $L(\theta_1, \theta_2)=N^{-1}\sum_i((Q_{\theta_1}(s_i, a_i)- \hat{q}_i)^2 + (Q_{\theta_2}(s_i, a_i)- \hat{q}_i)^2)$

         current resampled actions $\hat{a}_i \sim \pi\phi(s_i)$

         current Q1 value $q_{i, 1} = Q_{\theta_1}(s_i, \hat{a}_i)$

         current Q2 value $q_{i, 2} = Q_{\theta_2}(s_i, \hat{a}_i)$

         policy gradient $\nabla_\phi J(\phi) = N^{-1}\sum_i \nabla_\phi (\min(q_{i, 1}, q_{i, 2})-\alpha \log \pi_\phi(s_i, \hat{a}_i))$

         temperature gradient $\Delta_\alpha = \hat{H} + N^{-1}\sum_i \log \pi(s_i, a_i)$

      3. update value networks

         $$\theta_1 \leftarrow \theta_1 - \eta \nabla_{\theta_1}L(\theta_1, \theta_2) \\ \theta_2 \leftarrow \theta_2 - \eta \nabla_{\theta_2}L(\theta_1, \theta_2)$$

         update policy network $\phi \leftarrow \phi + \beta \nabla_\phi J(\phi )$

         update temperature $\alpha \leftarrow \alpha + \beta \Delta_\alpha$

         update target networks

         $$\theta_{1}' \leftarrow \tau\theta_{1}' + (1-\tau)\theta_1 \\ \theta_{2}' \leftarrow \tau\theta_{2}' + (1-\tau)\theta_2 \\$$

关于SAC的收敛性，其前作SQL中有更详细的论述，其实SAC与SQL的差别非常小，以至于SAC在ICLR被review时差点因为创新性不足被据掉，有兴趣的同学可以仔细拜读。

Proximal Policy Optimisation

PPO是online reinforcement learning的集大成(tricks)之作，该算法甚至被用来训练Dota2 AI。我们在第一篇的policy optimisation提到，加了importance sampling修正过后的Policy Gradient是

我们接下来会看到advantage function也可以被修正，我们称修正后的advantage function为Generalized Advantage Estimation。

我们设TD error $\delta_{t+k} = r(s_{t+k}, a_{t+k}) + \gamma V(s_{t+k+1}) - V(s_{t+k})$， 那么

一般我们会用NN做function estimator，所以如果用$A^{(0)}$来estimate advantage function，那么偏差(bias)会完全来自于NN；而如果用$A^{(\infty)}$来estimate的话，本质上是在用Monte Carlo法来estimate $Q(s_t,a_t)$，但是model free的RL中，$r(s_{t+k}, a_{t+k})$只能被sample一次，如此得到的estimation会非常不可靠(high variance)。那么如何平衡估算的误差和可靠性(bias variance tradeoff)呢？

GAE提出

显然，当$\lambda = 0$时，$\hat{A}(s_t, a_t) = A^{(1)}(s_t, a_t)$；当$\lambda = 1$时，$\hat{A}(s_t, a_t)=A^{(\infty)}(s_t, a_t)$；那么$\lambda$的取值，就平衡着bias和variance。

在PPO中，作者将importance sampling和GAE结合，给出以下目标函数：

在实践中，因为$r = \pi_\theta(s_t, a_t)/\pi_{\theta'}(s_t, a_t)$会波动过大，作者对其做clip，使得

亦或者

这么简单的idea，自然难登大雅之堂，作者又是如何把结果包装的那么好看，让大家接受的呢？

当然是用trick！在code中用，在paper中不提。然而这么火的算法，必然会被人锤。在这篇文章中，作者比较了PPO的code中使用的各种trick对实验结果的影响，结果却十分呵呵哒：相比于其他trick，PPO的ratio clip对结果的影响却是微乎其微的。

这种现象在DL界的文章中非常普遍，也十分遭人厌恶，甚至有劣币驱逐良币的趋势，非常令人失望。