# Towards Global Optimality in Cooperative MARL with the Transformation And
Distillation Framework

Jianing Ye  Chenghao Li  Jianhao Wang  Chongjie Zhang

###### Abstract

Decentralized execution is one core demand in cooperative multi-agent
reinforcement learning (MARL). Recently, most popular MARL algorithms have
adopted decentralized policies to enable decentralized execution and use
gradient descent as their optimizer. However, there is hardly any theoretical
analysis of these algorithms taking the optimization method into
consideration, and we find that various popular MARL algorithms with
decentralized policies are suboptimal in toy tasks when gradient descent is
chosen as their optimization method. In this paper, we theoretically analyze
two common classes of algorithms with decentralized policies – multi-agent
policy gradient methods and value-decomposition methods to prove their
suboptimality when gradient descent is used. In addition, we propose the
Transformation And Distillation (TAD) framework, which reformulates a multi-
agent MDP as a special single-agent MDP with a sequential structure and
enables decentralized execution by distilling the learned policy on the
derived “single-agent” MDP. This approach uses a two-stage learning paradigm
to address the optimization problem in cooperative MARL, maintaining its
performance guarantee. Empirically, we implement TAD-PPO based on PPO, which
can theoretically perform optimal policy learning in the finite multi-agent
MDPs and shows significant outperformance on a large set of cooperative multi-
agent tasks.

Machine Learning, ICML

##  1 Introduction

Cooperative multi-agent reinforcement learning (MARL) is a promising approach
to a variety of real-world applications, such as sensor networks (Zhang &
Lesser, 2011), traffic light control (Van der Pol & Oliehoek, 2016), and
multi-robot formation (Alonso-Mora et al., 2017). One major challenge in MARL
is the scalability issue when the number of agents grows. To address this
challenge, the paradigm of centralized training with decentralized execution
(CTDE) (Oliehoek et al., 2011; Kraemer & Banerjee, 2016) is widely adopted,
allowing agents to access global information in training while executing in a
decentralized manner. On the other hand, gradient descent and its variants are
broadly used in deep MARL, usually as the default optimizer to optimize the
loss function.

Recently, many CTDE algorithms have been proposed to enable decentralized
execution by directly learning decentralized policies with gradient descent as
the optimizer. COMA (Foerster et al., 2018) and MAPPO (Yu et al., 2021)
factorize the joint policy as the direct product of decentralized policies.
Then they use their critic networks to estimate the policy gradient and update
the policy parameters. VDN (Sunehag et al., 2018), QMIX (Rashid et al., 2018),
and QPLEX (Wang et al., 2021b) factorize the joint Q-function into individual
Q-functions with the IGM constrain (Son et al., 2019) to enable standard TD-
learning, where the decentralized policies are the greedy policies w.r.t.
individual Q-functions. However, there is barely any theoretical analysis of
CTDE algorithms taking the optimization method into consideration, and we find
that many of them would get stuck in some local minima and thus lose their
optimality guarantee in toy tabular tasks.

To characterize this problem, we theoretically analyze two sub-classes of
state-of-the-art cooperative MARL: (1) multi-agent policy gradient algorithms
(MA-PG) Foerster et al. (2018); Yu et al. (2021); and (2) value-decomposition
algorithms (VD) Sunehag et al. (2018); Rashid et al. (2018); Wang et al.
(2021b). We prove that these two classes of algorithms are suboptimal with
mild assumptions. Intuitively, this is because directly learning decentralized
policies by MA-PG or VD restricts the parameter space to have a “decentralized
structure”, which would create numerous local optima, while gradient descent,
as a local search in the parameter space, is hard to escape from a local
optimum.

To address this optimality problem, we present a Transformation And
Distillation (TAD) framework. TAD first reformulates a multi-agent MDP as an
equivalent single-agent MDP with a sequential decision-making structure. With
this transformation, any off-the-shelf single-agent reinforcement learning
(SARL) algorithm can be adapted to efficiently learn a coordination policy in
the cooperative multi-agent task by solving the transformed single-agent task.
Finally, decentralized policies are derived by distilling the coordination
policy to enable decentralized execution. We formally prove that the TAD
framework can maintain the performance guarantee of the single agent algorithm
we choose so that TAD can guarantee optimality with the ability of
decentralized execution.

Empirically, we implement TAD-PPO based on PPO (Schulman et al., 2017), the
single agent algorithm. TAD-PPO can theoretically perform optimal policy
learning in finite multi-agent MDPs and empirically shows significant
outperformance on a large set of cooperative multi-agent tasks, including SMAC
(Samvelyan et al., 2019) and GRF (Kurach et al., 2019).

##  2 Related Work

Many algorithms are proposed to enable decentralized execution in cooperative
MARL.

Among them, policy-based algorithms try to optimize the policy by maximizing
its value. Typically, the joint policy is factorized as a direct product of
decentralized policies, and is end-to-end updated by the policy gradient
(Foerster et al., 2018; Wang et al., 2021c; Lowe et al., 2017; Yu et al.,
2021). Further, there are also algorithms using a heterogeneous way to update
the decentralized policies (Kuba et al., 2021, 2022), which alleviates the
non-stationarity in policy updates.

While value-based algorithms try to optimize the Bellman error of the joint
value function, which is usually decomposed into a function of local
Q-functions. To enable TD-learning, it is crucial to follow the IGM principle
(Son et al., 2019). Various works (Sunehag et al., 2018; Rashid et al., 2018)
are made to satisfy the IGM principle by giving up part of the completeness of
the Q-function class. Since an incomplete Q-function class would constitute
inherent Bellman error (Munos & Szepesvari, 2008) and harm the performance,
Son et al. (2019); Rashid et al. (2020) use soft regularizers to approximate
the IGM constraint, and Wang et al. (2021b) is the first work using a duplex
dueling structure to make the IGM constraint and the completeness constraint
both satisfied.

There are numerous theoretical works that analyze the optimality of popular
single-agent algorithms taking the optimization method into consideration
(Konda & Tsitsiklis, 1999; Degris et al., 2012; Fu et al., 2020). However, in
MARL, most of the analysis considers the optimizer as a black box and assumes
it can perfectly solve the corresponding optimization problem (Wang et al.,
2021b, a). TAD is the first work that theoretically analyzes the suboptimality
of two large classes of MARL algorithms when using gradient descent as the
optimizer. And TAD-PPO is the first MARL algorithm with decentralized
execution that not only achieves remarkable performance but also has a
theoretical guarantee on its optimality when gradient descent is used.

##  3 Preliminaries

###  3.1 RL Models

In MARL, we model a fully cooperative multi-agent task as a Dec-POMDP
(Oliehoek et al., 2016) defined by a tuple
$\langle\mathcal{S},\mathcal{A},P,\mathcal{\varOmega},O,r,\gamma,n\rangle$,
where $\mathcal{N}=\\{1,\cdots,n\\}$ is a set of agents and $\mathcal{S}$ is
the global state space, $\mathcal{A}$ is the individual action space, and
$\gamma$ is a discount factor. At each time step, agent $i\in\mathcal{N}$ has
access to the observation $o_{i}\in\mathcal{\varOmega}$, drawn from the
observation function $O(s,i)$. Each agent has an action-observation history
$\tau_{i}\in\mathcal{\varOmega}\times\left(\mathcal{A}\times\mathcal{\varOmega}\right)^{*}$
and constructs its individual policy $\pi(a_{i}|\tau_{i})$. With each agent
$i$ selecting an action $a_{i}\in\mathcal{A}$, the joint action
$\bm{a}\equiv[a_{i}]_{i=1}^{n}$ leads to a shared reward $r(s,\bm{a})$ and the
next state $s^{\prime}$ according to the transition distribution
$P(s^{\prime}|s,\bm{a})$. The formal objective of MARL agents is to find a
joint policy $\bm{\pi}=\langle\pi_{1},\dots,\pi_{n}\rangle$ conditioned on the
joint trajectories $\bm{\tau}\equiv[\tau_{i}]_{i=1}^{n}$ that maximizes a
joint value function
$V^{\bm{\pi}}(s)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{t}|s_{0}=s,\bm{\pi}\right]$.
Another quantity in policy search is the joint action-value function
$Q^{\bm{\pi}}(s,\bm{a})=r(s,\bm{a})+\gamma\mathbb{E}_{s^{\prime}}[V^{\bm{\pi}}(s^{\prime})]$.

Besides, we also introduce the Multi-agent MDPs (MMDP) (Boutilier, 1996) and
Markov Decision Process (MDP) (Sutton & Barto, 2018) as special cases of Dec-
POMDP, where an MMDP is a Dec-POMDP with full-observation, and an MDP is an
MMDP with only one agent. The formal definition is deferred to Section A.1.

###  3.2 Multi-agent Policy Gradient and Value-Decomposition

We introduce two popular classes of cooperative multi-agent learning
algorithms for our analysis: multi-agent policy gradient (MA-PG) and value-
decomposition (VD). To simplify our theoretical analysis, our discussion based
on the assumption that the environment is an MMDP.

#### Multi-agent Policy Gradient

MA-PG factorizes the joint policy as a direct product of the decentralized
policies with parameter $\Theta\in\text{dom}(\Theta)$:

$\displaystyle\forall
s\in\mathcal{S}:\quad\bm{\pi}(\bm{a}|s;\Theta)=\prod_{i=1}^{n}\pi_{i}(a_{i}|s;\Theta)$
(1)

Denoting $\mathcal{J}(\bm{\pi})$ as the expected return of policy $\bm{\pi}$,
the policy is updated by the policy gradient (Sutton & Barto, 2018) with a
small learning rate $\alpha$:
$\Theta^{(t+1)}\leftarrow\Theta^{(t)}+\alpha\nabla_{\Theta}\mathcal{J}(\bm{\pi}_{\Theta})$,
which is equivalent to minimize the following loss function by gradient
descent.

$\displaystyle\mathcal{L}(\Theta)=-\mathcal{J}(\bm{\pi}_{\Theta})$ (2)

#### Value-decomposition

VD maintains a joint Q-value function $Q(s,\bm{a};\Theta)$ and $n$ local
Q-value functions $Q_{1}(s,a_{1};\Theta),\cdots,Q_{n}(s,a_{n};\Theta)$
parameterized by some $\Theta\in\text{dom}(\Theta)$. Standard TD-learning is
then applied with a small learning rate $\alpha$ to update the parameter
$\Theta$, which is equivalent to minimizing the following loss function by
gradient descent (Rozada et al., 2021):

$\displaystyle\mathcal{L}(\Theta)=\frac{1}{2}\mathbb{E}_{s,\bm{a}}\left[Q(s,\bm{a};\Theta)-(\mathcal{T}Q_{\Theta})(s,\bm{a})\right]^{2}$
(3)

where $\mathcal{T}$ is the Bellman operator.

Meanwhile, the IGM (Individual-Global-Max) principle (Son et al., 2019) is
enforced to realize effective TD-learning, which asserts the consistency
between joint and local greedy action selections in the joint action-value
$Q(s,\bm{a})$ and local action-values $\left[Q_{i}(s,a_{i})\right]_{i=1}^{n}$,
respectively:

$\displaystyle\forall
s:\quad\mathop{\arg\max}_{\bm{a}\in\bm{\mathcal{A}}}Q(s,\bm{a})\supseteq\bigtimes_{i=1}^{n}\mathop{\arg\max}_{a_{i}\in\mathcal{A}}Q_{i}(s,a_{i})$
(4)

VD enables IGM condition by representing the joint Q-value function as a
specific function $f$ of local Q-functions:

$\displaystyle
Q(s,\bm{a};\Theta)=f(Q_{1}(s,\cdot),\cdots,Q_{n}(s,\cdot),s,\bm{a};\Theta)$
(5)

For example, Sunehag et al. (2018) represents $Q$ as a summation of
$[Q_{i}]_{i=1}^{n}$; and Rashid et al. (2018) can represent $Q$ as any
monotonic function of $[Q_{i}]_{i=1}^{n}$ by adjusting the parameter $\Theta$.

In this way, the joint Q-function is “decomposed” into local Q-functions, and
the decentralized policies of VD can be obtained by calculating the greedy
actions w.r.t. the local Q-functions.

##  4 Suboptimality of MA-PG and VD with Gradient Descent

In this section, we will formally analyze the suboptimality of MA-PG and VD
when using gradient descent as the optimizer. As mentioned before, gradient
descent can be viewed as a local search in the parameter space, which is hard
to escape from local optima. Yet, the loss functions in MA-PG and VD adopt
different ways to evaluate how good the current decentralized policies are
(Equations 2 and 3). We will show that these approaches create numerous local
optima in the loss function regardless of the parameterization of the
functions. Consequently, the convergence results of MA-PG and VD depend
heavily on the initialization, which contrasts with the results of many
classical SARL algorithms, e.g., Value Iteration.

###  4.1 Suboptimality of Multi-agent Policy Gradient

We first present the suboptimality theorem for MA-PG as follows.

Table 1: Matrix Game with locally optimal policies: in this case, $(0,0)$, $(1,1)$, and $(2,2)$ are three locally optimal policies in the production of the decentralized policies’ spaces. 10 | -30 | -30
---|---|---
-30 | 5 | -30
-30 | -30 | 1

######  Theorem 4.1.

There are tasks such that, when the parameter $\Theta$ is initialized in
certain region $\Omega$ with positive volume, MA-PG (Equations 1 and 2)
converges to a suboptimal policy with a small enough learning rate $\alpha$.

To serve intuitions about why Theorem 4.1 holds, we introduce a matrix game
here as a didactic example and defer the proof to Section B.2. The matrix game
described in Table 1 is a $1$-step cooperative game with two players. These
two players (one selects a row and one selects a column simultaneously,
$\mathcal{A}=\\{0,1,2\\}$) coordinate to select an entry of the matrix
representing the joint payoff. We will show that the corresponding $\Theta$s
of the suboptimal policies $(1,1)$ and $(2,2)$ are stationary points (with
zero gradients) of the loss function $\mathcal{L}$ in this case.

We prove it by contradiction, if the gradient of $\mathcal{L}$ in MA-PG
(Equation 2) is non-zero at some $\Theta$, then by the definition of gradient,
we can move $\Theta$ a little bit along the negative gradient to obtain a
strictly greater expected payoff $\mathcal{J}$. However, this is impossible
when the current policy is the deterministic policy $(1,1)$ since one cannot
increase the probability of $(0,0)$ (a better payoff, $10$) without increasing
the probability of $(0,1)$ or $(1,0)$ (an even larger penalization, $-30$)
when the policy space is a product space of decentralized policies’ spaces. A
similar situation also occurs when the current policy is $(2,2)$.

This example shows that the decentralized structure in policy restricts the
structure of parameter space and may create local optima independent of the
parameterization if we do not design the loss function carefully. This makes
the optimality guarantee lost when gradient descent is used.

###  4.2 Suboptimality of Value-Decomposition

As for VD, the situation is much more complex. IGM (Equation 4) is a vital
precondition to enable efficient TD-learning. Early work of VD uses specific
structures to satisfy a sufficient condition of IGM, such as linear structure
(Sunehag et al., 2018) or monotonic structure (Rashid et al., 2018). These
approaches sacrifice the completeness of the Q-function class, which would
incur inherent Bellman error and deviate the learning process to unexpected
behavior (Munos & Szepesvari, 2008; Agarwal et al., 2019). Later, QPLEX (Wang
et al., 2021b) addresses the incompleteness issue under the IGM constraint by
introducing a duplex dueling structure.

However, all these algorithms fail to guarantee optimality again because of
the structure of the parameter space they have. Since VD with an incomplete
function class already suffers from inherent Bellman error as mentioned above,
we consider VD with a complete function class. To characterize the
suboptimality of VD with a complete function class, we present Theorem 4.2.

######  Theorem 4.2.

For any VD (Equations 5, 3 and 4) with a complete function class, there are
tasks such that, when the parameter $\Theta$ is initialized in certain set
$\Omega$, it converges to a suboptimal policy.

The proof and a finer characterization are presented in Section B.3.

Roughly speaking, Theorem 4.2 is a consequence of the IGM constraint over
decentralized and joint policies. Because of it, the process of GD would be a
local search over the complete value function class keeping the IGM constraint
satisfied all along. Therefore such a searching process over the space looks
“crooked” and “obstructed” everywhere, making it easy to get stuck into some
local optimum.

##  5 Transformation and Distillation Framework

Figure 1:  The architecture of transformation and distillation framework with
PPO (TAD-PPO). WK, WQ, and V are key matrix, query matrix, and value matrix
respectively in the MHA module (Vaswani et al., 2017).

As suggested by Theorems 4.1 and 4.2, MA-PG and VD suffer from the cratered
loss function induced by the decentralized structure, which makes their
convergence results depend heavily on the initialization. However, the PG with
a softmax parameterization and the tabular Q-learning, which are the
counterparts of MA-PG and VD in SARL, both guarantee the global convergence to
the optimum (Mei et al., 2020; Watkins & Dayan, 1992) due to their nice global
properties of optimization objective. This observation motivates us to convert
the original multi-agent learning problem into a single-agent one to enjoy a
possibly better structure in the optimization problem.

Inspired by this observation and a series of prior works on sequence modeling
(Bertsekas, 2019; Angermueller et al., 2020; Jain et al., 2022; Olivecrona et
al., 2017; You et al., 2018), we find that breaking joint learning into
sequential decision-making directly transfers properties of single-agent
algorithms into multi-agent ones. To formalize such “reduction” of algorithms
from the perspective of performance guarantee, we propose the Transformation
And Distillation (TAD) framework, which is a two-stage framework under the
paradigm of centralized training with decentralized execution (CTDE).

###  5.1 TAD on MMDP

To simplify our analysis, we assume the underlying task to be an MMDP here.

In the centralized training phase of CTDE, all $n$ agents will coordinate to
improve their joint policy. In particular, when a joint action needs to be
inferred, they coordinate to infer $\bm{a}=(a_{1},\cdots,a_{n})$ jointly. If
we give these agents a virtual order and imagine they infer their individual
actions one after another, that is, when agent $i$ infers its action $a_{i}$,
all “previously inferred” actions $a_{j}(j<i)$ are known to $i$, then we can
view this procedure of multi-agent decision-making to a “single-agent” one,
since all agents are homogeneous here in MMDP. From a theoretical perspective,
the discussion above states a transformation from MMDP into MDP in essence.

We formally define the Sequential Transformation $\Gamma$ as Algorithm 1.

Algorithm 1 The Sequential Transformation $\Gamma$

1: Input: An MMDP $\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma,n)$.

2: Output: An MDP
$\Gamma(\mathcal{M})=(\mathcal{S}^{\prime},\mathcal{A}^{\prime},P^{\prime},r^{\prime},\gamma^{\prime})$.

3:
$\mathcal{S}^{\prime}\leftarrow\bigcup_{k=0}^{n-1}\mathcal{S}\times\mathcal{A}^{k}$.

4: $\mathcal{A}^{\prime}\leftarrow\mathcal{A}$.

5: $\gamma^{\prime}=\gamma^{1/n}$.

6: Initialize $P^{\prime}(s^{\prime}|s,a)=0$ for all
$s,s^{\prime}\in\mathcal{S}^{\prime},a\in\mathcal{A}^{\prime}$.

7: Initialize $r^{\prime}(s,a)=0$ for all
$s\in\mathcal{S}^{\prime},a\in\mathcal{A}^{\prime}$.

8: for all $s^{\prime}\in\mathcal{S}^{\prime}$ do

9: if $s^{\prime}=(s,a_{1},\cdots,a_{k})$ and $k<n-1$ then

10: // If this is not the last action:

11: for all $a_{k+1}\in\mathcal{A}^{\prime}$ do

12: $u\leftarrow(s,a_{1},\cdots,a_{k},a_{k+1})$. // Create a new virtual state
by appending $a_{k+1}$ to $s^{\prime}$.

13: $P^{\prime}(u|s^{\prime},a_{k+1})\leftarrow 1$. // Set a deterministic
transition from $s^{\prime}$ to $u$.

14: end for

15: else

16: // If this is the last action:

17: for all $a_{n}\in\mathcal{A}^{\prime}$ do

18: $r^{\prime}(s^{\prime},a_{n})\leftarrow r(s,a_{1},\cdots,a_{n})$.

19: // Set the reward according to $\mathcal{M}$.

20: for all $u\in\mathcal{S}$ do

21: $P^{\prime}(u|s^{\prime},a_{n})\leftarrow P(u|s,a_{1},\cdots,a_{n})$.

22: // Set the transition accordint to $\mathcal{M}$.

23: end for

24: end for

25: end if

26: end for

27: Return
$\Gamma(\mathcal{M})=(\mathcal{S}^{\prime},\mathcal{A}^{\prime},P^{\prime},r^{\prime},\gamma^{\prime})$.

We can then prove the equivalence of the MMDP $\mathcal{M}$ and the MDP
$\Gamma(\mathcal{M})$ after transformation in the perspective of policy value
by the following theorem. The proof is presented in Appendix C.

######  Theorem 5.1.

Let $C=\gamma^{(1-n)/n}$ be a constant. For any learned policy $\pi$ on the
transformed MDP $\Gamma(\mathcal{M})$, we can convert $\pi$ into a
coordination policy $\pi_{\text{c}}$ on the original MMDP $\mathcal{M}$, and
vice versa, such that
$\mathcal{J}_{\Gamma(\mathcal{M})}(\pi)=C\mathcal{J}_{\mathcal{M}}(\pi_{c})$.

Theorem 5.1 says that there is an easy-to-compute bijection between the policy
space of $\mathcal{M}$ and that of $\Gamma(\mathcal{M})$, such that the
relative magnitude of policy value retains.

#### The Transformation Stage

In the transformation stage of TAD, we use some SARL algorithm $A$, wrap the
interface of the multi-agent environment to make $A$ run as if it is
accessible to the interactive environment of $\Gamma\left(\mathcal{M}\right)$.
Then we convert the policy learned by $A$ to a coordination policy on
$\mathcal{M}$ without loss of performance by Theorem 5.1.

#### The Distillation Stage

In the distillation stage of TAD, a distillation process is applied to the
coordination policy to obtain decentralized policies. This is easy to be done
on MMDP, since we have full observations and therefore can completely know
what allies did and will do, which means we calculate the coordination policy
locally. To be succinct, the details are presented in Appendix C.

We present the whole TAD framework as Algorithm 2.

Algorithm 2 The Transformation And Distillation (TAD) framework

1: Input: An MMDP $\mathcal{M}$ of $n$ agents, a single agent algorithm $A$.

2: Output: Decentralized policies $\pi_{1},\cdots,\pi_{n}$.

3: The Transformation Stage (for centralized training):

4: $\mathcal{N}\leftarrow\Gamma(\mathcal{M})$. // Transform $\mathcal{M}$ into
an MDP $\mathcal{N}$.

5: Run $A$ on $\mathcal{N}$ to obtain a policy $\pi$.

6: Convert $\pi$ to a coordination policy $\pi^{c}$.

7: The Distillation Stage (for decentralized execution):

8: Distill $\pi^{c}$ into decentralized policies $\pi_{1},\cdots,\pi_{n}$.

9: Return $\pi_{1},\cdots,\pi_{n}$.

We have the following theorem for the TAD framework.

######  Theorem 5.2.

For any SARL algorithm $A$ with an optimality guarantee on MDP, TAD-$A$, the
MARL algorithm using the TAD framework and based on $A$, will have an
optimality guarantee on any MMDP.

Theorem 5.2 shows that the TAD framework successfully bridges the gap to
optimal decentralized policy learning for CTDE algorithms. The proof is
presented in Appendix C.

###  5.2 Extending TAD to Dec-POMDP

In practice, many MARL benchmarks are partially observable and require each
agent to execute independently. To apply our algorithms to partial-observable
environments with a decentralized execution manner, we need to extend the TAD
framework to the setting of Dec-POMDP.

In this paper, we select proximal policy optimization (PPO, Schulman et al.
(2017)) as the basic SARL algorithm because a suitable implementation of PPO
enjoys the optimality guarantee in MDP (Liu et al., 2019; Yao et al., 2021),
and its counterparts in the multi-agent setting, MAPPO (Yu et al., 2021) and
IPPO (de Witt et al., 2020), have already achieved great success in
challenging benchmarks.

The Actor-Critic structure is shown in Figure 1 with GRU modules to represent
partial observations. All agents share parameters of actor and critic for
enjoying learning efficiency enhanced by parameter sharing (Yu et al., 2021;
Li et al., 2021a). To provide representation diversity across agents, we
further add each agent’s identity as a part of input (Rashid et al., 2018) as
shown in Figure 1.

Following the TAD framework, we introduce previous agents’ actions to each
agent’s actor and critic modules, so that a sequential decision-making process
is enabled in the centralized training phase. However, this sequential
transformed information increases with respect to the number of agents. To
achieve scalability, we equip agents’ actor and critic with a multi-head
attention (MHA) module(Vaswani et al., 2017; Iqbal et al., 2021) respectively,
which contains queries WQs, keys WKs, and values Vs. WQs are outputs of an MLP
network with $h_{i}^{(t)}$ (output of GRU) as the input. WKs and Vs are
outputs of MLP networks with all previous actions $a_{<i}^{({t})}$ as the
input.

For the distillation part that distills the coordination policy into
decentralized policies, we optimize the KL divergence between the
decentralized policies and the joint coordination policy, which is known as
behavior cloning. Denote the joint policy
$\pi_{\text{jt}}(\bm{a}|\bm{\tau})=\prod_{i}\pi_{i,T}(a_{i}|\tau_{i},a_{<i})$,
we have

$\displaystyle\text{KL}\left(\pi_{\text{jt}}(\cdot|\bm{\tau})\middle\|\prod_{i=1}^{n}\pi_{i,E}(\cdot|\tau_{i};\phi)\right)$
$\displaystyle=$
$\displaystyle\underbrace{\mathop{\mathbb{E}}_{\bm{a}\sim\pi_{\text{jt}}(\cdot|\bm{\tau})}\left[-\sum_{i=1}^{n}\log\pi_{i,E}(a_{i}|\tau_{i};\phi)\right]}_{\text{distillation
loss (cross entropy)
}\mathcal{L}(\phi)}-\underbrace{H(\pi_{\text{jt}}(\cdot|\bm{\tau}))}_{\text{entropy
(a constant)}}$ (6)

where $\pi_{i,T}$ and $\pi_{i,E}$ are the coordination policy and the
decentralized policy of agent $i$.

Here we share GRU and the representation layer, whose inputs do not contain
other agents’ information. During the evaluation, only blue modules in Figure
1 are activated for decentralized execution. To distinguish policies in
different stages, we name the policy in the transformation stage as TAD-PPO-T
and the policy during the distillation stage as TAD-PPO.

##  6 Experiments

We design experiments to answer the following questions: (1) Can the TAD
framework achieve the global optimal policy on MMDP? (2) Can TAD-PPO improve
learning efficiency for policy-based MARL algorithms? (3) Will the
distillation stage degenerate the performance of joint policy learning during
decentralized execution?

We first use a didactic example to demonstrate the global optimality of our
coordination policy compared to multi-agent value-based methods, i.e., VDN
(Sunehag et al., 2018), QMIX (Rashid et al., 2018), QTRAN (Son et al., 2019),
and QPLEX (Wang et al., 2021b), and policy-based methods, i.e., MAPPO (Yu et
al., 2021) and HAPPO (Kuba et al., 2021). To approach complex domains, we
conduct experiments on the StarCraft II micromanagement (SMAC) benchmark
(Samvelyan et al., 2019) and Google Research Football (GRF) benchmark (Kurach
et al., 2019). Evaluation results are averaged over three random seeds and use
95% bootstrapped confidence interval to present the vairance.

###  6.1 Didactic Example

Figure 2: Learning curves in the didactic example.

We conduct a didactic example to investigate the optimality of MARL learning
algorithms. This didactic exmample is a stacked matrix game, which has 10 one-
step matrices with two players. Defer the details to Appendix D.1. Figure 2
shows that TAD-PPO achieves the optimal performance and baselines cannot solve
these 10 matrices simultaneously. This result suggests that our Transformation
And Distillation framework can achieve the global optimal strategy with the
optimizer of gradient descent. As our theory indicates, the MARL policy
gradient methods (i.e., HAPPO and MAPPO) will converges to a locally optimal
policy due to bad hyperameter initializaton. In MARL value-decomposition
methods, VDN and QMIX suffers from incomplete function classes, QPLEX may get
stuck in local optimas due to its mixing structure, and QTRAN cannot optimize
well by its discontinuous loss function. In this didactic example, TAD-PPO
achieves the-state-of-art performance with a theoretical guarantee of
optimality using gradient descent.

Figure 3: Payoff of one matrix game with local optimal points and learned
joint policies based on our approach TAD-PPO and MAPPO..

To understand the policy learning in the didactic example, we use a popular
matrix proposed by QTRAN (Son et al., 2019) to visualize the joint policies of
TAD-PPO and MAPPO in Figure 3. In our Transformation And Distillation
framework, the local optima is unique and TAD-PPO can learn the optimal
policy, as shown in Figure 3 (b). However, Figure 3 (b) and (c) are two of
local optimas of MARL policy gradient methods and we find that MAPPO will
converge to the bad local optima in Figure 3 (c) with random parameter
initializaton of neural networks.

###  6.2 StarCraft II

Figure 4: Learning curve of SMAC Figure 5: Learning curve of GRF.

We benchmark our method on all 14 maps which are classified as easy, hard, and
super hard. Furthermore, we design a novel map with one local optimal point
and one global optimal point named $\mathtt{3h\\_vs\\_1b1z3h}$ and compare our
method with baselines in this map. In this section, we illustrate the
comparison of performance in four super hard maps ($\mathtt{MMM2}$,
$\mathtt{3s5z\\_vs\\_3s6z}$, $\mathtt{6h\\_vs\\_8z}$, $\mathtt{corridor}$),
one easy map ($\mathtt{1c3s5z}$), and one ourselves designed map
($\mathtt{3h\\_vs\\_1b1z3h}$) based on the SMAC benchmark. The comparison of
performance in other maps is shown in Appendix D.2.

Figure 6: Demonstration of $\mathtt{3h\\_vs\\_1b1z3h}$.

As shown in Figure 4, our algorithm based on the transformation and
distillation framework outperforms MAPPO in four out of six maps and
outperforms HAPPO in five out of six maps. Super hard maps are typically hard-
exploration tasks. However, taking benefit of the global optimality guarantee,
our approach can exploit better with the same exploration strategy as MAPPO
(based on the entropy of learned policies). We will highlight a map
$\mathtt{1c3s5z}$, where MAPPO converges to a locally optimal point but our
approach achieves global optimality with nearly 100$\%$ winning rate. This
phenomenon once again demonstrates the advantage of our sequential
transformation framework. HAPPO can also achieve a nearly 100$\%$ winning rate
on $\mathtt{1c3s5z}$ but fails on other maps. We believe it is still because
local optimality of Nash equilibrium learned by HAPPO. Meanwhile, compared
with our approach and MAPPO, agents cannot share parameters in HAPPO, which
significantly affects the training efficiency in complex tasks.

Figure 4 also demonstrates the validity of our transformation and distillation
framework. With sequential transformed information, TAD-PPO-T achieves
superior performance while enjoying the merits of global optimality. Although
TAD-PPO-T is not suitable for decentralized execution, its counterpart under
distillation, TAD-PPO, can execute in a decentralized manner with similar
performance.

We further discuss learning performance in our designed map
$\mathtt{3h\\_vs\\_1b1z3h}$, where we control three Hydralisks, while our
opponent controls three Hydralisks, one low-damage Zergling, and one Baneling
with high area damage. The initial positions of our controlled agents and
opposing agents are shown in Figure 6, where our agents are initialed on the
left side of the map. The explosion of the Baneling can only be avoided if all
agents gather fire to it instead of the nearer Zergling. However, gathering
fire to the Zergling could be a suboptimal equilibrium, because any agent’s
fire transfer from Zergling to Baneling will not influence the explosion of
Baneling but reduce the efficiency of killing Zergling. In this case, our
method can jump out of the local optimal point after 4M time steps, while the
state-of-the-art policy-based MARL algorithm MAPPO can only fall into the
local optimal point. This phenomenon emphasizes the superior advantages of our
algorithm in the environment with local optimal points.

###  6.3 Google Research Football

In this section, we test our approach against state-of-the-art policy-based
MARL baselines on another multi-agent benchmark named Google Research Football
(GRF). In GRF academic scenarios, we control left-side agents without the
goalkeeper and attempt to score facing opposing defenders and the opposing
goalkeeper. Following MAPPO (Yu et al., 2021), we use sparse rewards with both
SCORING and CHECKPOINT for our approach and all baselines, while using the
official simple 115-dimensional vector (Kurach et al., 2019) as the
observation. Each agent has a discrete action space of 19, including moving in
eight directions, sliding, shooting, and passing.

As shown in Figure 5, we benchmark our approach on three different GRF
scenarios, which are 2-agents control scenario
$\mathtt{Academy\\_Pass\\_and\\_Shoot\\_with\\_Keeper}$, 3-agents control
scenario $\mathtt{Academy\\_3\\_vs\\_1\\_with\\_Keeper}$, and 4-agents control
scenario $\mathtt{Academy\\_Counterattack\\_Hard}$. In GRF scenarios, agents
must coordinate timing and positions to organize offense to seize fleeting
opportunities. The cooperation between agents is difficult to coordinate
because of the sparsity of agents’ crucial movements. Our TAD framework forces
agents to consider the sequential information from previous ones during
training, which promotes coordination among agents for achieving sophisticated
cooperation. Compared with the state-of-the-art policy-based algorithm MAPPO,
our approach achieves superior performance in the most challenging scenario
$\mathtt{Academy\\_Counterattack\\_Hard}$. HAPPO achieves comparable
performance in $\mathtt{Academy\\_3\\_vs\\_1\\_with\\_Keeper}$ but fails in
the other two scenarios, further showing its weak adaptability in various
environments. Meanwhile, TAD-PPO still achieves similar performance to TAD-
PPO-T, illustrating the generality of our TAD framework.

##  7 Conclusion

In this paper, we study state-of-the-art cooperative multi-agent reinforcement
learning methods and find that, learning the decentralized policies with
gradient descent as multi-agent policy gradient algorithm and value-
decomposition algorithms may lead to a suboptimal solution. To character the
suboptimality, we theoretically prove two theorems indicating that the
decentralized structure will restrict the parameter space and thus make
gradient descent to get stuck in some local optima in these algorithms. To
solve this issue, we propose a novel Transformation And Distillation framework
that allows employing off-the-shelf single-agent reinforcement learning
methods to solve cooperative multi-agent tasks and retain their global
optimality guarantee. Based on this framework, we develop TAD-PPO that extends
single-agent PPO to multi-agent settings and significantly outperforms
baselines on various benchmark tasks. It is an interesting future direction to
extend efficient value-based SARL methods to multi-agent settings through our
transformation framework.

## References

  * Agarwal et al. (2019) Agarwal, A., Jiang, N., and Kakade, S. M.  Reinforcement learning: Theory and algorithms.  2019\.
  * Alonso-Mora et al. (2017) Alonso-Mora, J., Baker, S., and Rus, D.  Multi-robot formation control and object transport in dynamic environments via constrained optimization.  _The International Journal of Robotics Research_ , 36(9):1000–1021, 2017.
  * Angermueller et al. (2020) Angermueller, C., Dohan, D., Belanger, D., Deshpande, R., Murphy, K., and Colwell, L.  Model-based reinforcement learning for biological sequence design.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=HklxbgBKvr.
  * Bertsekas (2019) Bertsekas, D.  Multiagent rollout algorithms and reinforcement learning, 2019.  URL https://arxiv.org/abs/1910.00120.
  * Boutilier (1996) Boutilier, C.  Planning, learning and coordination in multiagent decision processes.  In _Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge_ , pp. 195–210. Morgan Kaufmann Publishers Inc., 1996\.
  * de Witt et al. (2020) de Witt, C. S., Gupta, T., Makoviichuk, D., Makoviychuk, V., Torr, P. H., Sun, M., and Whiteson, S.  Is independent learning all you need in the starcraft multi-agent challenge?  _arXiv preprint arXiv:2011.09533_ , 2020.
  * Degris et al. (2012) Degris, T., White, M., and Sutton, R. S.  Off-policy actor-critic.  _CoRR_ , abs/1205.4839, 2012.  URL http://arxiv.org/abs/1205.4839.
  * Foerster et al. (2018) Foerster, J. N., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S.  Counterfactual multi-agent policy gradients.  In _AAAI_ , 2018.
  * Fu et al. (2020) Fu, Z., Yang, Z., and Wang, Z.  Single-timescale actor-critic provably finds globally optimal policy, 2020\.  URL https://arxiv.org/abs/2008.00483.
  * Iqbal et al. (2021) Iqbal, S., De Witt, C. A. S., Peng, B., Böhmer, W., Whiteson, S., and Sha, F.  Randomized entity-wise factorization for multi-agent reinforcement learning.  In _International Conference on Machine Learning_ , pp. 4596–4606. PMLR, 2021.
  * Jain et al. (2022) Jain, M., Bengio, E., Garcia, A.-H., Rector-Brooks, J., Dossou, B. F. P., Ekbote, C., Fu, J., Zhang, T., Kilgour, M., Zhang, D., Simine, L., Das, P., and Bengio, Y.  Biological sequence design with gflownets, 2022.  URL https://arxiv.org/abs/2203.04115.
  * Konda & Tsitsiklis (1999) Konda, V. R. and Tsitsiklis, J. N.  Actor-critic algorithms.  In _NIPS_ , 1999.
  * Kraemer & Banerjee (2016) Kraemer, L. and Banerjee, B.  Multi-agent reinforcement learning as a rehearsal for decentralized planning.  _Neurocomputing_ , 190:82–94, 2016.
  * Kuba et al. (2021) Kuba, J. G., Chen, R., Wen, M., Wen, Y., Sun, F., Wang, J., and Yang, Y.  Trust region policy optimisation in multi-agent reinforcement learning.  _arXiv preprint arXiv:2109.11251_ , 2021.
  * Kuba et al. (2022) Kuba, J. G., Feng, X., Ding, S., Dong, H., Wang, J., and Yang, Y.  Heterogeneous-agent mirror learning: A continuum of solutions to cooperative marl, 2022.  URL https://arxiv.org/abs/2208.01682.
  * Kurach et al. (2019) Kurach, K., Raichuk, A., Stanczyk, P., Zajac, M., Bachem, O., Espeholt, L., Riquelme, C., Vincent, D., Michalski, M., Bousquet, O., and Gelly, S.  Google research football: A novel reinforcement learning environment.  _CoRR_ , abs/1907.11180, 2019.  URL http://arxiv.org/abs/1907.11180.
  * Li et al. (2021a) Li, C., Wang, T., Wu, C., Zhao, Q., Yang, J., and Zhang, C.  Celebrating diversity in shared multi-agent reinforcement learning.  _Advances in Neural Information Processing Systems_ , 34:3991–4002, 2021a.
  * Li et al. (2021b) Li, G., Cai, C., Chen, Y., Gu, Y., Wei, Y., and Chi, Y.  Is q-learning minimax optimal? a tight sample complexity analysis, 2021b.
  * Liu et al. (2019) Liu, B., Cai, Q., Yang, Z., and Wang, Z.  Neural proximal/trust region policy optimization attains globally optimal policy, 2019.  URL https://arxiv.org/abs/1906.10306.
  * Lowe et al. (2017) Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mordatch, I.  Multi-agent actor-critic for mixed cooperative-competitive environments.  _Neural Information Processing Systems (NIPS)_ , 2017.
  * Mei et al. (2020) Mei, J., Xiao, C., Szepesvári, C., and Schuurmans, D.  On the global convergence rates of softmax policy gradient methods.  _CoRR_ , abs/2005.06392, 2020.  URL https://arxiv.org/abs/2005.06392.
  * Mnih et al. (2013) Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M.  Playing atari with deep reinforcement learning, 2013.  URL https://arxiv.org/abs/1312.5602.
  * Munos & Szepesvari (2008) Munos, R. and Szepesvari, C.  Finite-time bounds for fitted value iteration.  _J. Mach. Learn. Res._ , 9:815–857, 2008.
  * Nemirovski et al. (2008) Nemirovski, A., Juditsky, A. B., Lan, G., and Shapiro, A.  Robust stochastic approximation approach to stochastic programming.  _SIAM J. Optim._ , 19:1574–1609, 2008.
  * Oliehoek et al. (2011) Oliehoek, F. A., Spaan, M. T. J., and Vlassis, N.  Optimal and approximate q-value functions for decentralized pomdps.  _CoRR_ , abs/1111.0062, 2011.  URL http://arxiv.org/abs/1111.0062.
  * Oliehoek et al. (2016) Oliehoek, F. A., Amato, C., et al.  _A concise introduction to decentralized POMDPs_ , volume 1.  Springer, 2016.
  * Olivecrona et al. (2017) Olivecrona, M., Blaschke, T., Engkvist, O., and Chen, H.  Molecular de novo design through deep reinforcement learning, 2017.  URL https://arxiv.org/abs/1704.07555.
  * Rashid et al. (2018) Rashid, T., Samvelyan, M., Witt, C. S. D., Farquhar, G., Foerster, J. N., and Whiteson, S.  Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning.  _ArXiv_ , abs/1803.11485, 2018.
  * Rashid et al. (2020) Rashid, T., Farquhar, G., Peng, B., and Whiteson, S.  Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning, 2020.  URL https://arxiv.org/abs/2006.10800.
  * Recht et al. (2011) Recht, B., Ré, C., Wright, S. J., and Niu, F.  Hogwild: A lock-free approach to parallelizing stochastic gradient descent.  In _NIPS_ , 2011.
  * Rozada et al. (2021) Rozada, S., Tenorio, V., and Marques, A. G.  Low-rank state-action value-function approximation, 2021.  URL https://arxiv.org/abs/2104.08805.
  * Samvelyan et al. (2019) Samvelyan, M., Rashid, T., Witt, C. S. D., Farquhar, G., Nardelli, N., Rudner, T. G. J., Hung, C.-M., Torr, P. H. S., Foerster, J. N., and Whiteson, S.  The starcraft multi-agent challenge.  _ArXiv_ , abs/1902.04043, 2019.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _ArXiv_ , abs/1707.06347, 2017.
  * Shalev-Shwartz et al. (2007) Shalev-Shwartz, S., Singer, Y., Srebro, N., and Cotter, A.  Pegasos: primal estimated sub-gradient solver for svm.  _Mathematical Programming_ , 127:3–30, 2007.
  * Son et al. (2019) Son, K., Kim, D., Kang, W. J., Hostallero, D. E., and Yi, Y.  Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning.  _ArXiv_ , abs/1905.05408, 2019.
  * Sunehag et al. (2018) Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V. F., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., and Graepel, T.  Value-decomposition networks for cooperative multi-agent learning.  _ArXiv_ , abs/1706.05296, 2018.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Van der Pol & Oliehoek (2016) Van der Pol, E. and Oliehoek, F. A.  Coordinated deep reinforcement learners for traffic light control.  _Proceedings of Learning, Inference and Control of Multi-Agent Systems (at NIPS 2016)_ , 2016.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I.  Attention is all you need, 2017.  URL https://arxiv.org/abs/1706.03762.
  * Wang et al. (2021a) Wang, J., Ren, Z., Han, B., Ye, J., and Zhang, C.  Towards understanding cooperative multi-agent q-learning with value factorization.  _Advances in Neural Information Processing Systems_ , 34, 2021a.
  * Wang et al. (2021b) Wang, J., Ren, Z., Liu, T., Yu, Y., and Zhang, C.  Qplex: Duplex dueling multi-agent q-learning.  _ArXiv_ , abs/2008.01062, 2021b.
  * Wang et al. (2021c) Wang, Y., Han, B., Wang, T., Dong, H., and Zhang, C.  Dop: Off-policy multi-agent decomposed policy gradients.  In _ICLR_ , 2021c.
  * Watkins & Dayan (1992) Watkins, C. and Dayan, P.  Q-learning.  _Machine Learning_ , 8:279–292, 1992.
  * Yao et al. (2021) Yao, H., Hsieh, P., Ho, K., Hu, K., Ouyang, L., and Wu, I.  Hinge policy optimization: Rethinking policy improvement and reinterpreting PPO.  _CoRR_ , abs/2110.13799, 2021.  URL https://arxiv.org/abs/2110.13799.
  * You et al. (2018) You, J., Liu, B., Ying, R., Pande, V., and Leskovec, J.  Graph convolutional policy network for goal-directed molecular graph generation, 2018.  URL https://arxiv.org/abs/1806.02473.
  * Yu et al. (2021) Yu, C., Velu, A., Vinitsky, E., Wang, Y., Bayen, A., and Wu, Y.  The surprising effectiveness of ppo in cooperative, multi-agent games.  _arXiv preprint arXiv:2103.01955_ , 2021.
  * Zhang & Lesser (2011) Zhang, C. and Lesser, V.  Coordinated multi-agent reinforcement learning in networked distributed pomdps.  In _Twenty-Fifth AAAI Conference on Artificial Intelligence_ , 2011\.

##  Appendix A Omitted Definitions in Section 3

###  A.1 RL Models

In single-agent RL (SARL), an agent interacts with a Markov Decision Process
(MDP) to maximize its cumulative reward (Sutton & Barto, 2018). An MDP is
defined as a tuple $(\mathcal{S},\mathcal{A},P,r,\gamma)$, where $\mathcal{S}$
and $\mathcal{A}$ denote the state space and action space. At each time step
$t$, the agent observes the state $s_{t}$ and chooses an action
$a_{t}\in\mathcal{A}$, where $a_{t}\sim\pi(s_{t})$ depends on $s_{t}$ and its
policy $\pi$. After that, the agent will gain an instant reward
$r_{t}=r(s_{t},a_{t})$, and transit to the next state $s_{t+1}\sim
P(\cdot|s_{t},a_{t})$. $\gamma$ is the discount factor. The goal of an SARL
agent is to optimize a policy $\pi$ that maximizes the expected cumulative
reward, i.e., $\mathcal{J}(\pi)=\mathbb{E}_{s_{t+1}\sim
P(\cdot{|s_{t},\pi(s_{t})})}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},\pi(s_{t}))\right]$.

we also present a framework of Multi-agent MDPs (MMDP) (Boutilier, 1996), a
special case of Dec-POMDP, to model cooperative multi-agent decision-making
tasks with full observations. MMDP is defined as a tuple
$\langle\mathcal{S},\mathcal{A},P,r,\gamma,n\rangle$, where $n$,
$\mathcal{S}$, $\mathcal{A}$, $P$, $r$, and $\gamma$ are state space,
individual action space, transition function, reward function, discount
factor, and the agent number in Dec-POMDP, respectively. Due to the full
observations, at each time step, the current state $s$ is observable to each
agent. For each agent $i$, an individual policy $\hat{\pi}_{i}(a|s)$
represents a distribution over actions conditioned on the state $s$. Agents
aim to find a joint policy
$\hat{\bm{\pi}}=\langle\hat{\pi}_{1},\dots,\hat{\pi}_{n}\rangle$ that
maximizes a joint value function $\widehat{V}^{\hat{\bm{\pi}}}(s)$, where
denoting
$\widehat{V}^{\hat{\bm{\pi}}}(s)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{t}|s_{0}=s,\hat{\bm{\pi}}\right]$.

##  Appendix B Omitted Proofs in Section 4

###  B.1 Some Lemmas for Gradient Descent and Local minima

Since we are going to analyze the behavior of gradient descent (GD), we
introduce some preliminaries and lemmas related to GD here.

GD in this paper is chosen to minimize some real-valued function $f(x)$. It
starts from some initial point $x_{0}$, and updates the points as
$x_{t+1}=x_{t}-\alpha\nabla f(x_{t})$, where $\alpha>0$ is a sufficiently
small constant learning rate. Classical analysis of GD requires the objective
function $f(x)$ to be smooth and $\alpha$ to be a sufficiently small (or
diminishing) learning rate to guarantee convergence to a local optimum.

The $L$-smoothness assumption is usually adopted, which says the derivative
function is $L$-Lipschitz.

######  Definition B.1 ($L$-smoothness).

A function $f(x)$ is said to be $L$-smooth, if its derivative function is
$L$-Lipschitz, i.e., $\forall x,x^{\prime}:\|\nabla f(x)-\nabla
f(x^{\prime})\|\leq L\|x-x^{\prime}\|$.

We then present several lemmas for $L$-smooth functions (Lemmas B.2, B.3 and
B.4), which are classical results in the analysis of gradient descent.

######  Lemma B.2.

Suppose $f$ is $L$-smooth, then $\forall x,x_{0}:f(x)\leq
f(x_{0})+\langle\nabla f(x_{0}),x-x_{0}\rangle+\frac{L}{2}\|x-x_{0}\|^{2}$.

###### Proof.

Let $g(t)=f(x_{0}+t(x-x_{0}))$, then $g(1)=f(x),g(0)=f(x_{0})$.

$\displaystyle f(x)-f(x_{0})$
$\displaystyle=g(1)-g(0)=\int_{0}^{1}g^{\prime}(t){\rm d}t$
$\displaystyle=\int_{0}^{1}\langle\nabla
f(x_{0}+t(x-x_{0})),x-x_{0}\rangle{\rm d}t$
$\displaystyle=\int_{0}^{1}\langle\nabla f(x_{0}+t(x-x_{0}))-\nabla
f(x_{0}),x-x_{0}\rangle{\rm d}t+\langle\nabla f(x_{0}),x-x_{0}\rangle$
$\displaystyle\leq\int_{0}^{1}\|\nabla f(x_{0}+t(x-x_{0}))-\nabla
f(x_{0})\|\cdot\|x-x_{0}\|{\rm d}t+\langle\nabla f(x_{0}),x-x_{0}\rangle$
$\displaystyle\leq\int_{0}^{1}Lt\|x-x_{0}\|\cdot\|x-x_{0}\|{\rm
d}t+\langle\nabla f(x_{0}),x-x_{0}\rangle$
$\displaystyle=\frac{L}{2}\|x-x_{0}\|^{2}+\langle\nabla
f(x_{0}),x-x_{0}\rangle$

∎

Then we have the following lemma for GD.

######  Lemma B.3.

Under the above conditions, if $\alpha\in\left(0,\frac{2}{L}\right)$, then
$f(x_{t+1})\leq f(x_{t})-c\|\nabla f(x_{t})\|^{2}$ for some constant $c>0$.

###### Proof.

$\displaystyle f(x_{t+1})$ $\displaystyle\leq f(x_{t})+\langle\nabla
f(x_{t}),x_{t+1}-x_{t}\rangle+\frac{L}{2}\|x_{t+1}-x_{t}\|^{2}$ (By Lemma B.2)
$\displaystyle=f(x_{t})+\langle\nabla f(x_{t}),-\alpha\nabla
f(x_{t})\rangle+\frac{L}{2}\alpha^{2}\|\nabla f(x_{t})\|^{2}$
$\displaystyle\leq f(x_{t})-\alpha\|\nabla
f(x_{t})\|^{2}+\frac{L}{2}\alpha^{2}\|\nabla f(x_{t})\|^{2}$
$\displaystyle=f(x_{t})-\alpha\left(1-\frac{L}{2}\alpha\right)\|\nabla
f(x_{t})\|^{2}$

Letting $c=\alpha\left(1-\frac{L}{2}\alpha\right)>0$ completes the proof.

∎

######  Lemma B.4.

Under the above conditions, if $\alpha\in\left(0,\frac{2}{L}\right)$, then
either $f(x)$ decreases to $-\infty$ or $f(x)$ converges and
$\lim_{t\rightarrow+\infty}\nabla f(x_{t})=0$. If $\\{x_{t}\\}$ converges, the
limiting point is a stationary point of $f$.

###### Proof.

The first part of this lemma is a corollary of Lemma B.3 and Monotone
Convergence Theorem. The second part can be proved by contradiction. Supposing
the limit point $x^{*}$ is not a stationary point, then $\nabla f(x^{*})$ is
non-zero due to the Lipschitz continuity, which derives a contradiction by
taking one-step gradient update over a sufficiently close $x_{t}$ near
$x^{*}$. ∎

Besides, the following lemma for local minima is simple but crucial in our
analysis.

######  Lemma B.5.

If $g$ is a continuous function, and $y_{0}=g(x_{0})$ is a local minimum of
the function $f(y)$, then $x_{0}$ is a local minimum of $f\circ g$.

###### Proof.

Since $y_{0}$ is a local minimum of $f(y)$, there exists a small open set
$O\ni y_{0}$, such that $\forall y\in O:f(y)\geq f(y_{0})$.

Due to the continuity of $g$, $O_{1}=g^{-1}(O)$ is also open. So that we can
find a small neighborhood $O_{2}$ of $x_{0}$, such that $x_{0}\in
O_{2}\subseteq O_{1}$, which implies $g(O_{2})\subseteq O$. Then we have
$\forall x\in O_{2}:f(g(x))\geq f(y_{0})=f(g(x_{0}))$. ∎

###  B.2 The Suboptimality Theorem for Multi-agent Policy Gradient Algorithm
(MA-PG)

Here we present a proof of Theorem 4.1.

Recall the policy factorization and the loss function of MA-PG:

$\displaystyle\forall
s\in\mathcal{S}:\quad\bm{\pi}(\bm{a}|s;\Theta)=\prod_{i=1}^{n}\pi_{i}(a_{i}|s;\Theta)$
(1) $\displaystyle\mathcal{L}(\Theta)=-\mathcal{J}(\bm{\pi}_{\Theta})$ (2)

To simplify our analysis, we abuse the notation a little bit to rewrite the
policy factorization as

$\displaystyle\forall
s\in\mathcal{S}:\quad\bm{\pi}(s;\Theta)=\bigotimes_{i=1}^{n}\pi_{i}(s;\Theta)$
(7)

where $\pi_{i}(s;\Theta)$ is now a probability vector in the probability
simplex $\Delta(\mathcal{A})$, and $\bm{\pi}(s;\Theta)$ is the tensor product
of these vectors.

We also use $L(\bm{\pi})=-\mathcal{J}(\bm{\pi})$ or
$L(\pi_{1},\cdots,\pi_{n})=-\mathcal{J}(\bigotimes\pi_{i})$ to represent the
loss of a policy, which is essentially the same as $\mathcal{L}$ except for
its domain.

Our analysis is based on the implicit assumptions:

######  Assumption B.6 (smoothness).

For all $s\in\mathcal{S}$, the function $\bm{\pi}(s;\Theta)$ is twice
differentiable.

######  Assumption B.7 (bounded gradient).

For all $s\in\mathcal{S},i\in\\{1,\cdots,n\\}$, $\|\nabla\pi_{i}(s;\Theta)\|$
and $\|\nabla^{2}\pi_{i}(s;\Theta)\|$ are bounded.

######  Assumption B.8 (completeness).

For all $s\in\mathcal{S}$, all probability distribution in the product space
$\bigtimes_{i=1}^{n}\Delta(\mathcal{A})$ is representable by
$\bm{\pi}(s;\Theta)$.

The smoothness assumption is common. The bounded gradient assumption is also
wildly used in analyzing GD and non-convex optimization problems(Recht et al.,
2011; Nemirovski et al., 2008; Shalev-Shwartz et al., 2007). The completeness
assumption (or regularity assumption) is made to prevent degenerated cases
such as the function being a constant ($\Theta$ does not affect the policy),
which is of little significance to analyze.

######  Theorem 4.1.

There are tasks such that, when the parameter $\Theta$ is initialized in
certain region $S$ with positive volume, MA-PG (Equations 1 and 2) converges
to a suboptimal policy with a small enough learning rate $\alpha$.

###### Proof.

We prove the theorem in three steps. First, we construct a matrix game just
like Table 1, which is a 1-step MMDP. Second, we prove the loss function in
this task contains $\Omega(|\mathcal{A}|)$ suboptimal local minima. Finally,
we prove that for each local minima we construct, there is a neighborhood $S$,
such that the gradient descent process will never escape from it with a small
enough learning rate. Moreover, the policy will converge.

We construct a 2-agent matrix game here with the payoff matrix $M$:

$M=\left(\begin{array}[]{cccc}1&0&\cdots&0\\\ 0&2&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&|\mathcal{A}|\end{array}\right)$

Since there is only one state, we omit the state $s$ in our policy.

We claim that for any deterministic policy selecting the entry of the diagonal
of $M$, the corresponding $\Theta$ is a local minimum of $\mathcal{L}$, where
the existence of $\Theta$ is guaranteed by B.8.

That is, we have $\Theta_{1},\cdots,\Theta_{|\mathcal{A}|}$ such that
$\bm{\pi}(\Theta_{i})$ is the deterministic policy selecting the entry
$M_{i,i}$. And if the claim is true, $\Theta_{i}$ will be a suboptimal local
minimum of $\mathcal{L}$ for $i=1,\cdots,|\mathcal{A}|-1$.

We now prove that for any $i\in\\{1,\cdots,|\mathcal{A}|\\}$, $\Theta_{i}$ is
a local minimum.

Fix some $i$. Denote $\bm{p}=\bm{q}=\delta_{i}$, where
$\delta_{i}\in\Delta(|\mathcal{A}|)$ is the one-hot probability vector
indicating the deterministic policy of selecting the $i$-th action. By
definition of $\Theta_{i}$, we have
$\bm{\pi}(\Theta_{i})=\bm{p}\otimes\bm{q}$.

The payoff of joint policy $\bm{\pi}(\Theta_{i})$ is thus
$\mathcal{J}(\bm{\pi}(\Theta_{i}))=\bm{p}^{\top}M\bm{q}$. Now we investigate
some policy $\bm{p}^{\prime}\otimes\bm{q}^{\prime}$ in a sufficiently small
neighborhood of $\bm{p}\otimes\bm{q}$ in the product space.

Denote
$\Delta\bm{p}=(\bm{p}-\bm{p}^{\prime}),\Delta\bm{q}=(\bm{q}-\bm{q}^{\prime}),\epsilon_{1}=\min\\{\frac{1}{2}\|\Delta\bm{p}\|_{1},\frac{1}{2}\|\Delta\bm{q}\|_{1}\\},\epsilon_{2}=\max\\{\frac{1}{2}\|\Delta\bm{p}\|_{1},\frac{1}{2}\|\Delta\bm{q}\|_{1}\\}$.
We have
$\epsilon_{2}\geq\Delta\bm{p}(i),\Delta\bm{q}(i)\geq\epsilon_{1},-\epsilon_{1}\geq\Delta\bm{p}(j),\Delta\bm{q}(j)\geq-\epsilon_{2}$,
for $j\neq i$.

Therefore,

$\displaystyle\bm{p}^{\prime\top}M\bm{q}^{\prime}$
$\displaystyle=(\bm{p}-\Delta\bm{p})^{\top}M(\bm{q}-\Delta\bm{q})$
$\displaystyle=\mathcal{J}(\bm{p},\bm{q})-\Delta\bm{p}^{\top}M\bm{q}-\bm{p}^{\top}M\Delta\bm{q}+\Delta\bm{p}^{\top}M\Delta\bm{q}$
$\displaystyle=\mathcal{J}(\bm{p},\bm{q})-\delta_{i}^{\top}M(\Delta\bm{p}+\Delta\bm{q})+\Delta\bm{p}^{\top}M\Delta\bm{q}$
$\displaystyle=\mathcal{J}(\bm{p},\bm{q})-i(\Delta\bm{p}(i)+\Delta\bm{q}(i))+\sum_{k=1}^{|\mathcal{A}|}k\Delta\bm{p}(k)\Delta\bm{q}(k)$
$\displaystyle\leq\mathcal{J}(\bm{p},\bm{q})-(\epsilon_{1}+\epsilon_{2})+\epsilon_{2}^{2}|\mathcal{A}|^{2}$
$\displaystyle=\mathcal{J}(\bm{p},\bm{q})-\Omega(\epsilon_{2})+O(\epsilon_{2}^{2})$
(8) $\displaystyle<\mathcal{J}(\bm{p},\bm{q})$

This inequality suggests that $\delta_{i}\otimes\delta_{i}$ is a local minimum
of the payoff in the space $\Delta(|A|)^{2}$.

Then due to the continuity of $\bm{\pi}(\Theta)$ (B.6), $\Theta_{i}$ would be
a local minimum of $\mathcal{L}(\Theta)$ in the space $\text{dom}(\Theta)$ by
Lemma B.5.

We now prove the for all $i=1,\cdots,|\mathcal{A}|-1$, there is a neighborhood
$S$ of $\Theta_{i}$, such that for all $\Theta\in S$, a gradient update
$\Theta^{\prime}\leftarrow\Theta-\alpha\nabla\mathcal{L}(\Theta)$ still lies
in $S$ for small enough $\alpha$.

In general, the local optimality does not imply local convexity111Consider a
$C^{\infty}$ function $f(x)=\exp(-1/x^{2})(\sin(1/x)+1)$ at $x=0$., and
therefore no local convergence result is guaranteed for GD by initializing
near a local optimum. However in this case, our function has a higher-level
structure in the space $\Delta(|\mathcal{A}|)^{2}$, which is essential for us
to establish our result.

We fix some $i\in\\{1,\cdots,|\mathcal{A}|-1\\}$.

Denote
$p(\Theta)=(\pi_{1}(\Theta),\pi_{2}(\Theta))\in\Delta(|\mathcal{A}|)^{2}$, and
let $x=p(\Theta_{i})$.222Note that the range of $p$ is
$\Delta(|\mathcal{A}|)^{2}=\Delta(|\mathcal{A}|)\times\Delta(|\mathcal{A}|)$,
while the range of $\bm{\pi}$ is $\Delta(|\mathcal{A}|^{2})$. Let $\epsilon>0$
be a sufficiently small constant to be determined later. In the space
$\Delta(|\mathcal{A}|)^{2}$, we consider an open ball $B_{\epsilon}(x)$
centered at $x$ with radius $\epsilon$, where the distance is the total
variation $\|\cdot\|_{TV}$, i.e., half-$L^{1}$-norm
$\frac{1}{2}\|\cdot\|_{1}$. The selection of the norm is not crucial, since
all norms on a finite-dimensional linear space are equivalent333This is a
classical result in finite linear space:
$\forall\|\cdot\|_{1},\|\cdot\|_{2}\exists
c_{1},c_{2}>0:c_{1}\|\cdot\|_{1}\leq\|\cdot\|_{2}\leq c_{2}\|\cdot\|_{1}$..

We let $R=p^{-1}(B_{\epsilon}(x))\ni\Theta_{i}$. And for any $\theta\in R$,
denote the gradient update at $\theta$ as
$s_{\theta}=-\alpha\nabla\mathcal{L}(\theta)$. Adopting the notations above,
we prove the following lemma.

######  Lemma B.9.

$\mathcal{L}(\theta+s_{\theta})\leq\mathcal{L}(\theta)$ for sufficiently small
$\alpha$.

###### Proof.

According to B.7, we have $\|\nabla p(\Theta)\|$ and $\|\nabla^{2}p(\Theta)\|$
are bounded by some constant $G$. Then for any $\Theta$, by applying the chain
rule and the product rule of gradient, we have

$\displaystyle\|\nabla^{2}\mathcal{L}(\Theta)\|$
$\displaystyle=\|\nabla^{2}p(\Theta)\nabla L(x)+\nabla
p(\Theta)\nabla^{2}L(x)\|$ $\displaystyle\leq\|\nabla^{2}p(\Theta)\|\|\nabla
L(x)\|+\|\nabla p(\Theta)\|\|\nabla^{2}L(x)\|$ $\displaystyle\leq
G|\mathcal{A}|+G\sqrt{|\mathcal{A}|}$

Let $H=G|\mathcal{A}|+G\sqrt{|\mathcal{A}|}$, then $\nabla\mathcal{L}$ is
$H$-Lipschitz by the mean-value theorem, which means $\mathcal{L}$ is
$H$-smooth.

Then by Lemma B.3, $\mathcal{L}(\theta+s_{\theta})$ is not increasing by
making $\alpha<2/H$.

∎

We further denote $S_{\delta}=\\{y\in\Delta(|\mathcal{A}|)^{2}:L(y)\leq
L(x)+\delta\\}\cap B_{\epsilon}(x)$. Here comes the key lemma.

######  Lemma B.10.

There exist $\delta,\epsilon^{\prime},\epsilon$, such that

  1. 1.

$\delta>0$ and $0<\epsilon^{\prime}<\epsilon$.

  2. 2.

$S_{\delta}\subset B_{\epsilon^{\prime}}(x)\subset B_{\epsilon}(x)$.

###### Proof.

Recall that $x=p(\Theta_{i})=(\delta_{i},\delta_{i})$. Let
$y=(\bm{p},\bm{q})\in B_{\epsilon}(x)$, solve the inequality
$L(y)=-\bm{p}^{\top}M\bm{q}\leq L(x)+\delta$, we have,444$\delta$ here is a
small constant, while $\delta_{i}$ is the one-hot vector defined before.

$\displaystyle-\left(i(1-\|\delta_{i}-\bm{p}\|)(1-\|\delta_{i}-\bm{q}\|)+\sum_{(u,v)\neq(i,i)}M(u,v)\bm{p}(u)\bm{q}(v)\right)$
$\displaystyle\leq-i+\delta$ $\displaystyle
i\|x-y\|-i\|\delta_{i}-\bm{p}\|\|\delta_{i}-\bm{q}\|-\sum_{(u,v)\neq(i,i)}M(u,v)\bm{p}(u)\bm{q}(v)$
$\displaystyle\leq\delta$ $\displaystyle\|x-y\|$
$\displaystyle\leq\frac{1}{i}\left(\delta+|\mathcal{A}|^{3}\|x-y\|^{2}\right)$
$\displaystyle\|x-y\|$
$\displaystyle\leq\frac{1}{i}\left(\delta+\epsilon^{2}|\mathcal{A}|^{3}\right)$
(9)

We choose $\epsilon$ and $\delta$ small enough such that
$0<\delta<i\epsilon/3-\epsilon^{2}|\mathcal{A}|^{3}$, then we will have
$\|x-y\|<\epsilon/2$ by plugging it into Equation 9. This suggests that
$S_{\delta}\subset B_{\epsilon/2}(x)\subset B_{\epsilon}(x)$ and completes our
proof. ∎

By Lemma B.10, we can find some $\delta>0$ and $0<\epsilon^{\prime}<\epsilon$,
such that $S_{\delta}\subset B_{\epsilon^{\prime}}(x)\subset B_{\epsilon}(x)$.
Then for any $\theta\in p^{-1}(S_{\delta})$, we have

  1. 1.

$p(\theta+s_{\theta})\in\\{y\in\Delta(|\mathcal{A}|)^{2}:L(y)\leq
L(x)+\delta\\}$, because $\mathcal{L}(\theta+s_{\theta})$ is not increasing
(Lemma B.9);

  2. 2.

$p(\theta+s_{\theta})\in B_{\epsilon}(x)$ by letting $\alpha$ small enough
such that $\alpha<\frac{1}{2G^{2}}(\epsilon-\epsilon^{\prime})$, where $G$ is
an upper bound of $\|\nabla p(\theta)\|$ (B.7).

The second bullet holds because

$\displaystyle\|p(\theta+s_{\theta})-p(\theta)\|$ $\displaystyle\leq
G\|s_{\theta}\|$ (B.7 and mean-value theorem) $\displaystyle=\alpha G\|\nabla
p(\theta)\|$ $\displaystyle\leq\alpha G^{2}$ (B.7)
$\displaystyle=(\epsilon-\epsilon^{\prime})/2$

These give us $\forall\theta\in p^{-1}(S_{\delta}):\theta+s_{\theta}\in
p^{-1}(S_{\delta})$. Again by the local $H$-smoothness and Lemma B.4, we are
able to claim that $\mathcal{L}(\theta)$ converges to a suboptimal value when
$\theta$ is initialized in $S_{\delta}$.

∎

###  B.3 The Suboptimality Theorems for Value-decomposition Algorithms (VD)

We are going to present three suboptimality theorems here for VD
progressively. To start with, we recall the definition of VD (Equations 5, 3
and 4).

Value-decomposition: $\displaystyle
Q(s,\bm{a};\Theta)=f_{\text{mix}}(Q_{1}(s,\cdot),\cdots,Q_{n}(s,\cdot),s,\bm{a};\Theta)$
(5) Loss function:
$\displaystyle\mathcal{L}(\Theta)=\frac{1}{2}\mathbb{E}_{s,\bm{a}}\left[Q(s,\bm{a};\Theta)-(\mathcal{T}Q_{\Theta})(s,\bm{a})\right]^{2}$
(3) IGM condition: $\displaystyle\forall
s:\quad\mathop{\arg\max}_{\bm{a}\in\bm{\mathcal{A}}}Q(s,\bm{a})\supseteq\bigtimes_{i=1}^{n}\mathop{\arg\max}_{a_{i}\in\mathcal{A}}Q_{i}(s,a_{i})$
(4)

To reduce unnecessary difficulties in understanding, we explicitly describe
the joint Q-value as a function $f_{\text{mix}}$ of individual Q-values in
Equation 5, which is the origin of the name “value-decomposition”. However,
one may notice that, since the local Q-functions $Q_{1},\cdots,Q_{n}$ are also
parameterized by $\Theta$, then it is unnecessary for the joint Q-function to
take local Q-values as inputs. That is, Equation 5 is redundant. The only
thing we need is to have $n+1$ functions satisfying Equation 4, where one is
the joint Q-function $Q(s,\bm{a};\Theta)$, and the other $n$ are the local
Q-functions $Q_{1}(s,a_{1};\Theta),\cdots,Q_{n}(s,a_{n};\Theta)$, all
parameterized by $\Theta$.

So that our definition of VD goes beyond the original form of “value-
decomposition”.

To facilitate our analysis, we first introduce two kinds of completeness here.

######  Definition B.11 (Completeness of $Q$-function Class).

Consider a value-decomposition algorithm $D$ (Equations 4 and 3). We denote
$\mathcal{S},\mathcal{A},n$ as the state space, individual action space and
the number of agents here.

$D$ is said to have a complete Q-function class if for any
$f\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$, there is a
$\Theta\in\text{dom}(\Theta)$, such that $\forall
s\in\mathcal{S},\bm{a}\in\mathcal{A}^{n}:Q(s,\bm{a};\Theta)=f(s,\bm{a})$.

Further more, $D$ is said to have an IGM-complete Q-function class if for any
$f\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$, and for any deterministic
joint policy $\bm{\pi}:\mathcal{S}\rightarrow\mathcal{A}^{n}$ such that
$\forall s\in\mathcal{S}:\bm{\pi}(s)\in\operatorname*{arg\,max}f(s,\cdot)$,
there is a $\Theta\in\text{dom}(\Theta)$, such that

  1. 1.

$\forall
s\in\mathcal{S},\bm{a}\in\mathcal{A}^{n}:Q(s,\bm{a};\Theta)=f(s,\bm{a})$.

  2. 2.

$\forall
i\in[n],s\in\mathcal{S}:\operatorname*{arg\,max}Q_{i}(s,\cdot;\Theta)=\\{\pi_{i}(s)\\}$,
where $\bm{\pi}=(\pi_{1},\cdots,\pi_{n})$.

In a nutshell, the completeness says we can factorize any joint Q-function in
$\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ into local Q-functions
$Q_{1},\cdots,Q_{n}$ by some parameter $\Theta$, while the IGM-completeness
says that when factorizing some joint Q-function with multiple greedy policies
(i.e., $\exists s:|\operatorname*{arg\,max}Q(s,\cdot)|>1$), we can select any
one of them such that after factorization, the greedy policies of local
Q-functions are consistent to the selected greedy policy.555The IGM-
completeness is a mild and natural restriction of the completeness when the
IGM condition is satisfied. QPLEX(Wang et al., 2021b) satisfies the IGM-
completeness.

Then we abuse notations similar to the case of MA-PG (Section B.2).

For all $i\in\\{1,\cdots,n\\}$, we denote
$Q_{i}(\Theta)\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$, where
$Q_{i}(\Theta)(s,a)=Q_{i}(s,a;\Theta)$.

Similarly, denoting
$Q(\Theta)\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}^{n}}$, where
$Q(\Theta)(s,\bm{a})=Q(s,\bm{a};\Theta)$.

We also use
$L(f)=\frac{1}{2}\mathbb{E}_{s,\bm{a}}\left[f(s,\bm{a})-(\mathcal{T}f)(s,\bm{a})\right]^{2}$,
where $f\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}^{n}}$ and $\mathcal{T}$ is
the Bellman operator. $L$ is essentially the same as $\mathcal{L}$ except its
domain.

Before we prove Theorem 4.2, we introduce two more versions of the
suboptimality theorems for VD (Theorems B.12 and B.14).

######  Theorem B.12.

There are tasks such that, when the parameter $\Theta$ is initialized in
certain set $S$, any VD with an IGM-complete function class converges to a
suboptimal policy.

###### Proof.

Our proof contains 4 parts.

We will first construct an $n$-player matrix game, which is a $1$-step MMDP.
Second, we will find a series of functions
$f^{(j)}\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}^{n}}$, such that for all
$j$, $f^{(j)}$ is a local optimum of $L$ in a restricted space $R$. Third, we
decompose $f^{(j)}$ by the value decomposition scheme to find a $\Theta^{(j)}$
such that $Q(\Theta^{(j)})=f^{(j)}$. Finally, we prove that $\Theta^{(j)}$ is
a local minimum of $\mathcal{L}$ by Lemma B.5 after showing that the function
$Q:\text{dom}(\Theta)\rightarrow\mathbb{R}^{\mathcal{S}\times\mathcal{A}^{n}}$
is a locally a function with range in $R$ (i.e.,
$Q:\text{dom}(\Theta)\rightarrow R$ near $\Theta^{(j)}$).

We arbitrarily choose the one-step payoff function (the $n$-dimensional matrix
in the $n$-player matrix game) $T\in\mathbb{R}^{|\mathcal{A}|^{n}}$ with
different values on all entries. Since this is a $1$-step game, we omit the
state in our formulation. We also have $\mathcal{T}f=T$ for any value function
$f\in\mathbb{R}^{|\mathcal{A}|^{n}}$ since the task lasts only for $1$ step.
And the loss function can be simplified as follows.

$\mathcal{L}(\Theta)=\frac{1}{2}\mathbb{E}_{\bm{a}\sim\mathcal{D}}\left[Q(\bm{a};\Theta)-T(\bm{a})\right]^{2}$

for some distribution $\mathcal{D}$ fully supported on $\mathcal{A}^{n}$.

Let $\bm{a}^{*}$ be any joint action in $\mathcal{A}^{n}$. Denote the
restricted value function space
$\mathcal{R}(\bm{a}^{*})=\\{f\in\mathbb{R}^{|\mathcal{A}|^{n}}:\bm{a}^{*}\in\operatorname*{arg\,max}f(\cdot)\\}$
as the set of matrices with $\bm{a}^{*}$ as its greedy action (may not be
unique).

We present the following lemma.

######  Lemma B.13.

The set $\operatorname*{arg\,min}_{f\in\mathcal{R}(\bm{a}^{*})}L(f)$ contains
exactly one element.

###### Proof.

We first note that $\mathcal{R}(\bm{a}^{*})$ is convex in that for any
$f_{1},f_{2}\in\mathcal{R}(\bm{a}^{*})$ and $\beta\in[0,1]$, we have

$\displaystyle\forall\bm{a}:\quad(\beta f_{1}+(1-\beta)f_{2})(\bm{a}^{*})$
$\displaystyle=\beta f_{1}(\bm{a}^{*})+(1-\beta)f_{2}(\bm{a}^{*})$
$\displaystyle\geq\beta f_{1}(\bm{a})+(1-\beta)f_{2}(\bm{a})$
$\displaystyle=(\beta f_{1}+(1-\beta)f_{2})(\bm{a})$

so that $(\beta f_{1}+(1-\beta)f_{2})\in\mathcal{R}(\bm{a}^{*})$.

Denote $S=\operatorname*{arg\,min}_{f\in\mathcal{R}(\bm{a}^{*})}L(f)$. It is
obvious that $S$ is non-empty. Suppose $f_{1},f_{2}$ are two different element
in $S$, we investigate the loss of $f=(f_{1}+f_{2})/2$, which is also in
$\mathcal{R}(\bm{a}^{*})$ by the convexity.

Since $f_{1}\neq f_{2}$, there exists some $\tilde{\bm{a}}$ such that
$f_{1}(\tilde{\bm{a}})\neq f_{2}(\tilde{\bm{a}})$. Denote
$l(x,c)=\frac{1}{2}(x-c)^{2}$, which is a strict convex function for any fixed
$c$, we have

$\displaystyle L(f)$
$\displaystyle=\frac{1}{2}\mathbb{E}_{\bm{a}\in\mathcal{D}}[f({\bm{a}})-T({\bm{a}})]^{2}$
$\displaystyle=\sum_{\bm{a}}\mathcal{D}(\bm{a})l(f({\bm{a}}),T({\bm{a}}))$
$\displaystyle<\sum_{\bm{a}}\mathcal{D}(\bm{a})\left(\frac{1}{2}l(f_{1}({\bm{a}}),T({\bm{a}}))+\frac{1}{2}l(f_{2}({\bm{a}}),T({\bm{a}}))\right)$
$\displaystyle=\frac{1}{2}(L(f_{1})+L(f_{2}))$ $\displaystyle=L(f_{1})$

where the inequality is by Jensen’s inequality, the strict inequivalence holds
since $f_{1}(\tilde{\bm{a}})\neq f_{2}(\tilde{\bm{a}})$. This contradicts the
fact that $f_{1}$ minimizes $L$ in $\mathcal{R}(\bm{a}^{*})$. ∎

By Lemma B.13, the minimizer is unique. Therefore we denote $f_{\bm{a}^{*}}$
be the only element in
$\operatorname*{arg\,min}_{f\in\mathcal{R}(\bm{a}^{*})}L(f)$.

It is obvious that $f_{\bm{a}^{*}}$ is not the globally optimal solution for
$L$ in $\mathbb{R}^{|\mathcal{A}|^{n}}$ unless
$\bm{a}^{*}\in\operatorname*{arg\,max}T(\cdot)$ since the globally optimal
solution is exactly $T$ itself.

Now by IGM-completeness, we can find a $\Theta_{\bm{a}^{*}}$ such that
$Q(\Theta_{\bm{a}^{*}})=f_{\bm{a}^{*}}$, and
$\operatorname*{arg\,max}Q_{i}(\Theta_{\bm{a}^{*}})(\cdot)=\\{\bm{a}^{*}(i)\\}$,
for $i=1,\cdots,n$.

Since
$\operatorname*{arg\,max}Q_{i}(\Theta_{\bm{a}^{*}})(\cdot)=\\{\bm{a}^{*}(i)\\}$,
we know that the largest action value in $Q_{i}(\Theta_{\bm{a}^{*}})(\cdot)$
is strictly larger than the second largest action value. Therefore by the
continuity of $Q_{i}$, there is a small neighborhood
$O\ni\Theta_{\bm{a}^{*}}$, such that $\forall\Theta\in
O:\operatorname*{arg\,max}Q_{i}(\Theta)(\cdot)=\\{\bm{a}^{*}(i)\\}$ for all
$i\in\\{1,\cdots,n\\}$, and the
$\bm{a}^{*}\in\operatorname*{arg\,max}Q(\Theta)$ by IGM (Equation 4).

Therefore, we have $Q(\Theta)\in\mathcal{R}(\bm{a}^{*})$ for all $\Theta\in
O$. And consequently $\mathcal{L}(\Theta)=L(Q(\Theta))\geq
L(f_{\bm{a}^{*}})=\mathcal{L}(\Theta_{\bm{a}^{*}})$, which means we find a
local minimum $\Theta_{\bm{a}^{*}}$ for $\mathcal{L}$.

In this way, let
$S=\\{\Theta_{\bm{a}^{*}}:\bm{a}^{*}\not\in\operatorname*{arg\,max}T(\cdot)\\}$.
When initialized in $S$, gradient descent will get stuck since the gradient is
zero at all local minima, resulting in a suboptimal policy. ∎

Comparing Theorem 4.2 and Theorem B.12, we shall see that the statement for VD
with a complete class and that for VD with an IGM-complete class only differ
in the order of the logical predicates. That is, for any VD with a complete
class, we can construct tasks to make it fail, while we can construct tasks
make all VD fail uniformly when an IGM-complete class is equipped.

This difference might not be essential, in that if we add some regularity
constraint for VD with a complete class (e.g., some compactness assumptions),
we can still find tasks uniformly make VD fail (Theorem B.14).

Based on the principle of conducting intuitions, we are not going deep.

######  Theorem B.14.

There are tasks such that, when the parameter $\Theta$ is initialized in
certain set $S$, any VD with an complete function class as well as a $Q$ such
that its inversion keeps boundedness (i.e., for all bounded $X$, $Q^{-1}(X)$
is also bounded) converges to a suboptimal policy.

###### Proof.

We continue to use notations defined in the proof of Theorem B.12.

The argument in the proof of Theorem B.12 fails here since the factorization
$f_{\bm{a}^{*}}=Q(\Theta_{\bm{a}^{*}})$ cannot be guaranteed to have
$\\{\bm{a}^{*}(i)\\}=\operatorname*{arg\,max}Q_{i}(\cdot)$ for $i=1,\cdots,n$
when $f_{\bm{a}^{*}}$ has multiple greedy actions (i.e.,
$|\operatorname*{arg\,max}f_{\bm{a}^{*}}(\cdot)|>1$).

To solve the issue, we construct a special matrix game, where

$T(\bm{a})=\left\\{\begin{array}[]{ll}i,&a_{1}=a_{2}=\cdots=a_{n}=i\\\
0,&\text{otherwise}\end{array}\right.$

Consider all $\bm{a}^{*}$ in form of $(k,\cdots,k)$ for
$k=1,\cdots,|\mathcal{A}|-1$.

Let
$f_{m}(\bm{a})=\left\\{\begin{array}[]{ll}f_{\bm{a}^{*}}(\bm{a})-\frac{1}{m},&\bm{a}^{*}\neq\bm{a}\in\operatorname*{arg\,max}f_{\bm{a}^{*}}(\cdot)\\\
f_{\bm{a}^{*}}(\bm{a}),&\text{otherwise}\end{array}\right.$ for
$m\in\mathbb{N}$.

Then $\operatorname*{arg\,max}f_{m}(\cdot)=\\{\bm{a}^{*}\\}$ for all
$m\in\mathbb{N}$.

By the completeness of Q-function class, we are able to find some
$\Theta_{m}$, such that $f_{m}=Q(\Theta_{m})$. By the uniqueness of greedy
policy of $f_{m}$, we have for all $a_{i}\in\mathcal{A}$ other than $k$:
$Q_{i}(k;\Theta_{m})>Q_{i}(a_{i};\Theta_{m})$ for $i=1,\cdots,n$.

Consider the set
$R=Q^{-1}\left(\overline{B}_{1}(f_{\bm{a}^{*}})\right)$.666Here
$\overline{B}_{1}(f_{\bm{a}^{*}})$ is the closed Ball centered at
$f_{\bm{a}^{*}}$ with radius $1$ (w.r.t. the $L^{\infty}$ distance
$\|\cdot\|_{\infty}$). $R$ is closed since $Q$ is continuous. And $R$ is also
bounded, since $Q^{-1}$ keeps boundedness.

In this way, $R$ is compact. By Bolzano Weierstrass Theorem, we can find a
convergent subsequence $\\{\Theta_{m_{j}}\\}_{j=1}^{\infty}$. Take the limit,
we have $\Theta_{m_{j}}\rightarrow\Theta_{\bm{a}^{*}}\in R$. By the
continuity, we have
$Q(\Theta_{\bm{a}^{*}})=\lim\limits_{m\rightarrow\infty}f_{m}=f_{\bm{a}^{*}}$,
and $\forall a_{i}\in\mathcal{A}:Q_{i}(k;\Theta_{\bm{a}^{*}})\geq
Q_{i}(a_{i};\Theta_{\bm{a}^{*}})$ for $i=1,\cdots,n$, which means
$k\in\operatorname*{arg\,max}Q_{i}(\Theta_{\bm{a}^{*}})$

According to the argument of Theorem B.12, the only thing remains for us is to
prove $\\{k\\}=\operatorname*{arg\,max}Q_{i}(\Theta_{\bm{a}^{*}})$ for all
$i\in\\{1,\cdots,n\\}$.

To prove it, we need the following lemma.

######  Lemma B.15.

For the $n$-dimensional matrix $T$ defined above, any
$k\in\\{1,\cdots,|\mathcal{A}|\\}$ and $\bm{a}^{*}=(k,\cdots,k)$, we have

  1. 1.

$f_{\bm{a}^{*}}(\bm{a})>0$ for all $\bm{a}$ on the diagonal (i.e.,
$\bm{a}=(t,\cdots,t)$ for some $t\in\\{1,\cdots,|\mathcal{A}|\\}$).

  2. 2.

$f_{\bm{a}^{*}}(\bm{b})=0$ for all $\bm{b}$ not on the diagonal (i.e.,
$\bm{b}\neq(t,\cdots,t)$ for any $t\in\\{1,\cdots,|\mathcal{A}|\\}$).

###### Proof.

First, we can claim $f_{\bm{a}^{*}}(\bm{a}^{*})\geq 1$. Since if
$f_{\bm{a}^{*}}(\bm{a}^{*})<1$, we can let
$g(\bm{u})=\left\\{\begin{array}[]{ll}1,&\bm{u}=\bm{a}^{*}\\\
f_{\bm{a}^{*}}(\bm{u}),&\text{otherwise}\end{array}\right.$, and in this way
we have

  1. 1.

$g\in\mathcal{R}(\bm{a}^{*})$ in that $g(\bm{a}^{*})=1\geq
f_{\bm{a}^{*}}(\bm{a}^{*})\geq f_{\bm{a}^{*}}(\bm{u})=g(\bm{u})$ for all
$\bm{u}\neq\bm{a}^{*}$.

  2. 2.

$L(g)<L(f_{\bm{a}^{*}})$ in that

    1. (a)

$L(g)-L(f_{\bm{a}^{*}})=\frac{1}{2}\mathcal{D}(\bm{a}^{*})[(1-T(\bm{a}^{*}))^{2}-(f_{\bm{a}^{*}}(\bm{a}^{*})-T(\bm{a}^{*}))^{2}]$.

    2. (b)

$f_{\bm{a}^{*}}(\bm{a}^{*})<1\leq T(\bm{a}^{*})$.

which contradicts the definition of $f_{\bm{a}^{*}}$.

Secondly, we prove the original lemma again by contradiction similarly.

Suppose we have $f_{\bm{a}^{*}}(\bm{a})\leq 0$ for some $\bm{a}$ on the
diagonal, we can let $g(\bm{u})=\left\\{\begin{array}[]{ll}1,&\bm{u}=\bm{a}\\\
f_{\bm{a}^{*}}(\bm{u}),&\text{otherwise}\end{array}\right.$. This also results
in $g\in\mathcal{R}(\bm{a}^{*})$ and $L(g)<L(f_{\bm{a}^{*}})$, which
contradicts the definition of $f_{\bm{a}^{*}}$.

Suppose we have $f_{\bm{a}^{*}}(\bm{b})>0$ for some $\bm{b}$ not on the
diagonal, we can let $g(\bm{u})=\left\\{\begin{array}[]{ll}0,&\bm{u}=\bm{b}\\\
f_{\bm{a}^{*}}(\bm{u}),&\text{otherwise}\end{array}\right.$. This also results
in $g\in\mathcal{R}(\bm{a}^{*})$ and $L(g)<L(f_{\bm{a}^{*}})$, which
contradicts the definition of $f_{\bm{a}^{*}}$.

∎

Then we prove it by contradiction. Suppose that there are some $i$, and
$a_{i}\neq k$, such that
$Q_{i}(k;\Theta_{\bm{a}^{*}})=Q_{i}(a_{i};\Theta_{\bm{a}^{*}})$. Let
$\bm{b}=(\underbrace{k,\cdots,k}_{i-1\text{ copies}},a_{i},k,\cdots,k)$
differing with $\bm{a}^{*}$ only at the $i$-th action. Then we have
$Q(\bm{b};\Theta_{\bm{a}^{*}})=f_{\bm{a}^{*}}(\bm{b})=0$ by Lemma B.15, since
$\bm{b}$ does not belong to the diagonal. On the other hand,
$Q(\bm{b};\Theta_{\bm{a}^{*}})=\max Q(\cdot;\Theta_{\bm{a}^{*}})=\max
f_{\bm{a}^{*}}(\cdot)>0$ by the IGM assumption, which leads to a
contradiction.

Collecting all $\Theta_{\bm{a}^{*}}$ into a set $S$ completes our proof. ∎

Now we are able to prove Theorem 4.2.

######  Theorem 4.2.

For any VD (Equations 3 and 4) with a complete function class, there are tasks
such that, when the parameter $\Theta$ is initialized in certain set $S$, it
converges to a suboptimal policy.

###### Proof.

We continue to use notations in the proofs of Theorems B.12 and B.14. And we
further assume the distribution $\mathcal{D}$ in the loss function to be
uniform WLOG, since treating an arbitrary $\mathcal{D}$ with full support only
brings complexity in form for our analysis.

Note that in the proof of Theorems B.14 and B.12, it is essential for us to
find $\bm{a}^{*}$ and $\Theta_{\bm{a}^{*}}$ subject to

High level local minima: $\displaystyle Q(\Theta_{\bm{a}^{*}})=f_{\bm{a}^{*}}$
(10) Greedy action consistency:
$\displaystyle\\{\bm{a}^{*}\\}=\bigtimes_{i=1}^{n}\operatorname*{arg\,max}Q_{i}(\Theta_{\bm{a}^{*}})$
(11)

In the proof of Theorem B.12, we fix $\bm{a}^{*}$ at first and then make it by
the assumption of IGM-completeness. While in the proof of Theorem B.14, we
again fix $\bm{a}^{*}$ at first and then make it by the B-W theorem based on
the compactness of $R$. Nevertheless, we have neither of them here.

However, the proof of Theorem B.14 gives us an important implication:

######  Fact B.16.

For any positive diagonal tensor $f\in\mathcal{R}^{|\mathcal{A}|^{n}}$, i.e.,

  1. 1.

$f$ is positive on the diagonal, i.e. $f(\bm{a})>0$ for all
$\bm{a}\in\\{(k,\cdots,k):k=1,\cdots,|\mathcal{A}|\\}$.

  2. 2.

$f$ is zero on the non-diagonal, i.e. $f(\bm{b})=0$ for all
$\bm{b}\not\in\\{(k,\cdots,k):k=1,\cdots,|\mathcal{A}|\\}$.

we have $|\operatorname*{arg\,max}Q_{i}(\Theta)|=1$ for $i=1,\cdots,n$, where
$\Theta$ is the parameter that decomposes $f$ (i.e., $Q(\Theta)=f$).

###### Proof.

This is essentially the argument at the end of the proof of Theorem B.14. We
omit the complete proof here for simplicity. ∎

B.16 tells us that factorizing a positive diagonal tensor results in a unique
local greedy action for all $i\in[n]$.

Now we are going to construct some positive diagonal tensor $T$ with a proper
structure. We first define a recursive sequence $\\{h_{t}\\}_{t\geq 1}$ as
follows:

  * •

$h_{1}=0$.

  * •

$\forall t>1:h_{t}=(t-1)h_{t-1}-\sum\limits_{i<t-1}h_{i}-1$.

Let $C\in\mathbb{R}^{|\mathcal{A}|}$ and
$C(t)=h_{|\mathcal{A}|-t+1}-h_{|\mathcal{A}|}+1$ for
$t=1,\cdots,|\mathcal{A}|$, we fill the diagonal of the $n$-dimensional tensor
$T$ by $C(1),\cdots,C(|\mathcal{A}|)$, denoted by $T=\text{diag}_{n}\\{C\\}$.
We have the following lemma for the structure of $f_{\bm{a}^{*}}$ when
$\bm{a}^{*}$ is some joint action on the diagonal.

######  Lemma B.17.

Suppose $T=\text{diag}_{n}\\{C\\}$ and $\bm{a}^{*}=(l,\cdots,l)$ for some
$l\in\\{1,\cdots,|\mathcal{A}|\\}$, we have
$f_{\bm{a}^{*}}=\text{diag}_{n}\\{D\\}$, where

  1. 1.

$D(k)=C(k)$ for $k=1,\cdots,l-1$.

  2. 2.

$D(k)=\frac{1}{|\mathcal{A}|-l+1}\sum_{i\geq l}C(i)$ for
$k=l,\cdots,|\mathcal{A}|$.

Moreover, let $P$ be any permutation over $\\{1,\cdots,|\mathcal{A}|\\}$, then
if $T=\text{diag}_{n}\\{P\circ C\\}$, we have
$f_{\bm{a}^{*}}=\text{diag}_{n}\\{P\circ D\\}$.777$P\circ A$ means the
permutation $P$ acting on the vector $A$, which results in a new vector $B$
such that $B(k)=A(P(k))$.

###### Proof.

It is easy to see that $C(k)\geq 1$ for all $k$. Therefore by Lemma B.15,
$f_{\bm{a}^{*}}$ should be a diagonal tensor.

Let $D(l)=v$, by the definition of $f_{\bm{a}^{*}}$, we have $D(k)\leq v$ for
all $k$. Suppose $C(k)<v$ for some $k\neq l$, then we must have $D(k)=C(k)$
since this would result in a zero loss on the entry; and for all $k\neq l$
such that $C(k)\geq v$, we must have $D(k)=v$ since this would result in a
minimum loss under the constraint $D(k)\leq v$.

Let $M(v)\in\mathcal{R}^{|\mathcal{A}|}$ be a vector such that
$M(v)(k)=\left\\{\begin{array}[]{ll}C(k),&C(k)<v\text{ and }k\neq l\\\
v,&\text{otherwise}\end{array}\right.$

Then minimizing $L$ in $\mathcal{R}(\bm{a}^{*})$ is equivalent to minimizing
$\phi(v)=L(M(v))$.

Now we show that the global minimum $v^{*}$ of $L$ is
$\frac{1}{|\mathcal{A}|-l+1}\sum_{i\geq l}C(i)$.

First, it is obvious that $v^{*}\geq C(l)$.

Secondly, note that

$\displaystyle\left[\frac{1}{|\mathcal{A}|-l+1}\sum_{i\geq
l}C(i)\right]-C(l+1)$
$\displaystyle=\left[\frac{1}{|\mathcal{A}|-l+1}\sum_{i\geq
l}(h_{|\mathcal{A}|-i+1}-h_{|\mathcal{A}|}+1)\right]-(h_{|\mathcal{A}|-l}-h_{|\mathcal{A}|}+1)$
$\displaystyle=\left[\frac{1}{|\mathcal{A}|-l+1}\sum_{i\leq|\mathcal{A}|-l+1}h_{i}\right]-h_{|\mathcal{A}|-l}$
$\displaystyle=\frac{1}{|\mathcal{A}|-l+1}\left[(|\mathcal{A}|-l)h_{|\mathcal{A}|-l}-\sum_{i\leq|\mathcal{A}|-l-1}h_{i}-1+\sum_{i\leq|\mathcal{A}|-l}h_{i}\right]-h_{|\mathcal{A}|-l}$
$\displaystyle=\frac{1}{|\mathcal{A}|-l+1}\left[(|\mathcal{A}|-l+1)h_{|\mathcal{A}|-l}-1\right]-h_{|\mathcal{A}|-l}$
$\displaystyle=-\frac{1}{|\mathcal{A}|-l+1}$

That is, $\mathbf{Mean}\\{C(l),\cdots,C(|\mathcal{A}|)\\}<C(l+1)$. As a
consequence, $\mathbf{Mean}\\{C(l),C(l+2),\cdots,C(|\mathcal{A}|)\\}<C(l+1)$.
By induction, it is easy to show that
$\mathbf{Mean}\\{C(l),C(l^{\prime}),\cdots,C(|\mathcal{A}|)\\}<C(l+1)$ for all
$l^{\prime}>l$.

Third, note that for all $v\geq C(l)$,

$\phi(v)=\frac{1}{|\mathcal{A}|^{n}}\left((C(l)-v)^{2}+\sum_{i\geq
l^{\prime}}(C(i)-v)^{2}\right)\quad\text{where }l^{\prime}=\min\\{j:C(j)\geq
v\\}$

Also, recall that for any $m$ and $x_{1},\cdots,x_{m}$, the function
$\xi(x)\stackrel{{\scriptstyle\Delta}}{{=}}\sum_{k=1}^{m}(x_{k}-x)^{2}$
monotonically decreases on $(-\infty,\overline{x})$ and monotonically
increases on $(\overline{x},+\infty)$, where
$\overline{x}=\mathbf{Mean}\\{x_{1},\cdots,x_{m}\\}$.999It can be easily
proved by taking the derivative.

Thus, we have

  1. 1.

$\phi$ is continuous.

  2. 2.

On $[C(l),\mathbf{Mean}\\{C(l),\cdots,C(|\mathcal{A}|)\\})$,
$\phi(v)=\frac{1}{|\mathcal{A}|^{n}}\sum_{i\geq l}(C(i)-v)^{2}$ monotonically
decreases.

  3. 3.

On $(\mathbf{Mean}\\{C(l),\cdots,C(|\mathcal{A}|)\\},C(l+1)]$,
$\phi(v)=\frac{1}{|\mathcal{A}|^{n}}\sum_{i\geq l}(C(i)-v)^{2}$ monotonically
increases.

  4. 4.

On $(C(l+1),C(l+2)]$,
$\phi(v)=\frac{1}{|\mathcal{A}|^{n}}\left((C(l)-v)^{2}+\sum_{i\geq
l+2}(C(i)-v)^{2}\right)$ monotonically increases.

  5. 5.

Based on 1, 3, 4 and by induction, on
$(\mathbf{Mean}\\{C(l),\cdots,C(|\mathcal{A}|)\\},+\infty)$, $\phi(v)$
monotonically increases.

which means $v^{*}=\mathbf{Mean}\\{C(l),\cdots,C(|\mathcal{A}|)\\}$.

This completes the proof of the first part of the lemma. For the second part
when a permutation $P$ is involved, the discussion is essentially the same, we
omit it here.

∎

Lemma B.17 shows that when we choose $\bm{a}^{*}=(l,\cdots,l)$, the resulting
diagonal of $f_{\bm{a}^{*}}$ contains two parts:

  1. 1.

The top $l-1$ smallest entries are “revealed” as they exactly are.

  2. 2.

Other entries are “masked” by the same constant
$v=\frac{1}{|\mathcal{A}|-l+1}\sum_{i\geq l}C(i)$.

This motivates us to construct the diagonal of $T$ recursively.

Algorithm 3 Construction of $T$ and Local Minima

1: Output: $T\in\mathbb{R}^{|\mathcal{A}|^{n}}$ and a set $S$ of parameters.

2: Initialize $E\in\mathbb{R}^{|\mathcal{A}|}$ with all zeros. // The diagonal
of $T$ to be constructed.

3: for $l=1$ to $|\mathcal{A}|$ do

4: $D\leftarrow E$. // Reveal $l-1$ known entries of the diagonal.

5: Fill in all zero entries of $D$ by
$v=\frac{1}{|\mathcal{A}|-l+1}\sum_{i\geq l}C(i)$. // Mask all unknown
entries.

6: $f\leftarrow\text{diag}_{n}\\{D\\}$.

7: Calculate $\Theta_{l}$ such that $Q(\Theta_{l})=f$. // Decomposition, by
the completeness assumption.

8: $S=S\cup\\{\Theta_{l}\\}$. // This would be a local minimum at last.

9: $j\leftarrow\operatorname*{arg\,max}Q_{1}(\Theta_{l})$. // By B.16,
$\operatorname*{arg\,max}Q_{1}(\Theta_{l})=\cdots=\operatorname*{arg\,max}Q_{n}(\Theta_{l})$,
$|\operatorname*{arg\,max}Q_{1}(\Theta_{l})|=1$.

10: $E(j)\leftarrow C(l)$. // Determine the index of $C(l)$.

11: end for

12: $T\leftarrow\text{diag}_{n}\\{E\\}$.

13: Return $T,S$.

It is easy to check that Equations 10 and 11 are satisfied by the $T$ and $S$
output by Algorithm 3.

This completes our proof. ∎

###  B.4 Some Discussion on QPLEX

QPLEX(Wang et al., 2021b) is a value-decomposition algorithm with an IGM-
complete (Definition B.11) function class. According to Theorem 4.2, its loss
function $\mathcal{L}$ has numerous local minima.

In the empirical design of the algorithm, we notice that QPLEX has used some
engineering tricks like ”stop gradient” to modify the gradient of non-optimal
points helping the algorithm to jump out of local optima. But these tricks
lack of theoretical guarantee, we can still construct cases where QPLEX is not
able to reach the global optimum, such as the following Matrix Game (Table2).

-20 | 10
---|---
10 | 9
Table 2: Matrix Game 2, $m=2$

This Matrix Game has two global optima $(0,1)$ and $(1,0)$, and one suboptimal
solution $(1,1)$ with high reward. QPLEX will likely to initialize to the
suboptimal solution $(1,1)$, and after that, it gets confused since the
manually modified gradient does not tell it the right direction. The learned
joint $Q$ vibrates around the following matrix:

$\left(\begin{array}[]{cc}-20&29/3-\epsilon\\\
29/3-\epsilon&29/3\end{array}\right)$

which can be proved to be a local optimum of the loss function $\mathcal{L}$
according to the proof of Theorem 4.2.

##  Appendix C Omitted Definitions and Proofs in Section 5

###  C.1 Omitted proof of Theorem 5.1

Before we provide the proof of Theorem 5.1, we first introduce the policy
conversion between a policy $\pi$ on $\Gamma(\mathcal{M})$ and a coordination
policy $\pi^{c}$ on $\mathcal{M}$. $\mathcal{M}$ and $\Gamma(\mathcal{M})$
refer to an MMDP and its sequential transformation (Algorithm 1).

We define the coordination policy at first.

######  Definition C.1 (coordination policy).

A coordination policy $\pi^{c}$ is $n$ individual policies for sequential
decision making. That is $\pi^{c}=(\pi_{1},\cdots,\pi_{n})$, where
$\pi_{i}(a_{i}|s,a_{<i})$ is a policy of agent $i$ conditioned on the state
$s$ and “previously inferred” actions $a_{<i}=\langle
a_{1},\dots,a_{i-1}\rangle$.

Then there is a natural correspondence between the policy $\pi$ on
$\Gamma(\mathcal{M})$ and the corresponding coordination policy $\pi^{c}$ on
$\mathcal{M}$. We present the bi-directional conversion as follows.

#### from $\pi$ to $\pi^{c}$

Suppose we have a policy $\pi(a_{k+1}|(s,a_{1},\cdots,a_{k}))$ on
$\Gamma(\mathcal{M})$. Denote
$\pi_{k}(a_{k}|s,a_{1},\cdots,a_{k-1})=\pi(a_{k}|(s,a_{1},\cdots,a_{k-1}))$.
Then $\pi^{c}=(\pi_{1},\cdots,\pi_{n})$ is the corresponding coordination
policy on $\mathcal{M}$.

#### from $\pi^{c}$ to $\pi$

Suppose we have a coordination policy $\pi^{c}=(\pi_{1},\cdots,\pi_{n})$ on
$\mathcal{M}$. We can directly have the policy $\pi$ on $\Gamma(\mathcal{M})$,
where
$\pi(a_{k}|(s,a_{1},\cdots,a_{k-1}))=\pi_{k}(a_{k}|s,a_{1},\cdots,a_{k-1})$.

Now, we rephrase Theorem 5.1 and give a proof.

######  Theorem 5.1.

For any policy $\pi$ on $\Gamma\left(\mathcal{M}\right)$ and its corresponding
coordination policy $\pi^{c}$ on $\mathcal{M}$, we have
$\mathcal{J}_{\mathcal{M}}(\pi^{c})=\gamma^{(1-n)/n}\mathcal{J}_{\Gamma\left(\mathcal{M}\right)}(\pi)$.

###### Proof.

We use the notations defined in Algorithm 1.

For some policy $\eta$, the notation $r(s,\eta)$ refers to
$\mathbb{E}_{a\sim\eta(\cdot|s)}[r(s,a)]$. And the notation $P(s,\eta)$ refers
to the distribution of $s^{\prime}$, where $a\sim\eta(\cdot|s),s^{\prime}\sim
P(\cdot|s,a)$.

$\displaystyle\mathcal{J}_{\mathcal{M}}(\pi^{c})$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},\pi^{c})\middle|s_{t+1}\sim
P(s_{t},\pi^{c})\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{\infty}{\gamma^{\prime}}^{nt}r^{\prime}\left(\left(s_{t},a_{<n}^{(t)}\right),\pi\right)\middle|s_{t+1}\sim
P(s_{t},\pi^{c}),a_{l}^{(t)}\sim\pi\left(\cdot\middle|\left(s_{t},a_{<l}^{(t)}\right)\right)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{\infty}\sum_{k=0}^{n-1}{\gamma^{\prime}}^{nt+k-n+1}r^{\prime}\left(\left(s_{t},a_{<k}^{(t)}\right),\pi\right)\middle|s_{t+1}\sim
P(s_{t},\pi^{c}),a_{l}^{(t)}\sim\pi\left(\cdot\middle|\left(s_{t},a_{<l}^{(t)}\right)\right)\right]$
$\displaystyle=\mathbb{E}\left[{\gamma^{\prime}}^{1-n}\sum_{t^{\prime}=0}^{\infty}{\gamma^{\prime}}^{t^{\prime}}r^{\prime}(s_{t^{\prime}},\pi)\middle|s_{t^{\prime}+1}\sim
P^{\prime}(s_{t^{\prime}},\pi)\right]$
$\displaystyle=\mathcal{\gamma}^{\frac{1-n}{n}}J_{\Gamma\mathcal{(}\mathcal{M})}(\pi)$

∎

###  C.2 Omitted Proof of Theorem 5.2

Before we prove Theorem 5.2, we first define our distillation process on MMDP
in Algorithm 4.

Algorithm 4 The Distillation Stage in the TAD framework

1: Input: An MMDP $\mathcal{M}$ of $n$ agents, a coordination policy
$\pi^{c}=(\pi_{1},\cdots,\pi_{n})$ on $\mathcal{M}$.

2: Output: Decentralized policies $\eta_{1},\cdots,\eta_{n}$.

3: // Calculate the greedy policy for each agent.

4: for $k=1$ to $n$ do

5: for all $s\in\mathcal{S},a_{1},\cdots,a_{k-1}\in\mathcal{A}$ do

6:
$a^{*}\leftarrow\operatorname*{arg\,max}_{a_{k}}\pi_{k}(a_{k}|s,a_{1},\cdots,a_{k-1})$
// If there are multiple, select arbitrarily.

7: $\mu_{k}(s,a_{1},\cdots,a_{k-1})=a^{*}$. // Convert $\pi^{c}$ to a
deterministic coordination policy.

8: end for

9: end for

10: for all $s\in\mathcal{S}$ do

11: for $k=1$ to $n$ do

12: $\eta_{k}(s)=\mu_{k}(s,\eta_{1}(s),\cdots,\eta_{k-1}(s))$. // The
deterministic coordination policy is natually decentralized.

13: end for

14: end for

15: Return $\eta_{1},\cdots,\eta_{n}$.

Now we present the proof of Theorem 5.2.

######  Theorem 5.2.

For any SARL algorithms $A$ with optimality guarantee on MDP, TAD-$A$, the
MARL algorithm using TAD framework and based on $A$, will have optimality
guarantee on any MMDP.

###### Proof.

For arbitrary MMDP $\mathcal{M}$, since $A$ has an optimality guarantee on
MDP, the policy on $\Gamma(\mathcal{M})$ learned by $A$ maximizes the expected
return on $\Gamma(\mathcal{M})$. Then by Theorem 5.1, the coordination policy
$\pi^{c}$ obtained in the transformation stage (see Algorithm 2) maximizes the
expected return on $\mathcal{M}$.

In the distillation stage (Algorithm 4), $\pi^{c}$ is first converted into a
deterministic coordination policy $\mu^{c}=(\mu_{1},\cdots,\mu_{k})$. Since
$\pi^{c}$ is optimal on $\mathcal{M}$, $\mu^{c}$ should also be optimal.

Finally, line 8-10 in Algorithm 4 describe the way we decentralize a
deterministic coordination policy $\mu^{c}$. It is obvious that
$\mu^{c}=\bigtimes_{i=1}^{n}\eta_{i}$. Therefore the decentralized policies
$\eta_{1},\cdots,\eta_{n}$ are also optimal. ∎

###  C.3 The Complexity of the Transformed Model

By the TAD framework, we are able to convert any MMDP to an MDP and run SARL
algorithms on the MDP to solve the MMDP. One natural question is, will such
framework bring additional hardness of the task?

We will exclude the influence of the distillation stage and consider the
sequential transformation only. That is, we consider the sequential
transformation framework (the TAD framework without distillation).

First of all, the sequential transformation framework in reversible in that
for any multi-agent algorithm $A$, and any MDP $\widetilde{\mathcal{M}}$, we
can always compress $n$ steps on $\widetilde{\mathcal{M}}$ into one step to
obtain $\Gamma^{-1}(\widetilde{\mathcal{M}})$ and then use the corresponding
multi-agent algorithm $A$ to solve it.

Then, we introduce the concept of minimax sample complexity. Roughly speaking,
the minimax sample complexity is the sample complexity of the “best” algorithm
over the “hardest” task. Since the sequential transformation framework is
reversible with only negligible additional cost in time and space, we are able
to claim the sequential transformation framework does not increase the minimax
sample complexity101010One should keep in mind that every $n$ samples on MDP
correspond to exactly one sample on MMDP. Particularly, the number of bits we
need to record every $n$ samples on MDP are exactly what we need to record one
sample on MMDP..

Nevertheless, for a concrete algorithm $A$ (e.g. Q-learning), the sample
complexity is not necessary to be the same after such transformation.

We take Q-learning as an example and first investigate the size of state-
action space before and after the transformation. It easy to see that the size
of the state-action space of $\mathcal{M}$ is
$|\mathcal{S}||\mathcal{A}|^{n}$, and that of its
$\Gamma\left(\mathcal{M}\right)$ is
$|\mathcal{A}|\sum_{i=0}^{n-1}|\mathcal{S}||\mathcal{A}|^{i}=|\mathcal{S}||\mathcal{A}|\frac{1-|\mathcal{A}|^{n}}{1-|\mathcal{A}|}\leq
2|\mathcal{S}||\mathcal{A}|^{N}$. This implies that the sequential transform
does not increase the complexity in the state-action space.

However, if we take a closer look here of the sample complexity, we will find
that the exact sample complexity bound of Q-learning is
$O^{*}\left(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\epsilon^{2}}\right)$
((Li et al., 2021b)), which depends on not only the size of state-action
space, but also on the magnitude of $\frac{1}{1-\gamma}$. This implies that
the sample complexity may increase for certain algorithms since
$\Gamma\left(\mathcal{M}\right)$ has a longer horizon ($n$ times).

##  Appendix D Experimental Details

In this section, we provide more experimental results supplementary to those
presented in Section 6. We also discuss the details of the experimental
settings of both our matrix game and the StarCraft II micromanagement (SMAC)
benchmark.

###  D.1 Details of Multi-task Matrix Game

In multi-task matrix game, the return of the optimal strategy corresponding to
each matrix is 10, which means the sum rewards of the global optimal strategy
is 100. Two agents are initialized to one matrix uniformly at random, and the
ID of a current matrix is observable to both of them. They need to cooperate
to select the entry with the maximum reward for the current matrix, after
that, the game ends. Each matrix contains $5\times 5=25$ entries, which means
$\mathcal{A}=\\{0,1,2,3,4\\}$ for each agent.

Table 3: Multi-task Matrix Game

Matrix 1 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | 10 | -10 | -10 | -10 | -10
$\mathcal{A}^{(2)}$ | -10 | 9 | 0 | 0 | 0
$\mathcal{A}^{(3)}$ | -10 | 0 | 9 | 0 | 0
$\mathcal{A}^{(4)}$ | -10 | 0 | 0 | 9 | 0
$\mathcal{A}^{(5)}$ | -10 | 0 | 0 | 0 | 9

Matrix 2 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | 10 | -10 | 10 | -10 | 10
$\mathcal{A}^{(2)}$ | -10 | 10 | -10 | 10 | -10
$\mathcal{A}^{(3)}$ | 10 | -10 | 10 | -10 | 10
$\mathcal{A}^{(4)}$ | -10 | 10 | -10 | 10 | -10
$\mathcal{A}^{(5)}$ | 10 | -10 | 10 | -10 | 10

Matrix 3 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | -20 | -20 | -20 | -20 | 10
$\mathcal{A}^{(2)}$ | -20 | -20 | -20 | 10 | 9
$\mathcal{A}^{(3)}$ | -20 | -20 | 10 | 9 | 9
$\mathcal{A}^{(4)}$ | -20 | 10 | 9 | 9 | 9
$\mathcal{A}^{(5)}$ | 10 | 9 | 9 | 9 | 9

Matrix 4 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | -20 | -20 | -20 | -20 | 10
$\mathcal{A}^{(2)}$ | -20 | -20 | -20 | 10 | 9
$\mathcal{A}^{(3)}$ | -20 | -20 | 10 | 9 | 8
$\mathcal{A}^{(4)}$ | -20 | 10 | 9 | 8 | 7
$\mathcal{A}^{(5)}$ | 10 | 9 | 8 | 7 | 6

Matrix 5 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | -20 | -15 | -10 | -5 | 6
$\mathcal{A}^{(2)}$ | -20 | -15 | -10 | 7 | 5
$\mathcal{A}^{(3)}$ | -20 | -15 | 8 | 6 | 4
$\mathcal{A}^{(4)}$ | -20 | 9 | 7 | 5 | 3
$\mathcal{A}^{(5)}$ | 10 | 8 | 6 | 4 | 2

Matrix 6 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | 0.8 | -16.0 | -5.0 | -10.9 | -3.7
$\mathcal{A}^{(2)}$ | -9.2 | -4.2 | 7.3 | 9.6 | -3.0
$\mathcal{A}^{(3)}$ | -20.0 | -18.1 | 0.2 | -4.3 | 9.0
$\mathcal{A}^{(4)}$ | -14.9 | -2.0 | -17.7 | -17.6 | -0.8
$\mathcal{A}^{(5)}$ | 3.8 | 10 | 7.5 | 9.2 | -10.7

Matrix 7 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | -14.4 | -15.8 | 1.5 | -5.4 | 10
$\mathcal{A}^{(2)}$ | -13.2 | 5.8 | -8.7 | -2.2 | -18.2
$\mathcal{A}^{(3)}$ | -5.9 | -19.0 | -0.7 | -2.0 | -19.5
$\mathcal{A}^{(4)}$ | 0.8 | 4.7 | -14.8 | 2.5 | -4.1
$\mathcal{A}^{(5)}$ | -11.3 | -8.2 | -20.0 | -17.3 | -17.6

Matrix 8 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | -1.4 | -19.2 | 7.2 | -5.5 | 7.4
$\mathcal{A}^{(2)}$ | -18.5 | -20.0 | -14.4 | -17.6 | -5.1
$\mathcal{A}^{(3)}$ | 3.6 | 5.5 | 10 | -13.3 | -4.9
$\mathcal{A}^{(4)}$ | 9.8 | -12.3 | 0.6 | -16.5 | -13.0
$\mathcal{A}^{(5)}$ | -11.8 | -20.0 | -2.4 | 7.1 | -2.3

Matrix 9 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | -4.5 | -5.2 | -8.4 | -8.9 | 5.5
$\mathcal{A}^{(2)}$ | -12.4 | -9.5 | 8.8 | 5.4 | 4.4
$\mathcal{A}^{(3)}$ | -4.6 | 1.3 | 5.5 | 7.3 | -6.8
$\mathcal{A}^{(4)}$ | 9.0 | -18.7 | -18.2 | -13.7 | -8.2
$\mathcal{A}^{(5)}$ | 2.2 | -9.1 | 10 | 7.1 | -20.0

Matrix 10 $a_{2}$ $a_{1}$ | $\mathcal{A}^{(1)}$ | $\mathcal{A}^{(2)}$ | $\mathcal{A}^{(3)}$ | $\mathcal{A}^{(4)}$ | $\mathcal{A}^{(5)}$
---|---|---|---|---|---
$\mathcal{A}^{(1)}$ | -8.4 | -1.8 | -20.0 | 7.3 | -3.0
$\mathcal{A}^{(2)}$ | -8.7 | 1.7 | 4.8 | 2.0 | -7.8
$\mathcal{A}^{(3)}$ | -13.3 | -3.2 | 0.7 | -1.8 | -10.7
$\mathcal{A}^{(4)}$ | 9.8 | -12.3 | 0.6 | -16.5 | -13.0
$\mathcal{A}^{(5)}$ | 1.8 | 2.9 | -1.1 | 10 | 8.2

All 10 payoff matrices are listed in Table 3. The optimal strategies’ payoff
of all matrices is 10. Matrices $1-5$ are hand-crafted in order to create some
hard NEs. Matrices $6-10$ are drawn uniformly at random. It’s worth noting
that a random $5\times 5$ matrix has $25/9\approx 2.77$ different NEs in
expectation. And in our opinion, the existence of suboptimal NEs is the main
reason why existing algorithms fail.

###  D.2 Benchmarking on StarCraft II Micromanagement Tasks

Figure 7: Comparisons between our approach and policy-based state-of-the-art
MARL baselines on all super hard maps. Figure 8: Comparisons between our
approach and policy-based state-of-the-art MARL baselines on all hard maps.

In section 6.2, we have compared and discussed the advantage of our approach
against baselines on several representative maps. Here we further compare our
reproach against baselines on all maps. The SMAC benchmark contains 14 maps
that have been classified as easy, hard, and super hard. In this paper, we
design one more map $\mathtt{3h\\_vs\\_1b1z3h}$, whose difficulty is
comparable with official super hard maps.

In Figure. 7, we compare the performance of our approach with baseline
algorithms on all super hard maps. We can see that TAD-PPO outperforms all the
baselines, especially on $\mathtt{3s5z\\_vs\\_3s6z}$, $\mathtt{MMM2}$, and
$\mathtt{3h\\_vs\\_1b1z3h}$. These results demonstrate that TAD-PPO can handle
challenging tasks more efficiently with theoretical guarantees of global
optimality. HAPPO performs poorly on 4 out of 6 super hard maps, demonstrating
its limitation on complex tasks.

Figure 9: Comparisons between our approach and policy-based state-of-the-art
MARL baselines on all easy maps.

Our approach achieves similar convergence performance with MAPPO in hard maps
as shown in Figure. 8, because there is no obvious local optimal point in hard
maps. In easy maps, our approach achieves faster convergence rate compared
with MAPPO in three out of five maps as shown in Figure. 9.

###  D.3 Hyper-parameters

Our code is implemented based on MAPPO. We share the same structure and hyper-
parameters with MAPPO (Yu et al., 2021) except improvement we mentioned in
Section 5.2 to instantiate our transformation framework, which contains two
extra hyper-parameters: the number of our multi-head attention modules’ heads
($N_{h}$) and the dimension ($D$) of WQs, WKs, and Vs. In all easy and hard
maps of the SMAC benchmark, we set $N_{h}=4$ and $D=4$. In super hard maps of
the SMAC benchmark, we adapt two sets of hyper-parameters to deal with various
diversity level of teammate strategies. In $\mathtt{MMM2}$,
$\mathtt{corridor}$, and $\mathtt{3h\\_vs\\_1b1z3h}$, we set $N_{h}=4$ and
$D=8$. In other three super hard maps, we set $N_{h}=3$ and $D=4$. In all GRF
academic scenarios used in this paper, we set $N_{h}=4$ and $D=6$.

###  D.4 Running time of TAD-PPO

The sequential update does take longer time than the concurrent update in the
training phase, while in the testing phase, our algorithm doesn’t take extra
time since a decentralized policy is already calculated by distillation.

Specifically, in the training phase, our framework takes $n$ times the time to
do action inference, where $n$ is the number of agents. However, it’s worth
mentioning that, the time of action inference is only part of the time doing a
whole training iteration, which also includes environment simulation and
policy training. On the whole, the training time cost of our framework is 0.91
times more than MAPPO in SMAC environment $\mathtt{3m}$ (3 agents), and 1.76
times more in SMAC environment $\mathtt{10m\ vs\ 11m}$ (10 agents). This
result embodies a trade-off between training time and training performance.
Specific time of each part is shown Table 4.

Table 4: Comparison between TAD-PPO and MAPPO on training time Env: | Action | Env | Env interaction: | Policy | The whole training phase:
---|---|---|---|---|---
3m (1M) |  inference: $t_{I}$ |  simulation: $t_{S}$ | $t_{I}+t_{S}$ |  Training: $t_{P}$ | $t_{I}+t_{S}+t_{P}$
TAD-PPO | 1694.6s | 915.4s | 2610s | 233.7s | 2843.7s
MAPPO | 434.9s | 904.5s | 1339.4s | 151.9s | 1491.3s
Ratio | 3.9 | 1.01 | 1.95 | 1.54 | 1.91
Env: | Action | Env | Env interaction: | Policy | The whole training phase:
10m vs 11m (1M) |  inference: $t_{I}$ |  simulation: $t_{S}$ | $t_{I}+t_{S}$ |  Training: $t_{P}$ | $t_{I}+t_{S}+t_{P}$
TAD-PPO | 5011.7s | 2065.5s | 7077.2s | 794.1s | 7871.1s
MAPPO | 501.1s | 2063.2s | 2564.3s | 292.1s | 2856.4s
Ratio | 10.0 | 1.0 | 2.76 | 2.72 | 2.76

###  D.5 TAD-DQN results

Figure 10: Comparisons between TAD-DQN and off-policy baselines on Markov
Game, a hard and a superhard SMAC maps.

We also implement the off-policy method TAD-DQN based on the single agent
algorithm DQN (Mnih et al., 2013) for completeness. In Figure 10 We evaluate
DQN on a Markov Game (Matrix games with random transition), a hard and a
superhard SMAC maps to show that our framework is also compatible with off-
policy methods.

###  D.6 Learned behaviour of the sequential framework

We visualize the policy learned by our approach and compare it with MAPPO in
MMM2. Based on the comparison, we notice an interesting phenomenon. The joint
strategy trained by MAPPO is usually conservative, only moving in a small
area, and only two agents are left in the end. On the contrary, the joint
strategy trained by our approach is more aggressive. Our agents pull back and
forth frequently based on opponents’ movement in a large-scale range while
ensuring effective fire focus. We think this phenomenon is caused by our
sequential transformation framework, which enables each agent to fully
understand the team strategy for more efficient coordination.