Year: 2021

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) (Schröder de Witt et al., 2020) and Multi-Agent PPO (MAPPO) (Yu et al., 2021), 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.

heading: 1 INTRODUCTION
text: 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 a simulated or laboratory setting, decentralized policies can often be learned in a centralized fashion, i.e., Centralized Training with Decentralized Execution (CTDE)(Oliehoek & 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 a natural approach to CTDE because critics can exploit centralized training by conditioning on extra information not available to the decentralized policies (Lowe et 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., 2018) on MARL benchmark tasks such as Starcraft Multi-Agent Challenge (SMAC) (Samvelyan et al., 2019). However, two recent actor-critic algorithms (Schröder de Witt et al., 2020; Yu et al., 2021) have upended this ranking by outperforming previously dominant MARL methods, such as MADDPG (Lowe et al., 2017) and value-decomposed Q-learning (Sunehag et al., 2017; Rashid et al., 2018). Both algorithms are multi-agent extensions of Proximal Policy Optimization (PPO) (Schulman et al., 2017) but one uses decentralized critics, i.e., independent PPO (IPPO) (Schröder de Witt et al., 2020), and the other uses centralized critics, i.e., 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-agent setting by computing ratios separately for each agent’s policy during training, which we call independent ratios. Unfortunately, until now there has been no theoretical justification for the use of such independent ratios. In this paper we show that the analysis that underpins the monotonic
policy improvement guarantee for PPO (Schulman et al., 2015) does not carry 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.e., 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 a monotonic policy improvement guarantee. Moreover, as independent ratios consider only the change in one agent’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 a new monotonic improvement analysis that holds even when the transition dynamics are non-stationary. We show that, despite this non-stationarity, a 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 a 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 a fixed point.
Finally, we provide empirical results that 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. 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.

heading: 2 RELATED WORK
text: The use of trust region optimization in MARL traces back to parameter-sharing TRPO (PSTRPO) (Gupta et al., 2017), which combines parameter sharing with TRPO for cooperative multiagent continuous control but provides no theoretical support. Our analysis showing that a 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 independent learning and proposes to enforce a trust region constraint by approximating the stable fixed point via a meta-game. Despite the improvement guarantee for joint policies, solving a 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 to the multi-agent case (Li & He, 2020) and divides the trust region by the number of agents. However, the analysis assumes a private reward for each agent, which yields different theoretical results from ours. Non-stationarity has been discussed in multi-agent mirror descent with trust region decomposition (Li et al., 2021), 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 a fully centralized action-value function and thus becomes becomes impractical when there are many agents.

heading: 3 BACKGROUND
text: 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 a decentralized Markov
decision process (Dec-MDP), defined by a tuple {N ,S,A, P, r, ρ0, γ}, where N , {1, . . . , N} denotes the set ofN agents and s ∈ S , S1×S2×...×SN describes the joint state of the environment. The initial state s0 ∼ ρ0 is drawn from distribution ρ0, and at each time step t, all agents k ∈ N choose simultaneously one action akt ∈ Ak, yielding a joint action at , a1t × a2t × ...× aNt ∈ A , A1 ×A2 × ...×AN . After executing the joint action at in state st, the next state st+1 ∼ P (st,at) is drawn from transition kernel P and a collaborative reward rt = r(st,at) is returned. In a DecMDP, each agent k ∈ N has a local state skt ∈ Sk, and chooses its actions with a decentralized policy akt ∼ πk(·|skt ) based only on its local state. The collaborating team of agents aims to learn a joint policy, π(at|st) , ∏N k=1 πk(a k t |skt ), that maximizes their expected discounted return,
η(π) , E(st,at)[ ∑∞ t=0 γ trt], where γ ∈ [0, 1) is a discount factor.
Policy optimization methods. For single-agent RL that is modeled as an infinite-horizon discounted Markov decision process (MDP) {S,A, P, r, ρ0, γ}, the performance for a policy π(a|s) is defined as: η(π) = E(st,at) [∑∞ t=0 γ tr(st, at) ] . The action-value function Qπ and value function Vπ are defined as:
Qπ(st, at) = Est+1∼p(·|st,at), at+1∼π(·|st+1) [ ∞∑ l=0 γlr(st+l, at+l) ] , Vπ(st) = Eat∼π(·|st) [ Qπ(st, at) ] .
Let the advantage function be Aπ(s, a) = Qπ(s, a)− Vπ(s); the following useful identity expresses the expected return of another policy π̃ in terms of the advantage over π (Kakade & Langford, 2002): η(π̃) = η(π) + ∑ s ρπ̃(s) ∑ a π̃(a|s)Aπ(s, a), where ρπ̃(s) is the state distribution induced by π̃. The complex dependency of ρπ̃(s) on π̃ makes the righthand side difficult to optimize directly. Schulman et al. (2015) proposed to consider the following surrogate objective
Lπ(π̃) = η(π) + ∑ s ρπ(s) ∑ a π̃(a|s)Aπ(s, a) = η(π) + E(s,a)∼ρπ [ π̃(a|s) π(a|s) Aπ(s, a) ] ,
where the ρπ̃ is replaced with ρπ. Define DmaxTV (π, π̃) , maxsDTV ( π(·|s), π̃(·|s) ) , where DTV is the total variation (TV) divergence. Theorem 1. (Theorem 1 in Schulman et al. (2015)) Let α = DmaxTV (π, π̃). Then the following bound holds
η(π̃) ≥ Lπ(π̃)− 4 γ
(1− γ)2 α2,
where = maxs,a|Aπ(s, a)|.
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 et al., 2017). TRPO suggests a robust way to take large update steps by using a constraint, rather than a penalty, on the TV divergence, and considers the following practical optimization problem,
TRPO: max π̃ E(s,a)∼ρπ [ π̃(a|s) π(a|s) Aπ(s, a) ] , s.t. DmaxTV (π(·|s), π̃(·|s)) ≤ α. (1)
This constrained optimization is 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|s) π(a|s) to form a lower bound of Lπ(π̃):
PPO: max π̃
E(s,a)∼ρπ [ min ( λπ̃Aπ(s, a), clip(λπ̃, 1− , 1 + )Aπ(s, a) )] , (2)
where is a hyperparameter to specify the clipping range.
Independent PPO and Multi-Agent PPO. Both IPPO (Schröder de Witt et al., 2020) and MAPPO (Yu et al., 2021) optimize decentralized policies with independent ratios. In particular, the main objective IPPO and MAPPO optimize is
max π̃k
E(sk,ak)∼ρπk [ min ( λπ̃kA k(sk, ak), clip(λπ̃k , 1− , 1 + )Ak(sk, ak) )] ∀k ∈ {1, 2, ..., N},
(3)
where λπ̃k = π̃k(a k|sk) πk(ak|sk) denotes the ratio between the decentralized policy probabilities of agent k before and after updating. The difference between IPPO and MAPPO lies in how they estimate the advantage function: IPPO learns a decentralized advantage functionAk(sk, ak) , ∑∞ t=0[r(s k t , a k t )]− V (sk) based on the local information (sk, ak) for each agent, while MAPPO uses a centralized critic that conditions on centralized state information s: Ak(sk, ak) , Es−k [∑∞ t=0[r(s k t , a k t )] − 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 k in the objective and use experience from all agents to update the actor and critic networks:
max π̃θ ∑ k E(sk,ak)∼ρπθ [ min ( λθAφ(s k, ak), clip(λθ, 1− , 1 + )Aφ(sk, ak) )] , (4)
where λθ = π̃θ(a k|sk) πθ(ak|sk) , and θ, φ are 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).

heading: 4 TRUST REGION ANALYSIS FOR MARL
text: 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 a new analysis that shows how monotonic policy improvement can still arise from non-stationary transition dynamics with independent ratios.

heading: 4.1 OPTIMIZATION WITH JOINT RATIOS
text: Consider the joint policy π(a|s) and the centralized advantage function Aπ(s,a) = Qπ(s,a) − Vπ(s). Then, the trust region analysis for single-agent RL carries over directly to MARL with the surrogate objective as Lπ(π̃) = η(π) + ∑ s ρπ(s) ∑ a π̃(a|s)Aπ(s,a). One can consider the same optimization problem for TRPO shown in equation 1,
max π̃ E(s,a)∼ρπ [ π̃(a|s) π(a|s) Aπ(s,a) ] , s.t. DmaxTV (π(·|s), π̃(·|s)) ≤ α. (5)
The trust region constraint is enforced over joint policies, which we refer as a centralized trust region constraint. With joint ratios defined as λπ̃ = π̃(a|s) π(a|s) = ∏N k=1 [ π̃k(ak|sk) πk(ak|sk) ] , one can simplify the above optimization as PPO to have the following objective,
JR-PPO: max π̃
E(s,a)∼ρπ [ min ( λπ̃Aπ(s,a), clip(λπ̃, 1− , 1 + )Aπ(s,a) )] . (6)
We call the resulting algorithm Joint Ratio PPO (JR-PPO) (see Algorithm 1 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 analysis:, i.e., Theorem 1. Furthermore, the objective used in IPPO and MAPPO is not equivalent to the above objective as they are lower bounds of different objectives. Thus, Theorem 1 does not imply any guarantees for IPPO and MAPPO.

heading: 4.2 OPTIMIZATION WITH INDEPENDENT RATIOS
text: Optimization with independent ratios, however, induces non-stationarity in MARL. When optimizing decentralized policies, the environment is non-stationary from the perspective of a 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 sk induced by the underlying MDP for agent k. When all agents’ policies are updated from π1, ..., πN to π̃1, ..., π̃N , the state transition distribution of this Markov chain also shifts. We denote such transition shift from sk to s̃k for agent k as
∆π̃1,...,π̃Nπ1,...,πN (s̃ k|sk) , ∑ ak [ pπ̃1,...,π̃N (s̃ k|sk, ak)π̃k(ak|sk)− pπ1,...,πN (s̃k|sk, ak)πk(ak|sk) ] ,
where pπ1,...,πN and pπ̃1,...,π̃N 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 pπk to pπ̃k ), 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 πk to π̃k). See the appendix 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 policy changes. As a result, Theorem 1 no longer holds if one optimizes with independent ratios as in IPPO and MAPPO.

heading: 4.3 MONOTONIC POLICY IMPROVEMENT FOR INDEPENDENT RATIOS
text: 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 in 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 a Dec-MDP, the transition shift ∆π̃1,...,π̃Nπ1,...,πN (s̃ k|sk) decomposes as follows:
∆π̃1,...,π̃Nπ1,...,πN (s̃ k|sk) = ∆π̃1,π2,...,πNπ1,π2,...,πN (s̃ k|sk) + ∆π̃1,π̃2,π3,...,πNπ̃1,π2,π3,...,πN (s̃ k|sk) + ...+ ∆π̃1,...,π̃N−1,π̃Nπ̃1,...,π̃N−1,πN (s̃ k|sk).
The proof is given in the appendix A.3.1. This proposition implies that the state transition shift at local observation sk is caused by the shifts arising from all decentralized policies. This decomposition 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 πk as L(k)π1,π2,...,πN (π̃k′) = ∑ sk ρπ1,π2,...,πN (s k) ∑ ak π̃k′(a k|sk)Aπk′ (s k, ak),
and the expected return of decentralized policy πk as ηπ1,...,πN (πk) = E(sk,ak)∼ρπ1,...,πN (sk,ak) [ rk(s k, ak) ] .
In practice, rk(sk, ak) 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 a centralized trust region constraint as in equation 5. Theorem 2. Let α = DmaxTV (π, π̃). Then the following bound holds :
ηπ̃1,...,π̃N (π̃k) ≥ ηπ1,...,πN (πk) + N∑ k′=1 L(k)π1,...,πN (π̃k′)− 4 γ (1− γ)2 α2 ∀k,
where = maxk∈N maxsk,ak |Aπk(sk, ak)|.
The proof is given in the appendix A.3.2. This theorem implies that, for sufficiently small α, the performance increase of a decentralized policy πk is lower bounded by the sum of surrogate objectives for each decentralized policy with respect to the samples generated by πk. In other words, if the trust region is enforced, the sum of surrogate objectives yields an approximate lower bound for ηπ̃1,π̃2,...,π̃N (π̃k), which holds for any decentralized policy π̃k.
Theorem 2 differs from Theorem 1 in three respects. First, the lower bound for one decentralized 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 πk, we can simultaneously maximize L (k) π1,...,πN (π̃1) + L (k) π1,...,πN (π̃2) + ...+ L (k) π1,...,πN (π̃N ). Second, unlike the surrogate objective in Theorem 1, the new surrogate objective implicitly contains an independent ratio λπ̃k , π̃k(a k|sk) πk(ak|sk) as it can be rewritten as follows: L (k) π1,π2,...,πN (π̃k′) =
E(sk,ak) [ π̃k′ (a
k|sk) πk′ (a k|sk)Aπk(s k, ak) ] . Third, the additional term 4 γ(1−γ)2α
2 requires computing the total variation between joint policies π(a|s) and π̃(a|s), rather than the policies that are directly optimized. 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.

heading: 5 REALIZING TRUST REGIONS VIA BOUNDING INDEPENDENT RATIOS
text: 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 to enforce such a centralized trust region constraint, and this enforcement requires taking into account the number of agents. To achieve this, we first present two lemmas about DTV divergence.
Proposition 2. In a Dec-MDP, DmaxTV (π, π̃) ≤ ∑N k=1D max TV (πk, π̃k).
This proposition is a direct result of the fact that the joint policy in a Dec-MDP factors as a product of decentralized polices, i.e., π = ∏N k=1 πk .
Proposition 3. DmaxTV (πk, π̃k) = maxs∈S ∑ π̃k(ak|sk)≥πk(ak|sk) [ π̃k(a k|sk)− πk(ak|sk) ] .
This useful identity follows from a property of DTV: DTV(µ(x), ν(x)) = ∑ µ(x)>ν(x)[µ(x)− ν(x)] where µ and ν are two distributions. This proposition indicates that a 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 Aπk(sk, ak) converges to a fixed point for ∀k. Theorem 3. If independent ratios λk , π̃k(a k|sk)
πk(ak|sk) are within the range [1− k, 1 + k] for ∀k ∈ N , then the following bound holds: DmaxTV (πk(·|s), π̃k(·|s)) < k; DmaxTV (π(·|s), π̃(·|s)) < ∑N k=1 k.
This theorem comes from that fact that optimizing π̃(s, a) with respect to a converged A(s, a) leads to π̃(a|s) > π(a|s) if A(s, a) > 0, ∀s, a in actor-critic algorithms (Konda & Tsitsiklis, 2000). Thus, based on Proposition 3, we have the following
DmaxTV (πk, π̃k) = max sk ∑ ak∈Ak
Ak(s k,ak)>0
[π̃k(a k|sk)− πk(ak|sk)] ≤ max
sk
∑ a∈Ak
Ak(s k,ak)>0
[ kπk(a k|sk)] < k.
The equation is from Proposition 3 by considering A(s, a) > 0 such that π̃(a|s) > π(a|s). The first inequality is a result of bounded ratios and the second is from ∑ a∈{a:A(s,a)>0}[π(a|s)] < 1 (considering the lower bound yields the same analysis.) Furthermore, the trust region constraint over joint policies is a direct result of Proposition 2. The detailed proof is given in the appendix A.3.3. As DTV is a bounded divergence between [0, 1], the ratio guarantee makes sense when k ≤ 1.0.
Theorem 3 implies that bounding independent ratios π̃k(a k|sk)
πk(ak|sk) with [1 − k, 1 + k] amounts to enforcing a trust region constraint with size over decentralized policies. Thus, to enforce the centralized trust region constraint over joint policies, i.e., DmaxTV (π, π̃) ≤ α as in Theorem 2, one can consider bounding independent ratios according to the number of agents, e.g., λk , π̃k(a k|sk)
πk(ak|sk) ∈ [1− αN , 1 + α N ]. In the next section, we present practical implementations of these ratio constraints.

heading: 6 INSTANTIATING RATIO CONSTRAINTS
text: 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 a fixed point.

heading: 6.1 OPTIMIZING SURROGATE OBJECTIVES
text: The objective is to update all agents’ policies simultaneously with the experience from all agents, which can be further simplified with parameter sharing (Gupta et al., 2017):
max θ ∑ k ∑ sk ρπ1,π2,...,πN (s k) ∑ uk π̃θ(u k|sk)Aφ(sk, uk), (7)
s.t. DmaxTV (π(·|s), π̃(·|s)) ≤ α, (8)
where θ 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 7, similar to PPO (Schulman et al., 2017). Namely, with independent ratios λk = π̃θ(u
k|sk) πθ(uk|sk) ∀k ∈ N , we can optimize the following objective:
max θ ∑ k E(sk,uk)∼ρ(sk,uk) [ min ( λkAk, clip(λk, 1− , 1 + )Ak )] ,
which is exactly the objective used by IPPO and MAPPO.

heading: 6.2 ENFORCING THE TRUST REGION CONSTRAINT
text: 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 πk(ak|sk) is bounded. Therefore, to enforce the centralized trust region constraint, one can impose a sufficient condition as follows,
DmaxTV ( πθ(·|sk), π̃θ(·|sk) ) ≤ α N ∀k ∈ N , (9)
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 3, bounding independent ratios is an effective way to enforce the trust region constraint. One can thus impose a sufficient condition to constrain independent ratios λk such that λk ∈ [1− αN , 1 + α N ], where N is the number of agents in training. Clipping is one of 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 of epochs so the ratios can be properly bounded. We show in the experiment section 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.

heading: 6.3 LEARNING ADVANTAGE FUNCTIONS
text: We now look at the training of the advantage function, where IPPO and MAPPO differ. IPPO trains a decentralized advantage function, while MAPPO trains a centralized one that incorporates centralized state information. Assume a stationary distribution of (sk, ak) exists. From Lyu et al. (2021), we have the following:
Proposition 4. (Lemma 1 & 2 in Lyu et al. (2021)) Training of centralized critic and k-th decentralized critic admits unique fixed points Qπ(sk, s−k, ak, a−k) and Es−k,a−k [Qπ(sk, s−k, ak, a−k)] respectively, where Qπ is the true expected return under the joint policy π.
Accordingly, based on the definition, the centralized value function is V (s) = V (sk, s−k) = Eak,a−k [Qπ(sk, s−k, ak, a−k)] and the decentralized one is V (sk) = Es−k,ak,a−k [Qπ(sk, s−k, uk, a−k)] = Es−k [V (sk, s−k)] = Es−k [V (s)]. Thus, we have AIPPO(sk, ak) = AMAPPO(sk, ak) (and so IPPO and MAPPO objectives are equivalent) given that the underlying critics converge to a fixed point.

heading: 7 EXPERIMENTS
text: 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 on SMAC maps with varied difficulty and numbers of agents.
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 are properly set. We train decentralized policies on one map, 2s3z, and clip the independent ratios when optimizing the surrogate objective. Figure 1a 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 are properly specified. In particular, the range of independent ratios grows as the number of optimization epochs increases. This growth is slower when the clipping range is smaller, e.g., = 0.1. Furthermore, the clipping range may not strictly bound ratios between [1− , 1 + ]: when the clipping range is 0.1, the independent ratios can exceed 1.2; and the independent ratios can even grow up to 1.6 when the clipping range is 0.3.
Ratio clipping and trust region constraint. Next, we show that the trust region defined by the total variation is empirically bounded by independent ratio clipping, and this bound is also proportional to the number of agents. Specifically, we compute the maximum total variation divergence DmaxTV 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 DmaxTV . Figure 1b shows the distribution of DmaxTV over decentralized policies when clipping range varies. For clipping at 0.1, all DmaxTV values are smaller than 0.2, meaning that the trust region is effectively enforced to be small. As the clipping range increases, more DmaxTV values exceed 0.3. For the case without clipping, DmaxTV almost uniformly distributes among [0.0, 0.8], implying trust region is no longer enforced. Figure 1c presents the distribution of DmaxTV over joint polices for clipping at 0.1, on maps with different number of agents. See appendix Table 1 for more details. The DmaxTV (π, π̃) is estimated by summing up the empirical total variation distances DmaxTV (πk, π̃k) over all agents. The D max TV (π, π̃) 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 1d presents the distribution of DmaxTV 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 on SMAC Figure 2 shows the empirical returns and trust region estimates with different ratio clipping values across different maps in SMAC. 1 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 = 0.1 in the initial training phase also grows from less than 0.3 to more than 0.5. In contrast, for clipping at
1Trained via decentralized advantage, i.e., IPPO. Results with centralized advantage are similar, as presented in the appendix A.4. Unlike Yu et al. (2021), the value function is not clipped in our experiments.
0.5 and 1.0, the learning quickly plateaus at local optima, especially on maps with many agents, e.g., 10m_vs_11m and 27m_vs_30m, which shows that the policy performance η(πk) is 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 are 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 set the clipping range for 3s5z, 1c3s5z, 10m_vs_11m, and bane_vs_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. (2021), which provides more empirical comparisons between IPPO and MAPPO. Such comparable performance also implies that, for actor-critic methods in MARL, the way of training critics could be less crucial than enforcing the trust region constraint.

heading: 8 CONCLUSION
text: In this paper, we present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative MARL. We show that, despite the non-stationarity in 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 a theoretical foundation for proximal ratio clipping by showing that a trust region constraint can be effectively enforced in a principled way by bounding independent ratios based on the number of agents in training. 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.

heading: A APPENDIX

heading: A.1 JOINT RATIO PPO
text: Algorithm 1 Joint Ratio PPO (JR-PPO) for iteration i = 0, 1, 2, . . . do
Roll out decentralized policies [π1, π2, ..., πN ] in environment; Compute centralized advantage estimates A(s,a); Compute joint ratios λπ̃ = π̃(a|s) π(a|s) = ∏N k=1 [ π̃k(ak|sk) πk(ak|sk) ] ;
Optimize the surrogate objective maxπ̃ E [ min ( λπ̃A(s,a), clip(λπ̃, 1− , 1 + )A(s,a) )] .
end for

heading: A.2 STATIONARITY ASSUMPTION IN TRPO
text: The single-agent TRPO relies on the following analysis:
Lπ(π̃)− Lπ(π) = ∑ s ρ(s) ∑ a ( π̃(a|s)− π(a|s) ) Aπ(s, a)
= ∑ s ρ(s) ∑ a ( π̃(a|s)− π(a|s) )[ r(s) + ∑ s′ p(s′|s, a)γv(s′)− v(s) ]
= ∑ s ρ(s) ∑ s′ ∑ a ( π̃(a|s)− π(a|s) ) p(s′|s, a)γv(s′)
= ∑ s ρ(s) ∑ s′ ∑ a ( π̃(a|s)p(s′|s, a)− π(a|s)p(s′|s, a) ) γv(s′)
= ∑ s ρ(s) ∑ s′ ( pπ̃(s ′|s)− pπ(s′|s) ) γv(s′).
This analysis is based on the assumption that p(s′|s, a) remains the same before and after π is updated, such that transition shift pπ̃(s′|s) − pπ(s′|s) is only caused by the agent’s policy update, i.e., endogenously. Such analysis no longer holds when the transition dynamics p(s′|s, a) are non-stationary: pπ̃(s′|s, a) 6= pπ(s′|s, a).

heading: A.3 PROOFS

heading: A.3.1 PROOF OF PROPOSITION 1
text: Proof. Assume agent k’s policy πk is executed independently of other agents policies π−k, we have
∆π̃ 1,...,π̃N
π1,...,πN (s̃k|sk) = ∑
s̃−k,s−k
ak,a−k
p(s̃k, s̃−k|sk, s−k, ak, a−k) [ π̃k(ak|sk)π̃−k(a−k|s−k)− πk(ak|sk)π−k(a−k|s−k) ]
= ∑
s̃−k,s−k
ak,a−k
p(s̃k, s̃−k|sk, s−k, ak, a−k) · [ π̃k(ak|sk)π̃−k(a−k|s−k)− π̃k(ak|sk)π−k(a−k|s−k)︸ ︷︷ ︸
exogenous
+ π̃k(ak|zk)π−k(a−k|s−k)− πk(ak|sk)π−k(a−k|s−k)︸ ︷︷ ︸ endogenous
] .
The above decomposition can be repeated such that the exogenous part can be translated into endogenous parts that are specific to each agent. Specifically, repeat the decomposition for the
exogenous part by considering agent k′ (k′ 6= k):
π̃k(ak|sk)π̃−k(a−k|s−k)− π̃k(ak|sk)π−k(a−k|s−k) =π̃k(ak|sk) [ π̃k ′ (ak ′ |sk ′ )π̃−{k,k ′}(a−{k,k ′}|s−{k,k ′})− πk ′ (ak ′ |sk ′ )π−{k,k ′}(a−{k,k ′}|s−{k,k ′}) ]
=π̃k(ak|sk) [ π̃k ′ (ak ′ |sk ′ )π̃−{k,k ′}(a−{k,k ′}|s−{k,k ′})− π̃k ′ (ak ′ |sk ′ )π−{k,k ′}(a−{k,k ′}|s−{k,k
′})︸ ︷︷ ︸ πk-exogenous
+ π̃k ′ (ak ′ |sk ′ )π−{k,k ′}(a−{k,k ′}|s−{k,k ′})− πk ′ (ak ′ |sk ′ )π−{k,k ′}(a−{k,k ′}|s−{k,k ′})︸ ︷︷ ︸ πk-endogenous .
So on and so forth, one can decompose ∆π̃ 1,...,π̃N
π1,...,πN (s̃k|sk) as follows:
∆π̃ 1,...,π̃N π1,...,πN (s̃k|sk) = ∆π̃ 1,π2,...,πN π1,π2,...,πN (s̃k|sk) + ∆π̃ 1,π̃2,π3,...,πN π̃1,π2,π3,...,πN (s̃k|sk) + ...+ ∆π̃ 1,...,π̃N−1,π̃N π̃1,...,π̃N−1,πN (s̃k|sk),
which implies that the state transition shift at local observation sk is caused by the shifts arising from all decentralized policies.

heading: A.3.2 PROOF OF THEOREM 2
text: Proof. This proof is based on the perturbation theory. Let Gsi = (1 + γP siπ1,π2,...,πN + (γP siπ1,π2,...,πN ) 2 + ... = (1− γP siπ1,π2,...,πN ) −1 and G̃si = (1 + γP siπ̃1,π̃2,...,π̃N + (γP si π̃1,π̃2,...,π̃N )2 + ... = (1−γP siπ̃1,π̃2,...,π̃N ) −1 denote the distribution of state si under π1, π2, ..., πN and π̃1, π̃2, ..., π̃N . We will use the convention that ρ (a density on state space) is a vector and r (a reward function on state space) is a dual vector (i.e., linear functional on vectors), thus rρ is a scalar meaning the expected reward under density ρ. Note that η(π) = rGρ0, and η(π̃) = rG̃ρ0. Denote the state shift of si as ∆(si) = P siπ̃1,π̃2,...,π̃N − P si π1,π2,...,πN . Using the perturbation theory, we have the following
[Gsi ]−1 − [G̃si ]−1 = γP siπ̃1,π̃2,...,π̃N − γP si π1,π2,...,πN = γ∆(si).
Left multiply by Gsi and right multiply by G̃si :
G̃si = Gsi + γGsi∆(si)G̃ si .
Substituting the right-hand side into G̃si gives
G̃si −Gsi = γGsi∆(si)Gsi + γ2Gsi∆(si)Gsi∆(si)G̃si).
Consider decentralized policy πi:
ηπ̃1,π̃2,...,π̃N (π̃i)− ηπ1,π2,...,πN (πi) =rG̃siρ0 − rGsiρ0 = r(G̃si −Gsi)ρ0 =γrGsi∆(si)G siρ0 + γ 2rGsi∆(si)G si∆(si)G̃ siρ0.
Let us first consider the leading term γrGsi∆(si)Gsiρ0,
γrGsi∆(si)G siρ0 = ∑ si ρ(si) ∑ s′i (pπ̃(s ′ i|si)− pπ(s′i|si))γv(s′i) = ∑ si ρ(si) ∑ s′i ∆π̃1,...,π̃Nπ1,...,πN (s ′ i|si)γv(s′i)
= ∑ si ρ(si) ∑ s′i [ ∆π̃1,π2,...,πNπ1,π2,...,πN (s ′ i|si) + ∆ π̃1,π̃2,π3,...,πN π̃1,π2,π3,...,πN (s′i|si) + ...+ ∆ π̃1,...,π̃N−1,π̃N π̃1,...,π̃N−1,πN (s′i|si) ] γv(s′i).
For one of these summation terms, we have the following 2:∑ si ρ(si) ∑ s′i [ ∆ π̃1,...,π̃j−1,π̃j ,...,πN π̃1,...,π̃j−1,πj ,...,πN (s′i|si) ] γv(s′i) (10)
= ∑ si ρ(si) ∑ s′i ∑ ai ( pπ̃1,...,π̃j−1,πj ,...,πN (s ′ i|si, ai)π̃j(ai|si)− pπ̃1,...,π̃j−1,πj ,...,πN (s′i|si, ai)πj(ai|si) ) γv(s′i)
(11) = ∑ si ρ(si) ∑ ai ( π̃j(ai|si)− πj(ai|si) )∑ s′i pπ̃1,...,π̃j−1,πj ,...,πN (s ′ i|si, ai)γv(s′i) (12)
= ∑ si ρ(si) ∑ ai ( π̃j(ai|si)− πj(ai|si) )[ r(si) + ∑ s′i pπ̃1,...,π̃j−1,πj ,...,πN (s ′ i|si, ai)γv(s′i)− vπ̃1,...,π̃j−1, πj ,...,πN (si) ]
(13) = ∑ si ρ(si) ∑ ai ( π̃j(ai|si)− πj(ai|si) ) Aπj (si, ai) (14)
=L(i)π1,π2,...,πN (π̃j)− L (i) π1,π2,...,πN (πj). (15) The derivation from line 13 to 14 is based on the following definition:
Aπj (si, ai) , r(si) + ∑ s′i pπ̃1,...,π̃j−1,πj ,...,πN (s ′ i|si, ai)γv(s′i)− vπ̃1,...,π̃j−1, πj ,...,πN (si),
where vπ̃1,...,π̃j−1, πj ,...,πN
(si) , r(si) + γ ∑ s′i pπ̃1,...,π̃j−1,πj ,...,πN (s ′ i|si, ai) ∑ ai πj(ai|si)v(s′i). which
will result in L(i)π1,π2,...,πN (πj) = 0 for ∀j. In fact, for line 13, r(si) and vπ̃1,...,π̃j−1, πj ,...,πN (si) can be interpreted as functions over si, which will be zero if integrated with ∑ ai ( π̃j(ai|si)− πj(ai|si) ) . Note that the advantage function also conditions on the πj .
Note that the advantage of πj with respect to si, ai 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:
γrGsi∆(si)G siρ0 = L (i) π1,π2,...,πN (π̃1)− L (i) π1,π2,...,πN (π1)
+ L(i)π1,π2,...,πN (π̃2)− L (i) π1,π2,...,πN (π2)
+ ...+ L(i)π1,π2,...,πN (π̃N )− L (i) π1,π2,...,πN (πN ).
Note that L(i)π1,π2,...,πN (πj) = 0 for ∀j. Thus, γrGsi∆(si)G siρ0 = L (i) π1,π2,...,πN (π̃1) + L (i) π1,π2,...,πN (π̃2) + ...+ L (i) π1,π2,...,πN (π̃N ).
Next we bound the second term γ2rGsi∆(si)Gsi∆(si)G̃siρ0. First we consider the product γrGsi∆(si) = γv∆(si). Consider the component of this dual vector:
|(γrGsi∆(si)s| = | ∑ s′i (pπ̃i(s ′ i|si)− pπi(s′i|si))γvi(s′i)|
=| ∑
s′1,...,s ′ N
∑ s1,...,si−1,si+1,sN ∑ a1,...,aN p(s′1, ..., s ′ N |s1, ..., sN , a1, ..., aN )vi(s′i) [ N∏ j=1 π̃j(ai|si)− N∏ j=1 πj(ai|si) ] |
=| ∑
s1,...,si−1,si+1,sN ∑ a1,...,aN Ai(si, ai) [ N∏ j=1 π̃j(ai|si)− N∏ j=1 πj(ai|si) ] |.
Thus, we have
‖(γrGsi∆(si)s‖ ≤ ∑
s1,...,sN ∑ a1,...,aN |Ai(si, ai)|| N∏ j=1 π̃j(ai|si)− N∏ j=1 πj(ai|si)| ≤ 2α .
2 Note that Aπj (si, ai) in the analysis is defined with the transition dynamics pπ̃1,...,π̃j−1,πj ,...,πN (s ′ i|si, ai).
We bound the other portion Gsi∆(si)G̃siρ0 using the l1 operator norm:
‖Gsi∆(si)G̃siρ0‖1 ≤ ‖∆(si)‖1 (1− γ)2 .
The ‖∆(si)‖1 can be bound as follows: ‖∆(si)‖1 = ∑ s′i,si |pπ̃i(s′i|si)− pπi(s′i|si)|
= ∑
s′1,...,s ′ N
∑ s1,...,sN ∑ a1,...,aN p(s′1, ..., s ′ N |s1, ..., sN , a1, ..., aN )| N∏ j=1 π̃j(ai|si)− N∏ j=1 πj(ai|si)|
= ∑
s1,...,sN ∑ a1,...,aN | N∏ j=1 π̃j(ai|si)− N∏ j=1 πj(ai|si)| ≤ 2α.
So we have that
γ2|rGsi∆(si)Gsi∆(si)G̃siρ0| ≤ γ‖rGsi∆(si)‖∞‖Gsi∆(si)G̃siρ0‖1 ≤ 4 γ
(1− γ)2 α2.

heading: A.3.3 PROOF OF THEOREM 3
text: Proof. Given the assumption that the advantage function A(s, a) converges to a fixed point. we have the fact that optimizing π̃(s, a) with respect toA(s, a) leads to π̃(a|s) > π(a|s) ifA(s, a) > 0, ∀s, a. Consider independent ratios λk , π̃k(a k|sk)
πk(ak|sk) which are within the range [1− k, 1 + k] for ∀k ∈ N , Thus, based on Proposition 3, we have the following
DmaxTV (πk, π̃k) = max sk ∑ ak∈Ak
π̃(a|s)>π(a|s)
[π̃k(a k|sk)− πk(ak|sk)]
≤ max sk ∑ ak∈Ak
Ak(s k,ak)>0
[(1 + k)πk(a k|sk)− πk(ak|sk)]
≤ max sk ∑ a∈Ak
Ak(s k,ak)>0
[ kπk(a k|sk)] < k.
The first inequality is a result of bounded ratios and the second is from ∑ a∈{a:A(s,a)>0}[π(a|s)] < 1. Furthermore, the trust region constraint over joint policies is a direct result of Proposition 2. One can also consider A(s, a) < 0, which leads to π̃(a|s) < π(a|s) in optimization. Given that independent ratios are also lower bounded by 1− , the same conclusion can be reached for DmaxTV .

heading: A.4 EXPERIMENT DETAILS AND MORE RESULTS
text: The number of agents in each is given in Table 1.
Test battle win mean of IPPO on maps with varied difficulty and numbers of agents is presented in Figure 4.
Empirical test battle win mean, test returns and trust region estimates of MAPPO on maps with varied difficult and numbers of agents are presented in Figure 5.

heading: A.5 ABLATIONS ON SMALL CLIPPING VALUES
text: We also present the ablation results for small clipping values, i.e., < 0.1, in Figure 6. It is true that a small clipping value results in a small trust region, and thus small clipping values, e.g., 0.08, 0.05 and 0.03, would be preferred for maps with a large number of agents, e.g., maps 10m_vs_11m (10
agents) and 27m_vs_30m (27 agents). However, when the clip value is too small, e.g., = 0.01 in maps with 5 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, to ensure monotonic improvement, and the policy update step, to ensure a sufficient parameter update at each iteration.

heading: A.6 COMPARISON BETWEEN JOINT RATIO CLIPPING AND INDEPENDENT RATIO CLIPPING
text: We apply the same clipping values to these two types of clipping, and use maps with many agents, i.e., 10m_vs_11m and 27m_vs_30m, to make the difference more salient (based on the theoretical results in the paper). The results are presented in Figure 7 and 8.
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., = 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 is also aligned with our theoretical analysis.

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