Coordinated Proximal Policy Optimization

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.

heading: 1 Introduction
text: Cooperative Multi-Agent Reinforcement Learning (CoMARL) shows great promise for solving various real-world tasks, such as traffic light control (Wu et al., 2020), sensor network management (Sharma and Chauhan, 2020) and autonomous vehicle coordination (Yu et al., 2019). In such applications, a team of agents aim to maximize a joint expected utility through a single global reward. Since multiple agents coexist in a common environment and learn and adapt their behaviour concurrently, the arising non-stationary issue makes it difficult to design an efficient learning method (Hernandez-Leal et al., 2017; Papoudakis et al., 2019). Recently, a number of CoMARL
∗Corresponding authors.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
methods based on Centralized Training Decentralized Execution (CTDE) (Foerster et al., 2016) have been proposed, including policy-based (Lowe et al., 2017; Foerster et al., 2018; Wang et al., 2020; Yu et al., 2021) and value-based methods (Sunehag et al., 2018; Rashid et al., 2018; Son et al., 2019; Mahajan et al., 2019). While generally having more stable convergence properties (Gupta et al., 2017; Song et al., 2019; Wang et al., 2020) and being naturally suitable for problems with stochastic policies (Deisenroth et al., 2013; Su et al., 2021), 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-based 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, a multiagent 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 a 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, a 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 a direct coordination over the policies at the level of each agent’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 3 introduces the derivation process of CoPPO. Section 4 presents the experimental studies, and Section 5 reviews some related works. Finally, Section 6 concludes the paper.

heading: 2 Background
text: We model the fully cooperative MARL problem as a Dec-POMDP (Oliehoek and Amato, 2016) which is defined by a tuple G = 〈N,S,Ω, O,A,R, P, γ〉. N is the number of agents and S is the set of true states of the environment. Agent i ∈ {1, . . . , N} obtains its partial observation oi ∈ Ω according to the observation function O(s, i), where s ∈ S. Each agent has an action-observation history τ i ∈ T ≡ (Ω × A)∗. At each timestep, agent i chooses an action ai ∈ A according to its policy π(ai|τ i), and we use a to denote the joint action {a1, . . . , 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′|s,a). The joint action-value function induced by a joint policy π is defined as: Qπ(st,at) = Est+1:∞,at+1:∞ [ ∑∞ t′=0 γ
t′Rt+t′ |st,at], where γ ∈ [0, 1) is the discounted factor. We denote the joint action of agents other than agent i as a−i, and π−i, τ−i follow a similar convention. Joint policy π can be parameterized by θ = {θ1, . . . , θN}, where θi 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.e. πi(τ i) = arg maxai Q i(τ i, ai). Without loss in
generality, the update rule for value-based methods can be formulated as follows: ∆θi ∝ Eπ [( R(s,a) + max
a′ Qtot(s,a′)−Qtot(s,a) ) ∂Qtot ∂Qi ∇θiQi(τ i, ai) ] , (1)
where θi represents the parameter of Qi, and Qtot is the global action-value function. The centralized training procedure enables value-based methods to factorize Qtot into some local action-values. Eq. (1) is essentially Q-learning if rewriting ∂Q tot
∂Qi ∇θiQ i(τ i, ai) as∇θiQtot. The partial derivative is
actually a credit assignment term that projects the step size of Qtot to that of Qi (Wang et al., 2020).
Policy-based MARL In CTDE policy-based methods such as (Foerster et al., 2018; Lowe et al., 2017; Wang et al., 2020; Yu et al., 2021), an agent selects its action from an explicit policy πi(ai|τ i). The vanilla multi-agent policy gradient algorithm updates the policy using the following formula:
∆θi ∝ Eπ [ Qtotπ (s,a)∇θiπi(ai|τ i) ] . (2)
In order to reduce the variance and address the credit assignment issue, COMA (Foerster et al., 2018) replace Qtot with the counterfactual advantage: Aπ(s,a) = Qπ(s, (ai,a−i)) − Eâi∼πi [Qπ(s, (âi,a−i))]. This implies that fixing the actions of other agents (i.e. a−i), an agent will evaluate the action it has actually taken (i.e. ai) by comparing with the average effect of other actions it may have taken.

heading: 3 Coordinated Proximal Policy Optimization
text: In policy-based methods, properly limiting the policy update step size is proven to be effective in single-agent settings (Schulman et al., 2015a, 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, we propose the CoPPO algorithm to adaptively adjust the step sizes during the update of the policies of multiple agents.

heading: 3.1 Monotonic Joint Policy Improvement
text: The performance of joint policy π is defined as: J(π) .= Ea∼π,s∼ρπ [ ∑∞ t=0 γ
tRt+1(s,a)] , where ρπ 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.1 for proof):
J(π̃)− J(π) = Ea∼π̃,s∼ρπ̃ [Aπ(s,a)] , (3) where Aπ(s,a) = Qπ(s,a)− V π(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 so that ∑ a π̃(a|s)Aπ(s,a) > 0 for every s. Modeling the dependency of ρπ̃ on π̃ involves the complex dynamics of the environment, so we extend the approach proposed in (Kakade and Langford, 2002) to derive an approximation of J(π̃), denoted as J̃π(π̃):
J̃π(π̃) . = J(π) + Ea∼π̃,s∼ρπ [Aπ(s,a)] . (4)
Note that if the policy is differentiable, then J̃π(π̃) matches J(π̃) to first order (see Appendix A.2 for proof). Quantitatively, we measure the difference between two joint policies using the maximum total variation divergence (Schulman et al., 2015a), which is defined by: DmaxTV [π‖π̃] . =
maxsDTV [π(·|s)‖π̃(·|s)], where DTV [π(·|s)‖π̃(·|s)] = 12 ∫ A |π(a|s) − π̃(a|s)|da (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 = maxs,a |Aπ(s,a)| , αi = √ 1 2D max TV [π
i||π̃i], 1 ≤ i ≤ N , and N be the total number of agents, then the error of the approximation in Eq. (4) can be explicitly bounded as follows:
∣∣∣J(π̃)− J̃π(π̃)∣∣∣ ≤ 4 [1− γ∏Ni=1(1− αi) 1− γ − 1 ] . (5)
Proof. See Appendix A.3.
As shown above, the upper bound is influenced by αi, N and . By definition, we have αi ≤ 1 and ≥ 0, thus the upper bound will increase when αi 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 , from Eq. (5) we can roughly conclude that a larger advantage value can cause higher approximation error, and this is reasonable because J̃π(π̃) approximates J(π̃) by approximating the expectation
over Aπ . Transforming the inequality in Eq. (5) leads to J(π̃) ≥ J̃π(π̃)−4 ( 1−γ ∏N i=1(1−αi) 1−γ − 1 ) . Thus the joint policy can be iteratively updated by:
πnew = arg max π̃
[ J̃πold(π̃)− 4 ( 1− γ ∏N i=1(1− αi)
1− γ − 1
)] . (6)
Eq. (6) involves a complete search in the joint observation space and action space for computing and αi, 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.

heading: 3.2 The Final Algorithm
text: Notice that the complexity of optimizing the objective in Eq. (6) mainly lies in the second term, i.e. 4
( 1−γ
∏N i=1(1−αi) 1−γ − 1 ) . While has nothing to do with π̃, it suffices to control this second
term only by limiting the variation divergence of agents’ policies (i.e. αi), because it increases monotonically as αi increases. Then the objective is transformed into J̃πold(π̃) that can be optimized subject to a trust region constraint: αi ≤ δ, i = 1, . . . , N . For higher scalability, αi can be replaced by the mean Kullback-Leibler Divergence between agent i’s two consecutive policies, i.e. Es∼ρπ [ DKL[π i(·|τ i)||π̃i(·|τ i)] ] .
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 is 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 J̃πold(π̃), resulting in the maximization of Ea∼πold [min (rAπold , clip (rAπold , 1− , 1 + ))] w.r.t π, where r = π(a|s) πold(a|s) , and A πold(s,a) is denoted as Aπold for brevity. The clip function prevents the joint probability ratio from going beyond [1− , 1 + ], thus approximately limiting the variation divergence of the joint policy. Since the policies are independent during the fully decentralized execution, it is reasonable to assume that π(a|τ ) = ∏N i=1 π i(ai|τ i). Based on this factorization, the following objective can be derived:
maximize θ1,...,θN Ea∼πold min  N∏
j=1
rj Aπ, clip  N∏
j=1
rj  , 1− , 1 + Aπ  , (7) where θj is the parameter of agent j’s policy, and rj =
πj(aj |τj ;θj) πjold(aj |τj ;θ j old) . While Aπ is defined as
Qπ(s,a)− V π(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) = ∑N i=1 c
i · Ai(s, (ai,a−i)), where Ai(s, (ai,a−i)) = Qπ(s, (ai,a−i)) − Eâi [Qπ(s, (âi,a−i))] is the counterfactual advantage and ci is a 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. (7) then can be transformed to maximizing each agent’s own objective:
Li(θ) = Ea∼πold min ∏
j 6=i
rj  riAi, clip ∏
j 6=i
rj  ri, 1− , 1 + Ai  . (8)
However, the ratio product in Eq. (8) raises a 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:
Vara−i∼π−iold ∏ j 6=i rj  ≥∏ j 6=i Varaj∼πjold [ rj ] . (9)
Proof. See Appendix A.5.
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-decentralized mismatch issue mentioned in (Wang et al., 2020). To be concrete, when Ai > 0, the external min operation in Eq. (8) can prevent the gradient of Li(θ) from exploding when ∏ j 6=i r j is large, thus limiting the variance raised from other agents; but when Ai < 0, the
gradient can grow rapidly in the negative direction, because Li(θ) = E [(∏ j 6=i r j ) riAi ] when(∏
j 6=i r j ) ri ≥ 1 + . Moreover, the learning procedure in Eq. (8) can cause a potential exploration issue, that is, different agents might be granted unequal opportunities to update their policies. Consider a scenario when the policies of some agents except agent i are updated rapidly, and thus the product of these agents’ ratios might already be close to the clipping threshold, then a small optimization step of agent i will cause ∏N j=1 r
j to reach the threshold and thus being clipped. In this case, agent i has no chance to 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 to modify Eq. (8) as follows:
Li(θ) = Ea∼πold { min [ g(r−i)riAi, clip ( g(r−i)ri, 1− 1, 1 + 1 ) Ai ]} , (10)
where g(r−i) = clip (∏
j 6=i r j , 1 − 2, 1 + 2 ) , 2 < 1. In Eq. (8), the existence of ∏ j 6=i r j
imposes an influence on the objective of agent i through a weight of ∏ j 6=i r
j . Therefore, the clipping on ∏ j 6=i r
j ensures that the influence from the update of other agents on agent i is limited to [1− 2, 1 + 2], thus controlling the variance caused by other agents. Note that from the theoretical perspective, clipping separately on each individual probability ratio (i.e. ∏N j=1 clip(r
j , ·, ·)) 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 D.2.1. In addition, this trick also prevents the update step of each agent from being too small, because ri in Eq. (10) can at least increase to 1+ 11+ 2 r i or decrease to 1− 11− 2 r i before being clipped in each update.
In the next subsection, we will show that the presence of 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. 2) 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., 2020a,b) to handle the variance induced by distributed training in the single-agent setting. Nonetheless, since multiple policies are 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 to distinguish the update of different agents. The overall CoPPO algorithm with the double clipping trick is shown in Appendix B.

heading: 3.3 Interpretation: Dynamic Credit Assignment
text: The COMA (Foerster et al., 2018) algorithm tries to address the credit assignment issue in CoMARL using the counterfactual advantage. Nevertheless, miscoordination and suboptimatlity can still arise since the credit assignment in COMA is 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 is taken into account dynamically during the multiple epochs in each update. This process can adjust the
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.1 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., 2021) which generalizes PPO to multiagent settings simply by centralizing the value functions with an optimization objective of Eπold [ min [ rikA i, clip ( rik, 1− , 1 + )]] , which is a lower bound of Eπold [ rikA i ]
where rik represents the probability ratio of agent i at the kth optimization epoch during each update. Denoting (∏ j 6=i r j k ) Ai as Ãik, the CoPPO objective then becomes approximately a lower bound
of Eπold [ rikÃ i k ] . 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 Ai > 0 and whether ∏ j 6=i r j k > 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): Ai > 0, ∏ j 6=i r j k > 1. In this case ∣∣Ãik∣∣ > ∣∣Ai∣∣, thus ∥∥Ãik∇rik∥∥ > ∥∥Ai∇rik∥∥, indicating that CoPPO takes a larger update step towards increasing πi(ai|τ i) than MAPPO does. Concretely, Ai > 0 means that ai is considered (by agent i) positive for the whole team when fixing a−i and under similar observations. Meanwhile, ∏ j 6=i r j k > 1 implies that after this update epoch, a
−i are overall more likely to be performed by the other agents when encountering similar observations (see Appendix A.7 for the details). This makes fixing a−i more reasonable when estimating the advantage of ai, thus explaining CoPPO’s confidence to take a larger update step.
Case (2): Ai < 0, ∏ j 6=i r j k < 1. Similarly, in this case ∣∣Ãik∣∣ < ∣∣Ai∣∣ and hence ∥∥Ãik∇rik∥∥ <∥∥Ai∇rik∥∥, indicating that CoPPO takes a smaller update step to decrease πi(ai|τ i) than MAPPO does. To be specific, ai is considered (by agent i) to have a negative effect on the whole team since Ai < 0, and ∏ j 6=i r j k < 1 suggests that after this optimization epoch, other agents are overall less likely to perform a−i given similar observations. While the evaluation of ai is conditioned on a−i, it is reasonable for agent i to rethink the effect of ai and slow down the update of decreasing the probability of taking ai, thus giving more chance for this action to be evaluated.
It is worth noting that Ãik continues changing throughout the K epochs of update and yields dynamic adjustments in the step size, while Ai will remain the same during each update. Therefore, Ãik can be interpreted as a dynamic modification of Ai by taking other agents’ update into consideration.

heading: 4 Experiments
text: In this section, we evaluate CoPPO on a modified matrix penalty game and the StarCraft MultiAgent Challenge (SMAC) (Samvelyan et al., 2019). The matrix game results enable interpretative observations, while the evaluations on SMAC verify the efficacy of CoPPO in more complex domains.

heading: 4.1 Cooperative Matrix Penalty Game
text: The penalty game is a representative of problems with miscoordination penalties and multiple equilibria 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 modify 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 to achieve efficient coordination in this kind of game.
We train CoPPO, COMA (Foerster et al., 2018), MAPPO (Yu et al., 2021) 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 in Appendix C.1. From Fig. 1-upper left, we can see that CoPPO significantly outperforms other methods in terms of average rewards. Fig. 1-upper right presents an explanation of the result by showing the local advantages averaged among the three matching agents every time after receiving a miscoordination penalty. Each point on the horizontal axis represents a time step after a miscoordination penalty. While the times of penalties in a single run vary for different algorithms, we take the minimum times of 70 over all runs. The vertical axis represents 13 ∑ j 6=iA j for COMA, MAPPO and DOP, and represents the mean of K
epochs during one update, i.e., 13 ∑ j 6=i 1 K ∑K k=1 Ã j k, for CoPPO (i indicates the unmatching agent). Note that CoPPO can obtain the smallest local advantages that are close to 0 compared to other methods, indicating the smallest step sizes for the three agents in the direction of changing the current action. Fig. 1-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, a smaller value indicates a small adaptation in their current actions. This is consistent with what we have discussed in Section 3.3. Fig. 1-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 1 Fig. 2 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 of 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.1.

heading: 4.2 StarCraft II
text: We evaluate CoPPO in SMAC against various state-of-the-art methods, including policy-based methods (COMA (Foerster et al., 2018), MAPPO (Yu et al., 2021) and DOP (Wang et al., 2020)) and value-based methods (QMIX (Rashid et al., 2018) and QTRAN (Son et al., 2019)). The implementation of these baselines follows the original versions. The win rates are tested over 32 evaluation episodes after each training iteration. The hyperparameter settings and other implementation details are presented in Appendix C.2. The results are averaged over 6 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-policy method, CoPPO shows better stability across different runs, which is indicated by a narrower confidence interval around the learning curves.
Ablation study 2 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 3 In Section 3.2, the global advantage is decomposed into a weighted sum of local advantages. We also compare it to a mixing network with non-negative weights and the results are shown in Fig. 4. Similar to QMIX (Rashid et al., 2018), the effectiveness of the mixing network may largely owe to the improvement in the representational ability for the global advantage function.

heading: 5 Related Work
text: 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 as part of environment (Tampuu et al., 2017) suffers from the non-stationary issue (Hernandez-Leal et al., 2017; Papoudakis et al., 2019). The CTDE paradigm (Foerster et al., 2016) reaches a compromise between centralized and decentralized approaches, assuming a laboratory setting where each agent’s policy can be trained using extra global information while maintaining scalable decentralized execution.
A series of work have been developed in the CTDE setting, including both value-based and policybased methods. Most of the value-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 the representational ability of the joint action-value function, QMIX (Rashid et al., 2018) proposes to mix the local action-value functions via a non-negative-weighted neural network. QTRAN (Son et al., 2019) studies the decentralization & suboptimatlity trade-off and introduces a 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 on additional global information, such as other agents’ actions. DOP (Wang et al., 2020) introduces value decomposition into the multi-agent actor-critic framework, which enables off-policy critic learning and addresses the centralized-decentralized mismatch issue. MAPPO (Yu et al., 2021) generalizes PPO (Schulman et al., 2017) to multi-agent settings using a global value function.
The most relevant works are MAPPO (Yu et al., 2021), MATRPO (Li and He, 2020) and MATRL (Wen et al., 2020). MAPPO extends PPO to multi-agent 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 is 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 it into a 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. Different 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 3.1, 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 a coordinated adaptation of step size among agents during the policy update process.

heading: 6 Conclusion
text: In this paper, we extend the PPO algorithm to the multi-agent setting and propose an algorithm named CoPPO through a theoretically-grounded 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 a double clipping trick to 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-Bird Focused Research Program (No. JR202063). The authors would like to thank Wenxuan Zhu for pointing out some 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.

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

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.

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.