Monotonic Improvement Guarantees under Non-stationarity for Decentralized PPO
Authors: Mingfei Sun
Sam Devlin
Jacob Austin Beck
Katja Hofmann
Shimon Whiteson
Venue: ICLR 2022 Submitted (2022)
Keywords: Multi-Agent Reinforcement Learning

Abstract: We present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative Multi-Agent Reinforcement Learning (MARL), which holds even when the transition dynamics are non-stationary. This new analysis provides a theoretical understanding of the strong performance of two recent actor-critic methods for MARL, i.e., Independent Proximal Policy Optimization (IPPO) and Multi-Agent PPO (MAPPO), which both rely on independent ratios, i.e., computing probability ratios separately for each agent's policy. We show that, despite the non-stationarity that independent ratios cause, a monotonic improvement guarantee still arises as a result of enforcing the trust region constraint over joint policies. We also show this trust region constraint can be effectively enforced in a principled way by bounding independent ratios based on the number of agents in training, providing a theoretical foundation for proximal ratio clipping. Moreover, we show that the surrogate objectives optimized in IPPO and MAPPO are essentially equivalent when their critics converge to a fixed point. Finally, our empirical results support the hypothesis that the strong performance of IPPO and MAPPO is a direct result of enforcing such a trust region constraint via clipping in centralized training, and the good values of the hyperparameters for this enforcement are highly sensitive to the number of agents, as predicted by our theoretical analysis. 

Under review as a conference paper at ICLR 2022
MONOTONIC IMPROVEMENT GUARANTEES UNDER MON-STATIONARIT FOR DECENTRALIZED PPO
Anonymous authors Paper under double-blind review
ABSTRACT
We present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative Multi-Agent Reinforeement Learning (MARL), which holds even when the transition dynamics are non-stationary. This new analysis provides a theoretical understanding of the strong performance of two recent actor-critic methods for MARL,, i.e., Independent Proximal Policy Optimization (IPPO) (Schröder de Witt et al. (020)) and Multi-Agent PPO (MAPPO) (Yu et al., 202I), which both rely on independent ratios, i.e., computing probability ratios separately for each agent's policy. We show that, despite the non-stationarity that independent ratios cause, monotonic improvement guarantee still arises result of enforcing the trust region constraint over joint policies. We also show this trust region constraint can be effectively enforced in principled way by bounding independent ratios based on the number of agents in training, providing a theoretical foundation for proximal ratio clipping. Moreover, we show that the surrogate objectives optimized in IPPO and MAPPO are essentially equivalent when their critics converge to a fixed point. Finally, our empirical results support the hypothesis that the strong performance of IPPO and MAPPO is a direct result enforcing such a trust region constraint via clipping in centralized training, and the good values of the hyperparameters for this enforcement are highly sensitive to the number of agents, as predicted by our theoretical analysis.
INTRODUCTION
In cooperative multi-agent reinforcement learning (MARL), a team of agents must coordinate their behavior to maximize a single cumulative return (Panait & Luke 2005). In such a setting, partial observability and/or communication constraints necessitate the learning of decentralized policies that condition only on the local action-observation history of each agent. In simulated or laboratory setting, decentralized policies can often be learned in centralized fashion, i.e., Centralized Training with Decentralized Execution (Olichokk & Amato 2016), which allows agents to access each other's observations and unobservable extra state information during training.
Actor-critic algorithms (Konda & Tsitsiklis 2000) are natural approach to CTDE because critics can exploit centralized training by conditioning on extra information not available to the decentralized policies (Lowe al., 2017 Foerster et al. 2017). Unfortunately, such actor-critic methods have long been outperformed by value-based methods such as QMIX (Rashid et al. 20018) on MARL benchmark tasks such as Starcraft Multi-Agent Challenge (SMAC) (Samvelyan et al. 2019p. However, two 2020 Yu et al., (021) have upended this methods such as MADDPG (Lowe et al.) 2017 Rashid et al. 2018)). Both algorithms
recent actor-critic algorithms (Schröder de Witt et al. ranking by outperforming previously dominant MARL
2017) and recom-decomposed Q-learning (Sunehag et al. are multi-agent extensions of Proximal Policy Optimization (PPO) (Schulman et al. 2017) but one uses decentralized critics, i.c., independent PPO (IPPO) (Schröder de Witt et al. 2020). and the other uses centralized critics, i.c., multi-agent PPO (MAPPO) (Yu et al. 2021).
One key feature of PPO-based methods is the use of ratios (between the policy probabilities before and after updating) in the objective. Both IPPO and MAPPO extend this feature of PPO to the multi agget setting by computing ratios separately for each agent's 's policy during training. which call independent ratios. Unfortunately, until now there has been no theoretical justification for the use of such independent ratios. In this paper show that the analysis that underpins the monotonic

---

Under review as a conference paper at ICLR 2022
policy improvement guarantee for PPO (Schulman et al. 2015) does not earry over to the use of independent ratios in IPPO and MAPPO. Instead, a direct application of this analysis leads to a joint policy optimization and suggests the use of joint ratios, i..., computing ratios between joint policies.
The difference is crucial because, based on the existing trust region analysis for PPO, only a joint ratios approach enjoys monotonic policy improvement guarantee. Moreover, independent ratios consider only the change in one agent's 's policy and ignore the fact that the other agents' policies also change, the transition dynamics underlying these independent ratios are non-stationary (Papoudakis) et al. 2019), breaking the assumptions in the monotonic improvement analysis (Schulman et al. 2015 While some studies attempt to extend the monotonic improvement analysis to MARL (Wen et al. 2021 Li & He 2020), they primarily consider optimizing policies with joint ratios, rather than independent ratios as in our paper, and are thus not applicable to IPPO or MAPPO.
To address this gap, we provide new monotonic improvement analysis that holds even when the transition dynamics are non-stationary. We show that, despite this non-stationarity. monotonic improvement guarantee still arises as a result of enforcing the trust region constraint over joint policies, i.e., a centralized trust region constraint. In other words, constraining the update of joint policies in centralized training addresses the non-stationarity of learning decentralized policies. This new analysis implies that independent ratios can also enjoy the same performance guarantee as joint ratios if the centralized trust region constraint is properly enforced by bounding independent ratios, In this way both IPPO and MAPPO can guarantee monotonic policy improvement. We also provide theoretical foundation for proximal ratio clipping by showing that centralized trust region can be enforced in a principled way by bounding independent ratios based on the number of agents in training. Furthermore, we show that the surrogate objectives optimized in IPPO and MAPPO are essentially equivalent when their critics converge to fixed point.
Finally, we provide empirical results that support the hypothesis that the strong performance of IPPO and MAPPÓ is direct result of enforcing such a trust region constraint via clipping in centralized training. Particularly, we show that good values of the hyperparameters for the clipping range are highly sensitive to the number of agents, as these hyperparameters, together with the number of agents, effectively determine the size of the centralized trust region. Moreover, we show that IPPO and MAPPO have comparable performance on SMAC maps with varied difficulty and numbers of agents. This comparable performance also implies that the way of training critics could be less crucial in practice than enforcing a trust region constraint.
2 RELATED WORK
The use of trust region optimization in MARL traces back to parameter-sharing TRPO (PS- TRPO) (Gupta et al. 2017). which combines parameter sharing with TRPO for cooperative multi- agent continuous control but provides theoretical support. Our analysis showing that trust region constraint is pivotal to guarantee performance improvement in MARL applies to PS-TRPO, among other algorithms. Multi-agent trust region learning (MATRL) (Wen et al. 2021 uses a trust region for independent learning with a game-theoretical analysis in the policy space. MATRL considers in- dependent learning and proposes to enforce trust region constraint by approximating the stable fixed point via meta meta-game. Despite the improvement guarantee for joint policies, solving meta-game itself can be challenging because its complexity increases exponentially in the number of agents. We instead consider centralized learning and enforce the trust region constraint in a centralized and scalable way. Multi-Agent TRPO (MATRPO) directly extends TRPO the multi-agent case (Li & He 2020) and divides the trust region by the number of agents. However, the analysis assumes private reward for each agent, which yields different thcoretical results from ours. Non-stationarity has been discussed in multi-agent mirror descent with trust region decomposition (Li et al. (02T), which first decomposes the trust region for each decentralized policy and then approximates the KL divergence through additional training. However, this method needs to learn fully centralized action-value function and thus becomes becomes impractical when there are many agents.
3 BACKGROUND
Dec-MDPs. We consider a fully cooperative multi-agent task in which a team of cooperative agents choose sequential actions in a stochastic environment. It can be modeled as decentralized Markov
2

---

Under review as a conference paper at ICLR 2022
decision process (Dec-MDP), defined by tuple (N, S. A, p.r where W & [1.....N] denotes the set of N agents and S _ x5.xxx...xS describes the joint state of the environment. The initial state Su ~ Po is drawn from distribution po, and at each time step t, all agents & E N choose simultaneously one action a E A4 yielding joint action d, - af x a x... X a E EA At A² ... x AA After executing the joint action a, in state 8t, the next state 8 P(s az) is drawn from transition kernel P and a collaborative reward r; = r(8,, a+) is returned. In a Dec- MDP. each agent & / has local state st 8*, and chooses its actions with a decentralized policy of ~ (+(+ss)) based only on its local state. The collaborating team of agents aims to learn joint policy, TTaa & I ( (aa]))))) that maximizes their expected discounted return, (((T) (s,,)) (ir 2'Te), where 7 [0, 1) is discount factor.
Policy optimization methods. For single-agent RL that is modeled an infinite-horizon dis- counted Markov decision process (MDP) {S, A, P. Po; 7), the performance for policy T(als) is P,r,Po
defined as: r7())= (a)a)a)) 7rre, at)] The action- value function Q= and value function Vz are defined as:
(e az) 1
Σ x'r ('((s4) Vs((s) Ba. (St, (s,,))))) 1=0
Let the advantage function be (s, the expected return of another policy i in terms of the advantage over (Kakade & Langford 2002): ()( = 17(T)) + -. (s) E. { a), where p*(s) is the state distribution induced by The complex dependency of p*(s) on ă makes the righthand side difficult to optimize directly. Schulman et al. (2015) proposed to consider the following surrogate objective
Vs(:); - the following useful identity expresses
#(lss) (aas)) A (s. (s..)).
L (+) = n() + Σ Px Σ (s.)) nT(T) + (ssa)
where the is replaced with Pr. Define DI (T,, R) - max, Drv (T(-1S), it (-1s)) where Drv is the total variation (TV) divergence.
Theorem 1. (Theorem in Schulman et al. 2015 Let a (TV R). Then the following bound holds
467 a²
TT 2 (+)
- 71-
where c = max,, max,,
This theorem forms the foundation of policy optimization methods, including Trust Region Policy Optimization (TRPO) (Schulman et al., 2015) and Proximal Policy Optimization (PPO) (Schulman al. 2017). TRPO suggests robust way take large update steps by using constraint, rather than a penalty, on the TV divergence, and considers the following practical optimization problem,
TRPO: max [(,,a)~-r
(aass) (aas))
A, (s, a)).
s.t. D Dmax (T(-Is), (TV (+{s)) a.
(1)
This constrained optimization complicated as it requires using conjugate gradient algorithms with a quadratic approximation to the constraint. PPO simplifies the above optimization by clipping probability ratios A
#(a é) to form lower bound of Lx (m):
a(a *)
PPO:
(s,a)~< min (A=Ax clip - (s),)))ssss.))))
(2)
where e is hyperparameter specify the clipping range.
Both IPPO (Schröder de Witt et al.) 2020) and MAPPO YYu et al. (021) optimize decentralized policies with independent ratios. In particular, the main objective IPPO and MAPPO optimize is
Independent PPO and Multi-Agent PPO.
max E (s .a >>mpa min (A=, (s* a²)), clip(AE,, - (6* ad))]] 4h: E (1, ..., N}.
(3)
3

---

Under review as a conference paper at ICLR 2022
(v denotes the ratio between the decentralized policy probabilities of agent before and after updating. The difference between IPPO and MAPPO lies in how they estimate the advantage function: IPPO learns decentralized advantage function ( a²) - Ei=or( af V(**) based on the local information (s* a²) for each agent, while MAPPO uses a centralized critic that conditions on centralized state information 8: A a²) _ Ex Eizolr(s:: at)] V (s)]. where -k refers the set of all agents except agent k. Both methods use parameter sharing between agents. Consequently, as all agents share the same actor and critic networks, one can ignore the agent specifier & in the objective and use experience from all agents to update the actor and critic networks:
where Ad, fx(a 1a*)
max R6
(e (a p min (NeAs(s a²), clip(>e. 1 c, 1,1 + c)As(s ))
(4)
where Ag 1s*
mo(a"le*) ) and 8, Φ shared parameters for policy and advantage networks. The use of independent ratios together with parameter sharing has shown strong empirical results in various MARL benchmark tasks (Schröder de Witt et al. 2020 Yu et al. 2021).
4 TRUST REGION ANALYSIS FOR MARL
In this section, we first directly apply TRPO's trust region analysis to cooperative MARL, which yields joint ratios rather than the independent ratios adopted in IPPO and MAPPO. We then show that optimization with independent ratios induces non-stationarity in MARL, which breaks the stationarity assumption in the trust region analysis. Finally, we provide new analysis that shows how monotonic policy improvement can still arise from non stat-tttoonary transition dynamics with independent ratios.
4.1 OPTIMIZATION WITH JOINT RATIOS
Consider the joint policy π (a|s) and the centralized advantage function A a) = Qn a) V=(s). Then, the trust region analysis for single-agent RL carries over directly to MARL with the surrogate objective as L (T) = (π())) + +E. Pz (8) >. i[aa 8) (s, One can consider the same
optimization problem for TRPO shown in equation
म (als))
max #
((sa))===
A (s.a) a)).
s.t. Dmna (r(1s), S a.
(5)
(als)
The trust region constraint enforced over joint policies, which we refer as centralized trust region constraint. With joint ratios defined as A+ *(ass)
*(ala) II =x(aa((*))
can simplify the
m
above optimization as PPO have the following objective,
JR-PPO: max *
[(s,a)=>= [min (A (s. a), clip(>.. e,1 (s.
(6)
We call the resulting algorithm Joint Ratio PPO (JR-PPO) (see Algorithm in the appendix).
Unlike IPPO and MAPPO, JR-PPO consider joint ratios over the joint policies, rather than independent ones. This difference is crucial, as joint ratios naturally enjoy the monotonic improvement guarantee carried over from the single-agent trust region analysís:, i.e., Theorem Furthermore, the objective used in IPPO and MAPPO is not equivalent to the above objective they are lower bounds of different objectives. Thus, Theorem dooes not imply any guarantees for IPPO and MAPPO.
4.2 OPTIMIZATION WITH INDEPENDENT RATIOS
Optimization with independent ratios, however, induces non-stationarity in MARL. When optimizing decentralized policies, the environment is non-stationary from the perspective of single agent since the other agents also change their policies during training. To analyze the non-stationarity in decentralized policy optimization, we first consider the Markov chain for the local state s* induced by the underlying MDP for agent When all agents' policies are updated from Ti ... Ty to Th ..., WN. the state transition distribution of this Markov chain also shifts. We denote such transition shift from R g for agent l:
A Ai.....N (8 (** BI
[p (8 (a))) Pm...... (8 a (a+
4

---

Under review as a conference paper at ICLR 2022
where Pri..... and & refer to the transition dynamics before and update is updated. The state transition shift consists of two parts: an exogenous part, which is caused by the update of other agents' policies (i.e., the change of transition dynamics from pT, to Pa, ) and an endogenous part, which is contributed by the update of the agent's own policy (i.e., the change of agent k's policy from TA to ftg). See the appendix A.2 (A.2 for detailed analysis. The exogenous shift breaks the assumption in the monotonic improvement guarantee (Schulman et al., (2015) that the MDP is stationary, i.e., the state transition shift arises only endogenously from the agent's 's policy changes. As a result, Theorem T no longer holds if one optimizes with independent ratios as in IPPO and MAPPO.
4.3 MONOTONIC POLICY IMPROVEMENT FOR INDEPENDENT RATIOS
We now provide a new analysis for optimization with independent ratios. As the above analysis suggests that the exogenous transition shift breaks the trust region analysis in TRPO, we instead consider how to handle this exogenous shift training. Specifically, since the exogenous shift is caused by the changes of other agents' policies, it can be controlled by constraining the update of other agents' policies in centralized training.
Proposition 1. In Dec-MDP, the transition shift A A fN (5" (s*) decomposes as follows:
A A KI (8*) (s* A $2 NN
( 31 3 N
& + A
$1. N2. R1. ma.ns...........................
(8 (**) + ... A fI.-. RN 1.5N FI.... RN - 1.
(s*)
The proof is given in the appendix A.3.1 This proposition implies that the state transition shift at local observation s* is caused by the shifts arising from all decentralized policies. This decompo- sition inspires the derivation of a new monotonic improvement guarantee for decentralized policy optimization by enforcing the trust region over joint policies.
Define the surrogate objective for decentralized policy TT& as
L (k) #1. (ftw = Σ P AN (s
Σ ak
the (a*)s)) (s (s*,at" att).
and the expected return of decentralized policy Ty as
1. ue (Tx)) = (s ">pp) (a))a*)) [rx(s aa*) aa)]]-
In practice, Tx (s a²) is usually unknown. As the state transition shift decomposes into the sum of transition shifts caused by each decentralized policy, we can bound this state transition shift with centralized trust region constraint as in equation
Theorem 2. Let
DTV (T, t). Then the following bound holds
4ey (1 7)3 a²
1E (Fte) 2 Ma TN (TT) +
(k) 1 (Tw))
4k,
#=1
where E = maxKEN max,k, Aas (st a*))
The proof is given in the appendix A.3.2 This theorem implies that, for sufficiently small o, the performance increase of a decentralized policy ग is lower bounded by the sum of surrogate objectives for each decentralized policy with respect to the samples generated by Ti. In other words, the trust region is enforced, the sum of surrogate objectives yields an approximate lower bound for 17,, N (ft)), which holds for any decentralized policy #E.
Theorem 2 differs from Theorem I in three respects. First, the lower bound for one decentral- ized policy effectively relies on surrogate objectives for all agents, since the update of one agent's policy affects all other agents" transition probability. Therefore, to improve the performance for
policy Th, we can simultaneously maximize (k)
(x + L(kk) L (#2) + ... + I.(A) L (.
Second, unlike the surrogate objective in Theorem [ the new surrogate objective implicitly con-
tains an independent ratio Aä
(a=1/55 as can be rewritten as follows: (b) L (Tw) =
(s"a"
4ey 4er a² requires computing the total E(skaak) [ Ane (s* adt) (s* Third, the additional term (1->)>
variation between joint policies πT (aa s) and (a)s), rather than the policies that are directly opti- mized. We show in the next section that, in centralized training, this requirement is easily satisfied as the magnitude of the constraint on the update is proportional to the number of agents.
5

---

Under review as a conference paper at ICLR 2022
5 REALIZING TRUST REGIONS VIA BOUNDING INDEPENDENT RATIOS
Theorem 2 indicates that the centralized trust region is crucial to guarantee monotonic improvement. In this section, we show that bounding independent ratios is an effective way enforce such centralized trust region constraint, and this enforcement requires taking into account the number of agents. To achieve this, we first present two lemmas about Drv divergence.
Proposition 2. In Dec-MDP, TV (T, म) - Σ
D (Tks Tx).
This proposition is a direct result of the fact that the joint policy in Dec-MDP factors as a product of decentralized polices, i.e., π = [Ik=1 Th Proposition 3. DTV (Th, T&)) = max.es E [Tx (oalls*))) - xT(a+(s*)]
This useful identity follows from property of Drv: (Tv(u(z), v(x)) = En(a)s (u(x) (a)(()) (xx)] where μ and are two distributions. This proposition indicates that decentralized trust region is also defined by the sum of probability differences over a special subset. We use this to upper bound the trust region in the following analysis.
Assumption 1. Assume the advantage function Anu (5k, ax) converges to a fixed point for Vk.
Theorem 3. If independent ratios Ay:- A # (e") ( (o")) are within the range ck Ek) for for Wk e N,
then the following bound holds: DTV (Tx(-11) (x(-(s) < Ex: DTV (IT(1ss. T(1ss) Σx= Ek.
This theorem comes from that fact that optimizing 7(s a) with respect to a converged A a) leads
to मे (als)) > (als)) 3) if A(s, a) > O, Vs, a in actor-critic algorithms (Konda & Tsitsiklis 2000). Thus,
based on Proposition 3 we have the following
DTV (Tk, #x) = max
[*x(a*ls*) (a(a" S max
[CATT(a"1s ck.
(a "a"""""000
Aulo" (=)000
The equation is from Proposition by considering A(s, a) > 0 such that #(als) > (als)) The first inequality result of bounded ratios and the second from (o A(=,)))0) [[([s]]]]]] 1
(considering the lower bound yields the same analysis.) Furthermore, the trust region constraint over
joint policies is direct result of Proposition?? 2] The detailed proof is given in the appendix AA..3 As
DTv is bounded divergence between [0. 11. the ratio guarantee makes sense when EN S 1.0.
Theorem 3 implies that bounding independent ratios (a(a"(s*)
"x(a"(=*) with [1 cR Cx] amounts to enforcing a trust region constraint with size e over decentralized policies. Thus, to enforce the centralized trust region constraint over joint policies, i.e., Dmaa (T,, #) S as in Theorem 2 one
(a(a"Ts")
can consider bounding independent ratios according to the number of agents, e.g., A [x(aa(3") - 1 + ]. In the next section, we present practical implementations of these ratio constraints.
INSTANTIATING RATIO CONSTRAINTS
In this section, we show that IPPO and MAPPO effectively satisfy the conditions of Theorem 2 and Theorem 3 Specifically, the independent clipping and parameter sharing used by IPPO and MAPPO are useful ways to approximate the ratio constraints in Theorem 3 and to optimize the surrogate objective in Theorem 2 Furthermore, we show that the surrogate objectives optimized in IPPO and MAPPO are essentially equivalent when their critics converge to fixed point.
6.1 OPTIMIZING SURROGATE OBJECTIVES
The objective is to update all agents' policies simultancously with the experience from all agents, which can be further simplified with parameter sharing (Gupta al. 2017):
ΣΣ Pxt P P (s*
To( 1s* A ,
DIMAN (M((1s), 7 (s))s) S a,
(8)

---

Under review as a conference paper at ICLR 2022
where 8 and @ are the shared parameters for decentralized policies and critics. Furthermore, to effectively optimize the surrogate objective, we can clip the probability ratios of each decentralized policies to form a lower bound of the objective in equation[] similar to PPO (Schulman et al.) 2017).
Mo(u (at) Wk E NN we can optimize the following objective:
Namely, with independent ratios A
ma(a
max Σ
Bls min (>* clip - c, (1,),1+)))))]
which is exactly the objective used by IPPO and MAPPO.
6.2 ENFORCING THE TRUST REGION CONSTRAINT
Proposition 2 implies that, in centralized training, one way to enforce trust region constraint is to delegate the centralized trust region constraint to each agent, such that the update of each decentralized policy T& Ta(a" (a*|s*) ) is bounded. Therefore, to enforce the centralized trust region constraint, one can impose a sufficient condition as follows,
DTV (F -
a N
Vk VkEW,
which suggests that enforcement of the centralized trust region constraint translates to a decentralized trust region constraint if the trust region is specified properly according to the number of agents. Furthermore, based on Theorem bounding independent ratios is an effective way to enforce the trust region constraint. One can thus impose a sufficient condition to constrain independent ratios X such that x E many ways to achieve this sufficient condition but itself is a heuristic approximation so often fails to bound ratios exactly within the ranges. In practice, one would need to tune the the clipping range and the number epochs so the ratios can be properly bounded. We show the experiment section that good values of the hyprraarameters for the clipping range highly sensitive to the number of agents, as these hyperparameters, together with the number of agents, effectively determine the size of the centralized trust region.
No 1 + %) where N is the number of agents in training. Clipping is one of
6.3 LEARNING ADVANTAGE FUNCTIONS
We now look at the training of the advantage function, where IPPO and MAPPO differ. IPPO trains decentralized advantage function, while MAPPO trains a centralized one that incorporates centralized state information. Assume a stationary distribution of (s*, a+) exists. From Lyu et (021). have the following:
Proposition 4. (Lemma! I & 2 in Lyu et al. (202T) Training of centralized critic and k-th decen- tralized critic admits unique fixed points Q" (7( at a .a) and E, h,a (sQ , a a=*)] respectively, where Q is the true expected return under the joint policy n.
s
Accordingly, based on the definition, the centralized value function is V(s) = Vis 8
Bu 1Q (s*, - a²,a-=a aa]]] and the decentralized one is V(s*) E.-t a (Q" s-k, ut a a=]]]]
[V s*]] [V(s) Thus, we have AurO (st a² = AMAPPO (sk a (and so IPPO and MAPPO objectives are equivalent) given that underlying critics converge fixed point.
EXPERIMENTS
We consider the StarCraft Multi-Agent Challenge (SMAC) (Samvelyan et al., 2019) for our empirical analysis as it provides a wide range of multi-agent tasks with varied difficulty and numbers of agents. We first show that clipping is an effective way to constraint ratios when the number of optimization epochs and the learning rate are properly specified. Furthermore, we show that clipping also requires taking into account the number of agents such that the centralized trust region can be properly enforced. We then empirically demonstrate that bounding independent ratios in effect enforces the trust region over joint policies. Finally, we present results showing that IPPO and MAPPO perform equivalently SMAC maps with varied difficulty and numbers of agents.
7

---

Under review as a conference paper at ICLR 2022
Cloong 855
Clvvre Coonn
sloptritate sporr
(b)
(c)
Figure 1: Trust region with respect to the clipping range, the number of agents and the number of optimization epochs: (a) Ratio ranges for agents with the number of optimization epochs; (b) Cumulative percentage of decentralized trust region the clipping value varies; (c) Cumulative percentage of centralized trust region as the number of agents varies (clipping at 0.1); and (d) Cumulative percentage of centralized trust region with optimization epochs (clipping at 0.1).
Clipping and ratio ranges. Theorem 3 indicates that bounding the independent ratios amounts to enforcing a trust region constraint over joint policies. We empirically show that independent ratio clipping approximately bounds the independent ratios in the training if some hyperparameters properly set. We train decentralized policies on one map, 2s3z, and clip the independent ratios when optimizing the surrogate objective. Figure Ta shows how the the max and min of the ratios changes according to the number of optimization epochs with different clipping values. Independent ratio clipping can effectively constrain the range of ratios only when the number of optimization epochs and the clipping range properly specified. In particular, the range of independent ratios grows as the number of optimization epochs increases. This growth slower when the clipping range is smaller, e.g., 0.1. Furthermore, the clipping range may not strictly bound ratios between [1 1 + e]: when the clipping range is 0.1, the independent ratios can exceed 1.2; and the independent ratios can grow up to 1.6 when the clipping range is 0.3.
Ratio clipping and trust region constraint. Next, show that the trust region defined by the total variation is empirically bounded by independent ratio clipping, and this bound is also propor- tional to the number of agents. Specifically, we compute the maximum total variation divergence Dipex over empirical samples collected by the behavior policy during the first round of actor update, which contains 100 optimization epochs, and report the distribution of DTy Figure shows the distribution of Dawx over decentralized policies when clipping range varies. For clipping at 0.1, all D values are smaller than 0.2, meaning that the trust region is effectively enforced to be small. As the clipping range increases, more D values exceed 0.3. For the case without clipping, DTV almost uniformly distributes among [0.0, 0.8). implying trust region is no longer enforced. Figure Icl presents the distribution of Depax over joint polices for clipping at 0.1, on maps with different number of agents. See appendix Table [ for more details. The D (TT, # estimated by summing up the empirical total variation distances Diaax (T2, #x) over all agents. The Dipax #) grows almost proportionally with the number of agents, indicating that enforcing the centralized trust region with independent ratios clipping also requires considering the number of agents. Figure Id presents the distribution of Dipex over joint polices with different numbers of epochs for clipping at 0.1. Compared to the number of agents, the number of epochs has less impact on the trust region.
Independent ratios clipping SMAC Figure 2 shows the empirical returns and trust region estimates with different ratio clipping values across different maps SMAC. Notably, when the clipping value is small, e.g., 0.1, the joint total variation distance, i.e., the centralized trust region, can be effectively bounded, as in the second row in Figure 2 The empirical returns corresponding to 0.1 are thus improved monotonically, outperforming all other returns consistently in four maps. Moreover, as the number of agents increases, the trust region enforced by clipping value e = 0.1 in the initial training phase also grows from less than 0.3 to more than 0.5. In contrast, for clipping at
Trrined via decentralized advantage, i.c., IPPO. Results with centralized advantage similar, presented in the appendix A.4 Unlike Yu al. (02T), the value function not clipped in our experiments.
8

---

Under review as a conference paper at ICLR 2022
Figure 2: Empirical returns and trust region estimates for independent ratios clipping.
Figure 3: Contrasting IPPO and MAPPO across different maps.
0.5 and 1.0, the learning quickly plateaus at local optima, especially on maps with many agents, e.g., 10m_vs si__vs_lllm mm and 27m_vs__a vv_00m, which shows that the policy performance (y(Tx) closely related to the enforcement of trust region. We also apply the same clipping values to joint clipping and independent clipping, see Appendix A.6 for more analysis.
IPPO and MAPPO We show that the empirical performance of IPPO and MAPPO are very similar despite the fact that the advantage functions learned differently. We evaluate IPPO and MAPPO on maps of varied difficulty and numbers of agents. We heuristically set the clipping range based on the number of agents. Specifically, we the clipping range for 3s5z, 1c3s5z, 10m_w. _s_ 11m, and bane_ _s bane, as 0,1, 0.1, 0.1, and 0.05, respectively. The results are presented in Figure 3 On the four maps considered, IPPO and MAPPO perform similarly. This phenomenon can be observed in Yu et al. (202T), which provides more empirical comparisons between IPPO and MAPPO. Such comparable performance also implies that, for actor-crític methods in MARL, the way of training critics could be less crucial than enforcing the trust region constraint.
CONCLUSION
In this paper, we present new monotonic improvement guarantee for optimizing decentralized policies in cooperative MARL. We show that, despite the non-stationarity IPPO and MAPPO, a monotonic improvement guarantee still arises from enforcing the trust region constraint over joint policies. This guarantee provides a theoretical understanding of the strong performance of IPPO and MAPPO. Furthermore, we provide theoretical foundation for proximal ratio clipping by showing that a trust region constraint can be effectively enforced a principled way by bounding independent ratios based on the number of agents in training. Finally, our empirical results support the hypothesis

---

Under review as a conference paper at ICLR 2022
that the strong performance of IPPO and MAPPO is direct result of enforcing such a trust region constraint via clipping in centralized training.
REFERENCES
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual Multi-Agent Policy Gradients. 1705 08926 [cx], December 2017. URL
http:://rxiiy org/ wttp/////////ooooooo..oootaaaeee abs/1705, 08926
arXiv: 1705.08926.
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, pp. 66-83. Springer, 2017.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proc. 19th International Conference Machine Learning. Citeseer, 2002.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pp. 1008-1014, 2000.
Hepeng Li and Haibo He. Multi-agent trust region policy optimization. arXiv preprint arXiv:2010.07916. 2020.
Wenhao Li, Xiangfeng Wang, Bo Jin, Junjie Sheng, and Hongyuan Zha. Dealing with non- stationarity in multi-agent reinforcement learning trust region decomposition. arXiv preprint 1rXiv:2102.10616 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-competiive environments. arXiv preprint arXiv:1706. 07Xiv:1706.02275. 2017.
Xueguang Lyu, Yuchen Xiao, Brett Daley, and Christopher Amato. Contrasting centralized and decentralized critics in multi-agent reinforcement learning. arXiv preprint arXiv:2102.0444 2021.
Frans A. Oliehoek and Christopher Amato. A Concise Introduction Decentralized POMDPs. SpringerBriefs in Intelligent Systems. Springer International Publishing, 2016. ISBN 978-3- 319-28927-4, doi: 10. 100007998--33319-8822955
URLhttps::/ wwwp///wwww/////////////////wt springer.......... com/ gp/
book Book/978331922 9289274
Liviu Panait and Sean Luke. Cooperative Multi-Agent Learning: The State of the Art. Autonomous
Agents and Multi-Agent Systems, 11:387-434, November 2005. doi:
Georgios Papoudakis, Filippos Christianos, Arrasy Rahman, and Stefano V Albrecht. Dealing with non-stationarity in multi-agent deep reinforcement learning. arXiv preprint arXiv: arXiv:1906.0es 1906..4777777
2019.
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 Machine Learning, pp. 4295-4994444 43044. PMLR, 2018.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: arXiv:1902.0000 990200403, 2019.
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 the starcraft multi-agent challenge? CoRR, abs/2011,09533,, 2020. URL https:://axxi.... org abs/
2011.09533
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347, 2017.
10

---

Under review as a conference paper at ICLR 2022
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg. Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value- Setue-Decompotttinn Networks For Cooperative Aulli--Aent Learning. arXiv: 1706v:1006.00 05296 [cs], June 2017. URL htt.:tpp:/aarxt.oorg/b//////////
05296.
arXiv: 1706.05296.
Ying Wen, Hui Chen, Yaodong Yang, Zheng Tian, Minne Li, Xu Chen, and Jun Wang. A game- theoretic approach multi-agent trust region optimization. arXiv preprint arXiv:2106.06828 2021.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo cooperative, multi-agent games. arXiv preprint arXiv:2103.010000 2021.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1
JOINT RATIO PPO
Algorithm Joint Ratio PPO (JR-PPO)
for iteration 2, do
Roll out decentralized policies [T,, T2,..., TT in environment;
Compute centralized advantage estimates A(s, a);
Compute joint ratios A
*(als) II (a
Optimize the surrogate objective max; E min (A A clip -11, +ell+el (s a))]
end for
A.2 STATIONARITY ASSUMPTION IN TRPO
The aingle-agent TRPO relies on the following analysis:
(+) (T)
Σ p(s) Σ (A(als) =(als))
Σp(s)
p(s) Σ (f(als)-<<lls))) - [(aas)) +
e(s)]
Mss) Σ (#(a]s) (#(
pls) ΣΣ ( a))
E(ss) p(s) Σ (P=(8')s) p- (8())))
This analysis is based on the assumption that p(s'(s, a) remains the same before and after n is updated, such that transition shift (s'lss) (s'lss is only caused by the agent's policy update, ie., endogenously. Such analysis no longer holds when the transition dynamics p(s' a) are non-stationary: P= (=(5'ss,a) + (s)
A.3
PROOFS
A.3.1 PROOF PROPOSITION
Proof. Assume agent k's policy r² is executed independently of other agents policies K we have
#*..... #N TI... N
(3
Σ
p(s 5- |s* - k. at a- (a - (ak - x (att - #(aa [t|== *1s=+
k aa-
Σ
(a- p3zk , |* s at, ahk) 1 (a* (a- b - (a* -k - - (a
exogenous
a
n (a (1- 1 n (a (s
endogenous
The above decomposition can be repeated such that the exogenous part can translated into endogenous parts that specific to each agent. Specifically, repeat the decomposition for the
12

---

Under review as a conference paper at ICLR 2022
exogenous part by considering agent k'' (k' # k):
="(a"1s") * (aa IIs b - #" (a ) - (a *13 kk)
(a*""""")) |5 (at 1st ) (R.A') ) (a (R.'') 1s (k= x k/ (ath 1s YT (R.00) (a -0.00 (1--(13))]] [[AA3]
=# 10*) [ [ (a y 1 } (ar (k, )1s (hhh')) - =k (at 18 )ot 1k - -1-11111 (
exxogenous
+ x (a 15 18.03 (a 11.33// (K.0) nk (a 1st )o tKi (a (11-11///15 (1)kk)))))
st *--nndggenous
So and forth, one decompose A At " "..." (s* follows:
A # v M (5*1 A (8* (8)))**
(5415
A +
(8 1*),
which implies that the state transition shift at local observation sh is caused by the shifts arising from all decentralized policies.
A.3.2 PROOF OF THFOREM 2
Proof. This proof is based on the perturbation theory. Let G = (1 + 7 x1 NN
(1 wi...ai.i....................... ai. ) and G=: (1 + (1+7Prt, PP Ri, (7 po: # (1-=(1-PP #o.. ) denote the distribution of state s; under #1, T2, TN and TT, 22 NN. We will use the convention that p (a density on state space) is a vector and r (a reward function on state space) is dual vector (i.c., linear functional on vectors), thus rp is a scalar meaning the expected reward under density p. Note that n)(r)) = rGPo. and r7(#) ()) = rGpo. Denote the state shift of s; as ((s:)
Fi )2 2
pai
Ps, Fi. Using the perturbation theory, we have the following
Rn Tr..a.......N
(G+)-1 [G
Pé: TENTA... = 7\s())
Left multiply by G% and right multiply by G
G H A
Substituting the right-hand side into 8h gives
G G = 7 ACCC)))CCCCH
Consider decentralized policy T&:
1 Rx (its) - 17 17 (2.)
- po -0 r(ā 6² )po
-yrG* Po r2. " A(s:))*A(ss)***
Let us first consider the leading term yrG (()
GG ((s:) po
Σ p(ss) Σ
pm (s(()))))
Σp(es E(ss) Σ A (s((s)))oo)))
Σ p(s.) Σ
A AI.. (s((ss) + A F1 #9. (5/ (/((s)) ... + A
AN-1 (6/10s) vo(s)).
R n2.
x
13

---

Under review as a conference paper at ICLR 2022
For one of these summation terms, we have the following RI.-,
Σ p(s))
#i.... - (6(1s)) ro(ss)
(10)
p(8))
P ai)s)aaa)) - - (s/1es, as ()) (asls)))) ro(s))
(11)
Σ (ss) Σ
(Tr((clss)) (a(((ss))) (1((as))))((a(ss))
(s as)ru((
(12)
84
Σ ((s)) Σ (ty(aa)s)-=a(( [r(ss) + Σ
P P (1)
v/ :. (8:)
Kg....
5/
(13)
Ep(s:)
((s:) Σ
iry (agls:) (a(assss) An, (st, ai)
(14)
G
I
F1. 72 2 N (T)).
(15)
#1 T2
The derivation from line
13 to 14
is based on the following definition:
Ax, (ss, ax) r(s;) +
Σ p# -, aN (s/18,, as)y)(s)) 2/ (81))
where UR U (1.) (s:) A r(s.) 7 Eo; Pä P (s]1s;, a.) Ea, Ty (s(aass))((()). which
will result in T (Ty) = 0 for Vj. In fact, for line 13 r(s:) and Us u (8:) can be dgu-M interpreted as functions over 8i. which will be zero if integrated with Σn, (ūy(a:(si) Ty (a:|s:)). Note that the advantage function also conditions on the πÿ.
Note that the advantage of ny with respect to 8i, ag in multi-agent RL is defined differently from the advantage function in the single agent case.
We can thus repeat the above decomposition iteratively and have the following:
yr ((s) Po = -((t)
- L 11. 22... (T1) + I 11 TN (T22 [,(t)
Rx (#1) -2...
(1)
"11 32 .... (T2)
+ 11
(6)
(#N) [((
12 (xN).
Note that (a) _ WN (TT) = 0 for Vj. Thus,
(1] A(s) po an .y...... N (#t)
T
AN (#2) + ... + I.
Ra (#N).
Next we bound the second term 72r G (ss; G A(s:: po. First we consider the product gr (sx+) = (x)) Consider the component of this dual vector:
( > (p=,((/1)))) Pr, ((()ss))))
of
N
N II j=1
=| Σ Σ
Σ
.... SN, a.......00 aN aN)u:(s)) II
(y(a, (s))
x, (a((((s)))
$1 y S1 B 1, a1y...y
5=1
N
N II j=1
Σ
Σ
A a:) II
(a,1s))))
(a.ss)))
81 91 Bi....aN
j=1
Thus, we have
N (a.())))) - II
N
Σ Σ [A az) II
Ty (a((s1ss)1 S 2nc.
81 ai.....aN
j=1
j=1
Note that An, (81, a.) the analysis is defined with the transition dynamics P mo (s(()1, a.).
14

---

Under review as a conference paper at ICLR 2022
We bound the other portion G* G**A(s:) Po using the operator norm:
|| A(:)) polli _ |
(1 7)-
The ||((s))]1 can be bound as follows:
(s:))] =
Σ |pa, (8(118) - Pr, (s(18:)
N
N II
Σ
Σ
Σ
p(, 8y181, ,w SN, a1 ON)
( 8;)
x (a s:)
5 " $1o0088 Gio..a
j=1
j=1
N
N
Σ
Σ
II (y(la)))))) - II Ty(a,(s)) 2a.
So have that
4ey S (1 7)2 7)2
a²
A.3.3 PROOF OF THEOREM 3
Proof. Given the assumption that the advantage function A(s, a) converges a fixed point. we have the fact that optimizing (s,, a) with respect to A(s, a) leads to न (als) > (als) if A(s,s a) > O, Vs, a.
$
Consider independent ratios A
(a which are within the range [1 Ex. + Ex] for Vk e N,
Thus, based on Proposition
3 we have the following
D DMA (T 7t)) max
Σ
[xx(a*|**) 1 =T(("|s*)]
EA*
7(aa)))7(aas)
Σ
[11 + (1++)) - nn(a"10"
max g
As(a ))0
[ELTT(a*|s*)) < ck.
max
AE(s )>0
The first inequality is a result of bounded ratios and the second is from Ens (a: A(=,a))) [=]ass] 1. Furthermore, the trust region constraint over joint policies is direct result of Proposition 2 One can also consider A(s, a) < O, which leads म (a|s) (als)) in optimization. Given that independent ratios are also lower bounded by 1 c, the same conclusion can be reached for Dmnex
A.4 EXPERIMENT DETAILS AND MORE RESULTS
The number of agents each is given in Table
Test battle win mean of IPPO on maps with varied difficulty and numbers of agents is presented in Figure
Empirical test battle win mean, test returns and trust region estimates of MAPPO maps with varied difficult and numbers of agents are presented Figure
A.5 ABLATIONS ON SMALL CLIPPING VALUES
We also present the ablation results for small clipping values, i.e., 0.1. in Figure 6 It is true that small clipping value results a small trust region, and thus small clipping values, e.g., 0.08, 0.05 and 0.03, would be preferred for maps with large number of agents, e.g., maps 10m vs_ 1 11m (10
15

---

Under review as a conference paper at ICLR 2022
Table 1: Number of agents on maps.
SMAC Map
Number of agents
2s_vs_ 1sc
2
3s_ vs_
3
2s3z
6h_vs vs_8z
lc3s5z
10m_vs_ 1m
10
Figure 4: Test battle win mean of IPPO maps with varied difficulty and numbers of agents
agents) and 27m_ vs 30m (27 agents). However, when the clip value is too small, e.g., = 0.01 in maps with and 8 agents, the resultant trust region is also small and the update step in each iteration can thus be too small to improve the policy. Thus, one would need to trade off between the trust region constraint, ensure monotonic improvement, and the policy update step, ensure sufficient parameter update at each iteration.
A.6 COMPARISON BETWEEN JOINT RATIO CLIPPING AND INDEPENDENT RATIO CLIPPING
We apply the same clipping values to these two types of clipping, and use maps with many agents, i.e. 10m_vs vs__ Im and 27m_vs vs_30m, make the difference more salient (based on the theoretical results in the paper). The results are presented in Figure 7 and B
Compared to joint ratio clipping, the independent ratio clipping is more sensitive to the number of agents. In particular, for a small clipping value, e.g., e 0.1, joint ratio clipping consistently produces better performance than independent ratio clipping, even when the number of agents changes from 10 to 27. As the clipping value increases to 0.5, the performance gap between these two types of clipping becomes larger, which also aligned with our theoretical analysis.
16

---

Under review as a conference paper at ICLR 2022
2000 HODY EHOCIIOO PNOOSS000
2000 8000 1000 BOOOOEEOOOOO
2400 6000 5000 (SCSONOO MOOS FIOCSSOOO
Figure Empirical test battle win mean (first row). test returns (second row) and trust region estimates (third row) of MAPPO on maps with varied difficult and numbers of agents
17

---

Under review as a conference paper at ICLR 2022
Labe
Aot Ao AA LANee MMA mopee
Figure Empirical returns, trust region estimates and battle win rate for small values of independent ratios clipping.
18

---

Under review as a conference paper at ICLR 2022
2010
100
(a) Joint TV divergence
(b) Empirical returns
Figure 7: Joint divergence estimates and empirical returns for two types of ratio clipping at different clipping values: 0.1 (first row), 0.3 (first row) and 0.5 (first row).
19

---

Under review as a conference paper at ICLR 2022
Figure 8: Test battle win rate for two types of ratio clipping at different clipping values: 0.1 (first
row), 0.3 (first row) and 0.5 (first row).
20


Reviews:
[{"review_id": "uY-edYzWZcw", "reviewer": "Reviewer_ax1X", "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": "Improvements and Questions:\n- 0.1 Is a pretty standard clipping value, higher values are frequently not used for the reasons pointed out in this paper. I would have been very curious to see an ablation in the opposite direction, towards values < 0.1 since presumably the trust regions need to be smaller as the number of agents increase. Note, I am not suggesting that I would raise my score if this was done or requesting extra experiments, only that this would make for a better paper. \n- Proposition 4 and the subsequent discussion is slightly confusing to me; I accept that both admit unique fixed points under appropriate assumptions and so estimate the advantage identically at that fixed point. However, the assumption underlying the use of extra information is to make the learning of the value function easier; is the implication here that there are not effects of centralized value functions on the learning?\n- In Fig. 1d I find it surprising that the number of epochs appears to barely affect the total variational distance. This seems to suggest in turn that a large number of epochs should accelerate learning when the clipping ratio is 0.1; did you observe this?\n- What values are the number of epochs fixed to in Fig. 1b and c?\n- How does policies usually being recurrent in these settings factor into your results? \n\nClarity: \n- The x axis on most of the SMAC graphs should be in scientific notation. \n- The y axes on the SMAC graphs should probably not have underscores.\n- In the legend of Fig. 4 and 5, it’s not clear what the (4) is in all the legends.\n- Section 6.2 is written slightly confusingly in that it essentially says “a sufficient condition can be constructed to constrain independent ratios” and then follows up to say “ratio clipping is not sufficient to constrain independent ratios.” I think I understood what the author mean, that the estimation isn’t perfect so the constraint is not maintained, but I want to draw their attention to it having been confusing as a slight rewriting to clarify why the sufficient condition is not sufficient might be helpful. ", "summary_of_the_paper": "This paper works on extending the monotonic improvement guarantees of PPO to the multi-agent setting.", "summary_of_the_review": "A good paper that helps explain some of the recent results studying on-policy methods in MARL.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UdUSiVEdEAG", "reviewer": "Reviewer_7r77", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 theory explains some of the success (monotonic improvement) of IPPO and MAPPO. The motivation is clear, derivations are easy to follow, and is to the best of my knowledge, novel and non-trivial.\n\nHowever, while I like the theory presented, I am a little more skeptical with the impact of this paper, beyond reminding practitioners to decrease clipping ranges when there are more agents. I have a few minor gripes/questions\n1) Section 6.3 seems fairly out of place and not in line with the central message of this paper (which is about monotonic improvement, as opposed to being about IPPO or MAPPO specifically). \n\n2) Minor presentation issues. (i) Axis and labels on graphs are way too small (ii) Indices of summation can be explicitly stated for clarity. (iii) In section 6.1, is there a particular reason for using u^k as opposed to a^k? (iv) Why is the index k’ used in the definition of the surrogate objective and how is this different from k? (v) It would be very helpful to explain a little about the abbreviations used in SMAC (e.g., 10m vs 11m) etc, especially since these involve the number of agents (which is the key focus of this paper).\n\n3) I found the experiments section quite difficult to follow. The first set of experiments (clipping and ratio changes) shows that clipping roughly bounds independent ratios if *hyperparameters are properly set*. These hyperparameters include optimization epochs and clipping range. It is not clear what “properly” means here. Further, I think it would be helpful to explicitly state why this disagreement with theory occurs.\n4) The total variation reported in the second section of the experiments are based on samples collected by the behavior policy. Is this a good surrogate for the “true” TV between policies?\n\n5) In the last experimental section, the authors report that “as the number of agents increases … empirical returns drop from nearly 20.0 to 17.5”, presumably to show that having too large a trust region (due to there being too many agents) would negatively impact performance. This comparison does not seem fair, since these are 2 very different scenarios and perhaps, even the optimal policy would do worse in the latter case. Maybe a better comparison would be to compare clipping over *joint* policies (effectively fewer agents), but in the same environment, to decentralized policies. \n", "summary_of_the_paper": "This paper provides analysis showing monotonic improvements when in cooperative MARL settings, where independent, as opposed to joint ratios (over agents) are used. From a single agent’s perspective, a non-stationary distribution is experienced since other players are simultaneously performing updates to their policies, breaking the standard monotonic improvement property in TRPO. The authors’ propose a surrogate objective for decentralized policies, and show that the improvement in expected return can be bounded in terms of the sum of these (decentralized) surrogate objectives and a term proportionate to the total variation divergence between the 2 policies---analogous to the result by Schulman et al in 2005. Similarly, the authors proceed by showing that the TV divergence between policies can be bounded by enforcing constraints on independent ratios, where the strictness of these bounds depends on the number of agents. The trust region constraint is then split (independently) over all agents, and the authors show that prior methods like IPPO and MAPPO maximize an objective consistent with the proposed theory.", "summary_of_the_review": "I recommend this paper for acceptance. The work is novel and does not have any glaring faults apart from some of my (possibly to-be-clarified) doubts with the experiments. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PsiXQeM8IQO", "reviewer": "Reviewer_JmGx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. The paper is written clearly, and the technique is relatively straightforward.\n2. The analysis of ratio constraints between MAPPO and IPPO is interesting.\n\nWeakness:\n\n1. The paper considers the fully observable and cooperative case, which means all the agents have the same goal based on the same information. Therefore, it seems trivial to obtain the key result of the paper \"bounding independent ratios based on the number of agents\". Maybe the authors can further discuss the more general cases, like partial observation or competitive cases.\n2. The authors compared the MAPPO and IPPO on different SMAC. I think more experiments and baselines are required to verify the results. At least, the  JR-PPO should be included to show the differences between joint ratio and independent ratios.", "summary_of_the_paper": "This paper investigates how to enforce the trust-region constraint by bounding independent ratios based on the number of agents for cooperative multi-agent reinforcement learning. The authors also show that the surrogate objectives of IPPO and MAPPO are essentially equivalent when their critics converge to a fixed point, which is also supported by the empirical results.", "summary_of_the_review": "In summary, I think this paper has some interesting results but can be further improved on both theoretical and experimental sides.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CTJPZ3NomOB", "reviewer": "Reviewer_YJEa", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n- Decentralized policy learning with monotonic joint policy improvement is a very important problem for MARL.  \n- A theoretical understanding for the good performance of IPPO and MAPPO is also desirable. \n\n**Problems**\n\n- The main contribution is Theorem 2, but I think there might be some mistakes in the proof of Theorem 2. In the deductions at the top of the page 14, from the fourth line to the fifth line in the equations,   $r(s_i) + \\cdots$ **is not equal** to $A_{\\pi_j}(s_i, a_i)$. Although you have mentioned that you use an approximation for $A_{\\pi_j}(s_i,a_i)$ in the footnote, I think it is inappropriate to use such an approximation in the proof especially when this is the main contribution of this paper. Moreover, this approximation actually ignores the *non-stationarity* caused by independent learnings which is the major obstacle for this problem in theory. \n\nThis is the major issue of this paper. Please clarify if I misunderstood something. \n", "summary_of_the_paper": "This paper tries to provide a theoretical monotonic improvement guarantees for  IPPO and MAPPO and shows enforcing independent trust region constraints could enforce the trust region constraint over joint policies. The empirical results are also provided to support the hypothesis.", "summary_of_the_review": "The approximation is inappropriate which makes the contribution of the paper meaningless, unless I left something important.\n\n### After rebuttal\n\nThere is an error in the proof of Theorem 2 which is claimed as the major contribution of this paper.  During rebuttal, the authors changed these equations (10 -15) several times, but unfortunately none of them are correct. In the latest revision (from equation 13 to 14), the $new$ definition of $A_{\\pi_j}$ is given (the definition below equation 15), but it does not have any actual meaning (i.e., it is *not* an advantage function), just a function by definition. This DOES NOT accord with the learning of IPPO, MAPPO, or any other MARL methods I know. \n\nThus, I keep my score unchanged. \n", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission cannot be accepted as there seems to be a mistake in the proof of the main contribution (Theorem 2).
Decision: Reject