TRUST REGION POLICY OPTIMISATION IN MULTI-AGENT REINFORCEMENT LEARNING
Year: 2022

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

heading: 1 INTRODUCTION
text: Policy gradient (PG) methods have played a 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 embodiments 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 et al., 2018). The effectiveness of trust region methods largely stems from their theoretically-justified policy iteration procedure. By optimising the policy within a trustable neighbourhood of the current policy, thus avoiding making aggressive updates towards risky directions, trust region learning enjoys the guarantee 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 effectiveness. This is 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 convergence property (Claus & Boutilier, 1998). To address this, a learning paradigm named centralised training with decentralised execution (CTDE) (Lowe et al., 2017b; Foerster et al., 2018; Zhou et al., 2021) was developed. In CTDE, each agent is equipped with a joint value function which, during ∗First two authors contribute equally. Code is available at https://github.com/cyanrain7/ Trust-Region-Policy-Optimisation-in-Multi-Agent-Reinforcement-Learning.
training, has access to the global state and opponents’ actions. With the help of the centralised value function that accounts for the non-stationarity caused by others, each agent adapts its policy parameters accordingly. As such, the CTDE paradigm allows a straightforward extension of single-agent PG theorems (Sutton et al., 2000; Silver et al., 2014) to multi-agent scenarios (Lowe et al., 2017b; Kuba et al., 2021; Mguni et 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 a 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 1 later, parameter sharing could suffer from an exponentially-worse suboptimal outcome. On the other hand, although IPPO/MAPPO can be practically applied in 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 multi-agent advantage decomposition lemma and the sequential policy update scheme. With the advantage decomposition lemma, we introduce a multi-agent policy iteration procedure that enjoys the monotonic improvement guarantee. To implement such a procedure, we propose two practical algorithms: Heterogeneous-Agent 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 StarCraftII and Multi-Agent MuJoCo 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 state-of-the-art performance across all tested tasks.

heading: 2 PRELIMINARIES
text: 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.

heading: 2.1 COOPERATIVE MARL PROBLEM FORMULATION AND NOTATIONS
text: We consider a Markov game (Littman, 1994), which is defined by a tuple 〈N ,S,A, P, r, γ〉. Here, N = {1, . . . , n} denotes the set of agents, S is the finite state space, A = ∏n i=1Ai is the product of finite action spaces of all agents, known as the joint action space, P : S ×A× S → [0, 1] is the transition probability function, r : S ×A→ R is the reward function, and γ ∈ [0, 1) is the discount factor. The agents interact with the environment according to the following protocol: at time step t ∈ N, the agents are at state st ∈ S; every agent i takes an action ait ∈ Ai, drawn from its policy πi(·|st), which together with other agents’ actions gives a joint action at = (a1t , . . . , a n t ) ∈ A, drawn from the
joint policy π(·|st) = ∏n i=1 π
i(·i|st); the agents receive a joint reward rt = r(st,at) ∈ R, and move to a state st+1 with probability P (st+1|st,at). The joint policy π, the transition probabililty function P , and the initial state distribution ρ0, induce a marginal state distribution at time t, denoted by ρtπ . We define an (improper) marginal state distribution ρπ , ∑∞ t=0 γ
tρtπ . The state value function and the state-action value function are defined: Vπ(s) , Ea0:∞∼π,s1:∞∼P [∑∞ t=0 γ trt ∣∣ s0 = s] and
Qπ(s,a) , Es1:∞∼P,a1:∞∼π [∑∞ t=0 γ trt ∣∣ s0 = s, a0 = a]. The advantage function is written as Aπ(s,a) , Qπ(s,a) − Vπ(s). In this paper, we consider a fully-cooperative setting where all agents share the same reward function, aiming to maximise the expected total reward:
J(π) , Es0:∞∼ρ0:∞π ,a0:∞∼π [ ∞∑ t=0 γtrt ] .
Throughout this paper, we pay close attention to the contribution to performance from different subsets of agents. Before proceeding to our methods, we introduce following novel definitions.
Definition 1. Let i1:m denote an ordered subset {i1, . . . , im} of N , and let −i1:m refer to its complement. We write ik when we refer to the kth agent in the ordered subset. Correspondingly, the multi-agent state-action value function is defined as
Qi1:mπ ( s,ai1:m ) , Ea−i1:m∼π−i1:m [ Qπ ( s,ai1:m ,a−i1:m )] ,
and for disjoint sets j1:k and i1:m, the multi-agent advantage function is
Ai1:mπ ( s,aj1:k ,ai1:m ) , Qj1:k,i1:mπ ( s,aj1:k ,ai1:m ) −Qj1:kπ ( s,aj1:k ) . (1)
Hereafter, the joint policies π = (π1, . . . , πn) and π̄ = (π̄1, . . . , π̄n) shall be thought of as the “current”, and the “new” joint policy that agents update towards, respectively.

heading: 2.2 TRUST REGION ALGORITHMS IN REINFORCEMENT LEARNING
text: Trust region methods such as TRPO (Schulman et al., 2015a) were proposed in single-agent RL with an aim of achieving a monotonic improvement of J(π) at 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 Lπ(π̄) = J(π) + Es∼ρπ,a∼π̄ [Aπ(s, a)] ,DmaxKL (π, π̄) = maxs DKL (π(·|s), π̄(·|s)) . Then the inequality of
J(π̄) ≥ Lπ(π̄)− CDmaxKL ( π, π̄ ) (2)
holds, where C = 4γmaxs,a |Aπ(s,a)|(1−γ)2 .
The above theorem states that as the distance between the current policy π and a candidate policy π̄ decreases, the surrogate Lπ(π̄), 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
πk+1 = arg max π
( Lπk(π)− CDmaxKL (πk, π) ) .
Such an update guarantees a monotonic improvement of the policy, i.e., J(πk+1) ≥ J(πk). To implement this procedure in practical settings with parameterised policies πθ, Schulman et al. (2015a) approximated the KL-penalty with a KL-constraint, which gave rise to the TRPO update of
θk+1 = arg max θ Lπθk (πθ), subject to Es∼ρπθk [DKL(πθk , πθ)] ≤ δ. (3)
At each iteration k + 1, TRPO constructs a KL-ball Bδ(πθk) around the policy πθk , and optimises πθk+1 ∈ Bδ(πθk) to maximise Lπθk (πθ). By Theorem 1, we know that the surrogate objective Lπθk (πθ) is close to the true reward J(πθ) within Bδ(πθk); therefore, πθk leads to improvement. Furthermore, to save the cost on Es∼ρπθk [DKL(πθk , πθ)] when computing Equation (3), Schulman et al. (2017) proposed an approximation solution to TRPO that uses only first order derivatives, known as PPO. PPO optimises the policy parameter θk+1 by maximising the PPO-clip objective of
LPPOπθk (πθ) = Es∼ρπθk ,a∼πθk
[ min ( πθ(a|s) πθk (a|s) Aπθk (s, a), clip ( πθ(a|s) πθk (a|s) , 1± ) Aπθk (s, a) )] . (4)
The clip operator replaces the ratio πθ(a|s) πθk (a|s) with 1+ or 1− , depending on whether or not the ratio is beyond the threshold interval. This effectively enables PPO to control the size of policy updates.

heading: 2.3 LIMITATIONS OF EXISTING TRUST REGION METHODS IN MARL
text: Extending trust region methods to 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 at every iteration. This approach was adopted by MAPPO (Yu et al., 2021) in which the policy parameter θ is optimised by maximising the objective of
LMAPPOπθk (πθ) = n∑ i=1 Es∼ρπθk ,a∼πθk [ min ( πθ(ai|s) πθk (ai|s) Aπθk (s,a), clip ( πθ(ai|s) πθk (ai|s) , 1± ) Aπθk (s,a) )] .
(5)
Unfortunately, this simple approach has significant drawbacks. An obvious demerit is that parameter sharing requires that all agents have identical action spaces, i.e., Ai = Aj ,∀i, j ∈ N , which limits the class of MARL problems to solve. Importantly, enforcing parameter sharing is equivalent to putting a constraint θi = θj ,∀i, j ∈ 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, one state, and the joint action space {0, 1}n, where the reward is given by r(0n/2,1n/2) = r(1n/2,0n/2) = 1, and r(a1:n) = 0 for all other joint actions. Let J∗ be the optimal joint reward, and J∗share be the optimal joint reward under the shared policy constraint. Then
J∗share J∗ = 2 2n .
For proof see Appendix B. In the above example, we show that parameter sharing can lead to a 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 k + 1, agents construct trust regions of {Bδ(πiθi
k )}i∈N , and optimise their objectives {Lπθk (π i θiπ −i θ−i k )}i∈N .
2.0 1.5 1.0 0.5 1.0 1.5 2.00.5 0.0
Agent 2
0.5
1.0
1.5
2.0
0.0
2.0
1.5
1.0
0.5
A g e n t 1
0.000 0.000
MAPPO
HATRPO & HAPPO
Figure 1: Example of differentiable game with r(a1, a2) = a1a2. We initialise agents’ 1- D Gaussian policies with µ1 = −0.25, µ2 = 0.25. Orange intervals represent the KL-ball of δ = 0.5. Individual trust region update (red) jointly decreases the performance, whereas our sequential updates (blue) lead to improvement.
Admittedly, this approach can still be supported by the current MAPPO implementation (Yu et al., 2021) if one turns off parameter sharing, thus distributing the summation in Equation (5) to all agents. However, such an approach cannot offer a rigorous guarantee of monotonic improvement during training. In fact, agents’ local improvements in performance can jointly lead to a worse outcome. For example, in Figure 1, we design a single-state differential game where two agents draw their actions from Gaussian distributions with learnable means µ1, µ2 and unit variance, and the reward function is r(a1, a2) = a1a2. 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.
Having seen the limitations of existing trust region methods in MARL, in the following sections, we first introduce a multiagent policy iteration procedure that enjoys theoreticallyjustified 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 assuming homogeneous agents while still maintaining the monotonic improvement property.

heading: 3 MULTI-AGENT TRUST REGION LEARNING
text: The purpose of this section is to develop a theoretically-justified 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 η ∈ R, such that 0 < η 1, and for every agent i ∈ N , the policy space Πi is η-soft; that means that for every πi ∈ Πi, s ∈ S, and ai ∈ Ai, we have πi(ai|s) ≥ η.

heading: 3.1 TRUST REGION LEARNING IN MARL WITH MONOTONIC IMPROVEMENT GUARANTEE
text: We start by introducing a pivotal lemma which shows that the joint advantage function can be decomposed into a summation of each agent’s local advantages. Importantly, this lemma offers a critical intuition behind the sequential policy-update scheme that our algorithms later apply. Lemma 1 (Multi-Agent Advantage Decomposition). In any cooperative Markov games, given a joint policy π, for any state s, and any agent subset i1:m, the below equations holds.
Ai1:mπ ( s,ai1:m ) = m∑ j=1 A ij π ( s,ai1:j−1 , aij ) .
For proof see Appendix C.2. Notably, Lemma 1 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 et 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 i1:n, assuming agent i1 takes an action āi1 such that Ai1(s, āi1) > 0, and then, for the rest m = 2, . . . , n, the agent im takes an action āim such that Aim(s, āi1:m−1 , āim) > 0. For the induced joint action ā, Lemma 1 assures that Aπθ (s, ā) is 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. Definition 2. Let π be a joint policy, π̄i1:m−1 = ∏m−1 j=1 π̄
ij be some other joint policy of agents i1:m−1, and π̂im be some other policy of agent im. Then
Li1:mπ ( π̄i1:m−1 , π̂im ) , Es∼ρπ,ai1:m−1∼π̄i1:m−1 ,aim∼π̂im [ Aimπ ( s,ai1:m−1 , aim )] .
Note that, for any π̄i1:m−1 , we have Li1:mπ ( π̄i1:m−1 , πim ) = Es∼ρπ,ai1:m−1∼π̄i1:m−1 ,aim∼πim [ Aimπ ( s,ai1:m−1 , aim )] = Es∼ρπ,ai1:m−1∼π̄i1:m−1 [ Eaim∼πim [ Aimπ ( s,ai1:m−1 , aim )]] = 0. (6)
Building on Lemma 1 and Definition 2, we can finally generalise Theorem 1 of TRPO to MARL. Lemma 2. Let π be a joint policy. Then, for any joint policy π̄, we have
J(π̄) ≥ J(π) + n∑
m=1
[ Li1:mπ ( π̄i1:m−1 , π̄im ) − CDmaxKL (πim , π̄im) ] .
For proof see Appendix C.2. This lemma provides an idea about how a joint policy can be improved. Namely, by Equation (6), we know that if any agents were to set the values of the above summands Li1:mπ (π̄
i1:m−1 , π̄im) − CDmaxKL (πim , π̄im) by sequentially updating their policies, each of them can always make its summand be zero by making no policy update (i.e., π̄im = πim). This implies that any positive update will lead to an increment in summation. Moreover, as there are n agents making policy updates, the compound increment can be large, leading to a 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 1. We want to highlight that the algorithm is
Algorithm 1 Multi-Agent Policy Iteration with Monotonic Improvement Guarantee
1: Initialise the joint policy π0 = (π10 , . . . , π n 0 ). 2: for k = 0, 1, . . . do 3: Compute the advantage function Aπk(s,a) for all state-(joint)action pairs (s,a). 4: Compute = maxs,a |Aπk(s,a)| and C = 4γ (1−γ)2 . 5: Draw a permutaion i1:n of agents at random. 6: for m = 1 : n do 7: Make an update πimk+1 = arg maxπim [ Li1:mπk ( π i1:m−1 k+1 , π im ) − CDmaxKL (π im k , π im) ] . 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 1 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 a unique optimisation objective that takes into account all previous agents’ updates, which is also the key for the monotonic improvement property to hold.

heading: 3.2 THEORETICAL ANALYSIS
text: Now we justify by the following theorm that Algorithm 1 enjoys monotonic improvement property.
Theorem 2. A sequence (πk) ∞ k=0 of joint policies updated by Algorithm 1 has the monotonic improvement property, i.e., J(πk+1) ≥ J(πk) for all k ∈ N. For proof see Appendix C.2. With the above theorem, we finally claim a 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. Definition 3. In a fully-cooperative game, a joint policy π∗ = (π1∗, . . . , πn∗ ) is a Nash equilibrium (NE) if for every i ∈ N , πi ∈ Πi implies J (π∗) ≥ J ( πi,π−i∗ ) .
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 1’s asymptotic convergence behaviour towards NE. Proposition 2. Supposing in Algorithm 1 any permutation of agents has a fixed non-zero probability, a sequence (πk) ∞ k=0 of joint policies generated by Algorithm 1, in a cooperative Markov game, has a non-empty set of limit points, each of which is a Nash equilibrium.
For proof see Appendix C.3. In deriving this result, the novel details introduced by Algorithm 1 played an important role. The monotonic improvement property (Theorem 2), achieved through the multi-agent advantage and the sequential update scheme, provided us with a guarantee on the convergence of the return. Furthermore, randomisation of the update order assured that, at convergence, none of the agents is incentified to make an update. The proof is finalised by excluding a possibility that the algorithm converges at non-equilibrium points.

heading: 4 PRACTICAL ALGORITHMS
text: When implementing Algorithm 1 in practice, large state and action spaces could prevent agents from designating policies πi(·|s) for each state s separately. To handle this, we parameterise each agent’s policy πiθi by θ
i, which, together with other agents’ policies, forms a joint policy πθ parametrised by θ = (θ1, . . . , θn). In this section, we develop two deep MARL algorithms to optimise the θ.

heading: 4.1 HATRPO
text: Computing DmaxKL ( πim θimk , πimθim ) in Algorithm 1 is challenging; it requires evaluating the KLdivergence for all states at each iteration. Similar to TRPO, one can ease this maximal KLdivergence penalty DmaxKL ( πim θimk , πimθim ) by replacing it with the expected KL-divergence constraint Es∼ρπθk [ DKL ( πim θ im k (·|s), πim θim (·|s) )] ≤ δ where δ is a threshold hyperparameter, and the expectation can be easily approximated by stochastic sampling. With the above amendment, we propose practical HATRPO algorithm in which, at every iteration k + 1, given a permutation of agents i1:n, agent im∈{1,...,n} sequentially optimises its policy parameter θ im k+1 by maximising a constrained objective:
θimk+1 = arg max θim E s∼ρπθk ,a i1:m−1∼π i1:m−1
θ i1:m−1 k+1
,aim∼πim θim
[ Aimπθk (s,ai1:m−1 , aim) ] ,
subject to Es∼ρπθk [ DKL ( πim θ im k (·|s), πim θim (·|s) )] ≤ δ. (7)
To compute the above equation, similar to TRPO, one can apply a linear approximation to the objective function and a quadratic approximation to the KL constraint; the optimisation problem in Equation (7) can be solved by a closed-form update rule as
θimk+1 = θ im k + α j
√ 2δ
gimk (H im k ) −1gimk
(Himk ) −1gimk , (8)
where Himk = ∇ 2 θimEs∼ρπθk
[ DKL ( πim θ im k (·|s), πim θim (·|s) )]∣∣ θim=θ im k is the Hessian of the expected KL-
divergence, gimk is the gradient of the objective in Equation (7), α j < 1 is a positive coefficient that is found via backtracking line search, and the product of (Himk ) −1gimk can be efficiently computed with conjugate gradient algorithm.
The last missing piece for HATRPO is to estimate E ai1:m−1∼π
i1:m−1 θk+1 ,aim∼πim θim
[ Aimπθk ( s,ai1:m−1 , aim )] ,
which poses new challenges because each agent’s objective has to take into account all previous
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 3. Let π = ∏n j=1 π
ij be a joint policy, and Aπ(s,a) be its joint advantage function. Let π̄i1:m−1 = ∏m−1 j=1 π̄
ij be some other joint policy of agents i1:m−1, and π̂im be some other policy of agent im. Then, for every state s,
Eai1:m−1∼π̄i1:m−1 ,aim∼π̂im [ Aimπ ( s,ai1:m−1 , aim )] = Ea∼π [( π̂im(aim |s) πim(aim |s) − 1 ) π̄i1:m−1(ai1:m−1 |s) πi1:m−1(ai1:m−1 |s) Aπ(s,a) ] . (9)
For proof see Appendix D.1. One benefit of applying Equation (9) is that agents only need to maintain a joint advantage estimator Aπ(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 an estimator Â(s, a) of the advantage function Aπθk (s,a), for example GAE (Schulman et al., 2015b), we can estimate E a i1:m−1∼π i1:m−1
θ i1:m−1 k+1
,aim∼πim θim
[ Aimπθk ( s,ai1:m−1 , aim )] with an estimator of
(πimθ (aim |s) πimθk (a im |s) − 1 ) M i1:m ( s,a ) , where M i1:m = π̄i1:m−1(ai1:m−1 |s) πi1:m−1(ai1:m−1 |s) Â ( s,a ) . (10)
Notably, Equation (10) aligns nicely with the sequential update scheme in HATRPO. For agent im, since previous agents i1:m−1 have already made their updates, the compound policy ratio for M i1:m in Equation (10) is easy to compute. Given a batch B of trajectories with length T , we can estimate the gradient with respect to policy parameters (derived in Appendix D.2) as follows,
ĝimk = 1 |B| ∑ τ∈B T∑ t=0 M i1:m(st,at)∇θim log π im θim (ait|st) ∣∣ θim=θ im k .
The term −1 ·M i1:m(s,a) of Equation (10) is not reflected in ĝimk , as it only introduces a constant with zero gradient. Along with the Hessian of the expected KL-divergence, i.e.,Himk , we can update θimk+1 by following Equation (8). The detailed pseudocode of HATRPO is listed in Appendix D.3.

heading: 4.2 HAPPO
text: To further alleviate the computation burden fromHimk in HATRPO, one can follow the idea of PPO in Equation (4) by considering only using first order derivatives. This is achieved by making agent im choose a policy parameter θimk+1 which maximises the clipping objective of
Es∼ρπθk ,a ∼πθk
[ min ( πim θim
(ai|s) πim θ im k (ai|s) M i1:m (s,a) , clip
( πim θim
(ai|s) πim θ im k (ai|s) , 1±
) M i1:m (s,a) )] . (11)
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.

heading: 4.3 RELATED WORK
text: We are fully aware of previous attempts that tried to extend TRPO/PPO into MARL. Despite empirical successes, none of them managed to propose a theoretically-justified 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 et al. (2021) proposed MAPPO which enhances IPPO by considering a 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-theoretical approach at the meta-game level among agents. Unfortunately, it 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 π̄i(ai|s)/πi(ai|s) for all agents (see their Equation (7)), which, similar
to parameter sharing, largely limits the policy space for optimisation. Moreover, their method comes with a δ/n KL-constraint threshold that fails to consider scenarios with large agent number.
One of the key ideas behind our HATRPO/HAPPO is 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 is developed based on Lemma 1, which does not require any artificial assumptions 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 in HATRPO/MAPPO can be randomised at each iteration, which also offers desirable convergence property, as stated in Proposition 2 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, represented 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 a single iteration of sequential updates is insufficient to learn complex policies. Furthermore, its design and analysis rely on closed-form 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 as an effective solution to value-based methods in MARL where tremendous 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 1, 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 to future developments on value-based MARL methods.

heading: 5 EXPERIMENTS AND RESULTS
text: We consider two most common benchmarks—StarCraftII Multi-Agent Challenge (SMAC) (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.
StarCraftII Multi-Agent Challenge (SMAC). SMAC contains a 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 to 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 is 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 2 confirm that SMAC is not sufficiently difficult to show off the capabilities of HATRPO/HAPPO when compared against existing methods.
Multi-Agent MuJoCo. In comparison to SMAC, we believe Mujoco enviornment provides a more suitable testing case for our methods. MuJoCo tasks challenge a robot to learn an optimal way of motion; Multi-Agent MuJoCo models each part of a robot as an independent agent, for example, 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 HATRPO and its rivals enlarges with the increasing number of agents. Meanwhile, we can observe that HATRPO outperforms HAPPO in almost all tasks; we believe it is because the hard KL constraint
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
1000
2000
3000 4000 Av er ag e Ep iso de R ew
ar d
Ant 2x4
(a) 2x4-Agent Ant
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
0
1000
2000
3000
4000
Av er
ag e
Ep iso
de R
ew ar
d
Ant 4x2
(b) 4x2-Agent Ant
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
0
1000
2000
3000
4000
5000
Av er
ag e
Ep iso
de R
ew ar
d
Ant 8x1 HATRPO HAPPO MAPPO IPPO MADDPG
(c) 8x1-Agent Ant
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
0
1000
2000
3000
4000
5000
6000
Av er
ag e
Ep iso
de R
ew ar
d
HalfCheetah 2x3
(d) 2x3-Agent HalfCheetah
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
0
1000
2000
3000
4000
5000
6000
Av er
ag e
Ep iso
de R
ew ar
d
HalfCheetah 3x2
(e) 3x2-Agent HalfCheetah
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
0
1000
2000
3000
4000
5000
6000
Av er
ag e
Ep iso
de R
ew ar
d
HalfCheetah 6x1 HATRPO HAPPO MAPPO IPPO MADDPG
(f) 6x1-Agent HalfCheetah
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
0
1000
2000
3000
4000
5000
Av er
ag e
Ep iso
de R
ew ar
d
Walker 2x3
(g) 2x3-Agent Walker
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
0
1000
2000
3000
4000
Av er
ag e
Ep iso
de R
ew ar
d
Walker 3x2
(h) 3x2-Agent Walker
0.0 0.2 0.4 0.6 0.8 1.0 Environment steps 1e7
0
1000
2000
3000
4000
5000
Av er
ag e
Ep iso
de R
ew ar
d
Walker 6x1 HATRPO HAPPO MAPPO IPPO MADDPG
(i) 6x1-Agent Walker
Humanoid 17x1
HumanoidStandup 17x1
ManyAgentSwimmer 10x2
in HATRPO, compared to the clipping version in HAPPO, relates more closely to Algorithm 1 that attains monotonic improvement guarantee.

heading: 6 CONCLUSION
text: In this paper, we successfully apply trust region learning to multi-agent settings by proposing the first MARL algorithm that attains theoretically-justified monotonical improvement property. The key to our development is the multi-agent advantage decomposition lemma that holds in general with no need for any assumptions on agents sharing parameters or the joint value function being decomposable. Based on this, we introduced two practical deep MARL algorithms: HATRPO and HAPPO. Experimental results on both discrete and continuous control tasks (i.e., SMAC and Multi-Agent Mujoco) confirm their state-of-the-art performance. For future work, we will consider incorporating the safety constraint into HATRPO/HAPPO and propose rigorous safety-aware MARL solutions.

heading: A Preliminaries 14
text: A.1 Definitions and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.2 Proofs of Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

heading: B Proof of Proposition 1 16

heading: C Derivation and Analysis of Algorithm 1 17
text: C.1 Recap of Existing Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
C.2 Analysis of Training of Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . . . 17
C.3 Analysis of Convergence of Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . 19

heading: D HATRPO and HAPPO 22
text: D.1 Proof of Proposition 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
D.2 Derivation of the gradient estimator for HATRPO . . . . . . . . . . . . . . . . . . 22
D.3 Pseudocode of HATRPO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
D.4 Pseudocode of HAPPO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

heading: E Hyper-parameter Settings for Experiments 24

heading: F Ablation Experiments 26

heading: G Ablation Study on Non-Parameter Sharing MAPPO/IPPO 26
text: H Multi-Agent Particle Environment Experiments 27

heading: A PRELIMINARIES
text: A.1 DEFINITIONS AND ASSUMPTIONS
Assumption 1. There exists η ∈ R, such that 0 < η 1, and for every agent i ∈ N , the policy space Πi is η-soft; that means that for every πi ∈ Πi, s ∈ S, and ai ∈ Ai, we have πi(ai|s) ≥ η. Definition 3. In a fully-cooperative game, a joint policy π∗ = (π1∗, . . . , πn∗ ) is a Nash equilibrium (NE) if for every i ∈ N , πi ∈ Πi implies J (π∗) ≥ J ( πi,π−i∗ ) .
Definition 4. Let X be a finite set and p : X → R, q : X → R be two maps. Then, the notion of distance between p and q that we adopt is given by ||p− q|| , maxx∈X |p(x)− q(x)|.
A.2 PROOFS OF PRELIMINARY RESULTS
Lemma 3. Every agent i’s policy space Πi 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 πi, π̄i ∈ Πi, for every α ∈ [0, 1], απi + (1 − α)π̄i ∈ Πi. Clearly, for all s ∈ S and ai ∈ Ai, we have
απi(ai|s) + (1− α)π̄i(ai|s) ≥ αη + (1− α)η = η.
Also, for every state s,∑ ai [ απi(ai|s) + (1− α)π̄i(ai|s) ] = α ∑ ai πi(ai|s) + (1− α) ∑ ai π̄i(ai|s) = α+ 1− α = 1,
which establishes convexity.
For compactness, we first prove that Πi is closed. Let ( πik )∞ k=0
be a convergent sequence of policies of agent i. Let πi be the limit. We will prove that πi is a policy. First, by Assumption 1, for any k ∈ N, s ∈ S , and ai ∈ Ai, we have πik ( ai|s ) ≥ η.
Hence, πi ( ai|s ) = lim k→∞ πik ( ai|s ) ≥ lim k→∞ η ≥ η.
Furtheremore, for any k and s, we have ∑ ai π i k ( ai|s ) = 1. Hence∑
ai
πi ( ai|s ) = ∑ ai lim k→∞ πi ( ai|s ) = lim k→∞ ∑ ai πi ( ai|s ) = lim k→∞ 1 = 1.
With these two conditions satisfied, πi is a policy, which proves the closure.
Further, for all policies πi, states s and actions a, |πi(ai|s)| ≤ 1. This means that ||πi||max ≤ 1, which proves boundedness. Hence, Πi is compact.
Lemma 4 (Continuity of ρπ). The improper state distribution ρπ is continuous in π.
Proof. First, let us show that for any t ∈ N, the distribution ρtπ is continous in π. We will do it by induction. This obviously holds when t = 0, as ρ0 does not depend on policy. Hence, we can assume that for some t ∈ N, the distribution ρtπ is continuous in π. Let us now consider two policies π and π̂. Let s′ ∈ S. We have
∣∣ρt+1π (s′)− ρt+1π̂ (s′)∣∣ = ∣∣∣∣∣∑ s ρtπ(s) ∑ a π(a|s)P (s′|s, a)− ∑ s ρtπ̂(s) ∑ a π̂(a|s)P (s′|s, a) ∣∣∣∣∣ =
∣∣∣∣∣∑ s ∑ a [ ρtπ(s)π(a|s)− ρtπ̂(s)π̂(a|s) ] P (s′|s, a) ∣∣∣∣∣ ≤ ∑ s ∑ a ∣∣ρtπ(s)π(a|s)− ρtπ̂(s)π̂(a|s)∣∣P (s′|s, a)
= ∑ s ∑ a ∣∣ρtπ(s)π(a|s)− ρtπ(s)π̂(a|s) + ρtπ(s)π̂(a|s)− ρtπ̂(s)π̂(a|s)∣∣P (s′|s, a) ≤ ∑ s ∑ a ( ρtπ(s) |π(a|s)− π̂(a|s)|+ π̂(a|s)
∣∣ρtπ(s)− ρtπ̂(s)∣∣) ≤ ∑ s ∑ a ( ρtπ(s)||π − π̂||+ π̂(a|s)||ρtπ − ρtπ̂||
) = ∑ s ρtπ(s) ∑ a ||π − π̂||+ ∑ s ||ρtπ − ρtπ̂|| ∑ a π̂(a|s)
= |A| · ||π − π̂||+ |S| · ||ρtπ − ρtπ̂||. Hence, we obtain
||ρt+1π − ρt+1π̂ || ≤ |A| · ||π − π̄||+ |S| · ||ρ t π − ρtπ̂||. (12)
Using the base case, taking the limit as π̄ → π, we get that the right-hand-side of Equation (12) converges to 0, which proves that every ρt+1π is continuous in π, and finishes the inductive step.
We can now prove that the total marginal state distribution ρπ is continous in π. To do that, let’s take an arbitrary > 0, and a natural T such that T > log[ (1−γ)4 ]
log γ . Equivalently, we choose T such
that 2γ T
1−γ < 2 . Let π and π̂ be two policies. We have
|ρπ(s)− ρπ̂(s)| = ∣∣∣∣∣ ∞∑ t=0 γt ( ρtπ(s)− ρtπ̂(s) )∣∣∣∣∣ =
∣∣∣∣∣ T−1∑ t=0 γt ( ρtπ(s)− ρtπ̂(s) ) + γT ∞∑ t=T γt−T ( ρtπ(s)− ρtπ̂(s) )∣∣∣∣∣ ≤ T−1∑ t=0 γt ∣∣ρtπ(s)− ρtπ̂(s)∣∣+ γT ∞∑ t=T γt−T ∣∣ρtπ(s)− ρtπ̂(s)∣∣ ≤ T−1∑ t=0 γt ∣∣ρtπ(s)− ρtπ̂(s)∣∣+ γT ∞∑ t=T 2γt−T
= T−1∑ t=0 γt ∣∣ρtπ(s)− ρtπ̂(s)∣∣+ 2γT 1− γ < T−1∑ t=0 γt ∣∣ρtπ(s)− ρtπ̂(s)∣∣+ 2 ≤ T−1∑ t=0 ∣∣ρtπ(s)− ρtπ̂(s)∣∣+ 2 ≤ T−1∑ t=0 ||ρtπ − ρtπ̂||+ 2 . (13)
Now, by continuity of each of ρtπ , for t = 0, 1, . . . , T −1, we have that there exists a δ > 0 such that ||π − π̂|| < δ implies ||ρtπ − ρtπ̂|| < 2T . Taking such δ, by Equation (13), we get ||ρπ − ρπ̂|| ≤ , which finishes the proof.
Lemma 5 (Continuity of Qπ). Let π be a policy. Then Qπ(s, a) is Lipschitz-continuous in π.
Proof. Let π and π̂ be two policies. Then we have |Qπ(s, a)−Qπ̂(s, a)|
= ∣∣∣∣∣ ( r(s, a) + γ ∑ s′ ∑ a P (s′|s, a)π(a|s)Qπ(s, a) ) − ( r(s, a) + γ ∑ s′ ∑ a P (s′|s, a)π̂(a|s)Qπ̂(s, a) )∣∣∣∣∣ = γ
∣∣∣∣∣∑ s′ ∑ a P (s′|s, a) [π(a|s)Qπ(s, a)− π̂(a|s)Qπ̂(s, a)] ∣∣∣∣∣ ≤ γ
∑ s′ ∑ a P (s′|s, a) |π(a|s)Qπ(s, a)− π̂(a|s)Qπ̂(s, a)|
= γ ∑ s′ ∑ a P (s′|s, a) |π(a|s)Qπ(s, a)− π̂(a|s)Qπ(s, a) + π̂(a|s)Qπ(s, a)− π̂(a|s)Qπ̂(s, a)|
≤ γ ∑ s′ ∑ a P (s′|s, a) (|π(a|s)Qπ(s, a)− π̂(a|s)Qπ(s, a)|+ |π̂(a|s)Qπ(s, a)− π̂(a|s)Qπ̂(s, a)|)
= γ ∑ s′ ∑ a P (s′|s, a)|π(a|s)− π̂(a|s)| · |Qπ(s, a)|
+ γ ∑ s′ ∑ a P (s′|s, a)π̂(a|s) |Qπ(s, a)−Qπ̂(s, a)|
≤ γ ∑ s′ ∑ a P (s′|s, a)||π − π̂|| ·Qmax
+ γ ∑ s′ ∑ a P (s′|s, a)π̂(a|s)||Qπ −Qπ̂||
= γ Qmax · |A| · ||π − π̂||+ γ||Qπ −Qπ̂||
Hence, we get
||Qπ −Qπ̂|| ≤ γ Qmax · |A| · ||π − π̂||+ γ||Qπ −Qπ̂||,
which implies
||Qπ −Qπ̂|| ≤ γ Qmax · |A| · ||π − π̂||
1− γ . (14)
Equation (14) establishes Lipschitz-continuity with a constant γ Qmax·|A|1−γ .
Corollary 1. From Lemma 5 we obtain that the following functions are Lipschitz-continuous in π:
the state value function Vπ = ∑ a π(a|s)Qπ(s, a),
the advantage function Aπ(s, a) = Qπ(s, a)− Vπ(s),
and the expected total reward J(π) = Es∼ρ0 [Vπ(s)].
Lemma 6. Let π and π̂ be policies. The quantity Es∼ρπ,a∼π̂ [Aπ(s, a)] is continuous in π.
Proof. We have
Es∼ρπ,a∼π̂ [Aπ(s, a)] = ∑ s ∑ a ρπ(s)π̂(a|s)Aπ(s, a).
Continuity follows from continuity of each ρπ(s) (Lemma 4) and Aπ(s, a) (Corollary 1).
Corollary 2 (Continuity in MARL). All the results about continuity in π extend to MARL. Policy π can be replaced with joint policy π; as π is Lipschitz-continuous in agent i’s policy πi, the above continuity results extend to conitnuity in πi. Thus, we will quote them in our proofs for MARL.

heading: B PROOF OF PROPOSITION 1
text: Proposition 1. Let’s consider a fully-cooperative game with an even number of agents n, one state, and the joint action space {0, 1}n, where the reward is given by r(0n/2,1n/2) = r(1n/2,0n/2) = 1, and r(a1:n) = 0 for all other joint actions. Let J∗ be the optimal joint reward, and J∗share be the optimal joint reward under the shared policy constraint. Then
J∗share J∗ = 2 2n .
Proof. Clearly J∗ = 1. An optimal joint policy in this case is, for example, the deterministic policy with joint action (0n/2,1n/2).
Now, let the shared policy be (θ, 1−θ), where θ determines the probability that an agent takes action 0. Then, the expected reward is
J(θ) = Pr ( a1:n = (0n/2,1n/2) ) · 1 + Pr ( a1:n = (1n/2,0n/2) ) · 1 = 2 · θn/2(1− θ)n/2.
In order to maximise J(θ), we must maximise θ(1 − θ), or equivalently, √ θ(1− θ). By the artithmetic-geometric means inequality, we have√ θ(1− θ) ≤ θ + (1− θ)
2 =
1 2 ,
where the equality holds if and only if θ = 1− θ, that is θ = 12 . In such case we have
J∗share = J
( 1
2
) = 2 · 2−n/2 · 2−n/2 = 2
2n ,
which finishes the proof.

heading: C DERIVATION AND ANALYSIS OF ALGORITHM 1
text: C.1 RECAP OF EXISTING RESULTS
Lemma 7 (Performance Difference). Let π̄ and π be two policies. Then, the following identity holds,
J(π̄)− J(π) = Es∼ρπ̄,a∼π̄ [Aπ(s, a)] .
Proof. See Kakade & Langford (2002) (Lemma 6.1) or 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 Lπ(π̄) = J(π) + Es∼ρπ,a∼π̄ [Aπ(s, a)] ,DmaxKL (π, π̄) = maxs DKL (π(·|s), π̄(·|s)) . Then the inequality of
J(π̄) ≥ Lπ(π̄)− CDmaxKL ( π, π̄ ) (2)
holds, where C = 4γmaxs,a |Aπ(s,a)|(1−γ)2 .
Proof. See Schulman et al. (2015a) (Appendix A and Equation (9) of the paper).
C.2 ANALYSIS OF TRAINING OF ALGORITHM 1
Lemma 1 (Multi-Agent Advantage Decomposition). In any cooperative Markov games, given a joint policy π, for any state s, and any agent subset i1:m, the below equations holds.
Ai1:mπ ( s,ai1:m ) = m∑ j=1 A ij π ( s,ai1:j−1 , aij ) .
Proof. By the definition of multi-agent advantage function,
Ai1:mπθ (s,a i1:m) = Qi1:mπθ (s,a i1:m)− Vπθ (s)
= m∑ k=1 [ Qi1:kπθ (s,a i1:k)−Qi1:k−1πθ (s,ai1:k−1) ]
= m∑ k=1 Aikπθ (s,a i1:k−1 , aik),
which finishes the proof. Note that a similar finding has been shown in Kuba et al. (2021). Lemma 8. Let π = ∏n i=1 π i and π̄ = ∏n i=1 π̄ i be joint policies. Then
DmaxKL (π, π̄) ≤ n∑ i=1 DmaxKL ( πi, π̄i )
Proof. For any state s, we have
DKL (π(·|s), π̄(·|s)) = Ea∼π [logπ(a|s)− log π̄(a|s)]
= Ea∼π [ log ( n∏ i=1 πi(ai|s) ) − log ( n∏ i=1 π̄i(ai|s) )]
= Ea∼π [ n∑ i=1 log πi(ai|s)− n∑ i=1 log π̄i(ai|s) ]
= n∑ i=1 Eai∼πi,a−i∼π−i [ log πi(ai|s)− log π̄i(ai|s) ] = n∑ i=1 DKL ( πi(·|s), π̄i(·|s) ) .
Now, taking maximum over s on both sides yields
DmaxKL (π, π̄) ≤ n∑ i=1 DmaxKL ( πi, π̄i ) ,
as required.
Lemma 2. Let π be a joint policy. Then, for any joint policy π̄, we have
J(π̄) ≥ J(π) + n∑
m=1
[ Li1:mπ ( π̄i1:m−1 , π̄im ) − CDmaxKL (πim , π̄im) ] .
Proof. By Theorem 1
J(π̄) ≥ Lπ(π̄)− CDmaxKL (π, π̄) = J(π) + Es∼ρπ,a∼π̄ [Aπ(s,a)]− CDmaxKL (π, π̄) which by Lemma 1 equals
= J(π) + Es∼ρπ,a∼π̄
[ n∑
m=1
Aimπ ( s,ai1:m−1 , aim )] − CDmaxKL (π, π̄)
and by Lemma 8 this is at least
≥ J(π) + Es∼ρπ,a∼π̄
[ n∑
m=1
Aimπ ( s,ai1:m−1 , aim )] − n∑ m=1 CDmaxKL (π im , π̄im)
= J(π) + n∑ m=1 Es∼ρπ,ai1:m−1∼π̄i1:m−1 ,aim∼π̄im [ Aimπ ( s,ai1:m−1 , aim )] − n∑ m=1 CDmaxKL (π im , π̄im)
= J(π) + n∑ m=1 ( Li1:mπ ( π̄i1:m−1 , π̄im ) − CDmaxKL (πim , π̄im) ) .
Theorem 2. A sequence (πk) ∞ k=0 of joint policies updated by Algorithm 1 has the monotonic improvement property, i.e., J(πk+1) ≥ J(πk) for all k ∈ N.
Proof. Let π0 be any joint policy. For every k ≥ 0, the joint policy πk+1 is obtained from πk by Algorithm 1 update; for m = 1, . . . , n,
πimk+1 = arg max πim
[ Li1:mπk ( π i1:m−1 k+1 , π im ) − CDmaxKL ( πimk , π im )] .
By Theorem 1, we have J(πk+1) ≥ Lπk(πk+1)− CDmaxKL (πk,πk+1), which by Lemma 8 is lower-bounded by
≥ Lπk(πk+1)− n∑
m=1
CDmaxKL (π im k , π im k+1)
= J(πk) + n∑ m=1 ( Li1:mπk (π i1:m−1 k+1 , π im k+1)− CD max KL (π im k , π im k+1) ) , (15)
and as for every m, πimk+1 is the argmax, this is lower-bounded by
≥ J(πk) + n∑
m=1
( Li1:mπk (π i1:m−1 k+1 , π im k )− CD max KL (π im k , π im k ) ) ,
which, as mentioned in Definition 2, equals
= J(πk) + n∑ m=1 0 = J(πk),
where the last inequality follows from Equation (6). This proves that Algorithm 1 achieves monotonic improvement.
C.3 ANALYSIS OF CONVERGENCE OF ALGORITHM 1
Proposition 2. Supposing in Algorithm 1 any permutation of agents has a fixed non-zero probability, a sequence (πk) ∞ k=0 of joint policies generated by Algorithm 1, in a cooperative Markov game, has a non-empty set of limit points, each of which is a Nash equilibrium.
Proof. Step 1 (convergence). Firstly, it is clear that the sequence (J(πk)) ∞ k=0 converges as, by Theorem 2, it is non-decreasing and bounded above by Rmax1−γ . Let us denote the limit by J̄ . For every k, we denote the tuple of agents, according to whose order the agents perform the sequential updates, by ik1:n, and we note that ( ik1:n ) k∈N is a random process. Furthermore, we know that the sequence of policies (πk) is bounded, so by Bolzano-Weierstrass Theorem, it has at least one convergent subsequence. Let π̄ be any limit point of the sequence (note that the set of limit points is a random set), and ( πkj )∞ j=0
be a subsequence converging to π̄ (which is a random subsequence as well). By continuity of J in π (Corollary 1), we have
J(π̄) = J ( lim j→∞ πkj ) = lim j→∞ J ( πkj ) = J̄ . (16)
For now, we introduce an auxiliary definition.
Definition 5 (TR-Stationarity). A joint policy π̄ is trust-region-stationary (TR-stationary) if, for every agent i,
π̄i = arg max πi
[ Es∼ρπ̄,ai∼πi [ Aiπ̄(s, a i) ] − Cπ̄DmaxKL ( π̄i, πi )] ,
where Cπ̄ = 4γ (1−γ)2 , and = maxs,a |Aπ̄(s,a)|.
We will now establish the TR-stationarity of any limit point joint policy π̄ (which, as stated above, is a random variable). Let Ei0:∞1:n [·] denote the expected value operator under the random process (i0:∞1:n ). Let also k = maxs,a |Aπk(s,a)|, and Ck = 4γ k (1−γ)2 . We have
0 = lim k→∞ Ei0:∞1:n [J(πk+1)− J(πk)]
≥ lim k→∞ Ei0:∞1:n [Lπk(πk+1)− CkD max KL (πk,πk+1)] by Theorem 1
≥ lim k→∞ Ei0:∞1:n [ L ik1 πk ( π ik1 k+1 ) − CkDmaxKL ( π ik1 k , π ik1 k+1 )] by Equation (15) and the fact that each of its summands is non-negative
Now, we consider an arbitrary limit point π̄ from the (random) limit set, and a (random) subsequence( πkj )∞ j=0 that converges to π̄. We get
0 ≥ lim j→∞ Ei0:∞1:n [ L i kj 1 πkj ( π i kj 1 kj+1 ) − CkjDmaxKL ( π i kj 1 kj , π i kj 1 kj+1 )] .
As the expectation is taken of non-negative random variables, and for every i ∈ N and k ∈ N, with some positive probability pi, we have i kj 1 = i (because every permutation has non-zero probability), the above is bounded from below by
pi lim j→∞ max πi [ Liπkj (πi)− CkjDmaxKL ( πikj , π i )] ,
which, as πkj converges to π̄, equals to
pi max πi
[ Liπ̄(π i)− Cπ̄DmaxKL ( π̄i, πi )] ≥ 0, by Equation (6).
For convergence of Liπkj (π i) we used Definition 2 combined with Lemma 6, for convergence of Ckj we used Corollary 1, and the convergence of D max KL follows from continuity of DKL and max. This proves that, for any limit point π̄ of the random process (πk) induced by Algorithm 1, maxπi [ Liπ̄(π i)− Cπ̄DmaxKL ( π̄i, πi )] = 0, 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: a TR-stationary joint policy π̄, for every state s ∈ S, satisfies
π̄i = arg max πi
Eai∼πi [ Aiπ̄(s, a i) ] . (17)
We will use the technique of the proof by contradiction. Suppose that there is a state s0 such that there exists a policy π̂i with Eai∼π̂i [ Aiπ̄(s0, a i) ] > Eai∼π̄i [ Aiπ̄(s0, a i) ] . (18) Let us parametrise the policies πi according to the template
πi(·|s0) = ( θi1, . . . , θ i di−1, 1− di−1∑ j=1 θij )
where the values of θij (j = 1, . . . , d i − 1) are such that πi(·|s0) is a valid policy. Then we can rewrite our quantity of interest (the objective of Equation (17) as
Eai∼πi [ Aiπ̄(s0, a i) ] = di−1∑ j=1 θij ·Aiπ̄ ( s0, a i j ) + (1− di−1∑ h=1 θih)A i π̄ ( s0, a i di ) =
di−1∑ j=1 θij [ Aiπ̄ ( s0, a i j ) −Aiπ̄ ( s0, a i di )] +Aiπ̄ ( s0, a i di ) ,
which is an affine function of the policy parameterisation. It follows that its gradient (with respect to θi) and directional derivatives are constant in the space of policies at state s0. The existance of policy π̂i(·|s0), for which Inequality (18) holds, implies that the directional derivative in the direction from π̄i(·|s0) to π̂i(·|s0) is strictly positive. We also have
∂DKL(π̄i(·|s0), πi(·|s0)) ∂θij = ∂ ∂θij
[ (π̄i(·|s0))T (log π̄i(·|s0)− log πi(·|s0)) ] = ∂
∂θij
[ −(π̄i)T log πi ] (omitting state s0 for brevity)
= − ∂ ∂θij di−1∑ k=1 π̄i(aik) log θ i k − ∂ ∂θij π̄idi log
( 1−
di−1∑ k=1 θik
)
= − π̄ij θij + π̄idi 1− ∑di−1 k=1 θ i k = − π̄ij πij + π̄idi πidi = 0, when evaluated at πi = π̄i, (19)
which means that the KL-penalty has zero gradient at π̄i(·|s0). Hence, when evaluated at πi(·|s0) = π̄i(·|s0), the objective
ρπ̄(s0)Eai∼πi [ Aiπ̄(s0, a i) ] − Cπ̄DKL ( π̄i(·|s0), πi(·|s0) ) has a strictly positive directional derivative in the direction of π̂i(·|s0). Thus, there exists a policy π̃i(·|s0), sufficiently close to π̄i(·|s0) on the path joining it with π̂i(·|s0), for which
ρπ̄(s0)Eai∼π̃i [ Aiπ̄(s0, a i) ] − Cπ̄DKL ( π̄i(·|s0), π̃i(·|s0) ) > 0.
Let πi∗ be a policy such that π i ∗(·|s0) = π̃i(·|s0), and πi∗(·|s) = π̄i(·|s) for states s 6= s0. As for these states we have
ρπ̄(s)Eai∼πi∗ [ Aiπ̄(s, a i) ] = ρπ̄(s)Eai∼π̄i [ Aiπ̄(s, a i) ] = 0, and DKL(π̄i(·|s), πi∗(·|s)) = 0,
it follows that
Liπ̄(π i ∗)− Cπ̄DmaxKL (π̄i, πi∗) = ρπ̄(s0)Eai∼π̃i [ Aiπ̄(s0, a i) ] − Cπ̄DKL ( π̄i(·|s0), π̃i(·|s0) ) > 0 = Liπ̄(π̄ i)− Cπ̄DmaxKL (π̄i, π̄i),
which is a contradiction with TR-stationarity of π̄. Hence, the claim of Equation (17) is proved. Step 3 (optimality). Now, for a fixed joint policy π̄−i of other agents, π̄i satisfies
π̄i = arg max πi
Eai∼πi [ Aiπ̄(s, a i) ]
= arg max πi
Eai∼πi [ Qiπ̄(s, a i) ] , ∀s ∈ S,
which is the Bellman optimality equation (Sutton & Barto, 2018). Hence, for a fixed joint policy π̄−i, the policy π̄i is optimal:
π̄i = arg max πi J(πi, π̄−i).
As agent i was chosen arbitrarily, π̄ is a Nash equilibrium.

heading: D HATRPO AND HAPPO
text: D.1 PROOF OF PROPOSITION 3 Proposition 3. Let π = ∏n j=1 π
ij be a joint policy, and Aπ(s,a) be its joint advantage function. Let π̄i1:m−1 = ∏m−1 j=1 π̄
ij be some other joint policy of agents i1:m−1, and π̂im be some other policy of agent im. Then, for every state s,
Eai1:m−1∼π̄i1:m−1 ,aim∼π̂im [ Aimπ ( s,ai1:m−1 , aim )] = Ea∼π [( π̂im(aim |s) πim(aim |s) − 1 ) π̄i1:m−1(ai1:m−1 |s) πi1:m−1(ai1:m−1 |s) Aπ(s,a) ] . (9)
Proof. We have = Ea∼π [ π̄i1:m(ai1:m |s) πi1:m(ai1:m |s) Aπ(s,a)− π̄i1:m−1(ai1:m−1 |s) πi1:m−1(ai1:m−1 |s) Aπ(s,a) ] = Eai1:m∼πi1:m ,a−i1:m∼π−i1:m [ π̄i1:m(ai1:m |s) πi1:m(ai1:m |s) Aπ(s,a i1:m ,a−i1:m)
] − Eai1:m−1∼πi1:m−1 ,a−i1:m−1∼π−i1:m−1 [ π̄i1:m−1(ai1:m−1 |s) πi1:m−1(ai1:m−1 |s) Aπ(s,a i1:m−1 ,a−i1:m−1)
] = Eai1:m∼π̄i1:m ,a−i1:m∼π−i1:m [ Aπ(s,a i1:m ,a−i1:m) ]
− Eai1:m−1∼π̄i1:m−1 ,a−i1:m−1∼π−i1:m−1 [ Aπ(s,a i1:m−1 ,a−i1:m−1) ]
= Eai1:m∼π̄i1:m [ Ea−i1:m∼π−i1:m [ Aπ(s,a i1:m ,a−i1:m) ]]
− Eai1:m−1∼π̄i1:m−1 [ Ea−i1:m−1∼π−i1:m−1 [ Aπ(s,a i1:m−1 ,a−i1:m−1) ]]
= Eai1:m∼π̄i1:m [ Ai1:mπ (s,a i1:m) ]
− Eai1:m−1∼π̄i1:m−1 [ Ai1:m−1π (s,a i1:m−1) ] ,
which, by Lemma 1, equals = Eai1:m∼π̄i1:m [ Ai1:mπ (s,a i1:m)−Ai1:m−1π (s,ai1:m−1) ]
= Eai1:m∼π̄i1:m [ Aimπ (s,a i1:m−1 , aim) ] .
D.2 DERIVATION OF THE GRADIENT ESTIMATOR FOR HATRPO
∇θimEs∼ρπθk ,a∼πθk
[( πimθim (a
im |s) πim θimk (aim |s) − 1
) M i1:m(s,a) ]
= ∇θimEs∼ρπθk ,a∼πθk
[ πimθim (a
im |s) πim θimk (aim |s) M i1:m(s,a)
] −∇θimEs∼ρπθk ,a∼πθk [ M i1:m(s,a) ]
= Es∼ρπθk ,a∼πθk
[ ∇θimπimθim (a
im |s) πim θimk (aim |s) M i1:m(s,a)
]
= Es∼ρπθk ,a∼πθk
[ πimθim (a
im |s) πim θimk (aim |s) ∇θim log πimθim (a im |s)M i1:m(s,a)
] .
Evaluated at θim = θimk , the above expression equals Es∼ρπθk ,a∼πθk [ M i1:m(s,a)∇θim log πimθim (a im |s) ∣∣ θim=θimk ] ,
which finishes the derivation.
D.3 PSEUDOCODE OF HATRPO
Algorithm 2 HATRPO 1: Input: Stepsize α, batch sizeB, number of: agents n, episodesK, steps per episode T , possible
steps in line search L, line search acceptance threshold κ. 2: Initialize: Actor networks {θi0, ∀i ∈ N}, Global V-value network {φ0}, Replay buffer B 3: for k = 0, 1, . . . ,K − 1 do 4: Collect a set of trajectories by running the joint policy πθk = (π
1 θ1k , . . . , πnθnk ).
5: Push transitions {(oit, ait, oit+1, rt),∀i ∈ N , t ∈ T} into B. 6: Sample a random minibatch of B transitions from B. 7: Compute advantage function Â(s,a) based on global V-value network with GAE. 8: Draw a random permutation of agents i1:n. 9: Set M i1(s,a) = Â(s,a).
10: for agent im = i1, . . . , in do 11: Estimate the gradient of the agent’s maximisation objective
ĝimk = 1 B B∑ b=1 T∑ t=1 ∇θimk log π im θimk ( aimt | o im t ) M i1:m(st,at).
Use the conjugate gradient algorithm to compute the update direction ximk ≈ (Ĥ im k ) −1gimk , where Ĥimk is the Hessian of the average KL-divergence
1 BT B∑ b=1 T∑ t=1 DKL ( πim θimk (·|oimt ), π im θim (·|o im t ) ) .
12: Estimate the maximal step size allowing for meeting the KL-constraint β̂imk ≈ √ 2δ
(x̂imk ) T Ĥimk x̂ im k
.
13: Update agent im’s policy by θimk+1 = θ im k + α j β̂imk x̂ im k ,
where j ∈ {0, 1, . . . , L} is the smallest such j which improves the sample loss by at least καj β̂imk x̂ im k · ĝ im k , found by the backtracking line search.
14: Compute M i1:m+1(s,a) = πim θ im k+1 (aim |oim)
πim θ im k
(aim |oim ) M i1:m(st,at). //Unless m = n.
15: end for 16: Update V-value network by following formula:
17: φk+1 = arg minφ 1 BT B∑ b=1 T∑ t=0 ( Vφ(st)− R̂t )2 18: end for
D.4 PSEUDOCODE OF HAPPO
Algorithm 3 HAPPO 1: Input: Stepsize α, batch size B, number of: agents n, episodes K, steps per episode T . 2: Initialize: Actor networks {θi0, ∀i ∈ N}, Global V-value network {φ0}, Replay buffer B 3: for k = 0, 1, . . . ,K − 1 do 4: Collect a set of trajectories by running the joint policy πθk = (π
1 θ1k , . . . , πnθnk ).
5: Push transitions {(oit, ait, oit+1, rt),∀i ∈ N , t ∈ T} into B. 6: Sample a random minibatch of B transitions from B. 7: Compute advantage function Â(s,a) based on global V-value network with GAE. 8: Draw a random permutation of agents i1:n. 9: Set M i1(s,a) = Â(s,a).
10: for agent im = i1, . . . , in do 11: Update actor im with θimk+1, the argmax of the PPO-Clip objective
1 BT B∑ b=1 T∑ t=0 min
( πim θim (aimt |o im t )
πim θ im k (aimt |o im t )
M i1:m(st,at), clip ( πim θim (aimt |o im t )
πim θ im k (aimt |o im t )
, 1± ) M i1:m(st,at) ) .
12: Compute M i1:m+1(s,a) = πim θ im k+1 (aim |oim)
πim θ im k
(aim |oim ) M i1:m(s,a). //Unless m = n.
13: end for 14: Update V-value network by following formula:
15: φk+1 = arg minφ 1 BT B∑ b=1 T∑ t=0 ( Vφ(st)− R̂t )2 16: end for

heading: E HYPER-PARAMETER SETTINGS FOR EXPERIMENTS
text: The implementation of MADDPG is adopted from the Tianshou framework (Weng et al., 2021), all hyperparameters left unchanged at the origin best-performing status.

heading: F ABLATION EXPERIMENTS
text: 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 a 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).
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, parameter 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 in the sequential update scheme negatively affected the performance at convergence (especially in the task with 6 agents), as suggested by Proposition 2. We conclude that the fine performance of HATRPO relies strongly on the close connection between theory an implementation. The connection becomes increasingly important with the growing number of agents.

heading: G ABLATION STUDY ON NON-PARAMETER SHARING MAPPO/IPPO
text: We verify that heterogeneous-agent trust region algorithms (represented by HATRPO) achieve superior performance to, originally homogeneous, IPPO/MAPPO algorithms with the parameter-sharing function switched off.

heading: H MULTI-AGENT PARTICLE ENVIRONMENT EXPERIMENTS
text: We verify that heterogeneous-agent trust region algorithms (represented here by HAPPO) quickly solve cooperative MPE tasks.

Review summaries:
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. 

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.

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.