MADDPG 多智能体深度确定性策略梯度

论文链接：Counterfactual Multi-Agent Policy Gradients, AAAI 2017

代码链接：https://github.com/oxwhirl/pymarl

1. 引言

传统 RL 算法面临的一个主要问题是由于每个智能体都是在不断学习改进其策略，因此从每一个智能体的角度看，环境是一个动态不稳定的，这不符合传统 RL 收敛条件。并且在一定程度上，无法通过仅仅改变智能体自身的策略来适应动态不稳定的环境。由于环境的不稳定，将无法直接使用之前的经验回放等 DQN 的关键技巧。policy gradient 算法会由于智能体数量的变多使得本就有的方差大的问题加剧。

MADDPG 算法具有以下三点特征：

• 通过学习得到的最优策略，在应用时只利用局部信息就能给出最优动作。
• 不需要知道环境的动力学模型以及特殊的通信需求。
• 该算法不仅能用于合作环境，也能用于竞争环境。

MADDPG 算法具有以下三点技巧：

• 集中式训练，分布式执行

  训练时采用集中式训练 critic 与 actor，在训练阶段每个智能体的 Critic 网络会将所有智能体的观察及动作作为输入，而在执行阶段每个智能体的 Actor 网络仅将当前智能体的观察作为输入。

• 改进了经验回放记录的数据。为了能够适用于动态环境，每条样本由 $$(\mathbf{x}, \mathbf{x}', a_1, \cdots, a_n, r_1, \cdots, r_n)$$ 组成，其中 $\mathbf{x}=(o_1,\cdots ,o_n)$ 表示所有智能体的联合观测。

• 利用策略集合效果优化（policy ensemble）

对每个智能体学习多个策略，改进时利用所有策略的整体效果进行优化。以提高算法的稳定性以及鲁棒性。

其实 MADDPG 本质上还是一个 DPG 算法，针对每个智能体训练一个需要全局信息的 Critic 以及一个需要局部信息的 Actor，并且允许每个智能体有自己的奖励函数（reward function），因此可以用于合作任务或对抗任务。并且由于脱胎于 DPG 算法，因此动作空间可以是连续的。

2. 背景知识

2.1 DQN

DQN 的思想就是设计一个 $Q(s,a|\theta )$不断逼近真实的$Q(s,a)$函数。其中主要用到了两个技巧：

1. 经验回放。2. 目标网络。

该技巧主要用来打破数据之间联系，因为神经网络对数据的假设是独立同分布，而 MDP 过程的数据前后有关联。打破数据的联系可以更好地拟合 $Q(s,a)$ 函数。其代价函数为：

$$L(\theta )=E_{s,a,r,s^{\prime }}[(Q(s,a|\theta )-y{)}^2],\text{where}y=r+\gamma \underset{a^{\prime }}{max}\bar{Q}(s^{\prime },a^{\prime }|\bar{\theta })$$

其中 $Q(s^{\prime },a^{\prime }|\bar{\theta })$表示目标网络，其参数更新与$\theta$不同步（滞后）。

2.2 SPG（stochastic policy gradient）

SPG 算法不采用拟合 Q 函数的方式，而是直接优化累积回报来获得使回报最大的策略。假定参数化的策略为 ${\pi }_{\theta }(a|s)$，累积回报为$J(\theta )=E_{s\sim {\rho }^{\pi },a\sim {\pi }_{\theta }}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{r}_t]$。为了使$J(\theta )$最大化，直接对策略参数求导得到策略更新梯度：

$${\mathrm{\nabla }}_{\theta }J(\theta )=E_{s\sim {\rho }^{\pi },a\sim {\pi }_{\theta }}[{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a|s)Q^{\pi }(s,a)]$$

AC 算法也可以由此推出，如果按照 DQN 的方法拟合一个 $Q(s,a|\theta )$函数，则这个参数化的$Q(s,a|\theta )$函数被称为 Critic，${\pi }_{\theta }(a|s)$被称为 Actor。

2.3 DPG

上述两种算法都是针对随机策略，${\pi }_{\theta }(a|s)$是一个在状态 s 对于各个动作 a 的条件概率分布。DPG 针对确定性策略，${\mu }_{\theta }(s):S\to A$ 是一个状态空间到动作空间的映射。其思想与 SPG 相同，得到策略梯度公式为

$${\mathrm{\nabla }}_{\theta }J(\theta )=E_{s\sim \beta }[{\mathrm{\nabla }}_{\theta }{\mu }_{\theta }(s){\mathrm{\nabla }}_a{Q}^{\mu }(s,a){|}_{a={\mu }_{\theta }(s)}]$$

DPG 可以是使用 AC 的方法来估计一个 Q 函数，DDPG 就是借用了 DQN 经验回放与目标网络的技巧。

3. 研究痛点

1. 在多智能体问题中直接使用 DQN 算法时：

Independent Q-learning: 每个智能体都在随着训练而改变策略，导致整个环境的不稳定性。因此智能体存到 replay buffer 的经验都不能用。

-（1）对于每个智能体来说其身处的马尔可夫环境是非平稳的，而这会影响 Q 学习算法的收敛性。

-（2）另外 DQN 的经验回放技术的使用也将受到限制，因为当任意的 $\pi i\prime \ne \pi i$时有可能出现$P(s^{\prime }|s,a,{\pi }_1,...,{\pi }_N)\ne P(s^{\prime }|s,a,{\pi }_1^{\prime },...,{\pi }_N^{\prime })，$此时经验便不再有效，这也是由于马尔可夫环境的非平稳所导致的。

2. 策略梯度方法本来就面临高方差的问题，

-（1）而在多智能体环境中采用策略梯度方法将大大加剧其高方差的问题，因为此时每个智能体的 reward 不仅仅取决于当前智能体的动作，也取决于其他智能体的动作。 -（2）另外我们对策略梯度的采样估计方向也可能将随着智能体数量的增加而愈发不准确，具体如下。

4. MADDPG

4.1 多智能体 Actor Critic

MADDPG 采用集中式的学习，分布式的应用。因此我们允许使用一些额外的信息（全局信息）进行学习，只要在应用的时候使用局部信息进行决策就行。这点就是 Q-learning 的一个不足之处，Q-learning 在学习与应用时必须采用相同的信息。所以这里 MADDPG 对传统的 AC 算法进行了一个改进，Critic 扩展为可以利用其他智能体的策略进行学习，这点的进一步改进就是每个智能体对其他智能体的策略进行一个函数逼近。

环境的设置有较强的通用性：(1)每个智能体在实际执行时只使用 local observation；(2)不对环境建模；(3)不对智能体间的通信做显式建模。然而，既然在实际中不知道其他 agent 的信息，但是其他的 agent 的信息能够很好的帮助学习，很自然就会想：我们就在训练的时候使用这些信息，实际运用的时候的不用这些信息，那很自然就可以学习出一个更好的 agent 了。更进一步，我们想要在 offline 的时候利用更多的信息学习出一个拥有比较好 policy 的 agent，但是为了能够在实际的设置中使用，这个 agent 的 policy 的输入与输出在训练与实际使用的时候应该一样，所以无法直接把额外的信息直接结合在 policy 的输入中。那么有一种想法就是这些额外的信息既然无法直接用，那么就拿来做更准确的梯度的估计，那么很直观的想法就是用 Actor Critic 结构。

每一个智能体使用自己独立的 actor，通过自己观测状态 o，输出确定的动作 a，同时训练数据也只使用自己产生的训练数据，每一个 agent 同时也对应一个 critic，但是该 critic 同时接收所有 actor 产生的数据，本文将其当做中心化的 critic。这种中心化 critic 和普通的中心化 critic 不同的是，本文的 critic 存在 N 个（每个 agent 一个）。

我们用 $\theta =[{\theta }_1,\cdots ,{\theta }_n]$表示 n 个智能体策略的参数，$\pi =[{\pi }_1,\cdot ,{\pi }_n]$表示 n 个智能体的策略。针对第 i 个智能体的累积期望奖励$J({\theta }_i)=E_{s\sim {\rho }^{\pi },a_i\sim {\pi }_{{\theta }_i}}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{r}_{i,t}]$，针对随机策略，求策略梯度为：

$${\mathrm{\nabla }}_{{\theta }_i}J({\theta }_i)=E_{s\sim {\rho }^{\pi },a_i\sim {\pi }_i}[{\mathrm{\nabla }}_{{\theta }_i}\log {\pi }_i(a_i|o_i)Q_i^{\pi }(x,a_1,\cdots ,a_n)]$$

其中 $o_i$表示第 i 个智能体的观测，$x=[o_1,\cdots ,o_n]$表示观测向量，即状态。$Q_i^{\pi }(x,a_1,\cdots ,a_n)$表示第 i 个智能体集中式的状态-动作函数。由于是每个智能体独立学习自己的$Q_i^{\pi }$函数，因此每个智能体可以有不同的奖励函数（reward function），因此可以完成合作或竞争任务。

上述为随机策略梯度算法，下面我们拓展到确定性策略 ${\mu }_{{\theta }_i}$，梯度公式为

$${\mathrm{\nabla }}_{{\theta }_i}J\left({\mathit{\mu }}_i\right)={\mathbb{E}}_{\mathbf{x},a\sim \mathcal{D}}\left[{{\mathrm{\nabla }}_{{\theta }_i}{\mathit{\mu }}_i(a_i|o_i){\mathrm{\nabla }}_{a_i}{Q}_i^{\mathit{\mu }}(\mathbf{x},a_1,\dots ,a_N)|}_{a_i={\mathit{\mu }}_i}\left(o_i\right)\right]$$

由以上两个梯度公式可以看出该算法与 SPG 与 DPG 十分类似，就像是将单体直接扩展到多智能体。但其实 $Q_i^{\mu }$是一个非常厉害的技巧，针对每个智能体建立值函数，极大的解决了传统 RL 算法在 Multi-agent 领域的不足。D 是一个经验存储（experience replay buffer），元素组成为$(x,x^{\prime },a_1,\cdots ,a_n,r_1,\cdots ,r_n)$。集中式的 critic 的更新方法借鉴了 DQN 中 TD 与目标网络思想

$$L({\theta }_i)=E_{x,a,r,x^{\prime }}[(Q_i^{\mu }(x,a_1,\cdots ,a_n)-y{)}^2],\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{y}={\mathrm{r}}_{\mathrm{i}}+\gamma {\bar{\mathrm{Q}}}_{\mathrm{i}}^{{\mu }^{\prime }}({\mathrm{x}}^{\prime },{\mathrm{a}}_1^{\prime },\cdots ,{\mathrm{a}}_{\mathrm{n}}^{\prime }){|}_{{\mathrm{a}}_{\mathrm{j}}^{\prime }={\mu }_{\mathrm{j}}^{\prime }({\mathrm{o}}_{\mathrm{j}})}(1)$$

$Q_i^{{\mu }^{\prime }}$表示目标网络，${\mu }^{\prime }=[{\mu }_1^{\prime },\cdots ,{\mu }_n^{\prime }]$为目标策略具有滞后更新的参数${\theta }_j^{\prime }$。其他智能体的策略可以采用拟合逼近的方式得到，而不需要通信交互。

如上可以看出 critic 借用了全局信息学习，actor 只是用了局部观测信息。MADDPG 的一个启发就是，如果我们知道所有的智能体的动作，那么环境就是稳定的，就算策略在不断更新环境也是恒定的，因为模型动力学是稳定的：

$$P(s^{\prime }|s,a_1,\cdots ,a_n,{\pi }_1,\cdots ,{\pi }_n)=P(s^{\prime }|s,a_1,\cdots ,a_n)=P(s^{\prime }|s,a_1,\cdots ,a_n,{\pi }_1^{\prime },\cdots ,{\pi }_n^{\prime })$$

Actor Critic 的策略梯度公式为：

$${\mathrm{\nabla }}_{{\theta }_i}J\left({\theta }_i\right)=E_{s\sim p^u,a_i\sim {\pi }_i}[{\mathrm{\nabla }}_{{\theta }_i}\log {\pi }_i(a_i|o_i)Q_i^{\pi }(o_i,a_i)]$$

推广到多智能体设置下，Actor Critic 的策略梯度公式则为：

$${\mathrm{\nabla }}_{{\theta }_i}J\left({\theta }_i\right)={\mathbb{E}}_{s\sim p^{\mu },a_i\sim {\pi }_i}[{\mathrm{\nabla }}_{{\theta }_i}\log {\pi }_i(a_i|o_i)Q_i^{\pi }(\mathrm{x},a_1,\dots ,a_N)]$$

推广到 MADDPG 下，即输出确定性动作，则策略梯度公式为：

$${\mathrm{\nabla }}_{{\theta }_i}J\left({\mathit{\mu }}_i\right)={\mathbb{E}}_{\mathbf{x},a\sim \mathcal{D}}\left[{{\mathrm{\nabla }}_{{\theta }_i}{\mathit{\mu }}_i(a_i|o_i){\mathrm{\nabla }}_{a_i}{Q}_i^{\mathit{\mu }}(\mathbf{x},a_1,\dots ,a_N)|}_{a_i={\mathit{\mu }}_i}\left(o_i\right)\right]$$

其中$i$为 agent，$\mathit{\mu }$为策略。Critic 的更新为：

$$\mathcal{L}\left({\theta }_i\right)={\mathbb{E}}_{\mathbf{x},a,r,{\mathbf{x}}^{\prime }}\left[{(Q_i^{\mu }(\mathbf{x},a_1,\dots ,a_N)-y)}^2\right],y=r_i+{\gamma Q_i^{{\mu }^{\prime }}({\mathbf{x}}^{\prime },a_1^{\prime },\dots ,a_N^{\prime })|}_{a_j^{\prime }={\mathit{\mu }}_j^{\prime }\left(o_j\right)}$$

其中${\mathit{\mu }}^{\mathbf{\prime }}$为 target network 策略。

4.2 估计其他智能体策略

知道其他 agent 的策略这个假设过于强，所以这里提出弱化该假设的方法：知道对手的 action，不知道对手的 policy。然后通过别人的 observation 和 action 来估计出别人的 policy。所以可以采用极大似然估计来估计 policy，另外加上一个 entropy 增加 policy 的不确定性：

$$\mathcal{L}\left({\varphi }_i^j\right)=-{\mathbb{E}}_{o_j,a_j}[\log {\hat{\mathit{\mu }}}_i^j(a_j|o_j)+\lambda H\left({\hat{\mathit{\mu }}}_i^j\right)]$$

使用这个估计出的别人的策略来更新 Critic：

$$\hat{y}=r_i+\gamma Q_i^{{\mathit{\mu }}^{\prime }}({\mathbf{x}}^{\prime },{\hat{\mathit{\mu }}}_i^{\prime 1}\left(o_1\right),\dots ,{\mathit{\mu }}_i^{\prime }\left(o_i\right),\dots ,{\hat{\mathit{\mu }}}_i^{\prime N}\left(o_N\right))$$

4.3 策略集合优化（policies ensemble）

很多时候 agent 使用的策略只对当前的其他 agent 使用的策略有效，一旦其他 agent 稍微变化效果就变差，所以在这里我们对每个 agent 都训练$k$个不同的策略，然后在每次训练的时候就在这个策略集中随机挑选一个，那么这样就有可能能够学出$k$个不同的策略，但是在实际运用中，我们只使用一个 policy，所以我们可以利用这$k$个策略来做权衡，学习出一个总的策略。

这个技巧也是本文的一个亮点。多智能体强化学习一个顽固的问题是由于每个智能体的策略都在更新迭代导致环境针对一个特定的智能体是动态不稳定的。这种情况在竞争任务下尤其严重，经常会出现一个智能体针对其竞争对手过拟合出一个强策略。但是这个强策略是非常脆弱的，也是我们希望得到的，因为随着竞争对手策略的更新改变，这个强策略很难去适应新的对手策略。

对于每个 sub policy 单独采用 MADDPG 学习：

$$J_e\left({\mathit{\mu }}_i\right)={\mathbb{E}}_{k\sim \mathrm{unif}(1,K),s\sim p^{\mu },a\sim {\mathit{\mu }}_i^{(k)}}[R_i(s,a)]$$

因此策略梯度公式变为：

$${\mathrm{\nabla }}_{{\theta }_i^{(k)}}{J}_e\left({\mathit{\mu }}_i\right)=\frac{1}{K}{\mathbb{E}}_{\mathbf{x},a\sim {\mathcal{D}}_i^{(k)}}\left[{{\mathrm{\nabla }}_{{\theta }_i^{(k)}}{\mathit{\mu }}_i^{(k)}(a_i|o_i){\mathrm{\nabla }}_{a_i}{Q}^{{\mathit{\mu }}_i}(\mathbf{x},a_1,\dots ,a_N)|}_{a_i={\mathit{\mu }}_i^{(k)}}\left(o_i\right)\right]$$

4.4 MADDPG 算法流程如图：

5. 实验内容

在多个环境上打败了 DDPG、DQN 等 Independent learning 方法。

6. 缺点

• 每一个 Critic 需要观测到所有的 agent 的状态和动作，对于大量不确定 agent 的场景，不是特别实用
• 当 agent 数量特别多的时候，状态空间太过于巨大
• 每一个 agent 都对应了一个 actor 和一个 critic，数量多的时候，存在大量的模型。

7. 优点

• 对于集中训练分步执行的方法是一种完善
• 是多智能体环境下的开创性工作。