Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning
Authors: Jakub Grudzien Kuba
Ruiqing Chen
Muning Wen
Ying Wen
Fanglei Sun
Jun Wang
Yaodong Yang
Venue: ICLR 2022 Poster (2022)
Keywords: Multi-Agent Reinforcement Learning
trust-region method
policy gradient method

Abstract: Trust region methods rigorously enabled reinforcement learning (RL) agents to learn monotonically improving policies, leading to superior performance on a variety of tasks. Unfortunately, when it comes to multi-agent reinforcement learning (MARL),  the property of monotonic improvement may not simply apply; this is because agents, even in cooperative games, could have conflicting directions of policy updates. As a result, achieving a guaranteed improvement on the joint policy where each agent acts individually remains an open challenge. In this paper, we extend the theory of trust region learning to MARL. Central to our findings are the multi-agent advantage decomposition lemma and the sequential policy update scheme. Based on these, we develop Heterogeneous-Agent Trust Region Policy Optimisation (HATPRO) and Heterogeneous-Agent Proximal Policy Optimisation (HAPPO) algorithms. Unlike many existing MARL algorithms, HATRPO/HAPPO do not need agents to share parameters, nor do they need any restrictive assumptions on decomposibility of the joint value function. Most importantly, we justify in theory the monotonic improvement property of HATRPO/HAPPO. We evaluate the proposed methods on a series of Multi-Agent MuJoCo and StarCraftII tasks. Results show that HATRPO and HAPPO significantly outperform strong baselines such as IPPO, MAPPO and MADDPG on all tested tasks, thereby establishing a new state of the art. 

Published as a conference paper at ICLR 2022
TRUST REGION POLICY OPTIMISATION IN MULTI-AGENT REINFORCEMENT LEARNING
Jakub Grudzien Kubal Ruiqing Chen Muning Wen", Ying Wen', Fanglei Sun', Jun Wang', Yaodong Yang
Uniiversity of Oxford, "Huawei R&D UK "ShanghaiTech University, *Shanghai Jiao Tong University University College London Institute for AI, Peking University & BIGAI
*Corresponding to: yaodong. srrrdonn.yang@@k.... wang@pku..du....
ABSTRACT
Trust region methods rigorously enabled reinforcement learning (RL) agents learn monotonically improving policies, leading to superior performance on a va- riety of tasks. Unfortunately, when it comes to multi-agent reinforcement learning (MARL), the property of monotonic improvement may not simply apply; this is because agents, even in cooperative games, could have conflicting directions of policy updates. As a result, achieving a guaranteed improvement on the joint policy where each agent acts individually remains an open challenge. In this pa- per, we extend the theory of trust region learning to cooperative MARL. Central our findings are the multi-agent advantage decomposition lemma and the se- quential policy update scheme. Based on these, we develop Heterogeneous-Agenn Trust Region Policy Optimisation (HATPRO) and feeterogeneous-Aeen Proxi- mal Policy Optimisation (HAPPO) algorithms. Unlike many existing MARL al- gorithms, HATRPO/AAPPO do not need agents to share parameters, nor do they need any restrictive assumptions Most importantly, we justify in theory the monotonic improvement property of HATRPO/HAPPO. We evaluate the proposed methods series of Multi-Agent MuJoCo and StarCraftII tasks. Results show that HATRPO and HAPPO signifi- cantly outperform strong baselines such as IPPO, MAPPO and MADDPG on all tested tasks, thereby establishing a new state of the art.
decomposibility of the joint value function.
INTRODUCTION
Policy gradient (PG) methods have played major role in recent developments of reinforcement learning (RL) algorithms (Silver et al., 2014; Schulman et al., 2015a; Haarnoja et al., 2018). Among the many PG variants, trust region learning (Kakade & Langford, 2002), with two typical embodi- ments of Trust Region Policy Optimisation (TRPO) (Schulman et al., 2015a) and Proximal Policy Optimisation (PPO) (Schulman et al., 2017) algorithms, offer supreme empirical performance in both discrete and continuous RL problems (Duan et al., 2016; Mahmood al., 2018). The ef- fectiveness of trust region methods largely stems from their theoretically-justfieed policy iteration procedure. By optimising the policy within trustable neighbourhood of the current policy, thus avoiding making aggressive updates towards risky directions, trust region learning enjoys the guar- antee of monotonic performance improvement at every iteration.
In multi-agent reinforcement learning (MARL) settings (Yang & Wang. 2020), naively applying policy gradient methods by considering other agents as a part of the environment can lose its ef- fectiveness. This intuitively clear: once a learning agent updates its policy, so do its opponents; this however changes the loss landscape of the learning agent, thus harming the improvement effect from the PG update. As a result, applying independent PG updates in MARL offers poor conver- gence property (Claus Boutilier, 1998). To address this, learning paradigm named centralised training with decentralised execution (CTDE) (Lowe et al., 2017b; Foerster et al., 2018; Zhou et al., 2021) was developed.
CTDE, each agent is equipped with a joint value function which, during
* First two authors contribute equally. Code is available at https: / / thub www.hc.cooo.a.am com/ PO/////U-MAAAA MARI./ PRPO-PPO-11 MARI.

---

Published as a conference paper at ICLR 2022
training. has access to the global state and opponents' actions. With the help of the centralised value function that accounts for the non non-stationarity caused by others, each agent adapts its policy param- eters accordingly. As such, the CTDE paradigm allows straightforward extension of single-agent PG theorems (Sutton et al., 2000; Silver et al., 2014) to multi-agent scenarios (Lowe et al., 201 7b; Kuba al., 2021; Mguni al., 2021). Consequently, fruitful multi-agent policy gradient algorithms have been developed (Foerster et al., 2018; Peng et al., 2017; Zhang et al., 2020; Wen et al., 2018; 2020; Yang et al., 2018).
Unfortunately, existing CTDE methods offer no solution of how to perform trust region learning in MARL. Lack of such an extension impedes agents from learning monotonically improving policies in a stable manner. Recent attempts such as IPPO (de Witt et al., 2020a) and MAPPO (Yu et al., 2021) have been proposed to fill such gap; however, these methods are designed for agents that are homogeneous (i.e., sharing the same action space and policy parameters), which largely limits their applicability and potentially harm the performance. As we show in Proposition later, parameter sharing could suffer from exponentially
suboptimal outcome. On the other hand, although IPPO/MPPO can be practically applied a non-parameter sharing way, it still lacks the essential theoretical property of trust region learning, which is the monotonic improvement guarantee.
In this paper, we propose the first theoretically justified trust region learning framework in MARL. The key to our findings are the aulti-agent advantage decomposition lemma and the sequential pol- icy update scheme. With the advantage decomposition lemma, we introduce a multi-agent policy iteration procedure that enjoys the monotonic improvement guarantee. To implement such proce- dure, we propose two practical algorithms: Heterogeneous--ggen Trust Region Policy Optimisation (HATRPO) and Heterogeneous-Agent Proximal Policy Optimisation (HAPPO). HATRPO/HAPPO adopts the sequential update scheme. which saves the cost of maintaining a centralised critic for each agent in CTDE. Importantly, HATRPO/HAPPO does not require homogeneity of agents, nor any other restrictive assumptions on the decomposibility of the joint Q-function (Rashid et al., 2018). We evaluate HATRPO and HAPPO on benchmarks of StarCraftIl and Multi- Agent MuloCo against strong baselines such as MADDPG (Lowe et al., 2017a), IPPO (de Witt et al., 2020b) and MAPPO (Yu et al., 2021); results clearly demonstrate its saate-of-the-aee performance across all tested tasks.
2
PRELIMINARIES
In this section, we first introduce problem formulation and notations for MARL, and then briefly review trust region learning in RL and discuss the difficulty of extending it to MARL. We end by surveying existing MARL work that relates to trust region methods and show their limitations.
2.1 COOPERATIVE MARL PROBLEM FORMULATION AND NOTATIONS
We consider a Markov game (Littman, 1994). which is defined by a tuple (W.S, U.S,A,,P. P,P,r 7). Here,
V = (1,...,7) ) denotes the set of agents, S is the finite state space, A = I - A is the product of finite action spaces of all agents, known as the joint action space, P S x A S + [0. 1] is the transition probability function, r: x A + IR is the reward function, and > 00, 1) is the discount factor. The agents interact with the environment according to the following protocol: at time step & E N. the agents are state Se E S; every agent takes an action aj E .A', drawn from its policy N (-(ss), which together with other agents' actions gives a joint action a, = (a)..... ........" a²) E A. drawn from the joint policy π (-1s.) = II==1 n (:)ss)):; the agents receive a joint reward r, = r(s,, a:) E R, and move to state 1 with probability |(e a.). The joint policy π, the transition probabililty function P. and the initial state distribution p", induce marginal state distribution at time i, denoted by /
The state value function and the state-action value function are defined: V (s) _ E S - so = s] and Qn,s,, a) A E Paaa ~- [h 7'Te| So 8, ao = a). The advantage function is written as As a) A Q= a) - (+). In this paper, we consider a fully-cooperative setting where all agents share the same reward function, aiming to maximise the expected total reward:
We define an (improper) marginal state distribution PT 2 EE P/
J(T) E Exp -0l
Throughout this paper, we pay close attention to the contribution to performance from different subsets of agents. Before proceeding to our methods, introduce following novel definitions.
2

---

Published as a conference paper at ICLR 2022
Let 11:m denote ordered subset fi1,...,;m) of N, and let -11:m refer to its com- plement. We write is when we refer to the hthh agent in the ordered subset. Correspondingly, the multi-agent dtat-acttin value function is defined
Definition 1.
Q* (s.a"'.) BB a from On (s.attm (a:m )}
and for disjoint sets ji:k and 11:m, the multi agent advantage function is
1 (s. aie a fiom))
Qhaaiiio (5, (s,a"1.
Qhi (s, artie
(I)
Hereafter, the joint policies π (T''...,,TT) T) and ग = ( (......, ......,)) R²) shall be thought of as the "current", and the "new" joint policy that agents update towards, respectively.
2.2 TRUST REGION ALGORITIMMS IN REINFORCEMENT LEARNING
Trust region methods such as TRPO (Schulman et al., 2015a) were proposed in single-agent RL with an aim of achieving monotonic improvement of (T) each iteration. Formally, it can be described by the following theorem.
Theorem 1. (Schulman et al., 2015a, Theorem 1) Let be the current policy and be the next candidate policy. We define (+) J(T) + Bupper [Ax a)], Dan. ( T) max, DRL. ((([s),=(({(s)) Then the inequality of
J(T) 2 (T) CD
max KL. (T,
()
4vy maxe, (s.a)) (1-3)2
holds, where C
The above theorem states that as the distance between the current policy æ and a candidate policy decreases, the surrogate [=x( which involves only the current policy's state distribution, becomes an increasingly accurate estimate of the actual performance metric J ( Based on this theorem, an
iterative trust region algorithm is derived; at iteration k + 1, the agent updates its policy by
Mc++1 = arg max (I= (Tr CTE, m))
Such update guarantees monotonic improvement of the policy, i.e., (TTx+1) (TT.. To im- plement this procedure in practical settings with parameterised policies Te. Schulman al. (2015a) approximated the KL-penalty with KL-constraint, which gave rise to the TRPO update of
0k+1 arg max Lmo, (Te), subject to Ey-pror [ TT)] S 6.
(3)
0
At each iteration A: + 1, TRPO constructs a KI.-ball (s(TT.) around the policy TØ and optimises To++1 BB(To,) to maximise I. (To). By Theorem 1, we know that the surrogate objective Lus, (He) is close to the true reward [(TT) within Bs ); therefore, TØ, leads to improvement. Furthermore, save the cost Eu-poe [DKI (No,; mo)] when computing Equation (3), Schulman et al. (2017) proposed an approximation solution to TRPO that uses only first order derivatives, known PPO. PPO optimises the policy parameter 0k+1 by maximising the PPO-clip objective of
To(s)))
To (als))
PPO L Lr (mO) Es-pagg Joree
min
To. (als) Aus, as. clip
(To (a]s)" t
Anay (s.a)
(4)
The clip operator replaces the ratio (ela)s)
ney (als) with + e, depending on whether or not the ratio
is beyond the threshold interval. This effectively enables PPO to control the size of policy updates.
2.3 LIMITATIONS OF EXISTING TRUST REGION METHODS MARL
Extending trust region methods MARL is highly non-trivial. One naive approach is to equip all agents with one shared set of parameters and use agents' aggregated trajectories to conduct policy optimisation every iteration. This approach was adopted by MAPPO (Yu al., 2021) in which the policy parameter is optimised by maximising the objective of
I MAPPO (TTO) B Baupro mmm Leg,
min Tooaa's Toe (a*ls)
Ama, (s. a), clip
Ta(aa)s) T6, (a'ls)
1 +ee Ano, (s, (s.
(5)
3

---

Published as a conference paper at ICLR 2022
Unfortunately, this simple approach has significant drawbacks. An obvious demerit is that parameter sharing requires that all agents have identical action spaces, i.e., A'' = 4',Vi.J E W, which limits the class of MARL problems to solve. Importantly, enforcing parameter sharing is equivalent to putting a constraint 6' = 05, J E N on the joint policy space. In principle, this can lead to a suboptimal solution. To elaborate, we demonstrate through an example in the following proposition.
Proposition 1. Let's consider a fully-cooperative game with an even number of agents n,, state, and the joint action space 10, where the reward given by r(00/2, 10/2) = =(11122 0n/2) 1, and r(a 0 for all other joint actions. Let J be the optimal joint reward, and Shhre be the optimal joint reward under the shared policy constraint. Then
J Jhha 2 J
2
For proof see Appendix B. In the above example, we show that parameter sharing can lead suboptimal outcome that is exponentially worse with the increasing number of agents. We also provide an empirical verification of this proposition in Appendix F.
Apart from parameter sharing, a more general approach to extend trust region methods in MARL is to endow all agents with their own parameters, and at each iteration + 1, agents construct trust regions of (Ba( HEN, and optimise their objectives {Lmo, (= 0F ke)..
Admittedly, this approach can still be supported by the current MAPPO implementation (Yu al., 2021) if one turns off pa- rameter sharing, thus distributing the summation in Equation (5) all agents. However, such an approach cannot offer rigorous guarantee of monotonic improvement during training. In fact, agents' local improvements performance can jointly lead to worse outcome. For example, in Figure 1, we design single-state differential game where two agents draw their ac- tions from Gaussian distributions with learnable means μ 1² and unit variance, and the reward function is r(a' .d) = a' a². The failure of MAPPO-style approach comes from the fact that, although the reward function increases in each of the agents' (one-dimensional) update directions, it decreases in the joint (two-dimensional) update direction.
3
14
Figure 1: Example of two- player differentiable game with r(a' .a²) = a' a'a? We initialise two Gaussian policies with 2² -0.25, n²² = 0.25. The purple intervals represent the KL-ball of 6 = 0.5. Individual trust region updates (red) decrease the joint re- turn, whereas our sequential up- date (blue) leads to improvement.
Having seen the limitations of existing trust region methods in MARL, in the following sections, we first introduce a multi- agent policy iteration procedure that enjoys theoretically- justified monotonic improvement guarantee. To implement this procedure, we propose HATRPO and HAPPO algorithms, which offer practical solutions to apply trust region learning in MARL without the necessity of as- suming homogeneous agents while still maintaining the monotonic improvement property.
3 MULTI-AGENT TRUST REGION LEARNING
The purpose of this section is to develop a theoretically-justifi trust region learning procedure in the context of multi-agent learning. In Subsection 3.1, we present the policy iteration procedure with monotonic improvement guarantee, and in Subsection 3.2, we analyse its properties during training and at convergence. Throughout the work, we make the following regularity assumptions.
Assumption 1. There exists E R, such that 0 < 1 << 1, and for every agent i E N, the policy space II' is so-ffft; that means that for every x² E IT', s E S, and a E A', we have T' (a(lsss) 2 n.
3.1 TRUST REGION LEARNING IN MARL WITH MONOTONIC IMPROVEMENT GUARANTEE
We start by introducing a pivotal lemma which shows that the joint advantage function can be de- composed into summation of each agent's local advantages. Importantly, this lemma offers critical intuition behind the scquential updicy-update scheme that our algorithms later apply.
Lemma 1 (Multi-Agent Advantage Decomposition). In any cooperative Markov gumes, given joint policy n. for any state 8, and any agent subsel i1sm, the below equations holds.
Yn
Alam (8, (8,a (1:m)
Σd Ale (s,, a.a .a²))
1=1
4

---

Published as a conference paper at ICLR 2022
For proof see Appendix C.2. Notably, Lemma holds in general for cooperative Markov games, with no need for any assumptions on the decomposibility of the joint value function such as those in VDN (Sunehag et al.. 2018), QMIX (Rashid al., 2018) or Q-DPP (Yang et al., 2020).
Lemma 1 indicates an effective approach to search for the direction of performance improvement (i.e., joint actions with positive advantage values) in multi-agent learning. Specifically, let agents take actions sequentially by following an arbitrary order iim assuming agent i takes an action a' such that (s, > O, and then, for the rest such that 4 (s, @m _m"" > O. For the induced joint action a, Lemma assures that Ane (s, @) positive, thus the performance is guaranteed to improve. To formally extend the above process into a policy iteration procedure with monotonic improvement guarantee, we need the following definitions.
....., n, the agent bm takes an action a'm
Definition 2. Let be joint policy, hhum-1 [[==1 who be some other joint policy of agents 11m-11 1, and Rúm be some other policy of agent im- Then
L Faom (mp Atm
B
Samp a 1o jam wit [Atm mm (s. mm (,
Note that, for any 7 7f1m-11 we have
L faim f1:m-1, m//)) E soup flom L fim atm nost tr [A (s, a atrmm- a²m) a
x
E Bewpp from 1imma Eggi mus (A (s. d2:m-1 amm }]] =0. (6)
Building on Lemma 1 and Definition 2, we can finally generalise Theorem 1 of TRPO MARL. Lemma 2. Let be joint policy. Then, for any joint policy π., have
J( 2 ((T) + Σ famm
[
f x(m) -CDRL
max " (atm,R/))
11=1
For proof see Appendix C.2. This lemma provides an idea about how a joint policy be improved. Namely, by Equation (6), we know that if any agents were to set the values of the above summands L ( -m CDDL (M # by sequentially updating their policies, each of them can always make its summand be zero by making no policy update (i.e., # π T'M) This implies that any positive update will lead to an increment summation. Moreover, as there are n agents making policy updates, the compound increment can be large, leading to substantial improvement. Lastly, note that this property holds with no requirement on the specific order by which agents make their updates; this allows for flexible scheduling on the update order at each iteration. To summarise, we propose the following Algorithm I. We want to highlight that the algorithm is
Algorithm Multi-Agent Policy Iteration with Monotonie Improvement Guarantee
1: Initialise the joint policy To = (T)..... m
2: for k 0, l. do
3: Compute the advantage function An, ss a) for all state-(joint)action pairs (s, a).
4: Compute = max,,a |m (s, a) and C 4re
(I-
5: Draw a permutaion ii:n of agents at random.
6: for m
do
Jmm 7: Make an update #k+1 arg maxxim
f1:m [T++1
CDDL Sen KL
8: end for
9:
end for
markedly different from naively applying the TRPO update, i.e., Equation (3), on the joint policy of all agents. Firstly, our Algorithm does not update the entire joint policy at once, but rather update each agent's individual policy sequentially. Secondly, during the sequential update, each agent has unique optimisation objective that takes into account all previous agents' updates, which is also the key for the monotonic improvement property hold.
3.2 THEORETICAL ANALYSIS
Now we justify by the following theorm that Algorithm enjoys monotonic improvement property.
5

---

Published as a conference paper at ICLR 2022
Theorem 2. A sequence (= of joint policies updated by Algorithm has the monotonic im- provement property, i.e, ((Tx+1) 2 (J(T)) for all E N.
For proof see Appendix C.2. With the above theorem, we finally claim successful introduction of trust region learning to MARL, as this generalises the monotonic improvement property of TRPO. Moreover, we take a step further to study the convergence property of Algorithm 1. Before stating the result, we introduce the following solution concept.
a Nash equilibrium Definition 3. In a fully-cooperative game, a joint policy πT ........ m (NE) for every i N, X' E II' implies (ITz) ()).
NE (Nash, 1951) is a well-established game-theoretic solution concept. Definition 3 characterises the equilibrium point at convergence for cooperative MARL tasks. Based on this, we have the following result that describes Algorithm I's asymptotic convergence behaviour towards NE.
Theorem 3. Supposing in Algorithm any permalation of agents has a fixed non-zero probability to begin the update, a sequence (T&))=) of joint policies generated by the algorithm, in cooperative Markov game, has a non-empty set of limit points, each of which a Nash equilibrium.
For proof see Appendix C.3. In deriving this result, the novel details introduced by Algorithm played an important role. The monotonic improvement property (Theorem 2), achieved through the multi-agent advantage and the sequential update scheme, provided us with guarantee on the con- vergence of the return. Furthermore, randomisation of the update order assured that, at convergence, none of the agents is incentified to make update. The proof is finalised by excluding possibility that the algorithm converges at non-equilibrium points.
4 PRACTICAL ALGORITHMS
When implementing Algorithm in practice, large state and action spaces could prevent agents from designating policies (-Is) for each state s separately. To handle this, we parameterise each agent's policy Ty.. by 0', which, together with other agents' policies, forms a joint policy The parametrised
by 0 = (0) "o'....,")) 0")) In this section, we develop two deep MARL algorithms to optimise the 0.
4.1 HATRPO
Computing DKL. (mopp Tgam in Algorithm 1 is challenging: it requires evaluating the KL- divergence for all states each iteration. Similar to TRPO, one can ease this maximal KL- (mr opm mpm by replacing it with the expected KL--divergence constraint
divergence penalty DRLK
EipPro DKI. ( (-1s), mT (+ss)) I 8 where is a threshold hyperparameter, and the expectation can be easily approximated by stochastic sampling. With the above amendment, we propose practi- cal HATRPO algorithm in which, every iteration & + 1, given permutation of agents i1.m agent me (1....n) sequentially optimises its policy parameter 0fm by maximising a constrained objective:
0/71 arg max B
[A (s, flmm 1,a )},
suppag Flom
flam
Fon dim
subject to Egpopea
[DxL (TT (m (-1s), m/m (-1s)) 6.
To compute the above equation, similar to TRPO, one can apply a linear approximation to the objective function and quadratic approximation to the KI constraint; the optimisation problem in Equation (7) can be solved by closed-form update rule as
28
0ym of + a'
gi. (H Am (H
g
(8)
DRI. (an.(T// (m (-Is), mpr. (-1s) Imm =omm is the Hessian of the expected KL- divergence, g is the gradient of the objective in Equation (7), or is a positive coefficient that found via backtracking line search, and the product of (H?") ".. can be efficiently computed with conjugate gradient algorithm.
where H!! V2 pl Ex-
AArr, as afm }}.
The last missing piece for HATRPO is to estimate E a11m 1ntree f1im1 aa nos give.
which poses challenges because each agent's objective has to take into account all previous

---

Published as a conference paper at ICLR 2022
agents' updates, and the size of input vaires. Fortunately, with the following proposition, we can efficiently estimate this objective by employing a joint advantage estimator.
Proposition Let [T x² be a joint policy, and An (s, a) be its joint advantage function.
Let 7'imm1 of agent 2m Then, for every state
- m- at be some other joint policy of agents i 1mm-1 and a m be some other policy
18 f1.m we
wellim 1im 11 aa witt [ (s, a11mm-1 1.---,,a" ,a'm))
Atm (a'm (s)
π fimm - (at1mm (ammmmm|ss)
1|s) π (atimm-) A (s. a)
Bant
(9)
Trim (atm (s)
For proof see Appendix D.1. One benefit of applying Equation (9) is that agents only need to main- tain a joint advantage estimator Ax (s, a) rather than one centralised critic for each individual agent (e.g., unlike CTDE methods such as MADDPG). Another practical benefit one can draw is that, given estimator A(s, a) of the advantage function Aro, (s, a), a), for example GAE (Schulman al.,
2015b), we can estimate "1'im- mist $1im-1 11
[Atro (s,aStmi1,a"")) with an estimator of
Kam (a (s) A
(a 1) 1)arrin arri as, where
M
(a")mm-1 (s..a).
(10)
1ime
(a
11s)
Notably, Equation (10) aligns nicely with the sequential update scheme in HATRPO. For agent ims since previous agents 1m have already made their updates, the compound policy ratio for M fi:m in Equation (10) is easy to compute. Given batch B of trajectories with length T, we can estimate the gradient with respect to policy parameters (derived Appendix D.2) as follows,
M Mi (Sz, as) V @rm log mom (al p (allss))ltm=af
B
TEB
1-0
The term -1 M M (s, a) of Equation (10) is not reflected in gk as it only introduces a constant with zero gradient. Along with the Hessian of the expected KL-divergence, i.e., H we can update 0 by following Equation (8). The detailed pseudocode of HATRPO is listed in Appendix D.3.
4.2 HАРPO
To further alleviate the computation burden from H HATRPO, one can follow the idea of PPO in Equation (4) by considering only using first order derivatives. This is achieved by making agent fm choose policy parameter 0.T which maximises the clipping objective of
im
(a'ls M as, clip (a*ls)
Son
(a'1s (s)
2 (s. } (11)
Ea-pyor a
min
gim
gim
(arls) 1 +
fm
The optimisation process can be performed by stochastic gradient methods such as Adam (Kingma & Ba, 2014). We refer to the above procedure as HAPPO and Appendix D.4 for its full pseudocode.
4.3 RELATED WORK
We are fully aware of previous attempts that tried to extend TRPO/PPO into MARL. Despite em- pirical successes, none of them managed to propose a theoretically-jjstfieed trust region protocol in multi-agent learning, or maintain the monotonic improvement property. Instead, they tend to impose certain assumptions to enable direct implementations of TRPO/PPO in MARL problems. For example, IPPO (de Witt et al., 2020a) assume homogeneity of action spaces for all agents and enforce parameter sharing. Yu al. (2021) proposed MAPPO which enhances IPPO by consider- ing joint critic function and finer implementation techniques for on-policy methods. Yet, it still suffers similar drawbacks of IPPO due to the lack of monotonic improvement guarantee especially when the parameter-sharing condition is switched off. Wen et al. (2021) adjusted PPO for MARL by considering a game-theorene theoretical approach at the meta-game level among agents. Unfortunately. can only deal with two-agent cases due to the intractability of Nash equilibrium. Recently, Li & He (2020) tried to implement TRPO for MARL through distributed consensus optimisation; however, they enforced the same ratio म (a*) ()) (aals) for all agents (see their Equation (7)), which, similar
7

---

Published as a conference paper at ICLR 2022
NATRPO
202
202
HAPPO
MAPPO
0.
4.5
2.2
0.5
20
(a) 20-Vs-64zg (hard)
(b) 3s52 (hard)
(c) corridor (super hard)
Figure 2: Performance comparisons between HATRPO/HAPPO and MAPPO on three SMAC tasks. Since all methods achieve 100% win rate, we believe SMAC is not sufficiently difficult to discrimi- nate the capabilities of these algorithms, especially when non-parameter sharing not required.
to parameter sharing, largely limits the policy space for optimisation. Moreover, their method comes with 5/n KL--contrraint threshold that fails to consider scenarios with large agent number.
One of the key ideas behind our HATRPO/HAPPO the sequential update scheme. A similar idea of multi-agent sequential update was also discussed in the context of dynamic programming (Bertsekas, 2019) where artificial "in-between" states have to be considered. On the contrary, our sequential update sceheme developed based on Lemma 1, which does not require any artificial as- sumptions and hold for any cooperative games. Furthermore, Bertsekas (2019) requires to maintain a fixed order of updates that is pre-defined for the task, whereas the order HATRPO/MAPPO can be randomised at each iteration, which also offers desirable convergence property, as stated in Propo- sition 3 and also verified through ablation studies in Appendix F. The idea of sequential update also appeared in principal component analysis; in EigenGame (Gemp et al., 2020) eigenvectors, repre- sented as players, maximise their own utility functions one-by-one. Although EigenGame provably solves the PCA problem, it is of little use in MARL, where single iteration of sequential updates insufficient to learn complex policies. Furthermore, its design and analysis rely on closed-fom matrix calculus, which has no extension to MARL.
Lastly, we would like to highlight the importance of the decomposition result in Lemma 1. This result could serve efforts have been made to decompose the joint Q-function into individual Q-functions when the joint Q-function are decomposable (Rashid et al., 2018). Lemma in contrast, is a general result that holds for any cooperative MARL problems regardless of decomposibility. As such, we think of it as an appealing contribution future developments on value-based MARL methods.
effective solution to value-hased methods in MARL where tremendous
5 EXPERIMENTS AND RESULTS
We consider two most common (Samvelyan et al., 2019) and Multi-Agent MuJoCo (de Witt et al., 2020b)-for evaluating MARL algorithms. All hyperparameter settings and implementations details can be found in Appendix E.
Multi-Agent Challenge (SMAC)
StarCraftII Multi- Challenge (SMAC). SMAC contains set of StarCraft maps in which a team of ally units aims to defeat the opponent team. IPPO (de Witt et al., 2020a) and MAPPO (Yu et al., 2021) are known achieve supreme results on this benchmark. By adopting parameter sharing, these methods achieve a winning rate of 100% on most maps, even including the maps that have heterogeneous agents. Therefore, we hypothesise that non-parameter sharing not necessarily required and the trick of sharing policies is sufficient to solve SMAC tasks. We test our methods on two hard maps and one super-hard; results on Figure confirm that SMAC is not sufficiently difficult to show off the capabilities of HATRPO/HAPPO when compared against existing methods.
Aulti-Agent MuJoCo. In comparison SMAC, we believe Mujoco enviormment provides more suitable testing case for our methods. MuJoCo tasks challenge a robot to learn an optimal way of motion; Multi-Agent MuloCo models each part of robot as an independent agent, for exam- ple, a leg for a spider or an arm for a swimmer. With the increasing variety of the body parts, modelling heterogeneous policies becomes necessary. Figure 3 demonstrate that, in all scenarios, HATRPO and HAPPO enjoy superior performance over those of parameter-sharing methods: IPPO and MAPPO, and also outperform non- parameter sharing MADDPG (Lowe et al., 2017b) both in terms of reward values and variance. It is also worth noting that the performance gap between HA- TRPO and its rivals enlarges with the increasing number of agents. Mcanwhile, we can observe that HATRPO outperforms HAPPO in almost all tasks; believe it is because the hard KI. constraint
8

---

Published as a conference paper at ICLR 2022
Ant 2x4
Ant 4x2
Ant 8x1
Average Eptroo Rewerd
UNTROD
IUPRO
96-90
Average Eptade
1A MA.004
FPC
2010
Avarage
Environment
Environment
Environment
(a) 2x4-Agent Ant
(h) 4x2-Agent Ant
(c) 1-Aent Ant
HalfChaetsh 2x3
HalfCheetah 3x2
HalfCheetah 6x1
fverage Epioode Reward
Average Epioade Reward
HATIPO
RAPPO
RAPP
IPFO
Average
Environment
Environment
Environment
(d) 2x3 2x3-Agent HalfCheetah
(c) 3x2 3x2-Agent HalfCheetah
6x1 6xl-Agent HalfCheetahh
Walker 2x3
Walker 3x2
Walker 6x1
Average Epicodi Roward
Epicade Reword
HAI PPD
IIAPPO
1000
Avrerage Episade
1000
Environment stops
Environment staps
Enviionment stops
(g) 2x3--Aeet Walker
(h) 3x2-Agent Walker
(i) 6x1-Agent Walker
Humannoid 17x1
HumanoidtStandup 17x1
MaryAgentSwinmerr 10x2
Ausrage Epicada Bowward
Average Epicade
Environment
Environment
Environment
(i) 17x1-Agent Humanoid
(k) 17x1-Agent HumanoidStanduu
10x2-Agent Swimmer
Figure 3: Performance comparison on multiple Multi-Agent MuJoCo tasks. HAPPO and HATRPO consistently outperform their rivals, thus establishing new state-of-the-art algorithm for MARL. The performance gap enlarges with increasing number of agents.
in HATRPO, compared to the clipping version in HAPPO, relates closely to Algorithm I that attains monotonic improvement guarantee.
CONCLUSION
In this paper, successfully apply trust region learning to multi-agent settings by proposing the first MARL algorithm that attains theoretically-jusee justified monotonical improvement property. The key to development is the multi-agent advantage decomposition lemma that holds in general with need for any assumptions on agents sharing parameters or the joint value function being decompos- practical deep MARL algorithms: HATRPO and HAPPO.
able. Based this, introduced Experimental results on both discrete and continuous control tasks (i.e., SMAC and Multi-Agent Mujoco) confirm their state-of-the ofeth--rtt performance. For future work, we will consider incorporating the safety constraint into HATRPO/HAPPO and propose rigorous safety-aware MARL solutions.

---

Published as a conference paper at ICLR 2022
REFERENCES
Dimitri Bertsekas. Multiagent rollout algorithms and reinforcement learning. arXiv preprint
arXiv:/910.00/20, 2019.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multia- gent systems. AAAI/IAAI, 1998(746-752)22, 1998.
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-Alexandre Kamienny, Philip H. S. Torr, Wendelin Böhmer, and Shimon Whiteson. Deep multi-agent reinforcement learning for decentralized con- tinuous cooperative control. CoRR, abs/2003.06709, 2020b.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pp. 1129-1121111 1338. PMLR, 2016.
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.
Ian Gemp, Brian McWilliams, Claire Vernade, and Thore Graepel. Eigengame: Pea as nash equilibrium. arXiv preprint arXiv:2010.00554. 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International Confer- ence on Machine Learning. pp. 1861-1870. PMLR, 2018.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference Machine Learning. Citeseer, 2002.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6690 2014.
Jakub Grudzien Kuba, Muning Wen, Yaodong Yang, Linghui Meng, Shangding Gu, Haifeng Zhang, David Henry Mguni, and Jun Wang. Settling the variance of multi-agent policy gradients. arXiv preprint arXiv:2 108.v:2108.0866 08611 2021.
Hepeng Li and Haibo He. Multi-agent trust region policy optimization. arXiv e-prints, pp. arXiv- 2010, 2020.
Michael L Littman. Markov games as 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- environments. In Proceedings of the 31st International
critic for mixed cooperative-competii Conference on Neural Information Processing Systems, pp.
2017a.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-competiive environments. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6382-6393, 2017b.
A Rupam Mahmood, Dmytro Korenkevych, Gautham Vasan, William Ma, and James Bergstra. Benchmarking reinforcement learning algorithms on real-world robots. Conference on robot learning, pp. 561-591. PMLR, 2018.
David H Mguni, Yutong Wu, Yali Du, Yaodong Yang, Ziyi Wang, Minne Li, Ying Wen, Joel Jen- nings, and Jun Wang. Learning in nonzero-sum stochastic games with potentials. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1688-7699 PMLR, 18- 24 Jul 2021.
10

---

Published as a conference paper at ICLR 2022
John Nash. Non-cooperative games. Annals of mathematics, pp. 286-2886999 296,299,1111 1951.
P Peng, Yuan, Y Wen, Y Yang, Z Tang, H Long, and J Wang. Multiagent bidirectionally- coordinated nets for learning to play starcraft combat games. arxiv 2017. arXiv preprint arXiv:1703.10062 2017.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforce- ment learning. In International Conference on Machine Learning, pp. 4295-4304. PMLR, 2018.
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. arXiv preprint arXiv: MXXi::992.004040 04043, 2019.
John Schulman, Sergey Levine, Picter 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 1eXiv:5006002430 2015b.
John Schulman, F. Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, hid//1777063477 2017.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministie policy gradient algorithms. In International conference on machine learning, pp. 387-395. PMLR, 2014.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning based team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2085 2085-2087, 2018.
R. S. Sutton, D. Mcallester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems 12, volume 12, pp. 1057-1063, MIT Press, 2000.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2018.
Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In International Conference Learning Representations, 2018.
Ying Wen, Yaodong Yang, and Jun Wang. Modelling bounded rationality in multi- agent interactions by generalized recursive reasoning. In Christian Bessiere (ed.), Proceedings of the Twenty-Ning International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 414- International Joint Conferences on Artificial Intelligence Organization, 7 2020. Main track.
Ying Wen, Hui Chen, Yaodong Yang, Zheng Tian, Minne Li, Xu Chen, and Jun Wang. A game- theoretic approach multi-agent trust region optimization. arXiv preprint 206.:2006.06828. 2021.
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.14171, 2021.
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theo- retical perspective. arXiv preprint 20Xiv:2011.0058: 2020.
Yaodong Yang, Rui Luo, Minne Li. Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. In International Conference on Machine Learning, pp. 5571-5580. PMLR, 2018
11

---

Published as a conference paper at ICLR 2022
Yaodong Yang, Ying Wen, Jun Wang. Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang. Multi-agent determinantal q-learning. In International Conference on Machine Learning. pp- 10757-10766. PMLR, 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.01955 2021.
Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7325-7332, 2020.
Ming Zhou, Ziyu Wan, Hanjing Wang, Muning Wen, Runzhe Wu, Ying Wen, Yaodong Yang, Weinan Zhang, and Jun Wang. Malib: parallel framework for population-based multi-agent reinforcement learning. arXiv preprint arXiv: 100.0000, 2021.
12

---

Published as a conference paper at ICLR 2022
Appendices
A Preliminaries
14
A.1 Definitions and Assumptions
14
A.2 Proofs of Preliminary Results
14
Proof of Proposition
16
C Derivation and Analysis of Algorithm
17
C.1 Recap of Existing Results
Resttt..........................
17
C.2 Analysis of Training of Algorithm
17
C,3 Analysis of Convergence of Algorithm
19
HATRPO and HAPPO
22
D.I Proof of Proposition 2
22
D.2 Derivation of the gradient estimator for HATRPO
................................
22
D.3 Pseudocode of HATRPO
23
D.4 Pseudocode of HАPPO
24
E Hlyper-parmeede Settings for Experiments
24
Ablation Experiments
26
G Ablation Study Non-Parameter Sharing MAPPO/IPP
26
Multi-Agent Particle Environment Experiments
27
13

---

Published as a conference paper at ICLR 2022
A PRELIMINARIES
A.I DEFINITIONS AND ASSUMPTIONS
Assumption 1. There exists lj E R, such that < 1 < 1, and for every agent N,, the policy space 11f is r--oft; that means that for every x² E 11', s S, and a' E A', we have T' r'(l's) Z T)-
m is a Nash equilibrium Definition 3. In fully-copperative game, joint policy n. (m......,,"" (NE) for every i E E, x² E II' implies (T.) 2 (T', )..)
Definition 4. Let X be finite set and p X + R, q X IR be two maps. Then, the notion of distance between p and that adopt is given by |p all maxxex (p(x) {(x))
A.2 PROOFS PRELIMINARY RESULTS
Lemma 3. Every agent i's policy space II' is convex and compact under the maximum norm.
Proof. We start from proving convexity od the policy space: we prove that, for any two policies
n², Ht E II', for every a E [0, 1], ax' + (1 - a) E II'. Clearly, for all s E and a' E A', we have
a) ((cl) 2 on
(1-
Also, for every state s,
Σ + (1- =
+ (1 -
=a+1-a= -o = [(
(a'las)
which establishes convexity.
For compactness, we first prove that II' is closed.
Let (= be convergent sequence of policies of agent Let n' be the limit. We will prove that n' is a policy. First, by Assumption 1, for any & E N, E S, and a² E A', we have or (a'ls) 2 n..
Hence,
n² (a'ls) = lim गे (a'1s) 2 lim 2
t+
A k +20
Furtheremore, for any and s, we have Eat कं (a'ls) = 1. Hence
Σ x (a Σ lim o' (a'1s) kooc
lim
(a'
lim 1=1.
k00
With these two conditions satisfied, n' is policy, which proves the closure.
Further, for all policies n², states and actions a, (a')s) < 1. This means that ||~|| max 1, which proves boundedness. Hence, IT is compact.
Lemma (Continuity of px). The improper state distribution ps continuous x.
Proof. First, us show that for any f. E N, the distribution pt is continous in æ. We will do by induction. This obviously holds when t 0, as p does not depend policy. Hence, we can assume that for some & N, the distribution o is continuous w. Let us now consider two policies and it. Let s' E S. We have
-
- (6) (4)) (4(4) Σ {(ala)P(6(1saa) E (t) Σ ((slss)
Σ Σ [pL(s) - ({())((ass) P(s'(s,a)
(P((s)((ala)) - (a(a))(a(s) p()
14

---

Published as a conference paper at ICLR 2022
( - + (+)(((())))) -
- ( P(s(ss,))
(pL(+) [m(a]s) - #(a|b)) + (p)(s) (+())
(+](() #|| +(als)lod - -
Σ (s) Σ || - #|| + Σ ll - -bill Σ #(a|s)
|A| || #ll + |S| |1 1
Hence, we obtain
1 || S |A| - || + |S|- -1 -
(12)
Using the base case, taking the limit as n, we get that the right-hand-side of Equation (12) converges to O, which proves that every 1²² is continuous in ग, and finishes the inductive step.
We can now prove that the total marginal state distribution Pr is continous in To do that, let's
log (0-1)
take an arbitrary e > 0, and a natural T such that T
Equivalently, we choose such
log
that
< S. Let and # be two policies. We have 1-7
px))) =
r' (p)(s) p4(s))
Σ (pi(s) ds))) +9¹ r
Σx- 1- (0t(s) - pt()
(o)(()) -16) +7 Σ
1 1-7
(Pa(s) pa)
(-)
(14( - A0) + Σ
27
T-T
2T
T-1 (s)(s)
(1)) 400
pt(s)l
1-7
1=0
7-1 Σ
1A
(s)(s) (s))
ll
p + 2
(13)
1=
Now, by continuity of each of pt_ for t 0, 1,.,.... T 1, we have that there exists 5 > such that
|| f|| < â implies l| p < 27. Taking such 8, by Equation (13), we get Ilpt Pal S which finishes the proof.
Lemma 5 (Continuity of Q+). Let x be policy. Then Q= a) is Lipschite-continuuss in π.
Proof. Let m and á be two policies. Then we have (s) (=(s,a)
a() + II ((116 (((s,)) + 3Σ P(s') P(61).))))H)))))00
Σ -
(I133).0) (s -
15

---

Published as a conference paper at ICLR 2022
- #(d])) (+
(Qx -n
P(s |s a)) ø|| 2max
(1b))ll)) Q+ll
Quax
|A| || #1| +11 - Q=1l
Hence, we get
11Q Q+1l S Qmax |Al || #l| + 7 711 Q+11:
which implies
1|Q+ Q+I1 S 7 Qmax ||A1 ||/T All
(14)
Equation (14) establishes Lipschitz-contimuity with a constant 7 Quis IA|
1-y
Corollary 1. From Lemma 5 we obtain that the following functions Lipschitzccmtiinuuss in m
the state value function Va = E. (xa,s)
the advantage function A, a) and the expected total reward J (TT Eu-pa [v).
- (s).
Lemma 6. Let and से be policies. The quantity a [A a)] is continuous in
Proof. We have
Ev-p arta (s, a)] =Σ pt (alaa))))))
Continuity follows from continuity of each (*) (Lemma 4) and (s,8 a) (Corollary 1).
Corollary (Continuity in MARL). All the results about continuity in ा extend to MARL. Policy π can be replaced with joint policy π.; is Lipschitz caachitt-contiuuusss in agent i's policy x¹, the above continuity results extend to conitmuity in x². Thus, we will quote them in our proofs for MARL.
B PROOF OF PROPOSITION 1
Let's consider a fully-cooperative game with an even number of agents n, one state, and the joint action space {0, 13", where the reward given by (000/2,1122) and r(al.>) 0 for all other joint actions. Let J" be the optimal joint reward, and J be the optimal joint reward under the shared policy constraint. Then
Proposition 1.
12/) = r(1"/2 0n/2) 1,
J J
J.
2
Proof. Clearly J = 1. An optimal joint policy in this case is, for example, the deterministic policy with joint action (0n/2,17 1m/2..
Now, the shared policy be (0, 1 1-0), where determines the probability that an agent takes action 0. Then, the expected reward is
((0) Pr (a 1 (02/2 123) 1 Pr (a (a!!m =010/2,00// - 2- 2- (
0ym/2.
16

---

Published as a conference paper at ICLR 2022
In order to maximise J(),, must maximise 8(1 8), or equivalently, v0 - 0). By the crithmetic-geometri means inequality, we have
v 0( - 0) 2
2"
where the equality holds if and only if = 1 0, that is 0
In such case have
2"
J Jhhee = J
2 = 2- 2 1/2
2222
a/2
2
which finishes the proof.
C DERIVATION AND ANALYSIS OF ALGORITHM 1
C.I RECAP OF EXISTING RESULTS
Lemma 7 (Performance Difference). Let i and n be two policies. Then, the following identity holds,
((T) J(r) = Eampa and (s)
Proof. See Kakade & Langford (2002) (Lemmaa 6.1) Schulman et al. (2015a) (Appendix A).
Theorem 1. (Schulman et al., 2015a, Theorem 1) Let be the current policy and be the next candidate policy. We define (+) J(T) + Eerp [Ax(s, a)], DKu (T, T)
max, DRL (((]ss,=(((ss)) Then the inequality of
( 2 (a( CD (T, R)
holds, where C
max,, (A((s.))
(1-?)²
Proof. See Schulman al. (2015a) (Appendix and Equation (9) of the paper).
C.2 ANALYSIS OF TRAINING OF ALGORITHM
Lemma 1 (Multi-Agent Advantage Decomposition). In any cooperative Markov games, given joint policy n, for any state and any agent subset 11:m, the below equations holds.
A (8, ammm)
A (s. ,,t)))
Proof. By the definition of advantage function,
A fiom A
(s, a (im) Q41m (s, (2im)) - VTT (s)
Quaa (s, a (uLit) b2:k Qu aa
A (s, a $1 (
which finishes the proof.
Note that similar finding has been shown in Kuba al. (2021).
Lemma 8. Let π = I # and मे = I #² be joint policies. Then
max (T,, π) <
mux (T² 7
17

---

Published as a conference paper at ICLR 2022
Proof. For any state have
DKL. (TT+)s), (-1s))
Bawr [log (Tals) log क (a|ss)
n
Ea
log
II
π xa(alss)
log II # (a'ls)
n
n
Egna
log xt' (a'1s)
log F (a'ls) Σ
==1
a
[log n" (a'ls) (s) log #'
( (a'ls)
Σ DxL (+1(),), #' (+(s))
Now, taking maximum over s on both sides yields
D max KL (TT, T)
S
Σ
D
Dun (T', .7))
==1
as required.
Lemma 2. Let π be a joint policy. Then, for any joint policy n, we have
J( 2 J(T)
+
Σ
L
11mm-- Ftm) - CD "
(m'm,, Rim)]]
m=
Proof. By Theorem
J(#) > L ( CDRL KL (TT, 7)
(TT)) + Es-ep. [Am a)]
CD man (T,, T)
which by Lemma equals
-(T) + Egvpp, a
Σ m=
A (s, a 1 a,
max CD
KL
(TT, π)
and by Lemma 8 this is at least
2 J(TT) + Exppp an
Aim (s, aftmm-1,a" a²m) Σ m=1
Σ
CDRL
max (Irim tptm))
n =(TT)
[A (s, a 2l:m a a ]]
Σ
CD CDmux (TT 55m)
Soupe: a 1mm 11mmm 1n willimm 1im-- wtm
KT.
-(T)) + Σ (L (fr xpt))
CD (,'", KL.
m=1
10 of joint policies updated by Algorithm has the monotonic im- provement property, i.e., ( J(TR)) for all k E N.
Theorem 2. sequence (TT)
Proof. Let Ty be any joint policy. For every 2 O, the joint policy π& is obtained from T by Algorithm update; for I,...,n,
arg max
Trem fimm-1
[T4l
max CD
KL. (m xrim))
7m
18

---

Published as a conference paper at ICLR 2022
By Theorem have
J(T++1) 2 L (T&+1) CD.t. which by Lemma is lower-bounded by
max (Tt, Tk+1),
2 Li (Tx+1))
CDRL (Trke) mk++1)
m=1
=J(TT) + Σ Tiita (TT
flom
CDRL fm KL lk"
(15)
6411
m=1
bm and as for every m, Th41 is the argmax, this is lower-bounded by
((TH) + Σ [ (T (T+1 ( CDRL
from-1
max ( xxx
m=1
which, as mentioned in Definition 2, equals
11
( + -0=J(Te))
where the last inequality follows from Equation (6). This proves that Algorithm achieves mono- tonic improvement.
C.3 ANALYSIS OF CONVERGENCE OF ALGORITHM
Theorem 3. Supposing in Algorithm any permutation of agents has a fixed non-zero probability begin the update, a sequence (T=))=) of joint policies generated by the algorithm, in cooperative Markov game, has a non-empty set of limit points, each of which a Nash equilibrium.
Proof. Step 1 (convergence). Firstly, it is clear that the sequence (J(T)))Emm converges by Theorem 2, it is non-decreasing and bounded above by Rus. T- Let denote the limit by J. For every k, we denote the tuple of agents, according whose order the agents perform the sequential updates, by if.... and we note that (it..) KEN is a random process. Furthermore, we know that the sequence of policies (π:) is bounded, so by Delzano-Weierstrass. Theorem, it has at least one convergent subsequence, Let से any limit point of the sequence (note that the set of limit points is a random be a subsequence converging to क (which is random subsequence as well). By continuity of J in π (Corollary 1), we have
set), and (TK;)) ) f=
J( = lim Tky 50000
= lim (TTK)) = 5
(16)
For now, we introduce an auxiliary definition.
Definition 5 (TR-Stationarity). A joint policy म is trust-regoon-stationnry (TR-stationary) if. for every agent i,
#² = arg max Emppy (s, - C# DR.. (f',*'),
where C+
47e [I-7]a, and max, Am
We will now establish the TR-stationarity of any limit point joint policy (which, as stated above, is random variable). Let B,g. [1] denote the expected value operator under the random process (1:00) Let also < = maxs,a |Am, (8, a)), and Ca (1-5)z
47ea We have
0 lim Eygos [T(Tk+1) ) J(Tx))]
lim E,0.s [Tr, (TK+1) Cg max (TT, T(+1)] by Theorem
+00
lim E,o,s
L (
max CaD
by Equation (15) and the fact that each of its summands is non-negative
19

---

Published as a conference paper at ICLR 2022
Now, consider arbitrary limit point ग from the (random) limit set, and a (random) subsequence (kyy j=o that converges to π. We get
lim 10000
E Bro
Lan,
(ky+1)
Ck2 DK..
As the expectation is taken of non-negative random variables, and for every i E N and k E N, with some positive probability ps, we have thz = i (because every permutation has non-zero probability), the above bounded from below by
(Lr,,, (T') - CR2 DKL (Thy.)
Pe lim max - which, as TRy converges to गミ, equals
pi max [T= (T²) C# (# m²]] 2 0, by Equation (6).
x¹
For convergence of L,, (T') we used Definition 2 combined with Lemma 6, for convergence of Ck₁ we used Corollary 1, and the convergence of DRL follows from continuity DRL. and max. This proves that, for any limit point म of the random process (TT) induced by Algorithm 1, max,: (T') C=DRL max (+) = O, which is equivalent with Definition 5.
Step 2 (dropping the penalty term). Now, we have to prove that TR-stationary points are NEs of cooperative Markov games. The main step is to prove the following statement: TR- TR-staaionary joint policy म, for every state 8 E S, satisfies
arg max Eginor [A (s. a²)]
(17)
x¹
We will use the technique of the proof by contradiction. Suppose that there is state so such that there exists policy #* with
Ex A (so, a')] > Eginet [A (80, a')].
(18)
Let us parametrise the policies n² according to the template
(-100) = (si.
where the values of n2J (j = ,,...,, d' 1) are such that (-(ss) is a valid probability distribution. Then we can rewrite our quantity of interest (the objective Equation (17) as
Eginar [A5(5 a¹)]
2 (s o²) +
Σ
2 A (so. d'y.)
d' Σ
2 (so. a²) 1 (S0, ) + A (so. a
which is an affine function of the policy parameterisation. It follows that its gradient (with respect to x²)) and directional derivatives are constant in the space of policies at state sg. The existance of policy (- for which Inequality (18) holds, implies that the directional derivative in the direction from **(- to (-1so) is strictly positive. We also have
0D (# (-180), x (-110)) 0x²
# =-(((0)) (+=ss - log & (-1s0))
dr
[
log
(omitting state so for brevity)
dx
d-11
de
0
Σ
# log oj.
t log
1
Σ
Or
Ozy
k=
k=
7/
1
d -
2
+
0,
when evaluated at / #²,
(19)
Td.
20

---

Published as a conference paper at ICLR 2022
which means that the KL-penalty has gradient (-(-su). Hence, when evaluated at (-(ss) (-((s)), the objective
(50 (st (s0 at)] C+ ( (-1s0), x (-|s0)
has strictly positive directional derivative in the direction of #' (:) [0))- Thus, there exists policy T' (-18)), sufficiently close to म² 7-(-(s)) on the path joining it with n (-180). for which
P= (80 E - [A (s0, a')] DRL (T 7' (-18o) 0.
Let कh be policy such that (-180) (-180)) and n. (-1s)) (-1s) for states * 80. As for these states we have
P# Es) (s, a')] = p7 (si (ss, = O, and D (+1s),,, 0. follows that
D (m²) C= max ( m²) p* (st) [4 (so: af)] - DNL (T म (+|su)
L (=') C+ C
mux (#', 7)),
which is contradiction with TR-stationarity of न. Hence, the claim of Equation (17) is proved. Step 3 (optimality). Now, for fixed joint policy म of other agents, #t satisfies
arg max Egine (s, a¹)] = arg max Eginar 12' (s, a¹)], Vs E,
which is the Bellman optimality equation (Sutton Barto, 2018). Hence, for a fixed joint policy # カーं the policy #' is optimal:
arg max "))
As agent was chosen arbitrarily, म is a Nash equilibrium.
21

---

Published as a conference paper at ICLR 2022
D HATRPO AND HАPPO
D.1 PROOF OF PROPOSITION 2
Proposition 2. Let I[;=1
R² be a joint policy, and An (s, a) be its joint advantage function.
Let H 1im-1 -[
m- A's be some other joint policy of agents 11mm11 and n be some other policy
of agent im Then, for every state
E a1im w #himm atms nitt (Air (s, a f1:m a
4tm (a'm (8)
π 41mm-1 (amm-(aattoi (atim-11
Bax
1x (8,
(9)
mrtm mm (s)
π 1mm-1 fm
[s)
Proof. We have
n mm (a 1im (s)
1im
(a fl 11:m-118
Eas
Am (s, a)
Ar (5,
t bl (a (8)
n $1:m
fl:m
7 fi:m
(a fa:m
(s)
Egliom wim -1 11mm
A (8, a
11:m
π fm aatii
$1
11m
Baitm- Moim-loorrhl fiom 1,, fiom -our fiom
Ar (8, 1m f2om-1)
1mm-1 (a (afim-1
(s)
Emi with from fmmm
[ (s, a from
E. Baaim-- ta 11 f1om- wet -orrrr--inn f1 [Arr (8, a atom-1 km-m-1)
Eg wite fimm
E -iim wet '1mm [Ar a fimm a --(mm)
E Iom ma 2im-1 [E 100a-mmmm 1ww (1m-1 11m-11 [Am (s, a1mm- f1mm1
=Bal of [A (s, a almmm) }]
- -Eaitm- - [A (8, a a /1:m-))]
which, by Lemma 1, equals
Battm f1
[A (s, afsm)) A (8, 21mmm1]
E Ba o f1:m
[A (s, a fi ,
D.2 DERIVATION OF THE GRADIENT ESTIMATOR FOR HATRPO
(a
(s)
Vi Eu-pnos TTe
gim
M (s,
Fm gim
(atm
[s)
(a
(s)
Vprm Esupro artto,
gim
M (s. a)
Dorm Esuproo arto,
M (s,
(a (s)
of
(atm (s)
Euuppn arttoy
gim
M ka (s,
xe tm
(atmm (s)
gii
Son T gim
(a (s)
E ar may
Verm log mmm. km
(s) (s,
n Aoa off
(atm (s)
Evaluated at Hm mlm the above expression equals
Es-pro amttos
M (s, a) V gr log Tm (a (a) =m
bm
which finishes the derivation.
22

---

end for Published as a conference paper at ICLR 2022
D.3 PSEUDOCODE HATRPO
Algorithm HATRPO
1: Input: Stepsize batch size B, number of: agents n, episodes K, steps per episode T, possible
steps in line search L, line search acceptance threshold K.
2: Initialize: Actor networks (%: Vi N,, Global V-value network {do). Replay buffer B
3: for k = 0. 1..... K do
4: Collect a of trajectories by running the joint policy Tea (T
m0g>
5: Push transitions {(o), at, 11 re), Vi E N 7} into B. Sample a random minibatch of B transitions from B.
6:
7:
Compute advantage function Á(s, a) based on global V-value network with GAE.
8:
Draw random permutation of agents 11m.
9:
Set M (s, a) = A(s, a).
10:
for agent fm 11 :1:-... in do Estimate the gradient of the agent's maximisation objective
11:
R
g = =
log T #
(at km of M (st, ar).
o6
Use the conjugate gradient algorithm to compute the update direction
where Him tm k
the Hessian the average KL-divergence
B
T Σ
(Tr/ (-loi") Thun (-10,-))
DKL
BT
6=
t=1
12:
Estimate the maximal step size allowing for meeting the KL-constraint
25
fmm
V
(of
km yT H im km
13: Update agent im 's policy by
on 0z + a 3m
where j {0, L,..,, b is the smallest such which improves the sample loss by least xad ft att" 9 found by the backtracking line search.
(a (o'"))
Compute M (s,
2
M (Se; at). //Unless m n.
Ame (arm (oim
15:
end for
16:
Update V-value network by following formula:
B
Φk+1 arg mins BT
Σ
Vo((t) R1.)
23

---

15: end for Published as a conference paper at ICLR 2022
D.4 PSEUDOCODE HАPPO
Algorithm 3 HAPPO
1: Input: Stepsize batch size B, number of: agents n, episodes K, steps per episode T.
2: Initialize: Actor networks {o) Vi E W. Global V-value network { Replay buffer B
3: for k == 0, 1,..... K do
4: Collect a set of trajectories by running the joint policy Te,
(TT 0
x 0
5: Push transitions {(o}, aj, 1. Vi t E Т} into B.
6: Sample random minibatch of B transitions from B.
7:
Compute advantage function Á(s. a) based on global V-value network with GAE. Draw a random permutation of agents i1m.
8:
9:
Set M (s, a) = A(ss
10:
for agent im 41 81:...; do
11:
Update actor 2 with f the argmax of the PPO-Clip objective
min
fon (otm 1o!m)
5 (se, ar); clip
fm
{atm 1o
+ e M (0))
(oi (0mm)
(4 10in0
oim
I'm (a (o'm)
12:
Compute M as)
2+1
Misi as, //nnless m 72
(atm joim)
end for
14:
Update V-value network by following formula:
B
Vo((s) Rd.)
Φk+1 arg mins BT
b=11=0
E HYPER-PARAMETER SETTINGS FOR EXPERIMENTS
hyperparameters
value
hyperparameters
value
hyperparameters
value
critic
5e-4
optimizer
Adam
stacked-frames
1
gamma
0.95
optim eps
le-5
batch size
3200
gain
0.01
hidden layer
training threads
32
actor network
mlp
num mini-batch
rollout threads
20
hypernet embed
64
max grad norm
10
episode length
160
activation
ReLU
hidden layer dim
64
use huber loss
True
Table 1: Common hyperparameters used in the SMAC domain.
Algorithms
MAPPO
HAPPO
HATRPO
actor Ir
5e-4
5e-4
ppo epoch kl-threshold
0.06
ppo-clip
0.2
0.2
/
accept ratio
0.5
Table 2: Different hyperparameters used for MAPPO, HAPPO and HATRPO in the SMAC
The implementation of MADDPG adopted from the Tianshou framework (Weng et al., 2021), all hyperparameters left unchanged the origin best-performing status.
24

---

Published as a conference paper at ICLR 2022
hyperparameters
value
hyperparameters
value
hyperparameters
value
critic
5e-3
optimizer
Adam
num mini-bated batch
40
gamma
0.99
optim eps
le-5
batch size
4000
gain
0.01
hidden layer
training threads
8
std y coef
0.5
actor network
mlp
rollout threads
4
std x coef
max grad norm
10
episode length
1000
activation
ReLU
hidden layer dim
64
eval episode 32
Table Common hyperparameters used for IPPO, MAPPO, HAPPO, HATRPO the Multi Multi-Agent
MuloCo domain
Algorithms
IPPO
MAPPO
НАРPО
HATRPO
actor Ir ppo epoch kl-threshold
5e-6
5e-6
5c-6
5
/
[lc-4.1.5c-477c441e11
ppo-clip
0.2
0.2
0.2
/
accept ratio
0.5
Table 4: Different hyperparameters used for IPPO, MAPPO, HAPPO and HATRPO in the Multi-
Agent MuJoCo domain.
hyperparameters
value
hyperparameters
value
hyperparameters
value
actor
1e-3
optimizer
Adam
buffer size
le6
critic Ir
le-3
exploration noise
0.1
batch size
200
gamma
0.99
step-per-epoch
50000
training num
16
tau
5e-2
step-per-collector
2000
test num
10
start-timesteps
25000
update-per-step
0.05
n-step
1
epoch
200
hidden-sizes
[256,256]
episode length
1000
Table 5: Hyper- used for MADDPG the Multi-Agent MuJoCo domain
task
value
task
value
task
value
Ant(2x4)
le-4
Ant(4x2)
le-4
Ant(8x1)
le-4
HalfCheetah(2x3)
le-4
HalfCheetahh3x2)
le-4
HalfCheetah(6x1)
le-4
Walker(2x3)
1e-3
Walker(3x2)
le-4
Walker(6x1)
le-4
H1manoid(17x1)
7e-4
(umaaooddSStanuu((11x))
le-4
Swimmer(10x2)
1.5e-4
Table 6: Parameter kl-threshold used for HATRPO the Multi-Agent MuloCo domain
hyperparameters
value
hyperparameters
value
hyperparameters
value
7c-4
optimizer
Adam
num mini-batch
gamma
0.99
optim eps
le-5
eval episode
32
gain
0.01
hidden layer
training threads
1
grad norm
10
actor network
rollout threads
128
hidden layer dim
64
activation
ReLU
episode length
25
Table 7: Common hyperparameters used for MAPPO, HAPPO in the Multi-Agent Particle Environ-
ment
25

---

Published as a conference paper at ICLR 2022
F ABLATION EXPERIMENTS
In this section, we conduct ablation study to investigate the importance of two key novelties that our HATRPO introduced; they are heterogeneity of agents' parameters and the randomisation of order of agents in the sequential update scheme. We compare the performance of original HATRPO with version that shares parameters, and with a version where the order in sequential update scheme is fixed throughout training. We run the experiments on two MAMuJoCo tasks (2-agent & 6-agent).
Walker 2x3
Walker 6x1
Average Episode Reward
H40120 (he unndemadded
3000
3303
2000
Average
2310
1000
10
Environment steps
Enviranment steps
(a) 2-Agent Walker
(b) 6-Agent Walker
Figure 4: Performance comparison between original HATRPO, and its modified versions: HATRPO with parameter sharing, and HATRPO without randomisation of the sequential update scheme.
The experiments reveal that, although the modified versions of HATRPO still outperform baselines (represented by MAPPO), their deviation from the theory harms performance. In particular, pa- rameter sharing introduces extra variance to training, harms the monotonic improvement property (Theorem 2 assumes heterogeneity), and causes HATRPO to converge to suboptimal policies. The suboptimality is more severe in the task with more agents, as suggested by Proposition 1. Similarly, fixed order the sequential update scheme negatively affected the performance at convergence (especially in the task with 6 agents), as suggested by Proposition 3. We conclude that the fine per- formance of HATRPO relies strongly on the close connection between theory an implementation. The connection becomes increasingly important with the growing number of agents.
G ABLATION STUDY ON NON-PARAMETER SHARING MAPPO/IPPO
We verify that heterogeneous-agent trust region algorithms (represented by HATRPO) achieve supe- rior performance to, originally homogeneous, IPPO/MAPPO algorithms with the parameter-sharee function switched off.
Halfcheetah 3x2
Walker 3x2
Average Episode Reward
4002
Reward
MAdino ric chams parai. ahare
400
2300
Average
1000
Environment steps
Environment steps
(a) 3-Agent HalfCheetah
(b) 3-Agent Walker
Figure 5: Performance comparison between HATRPO and МАPPО/IPPO without parameter shar-
ing. HATRPO significantly outperforms counterparts.
26

---

Published as a conference paper at ICLR 2022
H MULTI-AGENT PARTICLE ENVIRONMENT EXPERIMENTS
We verify that heterogeneous-agen trust region algorithms (represented here by HАPPO) quickly solve cooperative MPE tasks.
Spread
Average Episode Reward
Average Episode Reward
MATO HAPP
-103
-90
-120
-140
-160
200
-000
0.00
025
0.56
0.15
1.0
1.25
155
175
2.00
0.0
05
2.5
2.0
12
Environment steps
Enviranment steps
Simple Spread
(b) Simple Reference
Figure 6: Performance comparison between MAPPO and HAPPO MPE.
27


Reviews:
[{"review_id": "nB5552y8UP", "reviewer": "Reviewer_be2v", "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": "- Strengths:\n\t- The paper is well motivated and clearly written overall. \n\t- Compared to existing methods (e.g., IPPO and MAPPO), HATRPO/HAPPO can maintain the monotonic policy improvement guarantee of trust region learning in multi-agent reinforcement learning. This is a very nice theoretical property (I did not carefully check the proof though). The idea of updating each agent's policy sequentially while taking into account all previous updates is very interesting. \n\t- Experimental results on Multi-Agent MuJoCo look quite nice. \n- Weaknesses:\n\t- For the experiments, I think it's important to test IPPO and MAPPO without parameter sharing to better demonstrate the advantages of the proposed methods. Also, no state-of-the-art multi-agent value-based methods are compared against. \n\t- On SMAC, HATRPO/HAPPO does not perform significantly better than MAPPO overall. The authors argue that it is probably because non-parameter sharing is not required in this domain, it'd then be nice to verify this hypothesis by testing MAPPO/IPPO without parameter sharing. Also, I think the results would be more impressive if the advantages of HATRPO/HAPPO over IPPO and MAPPO can be shown in another domain other than Multi-Agent MuJoCo.\n- Main questions:\n\t- In proposition 1, why is the optimal joint reward $2^n$? Also, this means that the reward can grow without bound as the number of agents increases, what kind of (realistic) multi-agent tasks have this property? \n\t- The paper mentions that the proposed methods allow for flexible scheduling on the policy update order for agents at each iteration. How was this update order scheduled in the experiments?\n\t- On SMAC, why is IPPO and MADDPG not compared against (as in Multi-Agent MuJoCo)?\n\t- What is the level of partial observability (e.g., can agents see each other) in the Multi-Agent MuJoCo environments?\n\t- I found it a little bit surprising that HATRPO performs much better than HAPPO in most Multi-Agent MuJoCo tasks. The authors mention that it is because \"the hard KL constraint in HATRPO, compared to the clipping version in HAPPO, relates more closely to Algorithm 1 that attains monotonic improvement guarantee.\" I don't fully understand why this makes HATRPO perform better. Can the authors comment a bit more about this?\n\t- The authors argue that one key advantage of HATRPO/HAPPO is that they do not need \"any restrictive assumptions on decomposibility of the joint value function.\" I think the authors should make it clearer that this is just an advantage against most multi-agent value-based methods. I think QPLEX [1] does not place any restrictions on the decomposability of joint action-value function either. Furthermore, in a multi-agent actor-critic framework (say MAPPO), the joint value/action-value function can be decomposed in any manner too if you want to. \n\n**Post-rebuttal:**\n\nI would like to thank the authors for their rebuttal. It's nice to see that the authors provided some results on MAPPO/IPPO without parameter sharing. It seems that MAPPO without parameter sharing performs significantly better than MAPPO with parameter sharing. I suggest the authors to provide results on all tested Multi-Agent MuJoCo tasks, rather than on just 2 tasks in Appendix G. Overall, I think it's a good paper. I maintain my score. \n\n[1] QPLEX: Duplex Dueling Multi-Agent Q-Learning. Wang et al.  ICLR 2021.", "summary_of_the_paper": "This paper proposes two algorithms, HATRPO and HAPPO, which extend TRPO and PPO to cooperative multi-agent settings, respectively. Unlike existing MARL algorithms such as IPPO and MAPPO, HATRPO/HAPPO can guarantee monotonic policy improvements,  taking advantage of the proposed multi-agent advantage decomposition lemma and sequential policy update scheme. In addition, HATRPO/HAPPO can be applied to heterogeneous agents and does not require the joint value function being decomposable. Experimental results on Mulit-Agent MuJoCo demonstrate the competitive performance of the proposed methods. ", "summary_of_the_review": "I'm leaning towards accepting the paper as the proposed methods seem novel and have nice theoretical guarantee. But I'm not very confident as I believe that the paper would merit a stronger empirical section.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "e1cbXUNZq1", "reviewer": "Reviewer_ZAQm", "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": "The problem is well-formulated, but difficult to follow in some sections. Experiments are validating the claims authors made in the paper. I have the following concerns and questions regarding this paper. I can adjust my score accordingly after the authors reply to these questions:\n\n(1) I have a bit of difficulty understanding Lemma 2 intuitively. Is there any guarantee on the positive update to happen? What if $L_\\pi^{i_{1:m}}(.,.)-CD_{\\mathrm{KL}}^{{\\mathrm{max}}}(\\pi^{i_m}_k,\\pi^{i_m})$ is negative? In other words, is the  joint policy improvement guarantee based on a positivity assumption?\n\n(2) Algorithm 1, line 7, based on my understanding from Lemma 2, inside the argmax the compliment sign should be used as: $CD_{\\mathrm{KL}}^{\\mathrm{max}} (.,\\pi^{-i_m})$ \nnot\n $CD_{\\mathrm{KL}}^{{\\mathrm{max}}}(.,\\pi^{i_m})$. Could you correct me if I am wrong?\n\n(3) Some intuitions are required before/after Proposition 2 to let the reader know the outcome of this proposition. In fact, based on Appendix C.3, some more auxiliary definitions are required to prove the Nash equilibrium. Also I have some doubts regarding the one-shot Markov game definition, could you elaborate?\n\n(4) Doesn’t proposition 3 violate the assumption of HATPRO on “agents do not share parameters” and “there is no assumption on the  decomposability of the joint value function”?\n\n(5) There are many grammatical mistakes in this paper that require a thorough proofread. E.g. \nPermutaion, theorm, enviornment,...\n", "summary_of_the_paper": "This paper proposes Heterogeneous-Agent Trust Region Policy Optimisation (HATPRO), in which: (1) agents do not share parameters (2) there is no assumption on the  decomposability of the joint value function. Two adaptive algorithms are introduced to enable sequential updating that benefit from a monotonic improvement guarantee.", "summary_of_the_review": "The paper is strong in theoretical presentation and experiments are sufficient. However, the readability of the paper is an issue and requires some modifications. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "M5wwEaAIkam", "reviewer": "Reviewer_ubwY", "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": "Pro: \n- The paper clearly explains the related works and the improvement with respect to them. To me, the authors extend successfully a well-known state-of-the-art algorithm for single-agent RL problems in the multi-agent framework, providing potentially a new competitive algorithm also in this scenario. Claim supported by the results of the comparison with MADDPG, which is a state-of-the-art algorithm for the multi-agent problem.\n- I think that giving support for heterogeneous agents is a relevant problem in order to cover more realistic problems.\n- This paper provides a good number of experiments to support their claims, comparing their algorithms with the related works in many environments. Moreover, they provide the hyperparameters used in the experiments allowing results reproducibility.\n\nCons:\n- In my opinion, it is not clearly highlighted why it is important to guarantee that the policy improves monotonically.\n- The proposed algorithms work only for the cooperative setting, with a shared reward function, while MADDPG is working in both cooperative and competitive scenarios, and the letter is known to be a much harder problem. This could be potentially a weak point even if the developed algorithms show better performance in the evaluated experiments.\n- The fact that the proposed approach works in cooperative scenarios only is not immediately clear neither from the title nor from the abstract and introduction. Since this represents a significant assumption, it should be made clear as soon as possible.\n- The definition of Nash equilibrium for cooperative games seems quite unneeded. If all the agents share the same objective they aim at achieving the Pareto optimal solution and, given that they share the same reward, are never induced to unilaterally deviate from this solution. Can the authors explain why this definition is needed?\n- The phrase \"one-shot Markov game\" is employed in Proposition 2, but never defined. Can the authors clarify?\n\nMinor Issues:\n- Assumption 1: this assumption is prescribing that every action is played with non-zero probability. It seems to me that this prevents from converging to deterministic policies, which can be considered a limitation of the approach. Can the authors clarify?\n- Plots are not readable in grayscale, I suggest using different linestyles and/or markers\n- Ticks on the plot axis are too small", "summary_of_the_paper": "The goal of this work is to extend to the multi-agent framework the guarantee that the policy is improved monotonically after each update, as provided by TRPO for the single-agent case. The authors develop two practical algorithms where this guarantee is ensured. The algorithms are supported by a theoretical basis that explains the expansion in the multi-agent framework and relax the agents' homogeneity assumption present in the related works. An experimental evaluation showing the advantages of the proposed approach over state-of-the-art methods is provided.", "summary_of_the_review": "Overall, although the theoretical analysis adapts well-known tools from the safe-learning literature, I think that the proposed algorithms represent an advancement for the cooperative multi-agent setting and the experimental results are able to highlight the advantages of the proposed approach. \n", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JGoneDwtvxk", "reviewer": "Reviewer_WgFJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths: This paper tackles a very important problem in cooperative MARL and provides a simple, elegant solution. The paper is strong theoretically. Unfortunately, the SMAC experiments could not distinguish the approaches compared, but the MuJoCo experiments revealed strong performance from the proposed approach.\n\nWeaknesses:\n1) The abstract says \"even in cooperative games\", but it's not clear that this is the primary setting until later. Cooperative MARL is not as general as MARL, so I would advise clarifying this distinction earlier on. Similarly, Markov games typically model non-cooperative games as well, i.e., each agent has their own reward function $r_i$. It would help to make this distinction clear here too (at the start of section 2 rather than right above the definition of $J(\\pi)$). If \"Cooperative\" fits in the title, that would be great.\n2) Please show the steps for arriving at $\\hat{g}$ right before section 4.2. I was surprised to see the coefficient $\\frac{\\pi_{\\theta}}{\\pi_{\\theta_k}} - 1$ disappear. It's fine if this goes in the appendix, but it should be derived fully somewhere. Sorry if I missed it.\n3) In Figure 3, MADDPG appears to be starting to learn late in some of the experiments (e.g., d, e, f) to the point where it may surpass the performance of HATPRO which appears to asymptote. Can you include longer runs in the appendix?\n4) The approach of imposing a hierarchy on players was also proposed at last years ICLR in EigenGame which solves PCA as an n-player game. The hierarchy is drawn randomly at the beginning of the game and held fixed for all time whereas you draw a new one at every iteration. It was also critical there for (proving) and accelerating convergence to the equilibrium. Maybe this is a more general principle for n-player games that is worth discussing in your paper.\n5) I am also curious to see a discussion of the optimal hierarchy and what performance might be lost by randomly sample a hierarchy uniformly at every iteration.\n\nMinor:\n- Choice of \"sequential\": it was not clear to me initially that this referred to the update being sequential across the players. Maybe the word \"hierarchical\" or being more explicit about what is meant by sequential could help.\n- Definition 1: Should you add $m < n$?\n- I found it a bit confusing to use $L$ for something we want to maximize. Why not $f, g, U$?\n- Theorem 1: The expectation $\\mathbb{E}_{s \\sim \\rho_\\pi}$ is defined w.r.t. an improper distribution. Can you be more rigorous (proper) here?\n- Above definition 2: \"assuming agent $i_1$ takes an action $\\bar{a}^{i_m}$ such that $A^{i_m}(\\ldots) > 0$\". Can you comment on feasibility here? I expect it is always possible to find $A \\ge 0$. When only $A=0$ is available for all agents, then the agents have reached a local max. Otherwise, there is room for improvement. Can you add a discussion like that if that is correct?\n- Definition 2: You say let \"$\\bar{\\pi}^{i_{1:m-1}}$ be some other joint policy\". I guess the emphasis should be on \"other\" here. Can you not explicitly define $\\pi = \\prod_{n=1}^N \\pi^{i_n}$ and $\\bar{\\pi}^{i_{1:m-1}} = \\prod_{n=1}^{m-1} \\hat{\\pi}^{i_n}$? The details here are important and it was a bit hard to visually follow all the subscripts. Any help you can give the reader would be appreciated.\n- Given this is a cooperative MARL paper, I found the Nash result interesting, but unnecessary and possibly a distraction. I suggest it can be moved to the appendix if you need space.\n- Please define \"one-shot\" games. Are these not just multi-armed bandits? Looking at the appendix, under equation (17) on p. 20, it seems you should replace $s_t$ with $s$ or explicitly define a \"one-state\" game as $s_t = s \\forall t$.\n- typo \"vaires\" at the bottom of page 6", "summary_of_the_paper": "This paper introduces a trust region policy optimization method for cooperative multiagent reinforcement learning with a improvement guarantee. This is accomplished by imposing an arbitrary hierarchy on the players so that each player optimizes its policy w.r.t. the players who updated before it in the hierarchy. To my knowledge, this is the first extension of PPO and TRPO to the MARL setting with an improvement guarantee. Experiments demonstrate the efficacy of the approach.", "summary_of_the_review": "In my opinion, this is an important theoretical result for cooperative MARL with good empirical support from experiments.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes a new approach to deriving a policy gradient type algorithm for multi agent RL (MARL) where the agents are interested in a common objective but with potentially different action spaces. It extends the monotone improvement property for single agent trust-region based methods like TRPO to a multi agent update setting where the updates are performed in sequence by the agents, and uses this idea to derive new multi agent analogues of TRPO and PPO. These algorithms are shown to be competitive with existing strategies for MARL on a Starcraft environment, and superior in the case of common Mujuco benchmarks. 

All reviewers are unanimous in their appreciation for the paper's contributions. The initial concerns about clarity of the technical results, especially the improvement guarantee of the key lemma, that some reviewers had were addressed adequately by the author responses. Hence, I gladly recommend acceptance.
Decision: Accept (Poster)