Heterogeneous-Agent Mirror Learning
Authors: Jakub Grudzien Kuba
Xidong Feng
Shiyao Ding
Hao Dong
Yaodong Yang
Venue: Submitted to ICLR 2023 (2023)
Keywords: deep multi-agent reinforcement learning
multi-agent reinforcement learning theory

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, 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.

Under review as a conference paper at ICLR 2023
HETEROGENEOUS-AGEN MIRROR LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
The necessity for cooperation among independent intelligent machines has pop- ularised cooperative multi-agent reinforcement learning (MARL) in the artificial intelligence (AI) research community. However, many research endeavours have been focused 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, this paper.we we introduce a novel framework named Heterogeneous-Agern Mirror Learning (HAML) that provides general template for MARL actor-critic algorithms. We prove that algorithms derived from the HAMI 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 prov- ing that the current state-of-the-art cooperative MARL algorithms, HATRPO and НАРРО, 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 StarCraftII and Multi-Agent MuJoCo tasks.
INTRODUCTION
While the policy gradient (PG) formula has been long known in the reinforcement learning (RL) community (Sutton et al., 2000), it has not been until trust region learning (Schulman et al., 2015a) 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 (Schulman et al., 2015a), PPO (Schulman al., 2017) and their extensions (Schulman al., 2015b; Hsu et al., 2020), became effective tools for solving challenging Al problems (Berner et al., 2019). 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 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) (Schulman et al., 2017). Furthermore, the trust- region interpretation of PPO has been formally rejected by recent studies both empirically (Engstrom al., 2020) and theoretically (Wang al., 2020); this revealed that the algorithm violates the trust-region constraints neither constraints the KL-divergence between two consecutive policies, nor does 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. (2022b) 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 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 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 connection between 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-agen agent reinforcement learning (MARL) it has only been exacerbated, Although the PG theorem has been successfully extended to the multi-agent PG (MAPG) version (Zhang al., 2018 8), it has only recently

---

Under review as a conference paper at ICLR 2023
been shown that the variance of MAPG estimators grows linearly with the number of agents (Kuba et al., 2021). Prior to this, however, a novel paradigm of centralised training for decentralised execution (CTDE) (Foerster et al., 2018; Lowe et al., 2017b) 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 algorithmss' implementations to the multi-agent setting. As a result, direct extensions of TRPO (Li & He, 2020) and PPO (de Witt et al., 2020a; Yu et al., 2021) 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 (Kuba et al., 2022a). Importantly, these methods can be proved to be suboptimal at convergence in the common setting of parameter sharing (Kuba et al., 2022a) which is considered as default by popular multi-agent algorithms (Yu et al., 2021) and popular multi-agent benchmarks such as SMAC (Samvelyan et al., 2019) due to the computational convenience it provides.
In this paper, we resolve these issues by proposing Heterrogeneous-AAent Mirror Learning (HAML)- 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 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-ar art (SOTA) MARL algorithms, HATRPO and HAPPO (Kuba et al., 2022a), 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. Furthermore, although HAML mainly a theoretical contribution, we can naturally demonstrate its usefulness by using it to derive two heterogeneous-agemt extensions of successful RL algorithms: HAA2C (for A2C (Mnih et al., 2016)) and HADDPG (for DDPG (Lillicrap et al., 2015)), whose strength are demonstrated on benchmarks of StarCraftII (SMAC) (de Witt et al., 2020a) and Multi-Agent MuJoCo (de Witt et al., 2020b) against strong basclines such as MADDPG (Lowe et al., 2017b) and MAA2C (Papoudakis et al., 2021).
2 PROBLEM FORMULATION
We formulate the cooperative MARL problem as cooperative Markov game (Littman, 1994) defined by tuple (N, S A, P,,, d). Here, .N' {1,...,,)) n is a of n agents, S is the state space, A= x A 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: S x A + IR is the joint reward function, P P:4 S x A x S + [0. the transition probability kernel. y E denotes the set of probability distributions over a set X) is the positive initial state distribution. In this work, we will also use the notation P(X) to denote the power set of set X. At time step &. E N, the agents are at state s, (which may not be fully observable); they take independent actions a/. Vi E N drawn from their policies n'' =fd (ss)) E P(A'), and equivalently, they take a joint action a (a)...., af") drawn from their joint policy (--(s)) = II (-'ss) E P(A). We write IIo A (x=EsT((>1ss) |Vs S, (+*ss) E }(A')] to denote the policy space of agent i, and II (II', ,I."".,11')) to denote the joint policy space. It is important note that when x' (lss) is Dirac delta ditribution, the policy is referred to as deterministic (Silver et al., 2014) and we write (s) to refer to its centre. Then, the environment emits the joint reward r(st, a.) and moves to the next state Se+11 ~ P(-|se, ax)= P(S). The initial state distribution d, the joint policy n, and the transition kernel P induce the (improper) marginal state distribution Pr (s) ع Ei 7 Pr((s = s|d, TT). The agents aim to maximise the expected joint return, defined as
[0, 1) is the discount factor, and
P(S) (where P(X)
((T) E R
Σ Srrr(st, at)
We adopt the most common solution concept for multi-agent problems which is that of Nash equilibria (Nash, 1951; Yang& & Wang. 2020). We say that joint policy TEE II is a NE if none of the agents can increase the joint return by unilaterally altering its policy. More formally, TEE is a NE if
Vi E N, Vn III, J(T',, mNa') S ((TNE).
2

---

Under review as a conference paper at ICLR 2023
To study the problem of finding NE, introduce the following notions. Let 81:m (di,..., (mm) S W be an ordered subset of agents. We write -m to refer to its complement, and and -i, respectively, when = 1. We define the multi-agent state-action value function
Qx (8, a 1:m
R 20
y (Se( ac) So 8, from
flom flom Ail:00 P.
When m = n (the joint action of all agents is considered), then iim E Sym(n), where Sym (n) denotes the of permutations of integers ,,..., n. known the symmetric group. In that case write Qu (8, a²==)) ) = Qn (8, a) which is known as the (joint) state-action value function. On the 0, i.e,, f1:m 0, the function takes the form V (s), known the state-value
other hand, when function. Consider two disjoint subsets of agents, f1:k and i1:m. Then, the multi-agent ad advantage function of fim with respect Ji:k is defined as
1 1imm (s, a 1ik
faom
Qu ( a a!im)) - Q (2.2""(,a"110 al
As it has been shown in Kuba et al. (2021), the multi-agent advantage function allows for additive decomposition of the joint advantge function by the means of the following lemma.
Lemma (Multi-Agent Advantage Decomposition). Let π be joint policy, and i1, arbitrary ordered subset of agents. Then. for any state s and joint action a gm
be an im ,.....,.m
Attmm (8, ( (1:m
A (3, ((2,""")-1,a'))
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.
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, not taken care of, may provably deteriorate 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: n' = n, VV, so that π = (f..... ......,)) π) (de Witt et al., 2020a; Yu et al., 2021). I). This approach enables a straightforward adoption of an RL algorithm 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., A' A4, Vi,j E N. Furthermore, policy sharing prevents agents from learning different skills. This scenario may be particularly dangerous in games with large number of agents, shown in Proposition 1, proved by Kuba et al. (2022a).
Proposition 1 (Trap of Homogeneity). Let's consider a fully-cooperativv game with an even nun- ber of agents n, one state, and the joint action space {0, 1)"", where the reward is given by r(0n/2 1n/2)= = r(1"/2,00' 0n/2) 1, and r") = 0 for all other joint actions. Let J be the optimal joint reward, and Jinm be the optimal joint reward under the shared policy constraint. Then
J
2n
A more ambitious approach to MARL is to allow for heterogeneity of policies among agents, i.e.. to let n' and n be different functions when i + j E 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 result of training, if that is indeed optimal. Nevertheless, training heterogeneous agents is highly non-tre trivial. Given a joint reward, an individual agent may not be able to distill its own contibution to it it-a problem known as credit assigument (Foerster al., 2018). Furthermore, even if an agent identifies its improvement direction, it may be conflicting with those of other agents, which then results in performance damage, exemplify in Proposition 2, proved in Appendix A.2.
3

---

Under review as a conference paper at ICLR 2023
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 given by r(0.0) = 0, r)) r(1,0) 2, and r r(1, 1) = -1 Suppose that (0) > 0.6 for i 1, Then, if agents i update their policies by
arg max E of twar Am a EN,
new
then the resulting policy will yield a lower return,
[(Taat)) > J[Wwew) min J(T).
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 SECOND LOOK AT SOTA MARL ALGORITTM
Multi-Agent Advantage Actor-Critic MAA2C (Papoudakis al., 2021) extends the A2C (Mnih et al., 2016) 6) algorithm to MARL by replacing the RI. optimisation (single-agent policy) objective with the MARL one (joint policy).
C MAAGC (TT) 2 E (s, a)].
which computes the gradient with respect to every agent i's policy parameters, and performs gradient-ascent update for each agent. This algorithm straightforward to implement and is capable of solving simple multi-agent problems (Papoudakis al., 2021). 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 suffer from large variance which grows linearly with the number of agents (Kuba et al., 2021), thus making the algorithm unstable. To assure greater stability, the following MARL extensions of stable RL approaches have been developed.
Multi-Agent Deep Deterministic Policy Gradient MADDPG (Lowe et al., 2017a) is MARL extension of the popular DDPG algorithm (Lillicrap et al., 2015). At every iteration, every agent i updates its deterministic policy by maximising the following objective
C. MADDRC A Bewsppa [Qina (s, (s)) = Be--Baa [Oima (s, pold (s))
(3)
where Bess state distribution that is not necessarily equivalent Pras 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- property granted by deterministic policies (Silver al., 2014), well low sample complexity due to learning from off- off-po data. Such a combination gives the algorithm a strong performance in continuous-action tasks (Lowe et al., 2017a; Kuba al., 2022a). However, this method's strengths also constitute its limitations-it is applicable to continuous problems only (discrete problems require categorical-disttibuuioo policies), and relies large memory capacity store the off- off-policy data.
Multi-Agent PPO MAPPO (Yu et al., 2021) is relatively straightforward extension of PPO (Schulman et al., 2017) to MARL. its default formulation, the agents employ the trick of policy shuring described in the previous subsection. As such, the policy is updated to maximise
<aal|s) (aia(aals)
aTaa (s)
aa)a Am
C MAPPO (IT) EE- Wo-
Σ min
Ama (s, a), clip(
(asa (aa))))))) 1 () Anaa
(4)
where the clip(., 1 + e) operator clips the input to 1 e/l + e if it 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 's performance on the StarCraftIl benchmark is remarkable, and it accomplished by using only on- polooiiy data. Nevertheless, the policy-sharing strategy limits the algorithm's applicability and leads to its suboptimality, as we discussed in Proposition 1. Trying to
4

---

Under review as a conference paper at ICLR 2023
avoid this issue, one can implement the algorithm without policy sharing, thus making the agents simply take simultancous PPO updates meanwhile employing 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 implementa- tion settings 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 be rigorously solved. With this motivation, in the next section, we develop theoretical framework for development of MARL algorithms with correctness guarantees.
HETEROGENEOUS -AGEGGGNNNONSSSSNNTTT MIRROR LEARNING
In this section, we introduce heterogeneeous-gger mirror learning (HAML) template that includes continuum of MARL algorithms which we prove to solve cooperative problems with correctness guarantees. HAML 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 N, heterogeneoou-agentt drift functional (HADF) Div of consists of map, which is defined as
D' III x II P(-i) x S
:P(A') RR,
such that for all arguments, under notation D ( s 7 p D (
1. Di (s T)m))
2 Di (T T)) (non-negativity).
2. Dr (+' klum) has all Gâteaux derivatives at A' T² (zero gradient).
and a probability distribution vi ns E EP(S) over states that can (but does not have to) depend on π and #4, and such that the drift D of a¹ from x² with respect to Them defined
D Di ( [/)m) & E
[D (4*1s 71mm) )}
continuous with respect π, fimm and ai. We say that the HADF is positive " (f*) -0 implies X' = ='',, and trivial " | for all π., 7 and #;,
Intuitively, the drift " (* is notion of distance between nO and # given that agents ji:m just updated to hh We highlight that, under this conditionality, the same update (from n' to #') can have different in a coordinated way. Before that, we introduce a notion that renders hard constraints, which may be part of algorithm design, an inherrent limitation.
will later enable HAML agents softly constraint their learning steps
Definition 2. Let E N. We say that, Ui XI + F(IT)) is a neighbourhood operator if'v'' E II', Ur (TT) contains closed ball, i.e., there exists state-wise monotonically non-decreasing metric X: II' II' + R such that Va E II' there exists 8 > such that X(**  < = म' E U (T').
Throughout this work, for every joint policy ग, we will associate it with its sampling distribution positive state distribution 8 E P(S) that is continuous in π (Kuba et al., 2022b). With these notions defined, we introduce the main definition of the paper.
Definition 3. Let E N. jl.m P(--), and Di. be a HADF of agent i. The heterogeneous--gent mirror operator (HAMO) integrates the advantage function as
(s)
[M(t) Dur zh (s) F. Pallom Wllm at aat AA (8, a 91mm a²)]
D' (**|s,, 1,, #(im). (x)
We note two important facts. First, when oz a Br, 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 #' = n², HAMO evaluates to zero. Therefore, as the HADF is non-negative, a policy a' 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 general framework for MARI. algorithm design.
5

---

Under review as a conference paper at ICLR 2023
4.2 THEORETICAL PROPERTIES OF HAML
It turns out that, under certain configuration, agents' local improvements result in the joint improve- ment of all agents, described by the lemma below.
Lemma 2 (HAMO Is All You Need). Let Told and Tnew be joint policies and let imm E Sym(n) be an agent permulation. Suppose that, for every state s S and every m ,,,,,,
[M (
Dimo fism- Ama)(s)
[M 1
Dim.n. fim-1 A
(5)
Then, Thew is jointly better than aatd so that for every state
Vinn (8) (s).
Subsequently, the monotonic improvement property of the joint return follows naturally,
[TTew = Essd V (s)] 2 Ia-d [+) = (TToi)
However, the conditions of the lemma require every agent to solve [S] instances of Inequality (5), which may be an intractable problem. We shall design single optimisation objective whose solution satisfies those inqqualities instead. Furthermore, to have practical application to large-scale problems, such an objective should be estimatable via sampling. To handle these challenges, introduce the following Algorithm Template 1 which generates a continuum of HAMI. algorithms.
Algorithm Template 1: Heterogeneeous-Agenn Mirror Learning
Initialise joint policy To = (T.....,. :;);:
for k = 0, 1,... do
Compute the advantage function Am, (s, a) for all state-Gjont)aattion pairs (s, a): Draw a permutaion im of agents at random Wfrom a positive distribution p E P(Sym(n)); for : do
[
fimm1 Ar (s)]; Dimir (44
Make an update T #++1
arg max Eldin (m)))) Bs
Output AA limit-point joint policy no0
Based on Lemma 2 and the fact that x' (TT),, N, IT', algorithm (weakly) improves the joint return at every iteration. In practical settings, such as deep MARL, the maximisation step of HAML method can be performed by few steps of gradient ascent on a sample average of HAMO (see Definition l). We also highlight that if the neighbourhood operators L/' can be chosen 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-netword policies, as 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- exed-point joint policies of this randomised procedure assure that none of the agents is incentivised to make an update, namely reaching NE. We provide the full list of the most fundamental HAML properties in Theorem which shows that any method derived from Algorithm Template solves the cooperative MARL problem.
know any HAML
Theorem (The Fundamental Theorem of Meteroggeneous-Agen Mirror Learning). Let, for every agent i AV, D'." be HADF, Ut be a neighbourhood operator, and let the sampling distributions 3n depend continuously on π. Let To E II, and the sequence of joint policies (Tx)
oo be obtained
by a HAML algorithm induced by D',,U' Vi E N, and 3q. Then, the joint policies induced by the algorithm enjoy the following list of properties
1. Attain the monotonic improvement property,
J(TT+1) 2 J(TT),
2. Their value functions converge to Nash value function NE
lim 10
V= NE

---

Under review as a conference paper at ICLR 2023
3. Their expected returns converge Nash returm.
lim J(TR)) = JNE
4. Their w- u-limit set consists of Nash equilibria.
See the proof in Appendix C. With the above theorem, we can conclude that HAML provides 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 sanity check for its practicality, show that two SOTA MARL methods HATRPO and HAPPO (Kuba et al., 2022a) 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 im (the permutation in. is drawn from the uniform distribution) updates its policy
maximise (in mmm)
E
A (s, a fiom ,,a'm))
subject (FL m/m) S 8.
This optimisation objective can be casted as a HAMO with the trivial HADF Din.k = 0, and the Kl--divergence neighbourhood operator
_ (+r = f
Esspp
im ( () (s*])) s {
The sampling distribution used in HATRPO is Bor Px. Lastly, the agents update their policies in random loop, the algorithm is an instance of HAML. Hence, it is monotonically improving and converges a Nash equilibrium set.
In HAPPO, the update rule of agent im is changes with respect to HATRPO as
min (r(#'m) A (s, a atmmm)) clip(r(#*"") f" ), + + Adam (s, (amm))
Somparg 11mm mere
where r(#t)
We show in Appendix that this optimisation objective is equivalent to (s)))
('(a'ss)
Ex--paas
E
[Air (s, a fi _aa1,aa"m sm)
1. 1 F1mm-1
CeLLU((((="m) clip(r(=""), 1 + c)] A (s, a ftom (aa==))))))))))))))
}}]}
The purple term is clearly non negative due to the presence of the ReLU funciton. Furthermore, for policies f sufficiently close to T'm the clip operator does not activate, thus rendering r(*i") unchanged. Therefore, the purple term is zero at and in region around 7 mhn which also implies that its Gâteaux derivatives are zero. Hence, it evaluates a HADF for agent iyy- thus making HAPPO valid HAML instance.
Finally, we would like to highlight that these results about HATRPO and HAPPO significantly strengthen the work originally by Kuba et al. (2022a) who only derived these learning protocols as approximations to theoretically sound algorithm (see Algorithm in Kuba et al. (2022a)), 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 heterogeneouu-ageen 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, well deliver more robust versions of multi-agent extensions of popular RL algorithms such as A2C and DDPG.
7

---

Under review as a conference paper at ICLR 2023
5m, ys_
24, vs, v5g842
Alarc4
Deward
Dewandd
Environment steps
Environment steps 8h R2
Environment steps 34
$452_v4_ 3662
Mac
Rewsrdd
Reewordd
Rewward
Environment steps
Environment steps
Environment steps
Figure 1: Comparison between HAA2C (yellow) vs MAA2C-S (blue) and MAA2C-NS (pink) SMAC.
HAA2C intends to optimise the policy for the joint advantage function at every iteration, and similar to A2C, does not impose any penalties constraints that procedure. This learning procedure is accomplished by, first, drawing a random permutation of agents ii:n, and then performing a few steps of gradient ascent the objective of
From (a 1m (S)TT" fm (a'm [s) Arm (s, a 4tom-1 a
B
Tnow
(6)
Fr:m (a 11:m-1 (s)Tall (atm|s)
π old
with respect to f parameters, for each agent im in the permutation, sequentially. In practice, we replace the multi-agent advantage A'm (s, a ft:m-1 ,a"' 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 aate-action value function off off-policy. As 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 im random permutation i1.. maximises
Ex-Apas Qui (s, f1om ((s). (s))
with respect to ,/' 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 opportunities for HAML algorithm design yet be discovered with more future work. Nevertheless, we begin this search from these two straightforward methods, and analyse their performance in the next section.
EXPERIMENTS AND RESULTS
In this section ()) 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 (Samvelyan et al., 2019) and Multi-Agent MuloCo (Peng et al., 2020), for discrete (only HAA2C) and continuous action settings, respectively.
We begin by demonstrating the performance of HAA2C. As a bascline, we use its "naive" predecessor, MAA2C, in both policy-sharing (MAA2C-S) and heterogeneous (MAA2C-NS) versions. Results on Figures & show that HAA2C generally achieves higher rewards SMAC than both versions of MAA2C, while maintaining lower variance. The performance gap increases in MAMuJoCo, where the
Our code is available at httptt:t///ggg httpg/gtthhhhoooo com/ httptth....oooaooooooaaateeeee/e http///mmmsswaaree////a.
8

---

Under review as a conference paper at ICLR 2023
HallChwetah-2x3
Ant--x4
Walker2d-233
300
25/3
Rewaard
300g
204
100
100
10
Environment staps
Erifronmmntt steps
Environment steps
HallChweefah-x22
Ant-4K2
Waker2d-3x2
MALt
Belwird
Environment steps
Environment steps
Environment steps
Figure Comparison between HAA2C (yellow) vs MAA2C-S (blue) and MAA2C-NS (pink) in MAMuJoCo.
Reacher-2xt
Hopper-3x1
Walker- 3x2
2000
2012
Environment stops
Environment steps
Environment
Ant-tx2
Swimmer-221
Humanoid-9(s
Rewwrrd
Reward
100
Environment stops
Environment steps
Environment steps
Figure 3: Comparison between HADDPG (yellow) and MADDPG (pink) in MAMuJoCo.
agents must learn diverse policies to master complex movements (Kuba et al., 2022a). Here, echoing Proposition I, the homogeneous MAA2C-S fails completely, and conventional, heterogeneous MAA2C-NS underperforms by 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 revelas that HADDPG achieves higher reward than MADDPG, while sometimes displaying significantly lower variance (e.g in Reacher-2x1 and Swimmer-2x1), Hence, conclude that HADDPG performs better.
6 CONCLUSION
In this paper, described and addressed the problem of lacking principled treatments for cooperative MARL tasks. Our main contribution is the development of heterogeneous-ageen mirror learning (HAML). 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 template for designing both principled and practical MARL algorithms hereafter.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Lawrence M Ausubel and Raymond J Deneckere. A generalized theorem of the maximum. Economic Theory, 3(1))99-101) 107, 1993.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw 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: 2019.
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.0953: 2020a.
Christian Schröder de Witt, Bei Peng, Pierre-Alexandrr Kamienny, Philip H. S. Torr, Wendelin Böhmer, and Shimon Whiteson. Deep multi -agett reinforcement learning for decentralized continuous cooperative control. CoRR, abs/2003.06709, 2020b. URL https: / /ataiaaxxooooo////a.ee.. org/ abs/2003. 06709.
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters deep policy gradients: case study on ppo and trpo. arXiv preprint 200i 2020.
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.
Chloe Ching Yun Hsu, Celestine Mendler-Dünner, and Moritz Hardt. Revisiting design choices in proximal policy optimization. arXiv preprint arXiv:2009.10897 2020.
Jakub Grudzien Kuba, Muning Wen, Linghui Meng. Haifeng Zhang, David Mguni, Jun Wang, Yaodong Yang, al. Settling the variance of multi-agent policy gradients. Advances in Neural Information Processing Systems, 34:13458-1344 13470, 2021.
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, 2022a.
Jakub Grudzien Kuba, Christian Schroeder de Witt, and Jakob Foerster. Mirror leamiigg A unifying framework of policy optimisation. ICML, 2022b.
Hepeng Li and Haibo He. arXiv:2010.07916. 2020.
Multi-agent trust region policy optimization. arXiv preprint
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 0tt:::15090097.7.. 2015.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperaaive-cooppttiieee environments. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pp. 6382-6393, 2017a.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compettive environments. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6382-6393, 2017b.
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, pp. 1928-1937. PMLR, 2016.
John Nash. Non-cooperative games. Annals of mathematics, pp. 286-295, 1951.
10

---

Under review as a conference paper at ICLR 2023
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms cooperative tasks. In Proceedings of the Neural Information Processing Systems Track Datasets and Benchmarks (NeurIPS), 2021. URL
http::/ http///axvvvvvv/. wwrgg / abs bobs// 2006 10000.07770 077869.
Bei Peng, Tabish Rashid, Christian A Schroeder de Witt, Pierre-Alexandre Kamienny, Philip HS Torr. Wendelin Böhmer, and Shimon Whiteson. Faemac: Factored multi-agent centralised policy gradients. arXiv e-prints, pp. arXiv-2003, 2020.
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.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015a.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint 1iXv::5506002335 2015b.
John Schulman, F. Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/1707.066. 06346, 2017.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, pp. 387-395, PMLR, 2014.
R. Sutton, Mcallester, Singh, and Y. Mansour, Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems 12, volume 12, pp. 1057-1063. MIT Press, 2000.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2018.
Yuhui Wang, Hao He, and Xiaoyang Tan. Truly proximal policy optimization. In Uncertainty in Artificial Intelligence, pp. 113-122. PMLR, 2020.
Jayy Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Dubureq, Minghao Zhang, Hang Su, and Jun Zhu. Tianshou: a highly modularized deep reinforcement learning library. arXiv preprint arXiv:2107.14177 14171, 2021.
Yaodong Yang and Jun Wang. An overview multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:201 1.00583, 2020.
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.0115.. 2021.
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, pp. 5872-5881. PMLR, 2018

---

Under review as a conference paper at ICLR 2023
A PROOFS OF PRELIMINARY RESULTS
A. PROOF OF LEMMA 1
Lemma 1 (Multi-Agent Advantage Decomposition). Let π be joint policy, and , im be an arbitrary ordered subset of agents. Then, for any state and joint action a im
A (8, a mmmm
Σ A (s,a"1101100
(I)
Proof. (We quote the proof from (Kuba et al., 2022a).) We start as expressing the multi-agent
advantage telescoping sum, and then rewrite it using the definition of multi-agent advantage,
mm (s, a from) = e (s, a aftim) (s)(s)
m
m
Σ
2 as, - (s, ( 11)- = Σ
A (s, aat--11,,,, ,at).
A.2 PROOF OF PROPOSITION 2
Proposition (Trap of Heterogeneity). Let's consider a fully-cooperative game with agents, one state, and the joint action space {0, 132, where the reward is given by r(0,0) = 0, rr0, r(1,0) 2, and r(1, =1 Suppose that T (a)(0) > 0.6 for 1,2. Then, if agents i update their policies by
max E, giwaria ewoedd (a EN,
New
then the resulting policy will yield a lower return,
J (TT > J (TToow min min J(T)..
As there is only one state, we can ignore the infinite horizon and the discount factor thus making the state-action value and the reward functions equivalent, Q = r.
Let us, for brevity, define n² = Tuu (0) > 0.6, for i 1, We have
J (TT.iaa) Pr(al a² (0, + (1 Pr(a' = a² a3) # (0.0))
0.6
0.6²) 0064.
The update rule stated in the proposition can be equivalently written as
T new = arg max E Biiwaii imnzn (Q (a", a a-)]
(8)
We have
E B (0 (0.=0))===(((0000 + - + x1r00))(01 2(1 ²)
and similarly
E Eg-tNem 12 (1, aaa) = -r + (11---))(1111 2T (1 T -T
Hence, if - > 0.6, then
B, fo [Q (1,a 3t
>>>1>>00 3 x 0.6 - 0.8 > 2xt B, iN [ a})
Therefore, for every i, the solution to Equation (8) is the greedy policy Tiem (1) = 1. Therefore,
J (Tnow) = Q(1, 1) = r(1, 1) = 1,
which finishes the proof.
12

---

Under review as a conference paper at ICLR 2023
B PROOF OF HAMO Is All You Need LEMMA
Lemma (HAMO Is All You Need). Let wold and Tnew be joint policies and let i1mm E Sym(n) be an agent permutation. Suppose that, for every state S and every m ,
[M (3
Am
A ( (s).
(5)
Dimm.
11:m
Dim Mare
Then, Tnew is jointly better than aI ald so that for every state 8,
V (s) 2 Viru(()) (8).
Am Ban (o)
fr (0)
Proof.
Let D mou (Tnow(s) 2 Em gives
Dim (Ir Tide
$1:m-1) new
Combining this with Lemma
E Ea-wae (Amou (0, (s, DD mau (Thew//))
fm
(8)
from aatm mation AArr (s, a fl:m aaa))
D
fm siad
(TT (s, Tnew
61:m-
Br (8)
m=1
by Inequality (5)
v sm
(8)
11mm
frim
[Arra (s, flom ammm
Wald Fo
Brae (s)
Dinn Wiad
(Tolld (s, nnew
f1:m-1)
m=1
Ean [Ara (s, a)] D mu (s).
The resulting inequality can be equivalently rewritten as
Ea-wae Q (s, a)] D mau (Tnew| (s) 2 Ea-wns mmai (s, a)] -Dmm (Tolals), Vs S. (9)
We use it to prove the claim follows,
V VaLw (s) = Ea-TTe Tine ( (s,a)]
En-TTe (Qmauee (s, a)] D mas (Tnew
+ D mia (Tnowls) + Barten 1Q ()) Qmn (s,
by Inequality (9)
Ea-mau [Q (s, a)] Dan (Troaals)
+ D mas (Teew(s) + Barwen 1 new (8, (s,
ViLu (s) + D mau (Trow) (s) + Earnun 1m (s, a) Qmaa (s, aJ]
ViLu (8) D mau (Trew (s)
E T s' [r(8, a) VV min (5') r(s, ~Vana (s)]
Vaau (s) + D man (Trowl (s) + 7 EarTye s' Vinn (s') V (s')]
2 Vinu (s) + 7 inf [V (s') ViLu (s))]
Hence V Tuuc (s) Vass (s) y inf ViTee (5') Vina (5))
Taking infimum over s and simplifying
(1 7) inf [Vine (s) VIrca (s) 2 0.
Therefore, inf, [Vr.n (s) ViLui [s)] 2 0, which proves the lemma.
13

---

Under review as a conference paper at ICLR 2023
C
PROOF OF THEOREM
Lemma 3. Suppose an agent im maximises the expected HAMO
Al New
arg max Bu
[M
D im Name
mim A A [s)
(10)
a tm EU (1)
Then, for every state s E S
M (mie
Amayl (8) 2 [M
(Tal) Amall (s).
D Fm
Dom.
Proof. We will prove this statement by contradiction. Suppose that there exists E S such that
M Tiee
Awael (su) < [M
(mar) Dim. mic
A (50).
(11)
Let us define the following policy mmm
Tuld (- fm [8), at 8 == 80
fm (. [s)
(m](s)=
Then (sm[s), at + 50
Note that f is (weakly) closer to Toll than new at so. and at the same distance at other states. Together with x nom E Umm (T ) this implies that tm E Umm (Tr Further,
[
Amall (s)) Barummae (M (m
Eg Bmad
A Ama (s)
Dimir man
Dim.r Taee
Br (8o)
([M
(m
Dimi" faum-r Amou] [ss) - (M
Amall (so)) > 0.
Dimil fism
The above contradicts nim. being the argmax of Inequality (11), as ffm is strictly better. The contradiciton finishes the proof.
Theorem (The Fundamental Theorem of Heterogeneous- Mirror Learning). Let, for every agent i N, Di." be HADF, Ut be neighbourhood operator, and let the sampling distributions 3n depend continuously on π. Let To E II, and the sequence of joint policies (#x))== be obtained by a HAML algorithm induced by Div algorithm enjoy the following list of properties
3/. ,u',, Vi N, and 8n. Then, the joint policies induced by the
1. Attain the monotonic improvement property,
J(TK+1) 2 J(TT))
2. Their value functions converge to a Nash value function VNE
lim
V VNEE
1-
3. Their expected returns converge Nash return.
lim J(TA) = NN
4. Their w-limit set consists of Nash equilibria.
Proof. Proof of Property 1.
It follows from combining Lemmas 2 & 3.
Proof of Properties 2, 4.
Step 1: convergence of the value function. By Lemma 2, have that Vx, (s) < V V (s), Ys S, and that the value function is (V,,, JaE converges. We denote its limit by V.
by Vmax- Hence, the sequence of value functions
Step 2: characterisation of limit points. As the joint policy space II is bounded, by Bolzano- Weierstrass theorem, we know that the sequence (TK))en has convergent subsequence. Therefore,
14

---

Under review as a conference paper at ICLR 2023
it has at least one limit point policy. Let क be such limit point. We introduce auxiliary notation: for a joint policy л and a permutation f1:m, let HU(TT, d1m)) be a joint policy obtained by a HAML update from π along the permutation 11m.
Claim: For any permutation 2imm E Sym(n).
म HU( 21:n).
(12)
=1mn) + क and (TEN be a subsequence converging to ग. Let us recall that the limit value function is unique and denoted as V. Writing x [-] for the expectation operator under the stochastic process (dim)eeN of update orders, for a state s S, we have
Proof of Claim. Let मे H
0 lim Eioo (I (s) VITE [s)]
1-300
every choice of permutation improves the value function
2 lim P(rf:n 21:0) [Vaa]V
VAL,, (s)]
= (1)))) lim (VHU(TT, ViTE, (o)]
7-000
By the continuity of the expected HAMO (following from the continuity of the value function (Kuba et al., 2022a, Appendix A), HADFs, neighbourhood operators, and the sampling distribution) obtain that the first component of + )1:a), which is 21 k; is continuous in gg, by Berge's Maximum Theorem (Ausubel & Deneckere, 1993). Applying this argument recursively for ø2, .2...... Zn. we have that HU( Zima) is continuous in TK.- Hence, as Tı, converges to म. its HU converges to the HU of म. which is म. Hence, we continue wiriting the above derivation as
= p(1mm) V+ (s) [s)] 2 0, by Lemma 2.
As arbitrary, the state-value function of न is the same that of == equation (Sutton& & Barto, 2018): Q(s, a) = r(s, a) -EV(ss). this also implies that their vtate- and advantage functions are the same: Q+ Q# and A* Aq. Let m be the smallest integer such that 4m * Tm This means that a fm achieves a greater expected HAMO than Tmm for which it is zero. Hence,
= V by the Bellman
Ennug [M A= (s)
Fm
(8)
= -n Eaalmwa 3im-1 atmm A (s, 21mm-1 aamm)))mm))))))mmm)mm)))))
R,
D 2em (# Pm n Fl:m
B (5)
Fm
-Eenpa Eggtim aertinng" ro flom amm rot [A (s, 21-m-1 a=*
R. mm
Dem ( |8, F1:m
Br (s)
and the expected value of the multi-agent advantage function is zero
# sm (8) am =f |s, Flim-)
}] S S.
(x(s)
This is contradiction, and the claim in Equation (12) proved, and the Step is finished.
Step 3: dropping the HADE. Consider an arbitrary limit point joint policy म. By Step 2, for any permutation 1imm considering the first component of the HU, and writing v² vd V
Eywan [[M A= A= (s)
max
(13)
x eUG (1(1)
(s) D4 (T (s)
Eswia Entiaat [An
max e' (r'1)
(x)
As the HADF is non-negative, and at q/ 7 its value and of its all Gâteaux derivatives are zero, follows by Step 3 of Theorem of (Kuba et al., 2022b) that for every 8 E S,
#1 (mm(s)
arg max Egi (Q# (s, a²)) (A(E)
15

---

Under review as a conference paper at ICLR 2023
Step 4: Nash equilibrium. We have proved that म satisfies
**(+ss)= = arg max Ex' (s, ((())))
arg max a a)],, vi N.seS.. (*))))))(AA)
Hence, by considering π - fixed, we see that n' satisfies the condition for the optimal policy (Sutton & Barto, 2018), and hence
arg max ,
n ")
x'EIT
Thus, म is Nash equilibrium. Lastly, this implies that the value function corresponds to a Nash value function VNE, the return corresponds to Nash return JNE
16

---

Under review as a conference paper at ICLR 2023
D CASTING HAPPO AS HAML
The maximisation objective of agent im in HAPPO is
min (r( A (s, (f, clip(((((() + A (s, af )}
Fixing and a f1mm-1, we can rewrite
Eg [A (s, a aft:mm-1 ammm )] EE tm mit (((7*m)AAAL) am (s, aa .ammm
min (((T"m) Aitm (s, a amimm- a²m clip(r(=("m) c) Alr.m (s, a am a atm ))}
By the multi-agent advantage decomposition.
frmm [ flom (s, fl amm.)
A 1.mm (s, a 11mm-1 1) +
+ Eg [4 (s, a 1imm-1 "0mmm,aa"))
Hence, the presence of the joint advantage of agents imm is equivalent to the multi-agent advantage of km given a am1m- that appears in HAMO. Hence, we only need to show that that the subtracted term is HADF. Firstly, change min into max with the identity min f(z) max(- f(x)).
E a'm wath ( A (s, a fi-m-1 aam)
- r( ) (s, a..a" 10 aa"m), -lipp(r( 1 + A (s, a ammm- atm)
+ max
which we then simplify
E n'm waa
max (0, [r((Tmm) - clip(((#*v)) + c)] A (s, (tima (a.m)) atmm))
E mom fm
ReLL (r(#*m)) clip(r(#'m) ), + e)] Abtmm m (s, al 1, aaam))
As discussed in the main body of the paper, this is an HADE.
17

---

Under review as a conference paper at ICLR 2023
E ALGORITHMS
Algorithm 2: HAA2C
Input: stepsize a, batch size B, number of: agents n, episodes K, steps per episode T,
mini-epochs e;
Initialize: the critic network: the policy networks: (0' JieN' replay buffer B;
for k= = 0, 1,... 1 do
Collect of trajectories by letting the agents act according their policies, af ~ xz. (:110)::
Push transitions {(o), aj, 1:41 E E, T into B;
Sample random minibatch of transitions from B;
Estimate the returns R and the advantage function, Á(s, a), using Vo and GAE; Draw a permutation of agents iim at random;
Set M (s, a) = A(s, a);
for agent im 11. in do
Set =i" (a' (o'm)) gm (a'm|o'm))
for mini-epoch- 1, ..... do
Compute agent im policy gradient
zim (4) (of")
g fm V Σ Mm (St, ao)
Jatm
arm (0 mo
Update agent im 's policy by
Im Oi argim.
w'm (a'm (o' Compute Min+1 (s, a)
Mmm (s. a) //unless m = m
Thth (atm lotm)
Update the critic by gradient descent on
# (Voss)) Ro))
Discard ø. Deploy 10'ee in exccution;
18

---

Under review as a conference paper at ICLR 2023
Algorithm 3: HADDPG
Input: stepsize a, Polyak coefficient т, batch size B, number of: agents ni, episodes K, steps per episode T, mini-epochs
Initialize: the critic networks: ó and ø' and policy networks: {0' HeN, replay buffer B, random
processes {X' Rev for exploration;
for k = 0, ..,, K 1 do
Collect set of transitions by letting the agents according to their deterministic policies with the exploratory noise
p (o') +
Push transitions {(oj, aj, of),, Vi E N,, E 7} into B;
Sample random minibatch of B transitions from B; Compute the critic targets
= 7 ac+1)
Update the critic by minimising the loss
= arg min & 1 E. (yr - (se,
Draw a permutation of agents i1: at random; for agent im ij...... in do Update agent im by solving
f TM arg max E. M bimm (o, (o:1--1) ), u (o ), a, amm4tin)
with mini-epochs of deterministic policy gradient ascent;
Update the target critic network smoothly
T + (1-7)d²
Discard Deploy her in execution;
19

---

Under review as a conference paper at ICLR 2023
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 card.
F.2 HYPERPARAMETERS
We implement the MAA2C and HAA2C based on HAPPO/HATRPO (Kuba et al., 2022a). We offer the hyperparameter use for SMAC in table and for Mujoco in table 2.
Table 1: Common hyperparameters used in the SMAC domain.
hyperparameters
value
hyperparameters
value Adam
hyperparameters
value
critic Ir
5e-4
optimizer
Backed-frames
gamma
0.99
optim eps
le
5
batch size
3200
gain
0.01
hidden layer
training threads
actor network
mlp
num mini-batch
rollout threads
hypernet embed
64
max grad norm
10
episode length 400
activation
ReLU
hidden layer dim
64
use huber loss
True
Table Common hyperparameters used for MAA2C-NS, MAA2C-S and HAA2C in the Multi-Agent MuloCo.
hyperparameters
value
hyperparameters
value
hyperparameters
value
critic Ir
le
optimizer
Adam
num mini-batch
1
gamma
0.99
optim eps
le
batch size
4000
gain
0.01
hidden layer
1
training threads
8
std y coef
0.5
actor network
mlp
rollout threads
4
std x coef activation
1
max grad norm
10
episode length
1000
ReLU
hidden layer dim
64
eval episode 32
In addition to those common hyperparameterrs, we the mini-epoch for HAA2C 5. For actor learning rate, we set it as 2e-4 for HalfCheetah and Ant while le-4 for Walker2d.
We implement the MADDPG and HADDPG based on the Tianshou framework (Weng et al., 2021). 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 Ir
3e 4
optimizer
Adam
replay buffer size
le6
critic
le - 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
664, 64]
episode length
1000
Table 4: Parameter n-step used for MADDPG/HADDPG in the Multi-Agent MuloCo
task
value
task
value
task
value
Reacher (2 x 1)
5
Hopper (3 1)
20
Walker (3 x 2)
Ant (4
20
Swimmer 1)
5
Humanoid (9]8)
20


Reviews:
[{"review_id": "v7Hoi-t0z6J", "reviewer": "Reviewer_iCs6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Recently Kuba et al. (2022a) introduced two cooperative MARL algorithms, HATRPO and HAPPO, which employed the idea of using a version of a multiagent advantage function which captures agents updating their portion of a policy sequentially rather than simultaneously and showed that it provides a monotone policy improvement guarantee.  Also recently, Kuba et al. (2022b) introduced Mirror learning as a way of understanding why algorithms like TRPO and PPO have a monotone improvement property.  This paper combines the two ideas showing that a richer class of algorithms which have both sequential advantage-based updates and use Mirror-learning style control of updates have the monotone improvement property.  This is empirically demonstrated by showing that instances of A2C and DDPG using the sequential advantage updates outperform traditional versions.", "summary_of_the_review": "Acceptable results, but presentation that is deficient in key ways.", "strength_and_weaknesses": "On the positive side, in combining these two ideas the paper provides additional insight into the (2022a) paper by both simplifying and generalizing the features needed and available (respectively) to guarantee policy improvement in cooperative MARL.  While this doesn’t require a lot of truly novel technical content, with the empirical demonstration of the benefits I think overall I would be happy to see these results in a good conference\n\nOn the negative side, the presentation is deficient in four respects.  First, the approach is presented as a monolithic whole, without identifying for readers some of the simplicity of the results.  In my view the whole inclusion of the drift functional / mirror learning is essentially a subsidiary result.  Theorem 1 holds even for the trivial drift functional, which means the key insight of the paper around the multi-agent advantage decomposition alone being sufficient is being buried under a lot of irrelevant technical detail.  Indeed, the HADF barely appears in the proof of Theorem 1 except as bookkeeping that could be replaced by 0.  In fact I think even greater generality is possible; the theorem requires a sequence of permutations over the agents while I believe it actually suffices that all agents be allowed to update an infinite number of times (although perhaps the permutation approach is more data efficient).  This detail is also irrelevant to the empirical results, which as the paper points out use neither HADFs nor neighborhood operators.  So while this material would be nice to include as an extension, it actually obscures and detracts from the main thrust of the paper.\n\nSecond, the paper presents as novel insights things which have long been known in the cs/econ literature on multiagent learning.  At least as far back as the 1996 Monderer and Shapley “Potential Games” paper, the convergence of dynamics where one agent at a time improves to Nash equilibrium in identical interest games has been well known.  Similarly, the problems of miscoordination when multiple agent update at the same time (which is explained in a needlessly complex way in Proposition 2) are well understood.  See, for example, Example 2 from “The Logit-Response Dynamics” by Alos-Ferrer and Netzer.  So while there is certainly some technical novelty in bringing these ideas to the richer cooperative MARL setting, the ideas themselves are not new.  Similarly, the limitations of homogeneous policies are well known.\n\nThird, this exemplifies a broader issue where the paper overstates its significance.  This happens at a low level with word choices which are excessive such as “fundamental theorem”, “endow MARL researchers”, and .  At a higher level, it is misleading to say in the introduction that CDTE methods lack “convergence results of any kind”.  COMA certainly comes with a convergence proof.  Kuba et al. 2022a are more careful, pointing out rather that COMA doesn’t provide any trust-region-style control of the step size and so is less stable.  But while this paper enables that, it doesn’t have any theory to establish how using it guarantees better stability.  So in that sense I don’t think the convergence theory in this paper is any stronger than in COMA.  While this sort of update does empirically seem to promote stability, as already mentioned the experiments in this paper don’t use it!  The paper also fails to give due credit to the two Kuba et al. 2022 papers.  The proof of Theorem 1 is straightforward and seems largely the same as the proof of the main result from the 2022a paper, but no technical credit is given to that paper for this.  The material in 4.1 is essentially a direct generalization of the material in the 2022b paper, and Lemma 2 is a direct generalization of their Lemma 3.3.  Yet that paper is mentioned only once in passing in that part.\n\nFourth, there are a number of small errors, unclear notation, and issues with definitions that should be corrected.  See details below.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "C02DIGgvQj", "reviewer": "Reviewer_T26V", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies MARL problems and proposes the Heterogeneous-Agent Mirror Learning (HAML) framework that enjoys monotonic improvement of the joint reward and convergence to NE. They show that HAML includes HATRPO and HAPPO as special instances. They provide HAML extensions of A2C and DDPG and show their effectiveness in experiments. ", "summary_of_the_review": "In summary, this paper is well-written and the topic is of great importance. The proposed framework is nicely motivated and enjoys a strong theoretical guarantee. The framework includes important SOTA algorithms as special instances. The extensions of the framework are achieving competitive performance in experiments. ", "strength_and_weaknesses": "## Strength\n- This paper is well-written and nicely organized. The proofs seem to be theoretically sound to me.\n- The topic of this paper, designing good MARL algorithms that enjoys proper convergence and reward improvement property, is the core of the relevant literature and is of great significance.  \n- The proposed framework is novel to me and is nicely motivated. The theoretical guarantee is strong.\n- The experiments are extensive and convincing.\n\n## Weaknesses\n- The maximization step of HAML seems to be the bottleneck of computational complexity. The authors remark that a few steps of gradient ascent are used in this process. The characterization of the number of steps needed is missing. It would be helpful if the authors could provide discussions on this part to complete the store of the framework.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BeDqlW_3lg", "reviewer": "Reviewer_iVJ4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a general template for MARL algorithmic designs. They 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. ", "summary_of_the_review": "This paper provides a general template for MARL algorithmic designs. They 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. Expanding the reason for limiting to Nash equilibrium and better comparisons would have been good. ", "strength_and_weaknesses": "+: The paper has nice result for the properties of a class of policies. \n\n-: The main issue is that achieving NE for cooperative games may not be the best strategy. We ideally want the cooperative equilibrium in a decentralized fashion. This aspect should be detailed better. \n\n-: The other issue is the comparisons. The entire area of CTDE is not considered for evaluations. See for instance the comparison strategies in recent NeurIPS paper: \"PAC: Assisted Value Factorisation with Counterfactual Predictions in Multi-Agent Reinforcement Learning\". Many of them are at https://github.com/hijkzzz/pymarl2 . ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3GqsNCyjqkM", "reviewer": "Reviewer_Axzm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors present a provably convergent MARL algorithmic template HAML, from which two existing MARL algorithms are derived as demonstration. In addition, further two MARL algorithms are cast as HAML instances to rid of their shortcoming defined as 'traps' in the paper. SMAC and MAMuJoCo evaluation shows better performance, or in cases of comparable reward levels, narrower confidence intervals.", "summary_of_the_review": "Authors make a clearly positioned contribution to explain policy gradient MARL algorithms in terms of their convergence properties and empirically show their findings. Minor points of revision include: delimitation with respect to value-based/communication-based MARL, more interpretive technicalities such as in Definition 3, and some comments on training time / computation.", "strength_and_weaknesses": "Paper's main strength lies in the provability of more stable convergence properties. Even though mirror learning concepts have been proposed in closely relevant previous works, extending those results to the multi-agent setting is far from trivial. Authors make a strong case for the correctness argument of HAMO and its monotonic improvement over the course of the training iterations.\n\nTracing the mirror learning idea back to the Kuba2022b paper does suggest that HAMO is meant to operate with policy gradient methods only, it would be nicer if a clear delimitation/disclaimer is made in the present paper. On a related note, some comments on representative value-based methods and/or communication-based MARL methods can help better position HAML and clarify which methods are/aren't HAMO's competitors.\n\nThe theorems and proofs support just exactly what is claimed earlier in the paper, but the current version reads a little like a dry array of correctly built up arguments. Insightful elaboration and a curated interpretation of what's between and beyond the equations would be an excellent addition. For example, at the bottom of page 5, what real-world implications do these two facts carry? Does HAMO collapse to a special case?\n\nAs is the case with provably convergent MARL algorithms, the training time/computation cost may have been the factor traded off for the convergence. Figures 1 to 3 are all plotted against environment steps, but one step of training a HAML instance would carry an expensive computation (Compute the advantage function A_\\pi_k in Algorithm Template 1). Please comment on the computation overhead.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject