Order Matters: Agent-by-agent Policy Optimization
Authors: Xihuai Wang
Zheng Tian
Ziyu Wan
Ying Wen
Jun Wang
Weinan Zhang
Venue: ICLR 2023 poster (2023)
Keywords: Multi-agent Reinforcement Learning

Abstract: While multi-agent trust region algorithms have achieved great success empirically in solving coordination tasks, most of them,  however, suffer from a non-stationarity problem since agents update their policies simultaneously. In contrast, a sequential scheme that updates policies agent-by-agent provides another perspective and shows strong performance. However, sample inefficiency and lack of monotonic improvement guarantees for each agent are still the two significant challenges for the sequential scheme. In this paper, we propose the \textbf{A}gent-by-\textbf{a}gent \textbf{P}olicy \textbf{O}ptimization (A2PO) algorithm to improve the sample efficiency and retain the guarantees of monotonic improvement for each agent during training. We justify the tightness of the monotonic improvement bound compared with other trust region algorithms. From the perspective of sequentially updating agents, we further consider the effect of agent updating order and extend the theory of non-stationarity into the sequential update scheme. To evaluate A2PO, we conduct a comprehensive empirical study on four benchmarks: StarCraftII, Multi-agent MuJoCo, Multi-agent Particle Environment, and Google Research Football full game scenarios. A2PO consistently outperforms strong baselines.

Published as a conference paper at ICLR 2023
ORDER MATTERS: AGENT-BY-AGENT POLICY OPTI- MIZATION
Xihuai Wang 2 Zheng Tian Ziyu Wan Ying Wen', Jun Wang? Weinan Zhang" 1
Shanghai Jiao Tong University, 2 Digital Brain Lab, ShanghaiTech University, University College London
ABSTRACT
While multi-agent trust region algorithms have achieved great success empiri- cally in solving coordination tasks, most of them, however, suffer from a non- stationarity problem since agents update their policies simultancously. In contrast, sequential scheme that updates policies agent-by-agent provides another per- spective and shows strong performance. However, sample inefficiency and lack of monotonic improvement guarantees for each agent are still the two significant challenges for the sequential scheme. In this paper, we propose the Agent-by- agent Policy Optimization (A2PO) algorithm improve the sample efficiency and retain the guarantees of monotonic improvement for each agent during train- ing. We justify the tightness of the monotonic improvement bound compared with other trust region algorithms. From the perspective of sequentially updating agents, we further consider the effect of agent updating order and extend the the- ory of non-stationarity into the sequential update scheme. To evaluate A2PO, we conduct a comprehensive empirical study on four benchmarks: StarCraftII, Multi- agent MuJoCo, Multi-agent Particle Environment, and Google Research Football full game scenarios. A2PO consistently outperforms strong baselines.
INTRODUCTION
Trust region learning methods in reinforcement learning (RL) Kakade & Langford 2002) have
achieved great success in solving complex tasks, from single-agent control tasks (Andrychowicz jet al.] 2020) to multi-agent applications (Albrecht & Stone 2018 Ye et al.) 2020). The methods deliver superior and stable performances because of their theoretical guarantees of monotonic policy improvement. Recently, several works that adopt trust region learning in multi-agent reinforcement learning (MARL) have been proposed, including algorithms which agents independently update their policies using trust region methods (de Witt et al. [0200] Yu et al. (0022) and algorithms that coordinate agents' policies during the update process (Wu al.) 2021 Kuba et al., (022). Most algorithms update the agents simultaneously, that is, all agents perform policy improvement at the same time and cannot observe the change of other agents, as shown Fig. D.. The simultaneous update scheme brings about the non-stationarity problem, i.e., the environment dynamic changes from one agent's 's perspective as other agents also change their policies (Hernandez-Lews et al. 2017).
In contrast to the simultaneous update scheme, algorithms that sequentially execute agent-by- agent updates allow agents to perceive changes made by preceding agents, presenting another perspective for analyzing inter-agent interac- tion (Gemp et af.) (022). [Bettekaas (2021) pro- posed a sequential update framework, named Rollout and Policy Iteration for Single Agent (RPISA) in this paper, which performs rollout every time an agent updates its policy (Fig. [T].. RPISA effectively turns non-stationary MARI, problems into stationary single agent reinforce- ment learning (SARL) ones. It retains the theo-
Multiple Rollents a Stage
Rallsct
Ralloce
Updatto
Upditton
Upplitee
Sequential Poliey Update
J
# Updatere (b)
Updatte R
Update
Single Rollect ot
Simullancous Policy
Updase x
Update
(c)
* All Updated
Figure I: The taxonomy on the rollout scheme and the policy update scheme.
Work done Digital Brain Lab. 'Coresponddecc to Zheng Tian <tianzheng @ shanghaitech..cu..cn
and Weinan Zhang

---

Published as a conference paper at ICLR 2023
retical properties of the chosen SARL base algorithm, such the monotonic improvement (akkdee & LLagfford] 2002). However, it is
since it only utilizes 1/n of the collected sam- ples to update agents' policies. On the other hand, heterogeneous Proximal Policy Optimization (HAPPO) (Kuba et al., (022) sequentially updates agents based on their local advantages estimated from the same rollout samples (Fig. [p).. Although it avoids the waste of collected samples and has a monotonic improvement on the joint policy, the policy improvement of a single agent is not the- oretically guaranteed. Consequently, one agent's policy update may offset previous agents' policy improvement, reducing the overall joint policy improvement.
In this paper, we aim to combine the merits of the existing single rollout and sequential policy update schemes. Firstly, we show that naive sequential update algorithms with a single rollout can lose the monotonic improvement guarantee of PPO for a single agent's policy. To tackle this problem, we propose surrogate objective with novel off-policy correction method, preceding-aye aggnnt off- policy correction (PreOPC), which retains the monotonic improvement guarantee on both the joint policy and each agent's policy. Then we further show that the joint monotonic bound built on the single agent bound is tighter than those of other simultaneous update algorithms and is tightened during updating the agents at stage] This leads to agent-by-ggent Policy Optimization (A2PO), a novel sequential update algorithm with single rollout scheme (Fig. [Tp). Further, we study the significance of the agent update order and extend the theory of non-stationarity to the sequential update scheme. We test A2PO on four popular cooperative multi-agent benchmarks: StarCraftlI, multi-agent MuJoCo, multi-agent particle environment, and Google Research Football full game scenarios. On all benchmark tasks, A2PO consistently outperforms strong baselines with a large margin in both performance and sample efficiency and shows an advantage in encouraging inter- agent coordination. To sum up, the main contributions of this work are as follows:
Monotonic improvement bound. We prove that the guarantees of monotonic improvement on each agent's 'ss policy could be retained under the single rollout scheme with the off-policy correction method PreOPC we proposed. We further prove that the monotonic bound on the joint policy achieved given theoretical guarantees of each agent is the tightest among single rollout algorithms, yielding effective policy optimization.
2. A2PO algorithm. We propose A2PO, the first agent-by- by-gent sequential update algorithm that retains the monotonic policy improvement on both each agent's policy and the joint policy and does not require multiple rollouts when performing policy improvement.
3. Agent update order. We further investigate the connections between the sequential policy up- date scheme, the agent update order, and the non-stationarity problem, which motivates two novel methods: a semi-greedy agent selection rule for optimization acceleration and an adaptive clip- ping parameter method for alleviating the non- non-stationarity problem.
2 RELATED WORKS
Trust Region Policy Optimization (TRPO) (Schulman al. 2015) and Proximal Policy Optimiza- tion (PPO) (Schulman et al., 2017 are popular trust region algorithms with strong performances,
benefiting from the guarantee of monotonic policy improvement (Kakade & LLngford 2002).
Sev-
eral recent works delve deeper into understanding these methods (Wang et al.] |019 Liu et al.
2019
Wang et al., 2020). In the multi-agent scenarios, de Witt et al. (2020) and Papoudakis et al.
2020
empirically studied the performance of Independent PPO in multi-agent tasks. Yu et al. (022)
conducted a comprehensive benchmark and analyzed the factor influential to the performance of Multi-agent PPO (MAPPO), variant of PPO with centralized critics, Coordinate PPO (CoPPO) (Wu et 202T) integrates the value decomposition (Sunchag et al. 2017) and approximately per- forms joint policy improvement with monotonic improvement. Several further trials to implement trust region methods are discussed in Wen et al. (202T): [i & He (2020;; Sun et al. (202)); Ye et al.) (002)). However, these MARL algorithms suffer from the non-stationarity problem as they update agents simultaneously. The environment dynamic changes from one agent's perspective as others also change their policies. Consequently, agents suffer from the high variance of gradients and quire more samples for convergence (Hernandez-Leal et al. 2017). To alleviate the -tt-stationarity problem. Multi-Agent Mirror descent policy algorithm with Trust region decomposition (MAMT) (Li et al. 2022b) factorizes the trust regions of the joint policy and constructs the connections among the factorized trust regions, approximately constraining the diversity of joint policy.
We define stage as period during which all the agents have heen updated once (Fig.
2

---

Published as a conference paper at ICLR 2023
Rollout and Policy Iteration for Single Agent (RPISA) (Bertsekas 2021) and Heterogeneous PPO (HAPPO) (Kuba et al. 2022) consider the sequential update scheme. RPISA suffers from sample inefficiency as it requires times of rollout for agents to complete their policies update. Addi- tionally, their work lacks practical algorithm for complex tasks. In contrast, we propose a practical algorithm A2PO that updates all agents using the same samples from single rollout. HAPPO is derived from the advantage decomposition lemma, proposed as Lemma in Kuba et al.) (2022). does not consider the distribution shift caused by preceding agents, and has no monotonic pol- icy improvement guarantee for each agent's policy. While A2PO is derived without decomposing the advantage, and has guarantee of monotonic improvement for each agent's policy. We further discuss other MARL methods in Appx. C
TRUST REGION METHOD IN SEQUENTIAL POLICY UPDATE SCHEME
3.1 MARL PROBLEM FORMULATION
We consider formulating the sequential decision-making problem in multi-agent scenarios as de- centralized Markov decision process (DEC-MDP) (Bernstein al. 2002). An n-agent DEC-MDP can be formalized as a tuple (S, heA. T.T.). where N = ....., n) is the set of agents, S the state space. A'' is the action space of agent i, and A= A' x x n the joint action space. r S A + I is the reward function, and T SSx Ax [0.1] is the dynamics function denoting the transition probability. 7 E [0. 1) t, each agent takes action oj from its policy n' (-1st), simultaneously according to the state St, forming the joint action a, = -(at.... . of and the joint policy TT-[st) = π x .... X π²" The joint policy of these agents induces normalized discounted state visitation distribution dt,, where d= (s) = (1 - 7) Ei= 7 Pr(s; = s/m) and Pr(-IT)= S - [0, [] is the probability func- tion under æ. then define the value function (*()) = (T EE 7'r(se, at)]s0 = and the advantage function A (s, a) r(s, a) + " (VT((')) V*(s), where {(50, ao), ($1, .......) denotes one sampled trajectory. The agents maximize their expected return, denoted as: π = argmax J(T) = argmax, (E mr) - 7'r(st, ax)]
reward discount factor.
time step
3.2 MONOTONIC IMPROVEMENT SEQUENTIAL POLICY UPDATE SCHEME
., n, without loss of generality. We define as We assume agents are updated in the order 1, 2, .., the joint base policy from which the agents are updated at stage, et = {I...., - as the set of preceding agents updated before agent i, and æ as the updated policy of agent We denote the joint policy composed of updated policies of agents in the set e', the updated policy of agent i and base policies of other agents as म' # x... x 7 x m1+1, x... n", and define - π and A general sequential update scheme is shown as follows, where L.4-11 ( is the surrogate objective for agent i:
A
# max, C.
maX 1
π
π
-
म.
Update x
Update x
We wish our sequential update scheme retains the desired monotonic improvement guarantee while improving the sample efficiency. Before going to our method, we first discuss why naively up- dating agents sequentially with the same rollout samples will fail in monotonic improvement for each agent. Since agent i updates its policy from #' intuitive surrogate objective (Schul- man et al. 2015) used by agent could be formulated as _ = J(+' + On (f'), where [A"(AA( On - ((s.a)><dd + [A (s, a)] and the superscript I means 'Intuitive'. The expected re-
turn, however, is not guaranteed to improve with such a surrogate objective, as elaborated in the following proposition.
For agent i, let E max (s, a Daw (T')) Vj E (e'U(i)) {i)), where Drv (pllq) is the total variation distance between distributions p and q and we define D (T| max, Drv (TT(((((()))))))))))) (+)(s))))(((())))))))))))))))))) then we have:
Proposition 1
Uncontrollbble
3
2
2e Σ jEe' ạ
Djee
[( - C 2ear T-
= (1)
1 1- 1- 111- ΣjE(e(u(A)) 0²)
1
The proof can be found in Appx. A.3
3

---

Published as a conference paper at ICLR 2023
Remark. From Eq. 1 and the definition of C we know J(*') J( -x((t') Bi. Thus J > J when Oz > B8 which can he satisfied by constraining 8f and op- timizing (r However, in 8/ the term 2e Djjet a² /(1 7), is uncontrollable by agent i. Consequently, the upper bound 8/ may be large and the expected performance I(+') may not be improved after optimizing (++')) when (#*)) < 3 even if a' is well constrained. Although one can still prove monotonic guarantee for the joint policy by summing Eq. ① for all the agents, we will show that the monotonic improvement on every single agent, if guaranteed, brings tighter monotonic bound on the joint policy and incrementally tightens the monotonic bound on the joint policy when updating agents during stage. Uncontrollable terms also appear when similarly ana- lyzing HAPPO and cause the loss of monotonic improvement for single agen
3.3 PRECEDING-AGENT OFF-POLICY CORRECTION
The uncontrollable term in Prop. | is caused by one ignoring how the updating of its preceding agents' policies influences its advantage function. We investigate reducing the uncontrollable term in policy evaluation. Since agent is updated from A'-1, the advantage function A should be used in agent i's surrogate objective rather than A=, However, A= is impractical to estimate using samples collected under π due to the off-policyness (Munos et al. 2016) of these samples. Nevertheless, we can approximate A# 4 by correcting the discrepancy between s'-1 and π at each time step (Harutyunyan et al.) 20166). To retain the monotonic improvement properties, we propose preceding gagett off policy correction (PreOPC), which approximates A# using samples collected under π by correcting the state probability at each step with truncated product weights:
Amin (1.0, &' (ar,(( ))(+)))))+)))))))))))))))))))) 3=1
A (5t, az) az) d
(2)
I (8+g))
121
where 8, r(s, (s++1) V(s)) is the temporal difference for V(sg), À is a parameter controlling the bias and variance, as used in Schulman et al. (2016). min(1.0, #' "(ar ((at)l)a))) Vj *(ar4)]
{1....,k} k} are truncated importance sampling weights, approximating the probability of 8 at time step & under #1-1 The derivation of Eq. (2) can be found in Appx.IA.. A.8
With PreOPC, the
surrogate objective of agent becomes L (++) = J(*'-1)+ + I-7 -_ (a.a)) * [AT
(s, a)]
and we summarize the surrogate objective of updating all agents as follows:
(x) - [
Σ (as.))((r L:)AA "(s,a)).
Note that Eq. 3 takes the sum of expectations of the global advantage function approximated under different joint policies, different from the advantage decomposition lemma in Kuba et al. (2022) which decomposes the global advantage function into local ones.
We can now prove that the monotonic policy improvement guarantee of both updating one agent's policy and updating the joint policy is retained by using Eq. (3) as the surrogate objective. The detailed proofs can be found in Appx. A.4
Theorem (Single Agent Monotonic Bound) For agent i, let ét = max,,a AA (s, a)). g² =
max,,a a A as
A
a)), a DTV (T ((5) Vj (e' then we have:
[J(#') L (
(+')
4e'a'
1-9 - 1- Eje(e((n)
w0) 1-7
476¹
(at Σ a²) g²
(4)
7/2 jE(CiU(())
1-7
The single agent monotonic bound depends on e', E and a' and the total variation distances of preceding agents. Unlike Eq. ( we can effectively constrain the monotonic bound by control- ling at since 5 decreases as agent i updating its value function (Munos et al., 2016) and does not
2 Moor discussions about why HAPPO fails to guarantee monotonic improvement for single agent's policy be found in Appx. A.6
4

---

Published as a conference paper at ICLR 2023
Table 1: Comparisons of trust region MARL algorithms. The proofs of the monotonic bounds can be found in Appx. A Note that we also provide the monotonic bound of RPISA-PPO, which implements RPISA with PPO as the base algorithm. We separate RPISA-PPO from other methods as it has low sample efficiency and thus does not constitute fair comparison.
Algorithm
Rollout
Update
Sample Efficiency
Monotonic Round
RPISA-PPO
Multiple
Sequential
Low
4c Ei
1-00-
Single Agent: 4ea (
(T-y T-10-o7))
MАPPO CoPPO
Single Single
Simultancous
High
4e -
Simultancous
High
4e 2 a
I-
4e > a' 1-111-
НАРPО
Single
Sequential
High
Single Agent: Guarantee
4e >n> ( T-7(1- Eettttee
A2PO (ours)
Single
Sequential
Hlgh
Single Agent: 4c'c0(1
lead to an unsatisfiable bound when a² is well constrained, providing the guarantee for monotonic improvement when updating single agent. Given the above bound, we can prove the monotonic improvement of the joint policy.
Theorem (Joint Monotonic Bound) For each agent N, let e² max, a A "(s, a)l
a² = DTV ( || 5² = max,,a AA (8, - A# (s, and e = max; 6', then we have:
[J( (+) < 4e
a 1=1 1-7
1 1->(1 EjE(eUED) ad) + 1-7
47e (1 7)
Σ
a') E
(5)
1-7
jE(e'Uf()
Eq. (5) suggests condition for monotonic improvement of the joint policy, similar that in the remark under Prop. [ We further prove that the joint monotonic bound is incrementally tight- ened when performing the policy optimization agent-by-agent during a stage due to the single agent monotonic bound, i.e., the condition for improving T(T) is relaxed and more likely to be satis- We present the monotonic bounds of other algorithms Eq. (5) achieves the tightest bound
fied. The details can be found in Appx.
A.5
1y compared to other single rollout algorithms, with ş Vi E N small enough. The assumption about ç is valid since preceding-agent off-policy correction is contraction operator, which is a corollary of Theorem in Munos et al.) (2016). A tighter bound improves expected performance by optimizing the surrogate objective more effectively (Li et al. 2022a).
in Tab. Since
"I-(1-> -== aF)
AGENT-BY-AGENT POLICY OPTIMIZATION
We first give a practical implementation for optimizing the surrogate objective 9 ( When up- dating agent i, the monotonic bound in Eq. 4 consists of the total variation distances related the preceding agents and agent i, i.c., a (j)( a². It suggests that we can control the monotonic bound by controlling total variation distances a Vj (e)(())) to effectively improve the expected performance. We consider applying the clipping mechanism to control the total variation distances ad Vj E (e*U (i)) (Queeney al. 2021
Sun et al. 2022). In the surrogate objective agent
(s, as), T(*--1) has no dependence to agent ie.. J(A--))+ I- ((..a) m) Ussc m7 A A
while the joint policy ratio the clipping mechanism. We further consider reducing the instability in estimating agent i's policy gradient by clipping the joint policy ratio preceding agents first, with a narrower clipping range Wu et al. 2021). Thus we apply the clipping mechanism on the joint policy ratio twice: once the joint policy ratio of preceding agents and once on the policy ratio of agent Finally, the practical objective for updating agent i becomes:
7' TTe af in the advantage estimation is appropriate for applying
L (**) (((s,))=aa m) [min (1(s, A= * clip (I(s,a), (4
(6)
5

---

Published as a conference paper at ICLR 2023
(s) where ((s, a) = <aaaa ((, a)) and g(s, a) = clip( hee (a'la)
Ie n (a2la) 1 + 5) The clipping parameter
é is selected as ç C(c,t), i), where is the base clipping parameter and C(:,-) -) is the clipping param- eter adapting function. We summarize our proposed Agent-by pent-by-agent Policy Optimization (A2PO) in
Alg. [ Note that in Line 6 the agent for the next update iteration is selected according the agent selection rule R()).
Algorithm 1: Agent-by-agent Policy Optimization (A2PO)
Initialize the joint policy πTu for iteration m = 1, . do
{mo ................................ m and the global value function V.
Collect data using mm (---1 , m for Order k ,,...., do
Select an agent according to the selection rule as = R(k.).
Policy ni = T m preceding agents e {R(1), R(k 1)}.
-EEN-e Joint policy 4' = {Ti T =m=-1
Compute the advantage approximation as A "(s, a) via Eq. 2
Compute the value target v(s))= A (s,a) + Vss). for P epochs do
10
Tim = arg max, - as in Eq. V = arg mily Bx (10(5) (1)
11
Eq. (6 approximates the surrogate objective of single agent. We remark that the monotonic im- provement guarantee of a single agent reveals how the update of a single agent affects the overall objective. We will further discuss R(-) and C(.-)) from the perspective of how to benefit the opti- mization of the overall surrogate objective by coordinating the policy updates of each agent.
Semi-greedy Agent Selection Rule. With the monotonic policy improvement guarantee the joint policy, as shown in Thm. 2 we can effectively improve the expected performance J I(T) by opti- mizing the surrogate objective of all agents Gr (T) [(T) + Σ Lx: (#'). Since the policies except T' are fixed when maximizing C+ ( we recogmize maximizing Σi= 2 ( as performing a block coordinate ascent, i.c., iteratively seeking to update block of chosen coordi- nates (agents) while other blocks (agents) are fixed. As special case of the coordinate selection rule, the agent selection rule becomes crucial for convergence. On the one hand, intuitively, up- dating agent with bigger absolute value of the advantage function contributes more to optimizing G. ( Inspired by the Gauss-Southwell rule (Gordon & Tibshirani] 2015), we propose the greedy agent selection rule, under which an agent with bigger absolute value of the expected advan- tage function is updated with higher priority. We will verify that the agents with small absolute values of the advantage function also benefit from the greedy selelction rule in Appx. B.2.3 On the other hand, purely greedy selection may lead to early convergence which harms the perfor- mance. Therefore, we introduce randomness into the agent selection rule to avoid converging too early (Lu al. 2018). Combining the merits, we propose the semi-greedy agent selection rule as
RR(k) = arg (aX-) Bz,ar ||A* R(k-1) []
k 0
k2 1' where (R(1), R(k 1)} and
RR(k) ~ U(N is a uniform distribution. We verify that the semi-greedy agent selection rule contributes to the performance of A2PO in Sec. 5.2
Adaptive Clipping Parameter. We improve the sample efficiency by updating all agents using the samples collected under the base joint policy However, when updating agent i by optimiz- ing - ((.a)))(dd "> [A (s, a)), the expectation of advantage function is estimated using the states sampled under π instead of - which reintroduces the non-stationarity since agent can not perceive the change of the preceding agents. With the non-stationarity modeled by the state tran- sition shift (Sun et al. 2022). we define the state transition shift encountered when updating agent i as the following property.
(d'(s) = Ea(T( [T a) (a(s) - т T [a]s))] The state transition shift has

---

Published as a conference paper at ICLR 2023
Proposition 2 The state transition shift 47
".. " (6'18) can be decomposed as follows. "'...."'-1.. ar p0..n
Prop. shows that the total state transition shift encountered by agent can be decomposed into the sum of state transition shift caused by each agent whose policy has been updated. Shifts caused by agents with higher priorities will be encountered by more following agents and thus contribute more to the non-stationarity problem. Recall that the state transition shift effectively measures the total variation distance between policies. Therefore, in order to reduce the non-stationarity brought by the agents' policy updates, we can adaptively clip each agent's 's surrogate objective according their update priorities. We propose a simple yet effective method, named adaptive clipping parameter, to adjust the clipping parameters according to the updating order: C(c, k) c. Ce + c. where is hyper-parameter. We demonstrate how the agents with higher prionities affect the following agents in Fig. 2 Under the clipping mechanism, the influence of the agents with higher priority could be reflected in the clipping ranges of the joint policy ratio. The policy changes of the preceding agents may constrain the following agents to optimize the surrogate objective within insufficient clipping ranges, as shown on the left side of Fig. 2
c.) k/n,
The right side of Fig. 2 demonstrates that the adaptive clipping parameter method leads to balanced and sufficient clipping ranges.
Agent
Agent 3
Agent
Agent 2
Agent
Agent
Rg
The clipping ranges of three agents. The surface 01 + 02 + 03 = demonstrates the policy space of three discrete actions. The agents are updated in the order of 2, 3, 1. The areas in gray/pink are the clipping ranges with/without considering the joint policy ratio of preceding agents. Left: The agents have the same clipping parameters. The clipping range of agent 1 is insufficient due to the large variation in the policies of agent and agent 3. Right: The clipping ranges are more balanced and sufficient with the adaptive clipping parameter method.
Figure 2:
5 EXPERIMENTS
In this section, we empirically evaluate and analyze A2PO in the widely adopted cooperative multi- agent benchmarks, including the StarCraftll Multi-agent Challenge (SMAC) (Samvelyan et al.) 2019), Multi-agent MuJoCo (MA-MuloCo) (de Witt et al., (020), Multi-agent Particle Environ- ment (MPE) (Lowe et al. 2017 and more challenging Google Research Football (GRF) full-game scenarios (Kurach al. 2020 Experimental results demonstrate that 1) A2PO achieves perfor-
mance and efficiency superior to those of state-of-the-art MARI. Trust Region methods, 2) A2PO has strength encouraging coordination behaviors to complete complex cooperative tasks, and 3) the PreOPC, the semi-greedy agent selection rule, and the adaptive clipping parameter methods significantly contribute to the performance improvement.
We compare A2PO with advanced MARL trust-region methods: MAPPO (Yu et al. 2022). CoPPO (Wu et al.] 202T) and HAPPO (Kuba et al.) (022). We implement all the algorithms as parameter sharing in SMAC and MPF, and as parameter-indeepeddett in MA-MuJoCo and GRF, according to the homogeneity and heterogeneity of agents. We divide the agents into blocks for tasks with numer- ous agents to control the training time of A2PO comparable to other algorithms. Full experimental
details can be found in Appx. B
5.1 PERFORMANCE AND EFFICIENCY
We evaluate the algorithms in 9 maps of SMAC with various difficulties, 14 tasks of 6 scenarios in
MA-MuloCo, and the 5-vs-5 and 11-vs-11 full game scenarios GRF Results in Tab. 2 Fig. 3 and
Fig. show that A2PO consistently outperforms the baselines and achieves higher sample efficiency in all benchmarks. More results and the experimental setups can be found in Appx. B.2
We evaluate A2PO fully cooperative and general-sum MPE tasks respectively, showing the potential of extending A2PO to general-sum games, see Appx. B.2.3 for full results.
*Code is available at attttps: httpp::///aoooooooao ymous 4open. www.eceeenncccceocoo ence/r/A2ee T/A2P0

---

Published as a conference paper at ICLR 2023
StarCraftII Multi-agent Challenge (SMAC). As shown in Tab. A2PO achieves (nearly) 100% win rates in 6 out of maps and significantly outperforms other baselines in most maps. In Tab. 2 additionally compare the performance with that of Qmix (Rashid et al., 2018), well known baseline in SMAC. We also observe that CoPPO and A2PO have better stability as they consider clipping joint policy ratios.
Table 2: Median win rates and standard deviations on SMAC tasks.
Map
Difficulty MAPPO w/ PS
CoPPO w/ PS
HAPPO w/ PS
A2PO w/ PS
Qmix w/ PS
MMM
Easy
96.910.88)
96.91.25)
95.3(248)
100
95.3(s.)
3s5z
Hard
84.4
92.2(2.35)
92.2(1.7))
98.4(184
88.3(299
5m_vs_6m
Hard
84.4(2.77)
84.4(2.1)
87.5(2.51)
90.6(3.06)
75.8
8m_vs_9m
Hard
84.4(2.39)
84,4(2.04
96.90377
100(1.4
92.2(2.0)
10m_vs_1 1m
Hard
93.8(18.7)
96,9226)
98.4(2.9)
100(a.521)
95.3(Lm)
6h vs 87
Super Hard 87.5(1.53)
90.60.765)
87.5u149
90.6(1.32)
9.4(2.0
3s57. vs. 3s6z
Super Hard 82.8(19.2)
84,4c29)
37.5(13.2)
93.8(19.8)
82.8(5.))
MMM2
Super Hard 90.6/8889
90.6c6.59
51.6/9.01
98.4(..25)
87.5(20)
27m_vs 27m.vs.30m 30m
Super Hard 93.8(3.75)
93.8r2.)
90.6(477)
100(1.5)
39.1e8)
Overall
88.7(6.6)
90.5(2.77
81.9(467)
96.9(3.41)
74.0tsx3)
Multi-agent MuJoCo environment (MA-MuJoCo). We investigate whether A2PO can scale to more complex continuous control -agett tasks in MA-MuJoCo. We calculate the normalized telurn mininum return
score maximum return minimum return over all the 14 tasks in the left of Fig. 3 We also present part of
results in the right of Fig. 3 where the control complexity and observation dimension, depending on
the number of the robot's 's joints, increases from left to right. We observe that A2PO generally shows
an increasing advantage over the baselines with increasing task complexity.
Nermalasd Tiala
Astant Held
WelkertMMett Iel
Himnonneorr 1he
5000
0033
00.00
SAARO
Notteata Store
F1 Tranddo Derim
XSPD
SLLPP1N-/1P Cuant
2300
LEKK
07
87
11
02
7707
07100
11.00
3.55
1.50
0733
13:55
Skyps
Figure 3: Experiments in MA-MuJoCo. Left: Normalized scores all the 14 tasks. Right: Com- parisons of averaged return on selected tasks. The number of robot joints increases from left to right.
Google Research Football (GRF). We evaluate A2PO in GRF full-game scenarios, where agents have difficulty discovering complex coordination behaviors. A2PO obtains nearly 100% win rate in the 5-vs-5 scenario. In both scenarios, we attribute the performance gain of A2PO to the learned coordination behavior. We analyze the experiments in GRF verify that A2PO encourages agents to learn coordination behaviors in complex tasks. In Tab. 3 an 'Assist' attributed to the player who passes the ball to the teammate that makes a score, 'Pass" is counted when the passing-and- receiving process is finished, Pass Rate" is the proportion of success passes over the pass attempts. A2PO have an advantage in passing-an and-aadddeeeee -ecceviinn coordination, leading more assists and scores.
Foothall c
Bootbell
Table 3: Learned behaviors the Google Re- search Football 5-vs-5 scenario. Bigger values are better except fot the 'Lost' metric.
Dtate
100
Metric
MAPPO
CoPPO
HAPPO
A2PO
0.8
0.0-
Assist
0.04maz
0.19
0.07
0.56
Goal
1.95am
4.42
2.68
9.01
Sptrdio
Epieddor
XAPPO
Lost
0.49mmm
0.74m33
1.04mm
0.78
Pass
1.52m.13)
3.44n
4m03
6.42
Figure 4: Averaged win rate on the Google Re- search Football full-game scenarios.
Pass Rate
19.3000
35.0pen
48.9
67.1amm
8

---

Published as a conference paper at ICLR 2023
5.2 ABLATION STUDY
This section studies how PreOPC, the semi-greedy agent selection rule, and the adaptive clipping parameter affect the performance. Full ablation details can be found in Appx. B.2.5
PreOPC. Fig. 5 shows the effects of utilizing off-policy correction in two cases: 1) Correc- tion on all agents' policies for simultaneous up- date algorithms, i.c., MAPPO w/ V-trace (Es- peholt et al.) 2018) and CoPPO w/ V-trace, and 2) Correction on the preceding agents' policies for sequential update algorithms, i.e., HAPPO w/ PreOC and A2PO. V-trace brings no general improvement to MAPPO and CoPPO, while PreOPC significantly improves the sequential update cases. PreOPC improves the perfor- mance of HАРPO significantly, while A2PO still outperforms HAPPO w/ PreOPC. The per- formance gap lies in that A2PO clips the joint policy ratios, which matches the monotonic bound in Thm. T The results verify that A2PO reaches outperforms the asymptotic performance of RPISA-PPE using an approximated advantage function and updating all the agents with the same rollout samples. Additionally, preceding- agentt off- policy correction does not increase the sensitivity of the hyper-parameter X, shown in Appx. B.2.5
Hemaneiee ilee? 98
MMMP
6000
2000
10:30
0033
0:40
0700
0.20
13:00
OUERO
AIRO
HAPPO vn/ Viiao
CUEPO Vicaac
BAPP0 PhoOPC
AIPO
Figure 5: Ablation experiments on preceding- agent off off-policy correction.
Agent Selection Rule. We provide comparisons of different agent selection rules in Fig. G The 'Cyclic' rule means select agents in the order 1..... n. and other rules have been introduced in sec. 4 The semi-greede rule considers the optimization acceleration and the performance balance among agents and thus performs the best in all tasks.
Adaptive Clipping Parameter. We propose the adaptive clipping parameter method for balanced and sufficient clipping ranges of agents. As shown in Fig. 7 the adaptive clipping parameter con- tributes to the performance gain of A2PO.
Fimonnsev222 d/s
MINIE
Eunoceétiv g6
5000
1000
4:00
3.25
1330
$3.00
310
17:00
311
11:0
Stege
Stage
X32
Stepr
BAPPO-CNEi
[IAPPN)
AAPO
Adge
MAPPO
OuPPO
HAPPO
AdPo
Figure 6: Ablation experiments on the agent se- lection rules.
Figure 7: Ablation experiments on the adaptive clipping parameter method.
CONCLUSION
In this paper, we investigate the potential of the sequential update scheme in coordination tasks. We introduce A2PO, a sequential algorithm using a single rollout at a stage, which guarantees monotonic improvement on both the joint policy and each agent's policy. We also justify that the monotonic bound achieved by A2PO is the tightest among existing trust region MARL algorithms under single rollout scheme. Furthermore, A2PO integrates the proposed semi-greedy agent selection rule and adaptive clipping parameter method. Experiments in various benchmarks demonstrate that A2PO consistently outperforms state-of-the methods in performance and sample efficiency and encour- ages coordination behaviors for completing complex tasks. For future work, we plan to analyze the theoretical underpinnings of the agent selection rules and study the learnable methods to select agents and clipping parameters.
9

---

Published as a conference paper at ICLR 2023
Acknowledgements. The SJTU team is partially supported by "New Generation of AI 2030" Ma- jor Project (2018AA00000900), the Shanghai Municipal Science and Technology Major Project (2011SHZDZX0102) the Shanghai Sailing Program (21YF142)900), the National Natural Science Foundation of China (62076161, 62106141). Xihuai Wang and Ziyu Wan are supported by Wu Wen Jun Honorary Scholarship, Al Institute, Shanghai Jiao Tong University. We thank Yan Song and He Jiang for their help in the football experiments.
Ethics Statement. Our method and algorithm do not involve any adversarial attack, and will not endanger human security. All our experiments are performed in the simulation environment, which does not involve ethical and fair issues.
Reproducibility Statement. The source code of this paper is available at https://
anonymous. 4open. science/r/AZeO We provide proofs in appx. AA including the proofs of intuitive sequential update, monotonic policy improvement of A2PO, incrementally tightened bound of A2PO and monotonic policy improvement of MAPPO, CoPPO and HАPPO. We specify all the experiments implementation details, the experiments setup, and the additional results in the appx. B The related works of coordinate descent are shown in appx. D
REFERENCES
Stefano V. Albrecht and Peter Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. Artif. Intell., 258:66 95, 2018. doi: 10. 10.11066j.artimt.2200 2018.01..02
URL httthhtts///oot /ttp::://do..o http://001...01111.11111/1.1/1/. arrt 2018 01.00.1.002
Agarwal Alekh, Jiang Nan, M. Kakade Sham, and Sun Wen. Reinforcement Learning: Theory and qithub.io/
Algorithms, 2022. URL
Marein Andrychowiez. Anton Raichuk, Piotr Stanezyk, Manu Orsini, Sertan Girgin, Raphaël Marinier, Léonard Hussenot, Matthieu Geist, Olivier Pietquin, Marcin Michalski. Sylvain Gelly, and Olivier Bachem. What matters in on-policy reinforcement learning? large-scale empirical study. CoRR, abs/2006.05990, 2020. URL https::/aaxii...oo org. abs///b////// 2006 05990
Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of markov decision processes. Math. Oper. Res., 27(4):819-840, 2002. doi: 10. 10.1228//mo: 2w..........997777 httLhttss////o..ooo
Dimitri Bertsekas. Multiagent Reinforcement Learning: Rollout and Policy Iteration. JEEE/CAA
Journal of Automatica Sinica, 8(2):249-272, February 2021. ISSN 2329-9266, 2329-9274. doi:
10. 11110009/.2221.... 1003814
Christian Schröder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip H. S. Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? CoRR, abs/2011.09533 2020. URL
2011 09533
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IM- PALA: scalable distributed deep-rl with importance weighted actor-learner architectures. In Jen- nifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmüssann Stockholm, Sweden, July 10-15, 2018, vol- ume 80 of Proceedings of Machine Learning Research, pp. 1406-1415 PMLR, 2018. URL httt::/prroceddi ngs. mm pwwps//esseee... v00 https///////sppo/oee// www.hoppelhlttto httmm
Ian M. Gemp, Charlie Chen, and Brian McWilliams. The generalized eingralizeedeegeevvalue problem as a nash equilibrium. CoRR, abbs/2200.04999, 2022. doi: 10.44550kaxXi.220644993.. URL hctps:
//doi Pebi.org//0.. 48544 / www.v. 2206. 04993
Tobias Glasmachers and Ürün Dogan. Accelerated coordinate descent with adaptive coordinate frequencies. In Cheng Soon Ong and Tu Bao Ho (eds.), Asian Conference on Machine Learning, ACML 2013, Canberra, ACT, Australia, November 13-15, 2013, volume 29 of JMLR Workshop and Conference Proceedings, pp. 72-86. JMLR.org. 2013. URL http: http:///cceeeing... mlr. mlr.prress/v29/Geeee assps////////aaaaeeccceecc r 1..3.
10

---

Published as a conference paper at ICLR 2023
Geoff Gordon and Ryan Tibshirani. Coordinate descent. Optimization, 10(36):725, 2015.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policcy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018.
Anna Harutyunyan, Mare G. Bellemare, Tom Stepleton, and Rémi Munos. Q(A) with off-policy cor- rections. In Ronald Ortner. Hans Ulrich Simon, and Sandra Zilles (eds.), Algorithmic Learning Theory 27th International Conference, ALT 2016. Bari, Italy. October 19-21, 2016, Proceed- ings, volume 9925 of Lecture Notes in Computer Science, pp. 305 2016. doi: 10.1007/
978-3-319-46379- 21. .1
URL
21
Qiang He and Xinwen Hou. Wd3: Taming the estimation bias in deep reinforcement learning. In 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAT), pp. 391-398, 2020. doi: 10.109ICTA115040220000000
Pablo Hernandez-Leal. Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A survey of learning in multiagent environments: Dealing with non-stationariiy. CoRR, abs//777.009883 2017. TRLLhttp: htttt:://axxxi.orrr/aaaaeeee//
C9183
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Claude Sammut and Achim G. Hoffmann (eds.), Machine Learning, Proceedings of the Nine- teenth International Conference (ICML 2002), University of New South Wales, Sydney, Australia, July 8-12, 2002, pp. 267-274. Morgan Kaufmann, 2002.
Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. In International Conference Learning Representations, 2022. URL/Lttps:: net forrmm?
EddEccGERRE E-GGGGGGGTTXxUU
Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marein Michalski, Olivier Bousquet, and Sylvain Gelly. Google research football: A novel reinforcement learning environment. In AAAI 2020, pp. 4501-4510. AAAI Press, 2020. URL https:: aaai. org. wtrg/indexx php phppAAAI/ /AAI/ article/view/58r.
Chenghao Li, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjie Zhang, Cel- ebrating Diversity in Shared Multi-Agent Reinforcement Learning. Advances in Neural Infor- mation Processing Systems, November 2021.
Hepeng Li and Haibo He. Multi-agent trust region policy optimization. CoRR, abs/2010,07916. 2020.
Hepeng Li, Nicholas Clavette, and Haibo He. An analytical update rule for general policy optimiza- tion. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICMI. 2022, 17-23 July 2022, Bal- fimore, Maryland, USA, volume 162 of Proceedings Machine Learning Research, pp. 12696- 12716. PMLR, 2022a. URL https::///// http:::::///ccceeciissscoo
press vlv221262v 62/ 1tt//.122... html
Wenhao Li, Xiangfeng Wang, Bo Jin, Junjie Sheng, and Hongyuan Zha. Dealing with non- stationarity in MARL via trust-region decomposition. In International Conference on Learning Representations, 2022b. URL htttps:::///oeneeee
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy op- timization attains globally optimal policy. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Achéé-Buc, Emily B. Fox, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pp. 10564-10575, 10575, 2019. URL http:::/pppcpeeeeeaaaeaa http:////ppreeeee.nn.....oooooo. www.:ip......rr.......m haat:/22007221333117778881822221
html

---

Published as a conference paper at ICLR 2023
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed coperative-competiiiy environments. In Isabelle Guyon, Ulrke von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neu- ral Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp- 6379-6390, 2017. URL https::pproceedgggssss neurips http://eeeee.esecceae////////11 cccppaerr/211/haah. 375333 a www6fe06c1991aaaeeee.aa Abstrarat html
Haihao Lu, Robert M. Freund, and Vahab S. Mirrokni. Accelerating greedy coordinate descent methods. In Jennifer G. Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10- 15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 3263-3272. PMLR, 2018.
mlr wtt.://inn..............eeee...e Tinesss/v0//II 1tt8/.htbblllllll
Remi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and Efficient Off- Policy Reinforcement Learning. In Advances in Neural Information Processing Systems, vol- ume 29, Curran Associates, Inc., 2016.
Georgios Papoudakis, Filippos
Christianos, Lukas Schäfer, and Stefano V. Albrecht. Comparative evaluation of multi-agent deep reinforcement learning algorithms. CoRR, abs/2006.07869, 2020.
URL https: /tttpp:///xxii.. http/axvvvvo// wwtp://ggggbbb./booo..
07869
Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierre-Alexande Kamienny, Philip Torr, Wendelin Bochmer, and Shimon Whiteson. Facmac: Factored multi-agent centralised policy gra- dients. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 12208-12221. Curran As- sociates, Inc., 2021. URLLhttps::/pproeeeediii neur httpcc/aapppee/////eee.e Papeaaaarr..aaa1llaappaaeeeerr. pdf
James Queeney. Yannis Paschalidis, and Christos G Cassandras. Generalized proximal policy op- timization with sample reuse. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 11909-11919. Curran Associates, Inc., 2021. URKLattpps//prrcediinoe neuripss wwwellbbeeeaappeeeeeeeee Paper.pdr
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 Schröder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob N. Foerster, and Shimon White- son. The starcraft multi-agent challenge. In Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor (eds.), Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada, May 13-17, 2019, pp- 2186-2188. International Foundation for Autonomous Agents and Multiagent Systems, 2019. URL http:///ll. acm. www.oorggaatteeooooooooo citt i oo. faffmmmd=3332055
John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust re- gion policy optimization. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, vol- ume 37 of JMLR Workshop and Conference Proceedings, pp. 1889-1897. 1889-1897.JMI...oorg 2015. URL http::/ httt:://proceedii ngs ......m... mm wwwps/eevvvv v37/ schu man 5t.ml
John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High-
dimensional continuous control using generalized advantage estimation. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings. 2016. URL. http:
7/arxiv. org abs /wt.//16...0 02438
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1 00347,,77 2017. URL http::/arz .rgg abs/ 1707. 06347
12

---

Published as a conference paper at ICLR 2023
Hao-Jun Michael Shi, Shenyinying Tu, Yangyang Xu, and Wotao Yin. A Primer Coordinate Descent Algorithms. arXiv: [math, stat], January 2017.
Mingfei Sun, Sam Devlin, Katja Hofmann, and Shimon Whiteson. Monotonic Improvement Guar- antees under Non-stationarity for Decentralized PPO. arXiv:2202.00088 00082 [es], January 2022.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinícius Flores Zam- baldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Grae- pel. celeeddecompooitionn networks for cooperative multi-agent agent learning. CoRR, abs/ abs/1706.05296, 2017. /ttL:ttttt//rr/iw.rr////////////
C5296
Hossein Taheri and Christos Thrampoulidis. Decentralized Learning with Separable Data: General- ization and Fast Algorithms, September 2022.
J Terry, Benjamin Black, Nathaniel Grammel, Mario Jayakumar, Ananth Hari, Ryan Sullivan, Luis Santos, Clemens Dieffendahl, Caroline Horsch, Rodrigo Perez-Vicente, et al. Pettingzoo: Gym for multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34: 15032-15043, 2021.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference Intelligent Robots and Systems, pp. 5026-5033.
IEEE, 2012. doi: 10.1 10.1000000020001...6688
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: duplex dueling multi-agent q-learning. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. htL:tttss/// Roc.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang, Neural policy gradient methods: Global optimality and rates of convergence. In 8th International Conference on Learning Represen- fations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URI. https://openreviier
net forum? wauumiid-BBat BJ@-JJJOESS
Yuhui Wang. Hao He, and Xiaoyang Tan. Truly proximal policy optimization. In Amir Globerson and Ricardo Silva (eds.), Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine mmlr.
Learning Research, pp. 113-122. AUAI Press, 2019. URL ppess/vv11/ae wwgp1//////ggbbb.. html
Muning Wen, Jakub Grudzien Kuba, Runji Lin, Weinan Zhang, Ying Wen, Jun Wang, and Yaodong Yang. Multi-Agent Reinforcement Learning is a Sequence Modeling Problem, May 2022.
Ying Wen, Hui Chen, Yaodong Yang, Zheng Tian, Minne Li, Xu Chen, and Jun Wang. A game- theoretic approach to multi-agent trust region optimization, 2021. URL https://arxx
atg/abs/215 06828
Zifan Wu, Chao Yu, Deheng Ye, Junge Zhang, Haiyin Piao, and Hankz Hankui Zhuo Coordi- nated proximal policy optimization. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrlPS 2021, December 6-14, 2021, virtual, volume 34, pp. 26437-26448, Curran Asso- ciates, Inc., 2021. URL fttt:::://proceediee neurips cc wctppappeee222//ass.... de
wtw.::/awe.....aaaaaaa---tttttt. html
Deheng Ye, Zhao Liu, Mingfei Sun, Bei Shi, Peilin Zhao, Hao Wu, Hongsheng Yu, Shaojie Yang, Xipeng Wu, Qingwei Guo, Qiaobo Chen, Yinyuting Yin, Hao Zhang, Tengfei Shi, Liang Wang, Qiang Fu, Wei Yang, and Lanxiao Huang. Mastering complex control in MOBA games with deep reinforcement learning. In AAAI 2020, pp. 6672-6679, AAAI Press, 2020. URL https: 7/ojs. aaai. org/ index. php/ /ttp//////////////e//////1/1
Jianing Ye, Chenghao Li, Jianhao Wang, and Chongjie Zhang. Towards Global Optimality in Coop- erative MARL with Sequential Transformation, August 2022.
13

---

Published as a conference paper at ICLR 2023
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games, July 2022.
Ming Zhou, Ziyu Wan, Hanjing Wang, Muning Wen, Runzhe Wu, Ying Wen, Yaodong Yang, Weinan Zhang, and Jun Wang. Malib: A parallel framework for population-based multi-agent reinforcement learning. CoRR, abs/2106.07551, 2021. URL https: /stes://arxiv.ooo /
F106.07551
14

---

Published as a conference paper at ICLR 2023
Supplementary Material
Table of Contents
Proofs
16
A.1
Notations
16
A.2
Useful Lemmas
16
A.3
Proofs of Intuitive Sequential Update
19
Proofs Monotonic Policy Improvement A2PO
Proofs Incrementally Tightened Bound A2PO
20
A.6
Prools of Monotomic Policy Improvement MAPPO, CoPPO and HAPPO
20
A.7
Comparisons Monotonic Improvement Bounds
22
A.8
Preceding-agent Off-policy Correction
23
A.9
Why Off Off-policyness is More Serious in Sequential Update Scheme?
23
Experimental Details
24
B.1
Implementation
24
Experimental Sctup and Additional Results
24
B.3
Wall Time Analysis
32
B.4
Hyper-parameters
32
he Related Work of Other MARL Methods
34
The Related Work Coordinate Descent
15

---

Published as a conference paper at ICLR 2023
A PROOFS
A.1 NOTATIONS
We list the main notations used in Tab. 4
Table
The notations and symbols used in this paper.
Notation
Definition
The state space
N
The of agents
The number of agents The agent index The action space of agent The reward function
A
T
The transition function The discount factor The time-step The state time-step t
o
The action of agent at time-step f
The joint action at time-step /
d
The discounted state visitation distribution
The state probability function
The value function
A
The advantage function
The trajectory of episode
A of preceding agents
The set of preceding agents updated before agent i
The policy of agent
The updated policy of agent i The joint policy
The bias and variance balance parameter The joint target policy
#
The joint policy after updating agent
J(T)
The expected return performance of the joint policy π
C 1
The surrogate objective of agent
C (ft)
An intuitive surrogate objective of agent
9 (T)
The surrogate objective of all agents
The upper bound an advantage function The total variation distance function The total variation distance between 2 policies The off policy correction error of --1
Drv
The clipping parameter adaptation function
R
The agent selection function
A.2 USEFUL LEMMAS
Lemma (Multi-agent Policy Performance Difference Lemma). Given any joint policies मे and n, the difference between the performance of two joint policies can be expressed as:
1 1- B(s.a))(a
[(m) -[(T)
(s
where d= = =(1 (1-7) Eee 7' s|TT) is the normalized discounted state visitation distribution.
Proof. A corollary of the Policy Performance Difference Lemma, see Lemma 1.16 in Alekh et al. 2022
For convenience, we give some properties and definitions of coupling and the definition of a- coupled policy pair (Schulman et al. 2015) here.
TThe definition of coupling and the properties be found in any textbook containing Markov Chains.
16

---

Published as a conference paper at ICLR 2023
Definition 1 (Coupling) A coupling of two probability distributions is and is pair of random variables (X, Y) such that the marginal distribution of X is ya and the marginal distribution of Y is A coupling (X,Y) satisfies the following constraints: Pr(X = z) p(z) and Pr(Y v)
(()).
Proposition 3 For any coupling (X.Y) that Drv(ull)) S Pr(X* Y)
Proposition 4 There exists a coupling (X,Y) that Drv(ulle) Pr(X *Y).
Corollary For all 8, there exists a coupling (T (-1s); ( that Pr(a = a) 2 DTV ( [T), for a π (-1s), à ~ #-1ss)
Proof. By prop. 4 there exists a coupling (f1ss,, s.t.
1 Pr(a- a) Pr(a + a) Drv (T,, H) S DIVe (T
Corollary For all s, Drv (T((s) s Ei (+(s)l
Proof. We denote क (-1s) (-) for brevity.
(TV(T((|s)|
1
Σ
(a')
II n (a')
2 pos0
i=1
II
(aa) - x' (a')
II
(aa)
+ r (a')
II
(aa)
II (a')
2
a
i=1
1=2
1=2
1=1
n II (a')
(a'))
T
+
Σ
x (a*) -  (a')
Σ
II
2 a!
2
0 20
1=2
i=2
a²
2 Σ
II (a))
1
(a - x (a+)
2
n
n (aa))
(a'))
(1s(+((ss)
Definition 2 (a-coupled policy pair) If (πt, Ft is an a-coupled policy pair, then (a, a|s) satisfies Pr(a + als) S a for all s, and (-1s), #(1ss).
From Corollaries and 2 we know that given any joint policy pair æ and म, select a D (TT(- T-(ss),, then (T, TT) is a-coupled policy pair that for all Pr(a # als) < Diaar (TT(-s) न (+ss) < Ei= a², where a = Dimea (x I
Lemma Given any joint policies it and n, (#, πT) is a coupled policy pair, the the following inequal- ity holds:
n
Ean# [A (s,a))
2e Σ a
where a² Dype (7 [(r)) and maxx, A a.).
17

---

Published as a conference paper at ICLR 2023
Proof. Note that Eawx [AT (s a)]
0. We have
|aa (s" a)]
Eavu [A a)] - Bann [A" (8, a)ll
((a.a)~(RR [A (8, (= a)]
Pr(ā + (a))) (s* @) A (s a)]
[a. (s, (s.
Σ a² max AMT (s,a))
8
Lemma 3 (Multi-agent Advantage Discrepancy Lemmna). Given any joint policies n², π=? and T²
(T'', 2²) and (T² π² are coupled policy pairs, the following inequality holds:
[TT E ((or xx))
[AT*
B (s) mx2)
<46" DTV "TV""(Tr (T' | (1- 111-1 DTV (I=²
where ex' maxx,a | (s, a)ll and we denote A(s, a) as for brevity.
Proof. Let n, represent the times a o a (T* disagrees with π²) before timestamp
R [o m=2) [ATi] B (1)mm .x2) [AT*]
Pr(n 0) ( [P a0)) [AT']
E (or (P m1) [1=)
@ Pr(n: =0]) -]])E
<( II Pr(ax = ax aa n (11xx) ax ~ (,((s=1)) E
km
(8) 5(1 <11 II (1 DTV (-²)|T²))) E
k=1
=(1 (1 Dmaz (IT" ( 2221[T²)) )))
<( (1 Dme (T22 || 3) ))²} 22 2- Dive (πT ar7[(72) e
=46" n DTV ( || (1 (1 - D
Dmaz (T² | ))))
In (a), denote ( (> *2),n,>0 [A*]] E (s m²? o m F for brevity.
(b) follows the definition of a-coupled policy pair.
We provide useful equation of the normalized discounted state visitation distribution here.
Proposition 5
20 7 Pr(s; s|(Tt) Σ n (a
E ((s.a)((a') (22) [f(s, (1 - 7)
ΣΣ
(1 7)
Pr(st = s/ Σ n (cls))(s,
t=0
(1 -
(Pp x2) (/) ar)
t=0
18

---

Published as a conference paper at ICLR 2023
A.3 PROOFS OF INTUITIVE SEQUENTIAL UPDATE
1
J(+') - [(A
B (( [A*]
1 1-y
1 B(eaa) #!)
[A*'1] -
B(s,a)/(dr #i)) [AT]
[aat *] -B(sa))((rr #1) [A#
$ 1 ?
B (saa) +1)
[A*'1] ((ssa))(d [AT]
((s,a))(dr #1)
<46 =4
111 - -11
Σ at)
t=0
jE(e'U(i3)
| A*
((saa)((d,,t)))
E
1 1-7
<4e
a²
1-7 1- -Eyteeur)))
1
1
ad) +
1
4a
+2 Σ ET ject
1-7 7
A.4 PROOFS OF MONOTONIC POLICY IMPROVEMENT OF A2PO
Theorem (Single Agent Monotonic Bound) For agent i, let e' = max,,a a |Aa' |At (s) 5² max,,a a A
(s. A= a)). a DTV (1')) Vj e ( {i)), then we have:
5
[J(A') L - ( s 4e'a"
1-7(1- E) = 1 1-7
1-7
47
(a*
Σ
a²)
+ T-7
(4)
7)2
jE(miL(())
Proof. Using Lemma 3 and Prop. 5 we get
I(*') - -((A--))
E ((s.a))(am #
[
1
1
[A* '1
[A
E B(saa)-ctt .9)
((a.a)((dTstt))
1 γ
1
[A*1-1] B(ea)miam #t) [A*-1]
((o.a)/dda #9)
[A* '1 B(s.a)-(dt, A
B(m.a)-(dT)
54
7'11 (1
Σ at)') +
1 ((s,a)>(dr [|at A
I-7 7
jE(e'Uf())
1
1
<4c #'- 0¹
1- 71 -Estouua) az)
+
1-
19

---

Published as a conference paper at ICLR 2023
Theorem 2 (Joint Monotonic Bound) For each agent N, let é max,,a | (s (s*
a' DV x
( 5- = maxX,
IAT A (s, - A (s, and = max e¹, then we have:
n
1 1-7(1 EjE(ou()) au) + E 5
[J( G (+))
S de
a
7
1-7
Y=1
47
(a' Σ a)) Ei= 5t
(5)
(1 7)
1-9
jE(elU(i))
Proof.
[TT (+)
[(+)- [(T) - Σ B(o.a))(dT |AT (s, (5, (
i=1
I(#""11)+ J(+") -[(#" ) + (.....I((+)) - J(
B(s,a) AA (s.
1 7 1=1
[ - -(
E E(s,a)((d, [Am (s, a))
1=1
1
Ei=r 5t
<4c
a
1-7
1-7(1 - EjE(ou(A)) oU)
+
1-7
1=1
5
4
a²
Σ at
+ Σ Ei= 5²
(1
)
1-7
jE(etU(ii)
A.5 PROOFS OF INCREMENTALLY TIGHTENED BOUND OF A2PO
Assume agent l is updated with order k in the sequence 1,... since * is known, we have
[TT) - (+)
k-1
+ Ei 5a
[(*') 1 + 4e
Σ a'
1-
Eselou(n)) 1-x(1
1-7
i=k
+ Σ e¹
J(*') L (A*) 4c Σ a'
11 1- 1-1(1-EnEteuu))) E)((e((ag)))) ad)
1-7
i=k-1
1
En
<4c a'
1=1 i 1 1- 71 Epe(d wn)
+ 1-7
Thus the condition for improving ( is relaxed during updating agents at stage.
A.6
PROOFS OF MONOTONIC POLICY IMPROVEMENT OF MAPPO, CoPPO AND HAPPO
In this section, we give proof of the monotonic policy improvement of MAPPO, and unify the formats of the monotonic bounds of CoPPO and HAPPO, without considering the parameter-sharing method.
((sa)) [AA=] J.
MAPPO. For MAPPO, (T) = En J(T) 1
We first prove that
for agent i, J(#) - [(T) - ((o.a))(dT..))
A
bounded.
20

---

Published as a conference paper at ICLR 2023
[(T) [(T) 1-
((s
1
E [(s,a))(d #) [Ar] ((s,a))-ddtt,
A
(( 7
(PP AT
A
7
2
16 +0..6" Σ a
1=0
2c
a
j=1
Sum the bounds for all agents and take the average, we get
1
[(T)
[TT)
((s m)
AT
n1
2TT n n+1 1
7 n
Finally, the monotonic bound for MAPPO is
J(#)-J(m
((o.a))(d
1
((T) - J(T)
((s,a)-(a m
A n
+ n n-1 1
7' AT
B(a.))(dd".))
n 1 1-7
1=1
nT n+1 1 12
d² 20
n 1=1
4eT
CoPPO. We prove the results CoPPO unified and convenient form. For CoPPO, Cx J(T) + E (a,))((77 +) [A7 (s, a)). prove the bound using Lemma 3
21

---

Published as a conference paper at ICLR 2023
[(]) - -T(T)
1-7 E ((s.a)((0m (
1
E [(ssa))(Prr) [A7] E (Pr [A
1=0
< "
a 11 (1 DTV ( (T](
1=0
i=1
<4c "
1-7 1- Σj=1 ad)
HАPPO. Following the proof of Lemma 2 in Kuba et al. (2022). we know that HAPPO has the same monotonic improvement bound as that of CoPPO. For the monotonic improvement of single agent, we formulate the surrogate objective of agent i using HAPPO as J(A'-1) + (a.a)~(dm (1" a)] T-y ((e.a)(dd * ( a)]. as shown in Proposition of Kuba
et al. (2022). Following the proof of Thm. [ we get the following inequality.
1
J(+') - [(
B (d) +1) [A*]+ +
1- B (d +
(>TA (1)) as) a)]
1 7
<
1
B Bloaa) #i)
[A*
(s,,)) #i) [AT]]
B(s,a) xi 1) a)]
1
1
E B(s.a) at)
[atin]]
1
B ((
[1*
1
1
E B(ssa)/(dt
[
E (d) [1T)]
+2 2
1
Σ a
1
jee
<4e#
(111- (1- Σ all9
jE(e"Ufit)
| - - + Σ a'
E (()
jEc
<4c
1
) 7
4a 40
A'-1
+ Σ a
1-7 1-~(1- EsE(e)(a)))))
0z)
JEC
The right side of the last inequality is not a monotonic improvement bound, or it does not provide a guarantee for improving the expected performance T(*') since the term Ejeet a' is not con- trollable for agent i, whether through policy improvement or value learning. The uncontrollable term means the expected performance may not be improved even if the total variation distances of consecutive policies are well constrained.
A.7 COMPARISONS ON MONOTONIC IMPROVEMENT BOUNDS
CoPPO and HAPPO have the same monotonic bound that is tighter than that of MAPPO. A2PO achieves the tightest monotonic bound given mild assumptions about the errors of preceding-agent off-policy correction, which is valid and easy to achieve since preceding-agen off-policy correction contraction operator. A sufficient condition that A2PO has the tightest bound is that g <
7(1->) EjEx- -1)
(1-x(1 Eieduty 0z D( 701 -0-00-00-000000 o. for all N.
22

---

Published as a conference paper at ICLR 2023
A.8 PRECEDING-AGENT OFF-POLICY CORRECTION
In Retrace(A) (Munos el al. 2016), consider the current policy as -'=1 and base policy as ग,, we have the following definition:
A min (1.0, (a-sslt)) (reth + 7Q++x+1 Q(+k),
R, T2 +
Σ
π ((att)(8tt))
==1
Following that same structure, we have:
A' ((rt)l9tt)))) (rete vV44441 Ve+k),
R. 7Ven Σ
A min (1.0, +(ac+)|s(t))
By subtracting V,, we get the definition of PreOPC. Or one can get >AT by substituting + yVi+1 for Qt and subtracting Tt + +VV+-
A.9 WHY POLICCNNSS IS MORE SERIOUS IN SEQUENTIAL UPDATE SCHEME?
As shown in Fig. 13 the off policy correction in sequential update algorithms improves the perfor- mance significantly while similar performance gaps are not observed when used in simultaneous update algorithms. We attribute the difference to the influence of the clipping mechanism the total variation distance.
prove exact relations, clipping the agents independently tends to larger total variation distances between the current and future policies of the agents, leading more "off-policyness' in sequential update algorithms.
From Corollary (rv(T > i==1 (r'l'") Although
23

---

Published as a conference paper at ICLR 2023
B EXPERIMENTAL DETAILS
B.1 IMPLEMENTATION
For a fair comparison, we (re)implement A2PO and the baselines based on the implementation of MAPPO. We keep the same structures for all the algorithms and tune all the algorithms following the same process, i.e., a grid search over a small collection of hyper-parameterss parameters, to avoid the influence of different implementation details on the results. The grid search is performed three hyper- parameters: the learning rate, À and the agent block num in the tasks with numerous agents.
The algorithms, including A2PO and baselines, parameter independent versions. A2PO in the parameter sharing version is implemented as in Alg. The main modifications are colored in blue. We rearrange the loops of agents and ppo epochs. The number of ppo epochs is divided by n for comparable updating times with the simultaneous algorithms. The approximated advantage estimated by correcting the action probabilities of all the agents given such e".
implemented into both parameter sharing and
Algorithm 2: Agent-by- Policy Optimization (Parameter Sharing)
with Ty = ... T8. and the global value Initialize the shared joint policy To = {mo...., #B) function V.
(ro....,,7]
for iteration m = 1, ..... do
Collect data using m- Policy n. = 1.
for L epochs do
for k: 1, . do
Agent R(k), preceding agents ef [R(I)..... R(n 1)}.
Joint policy 4 n.
Compute the advantage approximation A "(s, a) via eq. 2
10
Compute the value target v(s)) = A =M
(s, + Vs).
T arg max m - in eq.
6
arg miny Ex (|v(s) V (s)1
Practically, each agent is equipped with a value function, we generate the agent order at once to avoid estimating the advantage function mfn-1) times. The order becomes i.,..., J...... . in which E|A'| >= A/
B.2 EXPERIMENTAL SETUP AND ADDITIONAL RESULTS
B.2.1 STARCRAFTII MULTI-AGENT CHILLENGE
StarCraftII Multi-agent Challenge (SMAC) (Samvelyan et al. 2019) provides a wide range multi-
agent tasks in the battle scenarios of StarCraftll Algorithms adopting parameter sharing have shown superior performance in SMAC, so all the algorithms are implemented as parameter sharing. As shown in Tab. 5 we evaluate the algorithms 12 maps of SMAC with various difficulties, in which the baselines can not achieve 100% win rates easily. We use the results of Qmix in Yu et al. 2022 The learning curves for episode return are summarized in Fig.
B.2.2 MULTI-AGENT MUJoCo
Multi-agent MuJoCo (MA MuJoCo) (Peng et al. 202I) contains a range of multi-agent robot con- tinuous control tasks, in which an agent controls the composition of robot joints. MA MuJoCo extends the high-dimensional single-agent locomotion tasks MuJoCo (Todorov et al. 2012). a widely adopted benchmark for SARL algorithms (Haamoja al. 2018 He & Hou 2020), into the multi-agent case. Agents must cooperate in their actions for robot locomotion, and different agents control different compositions of the robot joints. We the reward settings of the original paper
24

---

Published as a conference paper at ICLR 2023
6igg
1.00
0720
0:73
180 Bat
We Beae:
013
0750
1.30
10
0770
0775
0300
Strps
Strpe
Stope
Sto
01:0
0.70
11t D2an
Win DiAt:
0.0
10:00
0.50
01.23
0.50
1.00
07.5
17.01
1.00
N1to EGdA
Min Dbul-
0.01
1100
01:00
x307
77m
comriler
3.10
1.00
1.00
0120
Mrn DbuAc
3t2ge
Stepe
MIXPPO w/
CcPPO PS
EAPPO
J22P0 P9
Figure 8: Comparisons of median win rate on SMAC.
25

---

Published as a conference paper at ICLR 2023
Table 5: Median win rates and standard deviations on SMAC tasks. 'w/ PS* means the algorithm is implemented as parameter sharing
Map
Difficulty
MAPPO w/ PS
CoPPO w/ PS
HАPPO w/ PS
A2PO w/ PS
Qmix w/ PS
MMM
Easy
96.9(0.988)
96.9(1.25)
95.3(2.48)
100(1.07)
95.3(2.5)
3s_vs_5
Hard
100(1.17)
100(2.08)
100(0.659)
100(0.534)
98,4(2.4)
2e.vs_642g
Hard
98.4(1.74)
96.9(0.521)
96.9(0.521)
96.9(0.659)
92.2(4.0)
3s5z
Hard
84.4(4.39)
92.2(2.35)
92.2(1.74)
98.4(1.04)
88.3(2.9)
5m_vs_6m
Hard
84.4(2.77)
84,4(2.12)
87.5(2.51)
90.6(3.06)
75.8(3.7)
anLvs_9m
Hard
84.4(2.39)
84,4(2.04)
96.9(3.78)
100(1.04)
92.2(2.0)
10m_vs_1l Im
Hard
93.8(18.7)
96.9(2.6)
98.4(2.99)
100(0.521)
95.3(1.0)
6h_vs_8z
Super Hard
87.5(1.53)
90.6(0.765)
87.5(1.49)
90.6(1.32)
9.4(2.0)
3s5z. .s...vs... .36z
Super Hard 82.8(19.2)
84.4(2.9)
37.5(13.2)
93.8(19.8)
82.8(5.3)
MMM2
Super Hard 90.6(8.89)
90.6(6.93)
51.6(9.01)
98.4(1.25)
87.5(2.6)
27m.vs_30m
Super Hard 93.8(3.75)
93.8(2.2)
90.6(4.77)
100(1.55)
39.1(9.8)
corridor
Super Hard 96.9(0)
100(0.659)
96.9(0.96)
100(0)
84.4(2.5)
overall
91.1(5.46)
92.6(2.2)
85.9(3668)
97.4(2.65)
78.4(3.6)
but set the environment to be fully observabld The agents are heterogencous and mostly asymmet- ric in MA-MuJoCo, implement the algorithms parameter-inddependent We test 14 tasks of 6 scenarios in MA MuloCo, as illustrated in Fig. 9
B.2.3 MULTI-AGENT PARTICLE ENVIRONMENT
We consider the Navigation task of the Multi-agent Particle Environment (MPE) (Lowe al.) 2017) implemented in PettingZoo TTeryy et al. 2021) which implements MPE with minor fixes and pro- vides convenience for customizing the number of agents and landmarks, and customizing the global and local rewards., with and 5 agents and corresponding numbers of landmarks. The agents are rewarded based on the minimum distance other, meaning that the reward is entirely up to the coordination behavior. We adopted two different reward settings: Fully Cooperative and General-suni In the Fully Cooperative setting, the agents share the same reward, while in the General-sum setting, the agents are additionally rewarded based on the local collision detection. The results in Fig. [0 show that A2PO generally outperforms the baselines on the average return and the sample efficiency. Noted that A2PO is developed in fully cooperative games, the results in the General-sum setting reveal the potential of extending A2PO into general-sum games. Further, the performance gap between A2PO and the baselines enlarges with the increasing number of agents.
the landmarks and penalized for colliding with each
B.2.4 GOOGLE RESEARCH FOOTBALL
In the above experiments, we have evaluated A2PO in tasks where agents can learn both their micro-operations and coordination behav- iors (SMAC and MA-MuJoCo) and tasks where agents can only learn coordination behaviors (the Navigation task). However, the coordina- tion behaviors the above tasks are relatively easy to discover, e.g.,
Pootiall 5 (Pirmmeter Sharing
agents learn to concentrate their fire to shoot the enemies and cover each other in SMAC. Recent works (Wen et al. 2022 Yu et al., 2022) have conducted experiments on Google Research Football academic scenar- ios with a small number of players and easily accessible targets, making the coordination behavior also easy to discover. In contrast, we evaluate A2PO in the full-game scenarios, where the players of the left team, ex- cept for the goalkeeper, are controlled to play football match against the right team controlled by the built-in AI provided by GRF, The agents in the full-game scenarios have high- digh-dimensional observations, complex action spaces, and a long-spa span timescale (3000 steps). We reconstruct the observation space and
300
Eceoda
MAPPO
HAPPO
CaPPO
AS50
Figure 11: 5-vs-5 sce- nario with Parameter sharing.
Empiricalyy, we find the fully ohservable setting does not make the tasks easier because of the information redundancy.
26

---

Published as a conference paper at ICLR 2023
Antont 2e0
Ancod bod
Eptock Beeee
Eptook Detun
a0:0
b000
0100
0.25
0.33
0183
0.20
15.0
0001
325
16.00
100
Willomade
Sptcod ttrtur
4000
Noood
6000
Nptodd
2000
2000
2200
1000
24- Gcl
Higtans
Hall
5000
Kiladd Detex
Bidod Detex
8007
2200
2330
30rp
K.0
30rpp
K27
3tepe
K007
ElatCChestch Det
ElatCheetthh 9K1
0030
Estedd Soecre
80300
0200
000
3.25
6150
0.75
010
11.0
0001
1450
1070
[1rnnookivv 1ic1
Npoccb tettm
1500.00
MARPO eyjo
Cwrtho wud H// w/ou
1000300
Figure 9; Comparisons of average episode return on MA-MuJoCo.
27

---

Published as a conference paper at ICLR 2023
3. Aggntt (Pully Cooperativ))
Ageste (Puly Cooperation)
3 Agents (Grreva) Sum)
5. Agente (General Sum)
-22.5
Tyoock fteere
-21.5
-0.0
-2.5
-2.40
Stope
Strppe
551pe
XCAPIN
3AAPPO
Figure 10:
Comparisons averaged return on the Multi-agent Particle Environment Navigation task. Left: The fully cooperative setting. Right: The general-sum setting.
design a dense reward to facilitate training in these scenarios based on Football-part parii.. The observa- tion is formed to be agent-specific. The reward function estimates the behaviors of the entire team, including scoring, and carrying the ball to the opponent's 's restricted area et al., but not the individual behaviors such ball-passing (Li et al. 202T). We implement all the algorithms for the 5-vs-5 sce- nario as both parameter sharing and parameter-independeee implemented as parameter sharing are shown in Fig. [I] in which A2PO gets free from the trouble that the controlled agents have similar behavior and compete for the ball (Li et al. 2021).
The additional results with algorithms
We implement all the algorithms on the 11-vs-11 scenario as parameter sharing using MALib (Zhou et al. 2021) for acceleration and train the algorithms for 300M environment steps. We summarize the learned behaviors observed in the game videos:
Basic Skills. The agents trained by MAPPO and CoPPO perform unsatisfactorily in basic skills such dribbling, shooting, and the agents even out of bounds frequently. In contrast, the agents trained by HAPPO and A2PO perform better in the basic skills. We attribute the problems the non-stationarity issue that seriously influences the simultane- ous updating algorithms. We also note that the agents trained by all the algorithms fail understand the off-side mechanism and occasionally gather together on the opponent's bottom line.
Passing and Receiving Coordination. We analyze the direct way for coordination: pass- ing and receiving the ball. As illustrated in Tab. 3 the agents trained by MAPPO have the lowest number of successful passes and the lowest successful pass rate, and we can hardly observe the agents passing the ball. Agents trained by CoPPO perform better on passing the ball but suffer from poor basic skills, and get tackled after receiving the ball. Agents trained by HAPPO prefer passing the ball without considering the teammates' situations, e.g., the receiver is marked by several opponents. Agents trained by A2PO can pass the ball to their teammates in way that leads to a score. We attribute the performance gain the preceding-agee agent off- off-policy correction, which means that agents estimate the teammates' situations and intentions better.
We further visualize the learned behaviors of A2PO in Fig. 12 In the top of Fig. 12 two players cooperatively break through the opponent's 's defense and complete passing and receiving coordi- nation for scoring. In the bottom of Fig. 12 three players make a fast thrust by two long passes: the goalkeeper passes the ball to the player at the edge, and the player at the edge passes the ball to the player behind the opponents. The complex coordination strategies are hardly observed in other baselines.
B.2.5 ABLATION
Preceding agent off-policy correction. More ablations on preceding-agent off-policy correction are shown in Fig. 13 The basclines are:
MAPPO w/ V-trace, CoPPO w/ V-trace: Simultaneous update methods with advantage estimation as V-trace.
HAPPO w/ PreOPC: HAPPO with advantage estimation as PreOPC.
28

---

Published as a conference paper at ICLR 2023
Motion player
Motion
location
?
Hisseyy Jocation
The player Turing best opponent with the player Johason marking.
Turing beat another oppenent. Johnson prepares to take the pess from Turing.
Thring passes the ball Johnson, then Johnson receives the thrusts shoot.
Johnson broaks through the opponent's goalkeeper, ahoots, and makes goal.
goalkeeper makes goal plays loog pass the player near the siddine.
The player Turing recenves the pass froos the goalkeeper, then driboles and passes the ball the playr the milfield.
The player Curie receives the pass Turnag, plays fist break.
Curie sboots and makes goal.
Figure 12: Visualization of trained A2PO policies the Google Research Football 1 11-s--1 11 sce- nario, which shows that A2PO encourages complex cooperation behaviors to make a goal. Top: Player Turing and Johnson cooperate to beat multiple opponents to break through the defense and make a goal. Bottom:
The goalkeeper, player Turing, and Curie achieve the pass and receive coop- eration twice. A fast thrust is made by consecutively passing the ball.
In this ablation study, the basclines equipped with off off-policy correction methods. The experiment yields the following three conclusions:
The results firstly support the conclusion in Sec. 3.3 that applying PreOPC to sequential update methods results in a greater performance improvement than applying V-trace to simultaneous update methods.
Secondly, the primary distinction between A2PO and HAPPO with PreOPC is the clipping objective. The results demonstrate that the clipping objective derived from the single-agent improvement bound contributes to the performance improvement.
And thirdly, although were unable to assess the error of PreOPC, compare A2PO with RPISA-PPO, which can be viewed as A2PO algorithms with error- froe off-policy correction methods (the advantage estimation is error-free) the expense of sample ineffi- ciency. A2PO reaches or outperforms the asymptotic performance of RPISA-PPO. A2PO outperforms RPISA-PPO since RPISA-PPO suffers from performance degradation sult of agents updating policies with separated data (Taheri & Thrampoulidis 2022).
We further analyze the sensitivity to the hyper-parameter Results in Fig. 14 illustrate that preceding-agen agent off-policy correction does not introduce more sensitivity.
Hunanooiv2 D/8
Aeragradi Dedlenacc
7100
3000
10000
2000
5000
VFT
000
0001
1.23
0200
0..5
-20
0120
1.20
13:03
1.70
0701
0123
1030
0.75
1000
0.20
1350
1170
SLAPTO
BATTO
SEAPR0 Vitrace
00300
Figure 13: Ablation experiments on preceding- agent off- policy correction.
Agent Selection Rule. More ablations on the agent selection rules are shown in Fig. I3 pare two additional rules: 'Reverse-greedy" and 'Reverse-semi- semi-greedy'. 'Reverse' means selecting the agent with the minimal advantage first. While we observe that the effect of the selection rule becomes less significant in tasks with homogeneous symmetric agents.
We com-
Going deeper into the effects of agent selection rules, we show that the agents with implicit guid- ance from the advantage estimation benefit from greedily selecting agents in Fig. T6 and 17 More
29

---

Published as a conference paper at ICLR 2023
Fumanrde22 9-8
Furmak Burien
00:0
2000
3.7
014
113
105
Strps
21ege
3w000
3w0/00
1w0000
Ant-v2
MAPPO
Folesta Totber
00:31
Einnd
370
010
103
120
110
175
30aps
30pp
31rpe
2m1000
Am100
Am1057
Am1150
1.30
1.00
1.00
Who Taese
0.30
0.50
0:20
0.30
010
30
0.
105
0.2
105
022
Skee
2m0000
A-1U33
Am1000
2m-250
M.APPO
MAPPO MA-Aviraor
Win Badt
Vina E-de
10in
Vin
0.1
605
62
3,000
$0.000
30.000
Figure 14: Sensitivity analysis of X.
30

---

Published as a conference paper at ICLR 2023
MMM2
Artrr Bx!
Bru Jm
8000
1003
1000
0.2
Stipe
X30
Stege
Strge
X10
9tee
X3P
3APPO-Cxdk:
EA2F0-Gmdy
X2PD-Cydl
AJPO&Gmmlyy
3APPO-Bences
X2FO-Runkkm
AZPO.Smnignnll
Figure 15: Ablation experiments on the agent selection rules. Left: Heterogeneous or asymmetric agents. Right: Homogeneous or symmetric agents.
even bars appear in one fig means the agents are more balanced in terms of the guidance from the advantage estimation. Take the agent 10 in Fig. [ō]for example, under 'Cyclic' and 'Random' rules, agent 10 perform the worst with high proportions, while it has higher proportions in prior ranks under 'Greedy' rule.
Jark
(a) The imbalance of the agents. The bar of agent illustrates the proportion of its ranks in terms of E, a. [1.4 []. Especially, agent 10 has implicit guidance, i.e. small absolute value of advantage function when using Cyclic and Ran- dom selection rule, comparable with other agents with Greedy selection rule.
(b) The coefficient of vari- of agent 10's order proportions.
Figure 16: Agents' imbalance in terms the estimated advantage. The experiment is conducted on the MMM2 task of SMAC.
Adaptive Clipping Parameter. More ablations on the adaptive clipping parameter are shown in Fig. 18 Similarly, we observe that the effect of the adaptive clipping parameter becomes less sig- nificant in tasks with homogeneous or symmetric agents.
Figure 17: More experiments on the agents' imbalance in terms the estimated advantage. 3s5z task. Bottom: MMM2 task.
Top:
31

---

Published as a conference paper at ICLR 2023
Tum Hys
MMM2
Artrr Ax!
0003
6000
3.65
6000
6890
3.65
0000
02:
0.5
1003
0.0g
X337
Strps
Stege
9tpee
X0P
SAATVO
ASSO wrtn Aelipe
MAPPO Ankge
CdPPO
Algli
EAPPO
Adgl
.2200
Figure 18: More ablation experiments on the adaptive clipping parameter. Left: Heterogeneous or asymmetric agents. Right: Homogeneous symmetric agents.
Huraancdd +22
Hlmmnnedd-22
Football 11 11
0.8
2000
4000
Win Rotee
0.5
2000
2000
0.4
MAPPO
CPPPO
1000
0.2
HAPPO
A2PO
11:0
11.25
11.00
03.70
1.00
350
Stapp
0.0
2.5
5.0
7.5
10.0
MAMPO w/u
C.P0
AXPO wia
Hours
(a) Comparison on Humanoid 9/8 over both environment sleps and training time.
(b) Comparison on GRF 11-vs-11 scenario.
Figure 19: Wall time Analysis.
B.3 WALL TIME ANALYSIS
Multiple updates in a stage may increase training time, and the need for more training time may im- pact the scalability of A2PO, which is common concern regarding the sequential update scheme. Nevertheless, sequential update scheme will increase training time less than might be expected. Before proceeding, we note that the majority of experiments in our work synchronously imple- mented, and the training time consists of the time spent updating policies and collecting samples.
We have proposed simple yet effective method for controlling training time in order reduce training time. As trade-off between performance and training time, we divide the agents into blocks to reduce the number of update iterations. For example, the tasks with 10 agents can be divided into 3 blocks, with sizes 3, 3, 4, respectively, and only 3 updates will be performed in a policy update iteration. From the implementation perspective, since the number of samples used in a single update decreases, the sequential update scheme requires less memory and less updating time when update policies. Therefore, is possible to control the training time as less than 1.5 times the training time of the simultancous update methods. In addition, assuming good implementation, fewer update iterations will be performed if mini-batches are used a single policy update, as the size of a mini-batch can be greater in sequential update methods under limited memory resources. In such a case, fewer mini-batches will be used, further decreasing the training time. Moreover, sampling consumes the majority of the training time, and the increased updating time appears less significant when analysing the wall time for on-policy algorithms with synchronized implementations.
The training time is depicted in Tab. 6 A2PO achieves significantly greater performance with only marginally more training time. In addition, we illustrate the Humanoid 9/8 comparisons regarding environment steps and training time Fig. 19a] and the comparisons on the GRF 11-vs-11 11 scenario in Fig. 196 A2PO maintains an advantage in terms of training time.
B.4 HYPER-PARE PARAMETERS
We tune several pappeeerrseeters in all the benchmarks, other hyper-parameter refer to the settings used in MAPPO. & selected to be 0.5 in all the tasks.
32

---

Published as a conference paper at ICLR 2023
Table 6: The comparison of training duration. The format of the first line in a cell is: Training
timm(Sanpinn time+ Updating Time). The second line of cell represents the time normalized.
Task
MAPPO
CoPPO
HAPPO
A2PO
31299m((333+0022mm
3h33mm3h6m-0h27mm L.020089 0.13)
3h49mm(h77++0h422mm
4h32mmGh4Im=0hh1mm
3s5z
L0000.8
L.0(0.89 0.20)
1.30(1066 0.25)
Im 4h52m)
3h19mtShh2mm + 4h55m)
16h22m/8h20mm 7h42m)
19t53m(Sh7m + 7h46m)
27m 30m
1.0000.64 0.36)
1.000.63 0.37)
1.20(0.62 0.58)
1.19(0.61 0.58)
2h0m(1h45mm (h15m)
0158m<1h43m) (m1)mm
2h155m 0h33m)
2h31m(2h0m 0h31m)
Humanoid 9
1.000.87 + 0.13)
0.9910.86 0.13)
1.1200.87 + 0.25)
I 1,26(1.00 1.000 0.26)
6h42m(6h16m 0h266m)
6h45m(6h19m 0h26m)
7h29mu66h5m lh24m)
7h2m(Sh34m 1h28m)
Ant 4x2
1.0000.33 0,07)
10110,94 0.07)
1,1200911 + 0.21)
I 1,05(0.33 0.22)
12h9tu(10h6m 2h3mm)
17h7mm(1hh5m 2h2m)
16h55mi 1h2m Sh53mm)
19h25m(11h59un + 7h26m)
Humanoid 17x1
1.000.83 0.17)
141(1.24 0.17)
1.39(0.91
1.600.99 0.61)
4hh466m(32h470m + 1h59m)
32b46m( 30049m Hh57m)
39h26m((1hhS4m + 7h32m)
37h26m( 7h24m)
Foothall 5vs5
1.0000944 + 0.06)
0.94/0.89 0.06)
1.1300.2 0.22)
1.0800086 0.21)
B.4.1
STARCRAFTII MULTI-AGENT CHALLENGE
We list the hyper-parameters used for each task of SMAC in Tab.
Table 7: Hyper-parameters in SMAC.
Hyperparameters agent block ppo epoch
MMM
3
0.95 0.2
3s_vs_5z
3
15
0.95
0.05
2c vs 64zg
2
0.95 0,2
3s5z
3
0.95 0.2
5m_vs_6m
2
10
0.93 0.05
8m_vs.90
5
15
0.95 0.05
10m_vs_
2
10
0,97 0.2
6h. vs.8z
2
0.99 0.2
vs.z_vs.3s6z
2
0.90 0.2
MMM2
2
0.95 0.2
27m vs.30m
3
5
0.95
0.2
corridor
2
0.95 0.2
B.4.2 MULTI-AGENT MuJoCo
For the model structure in MA MuJoCo, the output from the last layer is processed by Tanh layer and the action distribution modeled Gaussian distribution initialized with mean as 0 and log std as -0.5. The probability output of different actions are averaged when computing the policy ratio. The common hyper-paranee paraaeers used MA MuJoCo are listed in Tab.
Table 8: Common hypermeters in MA MuJoCo.
Hyperparameters
Values
entropy
0
gain
0.01
batch size
4000
B.4.3 MULTI-AGENT PARTICLE ENVIRONMENT
We list the hyper-purameters used in MPE in Tab. 10
B.4.4 GOOGLE RESEARCH FOOTBALL
We list the hyper-parameters used in the GRF 5-vs-5 scenario in Tab. 11
33

---

Published as a conference paper at ICLR 2023
Table Hypermeters for the scenarios in MA MuJoCo.
Hyperparameters
Ant
HalfCheetah
Hopper
Humanoid
HumanoidStandup
Walker2d
agent block
8x1:4
17x1:5
17x1:4
/
ppo epoch
8
5
5
5
actor
3c-4
3e-4
le-4
3e-4
3c-4
3e-4
critic Ir
3c-4
3e-4
lc-4
3c-4
3c-4
3e-4
A
0.93
0.93
0.95
0.9
0.93
0.93
0.2
0.2
0.1
0.2
0.2
0.2
Table 10: Hypermeters for the scenarios MPE.
Hyperparameters
Values
ppo epoch
chunk length
5
entropy
0.05
actor Ir
2c-4
critic lr
2c-4
X
0.97
0.2
C THE RELATED WORK OF OTHER MARL METHODS
Value decomposition methods. The value decomposition methods such as VDN (Sunehag et al, 2017) and Qmix (Rashid al. 2018), factorize the joint value function and adopt the central- ized training and decentralized execution paradigm. The Individual Siaettal--Goobl-MMMS (IGM) prin- ciple is proposed to ensure consistency between the joint and local greedy action selections in the joint Q-value function Qtae(T, a) and the individual Q-value function (Q'(7', ("T'',a") fi=1: a VT E arg T.arg A (To a) (arg max,' E.A' (' .!)...... arg =E Q"(7" aa)). Two sufficient conditions, the additivity and the monotonicity, to satisfy IGM are proposed in Sunchag al. (2017) and RRahid al. (2018) respectively. In addition the V function and Q function decomposition, QPLEX (Wang et al. 202T) considers implementing IGM in the dueling structure where Q = V + A. QPLEX only constrains the advantage functions ciple. The global advantage function is decomposed
T,
satisfy the IGM prin- (To a) = i=1 Ai(T, a A,(TT
where >; > O. We evaluate the performance of Qmix in Tab. 2 and Tab. 5 Integrat- ing the IGM principle into A2PO without compromising the monotonic improvement guarantee a desirable extension. Specifically, the udvantage-based IGM establishes a connection between the global advantage function and the local advantage functions, and the advantage decomposition A a) = Σi >x(T, a) A, (T, as) will not jeopardize the derivation of the monotonic improve- ment guarantee.
Convergence and optimality of MARL. T-PPO (Ye et al. 2022) firstly introduce framework called Generalized Multi-Agent Actor-Critic with Policy Factorization (GPF-MAC), which consists of methods with factorized local policies and may become stuck in sub-optimality. To address this problems. T-PPO transforms a multi-agent MDP into a special "single-agent" MDP with a sequen- tial structure. T-PPO transforms multi-agent MDP into a "single-agent" MDP with sequential structure to address this issue. T-PPO has been shown to produce an optimal policy if implemented properly. Theoretically, sequential update methods, such as A2PO and HАPPO, are also instances of GPF-MAC and may be stuck into sub-optimal policies. The main differences between A2PO and T-PPO include that A2PO updates the factorized policies sequentially and makes decisions simul- taneously, while T-PPO makes decisions sequentially, and that A2PO does not introduce the virtual state and the sequential transformation framework network. And theoretically, T-PPO may compro- mise the monotonic improvement guarantee. Tab, [2 we compare A2PÓ, MAPPO and T-PPO on SMAC tasks empirically. A2PO is superior to T-PPO in the majority of tasks.
34

---

Published as a conference paper at ICLR 2023
Table 11: Hypermeters for the scenarios in MPE.
Hyperparameters
Values
ppo epoch
10
chunk length
10
entropy
0.001
actor Ir
5e-4
critic Ir
5e-4
X
0.95
0.25
0.995
Table 12: Comparisons of A2PO, MAPPO and T-PPO.
Map
Difficulty
MAPPO w/ PS
T-PPO w/ PS
A2PO w/ PS
Ic3s5z
Easy
100(0.0)
99.8((0.0)
100(0.0)
MMM2
Super Hard
90.6(8.9)
81.6(7.7)
98.4(1.3)
3s5z. vs. 3s6z
Super Hard
82.8(19.2)
85.5(5.2)
93.8(19.8)
6h_vs_8z
Super Hard
87.5(1.5)
91.8(1.1)
90.6(1.3)
corridor
Super Hard 99.1(0.3)
96.9(0.0)
100(0.0)
D THE RELATED WORK OF COORDINATE DESCENT
Realizing the similarity between the sequential policy update scheme and the block coordinate de- scent algorithms, we borrow the optimization techniques in the coordinate descent algorithms to accelerate the optimization and amplify the convergence advantage over the simultaneous update scheme (Gordon & Tibshirani 2015 Shi et al.) 2017). One the critical questions in the coordi- nate descent algorithms is selecting the coordinate for the next-step optimization. Glasmachers & Dogan (203);; Lu et al. (2018) provided analyses of the convergence rate advantage of the Gauss- Southwell rule, i.c., greedily selecting the coordinate with the maximal gradient, over the random selection rule. We recognize the optimization of our surrogate objective (Schulman et al. 2017) agent-by-agent
block coordinate descent problem. Therefore the agent selection rule plays crucial role in accelerating the optimization. Inspired by the coordinate selection rules, we propose greedy and semi-greedy agent selection rules and empirically show that the underperforning agents benefit from the greedily selecting agents.
35


Reviews:
[{"review_id": "iWv6HaisElS", "reviewer": "Reviewer_7L45", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper briefly reviews previous works of sequential updating schemes in multiagent trust region algorithms and points out the limitations of these works, which are either sample inefficient or lack of monotonic improvement guarantee for each agent. To achieve both sample efficiency and monotonic improvement guarantee for each agent, it proposes a new algorithm Agent-by-Agent Policy Optimization (A2PO) and analyzes its monotonic improvement bound. ", "summary_of_the_review": "This work discusses the limitations of previous multi-agent trust-region algorithms and proposes an interesting method, which empirically shows outperformance. However, some further discussions are needed to justify the significance of this work. A final recommendation will depend on how questions in WEAKNESS are clarified.\n", "strength_and_weaknesses": "**STRENGTHS**\n\nThis paper does a sufficient literature survey. It is well-structured and easy to follow. Mathematical statements and proofs look sound. Experimental results show improvements over baselines. \n\nWEAKNESSES\n\n1) The motivation is a little confusing. Why should monotonic improvement for each agent be guaranteed? Is it possible that a better joint bound is obtained by giving up a monotonic improvement guarantee for each agent?\n\n2) The sample-inefficient claim for RPISA may not be right. It is not necessary to drop $(n-1)/n$ of the collected sample. For example, [1] is an implementation of RPISA, which is proven to be sample efficient. It will be helpful to have further discussions on these algorithms both theoretically and empirically.\n\n3) A2PO seems to take a lot of time in training. It is highly desired to elaborate on this issue.\n\n[1] Jianing Ye, Chenghao Li, Jianhao Wang, and Chongjie Zhang. Towards Global Optimality in Cooperative MARL with Sequential Transformation. ArXiv, abs/2207.11143, 2022.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fMDpLv-NSWe", "reviewer": "Reviewer_ZzqH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new surrogate objective in joint policy optimization for coordination tasks in MARL, following single roll-out and sequential update schemes. The new surrogate depends on a new off-policy correction method similar to the one in (Munos et al., 2016), and retains the monotonic improvement guarantees on individual agent and overall performance, while also maintaining high sample efficiency. Furthermore, they empirically show that the order of the agents' update and an adaptive clipping on the importance sampling probabilities has a substantial effect on the overall performance. Finally, they provide extensive experimental results on four MARL benchmarks, where they outperform previous trust-region MARL methods. \n", "summary_of_the_review": "#### $\\textbf{Summary}$\n\nOverall, I find the contribution of the paper important to the MARL community. The authors provide an elegant solution to the single-agent policy improvement problem in trust region cooperative MARL using sequential update schemes. Furthermore, the extensive experimental results offer a complete picture of the benefits of A2PO, and also of the benefits of agent selection order. \n\n\n", "strength_and_weaknesses": "#### $\\textbf{Strength}$\n\n1. The problem considered in the paper is well-motivated and the challenges are incrementally introduced, together with the relevant related work.\n2. The proposed off-policy correction method is theoretically guaranteed to satisfy monotonic single-agent improvement and, as a consequence, overall monotonic improvement. \n3. The joint policy monotonic improvement is tighter than previous state of the art.\n4. There are extensive experimental evaluations on well-known MARL benchmarks which clearly demonstrate the advantage of using A2PO. \n5. The authors further provide experimental justification for using semi-greedy agent selection and adaptive clipping in the estimated probabilities. \n\n#### $\\textbf{Weaknesses/Questions}$\n\n1. In the abstract it is claimed that A2PO improves sample efficiency, and in Table 1 it is again stated that the sample efficiency is high. What is meant by sample efficiency? Is it sample complexity? In any case, to my understanding, there is no subsequent result that shows an improvement of the sample efficiency in the paper. Is the statement based on a similar efficiency result imported from HAPPO since the rationale (at lease with respect to single roll-out usage) is similar? \n2. I would have liked to see some convergence guarantees of A2PO for single agent and/or multiple agents scenarios. Does A2PO converge to individual optimal policies for every agent (jointly), and if so, how fast compared to HAPPO or similar methods, in terms of agents number, episode length and epoch length? \n3. Can you elaborate on the importance of single-agent policy improvement in this setting? The reward function $r$ is the same for all agents, so there is no conflict of interest or notion of equilibrium, all agents are striving towards the same goal. If it wasn't for the improvement of joint monotonic bounds with respect to HAPPO, why should one care about single-agent policy improvement in this scenario? \n\n#### $\\textbf{Suggestions}$\n\n1. In some places such as first paragraph of Section 4 or Table 1, in-line equations may be improved to increase readability. \n2. In Section 3.1, either use the usual $\\mathbb{P}$ notation for probability, or you may want to define what $Pr$ means. \n3. I suggest you define the sample trajectory right after the definition of the value function, since that is where you first use it.\n4. In the sequential update scheme illustration (pipeline) in Section 3.2, you might want to define the surrogate objective $\\mathcal{L}$.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "dDUR9s1lU9", "reviewer": "Reviewer_N8aU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a sequential (agent by agent) policy gradient update algorithm (A2PO) in the MARL setting that guarantees monotonic policy improvement for each agent and also their joint policy. Theoretical guarantees are provided for monotonic improvement and experimental results also support the claims made in the paper. \n", "summary_of_the_review": "I would recommend rejecting the paper in its current form, primarily because the presentation of the material is difficult to follow and the paper does not seem to be polished overall due to several typos, even in the appendix, that make it cumbersome to read. \n\n===========\n\nAfter the rebuttal period, the authors' response to all the reviews has helped me understand the work more clearly. The authors have added a Table for consolidating all the notations used in the appendix. Although my initial reading of the paper gave me the impression that the paper is hard to follow and from a quick comparison of the latest version of the paper, it does not look like the authors have included any additional explanations in the text - I do not think the other reviewers had the same problem, so it might just be me. But I will agree that the authors have sufficiently addressed concerns regarding the main contributions of the paper in their response here to the reviewers and their experimental results are thorough and extensive. So, I am updating my score accordingly.", "strength_and_weaknesses": "This paper addresses an important problem in MARL. In prior work, the non-stationarity due to simultaneous policy update of agents in the multi-agent setting gives rise to high variance in the gradients, requiring more samples for convergence of each agent. Instead, the proposed A2PO algorithm uses importance sampling to weight off-policy samples used in sequential update of agent policies for the different agents in the team. \n\nIn general, the paper is not easy to follow due to the use of several notations that are not properly defined before being referenced and therefore, forces the reader to go back and forth looking for the appropriate definitions. It would help to perhaps create a consolidated table for all the notations and symbols used in the paper. \n\nSpecific comments about notation: \n\n- Page 3, Section 3.2 - what does the superscript $\\mathcal{I}$ indicate in $\\mathcal{L}^{\\mathcal{I}}_{\\hat{\\pi}^{i-1}}$? \n\n- Page 6, first paragraph, second line after eq 6: $\\mathcal{C}(\\cdot,\\cdot)$ has been used without first defining it. The definition is given in Page 7. \n\nSec 4, Semi-greedy Agent Selection Rule: “purely greedy selection may lead to early convergence which harms the performance.” - Could you please elaborate this point? \n\nSec 4, Adaptive Clipping Parameter: Could you please explain what is precisely meant by “balanced and sufficient” clipping ranges? \n\nSec 5.2: The results in the ablation study are difficult to follow. The paragraph PreOPC compares to MAPPO and CoPPO with V-trace, also to HAPPO and RPISA-PPO : but these methods are not described in the main paper which makes it difficult to understand the results. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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": "U6otwp7Ihd", "reviewer": "Reviewer_GdLP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a new MARL training objective to improve training efficiency. In the experiment, the proposed method, A2PO, outperforms previous SOTA methods. ", "summary_of_the_review": "This paper proposed a new MARL method and evaluated on some MARL benchmarks. But the improvements are not that satisfactory, ", "strength_and_weaknesses": "Strength:\n1. I admit this paper has good writing and analysis.\n\nWeakness:\n1. The wall time may be increased due to the multiple updates. The authors should compare wall time usage of different methods.\n\n2. The authors try to improve the sample efficiency problem of current MARL algorithms, but the performance improvements are not significant. Reasons below:\n\n- a. The benchmarks are somewhat toy. For instance, SMAC is a well-studied benchmark, many methods have shown performance not worse than A2PO (such as MAT[1]).\n\n- b. The author should consider MARL tasks that are really in the predicament of the sample efficiency, such as multi-agent competitive environments (such as Neural MMO[2]) and multi-agent visual navigation tasks.\n\n\n [1] Wen M, Kuba J G, Lin R, et al. Multi-Agent Reinforcement Learning is a Sequence Modeling Problem[J]. arXiv preprint arXiv:2205.14953, 2022.\n\n [2] Suarez, Joseph, et al. \"The neural mmo platform for massively multiagent research.\" arXiv preprint arXiv:2110.07594 (2021).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MNI3WehF6q", "reviewer": "Reviewer_GN3i", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the sample efficiency and single-agent monotonic improvement guarantees in sequential (agent-by-agent) policy updates in cooperative multi-agent tasks. To retain the guarantees of monotonic improvement for single agent, the authors propose the PreOPC, which approximate the true advantage of an agent. With this single-agent monotonic bound, a tighter joint monotonic bound can be achieved. Then, by optimizing the surrogate objective with the approximated advantage, the authors propose the A2PO algorithm, which achieves better performance with two techniques: semi-greedy agent selection rule and adaptive parameter clipping. Experiments have shown the effectiveness of the proposed algorithm.", "summary_of_the_review": "After reading the paper carefully, I think my comments and recommendation are accurate. ", "strength_and_weaknesses": "Strength:\n1.\tThe paper is well written and well organized.\n\n2.\tThe paper provides the single-agent monotonic bound in the setting with single-rollout and sequential policy update.\n\n3.\tExperimental results are solid.\n\nWeaknesses:\nSome questions:\n1.\tIt seems that the theoretical results are established on the condition that all agents can observe the global state and take this global state as input. I am somewhat unsure whether the theoretical results are fully satisfied by the experiments because in the environments such as SMAC, agents typically have access to local observation.\n\n2.\tRegarding the sequential update scheme, one concern is scalability, though the experiments in this work show that the sequential update scheme has better performance. This is because the update of an agent's policy can be done only when all preceding agents have updated their policies. When facing the settings with a large number of agents, this could be slow compared to simultaneous update schemes such as MAPPO. So, in this sense, I would like to know how long (wall clock time) it takes for the A2PO and other simultaneous update schemes such as MAPPO and CoPPO.\n\n3.\tCan the authors provide more explanations about the assumption on $\\xi^i$ in Theorem 1 and 2? Compared to previous monotonic bounds, A2PO can achieve a tighter bound only given that $\\xi^i$ is small enough. How to ensure this in experiments (please correct me if I have misunderstood or missed something)?\n\n4.\tThough this paper focuses on the policy-based methods, I think some discussion on the value-based methods such as QMIX and its variants is necessary (maybe in the appendix).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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:

Decision: Accept: poster