Coordinated Proximal Policy Optimization
Authors: Zifan Wu
Chao Yu
Deheng Ye
Junge Zhang
haiyin piao
Hankz Hankui Zhuo
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
multiagent Learning
Proximal Policy Optimization
StarCraft

Abstract: We present Coordinated Proximal Policy Optimization (CoPPO), an algorithm that extends the original Proximal Policy Optimization (PPO) to the multi-agent setting. The key idea lies in the coordinated adaptation of step size during the policy update process among multiple agents. We prove the monotonicity of policy improvement when optimizing a theoretically-grounded joint objective, and derive a simplified optimization objective based on a set of approximations. We then interpret that such an objective in CoPPO can achieve dynamic credit assignment among agents, thereby alleviating the high variance issue during the concurrent update of agent policies. Finally, we demonstrate that CoPPO outperforms several strong baselines and is competitive with the latest multi-agent PPO method (i.e. MAPPO) under typical multi-agent settings, including cooperative matrix games and the StarCraft II micromanagement tasks. 

Coordinated Proximal Policy Optimization
Zifan Wu
Chao Yu'
School of Computer Science and Engineering Sun Yat-sen University, Guangzhou, China wuzf50mai12. sysu. edu. cn
School of Computer Science and Engineering Sun Yat-sen University, Guangzhou, China yuchao3@mail, sysu. .tt.smmmmlllsuuu......mmm edu.cn cn
Deheng Ye
Junge Zhang"
Tencent Lab, Shenzhen, China dericye@tencent.com com
Institute of Automation
Chinese Academy of Science, Beijing, China jgzhang@nlpr ia cn
Haiyin Piao
School of Electronic and Information Northwestern Polytechnical University, Xian, China haiyinpiao@mail nwpu. edu. cn
wwpu.edu.com
Hankz Hankui Zhuo
School of Computer Science and Engineering Sun Yat-sen University, Guangzhou, China zhuchank@mail. sysu. edu, cn
Abstract
We present Coordinated Proximal Policy Optimization (CoPPO), an algorithm that extends the original Proximal Policy Optimization (PPO) to the multi- setting. The key idea lies in the coordinated adaptation of step size during the policy update process among multiple agents. We prove the monotonicity of policy improvement when optimizing a wwwrrreicallygrounndee joint objective, and derive a simplified optimization objective based such an objective in CoPPO can achieve dynamic credit assignment among agents, thereby alleviating the high variance issue during the concurrent update of agent policies. Finally, we demonstrate that CoPPO outperforms several strong baselines and is competitive with the latest multi-agent PPO method (i.e. MAPPO) under typical multi-agent settings, including cooperative matrix games and the StarCraft II micromanagement tasks.
of approximations. We then interpret that
1 Introduction
Cooperative Multi-Agent Reinforcement Learning (CoMARL) shows great promise for solving various real-world tasks, such as traffic light control (Wu al.) 2020), sensor network manage- ment (Sharma and Chauhan, 2020) and autonomous vehicle coordination (Yu et al. 2019). In such applications, a team of agents aim to maximize joint expected utility through single global reward. Since multiple agents coexist in common environment and learn and adapt their be- haviour concurrently, the arising non-stationary issue makes difficult to design an efficient learning method (Hernandez-Leal al. 2017 Papoudakis et al. 2019). Recently, a number of CoMARL
"Corresponiigg authors.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

methods based on Centralized Training Decentralized Execution (CTDE) FForster et al. 2016 have
been proposed, including policy-based (Lowe al. 2017 Foerster et al. 2018 Wang al. 2020
Yu et al. 202T) and balue-based methods (Sunehag et al.] 2018 Rashid et al. 2018 8 Son et al. 2019
Mahajan et al. 2019). While generally having more stable convergence properties (Gupta et al. 2017|[Song et 2019 Wang et al. (020) and being naturally suitable for problems with stochastic policies (Deisenroth et al. 2013 Su et al., 202I), policy-based methods still receive less attention from the community and generally possess inferior performance against value-based methods, as evidenced in the StarCraft II benchmark (Samvelyan et al. 2019).
The performance discrepancy between policy-based and value-based methods can be largely attributed to the inadequate utilization of the centralized training procedure in the CTDE paradigm. Unlike value-based methods that directly optimize the policy via centralized training of value functions using extra global information, policy-basede methods only utilize centralized value functions for state/action evaluation such that the policy can be updated to increase the likelihood of generating higher values (Sutton et al. 2000). In other words, there is an update lag between intermediate value functions and the final policy in policy-based methods, and merely coordinating over value functions is insufficient to guarantee satisfactory performance (Grondman et al. 2012 Fujimoto et al. 2018)
To this end, we propose the Coordinated Proximal Policy Optimization (CoPPO) algorithm, multi- agent extension of PPO (Schulman et al. 2017). to directly coordinate over the agents' policies by dynamically adapting the step sizes during the agents" policy update processes. We first prove a relationship between lower bound of joint policy performance and the update of policies. Based on this relationship, a monotonic joint policy improvement can be achieved through optimizing an ideal objective. To improve scalability and credit assignment, and to cope with the potential high variance due to non-stationarity. series of transformations and approximations are then conducted to derive an implementable optimization objective in the final CoPPO algorithm. While originally aiming at monotonic joint policy improvement, CoPPO ultimately realizes direct coordination over the policies at the level of each agent's 's policy update step size. Concretely, by taking other agents' policy update into consideration, CoPPO is able to achieve dynamic credit assignment that helps to indicate a proper update step size to each agent during the optimization procedure. In the empirical study, an extremely hard version of the penalty game (Claus and Boutilier 1998) is used to verify the efficacy and interpretability of CoPPO. In addition, the evaluation on the StarCraft II micromanagement benchmark further demonstrates the superior performance of CoPPO against several strong baselines.
The paper is organized as follows: Section 2 provides a background introduction. Section introduces the derivation process of CoPPO. Section 4
presents the experimental studies, and Section 5 reviews some related works. Finally, Section concludes the paper.
2 Background
We model the fully cooperative MARL problem as a Dec-POMDP (Olichock and Amato 2016) which is defined by a tuple G = (N, S, S2 O, A, R, P... N is the number of agents and S is the set of true states of the environment. Agent i E {1, {I....,Ny N} obtains its partial observation of e Ω according to the observation function (ss, i), where & E Each agent has an action-observation history T' E T = (Ω A)". At each timestep. agent chooses an action a' E A according to its policy π (aa((") and we use a to denote the joint action {a!...., aN}. The environment then returns the reward signal R(s. a) that is shared by all agents, and shifts to the next state according to the transition function P(s (//lls,, a). The joint action-value function induced by a joint policy π is
defined as: Q" (St, 0z)) = E 1:s0 EE==0? Rete (st, az). where E [0, 1) is the discounted factor. We denote the joint action of agents other than agent i as a and π- - -
follow a similar convention. Joint policy ग can be parameterized by {0) ................................ 0 J. where 05 is the parameter set of agent i's policy. Our problem setting follows the CTDE paradigm (Foerster et al. 2016), in which each agent executes its policy conditioned only on the partially observable information, but the policies can be trained centrally by using extra global information.
Value-based MARL In CTDE value-based methods such as (Sunehag et al. 2018 Rashid et al.. 2018. Son et al. 2019 Mahajan et al. 2019), an agent selects its action by performing an arg max operation over the local action-value function, i.c. x (7²) = arg max, Q'(T" a²). Without loss in

---

generality, the update rule for value-based methodd can be formulated as follows:
AP En (R(s,, a) + max Quat a') Qtaa (s.a)) a))
aQior aQu VoLQ(r''a))
(I)
a'
where l¹ represents the parameter of Q', and Qtaa is the global vectio-vvluue function. The centralized training procedure enables balue-based methods to factorize Qeo into some local action-values.
Eq. is essentially Q-learning if rewriting 0Q "Q2"" Vo Q' ( a²) as V Tiot. The partial derivative is
actually a credit assignment term that projects the step size of Qloi to that of Q' (Wang et al. 2020).
Policy-based MARL
In CTDE volicy-baseds methods such (Foerster al.
2018 Lowe et al.
2017 Wang et al. 2020 Yu et al. 2021), an agent selects its action from an explicit policy x [T))
The vanilla multi-agent policy gradient algorithm updates the policy using the following formula:
A x EE [Q Vo
In order to reduce the variance and address the credit assignment issue, COMA (Foerster al., 2018) replace Qeat with the counterfactual advantage: A (s, a) = QT (a Bg [Q" (a'. a ]. This implies that fixing the actions of other agents (i.e. "), an agent will evaluate the action has actually taken (i.e. a²) by comparing with the average effect of other actions it may have taken.
3 Coordinated Proximal Policy Optimization
In policy-based methods, properly limiting the policy update step size proven to be effective in single-agent settings (Schulman et al. 201 2017). In cases when there are multiple policies, it is also crucial for each agent to take other agents update into account when adjusting its own step size. Driven by this insight, propose the CoPPO algorithm to adaptively adjust the step sizes during the update of the policies of multiple agents.
3.1 Monotonic Joint Policy Improvement
The performance of joint policy π is defined as: J(T) = Eawn.s-p" |Er= r RR a)] where p* is the unnormalized discounted visitation frequencies when the joint actions are chosen from æ. Then the difference between the performance of two joint policies, say π and म, can be expressed as the accumulation of the global advantage over timesteps (see Appendix A. for proof):
J(#)= - J(x) = Ea~ #a=p [A (s. a)],
(3)
where A a) - as) - (s) is the joint advantage function. This equation indicates that if the joint policy æ is updated to म. then the performance will improve when the update increases the probability of taking "good" joint actions that Ea #(als) a) 0 for every Modeling the dependency of p* ग involves the complex dynamics of the environment, approach proposed in (Kakade and Langford 2002) to derive an approximation of J(#), denoted as jm (f):
extend the
J=( = J(T) + Ea-t,spp (s,
(4)
Note that if the policy is differentiable, then J= (ft) matches ( to first order (see Appendix A.2 for proof). Quantitatively, we measure the difference between two joint policies using the max- imum total variation divergence (Schulman et al. 201 which is defined by: D [|] max, Drv [-(+ss | [-[s)], where DTv [-]]]
JA (a]s)) म ({a]s) Ida (the definition for the discrete case is simply replacing the integral with a summation, and our results remain valid
in such case). Using the above notations, we can derive the following theorem:
Theorem 1. Let c = max,,a AA a) a V D max (T'
[+). S sis N, and N be the total number of agents, then the error of the approximation Eq. 14 can be explicitly bounded as follows:
1 7 [
(1 0z)
J(F) (+) 4c
(5)
3

---

Proof. See Appendix A.3
As shown above, the upper bound influenced by a;, N and c. By definition, we have a, S 1 and c 0, thus the upper bound will increase when increases for any i, implying that it becomes harder to make precise approximation when any individual of the agents dramatically updates their policies. Also, the growth in the number of agents can raise the difficulty for approximation. As for c, from Eq. 5 we can roughly conclude that larger advantage value can cause higher approximation error, and this reasonable because J approximates J( by approximating the expectation
over A Transforming the inequality in Eq. 5 leads to J ( 2 Ja (
(1-,, -1).
Thus the joint policy can be iteratively updated by:
a4)
7 Fee
arg max
J J ( 4e
(6)
Eq. (6) involves a complete search in the joint observation space and action space for computing and making it difficult to be applied to large-scale settings. In the next subsection, several transformations and approximations are employed to this objective to achieve better scalability.
3.2 The Final Algorithm
Notice that the complexity of optimizing the objective in Eq. (6) mainly lies the second term, ie. 4e [1=111",, (1-a.) 1-7 - 1). While has nothing to do with मं suffices to control this second term only by limiting the variation divergence of agents' policies (i.e. a;). because it increases monotonically a; increases. Then the objective is transformed into J (f) that can be optimized subject to a trust region constraint: a, I 6, i = I,...,N. For higher scalability, as can be replaced by the mean Kullback-Leibee Divergence between agent i's two consecutive policies, i.e. Egppp (+17")
As proposed in (Schulman et al., 2015a), solving the above trust region optimization problem requires repeated computation of Fisher-vector products for each update, which computationally expensive in large-scale problems, especially when there are multiple constraints. In order to reduce the computational complexity and simplify the implementation, importance sampling can be used to incorporate the trust region constraints into the objective of (fF). resulting in the maximization of <<al=)
Ea-soos [min (ota, cllp (rrta 6, + c))] w.r.t ग. where Tota(a[s)- and old (s, a) is denoted A Roia for brevity. The clip function prevents the joint probability ratio from going beyond [1 - c, + c), thus upproximately limiting the variation divergence of the joint policy. Since the policies are independent during the fully decentralized execution, it is reasonable to assume that T (aaTT)
-I, n5 (af(r() Based this factorization, the following objective can be derived:
maximize
Eaw
min
II rd
A A clip
II
.1-61
A
(7)
ON...ON
where 0 is the parameter of agent j's policy, and rd x (a'
While A is defined as Q"T a) (s). the respective contribution of each individual agent cannot be well distinguished. To enable credit assignment, the joint advantage function is decomposed to some local ones of the agents as: A (s,
(a')
Σi=1 e¹ As,s, (a', a)), where At(s, (a', a a)) Q* (s,ssa (a', a-))
EB (a', aadf.aai (a)) is the counterfactual advantage and of is non-negative weight.
During each update, multiple epochs of optimization are performed on this joint objective to improve sample efficiency. Due to the non-negative decomposition of A", there is a monotonic relationship between the global optimum and the local optima, suggesting a transformation from the joint objective to local objectives (see Appendix A.4 for the proof). The optimization of Eq. then can be transformed to maximizing each agent's 's own objective:
(II~ Ut
r r11-e, e, 1. A }.
L (0) = Eg old
min
II Js
r' clip
}
(8)

---

However, the ratio product in Eq. raises potential risk of high variance due to Proposition 1 Proposition 1. Assuming that the agents are fully independent during execution, then the following inequality holds:
Var
II iiti
Var
al [1]]-
iti
Proof. See Appendix A.3
According to the inequality above, the variance of the product grows at least exponentially with the number of agents. Intuitively, the existence of other agents' policies introduces instability in the estimate of each agent's policy gradient. This may further cause suboptimatlity in individual policies due to the centralized-decentralfiee
mismatch issue mentioned in (Wang et al. (020). To be concrete, when A' 0, the external min operation in Eq. can prevent the gradient of L'(6) from exploding
when II +t rd is large, thus limiting the variance raised from other agents; but when A' < 0, the
gradient can grow rapidly in the negative direction, because L'(
[II r2) r when
(IIsx:²) r5) 2 11+.. Moreover, the learning procedure in Eq. can cause a potential exploration issue, that different agents might be granted unequal opportunitres to update their policies. Consider a scenario when the policies of some agents except agent are updated rapidly, and thus the product of these agents' ratios might already be close to the clipping threshold, then small optimization step of agent will cause [[] r² reach the threshold and thus being clipped. In this case, agent i has no chance update its policy, while other agents have updated their policies significantly, leading to unbalanced exploration among the agents. To address the above issues, we propose a double clipping trick modify Eq.
N
(8) follows:
L (0) Earwos {min "o(r~))"" A clip (o(r-'))' - -1,1+ A
(10)
where i)r = clip(I] r9, 1 c2), c2 < G1. In Eq. (8). the existence of 1i imposes an influence the objective of agent through weight of II r5. Therefore, the clipping on IIix:'' r ensures that the influence from the update of other agents on agent i limited to [1 11-62, 62, 1 62]. thus controlling the variance caused by other agents. Note that from the theoretical perspective, clipping separately on each individual probability ratio (i.e. IT clip(r",.,,)) can also reduce the variance. Nevertheless, the empirical results show that clipping separately performs worse than clipping jointly. The detailed results and analysis for this comparison are presented in Appendix [.2.1] In addition, this trick also prevents the update step of each agent from being too small, because r² in Eq. (10) can at least increase I+el,- y or decrease to 1-e2 clipped in each update.
T-er," yd before being
I+te
In the next subsection, we will show that the presence other agents' probability ratio also enables a dynamic credit assignment among the agents in order to promote coordination, and thus the inner clipping threshold (i.e. 62) can actually function as a balance factor to trade off between facilitating coordination and reducing variance, which will be studied empirically in Section 4 A similar trick was proposed in (Ye et al.) 2020aah ()) to handle the variance induced by distributed training in the single-agent setting. Nonetheless, since multiple policies updated in different directions in MARL, the inner clipping here is carried out on the ratio product of other agents instead of the entire ratio product, in order distinguish the update of different agents. The overall CoPPO algorithm with the double clipping trick is shown in Appendix
3.3 Interpretation: Dynamic Credit Assignment
The COMA (Foerster et al. 2018) algorithm tries to address the credit assignment issue in CoMARL using the counterfactual ad advantage. Nevertheless, miscoordination and suboptimatlity can still arise since the credit assignment in COMA conditioned on the fixed actions of other agents, but these actions are continuously changing and thus cannot precisely represent the actual policies. While CoPPO also makes use of the counterfactual advantage, the overall update of other agents taken into account dynamically during the multiple epochs in each update. This process can adjust the
5

---

advantage value in a coordinated manner and alleviate the miscoordination issue caused by the fixation of other agents' joint action. Note that the theoretical reasoning for CoPPO in Section[3.] and 3.2 originally aims at monotonic joint policy improvement, yet the resulted objective ultimately realizes coordination among agents through a dynamic credit assignment among the agents in terms of coordinating over the step sizes of the agents' policies.
To illustrate the efficacy of this dynamic credit assignment, we make an analysis on the difference between CoPPO and MAPPO (Yu et al. (02T) which generalizes PPO to multi- agent settings simply by centralizing the value functions with an optimization objective of Exaia [min A clip (rk. -, c, +c]l which is a lower bound of Exai [r where ri rep- resents the probability ratio of agent i at the kyt optimization epoch during each update. De- noting (II r2)
A as Ai. the CoPPO objective then becomes approximately lower bound
of E Eru [rt A3 The discussion then can be simplified to analyzing the two lower bounds (see Appendix A.6 for the details of this simplification).
Depending on whether A' > 0 and whether [ r > 1, four different cases can be classified. For brevity, only two of them are discussed below while the rest are similar. The initial parameters of the two methods are assumed to be the same.
Case (1): A' > O, I1 r > 1. In this case | | thus ||A] Vrill > | indicating that CoPPO takes a larger update step towards increasing x' ra' than MAPPO does. Concretely, A > means that at is considered (by agent i) positive for the whole team when fixing a -1 and under similar observations. Meanwhile, I1 r > 1 implies that after this update epoch, a - are overall more likely be performed by the other agents when encountering similar observations (see Appendix A.7 for the details). This makes fixing a= more reasonable when estimating the advantage of a', thus explaining CoPPO's 's confidence to take a larger update step.
Case (2): A O, I1 Th < 1. Similarly, in this case | < | and hence || Vrill < | indicating that CoPPO takes a smaller update step to decrease T4' (a*()z)) than MAPPO does. To be specific, at is considered (by agent i) to have a negative effect on the whole team since A' < 0, and |1 - < 1 suggests that after this optimization epoch, other agents are overall less likely to perform ai given similar observations. While the evaluation of a² is conditioned on a a-i, it is reasonable for agent to rethink the effect of a' and slow down the update of decreasing the probability of taking a', thus giving more chance for this action to be evaluated.
It is worth noting that Aj. continues changing throughout the K epochs of update and yields dynamic adjustments in the step size, while A' will remain the same during each update. Therefore, Až can be interpreted dynamic modification of A by taking other agents' update into consideration.
Experiments
In this section, we evaluate CoPPO modified matrix penalty game and the StarCraft Multi- Agent Challenge (SMAC) (Samvelyan et al., 2019). The matrix game results enable interpretative observations, while the evaluations SMAC verivy the efficacy of CoPPO in more complex domains.
4.1 Cooperative Matrix Penalty Game
The penalty game is a representative of problems with miscoordination penalties and multiple equiliriia selection among optimal joint actions. It has been used as a challenging test bed for evaluating CoMARL algorithms (Claus and Boutilier] 1998] Spiros and Daniel, 2002). To further increase the difficulty of achieving coordination, we modily the two-player penalty game to four agents with nine actions for each agent. The agents will receive a team reward of 50 when they have played the same action, but be punished by -50 if any three agents have acted the same while the other does not. In all other cases, the reward is -40 for all the agents. The penalty game provides a verifying metaphor to show the importance of adaptive adjustment in the agent policies in order to achieve efficient coordinated behaviors. Thinking of the case when the agents have almost reached one of the optimal joint actions, yet at the current step they have received a miscoordination penalty due to the exploration of an arbitrary agent. Then smaller update steps for the three matching agents

---

would benefit the coordinated learning process of the whole group, since agreement on this optimal joint action would be much easier to be reached than any other optimal joint actions. Therefore. adaptively coordinating over the agent policies and properly assigning credits among the agents are crucial for the agents achieve efficient coordination in this kind of game.
CaPPOlours)
COMA
MAPPO
DOP
Avecage
Acorge Abatagg
-0.10
20
400
70
Variation of Average Adva witir K Epocchs
Grudient Variance
Goddent
Figure 1: Upper left: average rewards; Upper right: average advantages after penalty; Lower left: the variation of the average advantages within K (here K = 8) optimization epochs every time after a penalty; Lower right: running policy gradient variance.
We train CoPPO. COMA (Foerster al., 2018), MAPPO (Yu al., (021) and DOP (Wang et al.. 2020) for 10,000 timesteps, and the final results are averaged over 100 runs. The hyperparameters and other implementation details are described Appendix C.I From Fig. [ppee left, we can see that CoPPO significantly outperforms other methods in terms of average rewards. Fig. upper right presents an explanation the result by showing the local advantages averaged among the three matching agents every time after receiving miscoordination penalty. Each point the horizontal axis represents a time step after a miscoordination penalty. While the times of penalties in single run vary for different algorithms, vertical axis represents
take the minimum times of 70 over all runs. The Σjæs A' for COMA, MAPPO and DOP, and represents the mean of K epochs during one update, i.c., Y E A k E AV., for CoPPO (i indicates the unmatching agent). Note that CoPPO can obtain the smallest local advantages that are close to compared other methods, indicating the smallest step sizes for the three agents in the direction of changing the current action. Fig. D lower left shows the overall variation of the average advantages within K optimization epochs after receiving a miscoordination penalty. We can see that as the number of epochs increases, the absolute value of the average advantage of the three matching agents gradually decreases by considering the update of other agents. Since the absolute value actually determines the step size of update, smaller value indicates a small adaptation in their current actions. This is consistent with what we have discussed in Section 3.3 Fig. lower right further implies that through this dynamic process, the agents succeed in learning to coordinate their update steps carefully, yielding the smallest gradient variance among the four methods.
Ablation study Fig. provides an ablation study of the double clipping trick. We can see that a proper intermediate inner clipping threshold improves the global performance, and the double clipping trick indeed reduces the variance of the policy gradient. In contrast to DOP, which achieves low gradient variance at the expense of lack direct coordination over the policies, CoPPO can strike a nice balance between reducing variance and achieving coordination, by taking other agents' policy update into consideration. To make our results more convincing, experiments on more cooperative matrix games with different varieties are also conducted in Appendix D.I
7

---

0.10
0.05
0.15
withoud DC
Performanc
Guadiett Varianee
Anange Thearr
Cradent
710)
Figure 2: Ablation study the double clipping trick. The numbers 0.05, 0.10, 0.15 represent the inner clipping threshold, and "without DC" represents the case when the trick is not used. Left: average rewards; Right: running policy gradient variance.
4.2 StarCraft IT
We evaluate CoPPO in SMAC against various state-of-the-art methods, including policy-based meth- ods (COMA (Foerster et al.) 2018), MAPPO YYu al. (021) and DOP (Wang et al. 20200) and value-based methods (QMIX Rashid et al. 2018) and QTRAN (Son et al.) 2019p). The implemen- tation of these baselines follows the original versions. The win rates are tested over evaluation episodes after each training iteration. The hyperparameter settings and other implementation details are presented in Appendix C.2 The results are averaged over different random seeds for easy maps (the upper row in Fig. 3 and 8 different random seeds for harder maps (the lower row in Fig. 3). Note that CoPPO outperforms several strong baselines including the latest multi-agent PPO (i.e., MAPPO) method in SMAC across various types and difficulties, especially in Hard (3s5z, 10m vs 11m) and Super Hard (MMM2) maps. Moreover, as an on on-policy method, CoPPO shows better stability across different runs, which is indicated by narrower confidence interval around the learning curves.
CoPPO(ours
COMA
CTRAAN
So 19.99... 3c
2r3z
1ch05z
0.5
10m,
104
100
130
75.
1089
1000
Figure 3: Comparisons against baselines on SMACC
The first row in Fig. 4 shows the ablation study of double clipping in SMAC, and we can see that the results share the same pattern as in Section 4.1
Ablation study 2
Ablation study In Section 3.2 the global advantage is decomposed into a weighted sum of local advantages. We also compare it to mixing network with non-negative weights and the results are shown in Fig. 4 Similar to QMIX (Rashid al. 2018), the effectiveness of the mixing network may largely owe the improvement in the representational ability for the global advantage function.
8

---

305
03
1.5
1300
7740
Figure 4: Ablation studies the double clipping (the upper row) and the way of advantage decomposition (the maps respectively. In the upper row, the numbers "0.05, 0.10, 0.15" represent the
lower row), evaluated values inner clipping threshold, and "without DC represents the case where the double clipping trick not utilized. the lower row, "Amix" refers to non-negative-weiihte neural network, and "Asum" refers to an arithmetic summation.
Related Work
In recent years, there has been significant progress in CoMARL, Fully centralized methods suffer from scalability issues due to the exponential growth of joint action space, and applying DQN to each agent independently while treating the other agents part of environment (Tampuu et al. 2017) suffers from the non-statee non-stationary issue (Hernandez- Leal et al. 2017: Papoudakis et al., 2019). The CTDE paradigm (Foerster et al. 2016) reaches compromise between centralized and decentralized approaches, assuming a laboratory setting where each agent's 's policy can be trained using extra global information while maintaining scalable decentralized execution.
series of work have been developed in the CTDE setting, including both value-based and policy- based methods. Most of the aalue-based MARL methods estimate joint action-value function by mixing local value functions. VDN (Sunehag et al., 2018) first introduces value decomposition to make the advantage of centralized training and mixes the local value functions via arithmetic summation. To improve
representational ability the joint action-value function, QMIX (Rashid) neural
et al. 2018) proposes to mix the local action-valus functions via non--negatie-weigheee network. QTRAN (Son et al., 2019) studies the decentralization & suboptimatlity trade-off and introduces corresponding penalty term in the objective to handle it, which further enlarges the class of representable value functions. As for the policy-based methods, COMA (Foerster et al. 2018) presents the counterfactual advantage to address the credit assignment issue. MADDPG (Lowe et al. 2017) extends DDPG (Lillicrap et al.) 2015) by learning centralized value functions which are conditioned additional global information, such other agents' actions. DOP (Wang al. 2020)
introduces value decomposition into the multi-agent actor-critic framework, which enables off-policy
critic learning and addresses the sentralized-ddeeentaaiiiee mismatch issue. MAPPO (Yu al. 2021
generalizes PPO (Schulman et al. 2017) to multi-agent settings using global value function.
The most relevant works MAPPO Yu et al. 2021). MATRPO (Li and He 2020) and MATRL (Wen et al. 2020). MAPPO extends PPO to multi-agens settings simply by centralizing the critics.
With additional techniques such as Value Normalization, MAPPO achieves promising performance compared to several strong baselines. Note that our implementation built on the one of MAPPO (please refer to Appendix C.2 for more details).
As for MATRPO and MATRL, they both try to extend TRPO (Schulman et al. 2015a) to multi-agent settings. MATRPO focuses on fully decentralized training, which is realized through splitting the joint TRPO objective into N independent parts for each agent and transforming into consensus optimization problem; while MATRL computes independent trust regions for each agent assuming

---

that other agents' policies are fixed, and then solves a meta- game in order to find the best response to the predicted joint policy of other agents derived by independent trust region optimization. Dif- ferent from our work, they adopt the settings where agents have separate local reward signals. By comparison, CoPPO does not directly optimize the constrained objective derived in Section but instead incorporates the trust region constraint into the optimization objective, in order to reduce the computational complexity and simplify the implementation. CoPPO can sufficiently take advantage of the centralized training and enable coordinated adaptation of step size among agents during the policy update process.
Conclusion
In this paper, we extend the PPO algorithm to the multi-agent setting and propose an algorithm named CoPPO through a theoretically-goondde derivation that ensures approximately monotonic policy improvement. CoPPO can properly address the issues of scalability and credit assignment, which is interpreted both theoretically and empirically. We also introduce double clipping trick strike the balance between reducing variance and achieving coordination by considering other agents' update. Experiments on specially designed cooperative matrix games and the SMAC benchmark verify that CoPPO outperforms several strong baselines and is competitive with the latest multi-agent methods.
Acknowledgments and Disclosure of Funding
The work is supported by the National Natural Science Foundation of China (No. 62076259 and No. 62076263) and the Tencent AI Lab Rhino-Bing Focused Research Program (No. JR202063). The authors would like to thank Wenxuan Zhu for pointing out of the mistakes in the proof, Xingzhou Lou and Xianjie Zhang for running some of the experiments, as well as Siling Chen for proofreading the manuscript. Finally, the reviewers and metareviewer are highly appreciated for their constructive feedback on the paper.
References
Tong Wu, Pan Zhou, Kai Liu, Yali Yuan, Xiumin Wang, Huawei Huang, and Dapeng Oliver Wu. Multi-agent deep reinforcement learning for urban traffic light control in vehicular networks. IEEE Transactions Vehicular Technology, 69(8):8243 8256, 2020.
Anamika Sharma and Siddhartha Chauhan. A distributed reinforcement learning based sensor node scheduling algorithm for coverage and connectivity maintenance wireless sensor network. Wireless Networks, 26(6):441 4-29, 2020.
Chao Yu, Xin Wang, Xin Xu, Minjie Zhang. Hongwei Ge, Jiankang Ren, Liang Sun, Bingcai Chen, and Guozhen Tan. Distributed multiagent coordinated learning for autonomous driving highways based on dynamic coordination graphs. IEEE Transactions on Intelligent Transportation Systems, 21(2):735-748, 2019.
Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A survey of learning in multiagent environments: Dealing with non-stationarity. ArXiv, 0bs//707.09183. 2017.
Georgios Papoudakis, Filippos Christianos, Arrasy Rahman, and Stefano V. Albrecht. Dealing with non-stationarity in multi-agent deep reinforcement learning. arXiv preprint arXiv: 1rX.iv/906..00 1906.04737 2019.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 29:2137-22 145, 2016.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettiiv environments. Advances in Neural Information Processing Systems, 30:6379-6390, 2017.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the Conference of Association for the Advancement of Artificial Intelligence, volume 32, page 2974-2982, 2018.
10

---

Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Dop: Off--o multi- agent decomposed policy gradients. International Conference on Learning Representations. 2020.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang. A. Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. ArXiv, abs/2103.01955 2021.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative mullii-agnn learning based on team reward. In International Conference on Autonomous Agents and MultiAgent Systems, pages 2085-2087, 2018.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4304, 2018.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5887-5896, 2019.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. Advances in Neural Information Processing Systems, 32:7613-7624, 2019.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pages 66 83, 2017.
Xinliang Song, Tonghan Wang, and Chongjie Zhang. Convergence of multi-agent learning with a finite step size in general-sum games. In International Conference Autonomous Agents and MultiAgent Systems, pages 935-999999 335-943, 2019.
Mare Peter Deisenroth, Gerhard Neumann, Jan Peters, et al. A survey on policy search for robotics. Foundations and trends in Robotics, 2(1-2):388-433, 2013.
Jianyu Su, Stephen Adams, and Peter Beling. Value-decomposition multi-agent actor-critics. In Proceedings of the Conference of Association for the Advancement of Artificial Intelligence, volume 35, pages 11352-11360, 2021.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. In International Conference on Autonomous Agents and MultiAgent Systems, pages 2186-20 11866-2188, 2188, 2019.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pages 1057-1063, 2000.
Ivo Grondman, Lucian Busoniu, Gabriel AD Lopes, and Robert Babuska. A survey of actor-critic reinforcement learning: Standard and natural policy gradients. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 1296)112 2012.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-
critic methods. In International Conference Machine Learning, pages 1587-1596, 2018.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abss/1707.06l 06007,2277,7
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. Proceedings of the fifteenth national/tenth conference on Artificial inteliggence/mnovaaivee applications of artificial intelligence, 1998(746-752);,, 1998.
Frans A Oliehoek and Christopher Amato, A concise introduction to decentralized POMDPs. Springer, 2016.

---

John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1889-1897, 2015a.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference Machine Learning, pages 267-274, 2002.
Deheng Ye, Zhao Liu, Mingfei Sun, Bei Shi, Peilin Zhao, Hao Wu, Hongsheng Yu, Shaojie Yang, Xipeng Wu, Qingwei Guo, et al. Mastering complex control in moba games with deep reinforce- ment learning. In Proceedings of the Conference Association for the Advancement of Artificial Intelligence, pages 6672-6679, 2020a.
Deheng Ye, Guibin Chen, Wen Zhang. Sheng Chen, Bo Yuan, Bo Liu, Jia Chen, Zhao Liu, Fuhao Qiu, Hongsheng Yu, Yinyuting Yin, Bei Shi, Liang Wang, Tengfei Shi, Qiang Fu, Wei Yang, Lanxiao Huang, and Wei Liu. Towards playing full MOBA games with deep reinforcement learning. In Advances in Neural Information Processing Systems, pages 21 632, 2020b.
Spiros and K Daniel. Reinforcement learning of coordination in cooperative mas. The 18th National Conference on Artificial Intelligence, pages 326-331, 2002.
Ardi Tampuu, Tambet Matüien, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent cooperation and competition with deep reinforcement learning. PloS one, 12(4)=e0172395, 2017.
Timothy Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint ar arXiv:1509. 02977,, 2015.
Hepeng Li and Haibo He. Multi-agent trust region policy optimization. ArXiv, abs/2010.07996,,2200
Ying Wen, Hui Chen, Yaodong Yang, Zheng Tian, Minne Li, Xu Chen, and Jun Wang. Multi-agent trust region learning. 2020.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
David Pollard. Asymptopia: an exposition of statistical asymptotic theory. 2000. URL http: h/www.statt yaapl./ccc//ooooaar/////////pppp
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv: 15Xx::5506.02338 2015b.
12


Reviews:
[{"review_id": "zJeHnFXlTMU", "reviewer": "Reviewer_yRTL", "summary": "This paper presents a multi-agent generalization of proximal policy optimization algorithm (PPO) (Schulman'17). The authors provide monotonic policy improvement guarantee and use double clipping technique (Ye'20) in order to mitigate the exploration issues caused by multiplication of importance weights in off-policy sampling. They also interpret this objective function as dynamic credit assignment among agents which can reduce the variance in update. They test the proposed approach on cooperative matrix game and Starcraft tasks to show its outperformance over other multi agent RL algorithms.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The flow of the paper is nice and readable. The idea of the paper on multi agent RL with PPO is interesting as well.  \nIn summary, I see this paper as combination PPO and double clipping technique(Ye'20) in multiagents. Because the derivations are pretty straightforward and similar to  TRPO and PPO papers. Overall, The results are nice but not surprising at all. \nSome questions:\nDoes double clipping affect the convergence or policy improvement lemma? Can clipping be applied separately to each importance weight to avoid the problem?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "p4yjsL0hdOO", "reviewer": "Reviewer_ubaz", "summary": "This paper proposes the coordinated proximal policy optimization (CoPPO) algorithm for cooperative multi-agent systems. CoPPO is a novel algorithm with centralized training and decentralized execution (CTDE) which achieves better coordination between agents via a coordinated adapting process of the agents' step size when updating policies. The empirical results in penalty games and SMAC show that CoPPO outperforms the SOTA algorithms such as MAPPO and DOP.", "questions": "", "limitations": "", "rating": 6, "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": "The paper is technically sound and well written. I think it is a good paper. However, I still have one concern which I think is quite important for making the final decision: Why did the author only run 6 maps in the SMAC experiments? Why not compare the algorithms in more SMAC maps such as MMM, MMM2, 10m_vs_11m?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "6Hm3ywN6km", "reviewer": "Reviewer_iDqu", "summary": "This paper proposes a new CTDE algorithm CoPPO for cooperative MARL. CoPPO is based on the extended objective of TRPO in MARL settings. CoPPO uses the clip objective of PPO to implement the trust region constraint of TRPO and proposes a double clipping trick to adjust the step sizes of different agents.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The double clip trick is interesting, and it also has the efficacy of dynamic credit assignment. However, I have the following concerns.\n\n1. The objective of CoPPO is actually a direct extension of TRPO in multi-agent settings. If we take a centralized view, suppose the policies of agents are mutually independent, following the conclusion of TRPO, we can direct derive the same result. So the main contribution of this paper may lie in the double clipping trick for optimizing the objective. \n\n2. The paper is unclear in many ways  at least from the writing. For example, is a joint Q(s,a)  learned to compute A^i? where does c^i come from? \n\n3. Morever, the empirical results on SMAC maps seem to have some problems. The performance of MAPPO in the Hard and Super Hard maps are much lower than the results in the Table 1 in the original paper of MAPPO. And the learning curves of MAPPO in these maps are different with the original paper. \n\n4. Moreover, the performance of CoPPO in these maps is lower than the results of MAPPO in the original paper.\n\nI expect these concerns can be addressed during rebuttal. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As stated above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "0ULihdI_-U_", "reviewer": "Reviewer_A4sq", "summary": "This work presents an extension of the popular proximal policy optimization (PPO) algorithm for cooperative multi-agent tasks.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n* The proposed method falls into a promising direction for cooperative MARL methods. Much of the focus in this field has been in value-based methods, but simple extensions of single-agent policy-optimization methods have recently been shown to be competitive with the SOTA value-based ones. As such, this work is timely.\n* The exposition is clear and succinct. Theoretical contributions are well motivated and explained intuitively.\n* The expected baselines are present in the experiments, and the proposed method reliably outperforms them.\n\n# Weaknesses\nI don't believe the paper has any serious shortcomings, though there are a few minor points that could be addressed.\n* The colors should be consistent in Figures 1 and 2. In other words, whichever setting for the inner clipping threshold that is used in Figure 1 should be blue in figure 2. Perhaps the other settings should use colors or line patterns that aren't used in figure 1.\n* It would be good to see how CoPPO performs in more of the Hard and (especially) Super Hard tasks from SMAC. The MAPPO paper performs experiments on the whole set of tasks.\n\n# Overall Thoughts\nThis paper is a well thought out and sensible follow up to recent works which show the relatively untapped potential of policy-based methods for cooperative MARL.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "On the subset of tasks from SMAC selected for experimentation, the proposed methods performs well. I imagine that on at least some tasks from SMAC, the proposed method does not outperform the baselines, so it would be good to know what these are and what the authors' hypotheses are for the lack of improvement in those settings , if they exist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and AC discussed the paper. There was agreement that the approach is interesting and the results are impressive. The author response was also helpful in addressing some of the concerns of the reviewers (e.g., additional experimental results). There are still some concerns about the novelty of the approach and the comparisons with MAPPO. These should be clarified. 
Decision: Accept (Poster)