QTRAN 多智能体值分解

论文链接：QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning, ICML 2019

代码：https://github.com/Sonkyunghwan/QTRAN

VDN 和 QMIX 都是值分解领域的两大标杆性文章，VDN 将联合动作价值函数分解为单个动作价值函数的和。QMIX 扩展了这种可加性的值函数，进行因子分解，将联合作用价值函数表示为单调函数，而不是仅仅为加和，从而实现了环境的更进一步扩展。

值分解其实就是在保证联合动作取 argmax 的时候能够是对各个智能体的值函数取 argmax。VDN 中采用的是线性求和的方式，QMIX 中采用的是保证单调性。对于一些任务，比如像联合动作的最优就是各个智能体的单独的最优的值函数，这样的问题可以采用这种方式，对于不是这类型的问题的话，这种限制就太强了。

QTRAN 提出了一种新的值分解的算法，将原来的联合行动价值函数转换为一种易于分解的函数，它们具有相同的最优行动，这种方法有更一般的降解，适合更多的场合，号称可以降解一切可以降解任务。

1. QTRAN 直观理解

在 VDN 和 QMIX 中是将 $Q_{\mathrm{jt}}$通过累加求和和保证单调性的方式来分解的，作者这里提出一种更加鲁棒的分解方式，将原始的 $Q_{\mathrm{jt}}$ 映射成 $Q_{\mathrm{jt}}^{\prime }$，通过$Q_{\mathrm{jt}}^{\prime }$去分解值函数到各个子智能体上，来保证学到的$Q_{\mathrm{jt}}^{\prime }$与真实的动作值函数 $Q^{\ast }$ 非常接近。这样在学习真实的动作值函数的时候，没有像 VDN 和 QMIX 那样对其加上一些累加求和和保证单调性的限制，所以它能学地更好。

但是由于部分可观测的限制，$Q_{\mathrm{jt}}^{\prime }$ 无法直接用于决策，因此需要建立 $Q_{\mathrm{jt}}$、$Q_{\mathrm{jt}}^{\prime }$ 与 $\left[Q_i\right]$ 三者之间的关系。

2. 背景

2.1 Decentralized POMDP

Decentralized POMDP 是用来给合作式多智能体任务建模的标准方法，简称 DEC-POMDP，表示为$\mathcal{G}=<\mathcal{S},\mathcal{U},P,r,\mathcal{Z},O,N,\gamma >$：

• $i\in N:=\{1,\dots ,N\}$：N 个 agents.
• $s\in S$：环境的真实状态
• $u_i\in U$：每个 agent 的动作
• $u:={\left[u_i\right]}_{i=1}^N\in {\mathcal{U}}^N$：联合动作向量
• $P(s^{\prime }\parallel s,u):\mathcal{S}\times {\mathcal{U}}^N\times \mathcal{S}\mapsto [0,1]$：状态转移方程
• $r(s,u):\mathcal{S}\times {\mathcal{U}}^N\mapsto \mathbb{R}$：共享的联合奖励函数
• $\gamma \in [0,1)$：折扣因子
• $z=O(s,i):\mathcal{S}\times \mathcal{N}\mapsto \mathcal{Z}$：每个 agent 自己的部分观察
• ${\tau }_i\in \mathcal{T}:=(\mathcal{Z}\times \mathcal{U}{)}^{\ast }$：每个 agent 的动作-观察历史

2.2 IGM Condition and Factorizable Task

下面给出 IGM 与可分解任务的定义。IGM 全称 Individual-Global-Max，可以理解为独立值函数最大化与联合值函数最大化的一致性，具体定义为；

给定一个联合动作值函数$Q_{\mathrm{jt}}:{\mathcal{T}}^N\times {\mathcal{U}}^N\mapsto \mathbb{R}$，其中$\tau \in {\mathcal{T}}^N$是联合动作-观察历史，如果存在一系列的独立动作值函数${[Q_i:\mathcal{T}\times \mathcal{U}\mapsto \mathbb{R}]}_{i=1}^N$使得如下条件成立：

$$\arg \underset{\mathit{u}}{max}{Q}_{\text{jt}}(\mathit{\tau },\mathit{u})=\left(\begin{array}{c}\arg \underset{u_1}{max}{Q}_1({\tau }_1,u_1)\\ ⋮\\ \arg \underset{u_N}{max}{Q}_N({\tau }_n,u_N)\end{array}\right)$$

则认为$\left[Q_i\right]$对于$Q_{\mathrm{jt}}$满足 IGM，即$Q_{\mathrm{jt}}(\tau ,\mathit{u})$可以被$\left[Q_i({\tau }_i,u_i)\right]$分解。

如果某任务的$Q_{\mathrm{jt}}(\tau ,\mathit{u})$对于所有的$\tau \in {\mathcal{T}}^N$都可分解，那么就认为该任务本身是可分解的。

VDN 和 QMIX 的分解方式其实本质上是满足 IGM 的充分非必要条件：

$$\begin{array}{rl}& \text{ (Additivity) }{Q}_{\mathrm{jt}}(\tau ,u)=\sum _{i=1}^N{Q}_i({\tau }_i,u_i)\\ & \text{ (Monotonicity) }\frac{\partial Q_{\text{jt}}(\tau ,u)}{\partial Q_i({\tau }_i,u_i)}\ge 0,\mathrm{\forall }i\in \mathcal{N}\end{array}$$

它们与本文 QTRAN 方法的关系可以用下图表示：

（图：VDN、QMIX 与 QTRAN 可表示函数集合的关系示意）

2.3 QTRAN

QTRAN 核心思想是将原有的联合行动价值函数$Q_{\mathrm{jt}}(\tau ,u)$转换为与$Q_{\mathrm{jt}}(\tau ,u)$共享最优联合行动的$Q_{\mathrm{jt}}^{{}^{\prime }}(\tau ,u)$

2.3.1 可分解值函数

可分解值函数的特点由如下定理给出：

Theorem 1：令$\bar{\mathit{u}}\mathrm{\_}i=\arg \underset{u_i}{max}{Q}_i({\tau }_i,u_i)$为最优的局部动作，$\bar{\mathit{u}}=\left[\overline{u}\mathrm{\_}i\right]\mathrm{\_}{i=1}^N$，当满足以下条件时，一个可分解的联合动作值函数$Q_{\text{jt}}(\tau ,\mathit{u})$可分解为$\left[Q_i({\tau }_i,u_i)\right]$：

$$\sum _{i=1}^N{Q}_i({\tau }_i,u_i)-Q_{\mathrm{jt}}(\tau ,u)+V_{\mathrm{jt}}(\tau )=\{\begin{array}{ll}0& u=\overline{u},\\ \ge 0& u\ne \overline{u}\end{array}$$

其中

$$V_{\mathrm{jt}}(\tau )=\underset{u}{max}{Q}_{\mathrm{jt}}(\tau ,u)-\sum _{i=1}^N{Q}_i({\tau }_i,{\overline{u}}_i)$$

证明如下：

$$\begin{array}{rl}{Q}_{\mathrm{jt}}(\tau ,\overline{u})& =\sum _{i=1}^N{Q}_i({\tau }_i,{\overline{u}}_i)+V_{\mathrm{jt}}(\tau )(\text{ From}(4\mathrm{a}))\\ & \ge \sum _{i=1}^N{Q}_i({\tau }_i,u_i)+V_{\mathrm{jt}}(\tau )\\ & \ge Q_{\mathrm{jt}}(\tau ,u)(\text{ From}(4\mathrm{b}))\end{array}$$

注意，对于映射变化$\varphi (\mathit{Q})=A\cdot \mathit{Q}+B$来说，如果$A=\left[a_{ii}\right]\in \mathbb{R}\mathrm{\_}{+}^{N\times N}$是对称的对角矩阵且$a_{ii}>0,\mathrm{\forall }i$，$B=\left[b_i\right]\in {\mathbb{R}}^N$，那么上述定理依旧成立。可以把$A$与$B$看作是缩放与偏差。

因此可以找到一个转换联合动作值函数$Q_{\mathrm{jt}}^{{}^{\prime }}(\tau ,u)$满足上述定理：

$$Q_{\mathrm{jt}}^{\prime }(\tau ,u):=\sum _{i=1}^N{Q}_i({\tau }_i,u_i)$$

这是因为这种加和形式下，$\left[Q_i\right]$对于$Q_{\mathrm{jt}}^{\prime }$满足 IGM，又因为$\arg \underset{\mathit{u}}{max}{Q}_{\text{jt}}(\mathit{\tau },\mathit{u})=\arg \underset{\mathit{u}}{max}{Q}_{\text{jt}}^{\prime }(\mathit{\tau },\mathit{u})$，所以$\left[Q_i\right]$就是$Q_{\mathrm{jt}}^{\prime }$的分解。

2.3.2 方法框架

QTRAN 的框架如下图所示：

（图：QTRAN 网络结构示意）

其中包含三个网络：

$$\begin{array}{rl}& \text{独立动作值函数网络：}{f}_{\mathbf{q}}:({\tau }_i,u_i)\mapsto Q_i\\ & \text{联合动作值函数网络：}{f}_{\mathrm{r}}:(\tau ,\mathit{u})\mapsto Q_{\mathrm{jt}}\\ & \text{状态值函数网络：}{f}_{\mathbf{v}}:\mathit{\tau }\mapsto V_{jt}\end{array}$$

其中，联合动作值函数网络使用所有独立动作值函数网络采样得到的动作进行更新，并连接各个所有独立动作值函数网络底层输出的隐性特征$h_i({\tau }_i,u_i)=[h_{Q,i}({\tau }_i,u_i),h_{V,i}\left({\tau }_i\right)]$

2.3.3 损失函数

QTRAN 中的 loss 函数由三部分组成：

$$L(\mathit{\tau },\mathit{u},\mathit{r},{\mathit{\tau }}^{\prime };\mathit{\theta })=L_{\mathrm{td}}+{\lambda }_{\mathrm{opt}}{L}_{\mathrm{opt}}+{\lambda }_{\mathrm{nopt}}{L}_{\mathrm{nopt}}$$

其中：$L_{\mathrm{td}}$用于评估真实的动作值，$L_{\mathrm{opt}}$和$L_{\mathrm{nopt}}$用于评估分解$Q_{jt}$为$\left[Q_i\right]$时是否满足 Theorem 1。由于 Theorem 1 的条件需要在训练中采样大量样本才能满足，这里做了简化，即在训练$L_{\mathrm{opt}}$和$L_{\mathrm{nopt}}$时固定$Q_{jt}$，并使用$\hat{Q}\mathrm{\_}\mathrm{jt}$来表示这个固定的$Q_{jt}$。具体每个损失函数的定义如下：

$$\begin{array}{rl}{L}_{\mathrm{td}}(;\mathit{\theta })& ={(Q_{\mathrm{jt}}(\tau ,\mathit{u})-y^{\mathrm{d}\mathrm{q}\mathrm{n}}(r,{\mathit{\tau }}^{\prime };{\mathit{\theta }}^{-}))}^2\\ L_{\mathrm{opt}}(;\mathit{\theta })& ={(Q_{\mathrm{jt}}^{\prime }(\tau ,\bar{\mathit{u}})-{\hat{Q}}_{\mathrm{jt}}(\tau ,\bar{\mathit{u}})+V_{\mathrm{jt}}(\tau ))}^2\\ L_{\mathrm{nopt}}(;\mathit{\theta })& ={(min[Q_{\mathrm{jt}}^{\prime }(\tau ,\mathit{u})-{\hat{Q}}_{\mathrm{jt}}(\tau ,\mathit{u})+V_{\mathrm{jt}}(\tau ),0])}^2\end{array}$$

其中$y^{\mathrm{dqn}}(r,{\mathit{\tau }}^{\prime };{\mathit{\theta }}^{-})=r+\gamma Q_{\mathrm{jt}}({\tau }^{\prime },{\bar{\mathit{u}}}^{\prime };{\mathit{\theta }}^{-})$，${\overline{u}}^{\prime }={[\arg \underset{u_1}{max}{Q}_i({\tau }_i^{\prime },u_i;{\mathit{\theta }}^{-})]}_{i-1}^N$，${\theta }^{-}$为 DQN 目标网络的参数。

2.3.4 修改对联合行动价值函数的追踪

上述版本的 QTRAN 称为 QTRAN-base，反映其如何追踪联合行动价值函数的基本性质。然而，Theorem 1 的第二个条件太宽，导致神经网络无法完成构建$Q_{jt}$正确的分解，即对非最优行为施加不良影响，这进而影响了训练过程的稳定性和收敛速度。这促使去研究比 Theorem 1 的第二个条件更强的条件，同时满足 Theorem 1 的仿射变换的不变性：

Theorem 2：Theorem 1 的第二个条件替换为如下条件时，Theorem 1 依旧成立。当$u=\overline{u}$时，

$$\begin{array}{rl}\underset{u_i\in \mathcal{U}}{min}[& Q_{\mathrm{jt}}^{\prime }(\tau ,u_i,{\mathit{u}}_{-i})-Q_{\mathrm{jt}}(\tau ,u_i,{\mathit{u}}_{-i})+V_{\mathrm{jt}}(\tau )]=0,\mathrm{\forall }i=1,\dots ,N\end{array}$$

其中$\mathit{u}\mathrm{\_}-i=(u_1,\dots ,u_{i-1},u_{i+1},\dots ,u_N)$，即除了 agent$i$以外的所有动作。

为了实现 Theorem 2，使用反事实联合网络来替代联合动作值函数网络，即对于每个 agent 都设置一个反事实网络$Q_{\mathrm{jt}}(\tau ,\cdot ,\mathit{u}\mathrm{\_}-i)$。同时将$L_{\text{nopt}}$替换为$L_{\text{nopt-min}}$：

$$L_{\mathrm{nopt}-min}(\tau ,u,r,{\tau }^{\prime };\theta )=\frac{1}{N}\sum _{i=1}^N{\left(\underset{u_i\in U}{min}D(\tau ,u_i,u_{-i})\right)}^2$$

其中$D(\tau ,u_i,u_{-i})=Q_{\mathrm{jt}}^{\prime }(\tau ,u_i,u_{-i})-\hat{Q}\mathrm{\_}\mathrm{jt}(\tau ,u_i,u_{-i})+V_{\mathrm{jt}}(\tau )$

3. 实验内容

在下图的单状态马尔科夫博弈中，QTRAN 是唯一获得最优解的：

（图：单状态矩阵博弈实验结果示意）

QTRAN-alt 比 QTRAN-base 更好地区分最优动作与非最优动作：

（图：QTRAN-base 与 QTRAN-alt 动作区分能力示意）

将 Multi-domain Gaussian Squeeze、Modified predator-prey 等环境设置为强迫合作式的环境，表现超越了 VDN 与 QMIX：

（图：多个合作环境实验结果示意）

4. 缺点

• 分解的 Q 值依旧没有实际含义

• 在复杂的 MARL 任务上的实际表现很差，因为由于 QTRAN 使用的约束太过松散，实现时的过多近似会导致在很多任务上效果不如 Q-mix 理想

5. 优点

• 进一步扩大了 Q 值分解理论的适用范围
• 采用类似 dueling network 的结构可以提升学习效果, 加速收敛