# Heterogeneous-Agent Mirror Learning:
A Continuum of Solutions to Cooperative MARL

Jakub Grudzien Kuba∗,1, Xidong Feng∗,2,
Shiyao Ding3, Hao Dong4, Jun Wang2, Yaodong Yang†,4
1University of Oxford, 2University College London, 3Kyoto University, 4Peking
University

###### Abstract

The necessity for cooperation among intelligent machines has popularised
cooperative multi-agent reinforcement learning (MARL) in the artificial
intelligence (AI) research community. However, many research endeavours have
been focused on developing practical MARL algorithms whose effectiveness has
been studied only empirically, thereby lacking theoretical guarantees. As
recent studies have revealed, MARL methods often achieve performance that is
unstable in terms of reward monotonicity or suboptimal at convergence. To
resolve these issues, in this paper††∗Equal contribution. †Corresponding
author<EMAIL_ADDRESS>, we introduce a novel framework named
Heterogeneous-Agent Mirror Learning (HAML) that provides a general template
for MARL algorithmic designs. We prove that algorithms derived from the HAML
template satisfy the desired properties of the monotonic improvement of the
joint reward and the convergence to Nash equilibrium. We verify the
practicality of HAML by proving that the current state-of-the-art cooperative
MARL algorithms, HATRPO and HAPPO, are in fact HAML instances. Next, as a
natural outcome of our theory, we propose HAML extensions of two well-known RL
algorithms, HAA2C (for A2C) and HADDPG (for DDPG), and demonstrate their
effectiveness against strong baselines on StarCraftII and Multi-Agent MuJoCo
tasks.

##  1 Introduction

While the policy gradient (PG) formula has been long known in the
reinforcement learning (RL) community [25], it has not been until trust region
learning [21] that deep RL algorithms started to solve complex tasks such as
real-world robotic control successfully. Nowadays, methods that followed the
trust-region framework, including TRPO [21], PPO [23] and their extensions
[22, 7], became effective tools for solving challenging AI problems [2]. It
was believed that the key to their success are the rigorously described
stability and the monotonic improvement property of trust-region learning that
they approximate. This reasoning, however, would have been of limited scope
since it failed to explain why some algorithms following it (e.g. PPO-KL)
largely underperform in contrast to success of other ones (e.g. PPO-clip)
[ppo]. Furthermore, the trust-region interpretation of PPO has been formally
rejected by recent studies both empirically [engstrom2020implementation] and
theoretically [wang2020truly]; this revealed that the algorithm violates the
trust-region constraints—it neither constraints the KL-divergence between two
consecutive policies, nor does it bound their likelihood ratios. These
findings have suggested that, while the number of available RL algorithms
grows, our understanding of them does not, and the algorithms often come
without theoretical guarantees either.

Only recently, Kuba et al. [kuba2022mirror] showed that the well-known
algorithms, such as PPO, are in fact instances of the so-called mirror
learning framework, within which any induced algorithm is theoretically sound.
On a high level, methods that fall into this class optimise the mirror
objective, which shapes an advantage surrogate by means of a drift
functional—a quasi-distance between policies. Such an update provably leads
them to monotonic improvements of the return, as well as the convergence to
the optimal policy. The result of mirror learning offers RL researchers strong
confidence that there exists a connection between an algorithm’s practicality
and its theoretical properties and assures soundness of the common RL
practice.

While the problem of the lack of theoretical guarantees has been severe in RL,
in multi-agent reinforcement learning (MARL) it has only been exacerbated.
Although the PG theorem has been successfully extended to the multi-agent PG
(MAPG) version [zhang2018fully], it has only recently been shown that the
variance of MAPG estimators grows linearly with the number of agents
[kuba2021settling]. Prior to this, however, a novel paradigm of centralised
training for decentralised execution (CTDE) [foerster2018counterfactual,
maddpg] greatly alleviated the difficulty of the multi-agent learning by
assuming that the global state and opponents’ actions and policies are
accessible during the training phase; this enabled developments of practical
MARL methods by merely extending single-agent algorithms’ implementations to
the multi-agent setting. As a result, direct extensions of TRPO [li2020multi]
and PPO [de2020independent, mappo] have been proposed whose performance,
although is impressive in some settings, varies according to the version used
and environment tested against. However, these extensions do not assure the
monotonic improvement property or convergence result of any kind
[kuba2021trust]. Importantly, these methods can be proved to be suboptimal at
convergence in the common setting of parameter sharing [kuba2021trust] which
is considered as default by popular multi-agent algorithms [mappo] and popular
multi-agent benchmarks such as SMAC [samvelyanstarcraft] due to the
computational convenience it provides.

In this paper, we resolve these issues by proposing Heterogeneous-Agent Mirror
Learning (HAML)—a template that can induce a continuum of cooperative MARL
algorithms with theoretical guarantees for monotonic improvement as well as
Nash equilibrium (NE) convergence. The purpose of HAML is to endow MARL
researchers with a template for rigorous algorithmic design so that having
been granted a method’s correctness upfront, they can focus on other aspects,
such as effective implementation through deep neural networks. We demonstrate
the expressive power of the HAML framework by showing that two of existing
state-of-the-art (SOTA) MARL algorithms, HATRPO and HAPPO [kuba2021trust], are
rigorous instances of HAML. This stands in contrast to viewing them as merely
approximations to provably correct multi-agent trust-region algorithms as
which they were originally considered [kuba2021trust]. Furthermore, although
HAML is mainly a theoretical contribution, we can naturally demonstrate its
usefulness by using it to derive two heterogeneous-agent extensions of
successful RL algorithms: HAA2C (for A2C [mnih2016asynchronous]) and HADDPG
(for DDPG [lillicrap2015continuous]), whose strength are demonstrated on
benchmarks of StarCraftII (SMAC) [de2020independent] and Multi-Agent MuJoCo
[de2020deep] against strong baselines such as MADDPG [maddpg] and MAA2C
[papoudakis2021benchmarking].

##  2 Problem Formulations

We formulate the cooperative MARL problem as cooperative Markov game
[littman1994markov] defined by a tuple
$\langle\mathcal{N},\mathcal{S},\bm{\mathcal{A}},r,P,\gamma,d\rangle$. Here,
$\mathcal{N}=\\{1,\dots,n\\}$ is a set of $n$ agents, $\mathcal{S}$ is the
state space, $\bm{\mathcal{A}}=\times_{i=1}^{n}\mathcal{A}^{i}$ is the
products of all agents’ action spaces, known as the joint action space.
Although our results hold for general compact state and action spaces, in this
paper we assume that they are finite, for simplicity. Further,
$r:\mathcal{S}\times\bm{\mathcal{A}}\rightarrow\mathbb{R}$ is the joint reward
function,
$P:\mathcal{S}\times\bm{\mathcal{A}}\times\mathcal{S}\rightarrow[0,1]$ is the
transition probability kernel, $\gamma\in[0,1)$ is the discount factor, and
$d\in\mathcal{P}(\mathcal{S})$ (where $\mathcal{P}(X)$ denotes the set of
probability distributions over a set $X$) is the positive initial state
distribution. At time step $t\in\mathbb{N}$, the agents are at state
${\textnormal{s}}_{t}$ (which may not be fully observable); they take
independent actions ${\textnormal{a}}^{i}_{t},\forall i\in\mathcal{N}$ drawn
from their policies
$\pi^{i}(\cdot^{i}|{\textnormal{s}}_{t})\in\mathcal{P}(\mathcal{A}^{i})$, and
equivalently, they take a joint action
${\mathbf{a}}_{t}=({\textnormal{a}}^{1}_{t},\dots,{\textnormal{a}}^{n}_{t})$
drawn from their joint policy
${\bm{\pi}}(\cdot|{\textnormal{s}}_{t})=\prod_{i=1}^{n}\pi^{i}(\cdot^{i}|{\textnormal{s}}_{t})\in\mathcal{P}(\bm{\mathcal{A}})$.
We write $\Pi^{i}\triangleq\\{\times_{s\in\mathcal{S}}\pi^{i}(\cdot^{i}|s)\
|\forall
s\in\mathcal{S},\pi^{i}(\cdot^{i}|s)\in\mathcal{P}(\mathcal{A}^{i})\\}$ to
denote the policy space of agent $i$, and
$\bm{\Pi}\triangleq(\Pi^{1},\dots,\Pi^{n})$ to denote the joint policy space.
It is important to note that when $\pi^{i}(\cdot^{i}|s)$ is a Dirac delta
ditribution, the policy is referred to as deterministic
[silver2014deterministic] and we write $\mu^{i}(s)$ to refer to its centre.
Then, the environment emits the joint reward
$r({\textnormal{s}}_{t},{\mathbf{a}}_{t})$ and moves to the next state
${\textnormal{s}}_{t+1}\sim
P(\cdot|{\textnormal{s}}_{t},{\mathbf{a}}_{t})\in\mathcal{P}(\mathcal{S})$.
The initial state distribution $d$, the joint policy ${\bm{\pi}}$, and the
transition kernel $P$ induce the (improper) marginal state distribution
$\rho_{{\bm{\pi}}}(s)\triangleq\sum_{t=0}^{\infty}\gamma^{t}\text{Pr}({\textnormal{s}}_{t}=s|d,{\bm{\pi}})$.
The agents aim to maximise the expected joint return, defined as

$\displaystyle J({\bm{\pi}})=\mathbb{E}_{{\textnormal{s}}_{0}\sim
d,{\mathbf{a}}_{0:\infty}\sim{\bm{\pi}},{\textnormal{s}}_{1:\infty}\sim
P}\Bigg{[}\sum_{t=0}^{\infty}\gamma^{t}r({\textnormal{s}}_{t},{\mathbf{a}}_{t})\Bigg{]}.$

We adopt the most common solution concept for multi-agent problems which is
that of Nash equilibria [nash1951non, yang2020overview]. We say that a joint
policy ${\bm{\pi}}_{\text{NE}}\in\bm{\Pi}$ is a NE if none of the agents can
increase the joint return by unilaterally altering its policy. More formally,
${\bm{\pi}}_{\text{NE}}$ is a NE if

$\displaystyle\forall i\in\mathcal{N},\forall\pi^{i}\in\Pi^{i},\
J({\bm{\pi}}^{i},{\bm{\pi}}^{-i}_{\text{NE}})\leq J({\bm{\pi}}_{\text{NE}}).$

To study the problem of finding a NE, we introduce the following notions. Let
$i_{1:m}=(i_{1},\dots,i_{m})\subseteq\mathcal{N}$ be an ordered subset of
agents. We write $-i_{1:m}$ to refer to its complement, and $i$ and $-i$,
respectively, when $m=1$. We define the multi-agent state-action value
function as

$\displaystyle
Q^{i_{1:m}}_{{\bm{\pi}}}(s,{\bm{a}}^{i_{1:m}})\triangleq\mathbb{E}_{{\mathbf{a}}^{-i_{1:m}}_{0}\sim{\bm{\pi}}^{-i_{1:m}},{\textnormal{s}}_{1:\infty}\sim
P,{\mathbf{a}}_{1:\infty}\sim{\bm{\pi}}}\Bigg{[}\sum_{t=0}^{\infty}\gamma^{t}r({\textnormal{s}}_{t},{\mathbf{a}}_{t})\
\Big{|}\
{\textnormal{s}}_{0}=s,{\mathbf{a}}^{i_{1:m}}_{0}={\bm{a}}^{i_{1:m}}\Bigg{]}.$

When $m=n$ (the joint action of all agents is considered), then
$i_{1:n}\in\text{Sym}(n)$, where $\text{Sym}(n)$ denotes the set of
permutations of integers $1,\dots,n$, known as the _symmetric group_. In that
case we write
$Q^{i_{1:n}}_{{\bm{\pi}}}(s,{\bm{a}}^{i_{1:n}})=Q_{{\bm{\pi}}}(s,{\bm{a}})$
which is known as the (joint) state-action value function. On the other hand,
when $m=0$, _i.e._ , $i_{1:m}=\emptyset$, the function takes the form
$V_{{\bm{\pi}}}(s)$, known as the state-value function. Consider two disjoint
subsets of agents, $j_{1:k}$ and $i_{1:m}$. Then, the multi-agent advantage
function of $i_{1:m}$ with respect to $j_{1:k}$ is defined as

$\displaystyle
A_{{\bm{\pi}}}^{i_{1:m}}\big{(}s,{\bm{a}}^{j_{1:k}},{\bm{a}}^{i_{1:m}}\big{)}\triangleq
Q_{{\bm{\pi}}}^{j_{1:k},i_{1:m}}\big{(}s,{\bm{a}}^{j_{1:k}},{\bm{a}}^{i_{1:m}}\big{)}-Q_{{\bm{\pi}}}^{j_{1:k}}\big{(}s,{\bm{a}}^{j_{1:k}}\big{)}.$

As it has been shown in [kuba2021settling], the multi-agent advantage function
allows for additive decomposition of the joint advantge function by the means
of the following lemma.

######  Lemma 1 (Multi-Agent Advantage Decomposition).

Let $\bm{\pi}$ be a joint policy, and $i_{1},\dots,i_{m}$ be an arbitrary
ordered subset of agents. Then, for any state $s$ and joint action
${\bm{a}}^{i_{1:m}}$,

$\displaystyle
A_{\bm{\pi}}^{i_{1:m}}\big{(}s,{\bm{a}}^{i_{1:m}}\big{)}=\sum\limits_{j=1}^{m}A^{i_{j}}_{\bm{\pi}}\big{(}s,{\bm{a}}^{i_{1:j-1}},a^{i_{j}}\big{)}.$
(1)

Although the multi-agent advantage function has been discovered only recently
and has not been studied thoroughly, it is this function and the above lemma
that builds the foundation for the development of the HAML theory.

##  3 The State of Affairs in MARL

Before we review existing SOTA algorithms for cooperative MARL, we introduce
two settings in which the algorithms can be implemented. Both of them can be
considered appealing depending on the application, but these pros also come
with “traps” which, if not taken care of, may provably deteriorate an
algorithm’s performance.

###  3.1 Homogeneity _vs._ Heterogeneity

The first setting is that of homogeneous policies, _i.e._ , those where agents
all agents share one policy: $\pi^{i}=\pi,\forall\mathcal{N}$, so that
${\bm{\pi}}=(\pi,\dots,\pi)$ [de2020independent, mappo]. This approach enables
a straightforward adoption of an RL algorithm to MARL, and it does not
introduce much computational and sample complexity burden with the increasing
number of agents. Nevertheless, sharing one policy across all agents requires
that their action spaces are also the same, _i.e._ ,
$\mathcal{A}^{i}=\mathcal{A}^{j},\forall i,j\in\mathcal{N}$. Furthermore,
policy sharing prevents agents from learning different skills. This scenario
may be particularly dangerous in games with a large number of agents, as shown
in Proposition 1, proved by [kuba2021trust].

######  Proposition 1 (Trap of Homogeneity).

Let’s consider a fully-cooperative game with an even number of agents $n$, one
state, and the joint action space $\\{0,1\\}^{n}$, where the reward is given
by $r(\bm{0}^{n/2},\bm{1}^{n/2})=r(\bm{1}^{n/2},\bm{0}^{n/2})=1$, and
$r({\bm{a}}^{1:n})=0$ for all other joint actions. Let $J^{*}$ be the optimal
joint reward, and $J^{*}_{\text{share}}$ be the optimal joint reward under the
shared policy constraint. Then

$\displaystyle\frac{J^{*}_{\text{share}}}{J^{*}}=\frac{2}{2^{n}}.$

A more ambitious approach to MARL is to allow for heterogeneity of policies
among agents, _i.e._ , to let $\pi^{i}$ and $\pi^{j}$ be different functions
when $i\neq j\in\mathcal{N}$. This setting has greater applicability as
heterogeneous agents can operate in different action spaces. Furthermore,
thanks to this model’s flexibility they may learn more sophisticated joint
behaviours. Lastly, they can recover homogeneous policies as a result of
training, if that is indeed optimal. Nevertheless, training heterogeneous
agents is highly non-trivial. Given a joint reward, an individual agent may
not be able to distill its own contibution to it—a problem known as credit
assignment [foerster2018counterfactual, kuba2021settling]. Furthermore, even
if an agent identifies its improvement direction, it may be conflicting with
those of other agents, which then results in performance damage, as we
exemplify in Proposition 2, proved in Appendix A.2.

######  Proposition 2 (Trap of Heterogeneity).

Let’s consider a fully-cooperative game with $2$ agents, one state, and the
joint action space $\\{0,1\\}^{2}$, where the reward is given by
$r(0,0)=0,r(0,1)=r(1,0)=2,$ and $r(1,1)=-1$. Suppose that
$\pi_{\text{old}}^{i}(0)>0.6$ for $i=1,2$. Then, if agents $i$ update their
policies by

$\displaystyle\pi_{\text{new}}^{i}=\operatorname*{arg\,max}_{\color[rgb]{1,0.04,0.61}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.04,0.61}\pgfsys@color@cmyk@stroke{0}{0.96}{0.39}{0}\pgfsys@color@cmyk@fill{0}{0.96}{0.39}{0}\pi^{i}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\mathbb{E}_{{\textnormal{a}}^{i}\sim\color[rgb]{1,0.04,0.61}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.04,0.61}\pgfsys@color@cmyk@stroke{0}{0.96}{0.39}{0}\pgfsys@color@cmyk@fill{0}{0.96}{0.39}{0}\pi^{i}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},{\textnormal{a}}^{-i}\sim\pi^{-i}_{\text{old}}}\big{[}A_{{\bm{\pi}}_{\text{old}}}({\textnormal{a}}^{i},{\textnormal{a}}^{-i})\big{]},\forall
i\in\mathcal{N},$

then the resulting policy will yield a lower return,

$\displaystyle
J({\bm{\pi}}_{\text{old}})>J({\bm{\pi}}_{\text{new}})=\min_{{\bm{\pi}}}J({\bm{\pi}}).$

Consequently, these facts imply that homogeneous algorithms should not be
applied to complex problems, but they also highlight that heterogeneous
algorithms should be developed with extra cares. In the next subsection, we
describe existing SOTA actor-critic algorithms which, while often performing
greatly, are still not impeccable, as they fall into one of the above two
traps.

###  3.2 A Second Look at SOTA MARL Algorithms

#### Multi-Agent Advantage Actor-Critic

MAA2C [papoudakis2021benchmarking] extends the A2C [mnih2016asynchronous]
algorithm to MARL by replacing the RL optimisation (single-agent policy)
objective with the MARL one (joint policy),

$\displaystyle\mathcal{L}^{\text{MAA2C}}({\bm{\pi}})\triangleq\mathbb{E}_{{\textnormal{s}}\sim{\bm{\pi}},{\mathbf{a}}\sim{\bm{\pi}}}\big{[}A_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\mathbf{a}})\big{]},$
(2)

which computes the gradient with respect to every agent $i$’s policy
parameters, and performs a gradient-ascent update for each agent. This
algorithm is straightforward to implement and is capable of solving simple
multi-agent problems [papoudakis2021benchmarking]. We point out, however, that
by simply following their own MAPG, the agents perform uncoordinated updates,
thus getting caught by Proposition 2. Furthermore, MAPG estimates have been
proved to suffer from large variance which grows linearly with the number of
agents [kuba2021settling], thus making the algorithm unstable. To assure
greater stability, the following MARL methods, inspired by stable RL
approaches, have been developed.

#### Multi-Agent Deep Deterministic Policy Gradient

MADDPG [lowe2017multi] is a MARL extension of the popular DDPG algorithm
[lillicrap2015continuous]. At every iteration, every agent $i$ updates its
deterministic policy by maximising the following objective

$\displaystyle\mathcal{L}^{\text{MADDPG}}_{i}(\mu^{i})\triangleq\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\mu}}_{\text{old}}}}\Big{[}Q^{i}_{{\bm{\mu}}_{\text{old}}}\big{(}{\textnormal{s}},\mu^{i}({\textnormal{s}})\big{)}\Big{]}=\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\mu}}_{\text{old}}}}\Big{[}Q^{i}_{{\bm{\mu}}_{\text{old}}}\big{(}{\textnormal{s}},\mu^{i},{\bm{\mu}}^{-i}_{\text{old}}({\textnormal{s}})\big{)}\Big{]},$
(3)

where $\beta_{{\bm{\mu}}_{\text{old}}}$ is a state distribution that is not
necessarily equivalent to $\rho_{{\bm{\mu}}_{\text{old}}}$, thus allowing for
off-policy training. In practice, MADDPG maximises Equation (3) by a few steps
of gradient ascent. The main advantages of MADDPG include small variance of
its MAPG estimates—a property granted by deterministic policies
[silver2014deterministic], as well as low sample complexity due to learning
from off-policy data. Such a combination gives the algorithm a strong
performance in continuous-action tasks [lowe2017multi, kuba2021trust].
However, this method’s strengths also constitute its limitations—it is
applicable to continuous problems only (discrete problems require categorical-
distribution policies), and relies on large memory capacity to store the off-
policy data.

#### Multi-Agent PPO

MAPPO [mappo] is a relatively straightforward extension of PPO [ppo] to MARL.
In its default formulation, the agents employ the trick of policy sharing
described in the previous subsection. As such, the policy is updated to
maximise

$\displaystyle\mathcal{L}^{\text{MAPPO}}(\pi)\triangleq\mathbb{E}_{{\textnormal{s}}\sim\rho_{{\bm{\pi}}_{\text{old}}},{\mathbf{a}}\sim{\bm{\pi}}_{\text{old}}}\Bigg{[}\sum_{i=1}^{n}\min\Big{(}\frac{\pi({\textnormal{a}}^{i}|{\textnormal{s}})}{\pi_{\text{old}}({\textnormal{a}}^{i}|{\textnormal{s}})}A_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\mathbf{a}}),\text{clip}\big{(}\frac{\pi({\textnormal{a}}^{i}|{\textnormal{s}})}{\pi_{\text{old}}({\textnormal{a}}^{i}|{\textnormal{s}})},1\pm\epsilon\big{)}A_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\mathbf{a}})\Big{)}\Bigg{]},$
(4)

where the $\text{clip}(\cdot,1\pm\epsilon)$ operator clips the input to
$1-\epsilon$/$1+\epsilon$ if it is below/above this value. Such an operation
removes the incentive for agents to make large policy updates, thus
stabilising the training effectively. Indeed, the algorithm’s performance on
the StarCraftII benchmark is remarkable, and it is accomplished by using only
on-policy data. Nevertheless, the policy-sharing strategy limits the
algorithm’s applicability and leads to its suboptimality, as we discussed in
Proposition 1 and also in [kuba2021trust]. Trying to avoid this issue, one can
implement the algorithm without policy sharing, thus making the agents simply
take simultaneous PPO updates meanwhile employing a joint advantage estimator.
In this case, the updates are not coordinated, making MAPPO fall into the trap
of Proposition 2.

In summary, all these algorithms do not possess performance guarantees.
Altering their implementation settings to escape one of the traps from
Subsection 3.1 makes them, at best, fall into another. This shows that the
MARL problem introduces additional complexity into the single-agent RL
setting, and needs additional care to be rigorously solved. With this
motivation, in the next section, we develop a theoretical framework for
development of MARL algorithms with correctness guarantees.

##  4 Heterogeneous-Agent Mirror Learning

In this section, we introduce heterogeneous-agent mirror learning (HAML)—a
template that includes a continuum of MARL algorithms which we prove to solve
cooperative problems with correctness guarantees. HAML is designed for the
general and expressive setting of heterogeneous agents, thus avoiding
Proposition 1, and it is capable of coordinating their updates, leaving
Proposition 2 behind.

###  4.1 Setting up HAML

We begin by introducing the necessary definitions of HAML attributes: the
drift functional.

######  Definition 1.

Let $i\in\mathcal{N}$, a heterogeneous-agent drift functional (HADF)
$\mathfrak{D}^{i,\nu}$ of $i$ consists of a map, which is defined as

$\displaystyle\mathfrak{D}^{i}:\bm{\Pi}\times\color[rgb]{0.25,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.1,1}\pgfsys@color@cmyk@stroke{0.75}{0.90}{0}{0}\pgfsys@color@cmyk@fill{0.75}{0.90}{0}{0}\bm{\Pi}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\times\color[rgb]{1,0.04,0.61}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.04,0.61}\pgfsys@color@cmyk@stroke{0}{0.96}{0.39}{0}\pgfsys@color@cmyk@fill{0}{0.96}{0.39}{0}\mathbb{P}(-i)\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\times\mathcal{S}\rightarrow\\{\mathfrak{D}^{i}_{{\bm{\pi}}}(\cdot|s,\color[rgb]{0.25,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.1,1}\pgfsys@color@cmyk@stroke{0.75}{0.90}{0}{0}\pgfsys@color@cmyk@fill{0.75}{0.90}{0}{0}{\bm{\bar{\pi}}}\color[rgb]{1,0.04,0.61}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.04,0.61}\pgfsys@color@cmyk@stroke{0}{0.96}{0.39}{0}\pgfsys@color@cmyk@fill{0}{0.96}{0.39}{0}^{j_{1:m}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}):\mathcal{P}(\mathcal{A}^{i})\rightarrow\mathbb{R}\\},$

such that for all arguments, under notation
$\mathfrak{D}^{i}_{\bm{\pi}}\big{(}\hat{\pi}^{i}|s,{\bm{\bar{\pi}}}^{j_{1:m}}\big{)}\triangleq\mathfrak{D}^{i}_{\bm{\pi}}\big{(}\hat{\pi}^{i}(\cdot^{i}|s)|{\bm{\bar{\pi}}}^{j_{1:m}},s\big{)}$,

  1. 1.

$\mathfrak{D}^{i}_{\bm{\pi}}\big{(}\hat{\pi}^{i}|s,{\bm{\bar{\pi}}}^{j_{1:m}}\big{)}\geq\mathfrak{D}^{i}_{\bm{\pi}}\big{(}\pi^{i}|s,{\bm{\bar{\pi}}}^{j_{1:m}}\big{)}=0$
(non-negativity),

  2. 2.

$\mathfrak{D}^{i}_{\bm{\pi}}\big{(}\hat{\pi}^{i}|s,{\bm{\bar{\pi}}}^{j_{1:m}}\big{)}$
has all Gâteaux derivatives zero at $\hat{\pi}^{i}=\pi^{i}$ (zero gradient),

and a probability distribution
$\nu^{i}_{{\bm{\pi}},\hat{\pi}^{i}}\in\mathcal{P}(\mathcal{S})$ over states
that can (but does not have to) depend on ${\bm{\pi}}$ and $\hat{\pi}^{i}$,
and such that the drift $\mathfrak{D}^{i,\nu}$ of $\hat{\pi}^{i}$ from
$\pi^{i}$ with respect to ${\bm{\bar{\pi}}}^{j_{1:m}}$, defined as

$\displaystyle\mathfrak{D}^{i,\nu}_{{\bm{\pi}}}(\hat{\pi}^{i}|{\bm{\bar{\pi}}}^{j_{1:m}})\triangleq\mathbb{E}_{{\textnormal{s}}\sim\nu^{i}_{{\bm{\pi}},\hat{\pi}^{i}}}\big{[}\mathfrak{D}^{i}_{\bm{\pi}}\big{(}\hat{\pi}^{i}|{\textnormal{s}},{\bm{\bar{\pi}}}^{j_{1:m}}\big{)}\big{]},$

is continuous with respect to ${\bm{\pi}},{\bm{\bar{\pi}}}^{j_{1:m}}$, and
$\hat{\pi}^{i}$. We say that the HADF is positive if
$\mathfrak{D}^{i,\nu}_{{\bm{\pi}}}(\hat{\pi}^{i}|{\bm{\bar{\pi}}}^{j_{1:m}})=0$
implies $\hat{\pi}^{i}=\pi^{i}$, and trivial if
$\mathfrak{D}^{i,\nu}_{{\bm{\pi}}}(\hat{\pi}^{i}|{\bm{\bar{\pi}}}^{j_{1:m}})=0$
for all ${\bm{\pi}},{\bm{\bar{\pi}}}^{j_{1:m}}$, and $\hat{\pi}^{i}$, .

Intuitively, the drift
$\mathfrak{D}_{{\bm{\pi}}}^{i,\nu}(\hat{\pi}^{i}|{\bm{\bar{\pi}}}^{j_{1:m}})$
is a notion of distance between $\pi^{i}$ and $\hat{\pi}^{i}$, given that
agents $j_{1:m}$ just updated to ${\bm{\bar{\pi}}}^{j_{1:m}}$. We highlight
that, under this conditionality, the same update (from $\pi^{i}$ to
$\hat{\pi}^{i}$) can have different sizes—this will later enable HAML agents
to softly constraint their learning steps in a coordinated way. Before that,
we introduce a notion that renders hard constraints, which may be a part of an
algorithm design, or an inherrent limitation.

######  Definition 2.

Let $i\in\mathcal{N}$. We say that,
$\mathcal{U}^{i}:\bm{\Pi}\times\Pi^{i}\rightarrow\mathbb{P}(\Pi^{i})$ is a
neighbourhood operator if $\forall\pi^{i}\in\Pi^{i}$,
$\mathcal{U}_{{\bm{\pi}}}^{i}(\pi^{i})$ contains a closed ball, _i.e._ , there
exists a state-wise monotonically non-decreasing metric
$\chi:\Pi^{i}\times\Pi^{i}\rightarrow\mathbb{R}$ such that
$\forall\pi^{i}\in\Pi^{i}$ there exists $\delta^{i}>0$ such that
$\chi(\pi^{i},\bar{\pi}^{i})\leq\delta^{i}\implies\bar{\pi}^{i}\in\mathcal{U}^{i}_{{\bm{\pi}}}(\pi^{i})$.

Throughout this work, for every joint policy ${\bm{\pi}}$, we will associate
it with its sampling distribution—a positive state distribution
$\beta_{{\bm{\pi}}}\in\mathcal{P}(\mathcal{S})$ that is continuous in
${\bm{\pi}}$ [kuba2022mirror]. With these notions defined, we introduce the
main definition of the paper.

######  Definition 3.

Let $i\in\mathcal{N}$, $j^{1:m}\in\mathbb{P}(-i)$, and $\mathfrak{D}^{i,\nu}$
be a HADF of agent $i$. The heterogeneous-agent mirror operator (HAMO)
integrates the advantage function as

$\displaystyle\big{[}\mathcal{M}^{(\hat{\pi}^{i})}_{\mathfrak{D}^{i,\nu},{\bm{\bar{\pi}}}^{j_{1:m}}}A_{{\bm{\pi}}}\big{]}(s)\triangleq\mathbb{E}_{{\mathbf{a}}^{j_{1:m}}\sim{\bm{\bar{\pi}}}^{j_{1:m}},{\textnormal{a}}^{i}\sim\hat{\pi}^{i}}\Big{[}A^{i}_{{\bm{\pi}}}(s,{\mathbf{a}}^{j_{1:m}},{\textnormal{a}}^{i})\Big{]}-\frac{\nu^{i}_{{\bm{\pi}},\hat{\pi}^{i}}(s)}{\beta_{{\bm{\pi}}}(s)}\mathfrak{D}^{i}_{{\bm{\pi}}}\Big{(}\hat{\pi}^{i}\big{|}s,{\bm{\bar{\pi}}}^{j_{1:m}}\Big{)}.$

We note two important facts. First, when
$\nu^{i}_{{\bm{\pi}},\hat{\pi}^{i}}=\beta_{{\bm{\pi}}}$, the fraction from the
front of the HADF in HAMO disappears, making it only a difference between the
advantage and the HADF’s evaluation. Second, when $\hat{\pi}^{i}=\pi^{i}$,
HAMO evaluates to zero. Therefore, as the HADF is non-negative, a policy
$\hat{\pi}^{i}$ that improves HAMO must make it positive, and thus leads to
the improvement of the multi-agent advantage of agent $i$. In the next
subsection, we study the properties of HAMO in more details, as well as use it
to construct HAML—a general framework for MARL algorithm design.

###  4.2 Theoretical Properties of HAML

It turns out that, under certain configuration, agents’ local improvements
result in the joint improvement of all agents, as described by the lemma
below.

######  Lemma 2 (HAMO Is All You Need).

Let $\bm{\pi}_{\text{old}}$ and ${\bm{\pi}}_{\text{new}}$ be joint policies
and let $i_{1:n}\in\text{Sym}(n)$ be an agent permutation. Suppose that, for
every state $s\in\mathcal{S}$,

$\displaystyle\big{[}\mathcal{M}^{(\pi^{i_{m}}_{\text{new}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}_{\text{new}}^{i_{1:m-1}}}A_{\bm{{\bm{\pi}}_{\text{old}}}}\big{]}(s)\geq\big{[}\mathcal{M}^{(\pi^{i_{m}}_{\text{old}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}_{\text{new}}^{i_{1:m-1}}}A_{\bm{{\bm{\pi}}_{\text{old}}}}\big{]}(s).$
(5)

Then, $\bm{\pi}_{\text{new}}$ is jointly better than $\bm{\pi}_{\text{old}}$,
so that for every state $s$,

$\displaystyle V_{\bm{\pi}_{\text{new}}}(s)\geq V_{\bm{\pi}_{\text{old}}}(s).$

Subsequently, the monotonic improvement property of the joint return follows
naturally, as

$\displaystyle J(\bm{\pi}_{\text{new}})=\mathbb{E}_{{\textnormal{s}}\sim
d}\big{[}V_{\bm{\pi}_{\text{new}}}(s)\big{]}\geq\mathbb{E}_{{\textnormal{s}}\sim
d}\big{[}V_{\bm{\pi}_{\text{old}}}(s)\big{]}=J(\bm{\pi}_{\text{old}}).$

However, the conditions of the lemma require every agent to solve
$|\mathcal{S}|$ instances of Inequality (5), which may be an intractable
problem. We shall design a single optimisation objective whose solution
satisfies those inequalities instead. Furthermore, to have a practical
application to large-scale problems, such an objective should be estimatable
via sampling. To handle these challenges, we introduce the following Algorithm
Template 1 which generates a continuum of HAML algorithms.

Initialise a joint policy $\bm{\pi}_{0}=(\pi^{1}_{0},\dots,\pi^{n}_{0})$;

for  _$k=0,1,\dots$_ do

Compute the advantage function $A_{\bm{\pi}_{k}}(s,{\bm{a}})$ for all
state-(joint)action pairs $(s,{\bm{a}})$;

Draw a permutaion $i_{1:n}$ of agents at random \\\from a positive
distribution $p\in\mathcal{P}(\text{Sym}(n))$;

for  _$m=1:n$_ do

Make an update
$\pi^{i_{m}}_{k+1}=\operatorname*{arg\,max}\limits_{\pi^{i_{m}}\in\mathcal{U}^{i_{m}}_{{\bm{\pi}}_{k}}(\pi^{i_{m}}_{k})}\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\pi}}_{k}}}\Big{[}\big{[}\mathcal{M}^{(\pi^{i_{m}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}_{k+1}^{i_{1:m-1}}}A_{\bm{{\bm{\pi}}_{k}}}\big{]}(s)\Big{]}$;

Output : A limit-point joint policy ${\bm{\pi}}_{\infty}$

Algorithm Template 1 Heterogeneous-Agent Mirror Learning

Based on Lemma 2 and the fact that
$\pi^{i}\in\mathcal{U}_{{\bm{\pi}}}^{i}(\pi^{i}),\forall
i\in\mathcal{N},\pi^{i}\in\Pi^{i}$, we can know any HAML algorithm (weakly)
improves the joint return at every iteration. In practical settings, such as
deep MARL, the maximisation step of a HAML method can be performed by a few
steps of gradient ascent on a sample average of HAMO (see Definition 1). We
also highlight that if the neighbourhood operators $\mathcal{U}^{i}$ can be
chosen so that they produce small policy-space subsets, then the resulting
updates will be not only improving but also small. This, again, is a desirable
property while optimising neural-network policies, as it helps stabilise the
algorithm. One may wonder why the order of agents in HAML updates is
randomised at every iteration; this condition has been necessary to establish
convergence to NE, which is intuitively comprehendable: fixed-point joint
policies of this randomised procedure assure that none of the agents is
incentivised to make an update, namely reaching a NE. We provide the full list
of the most fundamental HAML properties in Theorem 1 which shows that any
method derived from Algorithm Template 1 solves the cooperative MARL problem.

######  Theorem 1 (The Fundamental Theorem of Heterogeneous-Agent Mirror
Learning).

Let, for every agent $i\in\mathcal{N}$, $\mathfrak{D}^{i,\nu}$ be a HADF,
$\mathcal{U}^{i}$ be a neighbourhood operator, and let the sampling
distributions $\beta_{{\bm{\pi}}}$ depend continuously on ${\bm{\pi}}$. Let
$\bm{\pi}_{0}\in\bm{\Pi}$, and the sequence of joint policies
$(\bm{\pi}_{k})_{k=0}^{\infty}$ be obtained by a HAML algorithm induced by
$\mathfrak{D}^{i,\nu},\mathcal{U}^{i},\forall i\in\mathcal{N}$, and
$\beta_{{\bm{\pi}}}$. Then, the joint policies induced by the algorithm enjoy
the following list of properties

  1. 1.

Attain the monotonic improvement property,

$\displaystyle J(\bm{\pi}_{k+1})\ \geq\ J(\bm{\pi}_{k}),$

  2. 2.

Their value functions converge to a Nash value function $V^{\text{NE}}$

$\displaystyle\lim_{k\rightarrow\infty}V_{\bm{\pi}_{k}}=V^{\text{NE}},$

  3. 3.

Their expected returns converge to a Nash return,

$\displaystyle\lim_{k\rightarrow\infty}J(\bm{\pi}_{k})=J^{\text{NE}},$

  4. 4.

Their $\omega$-limit set consists of Nash equilibria.

See the proof in Appendix A. With the above theorem, we can conclude that HAML
provides a template for generating theoretically sound, stable, monotonically
improving algorithms that enable agents to learn solving multi-agent
cooperation tasks.

###  4.3 Existing HAML Instances: HATRPO and HAPPO

As a sanity check for its practicality, we show that two SOTA MARL
methods—HATRPO and HAPPO [kuba2021trust]—are valid instances of HAML, which
also provides an explanation for their excellent empirical performance.

We begin with an intuitive example of HATRPO, where agent $i_{m}$ (the
permutation $i_{1:n}$ is drawn from the uniform distribution) updates its
policy so as to maximise (in $\bar{\pi}^{i_{m}}$)

$\displaystyle\mathbb{E}_{{\textnormal{s}}\sim\rho_{\bm{\pi}_{\text{old}}},{\mathbf{a}}^{i_{1:m-1}}\sim{\bm{\pi}}^{i_{1:m-1}}_{\text{new}},{\textnormal{a}}^{i_{m}}\sim\bar{\pi}^{i_{m}}}\Big{[}A^{i_{m}}_{\bm{\pi}_{\text{old}}}({\textnormal{s}},{\mathbf{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\Big{]},\
\ \ \text{subject to}\
\overline{D}_{\text{KL}}(\pi^{i_{m}}_{\text{old}},\bar{\pi}^{i_{m}})\leq\delta.$

This optimisation objective can be casted as a HAMO with the trivial HADF
$\mathfrak{D^{i_{m},\nu}}\equiv 0$, and the KL-divergence neighbourhood
operator

$\displaystyle\mathcal{U}^{i_{m}}_{{\bm{\pi}}}(\pi^{i_{m}})=\Big{\\{}\bar{\pi}^{i_{m}}\
\Big{|}\
\mathbb{E}_{{\textnormal{s}}\sim\rho_{{\bm{\pi}}}}\Big{[}\text{KL}\big{(}\pi^{i_{m}}(\cdot^{i_{m}}|{\textnormal{s}}),\bar{\pi}^{i_{m}}(\cdot^{i_{m}}|{\textnormal{s}})\big{)}\Big{]}\leq\delta\Big{\\}}.$

The sampling distribution used in HATRPO is
$\beta_{\bm{\pi}}=\rho_{\bm{\pi}}$. Lastly, as the agents update their
policies in a random loop, the algorithm is an instance of HAML. Hence, it is
monotonically improving and converges to a Nash equilibrium set.

In HAPPO, the update rule of agent $i_{m}$ is changes with respect to HATRPO
as

$\displaystyle\mathbb{E}_{{\textnormal{s}}\sim\rho_{\bm{\pi}_{\text{old}}},{\mathbf{a}}^{i_{1:m-1}}\sim{\bm{\pi}}^{i_{1:m-1}}_{\text{new}},{\textnormal{a}}^{i_{m}}\sim\pi^{i_{m}}_{\text{old}}}\Big{[}\min\big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}})A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\mathbf{a}}^{i_{1:m}}),\text{clip}\big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}}),1\pm\epsilon\big{)}A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\mathbf{a}}^{i_{1:m}})\big{)}\Big{]},$

where
${\textnormal{r}}(\bar{\pi}^{i})=\frac{\bar{\pi}^{i}({\textnormal{a}}^{i}|{\textnormal{s}})}{\pi^{i}_{\text{old}}({\textnormal{a}}^{i}|{\textnormal{s}})}$.
We show in Appendix D that this optimisation objective is equivalent to

$\displaystyle\mathbb{E}_{{\textnormal{s}}\sim\rho_{\bm{\pi}_{\text{old}}}}\Big{[}\mathbb{E}_{{\mathbf{a}}^{i_{1:m-1}}\sim{\bm{\pi}}^{i_{1:m-1}}_{\text{new}},{\textnormal{a}}^{i_{m}}\sim\bar{\pi}^{i_{m}}}\big{[}A^{i_{m}}_{\bm{\pi}_{\text{old}}}({\textnormal{s}},{\mathbf{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\big{]}$
$\displaystyle\quad\quad\quad\quad\quad-\color[rgb]{0.25,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.1,1}\pgfsys@color@cmyk@stroke{0.75}{0.90}{0}{0}\pgfsys@color@cmyk@fill{0.75}{0.90}{0}{0}\mathbb{E}_{{\mathbf{a}}^{i_{1:m}}\sim{\bm{\pi}}^{i_{1:m}}_{\text{old}}}\big{[}\text{ReLU}\big{(}\big{[}{\textnormal{r}}(\bar{\pi}^{i_{m}})-\text{clip}\big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}}),1\pm\epsilon\big{)}\big{]}A^{i_{1:m}}_{\bm{\pi}_{\text{old}}}(s,{\mathbf{a}}^{i_{1:m}})\big{)}\big{]}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
The purple  term is clearly non-negative due to the presence of the ReLU
funciton. Furthermore, for policies $\bar{\pi}^{i_{m}}$ sufficiently close to
$\pi^{i_{m}}_{\text{old}}$, the clip operator does not activate, thus
rendering ${\textnormal{r}}(\bar{\pi}^{i_{m}})$ unchanged. Therefore, the
purple  term is zero at and in a region around
$\bar{\pi}^{i_{m}}=\pi^{i_{m}}_{\text{old}}$, which also implies that its
Gâteaux derivatives are zero. Hence, it evaluates a HADF for agent $i_{m}$,
thus making HAPPO a valid HAML instance.

Finally, we would like to highlight that these results about HATRPO and HAPPO
significantly strengthen the work originally by [kuba2021trust] who only
derived these learning protocols as approximations to a theoretically sound
algorithm (see Algorithm 1 in [kuba2021trust]), yet without such level of
insights.

###  4.4 New HAML Instances: HAA2C and HADDPG

In this subsection, we exemplify how HAML can be used for derivation of
principled MARL algorithms, and introduce heterogeneous-agent extensions of
A2C and DDPG, different from those in Subsection 3.2. Our goal is not to
refresh new SOTA performance on challenging tasks, but rather to verify the
correctness of our theory, as well as deliver more robust versions of multi-
agent extensions of popular RL algorithms such as A2C and DDPG.

#### HAA2C

intends to optimise the policy for the joint advantage function at every
iteration, and similar to A2C, does not impose any penalties or constraints on
that procedure. This learning procedure is accomplished by, first, drawing a
random permutation of agents $i_{1:n}$, and then performing a few steps of
gradient ascent on the objective of

$\displaystyle\mathbb{E}_{{\textnormal{s}}\sim\rho_{{\bm{\pi}}_{\text{old}}},{\mathbf{a}}^{i_{1:m}}\sim{\bm{\pi}}^{i_{1:m}}_{\text{old}}}\Big{[}\frac{{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}({\mathbf{a}}^{i_{1:m-1}}|{\textnormal{s}})\pi^{i_{m}}({\textnormal{a}}^{i_{m}}|{\textnormal{s}})}{{\bm{\pi}}^{i_{1:m-1}}_{\text{old}}({\mathbf{a}}^{i_{1:m-1}}|{\textnormal{s}})\pi^{i_{m}}_{\text{old}}({\textnormal{a}}^{i_{m}}|{\textnormal{s}})}A_{{\bm{\pi}}_{\text{old}}}^{i_{m}}({\textnormal{s}},{\mathbf{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\Big{]},$
(6)

with respect to $\pi^{i_{m}}$ parameters, for each agent $i_{m}$ in the
permutation, sequentially. In practice, we replace the multi-agent advantage
$A_{{\bm{\pi}}_{\text{old}}}^{i_{m}}({\textnormal{s}},{\mathbf{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})$
with the joint advantage estimate which, thanks to the joint importance
sampling in Equation (6), poses the same objective on the agent (see Appendix
E for full pseudocode).

#### HADDPG

aims to maximise the state-action value function off-policy. As it is a
deterministic-action method, and thus importance sampling in its case
translates to replacement of the old action inputs to the critic with the new
ones. Namely, agent $i_{m}$ in a random permutation $i_{1:n}$ maximises

$\displaystyle\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\mu}}_{\text{old}}}}\Big{[}Q^{i_{1:m}}_{{\bm{\mu}}_{\text{old}}}\big{(}{\textnormal{s}},{\bm{\mu}}_{\text{new}}^{i_{1:m-1}}({\textnormal{s}}),\mu^{i_{m}}(s)\big{)}\Big{]},$
(7)

with respect to $\mu^{i_{m}}$, also with a few steps of gradient ascent.
Similar to HAA2C, optimising the state-action value function (with the old
action replacement) is equivalent to the original multi-agent value (see
Appendix E for full pseudocode).

We are fully aware that none of these two methods exploits the entire
abundance of the HAML framework—they do not possess HADFs or neighbourhood
operators, as oppose to HATRPO or HAPPO. Thus, we speculate that the range of
opportunities for HAML algorithm design is yet to be discovered with more
future work. Nevertheless, we begin this search from these two straightforward
methods, and analyse their performance in the next section.

Figure 1: Comparison between HAA2C (yellow) vs MAA2C-S (blue) and MAA2C-NS
(pink) in SMAC.

##  5 Experiments and Results

In this section(1)(1)(1)Our code is available at
https://github.com/anonymouswater/HAML, we challenge the capabilities of HAML
in practice by testing HAA2C and HADDPG on the most challenging MARL
benchmarks—we use StarCraft Multi-Agent Challenge [samvelyanstarcraft] and
Multi-Agent MuJoCo [peng2020facmac], for discrete (only HAA2C) and continuous
action settings, respectively.

We begin by demonstrating the performance of HAA2C. As a baseline, we use its
“naive” predecessor, MAA2C, in both policy-sharing (MAA2C-S) and heterogeneous
(MAA2C-NS) versions.

Figure 2: Comparison between HAA2C (yellow) vs MAA2C-S (blue) and MAA2C-NS
(pink) in MAMuJoCo.

Results on Figures 1 & 2 show that HAA2C generally achieves higher rewards in
SMAC than both versions of MAA2C, while maintaining lower variance. The
performance gap increases in MAMuJoCo, where the agents must learn diverse
policies to master complex movements [kuba2021trust]. Here, echoing
Proposition 1, the homogeneous MAA2C-S fails completely, and conventional,
heterogeneous MAA2C-NS underperforms by a significant margin (recall
Proposition 2).

As HADDPG is a continuous-action method, we test it only on MAMuJoCo
(precisely 6 tasks) and compare it to MADDPG.

Figure 3: Comparison between HADDPG (yellow) and MADDPG (pink) in MAMuJoCo.

Figure 3 revelas that HADDPG achieves higher reward than MADDPG, while
sometimes displaying significantly lower variance (_e.g_ in Reacher-2x1 and
Swimmer-2x1). Hence, we conclude that HADDPG performs better.

##  6 Conclusion

In this paper, we described and addressed the problem of lacking principled
treatments for cooperative MARL tasks. Our main contribution is the
development of heterogeneous-agent mirror learning (HAML), a class of provably
correct MARL algorithms, whose properties are rigorously profiled. We verified
the correctness and the practicality of HAML by interpreting current SOTA
methods—HATRPO and HAPPO—as HAML instances and also by deriving and testing
heterogeneous-agent extensions of successful RL algorithms, named as HAA2C and
HADDPG. We expect HAML to help create a template for designing both principled
and practical MARL algorithms hereafter.

## References

  * [1] Lawrence M Ausubel and Raymond J Deneckere.  A generalized theorem of the maximum.  Economic Theory, 3(1):99–107, 1993.
  * [2] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al.  Dota 2 with large scale deep reinforcement learning.  arXiv preprint arXiv:1912.06680, 2019.
  * [3] Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson.  Is independent learning all you need in the starcraft multi-agent challenge?  arXiv preprint arXiv:2011.09533, 2020.
  * [4] Christian Schröder de Witt, Bei Peng, Pierre-Alexandre Kamienny, Philip H. S. Torr, Wendelin Böhmer, and Shimon Whiteson.  Deep multi-agent reinforcement learning for decentralized continuous cooperative control.  CoRR, abs/2003.06709, 2020.
  * [5] Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry.  Implementation matters in deep policy gradients: A case study on ppo and trpo.  arXiv preprint arXiv:2005.12729, 2020.
  * [6] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson.  Counterfactual multi-agent policy gradients.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
  * [7] Chloe Ching-Yun Hsu, Celestine Mendler-Dünner, and Moritz Hardt.  Revisiting design choices in proximal policy optimization.  arXiv preprint arXiv:2009.10897, 2020.
  * [8] Jakub Grudzien Kuba, Ruiqing Chen, Munning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang.  Trust region policy optimisation in multi-agent reinforcement learning.  ICLR, 2022.
  * [9] Jakub Grudzien Kuba, Christian Schroeder de Witt, and Jakob Foerster.  Mirror learning: A unifying framework of policy optimisation.  ICML, 2022.
  * [10] Jakub Grudzien Kuba, Muning Wen, Linghui Meng, Haifeng Zhang, David Mguni, Jun Wang, Yaodong Yang, et al.  Settling the variance of multi-agent policy gradients.  Advances in Neural Information Processing Systems, 34:13458–13470, 2021.
  * [11] Hepeng Li and Haibo He.  Multi-agent trust region policy optimization.  arXiv preprint arXiv:2010.07916, 2020.
  * [12] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  arXiv preprint arXiv:1509.02971, 2015.
  * [13] Michael L Littman.  Markov games as a framework for multi-agent reinforcement learning.  In Machine learning proceedings 1994, pages 157–163. Elsevier, 1994\.
  * [14] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 6382–6393, 2017.
  * [15] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 6382–6393, 2017.
  * [16] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In International conference on machine learning, pages 1928–1937. PMLR, 2016.
  * [17] John Nash.  Non-cooperative games.  Annals of mathematics, pages 286–295, 1951.
  * [18] Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht.  Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks.  In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks (NeurIPS), 2021.
  * [19] Bei Peng, Tabish Rashid, Christian A Schroeder de Witt, Pierre-Alexandre Kamienny, Philip HS Torr, Wendelin Böhmer, and Shimon Whiteson.  Facmac: Factored multi-agent centralised policy gradients.  arXiv e-prints, pages arXiv–2003, 2020.
  * [20] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson.  The starcraft multi-agent challenge.  2019\.
  * [21] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In International conference on machine learning, pages 1889–1897. PMLR, 2015.
  * [22] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel.  High-dimensional continuous control using generalized advantage estimation.  arXiv preprint arXiv:1506.02438, 2015.
  * [23] John Schulman, F. Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  ArXiv, abs/1707.06347, 2017.
  * [24] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller.  Deterministic policy gradient algorithms.  In International conference on machine learning, pages 387–395. PMLR, 2014.
  * [25] R. S. Sutton, D. Mcallester, S. Singh, and Y. Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In Advances in Neural Information Processing Systems 12, volume 12, pages 1057–1063. MIT Press, 2000.
  * [26] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  2018\.
  * [27] Yuhui Wang, Hao He, and Xiaoyang Tan.  Truly proximal policy optimization.  In Uncertainty in Artificial Intelligence, pages 113–122. PMLR, 2020.
  * [28] Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Duburcq, Minghao Zhang, Hang Su, and Jun Zhu.  Tianshou: a highly modularized deep reinforcement learning library.  arXiv preprint arXiv:2107.14171, 2021.
  * [29] Yaodong Yang and Jun Wang.  An overview of multi-agent reinforcement learning from game theoretical perspective.  arXiv preprint arXiv:2011.00583, 2020.
  * [30] Chao Yu, A. Velu, Eugene Vinitsky, Yu Wang, A. Bayen, and Yi Wu.  The surprising effectiveness of mappo in cooperative, multi-agent games.  ArXiv, abs/2103.01955, 2021.
  * [31] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar.  Fully decentralized multi-agent reinforcement learning with networked agents.  In International Conference on Machine Learning, pages 5872–5881. PMLR, 2018.

##  Appendix A Proofs of Preliminary Results

###  A.1 Proof of Lemma 1

See 1

###### Proof.

(We quote the proof from [kuba2021trust].) We start as expressing the multi-
agent advantage as a telescoping sum, and then rewrite it using the definition
of multi-agent advantage,

$\displaystyle A_{{\bm{\pi}}}^{i_{1:m}}(s,{\bm{a}}^{i_{1:m}})$
$\displaystyle=Q_{{\bm{\pi}}}^{i_{1:m}}(s,{\bm{a}}^{i_{1:m}})-V_{{\bm{\pi}}}(s)$
$\displaystyle=\sum_{j=1}^{m}\big{[}Q_{{\bm{\pi}}}^{i_{1:j}}(s,{\bm{a}}^{i_{1:j}})-Q_{{\bm{\pi}}}^{i_{1:j-1}}(s,{\bm{a}}^{i_{1:j-1}})\big{]}=\sum_{j=1}^{m}A^{i_{j}}_{{\bm{\pi}}}(s,{\bm{a}}^{i_{1:j-1}},a^{i_{j}}).$

∎

###  A.2 Proof of Proposition 2

See 2 As there is only one state, we can ignore the infinite horizon and the
discount factor $\gamma$, thus making the state-action value and the reward
functions equivalent, $Q\equiv r$.

Let us, for brevity, define $\pi^{i}=\pi^{i}_{\text{old}}(0)>0.6$, for
$i=1,2$. We have

$\displaystyle J({\bm{\pi}}_{\text{new}})$
$\displaystyle=\text{Pr}({\textnormal{a}}^{1}={\textnormal{a}}^{2}=0)r(0,0)+\big{(}1-\text{Pr}({\textnormal{a}}^{1}={\textnormal{a}}^{2}=0)\big{)}\mathbb{E}[r({\textnormal{a}}^{1},{\textnormal{a}}^{2})|({\textnormal{a}}^{1},{\textnormal{a}}^{2})\neq(0,0)]$
$\displaystyle>0.6^{2}\times 0-(1-0.6^{2})=-0.64.$

The update rule stated in the proposition can be equivalently written as

$\displaystyle\pi^{i}_{\text{new}}=\operatorname*{arg\,max}\limits_{\pi^{i}}\mathbb{E}_{{\textnormal{a}}^{i}\sim\pi^{i},{\textnormal{a}}^{-i}\sim\pi^{-i}_{\text{old}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}({\textnormal{a}}^{i},{\textnormal{a}}^{-i})\big{]}.$
(8)

We have

$\displaystyle\mathbb{E}_{{\textnormal{a}}^{-i}\sim\pi^{-i}_{\text{old}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}(0,{\textnormal{a}}^{-i})\big{]}=\pi^{-i}Q(0,0)+(1-\pi^{-i})Q(0,1)=\pi^{-i}r(0,0)+(1-\pi^{-i})r(0,1)=2(1-\pi^{-i}),$

and similarly

$\displaystyle\mathbb{E}_{{\textnormal{a}}^{-i}\sim\pi^{-i}_{\text{old}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}(1,{\textnormal{a}}^{-i})\big{]}=\pi^{-i}r(1,0)+(1-\pi^{-i})r(1,1)=2\pi^{-i}-(1-\pi^{-i})=3\pi^{-i}-1.$

Hence, if $\pi^{-i}>0.6$, then

$\displaystyle\mathbb{E}_{{\textnormal{a}}^{-i}\sim\pi^{-i}_{\text{old}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}(1,{\textnormal{a}}^{-i})\big{]}=3\pi^{-i}-1>3\times
0.6-1=0.8>2-2\pi^{-i}=\mathbb{E}_{{\textnormal{a}}^{-i}\sim\pi^{-i}_{\text{old}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}(0,{\textnormal{a}}^{-i})\big{]}.$

Therefore, for every $i$, the solution to Equation (8) is the greedy policy
$\pi^{i}_{\text{new}}(1)=1$. Therefore,

$\displaystyle J({\bm{\pi}}_{\text{new}})=Q(1,1)=r(1,1)=-1,$

which finishes the proof.

##  Appendix B Proof of HAMO Is All You Need Lemma

See 2

###### Proof.

Let
$\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)\triangleq\sum_{m=1}^{n}\frac{\nu^{i_{m}}_{{\bm{\pi}}_{\text{old}},\hat{\pi}^{i_{m}}}(s)}{\beta_{{\bm{\pi}}_{\text{old}}}(s)}\mathfrak{D}^{i_{m}}_{{\bm{\pi}}_{\text{old}}}(\pi^{i_{m}}_{\text{new}}|s,{\bm{\pi}}^{i_{1:m-1}}_{\text{new}})$.
Combining this with Lemma 1 gives

$\displaystyle\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}}}\big{[}A_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]}-\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)$
$\displaystyle=\sum_{m=1}^{n}\big{[}A_{{\bm{\pi}}_{\text{old}}}^{i_{m}}(s,{\bm{a}}^{i_{1:m-1}},a^{i_{m}})-\frac{\nu^{i_{m}}_{{\bm{\pi}}_{\text{old}},\pi^{i_{m}}_{\text{new}}}(s)}{\beta_{{\bm{\pi}}_{\text{old}}}(s)}\mathfrak{D}^{i_{m}}_{{\bm{\pi}}_{\text{old}}}(\pi^{i_{m}}_{\text{new}}|s,{\bm{\pi}}^{i_{1:m-1}}_{\text{new}})\big{]}$
by Inequality (5)
$\displaystyle\geq\sum_{m=1}^{n}\big{[}A_{{\bm{\pi}}_{\text{old}}}^{i_{m}}(s,{\bm{a}}^{i_{1:m-1}},a^{i_{m}})-\frac{\nu^{i_{m}}_{{\bm{\pi}}_{\text{old}},\pi^{i_{m}}_{\text{old}}}(s)}{\beta_{{\bm{\pi}}_{\text{old}}}(s)}\mathfrak{D}^{i_{m}}_{{\bm{\pi}}_{\text{old}}}(\pi^{i_{m}}_{\text{old}}|s,{\bm{\pi}}^{i_{1:m-1}}_{\text{new}})\big{]}$
$\displaystyle=\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{old}}}\big{[}A_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]}-\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{old}}|s).$

The resulting inequality can be equivalently rewritten as

$\displaystyle\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]}-\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)\geq\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{old}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]}-\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{old}}|s),\forall
s\in\mathcal{S}.$ (9)

We use it to prove the claim as follows,

$\displaystyle V_{{\bm{\pi}}_{\text{new}}}(s)$
$\displaystyle=\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}}}\big{[}Q_{{\bm{\pi}}_{\text{new}}}(s,{\mathbf{a}})\big{]}$
$\displaystyle=\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]}-\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)$
$\displaystyle\quad+\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)+\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}}}\big{[}Q_{{\bm{\pi}}_{\text{new}}}(s,{\mathbf{a}})-Q_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]},$
by Inequality (9)
$\displaystyle\geq\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{old}}}\big{[}Q_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]}-\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{old}}|s)$
$\displaystyle\quad+\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)+\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}}}\big{[}Q_{{\bm{\pi}}_{\text{new}}}(s,{\mathbf{a}})-Q_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]},$
$\displaystyle=V_{\pi_{\text{old}}}(s)+\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)+\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}}}\big{[}Q_{{\bm{\pi}}_{\text{new}}}(s,{\mathbf{a}})-Q_{{\bm{\pi}}_{\text{old}}}(s,{\mathbf{a}})\big{]}$
$\displaystyle=V_{\pi_{\text{old}}}(s)+\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)+\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}},{\textnormal{s}}^{\prime}\sim
P}\big{[}r(s,{\mathbf{a}})+\gamma
V_{{\bm{\pi}}_{\text{new}}}({\textnormal{s}}^{\prime})-r(s,{\mathbf{a}})-\gamma
V_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}}^{\prime})\big{]}$
$\displaystyle=V_{\pi_{\text{old}}}(s)+\widetilde{\mathfrak{D}}_{{\bm{\pi}}_{\text{old}}}({\bm{\pi}}_{\text{new}}|s)+\gamma\mathbb{E}_{{\mathbf{a}}\sim{\bm{\pi}}_{\text{new}},{\textnormal{s}}^{\prime}\sim
P}\big{[}V_{{\bm{\pi}}_{\text{new}}}({\textnormal{s}}^{\prime})-V_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}}^{\prime})\big{]}$
$\displaystyle\geq
V_{\pi_{\text{old}}}(s)+\gamma\inf_{s^{\prime}}\big{[}V_{{\bm{\pi}}_{\text{new}}}(s^{\prime})-V_{{\bm{\pi}}_{\text{old}}}(s^{\prime})\big{]}.$
$\displaystyle\text{Hence}\quad
V_{{\bm{\pi}}_{\text{new}}}(s)-V_{\pi_{\text{old}}}(s)\geq\gamma\inf_{s^{\prime}}\big{[}V_{{\bm{\pi}}_{\text{new}}}(s^{\prime})-V_{{\bm{\pi}}_{\text{old}}}(s^{\prime})\big{]}.$
$\displaystyle\text{Taking infimum over }s\text{ and simplifying}$
$\displaystyle(1-\gamma)\inf_{s}\big{[}V_{{\bm{\pi}}_{\text{new}}}(s)-V_{{\bm{\pi}}_{\text{old}}}(s)\big{]}\geq
0.$

Therefore,
$\inf_{s}\big{[}V_{{\bm{\pi}}_{\text{new}}}(s)-V_{{\bm{\pi}}_{\text{old}}}(s)\big{]}\geq
0$, which proves the lemma. ∎

##  Appendix C Proof of Theorem 1

######  Lemma 3.

Suppose an agent $i_{m}$ maximises the expected HAMO

$\displaystyle\pi^{i_{m}}_{\text{new}}=\operatorname*{arg\,max}\limits_{\pi^{i_{m}}\in\mathcal{U}^{i_{m}}_{{\bm{\pi}}_{\text{old}}}(\pi^{i_{m}}_{\text{old}})}\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\pi}}_{\text{old}}}}\Big{[}\big{[}\mathcal{M}^{(\pi^{i_{m}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}({\textnormal{s}})\Big{]}.$
(10)

Then, for every state $s\in\mathcal{S}$

$\displaystyle\big{[}\mathcal{M}^{(\pi^{i_{m}}_{\text{new}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}(s)\geq\big{[}\mathcal{M}^{(\pi^{i_{m}}_{\text{old}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}(s).$

###### Proof.

We will prove this statement by contradiction. Suppose that there exists
$s_{0}\in\mathcal{S}$ such that

$\displaystyle\big{[}\mathcal{M}^{(\pi^{i_{m}}_{\text{new}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}(s_{0})<\big{[}\mathcal{M}^{(\pi^{i_{m}}_{\text{old}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}(s_{0}).$
(11)

Let us define the following policy $\hat{\pi}^{i_{m}}$.

$\displaystyle\hat{\pi}^{i_{m}}(\cdot^{i_{m}}|s)=\begin{cases}\pi^{i_{m}}_{\text{old}}(\cdot^{i_{m}}|s),\
\text{at}\ s=s_{0}\\\ \pi^{i_{m}}_{\text{new}}(\cdot^{i_{m}}|s),\ \text{at}\
s\neq s_{0}\end{cases}$

Note that $\hat{\pi}^{i_{m}}$ is (weakly) closer to $\pi^{i_{m}}_{\text{old}}$
than $\pi^{i_{m}}_{\text{new}}$ at $s_{0}$, and at the same distance at other
states. Together with
$\pi^{i_{m}}_{\text{new}}\in\mathcal{U}^{i_{m}}_{{\bm{\pi}}_{\text{old}}}(\pi^{i_{m}}_{\text{old}})$,
this implies that
$\hat{\pi}^{i_{m}}\in\mathcal{U}^{i_{m}}_{{\bm{\pi}}_{\text{old}}}(\pi^{i_{m}}_{\text{old}})$.
Further,

$\displaystyle\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\pi}}_{\text{old}}}}\Big{[}\big{[}\mathcal{M}^{(\hat{\pi}^{i_{m}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}({\textnormal{s}})\Big{]}-\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\pi}}_{\text{old}}}}\Big{[}\big{[}\mathcal{M}^{(\pi^{i_{m}}_{\text{new}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}({\textnormal{s}})\Big{]}$
$\displaystyle\beta_{{\bm{\pi}}_{\text{old}}}(s_{0})\big{(}\big{[}\mathcal{M}^{(\hat{\pi}^{i_{m}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}(s_{0})-\big{[}\mathcal{M}^{(\hat{\pi}^{i_{m}})}_{\mathfrak{D}^{i_{m},\nu},{\bm{\pi}}^{i_{1:m-1}}_{\text{new}}}A_{{\bm{\pi}}_{\text{old}}}\big{]}(s_{0})\big{)}>0.$

The above contradicts $\pi^{i_{m}}_{\text{new}}$ as being the argmax of
Inequality (11), as $\hat{\pi}^{i_{m}}$ is strictly better. The contradiciton
finishes the proof. ∎

See 1

###### Proof.

Proof of Property 1.
It follows from combining Lemmas 2 & 3.

Proof of Properties 2, 3 & 4.
Step 1: convergence of the value function. By Lemma 2, we have that
$V_{{\bm{\pi}}_{k}}(s)\leq V_{{\bm{\pi}}_{k+1}}(s),\ \forall s\in\mathcal{S}$,
and that the value function is upper-bounded by $V_{\max}$. Hence, the
sequence of value functions $(V_{{\bm{\pi}}_{k}})_{k\in\mathbb{N}}$ converges.
We denote its limit by $V$.

Step 2: characterisation of limit points. As the joint policy space $\bm{\Pi}$
is bounded, by Bolzano-Weierstrass theorem, we know that the sequence
$({\bm{\pi}}_{k})_{k\in\mathbb{N}}$ has a convergent subsequence. Therefore,
it has at least one limit point policy. Let ${\bm{\bar{\pi}}}$ be such a limit
point. We introduce an auxiliary notation: for a joint policy ${\bm{\pi}}$ and
a permutation $i_{1:n}$, let $\text{HU}({\bm{\pi}},i_{1:n})$ be a joint policy
obtained by a HAML update from ${\bm{\pi}}$ along the permutation $i_{1:n}$.

Claim: For any permutation $z_{1:n}\in\text{Sym}(n)$,

$\displaystyle{\bm{\bar{\pi}}}=\text{HU}({\bm{\bar{\pi}}},z_{1:n}).$ (12)

Proof of Claim. Let
$\hat{{\bm{\pi}}}=\text{HU}({\bm{\bar{\pi}}},z_{1:n})\neq{\bm{\bar{\pi}}}$ and
$({\bm{\pi}}_{k_{r}})_{r\in\mathbb{N}}$ be a subsequence converging to
${\bm{\bar{\pi}}}$. Let us recall that the limit value function is unique and
denoted as $V$. Writing $\mathbb{E}_{i^{0:\infty}_{1:n}}[\cdot]$ for the
expectation operator under the stochastic process
$(i^{k}_{1:n})_{k\in\mathbb{N}}$ of update orders, for a state
$s\in\mathcal{S}$, we have

$\displaystyle 0$
$\displaystyle=\lim_{r\rightarrow\infty}\mathbb{E}_{i^{0:\infty}_{1:n}}\big{[}V_{{\bm{\pi}}_{k_{r}+1}}(s)-V_{{\bm{\pi}}_{k_{r}}}(s)\big{]}$
as every choice of permutation improves the value function
$\displaystyle\geq\lim_{r\rightarrow\infty}\text{P}(i^{k_{r}}_{1:n}=z_{1:n})\big{[}V_{\text{HU}({\bm{\pi}}_{k_{r}},z_{1:n})}(s)-V_{{\bm{\pi}}_{k_{r}}}(s)\big{]}$
$\displaystyle=p(z_{1:n})\lim_{r\rightarrow\infty}\big{[}V_{\text{HU}({\bm{\pi}}_{k_{r}},z_{1:n})}(s)-V_{{\bm{\pi}}_{k_{r}}}(s)\big{]}.$

By the continuity of the expected HAMO (following from the continuity of the
value function [kuba2021trust, Appendix A], HADFs, neighbourhood operators,
and the sampling distribution) we obtain that the first component of
$\text{HU}({\bm{\pi}}_{k_{r}},z_{1:n})$, which is $\pi^{z_{1}}_{k_{r}+1}$, is
continuous in ${\bm{\pi}}_{k_{r}}$ by Berge’s Maximum Theorem
[ausubel1993generalized]. Applying this argument recursively for
$z_{2},\dots,z_{n}$, we have that $\text{HU}({\bm{\pi}}_{k_{r}},z_{1:n})$ is
continuous in ${\bm{\pi}}_{k_{r}}$. Hence, as ${\bm{\pi}}_{k_{r}}$ converges
to ${\bm{\bar{\pi}}}$, its HU converges to the HU of ${\bm{\bar{\pi}}}$, which
is $\hat{{\bm{\pi}}}$. Hence, we continue wiriting the above derivation as

$\displaystyle=p(z_{1:n})\big{[}V_{\hat{{\bm{\pi}}}}(s)-V_{{\bm{\bar{\pi}}}}(s)\big{]}\geq
0,\ \text{by Lemma \ref{lemma:hamo}}.$

As $s$ was arbitrary, the state-value function of $\hat{{\bm{\pi}}}$ is the
same as that of ${\bm{\pi}}$: $V_{\hat{{\bm{\pi}}}}=V_{{\bm{\pi}}}$, by the
Bellman equation [sutton2018reinforcement]:
$Q(s,{\bm{a}})=r(s,{\bm{a}})+\gamma\mathbb{E}V({\textnormal{s}}^{\prime})$,
this also implies that their state-value and advantage functions are the same:
$Q_{\hat{{\bm{\pi}}}}=Q_{{\bm{\bar{\pi}}}}$ and
$A_{\hat{{\bm{\pi}}}}=A_{{\bm{\bar{\pi}}}}$. Let $m$ be the smallest integer
such that $\hat{\pi}^{z_{m}}\neq\bar{\pi}^{z_{m}}$. This means that
$\hat{\pi}^{z_{m}}$ achieves a greater expected HAMO than $\bar{\pi}^{z_{m}}$,
for which it is zero. Hence,

$\displaystyle
0<\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\pi}}}}\Big{[}\big{[}\mathcal{M}^{(\hat{\pi}^{z_{m}})}_{\mathfrak{D}^{z,\nu},{\bm{\bar{\pi}}}^{z_{1:m-1}}}A_{{\bm{\bar{\pi}}}}\big{]}(s)\Big{]}$
$\displaystyle=\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\pi}}}}\Big{[}\mathbb{E}_{{\mathbf{a}}^{z_{1:m}}\sim{\bm{\bar{\pi}}}^{z_{1:m-1}},{\textnormal{a}}^{z_{m}}\sim\hat{\pi}^{z_{m}}}\big{[}A^{z_{m}}_{{\bm{\bar{\pi}}}}(s,{\mathbf{a}}^{z_{1:m-1}},{\textnormal{a}}^{z_{m}})\big{]}-\frac{\nu^{z_{m}}_{{\bm{\bar{\pi}}},\hat{\pi}^{z_{m}}}(s)}{\beta_{{\bm{\bar{\pi}}}}(s)}\mathfrak{D}^{z_{m}}_{{\bm{\pi}}}(\hat{\pi}^{z_{m}}|s,{\bm{\bar{\pi}}}^{z_{1:m-1}})\Big{]}$
$\displaystyle=\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\pi}}}}\Big{[}\mathbb{E}_{{\mathbf{a}}^{z_{1:m}}\sim{\bm{\bar{\pi}}}^{z_{1:m-1}},{\textnormal{a}}^{z_{m}}\sim\hat{\pi}^{z_{m}}}\big{[}A^{z_{m}}_{\hat{{\bm{\pi}}}}(s,{\mathbf{a}}^{z_{1:m-1}},{\textnormal{a}}^{z_{m}})\big{]}-\frac{\nu^{z_{m}}_{{\bm{\bar{\pi}}},\hat{\pi}^{z_{m}}}(s)}{\beta_{{\bm{\bar{\pi}}}}(s)}\mathfrak{D}^{z_{m}}_{{\bm{\pi}}}(\hat{\pi}^{z_{m}}|s,{\bm{\bar{\pi}}}^{z_{1:m-1}})\Big{]}$
and as the expected value of the multi-agent advantage function is zero
$\displaystyle=\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\pi}}}}\Big{[}-\frac{\nu^{z_{m}}_{{\bm{\bar{\pi}}},\hat{\pi}^{z_{m}}}(s)}{\beta_{{\bm{\bar{\pi}}}}(s)}\mathfrak{D}^{z_{m}}_{{\bm{\pi}}}(\hat{\pi}^{z_{m}}|s,{\bm{\bar{\pi}}}^{z_{1:m-1}})\Big{]}\leq
0.$

This is a contradiction, and so the claim in Equation (12) is proved, and the
Step 2 is finished.

Step 3: dropping the HADF. Consider an arbitrary limit point joint policy
${\bm{\bar{\pi}}}$. By Step 2, for any permutation $i_{1:n}$, considering the
first component of the HU, and writing
$\nu^{i}=\nu^{i}_{{\bm{\bar{\pi}}},\pi^{i}}$,

$\displaystyle\bar{\pi}^{i_{1}}$
$\displaystyle=\max_{\pi^{i_{1}}\in\mathcal{U}^{i_{1}}_{{\bm{\pi}}}(\pi^{i_{1}})}\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\bar{\pi}}}}}\Big{[}\big{[}\mathcal{M}^{(\pi^{i_{1}})}_{\mathfrak{D}^{i_{1},\nu}}A_{{\bm{\bar{\pi}}}}\big{]}({\textnormal{s}})\Big{]}$
(13)
$\displaystyle=\max_{\pi^{i_{1}}\in\mathcal{U}^{i_{1}}_{{\bm{\pi}}}(\pi^{i_{1}})}\mathbb{E}_{{\textnormal{s}}\sim\beta_{{\bm{\bar{\pi}}}}}\Big{[}\mathbb{E}_{{\textnormal{a}}^{i_{1}}\sim\pi^{i_{1}}}\big{[}A_{{\bm{\bar{\pi}}}}({\textnormal{s}},{\textnormal{a}}^{i_{1}})\big{]}-\frac{\nu^{i_{1}}({\textnormal{s}})}{\beta_{{\bm{\bar{\pi}}}}({\textnormal{s}})}\mathfrak{D}^{i_{1}}_{{\bm{\bar{\pi}}}}(\pi^{i_{1}}|{\textnormal{s}})\Big{]}.$

As the HADF is non-negative, and at $\pi^{i_{1}}=\bar{\pi}^{i_{1}}$ its value
and of its all Gâteaux derivatives are zero, it follows by Step 3 of Theorem 1
of [kuba2022mirror] that for every $s\in\mathcal{S}$,

$\displaystyle\bar{\pi}^{i_{1}}(\cdot^{i_{m}}|s)=\operatorname*{arg\,max}\limits_{\pi^{i_{1}}\in\mathcal{P}(\mathcal{A}^{i_{1}})}\mathbb{E}_{{\textnormal{a}}^{i_{1}}\sim\pi^{i_{1}}}\big{[}Q_{{\bm{\bar{\pi}}}}^{i_{1}}(s,{\textnormal{a}}^{i_{1}})\big{]}.$

Step 4: Nash equilibrium. We have proved that ${\bm{\bar{\pi}}}$ satisfies

$\displaystyle\bar{\pi}^{i}(\cdot^{i}|s)$
$\displaystyle=\operatorname*{arg\,max}_{\pi^{i}(\cdot^{i}|s)\in\mathcal{P}(\mathcal{A}^{i})}\mathbb{E}_{{\textnormal{a}}^{i}\sim\pi^{i}}\big{[}Q^{i}_{{\bm{\bar{\pi}}}}(s,{\textnormal{a}}^{i})\big{]}$
$\displaystyle=\operatorname*{arg\,max}_{\pi^{i}(\cdot^{i}|s)\in\mathcal{P}(\mathcal{A}^{i})}\mathbb{E}_{{\textnormal{a}}^{i}\sim\pi^{i},{\mathbf{a}}^{-i}\sim{\bm{\bar{\pi}}}^{-i}}\big{[}Q_{{\bm{\bar{\pi}}}}(s,{\mathbf{a}})\big{]},\
\forall i\in\mathcal{N},s\in\mathcal{S}.$

Hence, by considering ${\bm{\bar{\pi}}}^{-i}$ fixed, we see that
$\bar{\pi}^{i}$ satisfies the condition for the optimal policy
[sutton2018reinforcement], and hence

$\displaystyle\bar{\pi}^{i}=\operatorname*{arg\,max}\limits_{\pi^{i}\in\Pi^{i}}J(\pi^{i},{\bm{\bar{\pi}}}^{-i}).$

Thus, ${\bm{\bar{\pi}}}$ is a Nash equilibrium. Lastly, this implies that the
value function corresponds to a Nash value function $V^{\text{NE}}$, the
return corresponds to a Nash return $J^{\text{NE}}$. ∎

##  Appendix D Casting HAPPO as HAML

The maximisation objective of agent $i_{m}$ in HAPPO is

$\displaystyle\mathbb{E}_{{\textnormal{s}}\sim\rho_{\bm{\pi}_{\text{old}}},{\mathbf{a}}^{i_{1:m-1}}\sim{\bm{\pi}}^{i_{1:m-1}}_{\text{new}},{\textnormal{a}}^{i_{m}}\sim\pi^{i_{m}}_{\text{old}}}\Big{[}\min\Big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}})A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\mathbf{a}}^{i_{1:m}}),\text{clip}\big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}}),1\pm\epsilon\big{)}A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\mathbf{a}}^{i_{1:m}})\Big{)}\Big{]}.$

Fixing $s$ and ${\bm{a}}^{i_{1:m-1}}$, we can rewrite it as

$\displaystyle\mathbb{E}_{{\textnormal{a}}^{i_{m}}\sim\bar{\pi}^{i_{m}}}\big{[}A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\big{]}-\mathbb{E}_{{\textnormal{a}}^{i_{m}}\sim\pi^{i_{m}}_{\text{old}}}\Big{[}{\textnormal{r}}(\bar{\pi}^{i_{m}})A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}(s,{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})$
$\displaystyle-\min\Big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}})A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}}),\text{clip}\big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}}),1\pm\epsilon\big{)}A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}(s,{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\Big{)}\Big{]}.$

By the multi-agent advantage decomposition,

$\displaystyle\mathbb{E}_{{\textnormal{a}}^{i_{m}}\sim\bar{\pi}^{i_{m}}}\big{[}A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\big{]}$
$\displaystyle=A_{{\bm{\pi}}_{\text{old}}}^{i_{1:m-1}}(s,{\bm{a}}^{i_{1:m-1}})+\mathbb{E}_{{\textnormal{a}}^{i_{m}}\sim\bar{\pi}^{i_{m}}}\big{[}A^{i_{m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\big{]}.$

Hence, the presence of the joint advantage of agents $i_{1:m}$ is equivalent
to the multi-agent advantage of $i_{m}$ given ${\bm{a}}^{i_{1:m-1}}$ that
appears in HAMO. Hence, we only need to show that that the subtracted term is
an HADF. Firstly, we change $\min$ into $\max$ with the identity $-\min
f(x)=\max[-f(x)]$.

$\displaystyle\mathbb{E}_{{\textnormal{a}}^{i_{m}}\sim\pi^{i_{m}}_{\text{old}}}\Big{[}{\textnormal{r}}(\bar{\pi}^{i_{m}})A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}(s,{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})$
$\displaystyle+\max\Big{(}-{\textnormal{r}}(\bar{\pi}^{i_{m}})A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}({\textnormal{s}},{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}}),-\text{clip}\big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}}),1\pm\epsilon\big{)}A^{i_{1:m}}_{{\bm{\pi}}_{\text{old}}}(s,{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\Big{)}\Big{]}$
which we then simplify
$\displaystyle\mathbb{E}_{{\textnormal{a}}^{i_{m}}\sim\pi_{\text{old}}^{i_{m}}}\Big{[}\max\Big{(}0,\big{[}{\textnormal{r}}(\bar{\pi}^{i_{m}})-\text{clip}\big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}}),1\pm\epsilon\big{)}\big{]}A^{i_{1:m}}_{\bm{\pi}_{\text{old}}}(s,{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\Big{)}\Big{]}$
$\displaystyle=\mathbb{E}_{{\textnormal{a}}^{i_{m}}\sim\pi^{i_{m}}_{\text{old}}}\Big{[}\text{ReLU}\Big{(}\big{[}{\textnormal{r}}(\bar{\pi}^{i_{m}})-\text{clip}\big{(}{\textnormal{r}}(\bar{\pi}^{i_{m}}),1\pm\epsilon\big{)}\big{]}A^{i_{1:m}}_{\bm{\pi}_{\text{old}}}(s,{\bm{a}}^{i_{1:m-1}},{\textnormal{a}}^{i_{m}})\Big{)}\Big{]}.$

As discussed in the main body of the paper, this is an HADF.

##  Appendix E Algorithms

Input: stepsize $\alpha$, batch size $B$, number of: agents $n$, episodes $K$,
steps per episode $T$, mini-epochs $e$;

Initialize: the critic network: $\phi$, the policy networks:
$\\{\theta^{i}\\}_{i\in\mathcal{N}}$, replay buffer $\mathcal{B}$;

for  _$k=0,1,\dots,K-1$_ do

Collect a set of trajectories by letting the agents act according their
policies,
${\textnormal{a}}^{i}\sim\pi^{i}_{\theta^{i}}(\cdot^{i}|{\textnormal{o}}^{i})$;

Push transitions
$\\{({\textnormal{o}}^{i}_{t},{\textnormal{a}}^{i}_{t},{\textnormal{o}}^{i}_{t+1},{\textnormal{r}}_{t}),\forall
i\in\mathcal{N},t\in T\\}$ into $\mathcal{B}$;

Sample a random minibatch of $B$ transitions from $\mathcal{B}$;

Estimate the returns $R$ and the advantage function,
$\hat{A}({\textnormal{s}},{\mathbf{a}})$, using $\hat{V}_{\phi}$ and GAE;

Draw a permutation of agents $i_{1:n}$ at random;

Set
$M^{i_{1}}({\textnormal{s}},{\mathbf{a}})=\hat{A}({\textnormal{s}},{\mathbf{a}})$;

for  _agent $i_{m}=i_{1},\dots,i_{n}$_ do

Set
$\pi^{i_{m}}_{0}({\textnormal{a}}^{i_{m}}|{\textnormal{o}}^{i_{m}})=\pi^{i_{m}}_{\theta^{i_{m}}}({\textnormal{a}}^{i_{m}}|{\textnormal{o}}^{i_{m}})$;

for  _mini-epoch $=1,\dots,e$_ do

Compute agent $i_{m}$’s policy gradient
${\mathbf{g}}^{i_{m}}=\nabla_{\theta^{i}}\frac{1}{B}\sum\limits_{b=1}^{B}M^{i_{m}}({\textnormal{s}}_{b},{\mathbf{a}}_{b})\frac{\pi^{i_{m}}_{\theta^{i_{m}}}({\textnormal{a}}^{i_{m}}_{b}|{\textnormal{o}}^{i_{m}}_{b})}{\pi^{i_{m}}_{0}({\textnormal{a}}^{i_{m}}_{b}|{\textnormal{o}}^{i_{m}}_{b})}$.
Update agent $i_{m}$’s policy by
$\theta^{i_{m}}=\theta^{i_{m}}+\alpha{\mathbf{g}}^{i_{m}}$.

Compute
$M^{i_{m+1}}({\textnormal{s}},{\mathbf{a}})=\frac{\pi^{i_{m}}_{\theta^{i_{m}}}({\textnormal{a}}^{i_{m}}|{\textnormal{o}}^{i_{m}})}{\pi^{i_{m}}_{0}({\textnormal{a}}^{i_{m}}|{\textnormal{o}}^{i_{m}})}M^{i_{m}}({\textnormal{s}},{\mathbf{a}})$
//unless $m=n$;

Update the critic by gradient descent on
$\frac{1}{B}\sum\limits_{{\textnormal{s}}}\big{(}\hat{V}_{\phi}({\textnormal{s}}_{b})-R_{b}\big{)}^{2}$.

Discard $\phi$. Deploy $\\{\theta^{i}\\}_{i\in\mathcal{N}}$ in execution;

Algorithm 2 HAA2C

Input: stepsize $\alpha$, Polyak coefficient $\tau$, batch size $B$, number
of: agents $n$, episodes $K$, steps per episode $T$, mini-epochs $e$;

Initialize: the critic networks: $\phi$ and $\phi^{\prime}$ and policy
networks: $\\{\theta^{i}\\}_{i\in\mathcal{N}}$, replay buffer $\mathcal{B}$,
random processes $\\{\mathcal{X}^{i}\\}_{i\in\mathcal{N}}$ for exploration;

for  _$k=0,1,\dots,K-1$_ do

Collect a set of transitions by letting the agents act according to their
deterministic policies with the exploratory noise
${\textnormal{a}}^{i}=\mu^{i}_{\theta^{i}}({\textnormal{o}}^{i})+\mathcal{X}^{i}_{t}$.
Push transitions
$\\{({\textnormal{o}}^{i}_{t},{\textnormal{a}}^{i}_{t},{\textnormal{o}}^{i}_{t+1},{\textnormal{r}}_{t}),\forall
i\in\mathcal{N},t\in T\\}$ into $\mathcal{B}$;

Sample a random minibatch of $B$ transitions from $\mathcal{B}$;

Compute the critic targets  $y_{t}={\textnormal{r}}_{t}+\gamma
Q_{\phi^{\prime}}({\textnormal{s}}_{t+1},{\mathbf{a}}_{t+1})$. Update the
critic by minimising the loss
$\phi=\operatorname*{arg\,min}_{\phi}\frac{1}{B}\sum_{t}\big{(}y_{t}-Q_{\phi}({\textnormal{s}}_{t},{\mathbf{a}}_{t})\big{)}^{2}$.
Draw a permutation of agents $i_{1:n}$ at random;

for  _agent $i_{m}=i_{1},\dots,i_{n}$_ do

Update agent $i_{m}$ by solving
$\theta^{i_{m}}=\operatorname*{arg\,max}_{\hat{\theta}^{i_{m}}}\frac{1}{B}\sum_{t}Q_{\phi}\big{(}{\textnormal{s}}_{t},\mu^{i_{1:m-1}}_{\theta^{i_{1:m-1}}}({\mathbf{o}}^{i_{1:m-1}}_{t}),\mu^{i_{m}}_{\hat{\theta}^{i_{m}}}({\textnormal{o}}^{i_{m}}_{t}),{\mathbf{a}}^{i_{m+1:n}}_{t}\big{)}$.
with $e$ mini-epochs of deterministic policy gradient ascent;

Update the target critic network smoothly
$\phi^{\prime}=\tau\phi+(1-\tau)\phi^{\prime}$.

Discard $\phi$. Deploy $\\{\theta^{i}\\}_{i\in\mathcal{N}}$ in execution;

Algorithm 3 HADDPG

##  Appendix F Experiments

###  F.1 Compute resources

For compute resources, We used one internal compute servers which consists
consisting of 6x RTX 3090 cards and 112 CPUs, however each model is trained on
at most 1 card.

###  F.2 Hyperparameters

We implement the MAA2C and HAA2C based on HAPPO/HATRPO [kuba2021trust]. We
offer the hyperparameter we use for SMAC in table 1 and for Mujoco in table 2.

Table 1: Common hyperparameters used in the SMAC domain. hyperparameters | value | hyperparameters | value | hyperparameters | value
---|---|---|---|---|---
critic lr | 5e-4 | optimizer | Adam | stacked-frames | 1
gamma | $0.99$ | optim eps | $1\mathrm{e}-5$ | batch size | 3200
gain | $0.01$ | hidden layer | 1 | training threads | 64
actor network | $\mathrm{mlp}$ | num mini-batch | 1 | rollout threads | 8
hypernet embed | 64 | max grad norm | 10 | episode length | 400
activation | ReLU | hidden layer dim | 64 | use huber loss | True
Table 2: Common hyperparameters used for MAA2C-NS, MAA2C-S and HAA2C in the Multi-Agent MuJoCo. hyperparameters | value | hyperparameters | value | hyperparameters | value
---|---|---|---|---|---
critic lr | $1\mathrm{e}-3$ | optimizer | Adam | num mini-batch | 1
gamma | $0.99$ | optim eps | $1\mathrm{e}-5$ | batch size | 4000
gain | $0.01$ | hidden layer | 1 | training threads | 8
std y coef | $0.5$ | actor network | $\mathrm{mlp}$ | rollout threads | 4
std x coef | 1 | max grad norm | 10 | episode length | 1000
activation | ReLU | hidden layer dim | 64 | eval episode | 32

In addition to those common hyperparameters, we set the mini-epoch for HAA2C
as 5. For actor learning rate, we set it as 2e-4 for HalfCheetah and Ant while
1e-4 for Walker2d.

We implement the MADDPG and HADDPG based on the Tianshou framework
[weng2021tianshou]. We offer the hyperparameter we use in table 3 and 4.

Table 3: Hyper-parameter used for MADDPG/HADDPG in the Multi-Agent MuJoCo domain hyperparameters | value | hyperparameters | value | hyperparameters | value
---|---|---|---|---|---
actor lr | $3\mathrm{e}-4$ | optimizer | Adam | replay buffer size | $1\mathrm{e}6$
critic lr | $1\mathrm{e}-3$ | exploration noise | $0.1$ | batch size | 1000
gamma | $0.99$ | step-per-epoch | 50000 | training num | 20
tau | $0.1$ | step-per-collector | 2000 | test num | 10
start-timesteps | 25000 | update-per-step | $0.025$ | epoch | 200
hidden-sizes | $[64,64]$ | episode length | 1000 |  |
Table 4: Parameter n-step used for MADDPG/HADDPG in the Multi-Agent MuJoCo  task | value | task | value | task | value
---|---|---|---|---|---
Reacher $(2\times 1)$ | $5$ |  Hopper $(3\times 1)$ | $20$ |  Walker $(3\times 2)$ | $5$
Ant $(4\times 2)$ | $20$ |  Swimmer $(2\times 1)$ | 5 |  Humanoid $(9|8)$ | 5