对一些概念的理解

  1. 评估动作的价值，我们称为Q值：它代表了智能体选择这个动作后，一直到最终状态奖励总和的期望。Q值与环境的状态转移概率有很大关系，这个状态转移概率是不变的。

  2. 评估状态的价值，我们称为V值：它代表了智能体在当前状态之下，一直到最终状态奖励总和的期望。V值和我们选择的策略有很大的关系；例如当策略是平均选择两个奖励分别为10和20的动作时，得到的V值为15，但是以40%和60%的概率进行选择，得到的V值就是16。

  3. Q值和V值的关系：一个状态的V值，就是这个状态下的所有动作的Q值，在特定策略下的期望。类似的，Q值也是所有对应状态V值的期望，加上转移到新状态时获得的奖励。公式如下：
    $$
    \begin{align}
    v_\pi(s)&=\sum_{a\in A}\pi(a|s)q_\pi(s,a)\\
    q_\pi(s,a)&=R^a_s+\gamma\sum_{s^\prime\in S}P^a_{ss^\prime}v_\pi(s^\prime)\\
    v_\pi(s)&=\sum_{a\in A}\pi(a|s)\left(R^a_s+\gamma\sum_{s^\prime\in S}P^a_{ss^\prime}v_\pi(s^\prime)\right)
    \end{align}
    $$
    其中$s$代表状态，$a$代表动作，$v$代表V值，$q$代表Q值，$\pi$代表策略，$\gamma$代表折扣率，$R$代表奖励，$P$代表状态转移概率。

  4. 蒙特卡洛(MC)会让智能体从某个状态$S$出发，直到最终状态，然后回过头来给每个节点标记这次的价值$G$，其代表某次过程中，智能体在这个节点的价值。经过多次过程后，把每个状态的$G$值进行平均，这就是状态的V值。但是为了更好估计V值，需要对平均进行一些优化：$\overline{V(s_t)}\leftarrow\overline{V(s_t)}+\alpha\left(G_t-\overline{V(s_t)}\right)$。时序差分(TD)是一步一回头，用下一步的估值，估算当前状态的估值：$\overline{V(s_t)}\leftarrow\overline{V(s_t)}+\alpha\left(R_{t+1}+\gamma V(s_{t+1})-\overline{V(s_t)}\right)$。

  5. 人们试图使用下一个动作的Q值来代替V值，因为从状态$s_{t+1}$到动作$a_{t+1}$之间没有奖励反馈。但是有一个问题————现实中一般不是马尔科夫链，而是马尔科夫树，一个状态可能有很多动作，因此人们假定有个可能的动作产生的Q值能够一定程度上代表$V(s_{t+1})$。

    • 在相同策略下产生的动作$a_{t+1}$。这就是SARSA。
    • 选择能够产生最大Q值的动作$a_{t+1}$。这就是Q-learning。

  6. DQN和Q-learning并没有根本的区别。只是DQN用神经网络，也就是一个万能函数替代了原来Q-table而已，这样就实现了对连续状态的处理，不再只能处理离散状态。可以理解为一种时序差分(TD)+神经网络(NN)的方法。

  7. Policy Gradient(策略梯度，PG)相比DQN等算法的区别在于其抛弃了对于Q值和V值的计算，改用神经网络学习一个映射$f(s)=a$，根据$G$值利用带权重的梯度下降方法来调整策略中不同动作的概率，在代码实现中$G$值变成了参数调整的权值，$G$值越大，参数调整的幅度越大。相比于DQN算法，PG算法可以理解为一种蒙特卡洛(MC)+神经网络(NN)的方法。举一个简单的例子，比如：假设一个智能体从某个state出发，可以采取三个动作，最开始采用平均策略，各有33%的概率。第一次出发选择动作A，到达最终状态后开始回溯，计算得到G=1。然后就要更新策略：让A的概率提升，相对地，BC的概率就会降低，变为50%，25%，25%。第二次出发选中B动作，到达最终状态后开始回溯，计算得到G=-1。因此要少选择B，再次更新策略，变为55%，15%，30%。第三次出发选中C动作，到达最终状态后开始回溯，计算得到G=5。那么要求选择C的概率大大提高，变为20%，5%，75%。

  8. Actor-Critic(AC)具有两个网络：一个输入状态S，输出策略，负责选择动作，我们把这个网络称为Actor；一个负责计算每个动作的分数，我们把这个网络称为Critic。相对来说有些类似于对抗神经网络GAN，Actor负责选择(generator负责生成)，Critic负责批判(discriminator负责判别)。总的来说，AC可以被理解为TD版本的PG(TD相对于MC的改进就在于不必完成整个游戏过程，直到最终状态，才能通过回溯计算G值，大大提高了效率)。

  9. 有一些文章将AC描述为PG+DQN，这是可以理解的，但是有一点值得注意：在DQN预估的是Q值，在AC中的Critic估算的是V值。之所以Critic对动作进行评价却不使用Q值，而使用V值是因为特殊原因，我们举个例子进行说明：假设对于一个状态s,其动作可以为a1，a2，a3，三个动作的Q值分别为1,2,10。假设一开始采取的是平均策略，各有33%的概率，选择了动作a1，得到Q值为1。那么使用带权重的梯度下降算法更新策略的时候会倾向于增大选择a1的概率，这可能会导致选择a1的概率持续增大，掉入正数陷阱(本来应该是a3的概率最大，但是很不幸的是一次都没有抽到a3，因为采样次数不能无限，所以这种情况是可能发生的)。要解决这个问题，我们可以通过减去一个baseline，令Actor权重有正有负来实现。而通常这个baseline，我们选取的是权重的期望，而Q值的期望(均值)就是V值。因此，Critic对选择的动作进行评价时要使用V值。

  10. 根据9中的内容，我们可以得到更新的权重：$Q(s,a)-V(s)$，但是用两个网络分别计算Q和V太过冗余，因此将$Q(s,a)$用$\gamma V(s^\prime)+R$代替，得到新的权重TD-error$=\gamma V(s^\prime)+R-V(s)$。接着用Critic将TD-error尽量减小(TD-error作为Critic网络的loss)，然后将TD-error作为Actor更新策略时，带权重更新中的权重值。示意图如下所示：

    AC

DPG

DPG(Deterministic Policy Gradient)从理论的角度提出了一种deterministic、off-policy的policy gradient算法，并给出了policy gradient的计算公式和参数更新方法。在其基础上演化出了DDPG、D4PG等经典算法。

DPG针对连续动作空间的控制任务在传统的PG算法上做了改进，将策略函数的输出从一个分布(常用高斯分布)转变为一个唯一确定的动作；同时引入了AC框架，直接利用Critic(Q函数)找到可能的最优决策，然后用找到的最优决策来实现Actor中的策略优化(注意：正常来说AC框架应该使用V函数，但是因为DPG需要对动作求导，因此将V函数转换成了Q函数)；最后使用off-policy策略解决了探索不足的问题。

以往的PG工作中，大多数都采用随机策略，比如说PPO，它在面对连续的动作空间时，将输出一个高斯分布的均值$\mu$和方差$\sigma^2$，并利用这个高斯分布进行采样，每一次输出的动作将不同。但是DPG采用的是确定性策略输出，也就是说当面对同一个状态时，算法会输出相同的动作。

相比于随机策略，确定性策略的优劣都是显而易见的：

  • 优点：从理论上可以证明，确定性策略的梯度就是Q函数梯度的期望，这使得确定性方法在计算上比随机性方法更高效；
  • 缺点：对于每个状态，下一步的动作是确定的，这就导致只能做开发而不能做探索，有违exploitation-exploration trade-off。为了解决这个问题，DPG采用了off-policy的方法。也就是说，采样的policy和待优化的policy是不同的：其中采样的策略是随机的，而待优化的策略是确定性的。采样策略的随机性保证了充分的exploration。

整篇论文中的公式推导占据了绝大部分，本文不再赘述，只列出最重要的结论，并将其与随机策略进行对比：

  • 随机策略：在状态St时，每次采取的动作很可能不一样，随机选择动作，$\pi(a|s)=P(a|s)$
    $$
    \begin{align}
    \nabla_\theta J(\pi_\theta)&=\int_{\mathcal{S}}\rho^{\pi}(s)\int_{\mathcal{A}}\nabla_{\theta}\pi_{\theta}(a|s)Q^{\pi}(s,a)\mathrm{d}a\mathrm{d}s \\
    &=\mathbb{E}_{s\sim\rho^\pi,a\sim\pi_\theta}[\nabla_\theta\log\pi_\theta(a|s)Q^\pi(s,a)]
    \end{align}
    $$

  • 确定性策略：在状态St时，每次采取的动作都是一个确定的action，$a=\mu(s)$
    $$
    \begin{align}
    \nabla_\theta J(\mu_\theta)& =\int_{\cal S}\rho^{\mu}(s)\nabla_{\theta}\mu_{\theta}(s)\left.\nabla_{a}Q^{\mu}(s,a)\right|_{a=\mu_{\theta}(s)}\mathrm{d}s \\
    &=\mathbb{E}_{s\sim\rho^\mu}\left[\nabla_\theta\mu_\theta(s)\nabla_a Q^\mu(s,a)|_{a=\mu_\theta(s)}\right]
    \end{align}
    $$
    简单解释一句，公式的含义是：期望回报对待优化策略$\mu$的梯度，可以视作在随机采样策略$\rho$下，Q函数对$\mu$的梯度的期望。两者对比，显然确定性策略中减少了对于动作action的积分，这使得它更容易训练。

具体来说基于DPG思想的算法都分为寻找最优决策和优化当前策略两个阶段。在寻找最优决策阶段中，固定$Q(s,a)$函数的输入状态$s_t$，不断调整输入动作$a$，直到Q函数的输出值最大，这时的$a$即为最优决策$a^{*}$。在优化当前策略阶段中，让Actor的确定性策略$\mu(s)=a$模仿前面Critic找到的最优决策$a^{*}$。不过这次策略调整只改变了智能体在$s_t$这单个状态下的决策，接下来还需要将整个状态空间$S$中所有的状态的策略调整到最优，就可以得到最优策略$\mu^{*}$。

总的来说，这篇论文提出了一个理论基础，告诉我们使用off-policy方法，在采样时采用随机策略，待优化策略则采用确定性的策略在理论上是可行的，至于具体的实现方式则由DDPG这篇论文的工作进行探索。

SAC

首先回顾一下PPO类算法和DPG类算法。

DPG类算法前面已经进行了说明。

PPO算法的目标是在PG算法的优化过程中，使性能单调上升，并且使上升的幅度尽量大。PPO同样使用了AC框架，不过相比DPG更加接近传统的PG算法，采用的是随机的策略函数(Stochastic Policy)，智能体每次决策时都要从策略函数输出的分布中采样，得到的样本作为最终执行的动作，因此天生具备探索环境的能力，不需要为了探索环境给决策加上扰动；PPO的重心会放到actor上，仅仅将critic当做一个预测状态好坏(在该状态获得的期望收益)的工具，策略的调整基准在于获取的收益，不是critic的导数。对比DPG思想，PPO中的Actor不再是确定性策略$\mu(s)=a$，而是服从概率分布的随机策略$a\sim\pi_\theta(\cdot|s)$；Critic中也不再是让Q函数对动作求导，因此还原为使用V函数(状态到实数的映射，输入空间减少了动作，大大简化了值函数)。除此之外，PPO还使用了importance sampling、GAE、batch training、replay buffer等技巧，以及严格约束策略参数的更新速度，使策略的表现尽量单调上升。

PPO是sample inefficiency的，DDPG又对各种超参数十分敏感。因此基于最大熵(maximum entropy)的SAC算法出现了，它是一个随机策略的、off-policy的、基于AC框架的算法，其在优化策略以获取更高累计收益的同时，也会最大化策略的熵。将熵引入RL算法的好处在于可以让策略尽可能随机，智能体可以更充分地探索状态空间$S$，避免策略早早地落入局部最优点，并且可以探索到多个可行方案来完成指定任务，提高抗干扰能力。

下面来介绍SAC算法做了哪些改进：

  1. 最大化熵强化学习。最大化熵强化学习(MERL)算法的目标策略是：$\pi^{*}_{MaxEnt}=argmax_\pi\sum_t\mathbb{E}_{(s_t,a_t)\sim\rho_\pi}\left[R(s_t,a_t)+\alpha H(\pi(\cdot|s_t))\right]$，其中$R$是收益项，$H$是熵值项。此目标使得策略在最大化累计收益的同时，还能够最大化策略的熵值，借此让策略随机化，即输出的每一个action的概率尽可能分散，而不是集中在一个action上。对比DDPG的deterministic policy的做法，看到一个好的就捡起来，差一点的就不要了，而最大熵是都要捡起来，都要考虑。

  2. Soft Value Function。与一般RL类似，MERL也有自己的值函数，可以用于评价策略的好坏，这些公式都和一般RL中的公式类似：
    $$
    \begin{aligned}
    Q_{soft}^{\pi}(s,a)&=\mathbb{E}_{s_t,a_t\sim\rho_\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r\left(s_t,a_t\right)+\alpha\sum_{t=1}^{\infty}\gamma^{t}H\left(\pi\left(\cdot|s_{t}\right)\right)|s_0=s,a_0=a\right]\\
    V_{soft}^{\pi}(s)&=\mathbb{E}_{s_t,a_t\sim\rho_\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\left(r\left(s_t,a_t\right)+\alpha H\left(\pi\left(\cdot|s_{t}\right)\right)\right)|s_0=s\right]\\
    Q_{soft}^{\pi}(s,a)&=\underset{s^{\prime}\sim p(s^{\prime}|s,a)}{\mathbb{E}}\left[r\left(s,a\right)+\gamma V_{s o f t}^{\pi}\left(s^{\prime}\right)\right]\\
    V_{soft}^{\pi}(s)&=\underset{a\sim\pi}{\mathbb E}\left[Q_{soft}^{\pi}(s,a)-\alpha\log\pi(a|s)\right]
    \end{aligned}
    $$

  3. Energy Based Policy。由于基于能量的模型在面对多模态的值函数时，具有更强的策略表达能力，而一般的高斯分布只能将决策集中在Q值更高的部分，忽略其他次优解，MERL采用了基于能量的模型而非高斯分布来表示策略：
    $$
    \pi\left(a_t|s_t\right)\propto\exp\left(\frac{1}{\alpha}Q_{soft}\left(s_t,a_t\right)\right)
    $$

  4. Soft Policy Iteration。与一般的policy iteration类似，我们可以得到soft policy iteration的迭代方式：首先进行evaluation，固定policy，使用Bellman方程更新Q值直到收敛；接着进行improvement，更新policy。公式如下：
    $$
    \begin{align}
    Q^{\pi}_{soft}(s_t,a_t)&=r(s_t,a_t)+\lambda \mathbb{E}_{s_{t+1},a_{t+1}}[Q^{\pi}_{soft}(s_{t+1},a_{t+1})-\alpha\log(\pi(a_{t+1}|s_{t+1}))]\\
    \pi^\prime&=\arg\min_{\pi_k\in\Pi}D_{KL}(\pi_k(\cdot|s_t)||\frac{\exp(\frac{1}{\alpha}Q_{soft}^\pi(s_t,\cdot))}{Z_{soft}^\pi(s_t)})
    \end{align}
    $$

  5. Soft Actor-Critic。基于上述内容，我们可以得到SAC算法中Q、Policy各自的更新公式:
    $$
    \begin{align}
    J_Q(\theta)&=\mathbb{E}_{(s_t,a_t,s_{t+1})\sim\mathcal{D},a_{t+1}\sim\pi_{\phi}}[\frac{1}{2}(Q_t(s_t,a_t)-(r(s_t,a_t)+\gamma(Q_{\bar{\theta}}(s_{t+1},a_{t+1})-\alpha\log(\pi_\phi(a_{t+1}|s_{t+1})))))^2]\\
    J_\pi(\phi)&=\mathbb{E}_{s_{t}\sim\mathcal{D},\varepsilon\sim\mathcal{N}}[\alpha\log\pi_{\phi}(f_{\phi}(\varepsilon_{t};s_{t})|s_{t})-Q_{\theta}(s_{t},f_{\phi}(\varepsilon_{t};s_{t}))]
    \end{align}
    $$

最终我们得到了SAC算法如下图所示：

SAC