策略梯度算法专题

本文为译文，感谢原作者Weng, Lilian无私的分享。文章原文地址为：https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html

摘要：在本文中，我们深入了解一下策略梯度算法、工作原理以及一些近年来新提出的改进算法，包含：朴素(vanilla)策略梯度、actor-critic、off-policy 策略梯度、A3C、A2C、DPG、DDPG、D4PG、MADDPG、TRPO、PPO、ACER、ACTKR、SAC、TD3以及SVPG。

什么是策略梯度

策略梯度是解决强化学习问题的一类方法。如果您对强化学习领域还不了解，可以先阅读这一篇博文《深入了解深度学习：核心概念》来了解一下基本问题定义以及一些核心概念。

符号

下表列出了一些符号说明，用于帮助更好地理解本文。

策略梯度

强化学习的目标是找到一个可以让执行代理(agent)获取最大收益的最优策略。而策略梯度算法着眼点在于直接对策略本身进行建模和优化。策略通常用一个带参数(通常用$\theta$表示)的函数来建模。而后，可以使用各种各样的算法来对参数$\theta$进行优化，以达到收益（目标函数）最大化的目标。

收益（目标）函数定义为：

其中$d^{\pi }(s)$为由${\pi }_{\theta }$决定的马尔可夫平稳分布(在策略$\pi$下，一个on-policy的状态分布)。为了简化，当策略${\pi }_{\theta }$被用作其它函数的下标(或上标)时，参数$\theta$通常会被省略。比如$d^{\pi },Q^{\pi }$应该指的是$d^{{\pi }_{\theta }},Q^{{\pi }_{\theta }}$。

想象一下，如果你可以持续永久遍历马尔可夫链中的所有状态，那么随着时间的推移，最终你停留在某个状态的概率是一定的，这就是策略${\pi }_{\theta }$的平稳性。$d^{\pi }(s)=\underset{t\to \mathrm{\infty }}{lim}P(s_t=s|s_0,{\pi }_{\theta })$是从初始状态$s_0$开始，在遵从策略${\pi }_{\theta }$的情况下，执行$t$步后，状态停留在$s$的概率。事实上，马尔可夫链的平稳性是$PageRank$算法能够工作的主要原因之一。如果你想了解更多，可以查看这里。

由于在连续空间下，行为或者状态的数量是无限的，基于值(value)的方法的计算代价太大了。举例来说，在一般策略迭代方法中，策略改进那一步$\arg \underset{a\in \mathcal{A}}{max}{Q}^{\pi }(s,a)$要求对行为空间进行遍历，这就导致了维度诅咒问题。自然而然地，我们会希望基于策略的方法在连续空间中会比策略迭代法更加有用。

根据目标函数的梯度${\mathrm{\nabla }}_{\theta }J(\theta )$，我们可以使用策略提升算法，将参数$\theta$往某个特定的方向移动，以使策略${\pi }_{\theta }$可以最大化最终收益。

策略梯度定理

计算梯度${\mathrm{\nabla }}_{\theta }J(\theta )$是比较棘手的。因为它不仅依赖于行为的选择(由策略${\pi }_{\theta }$决定)，而且依赖于状态分布的平稳性。而这个状态分布本身还由策略${\pi }_{\theta }$间接的决定。在给定一个未知环境的情况下，很难预测一次策略更新会对状态分布产生什么样的影响。

幸运的是，策略梯度定理出来拯救世界了！鼓掌！它给出了目标函数导数的另外一种简化形式，其中并不包含状态分布$d^{\pi }(\cdot )$。这大大简化了梯度${\mathrm{\nabla }}_{\theta }J(\theta )$的计算：

策略梯度定理的证明

本小节信息量较大，是时候来复习一遍证明过程了(Sutton & Barto, 2017，章节13.1)，这可以帮助我们了解为什么策略梯度定理是正确的。

我们从对状态价值函数求导开始：

因此，我们有：

这个等式有一个非常漂亮的递归形式（看红色部分！），未来状态的价值函数可以通过同样的形式展开。

考虑如下序列，我们使用${\rho }^{\pi }(s\to x,k)$表示在策略${\pi }_{\theta }$指导下，从状态$s$到状态$x$的$k$步转移概率。

我们有：

• $k=0$时，${\rho }^{\pi }(s\to s,k=0)=1$​
• $k=1$时，我们将能够转移到状态$s^{\prime }$所有可能的行为出现的概率相加得到：${\rho }^{\pi }(s\to s^{\prime },k=1)=\sum _a{\pi }_{\theta }(a|s)P(s^{\prime }|s,a)$​
• 假设我们的目标是依照策略${\pi }_{\theta }$，从状态$s$经过$k+1$步转移到状态$x$，那么我们可以先从状态$s$经过$k$步转移到状态$s^{\prime }$，然后再从状态$s^{\prime }$经过1步转移到状态$x$。通过此种递归的方式，我们拆分转移概率：${\rho }^{\pi }(s\to x,k+1)=\sum _{s^{\prime }}{\rho }^{\pi }(s\to s^{\prime },k){\rho }^{\pi }(s^{\prime }\to x,1)$​

回到前面，我们对价值函数的梯度${\mathrm{\nabla }}_{\theta }{V}^{\pi }(s)$​进行展开。为了简化表示，我们令$\varphi (s)=\sum _{a\in \mathcal{A}}{\mathrm{\nabla }}_{\theta }{\pi }_{\theta }(a|s)Q^{\pi }(s,a)$​。随着我们对价值函数梯度$\mathrm{\nabla }{V}_{\theta }(\cdot )$​的不断展开，我们可以发现：我们可以从起始状态$s$​开始，通过$t$​​步执行之后，转移到任意一个状态。${\mathrm{\nabla }}_{\theta }{V}^{\pi }$展开如下：

我们将价值函数梯度表示带入到目标函数的公式中，并整理可以得到：

上式中$\propto$表示正比于，在离散的情况下（episodic case），比例系数常量$\sum _s\eta (s)$大小为每一轮(episode)的平均长度。在连续情况下该常量为1（Suton & Barto, 2017;章节13.2）。我们将上面的梯度进一步整理为如下形式：

其中${\mathbb{E}}_{\pi }$表示${\mathbb{E}}_{s\sim d_{\pi },a\sim {\pi }_{\theta }}$​，也就是状态和行为分布都遵从策略${\pi }_{\theta }$(on-policy)。

策略梯度定理是许多策略梯度算法的理论基础。这种朴素的策略梯度更新方法是无偏的（bias），但是存在很大的方差（variance）。下面我们提到的许多算法都是为了在保证偏差不变的情况下降低方差而提出的。

这里列出策略梯度算法的一些常用的形式（论文GAE中给出的），这篇文章讨论了GAE中的一些组成部分，强烈推荐。

译著: GAE 这篇文章我们之前有介绍过，参考链接。

GAE 中策略梯度公式简介

策略梯度的公式，通常有如下形式：

其中，${\mathrm{\Psi }}_t$的形式可以是：

其中，值函数：

Q函数：

优势函数：

策略梯度算法

近年来大量梯度策略算法被提出来，本文不可能介绍所有的算法，这里仅介绍一些我偶然了解到并且读过的一些。

REINFORCE

REINFORCE(蒙特卡洛策略梯度)算法依赖于蒙特卡洛方法生成样本来估计期望收益，以更新策略的参数。由于使用蒙特卡洛方法得到的梯度在期望意义上与实际的梯度是相等的，因此REINFORCE可以正常工作：

我们可以通过实际采样得到的样本路径(sample trajectories)中来估计$G_t$，并使用$G_t$进行策略梯度的参数更新。该方法依赖于完整的样本路径，这也是为什么我们称它是蒙特卡洛方法的原因。

此方法工作过程非常直观：

1. 随机初始化策略参数$\theta$
2. 使用策略${\pi }_{\theta }$来生成一个样本路径:$S_1,A_1,R_2,S_2,A_2,\dots ,S_T$
3. For t = 1, 2, ... , T:
   1. 估计回报$G_t$的值
   2. 更新策略参数:$\theta \leftarrow \theta +\alpha {\gamma }^t{G}_t{\mathrm{\nabla }}_{\theta }\ln {\pi }_{\theta }(A_t|S_t)$

REINFORCE 算法的一个常用变体是将$G_t$减去一个基线值。这样做可以降低梯度估计的方差，并且可以保持偏差不变（记住：我们总是希望执行将$G_t$减去一个基线值这个动作）。举例来说，一个常用的方法就是使用行为价值(action value)函数减去状态价值(state value)函数，也就是使用优势函数$A(s,a)=Q(s,a)-V(s)$来进行参数更新。这篇文章很好地解释了为什么使用基线值可降低方差，其中还介绍了策略梯度算法的一些基础知识。

Actor-Critic

策略梯度中有两个重要组成部分：策略模型和价值函数。除了学习策略之外，学习价值函数也是非常有意义的，因为值函数可以协助梯度更新。举例来说，在朴素策略梯度算法中，我们使用状态价值函数作为基线值时可以降低梯度方差，这就是Actor-Critic所做的事。

Actor-Critic方法由两个模型组成，它们之间可能会共享参数：

• Critic更新价值函数的参数$w$，根据不同的算法，价值函数可以是行为价值函数$Q_w(a,s)$或者状态价值函数$V_w(s)$
• Actor负责更新策略${\pi }_{\theta }(a|s)$的参数$\theta$（使用cirtic指示的方向）

我们来看一下简单的基于行为价值函数的Actor-Critic算法的工作流程：

1. 随机初始化$s,\theta ,w$​；对行为进行采样$a\sim {\pi }_{\theta }(a|s)$
2. For t = 1, ..., T:
   1. 采样奖励$r_t\sim R(s,a)$​以及下一个状态$s^{\prime }\sim P(s^{\prime }|s,a)$​
   2. 采样下一个行为$a^{\prime }\sim {\pi }_{\theta }(a^{\prime }|s^{\prime })$
   3. 更新梯度参数：$\theta \leftarrow \theta +{\alpha }_{\theta }{Q}_w(s,a){\mathrm{\nabla }}_{\theta }\ln {\pi }_{\theta }(a|s)$
   4. 计算时刻$t$时的TD值：${\delta }_t=r_t+\gamma Q_w(s^{\prime },a^{\prime })-Q_w(s,a)$​
   5. 更新行为价值函数的参数：$w\leftarrow w+{\alpha }_w{\delta }_t{\mathrm{\nabla }}_w{Q}_w(s,a)$
   6. 更新行为与状态：$a\leftarrow a^{\prime },s\leftarrow s^{\prime }$

上面的流程中${\alpha }_{\theta }$和${\alpha }_w$是针对策略与价值函数分别预先设置的超参数。

Off-Policy 策略梯度

REINFORCE和actor-critic算法的原始版本都是on-policy的：训练样本都是根据目标策略(target policy)来收集的 （这里目标策略指的是我们正在优化的策略完全一样的策略）。Off-policy方法相比于on-policy的方法有几个优势：

1. off-policy方法不要求有一个完整的样本路径它可以重用之前采样得到的样本（经验回放），这样样本采样效率就非常高，数据使用效率也就非常高
2. 使用与目标策略不一样的行为策略(behavior policy)来进行采样可以更好的进行探索(exploration)

译著：这里behavior也翻译为了行为，文中我们将 action 也译为了行为，注意区分。

现在让我们看看off-policy的策略梯度是如何计算的。收集样本所用的行为策略是一个已知的策略，用符号$\beta (a|s)$表示。目标函数将行为策略生成的样本所得奖励进行求和：

其中$d^{\beta }(s)$是行为策略$\beta$的一个平稳分布，$d^{\beta }(s)=\underset{t\to \mathrm{\infty }}{lim}P(S_t=s|S_0,\beta )$​；$Q^{\pi }$是根据目标策略（而不是采样所用的行为策略）得到的行为价值函数的估计。

给定根据行为策略所得到的训练观测样本，我们将梯度的形式修改为：

上式中$\frac{{\pi }_{\theta }(a|s)}{\beta (a|s)}为$重要性权重。由于$Q^{\pi }$是目标策略的函数，所以$Q^{\pi }$也是策略参数$\theta$的函数。那么，根据乘法求导法则，我们也需要计算梯度${\mathrm{\nabla }}_{\theta }{Q}^{\pi }(s,a)$。但实际上，梯度${\mathrm{\nabla }}_{\theta }{Q}^{\pi }(s,a)$的计算极其困难。幸运的是，我们如果使用将${\mathrm{\nabla }}_{\theta }Q$部分忽略的近似梯度，仍然可以保证策略的改进，并且最终可以得到一个局部最优的策略。具体可以参考此处的证明。

简单总结，在off-policy的设定下使用策略梯度算法，我们仅需要对价值函数进行加权求和，权重就是目标策略与行为策略之比：$\frac{{\pi }_{\theta }(a|s)}{\beta (a|s)}$。

A3C

[论文|代码]

A3C (Asynchronous Advantage Actor-Critic)是一个经典的策略梯度算法，此算法重点关注并行训练。

在$A3C$中，由critics 学习价值函数，多个actors进行并行训练并且不断和全局参数进行同步。可以看出A3C是专门针对并行训练设计的。

以使用状态价值函数为例，如果我们使用MSE (均方误差)为loss函数:$J_v(w)=(G_t-V_w(s){)}^2$，那么我们可以使用梯度下降算法来找到最优参数$w$。这个状态价值函数也被用作策略梯度更新时的基线值。

算法基本步骤如下：

1. 设定全参数$\theta ,w$，以及特定线程的参数${\theta }^{\prime },w^{\prime }$
2. 初始化时间步数$t=1$
3. 当$T\le T_{MAX}$:
   1. 重置梯度值：$d\theta =0,dw=0$
   2. 线程相关参数使用全局参数进行同步：${\theta }^{\prime }=\theta ,w^{\prime }=w$
   3. 令$t_{start}=t$，并且对初始状态进行采样$s_t$
   4. 当$s_t$不是终止态并且$t-t_{start}\le t_{max}$:
      1. 选择一个行为$A_t\sim {\pi }_{{\theta }^{\prime }}(A_t|S_t)$，执行$A_t$得到新的奖励$R_t$和下一个状态$s_{t+1}$
      2. 更新$t=t+1,T=T+1$
   5. 计算最后状态的收益估计：
      1. $R=0$，如果$s_t$为终止态
      2. $R=V_{w^{\prime }}(s_t)$，如果$s_t$​为非终止态
   6. For$i=t-1,\dots ,t_{start}$:
      1. $R\leftarrow \gamma R+R_i$
      2. 计算${\theta }^{\prime }$累计梯度：$d\theta \leftarrow d\theta +{\mathrm{\nabla }}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(a_i|s_i)(R-V_{w^{\prime }}(s_i))$
      3. 计算$w^{\prime }$累计梯度：$dw\leftarrow dw+2(R-V_{w^{\prime }}(s_i)){\mathrm{\nabla }}_{w^{\prime }}(R-V_{w^{\prime }}(s_i))$
   7. 使用累计梯度$d\theta ,dw$更新参数$\theta ,w$

使用A3C可以使用多个执行代理(agent)来进行并行训练。梯度的累积可以看做是随机梯度更新算法中多个$minibatch$的聚合；$\theta ,w$的值每次会被不同的训练线程独立地进行微小的更新。

A2C

[论文|代码]

A2C是$A3C$的同步、确定性版本。这也是它为什么被命名为$A2C$的原因，它将$A3C$​中的第一个A (asynchronous) 省略了。在A3C中，每一个执行代理与全局参数独立地进行参数同步，这会导致在某同一时刻，不同的执行代理训练所用的参数的版本不一致，因此聚合后的参数可能不是最优的。为了解决这种不一致性，在A2C中，每一轮都会等待所有执行代理执行完毕后再进行梯度的聚合。这样下一轮开始时，所有的执行代理都会使用同样最新参数的策略。同步梯度更新方法让训练过程更加专注，并且一定程度上可以让加快收敛速度。

在openai的实验结果中，A2C表现出了更高GPU利用率；在使用大的batch size的时候，A2C可以工作的更好，并且可以取得与A3C同样甚至更优的性能表现。

下图展示了A3C和A2C基本结构差异的一个对比：

DPG

[论文]

在我们上述提到的方法中，所有的策略函数$\pi (\cdot |s)$​都被建模为一个在行为空间$\mathcal{A}$上的一个概率分布，因此这里的策略都是随机策略。在DPG(deterministic policy gradient)，也就是确定性策略梯度中，策略被建模为仅会输出一个确定性行为：$a=\mu (s)$。这看起来很奇怪，策略如果输出单个确定的行为，那么行为概率的梯度如何计算呢？下面我们一步步来看。

首先我们定义一些新的符号来帮助理解和讨论：

• ${\rho }_0(s)$: 状态初始分布
• ${\rho }^{\mu }(s\to s^{\prime },k)$: 从状态s开始，根据策略$\mu$来执行$k$步之后到达状态$s^{\prime }$的概率密度函数
• ${\rho }^{\mu }(s^{\prime })$： 带衰减系数的状态分布，定义为：${\rho }^{\mu }(s^{\prime })={\int }_{\mathcal{S}}\sum _{k=1}^{\mathrm{\infty }}{\gamma }^{k-1}{\rho }_0(s){\rho }^{\mu }(s\to s^{\prime },k)ds$

优化的目标函数为：

确定性策略梯度定理：现在是时候计算梯度了！根据链式法则，我们首先计算$Q$对$a$的梯度，然后计算确定性策略$\mu$对$\theta$的梯度：

我们可以将确定性策略看作是随机策略的一种特殊形式，也就是策略的概率分布仅在某一个行为$a$上有非零概率。实际上，在DPG的论文中，作者指出：如果对随机策略${\pi }_{{\mu }_{\theta },\sigma }$，通过确定性策略${\mu }_{\theta }$和一个随机变量$\sigma$进行重参数化(re-parameterize)，那么随机策略最终会在$\sigma =0$时与确定性策略等价。由于随机策略需要对整个状态和动作空间进行积分，我们可以预计它需要比确定性策略更多的样本。

确定性策略定理可以被应用到一般策略梯度算法的框架中。

我们以一个on-policy的actor-critic算法为例展示DPG的工作过程。在on-policy的actor-critic算法每一次迭代的过程中，策略输出的行为都是确定的，策略参数的更新方法如下：

由于DPG的策略所输出的行为都是确定的，在没有引入足够随机性的情况下，很难保证采样过程会进行足够的探索(exploration)。因此，要么我们在策略中引入随机噪声（实际上，这样确定性策略就变成不确定了）；要么我们可以使用off-policy方法通过使用一个不同的随机行为策略生成训练样本来进行训练。

假设在off-policy方法中，训练样本路径是通过一个随机策略$\beta (a|s)$生成的，此时状态分布遵从相应的带衰减的状态概率密度${\rho }^{\beta }$：

注意，由于策略是确定的，我们仅需要使用$Q^{\mu }(s,{\mu }_0(s))$而不是$\sum _a\pi (a|s)Q^{\pi }(s,a)$来作为状态$s$的奖励估计。在使用随机策略的off-policy方法中，重要性采样(importance sampling)经常被用于修正行为策略与目标策略不一致所带来的误差。而在确定性策略梯度算法中，我们无需对行为进行积分，因此我们无需进行重要性采样。

DDPG

[论文|代码]

DDPG(Lillicrap, et al., 2015)(Deep Deterministic Policy Gradient)是一个model-free、off-policy的actor-critic算法，它将DPG算法和DQN算法结合了起来。我们回顾一下，DQN(Deep Q-Network)通过经验回放(experience-replay)以及目标网络冻结来稳定$Q$函数的学习过程。原始的DQN工作在离散空间中，DDPG结合了actor-critic框架，将DQN扩展到连续空间上，并且用其学习一个确定性的策略。

为了更好的进行探索，我们通过给确定性策略${\mu }_{\theta }(s)$添加噪声$\mathcal{N}$来得到一个新的探索策略${\mu }^{\prime }$：

此外，DDPG对于actor和critic参数的更新都是软更新("保守的策略迭代")。软更新不会直接使用新策略的参数，而是将新旧策略进行加权求和，也就是在参数更新时，引入了一个参数$\tau \ll 1$，并使用该参数进行更新操作：${\theta }^{\prime }\leftarrow \tau \theta +(1-\tau ){\theta }^{\prime }$。使用此方法，可以限制目标网络的更新速度。这与DQN中的设计不一样，在DQN中目标网络会在一定的时间段内被冻结。

文中提到的一个细节在机器人技术中特别有用，它是关于如何对低纬度特征的不同的物理单元进行归一化的问题。举例来说：我们设计了一个模型，它以机器人的位置以及速度作为输入，并以此来学习某个策略；这些物理量在本质上是不同的，同种类型的数据对于不同的机器人来说变化量可能非常大。文中就引入了Batch normalization来解决此类问题。算法截图图下：

D4PG

[论文]

D4PG (Distributed Distributional DDPG)在DDPG的基础上进行了一系列的改进，来让DDPG可以以分布式的方式运行。改进点有：

(1)分布式Critic: critic 用于对Q的期望值进行估计，Q值被看作一个服从分布$Z_w$的一个随机变量，因此$Q_w(s,a)=\mathbb{E}{Z}_w(x,a)$。优化目标是最小化两个分布之间的距离—分布式TD误差:$L(w)=\mathbb{E}[d({\mathcal{T}}_{{\mu }_{\theta }},Z_{w^{\prime }}(s,a),Z_w(s,a)]$，其中${\mathcal{T}}_{{\mu }_{\theta }}$为贝尔曼操作子。

确定性策略梯度更新公式变为：

(2)N步回报: 在计算TD误差时，D4PG计算了N步的TD值，而不是单步，新的TD目标值为：

(3)多个分布式并行actors: D4PG利用K个独立的actors来并行采集样本，并将其存储到一个统一的重放缓冲区中。

(4)带优先级的经验回放 (Prioritized Experience Replay, PER): 修改的最后一部分是关于如何从重放缓冲区中进行采样的。PER并非使用均匀分布进行采样，不同的样本被采样的概率不一样。假设重放缓冲区大小为$R$，样本$i$的采样概率为$(R{p}_i{)}^{-1}$，也就是样本的重要性权值为$(R{p}_i{)}^{-1}$。

下面的论文截图展示了D4PG算法，论文中的一些变量表示方法与本文中使用的有一些差别；比如我们使用$\mu (\cdot )$来表示确定性策略而不是$\pi (\cdot )$。

MADDPG

[论文|代码]

多执行体DDPG (Multi-Agent DDPG, MADDPG)扩展了DDPG算法，以使其可以工作在一个新的环境中。在此环境中，多个执行体需要合作来完成某项任务，但是这些执行体仅能观测到执行体本地信息。在单个执行体的观察中，它看到的环境是非平稳的，这种非平稳性是由各个执行体策略不断更新而这些更新又不是全局可知所造成的。MADDPG是一个actor-critic模型，它被特别设计用于处理这种可以与多个执行体进行交互的、策略不断变化的环境。

前面提到的问题可以在MDP的多执行体(multi-agent)版本中进行形式化描述，它们通常被称为马尔可夫博弈(Markov games)。MADDPG就是针对部分可观察马尔可夫博弈问题提出的。假设我们一共有N个执行体，并且有一个状态集合$\mathcal{S}$。每个执行体$1,2,...,N$拥有各自行为的集合${\mathcal{A}}_1,\dots ,{\mathcal{A}}_N$，以及各自的观测状态集合${\mathcal{O}}_1,\dots ,{\mathcal{O}}_N$。定义状态转移函数包含所有执行体的状态、行为以及观测值空间：$\mathcal{T}:\mathcal{S}\times {\mathcal{A}}_1\times \dots {\mathcal{A}}_N\mapsto \mathcal{S}$。对于每一个执行体，它的策略仅会作用于它自己的观测空间上。如果策略是随机的，将其表示为：${\pi }_{{\theta }_i}:{\mathcal{O}}_i\times {\mathcal{A}}_i\mapsto [0,1]$；如果策略是确定性的，将其表示为：${\mu }_{{\theta }_i}:{\mathcal{O}}_i\mapsto {\mathcal{A}}_i$。

我们使用符号$\overrightarrow{o},\overrightarrow{\mu },\overrightarrow{\theta }$分别表示：$\overrightarrow{o}=o_1,\dots ,o_N,\overrightarrow{\mu }={\mu }_1,\dots ,{\mu }_N,\overrightarrow{\theta }={\theta }_1,\dots ,{\theta }_N$。

MADDPG中的critic是一个中心化的critic，这里的中心化指的是critic可以使用所有执行体的相关数据（比如：执行的动作、观测到的状态等）。每个执行体会学习一个自己的行为价值函数$Q_i^{\overrightarrow{\mu }}(\overrightarrow{o},a_1,\dots ,a_N)$，可以看到这里的$Q$的输入使用到了所有其它执行体相关的数据，其中$a_1\in {\mathcal{A}}_1,\dots ,a_N\in {\mathcal{A}}_N$是$N$个执行体所执行的动作。每个执行体的$Q_i^{\overrightarrow{\mu }}$函数都是独立进行训练学习的，它们奖励（rewards）的结构可能会出现任意的结构，包括它们可能会去竞争奖励。

每个执行体$i$也拥有一个actor，用于进行策略探索以及策略参数${\theta }_i$的更新。

Actor 的更新:

其中$D$是经验回放的存储缓冲，其中包含了许多轮所收集到的样本：$(\overrightarrow{o},a_1,\dots ,a_N,r_1,\dots ,r_N,{\overrightarrow{o}}^{\prime })$，该样本表示从当前的观测状态$\overrightarrow{o}$开始，每个执行体分别执行动作$a_1,\dots ,a_N$，并且获取得到了奖励$r_1,\dots ,r_N$, 最终进入到下一个状态${\overrightarrow{o}}^{\prime }$。

Critic 的更新：

其中${\overrightarrow{\mu }}^{\prime }$为确定性的目标策略，它使用软更新进行参数的更新。

如果在critic更新的时候，策略${\overrightarrow{\mu }}^{\prime }$还是未知的，我们可以让每一个执行体学习、演化出其它执行体策略的近似策略。使用这些近似策略，MADDPG仍然可以有效地进行训练学习（虽然可能不太精确）。

为了缓解不同执行体之间的竞争或者合作带来的高方差，MADDPG提出了引入一个新方法-策略集成 (policy ensembles):

1. 每个执行体训练K个策略
2. 每一轮随机选择一个策略公开
3. 使用K个策略集成的结果进行策略更新

总结一下，MADDPG在DDPG基础上添加了三个额外的部分来让算法可以被应用到多执行体环境中:

• 中心化的critic + 分布式的actor
• 某个执行体的actor需要有估计其它执行体策略的能力
• 使用策略集成来降低方差

下图为论文中MADDPG架构示意图：

TRPO

[论文|代码]

为了改进训练的稳定性，我们应该避免在单次更新时策略参数改动太大。TRPO (Trust region policy optimization)通过在每次迭代时对策略更新的大小使用KL散度来进行约束以实现这一想法。

考虑这样一个情形，当我们执行off-policy RL算法时，我们用于收集样本路径的策略$\beta$与我们所优化的目标策略是不一样的。Off-policy模型中的目标函数会对所采集样本的优势值(A = Q-V)进行计算求和，而目标策略的分布与我们生成样本所用的行为策略的分布是不一致的（存在差异，会定期同步）。为了解决这种不一致性带来的误差，TRPO会使用我们之前提到的重要性权重$\frac{{\pi }_{\theta }(a|s)}{\beta (a|s)}$对此误差进行修正。这样我们可以得到目标函数：

其中${\theta }_{old}$是梯度更新前的参数，其它符号含义与前文一致。注意这里我们使用了优势函数的估计${\hat{A}}_{{\theta }_{old}}$而不是优势函数本身，优势函数本身$A(\cdot )$是未知的。

在进行on-policy训练时，理论上说我们用于收集样本的策略与我们想要优化的目标策略是一样的。但是，在一个异步并行训练的环境下，我们采集样本所用的行为策略可能与我们的目标优化策略产生差异。TRPO考虑到了这个微小的差异：它将行为策略标记为${\pi }_{{\theta }_{\text{old}}}(a|s)$，这样优化的目标函数就变为：

为了保证新旧策略间的差异不会太大，TRPO使用KL散度来限制新旧策略分布之间的距离。因此目标函数$J(\theta )$优化时，需要满足如下限制：

其中$\delta$为超参，用于限制两个分布之间的距离，$D_{KL}$为KL散度的算子。在满足这个限制的条件下，TRPO可以在策略迭代的过程中，保证改进方向的单调性（持续改进，不会变坏）。

PPO

[论文|代码]

我们看到TRPO算法较为复杂，还需要进行KL散度的计算，本小节所介绍的PPO算法使用了一个简单的方法对TRPO进行了改进。PPO (Proximal Policy Optimization)中使用了一个简洁的、截断式的目标函数来达到与TRPO相似的性能表现。

首先，我们定义新旧策略比为：

这样，TRPO （on-policy）的目标函数变为：

如果不对${\theta }_{old}$与$\theta$之间的距离进行限制，对于$J^{TRPO}(\theta )$的优化很可能会导致参数的更新值非常大，进而导致训练极其不稳定。PPO中通过将比例$r(\theta )$的大小强制限制在1左右（准确来说限制在$[1-ϵ,1+ϵ]$之间,$ϵ$为一个超参数），来限制策略参数的变化量。那么截断式的优化目标函数为：

上式中 clip 函数，让比例$r(\theta )$不会大于$1+ϵ$，不会小于$1-ϵ$。PPO的目标函数会选择原始目标函数与clip之后的目标函数中的较小版本。这样优化器就不会盲目让参数往可以让当前样本的奖励变得非常大的方向去移动。

如果在使用PPO的时候，所设计的策略模型(actor)与价值模型(critic)共享了部分参数，那么除了使用上面的截断式目标函数之外，目标函数还可以添加价值函数的惩罚项和一个熵(entropy)的惩罚项:

其中，红色部分为价值函数的惩罚项，蓝色部分为熵惩罚项，$c_1,c_2$是用于调节的超参数。添加熵惩罚项的目的是保证足够的探索(exploration)。

PPO算法在许多基线任务上都进行过测试，被证明简洁高效。

在后续的论文[Hsu等人, 2020]中，PPO中的两个设计选择被重新审视了，也就是：(1) 用于策略正则化的截断式的比例$r(\theta )$和 (2) 使用连续高斯或者离散softmax分布对策略行为空间进行采样。该论文首先列出了PPO算法的三个失败的情况：

1. 在连续的行为空间下，标准的PPO算法在奖励超出所能支持的边界之后，会变得不稳定
2. 在离散的行为空间下，如果奖励非常稀疏并且在某些行为上的奖励非常高的时候，标准PPO算法会停留在局部最优的行为上
3. 在初始化数据接近局部最优解时，策略对于初始化非常敏感

文中提出了两个替换的设计方案来解决上述问题：

1. 为了解决高斯策略相关的问题1&3，文中提出将行为空间离散化或者使用Beta分布来帮助避免这些问题
2. 针对问题1&2，文中提出使用KL正则(和TRPO中一样)来作为替代模型

PPG

[论文|代码]

让策略网络与价值网络间共享参数(共享神经网络层)是一把双刃剑。这种方法虽然可以让策略网络与价值网络来共享学习到的特征，但是引起两个模型之间的竞争冲突。策略网络与价值网络对于同一参数的优化方向是不一致的。PPG (Phasic Policy Gradient)对于传统的on-policy的actor-critic算法（PPO）进行了修改，以使其可以将策略网络的训练与价值网络的训练分在不同的阶段中进行：

1. 策略阶段：使用PPO的目标函数$L^{\text{CLIP}}(\theta )$来优化策略网络
2. 辅助阶段：优化辅助目标函数。在论文中，值函数的误差是唯一的辅助目标，但是辅助目标函数也可以添加一些其它项

除了PPO中的$L^{CLIP}(\theta )$之外，文中还定义了两个目标函数：联合目标函数和辅助目标函数，公式如下：

其中${\beta }_{clone}$是一个超参数用于控制在辅助阶段允许策略更新的程度。算法如下：

其中：

• $N_{\pi }$为在策略阶段策略更新迭代的次数。
• $E_{\pi }$和$E_V$控制了样本重用的迭代次数(一个用于策略函数，一个用于价值函数)，这两个参数都是用于策略阶段的
• $E_{aux}$定义了在辅助阶段样本重用的次数；论文的实验使用的参数为：$E_{aux}=6,E_{\pi }=E_V=1$

PPG在采样效率上相对于PPO来说有很大改进，下图是PPG和PPO性能表现归一化之后的对比图，PPG看起来好多了。

ACER

ACER (Actor-Critic with Experience Replay), 是一个off-policy的actor-critic 模型，当然它也会使用经验重放来提高样本效率，降低数据相关性。A3C构成了ACER算法的基础，但A3C是on-policy的。ACER是A3C的一个off-policy的版本。让A3C由on-policy变为off-policy的一个主要障碍就是如何控制off-policy预测器的稳定性。ACER提出了三个设计来解决这个问题：

• 使用Retrace Q值估计
• 使用带偏差修正的截断式重要性权重
• 应用高效TRPO

Retrace Q值估计

Retrace是一个off-policy的Q值估计算法，它依赖于环境收益，对于目标策略以及行为策略$(\pi ,\beta )$的收敛性都有很好的保证，并且数据使用效率也不错。

我们回顾一下TD学习是如何用于预测的：

1. 计算TD误差：${\delta }_t=R_t+\gamma {\mathbb{E}}_{a\sim \pi }Q(S_{t+1},a)-Q(S_t,A_t)$；$r_t+\gamma {\mathbb{E}}_{a\sim \pi }Q(s_{t+1},a)$就是大家所熟知的TD目标(TD target)值。式中我们使用了期望符号${\mathbb{E}}_{a\sim \pi }$，这是因为对于未来收益我们能做的最好估计就是服从当前的策略$\pi$
2. 通过将价值函数往目标值移动来更新$Q$值：$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha {\delta }_t$。可以看到$Q$值的改变量与TD误差成正比：$\mathrm{\Delta }Q(S_t,A_t)=\alpha {\delta }_t$。

这个过程是off-policy的，我们需要对$Q$值的更新使用重要性采样：

重要性权重的乘积看起来非常可怕，因为它可能会引入巨大的方差。RetraceQ值估计方法对$\mathrm{\Delta }Q$进行了修改，对于重要性权重进行了截断：

ACER 使用$Q^{ret}$作为训练的目标值，并且使用L2 loss函数：$(Q^{\text{ret}}(s,a)-Q(s,a){)}^2$。

重要性权重截断

为了降低策略梯度$\hat{g}$的高方差，ACER对于重要性权重使用常量$c$进行了截断，并且在后面添加了一个修正项。符号${\hat{g}}_t^{acer}$是时刻$t$时ACER的策略梯度。