Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning
Authors: Lijun Zhang
Lin Li
Wei Wei
Huizhong Song
Yaodong Yang
Jiye Liang
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-agent reinforcement learning
policy optimization
safe learning
scalable method
Primary area: reinforcement_learning
TL;DR: We develop a novel scalable multi-agent constrained policy optimization method and prove that the safety constraints and the joint policy improvement can be met when each agent adopts a sequential update scheme to optimize a $\kappa$-hop policy.

Abstract: A challenging problem in seeking to bring multi-agent reinforcement learning (MARL) techniques into real-world applications, such as autonomous driving and drone swarms, is how to control multiple agents safely and cooperatively to accomplish tasks. Most existing safe MARL methods learn the centralized value function by introducing a global state to guide safety cooperation. However, the global coupling arising from agents’ safety constraints and the exponential growth of the state-action space size limit their applicability in instant communication or computing resource-constrained systems and larger multi-agent systems. In this paper, we develop a novel scalable and theoretically-justified multi-agent constrained policy optimization method. This method utilizes the rigorous bounds of the trust region method and the bounds of the truncated advantage function to provide a new local policy optimization objective for each agent. Also, we prove that the safety constraints and the joint policy improvement can be met when each agent adopts a sequential update scheme to optimize a $\kappa$-hop policy. Then, we propose a practical algorithm called Scalable MAPPO-Lagrangian (Scal-MAPPO-L). The proposed method’s effectiveness is verified on a collection of benchmark tasks, and the results support our theory that decentralized training with local interactions can still improve reward performance and satisfy safe constraints.

Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning
Lijun Zhang', Lin Li', Wei Wei'r Huizhong Song', Yaodong Yang", Jiye Liang' 1. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, School of Computer and Information Technology. Shanxi University, Taiyuan, Shanxi, China.
Institute for AI, Peking University, Beijing, China.
Abstract
A challenging problem in seeking to bring multi-agent reinforcement learning (MARL) techniques into real-world applications. such as autonomous driving and drone swarms, is how to control multiple agents safely and cooperatively to accomplish tasks. Most existing safe MARL. methods learn the centralized value function by introducing global state to guide safety cooperation. However, the global coupling arising from safety constraints and the exponential growth of the state-action space size limit their applicability in instant communication or computing resource-constrainee systems and larger multi-agent systems. In this paper, we develop novel scalable and theoretically-jjstifeed multi-agent constrained policy optimization method. This method integrates the rigorous bounds of the trust region method and the bounds of the truncated advantage function to provide a new local policy optimization objective for each agent. Also, be
we prove that the safety constraints and the joint policy improvement met when each agent adopts sequential update scheme to optimize a re-hop policy. Furthermore, we propose practical algorithm called Scalable MAPPÓ- Lagrangian -SPaO-M- The proposed method's effectiveness is verified on a collection of benchmark tasks, and the results support our theory that decentralized training with local interactions can still improve reward performance and satisfy safe constraints.
Introduction
With the advanced and rapid developments of reinforcement learning technology, many researchers have gradually shifted their focus from virtual simulation to real-world cyber-physical applications [I 2]. In this process, safety challenges are inevitable, especially in multi-agent safety-critical scenarios, e.g., autonomous vehicle navigation (3], power grids [4) and drone swarms (5), in which agents perform complex cooperative tasks while adhering variety of local and system-wide limitations or constraints. These constraints can be derived from domain-specific knowledge and are intended prevent damage to people or other environmental elements, such as equipment and infrastructure, or to prevent the inability to accomplish specific tasks or objectives. Take multi-robot control as an example. Each running robot must not take certain actions or not visit certain states, which may imply unsafe for itself, its collaborators, or the infrastructure of its environment [6] These widespread potential dangers exacerbate the difficulty of safety decision decision-making when applying MARL. Consequently, it is necessary to research the safe decision decision-making making problem in MARL to ensure that agents can work together safely and cooperatively to accomplish tasks.
*Correspondence to wwwivei dexu...xu... edu. en>
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

There are two main approaches concerning safe MARL techniques in the existing literature. The first type is shielded-based reactive methods 77 8 which combine environmental dynamics and safety specification constraints to predict whether the actions chosen by agents will violate cost constraints. Nevertheless, due to the reliance on precise modeling knowledge, these methods may lead to poor performance when the accurate state transition model is unavailable. The second type formulates the safe MARL problem as a constrained Markov game, which requires agents to solve constrained optimization problem, i.e., maximize total reward while avoiding violating cost constraints. To mention a few, several safe MARL variants, such as CMIX [1] and MAPPO-L [0], have been proposed, which learn the centralized value function overcome policy conflicts caused by the partially observable and non-stationarity nature of the environment faced by each agent. Unfortunately, the global coupling arising from agents' safety constraints and the exponential growth of the state-action space size make the usability of these algorithms in instant communication or computing resourceeconstraiine systems and the scalability in larger multi-agent systems become bottleneck, limiting their applicability.
A promising approach for avoiding these shortcomings, which has received attention in recent years, is to exploit networked application-speeifie structures. For example, Safe Dec-PG [ employs primal-dual framework to find the saddle point between maximizing decoupled rewards and minimizing costs under a consensus network. However, it is worth noting that this approach still assumes each agent access the global state and requires that the actions of all neighboring agents on the network be available. Recent research [2] proposes a scalable safe MARL approach based on the spatial decay assumption of the environment dynamics, which updates the policies of agents by the truncated gradient estimators depending on the local states and actions of the k-hop neighboring agents. However, due to the dependence necessarily involves joint training in a local area, which is still plagued by non-stationary issues. Motivated by the urgent desire for scalable learning practical applications and the fact that meeting both safety constraints and joint policy improvement is challenging for most methods, we investigate a novel scalable safe MARL with theoretical analysis, practical algorithm, and simulation verification.
the actions and states of its neighbors, this method
Specifically, we focus on decentralized learning settings without global observability, where each agent only access the local state information of itself and its neighbors. Our main contributions are summarized as follows.
We develop a novel scalable multi-agent constrained policy optimization method that eliminates dependence on the global state and other agent actions during each agent's training. Furthermore, we parameterize each agent's policy and propose a practical algorithm called Scalable MAPPO-Lagrangian (Scal-MAPPO-L).
We quantify the maximum information loss regarding the advantage truncation based two assumptions about the transition dynamics and policies. Then, each agent's 's new local policy optimization objective is provided by integrating the rigorous bounds of the trust region method and the bounds of the truncated advantage function. In addition, we prove that the safety constraints and the joint policy improvement can be guaranteed when updating the local policy with a sequential update scheme.
Experimentally, we provide the results on several safe MARL tasks to evaluate the ef- fectiveness of our proposed method and the sensitivity for the parameter k. The results support our theory that decentralized training with local interactions can still improve reward performance and satisfy safe constraints.
2 Preliminaries
2.1 Constrained Markoy game
Consider a safe MARL problem subject to multiple constraints, where each agent are associated with an underlying undirected graph g = (W,E), E). Here, = f1,..., n is the set of n agents and C N A is the set of edges. The problem can be formulated as a constrained Markov game (N, A, P. Po: 7, R. c).. S St and A = X'eNA' are the state and action spaces, which are the product of local spaces; global state s = (s1 ".......""" .....))) and joint action a (a?,...,a") a") for any E S and E A. P: S x AxS - R is the probabilistic transition dynamics function, which

---

satisfies the Dobrushin condition 13 as follows:
W
|| - 2/ 2/ --
sup
where z = (s', a2) and n² (s 2²)) represent two different state-action pairs of the agent respectively, and z represents the state-action pair of the agent other than j. The value of W reflects the extent which the local transition probability of agent is affected by the state and action of agent j. Po is the initial state distribution, 7 E [0, 1) is the discount factor. the joint reward function, = {C) is the sets of cost functions (every agent i has m cost functions) of the form Cj St x A' - R. and finally the set of corresponding cost values is given by c=
x A - R is
{c) JEN is'""""""
At each timestep t, every agent is in a state si and takes an action aj according to its policy n' = (a Together with other agents actions, gives a joint action a, (a) ..... a, and the joint policy = [ x² (a The agents receive the reward R (St, az). meanwhile each agent i pays the costs Cj (st, af) A l...., m², and all agents have joint goal, i.e., maximizing the expected total reward of
J JTr A E Ao:00
R(s; ar)
meanwhile satisfying every agent i's safety constraints, written as
2
(T] Ego P 20
Σ
NCJ(s,. a!) S sc l...,
m
(3)
2.2 Spatial correlation decay
Exponential decay property [13 14]. also known spatial correlation decay, is powerful prop- erty associated with local interactions, which says that the impact of agents on each other decays exponentially in their graph distance. More information about spatial correlation decay is presented in Appendix B.T Here, inspired by [I5,, we make the following two assumptions for the spatial correlation of the transition dynamics and policies. We use the notation xt x'(+(sN;) for k-hop policies,
where SAy: represents the state of agent i's k-hop neighbors. It may be replaced with म. for simplicity when it is clear from context.
Assumption 2.1. (Spatial Decay of Correlation for the Dynamics) Assume that there exist 3 > in for any agents i,j E N, such that
max
AdlLD SC
(4)
KEN
JEN
where d(i,j) represents the distance between agent i and agent j. and ( E [0, 2/7)) is a constant.
Assumption 2.2. (Spatial Decay of Correlation for the Policies) Assume that there exist 3 2 such that for any agent i N, SAN SNy , SNN=,, one have
T (1552)) - x² (15N S Ee Ee-Br.
sup
(5)
Syg 1 x=²
Assumption 2.2 reveals how much information is lost compared with access the global state and allows us to consider a policy class with the necessary properties for the optimal policy under Assumption 2.1 More information stated in Appendix B.2
3 Scalable constrained policy optimization
This section develops a novel scalable and theoretically-justiiiee multi-agent constrained policy optimization method and proposes practical algorithm, i.e., Scal-MAPPO-L. by parameterizing each agent's policy. Specifically, first quantify the maximum information loss regarding the
3

---

advantage truncation based on the spatial correlation decay property of the transition dynamics and policies. Then, the rigorous bounds of the trust region method and the bounds of the truncated advantage function are integrated to provide a new local policy optimization objective for each agent. Further, we prove that the safety constraints and the joint policy improvement can guaranteed when updating the local police with sequential update scheme, in which the policy update only depends on its action and the state its k-hop neighbors for each agent.
3.1 Truncated advantage function estimator
For standard safe MARL, the state-action value function (the definition can be seen in Appendix and advantage function of agent yield that
(s, = Ea ir 2t (s,
(6)
(s, ,a) = QH, aa, Q+,
(7)
where s represents the global state, a represents the actions of all other agents, and Q*'(s, a² a²) represents the state-action value function of agent and agent j. Then, updating agents' policies with a sequential update scheme [16], the multi-agent joint advantage function A (s, a) can be written as
of sequentially unfolding multi-agent advantages of individual agents, as stated by the following lemma.
Lemma 3.1. (Multi-agent advantage decomposition). For any action a E N, and the state E S. the following identity holds
(s a) Σ (s)
Similar result to Lemma [.] can be seen in [10] and the proof is reported in Appendix C.2 Specif- ically, based on the multi-agent advantage decomposition in Lemma 3.1 the "surrogate" return is given as follows.
Definition 3.2. Let æ be a joint policy, 1 some other joint policy of agents : i 1, and # be a policy of agent Then, the surrogate return can be defined
I 1:
T 1:1-1
Exppp -10-) [4 (s, (: ,aa]]
(9)
Building on Lemma
3.1 and Definition 3.2. one can obtain
1:
Eg H1i
Σ A (s, 2::22-11,000 ,2t))
(10)
Further, recalling Assumption 2.1 and Assumption 2.2 we can quantify the maximum information loss regarding the advantage function stated by the following proposition.
Proposition 3.3. For any agent E N. let the parameters (n, (f e If A'ssupptoon 2.1
and Assumption 2.2 hold, for any uNz (sNt;aw)) &Ny ANt. the exponential decay property of the advantage Junction holds, iee, we have
sup
A
( (NN):RN=) A² (NNE: S 1p0
(11)
2N NC.
Proposition 3.3 shows that when the transition dynamics and policies correlation satisfy the exponen- tial correlation decay property, the advantage functions also have exponential decay dependence on the states and actions of the more distant agents. The proof of Proposition 3.3 is reported in Appendix In addition, based on this proposition, we can obtain the following corollary.
Corollary 3.4. For any agent E N, let the parameters (n/
( A
(1-7 + 1-76 .e-)). M is
(2+5)5
constant. If Proposition 3.3 holds, the exponential decay property of the surrogate return holds, ie.. we have
I (7 1:i-1 , =²
L
(#x)
S 1/ n
(12)

---

The proofs of Corollary 3.4 is reported in Appendix C.4
Corollary 3.4 shows that the approximation error of "h (#() decreases exponentially with when the truncated advantage functions are bounded. The main advantage of using the estimator L4 (#t) lies in that every agent only needs know the action and state of its k-hop neighbors, which can significantly reduce the communication burden and expand its application scenarios.
3.2 Scalable constrained policy optimization
With the Definition 3.2 we see that Lemma 3.1 allows for decomposing the joint surrogate return
I (Tt - Eappp a-= A (s, a)] into a sum over surrogates of L (# (=1-i_, #*) Then, combining
the rigorous bounds of the trust region method [17] and the bounds of the truncated advantage
function, we can obtain the following proposition.
Proposition 3.5. Let æ and गे be joint policies. Let each agent N sequentially solves the following optimization problem:
n arg max Lig (#/))
1/05 o/ DRI. (T (1))
(13)
$
where (1',0) = ( M'E
+
(2+ENC e e-9).
27 max
Ny (1-7)²
ant A's (2x22 at))
and DRES (m²)*t) =
T-7
I-76
maxsNz DEL (x' (8xx)) ); #'( (|sx2))) )), then the resulting joint policy H will improve the expected return, i.e.
N
Σ 1=1
(#x) - 1/65 - DRL
max (m((+t)
(14)
The proof of Proposition 3.5 is reported in Appendix C.S
Similarly, by generalizing the result about the surrogate return in Equation (12), we can derive how the expected costs change when the agents update their policies. Specifically, we provide the following corollary.
Corollary 3.6. Let π and स be joint policies. For any agent i E N and its cost index E +f....,,'' m').
the following inequality holds
i-1
Ji( S (T( + I. (#+) + 11" 00= + vj,n.
Σ h=1
Diax (x =²))
(15)
24 max, Ny as Ajing (evz a²)
where j (T%) Ne upak aatwey [1g [AS a.)
Un
(1-y}²
(r"" () = - + 1-76
M,g (2+EnS and Mj is a constant.
The proofs of Corollary 3.6 is reported in Appendix C.6
From (14), we can derive that the lower bound for the difference between the new joint policy म and the old joint policy π in terms of expected return can be decomposed into a cumulative sum of local surrogate TRPO policy objectives. From (15), can derive the upper bound for the new joint policy t, which can be used to restrict agents only to choose safe actions. Therefore, we use the objective, i... maximize the lower bound for the reward performance and minimize the upper bound for the safety constraints with a proper update size, as a surrogate for each agent. Then, we can obtaine the following theorem.
The joint policy π has the monotonic improvement property, J ( 2 J (TT), as well as it satisfies the safety constraints, Jÿ (#) S é₁ for any agent N and its cost index j E (1....,m'' m²). when the policy is updated by following a sequential update scheme, that is, each agent sequentially solves the following optimization problem:
Theorem 3.7.
# arg max
(Lig (#%) n' v ViDREE (mT)
*
s.t. { IT
DREX ( #t)) S 5%,, and
(16)
Jj (mx) + DJ (#t) + 11" dh + us DRLe (x) S - -VS,n Ei D max (# #1) }
5

---

53 L.a
Rinh (=+)
where 6x
min minnss-1 min sism!
mim min Sism! 1j.2
2ny max,
wg af
Al; (a))
2y max,
aad A (exg.at)
vi
(1',
(1-1)²
(1-2)²
M'S + (2+8)7
1-76 ; 1
(17"
12+507 M,S
I-76 , e.).
cg. - J (T
1-y
=
I-7
7iN Ei=l DRL (T #/4
The proof of Theorem 3.7 is reported in Appendix C.7 It assures that if one follows T6 to update policies, agents will not only explore safe policies independently: meanwhile, every new policy will be guaranteed to result in performance improvement. is worth mentioning that these two properties hold only under the condition that the only policy update restriction, i.e., क IT, is satisfied; this is due the KL-penalty in every agent's objective, i.e., v RL (TT #t). well the constraints on cost surrogates.
3.3 Algorithm
In this section, focus on how to practically implement policy updates in Theorem 3.7 for each agent. Specifically, we parameterize each local policy Toz by a neural network with parameter 0% At each policy update, every agent i maximizes its surrogate return subject to surrogate cost constraints and form of expected KL-divergence constraint DKL (T) #*) I 8% which avoids computing KL-divergence every state. Then, we introduce a scalar variable X for any agent e N and convert the constrained optimization problem from (16) into a min-max optimization problem with Lagrangian multipliers by subsuming the cost constraints. As such, the new optimization problem for any agent E N is as follows:
Baxs pept atwayy A (sN2,
max min 0% X Time
20
m
+ tdd tci)].
Σ u=1
E
up
s sains
(17)
s.t. S.t.DKL
Tog #02
5x
where Ximm is scalar variable, 0% is parameter of neural network, and d', is the cost-constranning value for agent i.
Further, denoting
m"
A ALAA og
as)
A (SNg a²) Σ Xo
(Auri ('N), + di.) di..
(18)
u=1
then the optimization problem in can be rewritten as
]] s.t. DKL (Tpg #b
max min
E
ys Pap
A
(A) Tog
(SNz,
S 8t.
(19)
1im
To alleviate complications caused by computing the KL-divergence constraint, we simplify by adopting the PPO-clip objective [18] i.e., replacing the KL-divergence constraint with the clip operator and updating the policy parameter with first-order methods. The final optimization problem takes the form
max min 0x X Ai
E N2 patt pine)
min
The (SNg,
A ((A) oo
a²),
A ((())
(SNEs at)
(20)
where the clip operator replaces the policy ratio with + e, or e, depending on whether its value below above the threshold interval. As such, agent i can learn within its trust region by updating

---

Mamyagert
450
IPRO
353
250
300
230
250
1.50
120
140
50
5000
Avenge Edbods Rowend
5000
2000
6920
5020
3000
2000
1000
1770
HAPRO
HAPFOL
Sral:MiPR0 ioun))
0.5
Enssionmmnnt
1.67
Enwironment
EnV rosmart.
Figure 1: Performance comparisons in terms of cost and reward three Safe ManyAgent Ant tasks. Each column subfigure represents a different task, and we plot the cost curves (the lower the better) in the upper row and the reward curves (the higher the better) in the bottom for each task.
8% maximize Equation 20 which only depends on its action and the state of its k--hop neighbors and can be computed analytically.
To summarize, we give procedure for each agent i, name Scalable MAPPO-Lagrangiaa (Scal- MAPPO-L), and provide its pseudocode (A (Algorithm[]) [ in Appendix C.8 The algorithm has simple idea that each agent independently optimizes the surrogate objective 20), which only depends on its action and the state of its k-hop neighbors for each agent. In the actual execution. some approximations of the surrogate objective are employed, the same as the MAPPO-L [TO]. Most of these approximations are traditional practices in RL, yet they may make it impossible for the practical algorithm to rigorously maintain the theoretical guarantees in Theorem 3.7
Experiments
In this section, we evaluate our method via several numerical experiments. Our experiments aim to answer the following questions: First, how does the cost and reward performance of Scal-MAPPO-L compare with existing methods on challenging agent safe tasks? Second, how does the different affect the performance of Scal-MAPPO-L, and could the advantage truncation effectively alleviate computational load?
4.1 Experimental setup
Safe MAMuloCo 10 is an extension of MAMuJoCo 19 which preserves the agents, physics simulator, background environment, and reward function and comes with obstacles, like walls or pitfalls. To answer the first question, we compare our method against the other PPO family algorithms, i... IPPO 20 HAPPO [16], and MAPPO-L [TO] and choose three games from Safe MAMuJoCo: Safe Many Ant task with 2 agents (2 x 3), 3 agents (3 x 2) and 6 agents (6 x 1) to evaluate their performance. Concerning the second question, we choose three games with different tasks and agent numbers from Safe MAMuJoCo: Safe ManyAgent Ant task with 6 agents (6 x 1), Safe Ant task with 8 agents (8 x 1), and Safe Coupled HalfCheetah task with 12 agents (12 1). We train Scal-MAPPO-L with the same network architecture and hyperparameters as the original MAPPO-L implementation. All reported results are averaged over three or more random seeds, and the curves smooth over time.
7

---

And
20
MAPPOL
NAPPOL
84
100
250
MATFOL
NATOLL
300
Figure 2: Performance comparisons in terms of cost and reward on Safe ManyAgent Ant task, Safe Ant task, and Safe Coupled HalfCheetah task. In each task, the performance of Scal-MAPPO-L with different and MAPPO-L demonstrated.
4.2 Results
Comparisons with baselines: Figure[[shows [[sowws the cost and reward performance of Scal-MAPPO-L and other PPO family algorithms on three Safe ManyAgent Ant tasks, where each agent in Scal- MAPPO-L is set to access the state of about half of the agents by adjusting the value of k. Specifically, 1 in Safe ManyAgent Ant (2 x 3), ManyAgent Ant (6 1). From Figure we can see that compared to IPPO and HAPPO, on all three tasks, both Scal-MAPPR MAPPOO and MAPPO-L have fewer constraint violations and good performance (in terms of reward), i.c.. they keep their explorations within the feasible policy space and quickly learn to satisfy safety constraints, which show that the safe learning algorithm is effective. Moreover, should be further pointed out that MAPOOLL only accesses half of the state information on all tasks; it exhibits almost identical performance and constraint violations with MAPPO-L (which accesses the global state). This means that the sensitivity of each agent to the states and actions perturbations of distant agents is minimal, and Scal-MAPPO-L is effective. More experimental results are in Appendix D
2 in Safe ManyAgent Ant (3 2), and
3 in Safe
Performance with different Figure 2 shows the performance of McaP-MA in different environments with varying values of K, where MAPPO-L accesses the global state. We have noticed that the algorithm's 's performance is consistently the lowest, and the cost is nearly the highest when K = 1. However, when the truncation with k >= 3, i.e., each agent has access to the states at least two neighbors, can approach or even outperform MAPPO-L in some environments, such as k = 6 in the Safe Ant task (8 1). This may be due to the fact that the impact of far-away agents' states and actions the agent's decision is almost negligible in many cases. However, for algorithms with global communication, such MAPPO-L, the difficulty of extracting useful information from many messages may lead to lower performance. Overall, these results underscore the efficiency of Scal-MAPPO-L since employs a smaller communication radius that can significantly reduce the computation.
observe that the performance of Scal-MAPPO-L improves considerably and
Related work
5.1
Safe RL
Safety one of the bottlenecks preventing RL use in real-life applications, such as physical roboties 21. medical applications [22) and autonomous driving 23 It has become a research hotspot in
recent years and growing number of safe RL approaches, such as primal-dual methods (24, formal methods (25). Lyapunov methods [26). Gaussian processes methods [27]. and safety-augmeetted
8

---

methods [28], have been developed. However, when it comes to multi-agent systems, a great challenge exacerbated by policy conflicts caused by multiple agents interacting within a shared environment and learning simultaneously. In other words, each agent has to not only satisfy its safety constraints but also consider the conflitss between its safety constraints and maximization reward as well as the safety constraints of others so that their joint behaviors have safety guarantee. In order to address the above issue, CMIX [9] and MAPPO-L [[0] have been proposed with the in-depth study of MARL. These algorithms follow the centralized training and decentralized execution (CTDE) framework [29] 30, 161, which learns the centralized value function by introducing the global state. Unfortunately, the global coupling arising from agents' safety constraints and the exponential growth of the state- state-action space size make the usability in communication or computing resource- resource-constraingg constrained systems and the scalability of these algorithms in larger multi-agent systems become a bottleneck, limiting their applicability. Recent works [T have provided some theoretical results to avoid these shortcomings. However, most of these methods fail ensure both safety guarantee and joint policy improvement under a decentralized learning framework under a decentralized learning framework, which motivates to investigate new scalable and sesoretically-juttffeee safe MARL method.
5.2 Centralized training
In cooperative MARL settings, the training of agents can be broadly divided into two paradigms, namely centralized and decentralized [31]. The centralized training paradigm describes agent policies updated based on mutual information, which can be further differentiated into the centralized and decentralized execution framework. Centralized training and centralized execution (CTCE) utilize the centralized evaluator and executor to learn the joint policy of all agents [32 18). The
obvious flaw is that its upplicability limited because its implementation requires the premise that instantancous and unconstrained information exchange between agents. Recently, centralized training
and decentralized execution (CTDE) has become the most popular framework (30) 20, 16 [0] since
the fact that it addresses the non-stationarity issue with the centralized value function, and removes the dependency on global state and actions during execution. Many experiment results demonstrate state-of-the-- performance on challenging tasks, such as unit micromanagement in StarCraft II
333. However, although this framework does not require agents to access the global state during execution, the reliance on the global state only during training still poses significant barrier to real-world applications, especially in scenarios where communication and computational resources are constrained [34 35).
5.3
Decentralized training
In decentralized learning paradigm, each agent learns independently and accessses local observations rather than the global state; the idea direct, comprehensible, and easy to realize practice There are two mainline research approaches concerning decentralized learning in the existing literature. One line of research pursues fully decentralized learning, such as independent Q-learning (IQL) (37 38 and independent actor-critic (IAC) [39 20), which make agents directly execute the single-agent Q-learning or actor-critic algorithm individually. Another line of research allows agents establish rational local communication networks, such as setting certain distance or neighbor graphs 40 [1]. which is also known as networked MARL. Communication networks expand agents' perceptual capabilities and mitigate, to some extent, the decision conflicts errors caused by partial observability. However, it is worth noting that each agent's 's decision violates the stationary condition of the Markov Decision Process (MDP) in both lines of research, even though they achieve good experimental results on a collection of benchmark tasks. It poses a significant challenge to the convergence analysis of algorithms in the short term. Recently, motivated by good experiment performance, some studies have tried to provide theoretical support for these phenomena. To mention a few, Qu et al. 42 introduced the spatial correlation decay property into the field of MARL and carried out a series of fundamental results [5] 43 12). which broadened the research avenues of scalable MARL. However, all of these studies mainly focus on (natural) policy gradient methods with average rewards or general utilities and have not yet been combined with trust region methods, which rigorously enable RL agents to learn monotonically improving policies. Furthermore, only recent research [12 considers both safety and scalability for MARL. Our results build upon the scalable MARI. family of works
36 34.
12 and PPO-based (TRPO-based) MARI, family of
works [6 10).

---

Conclusion
Safety is tremendous challenge for MARL when applied to real-world scenarios. In this paper, quantize the approximation errors arising from policy implementation and advantage truncation and then derive novel lower bound for joint policy improvement and an upper bound for the safety constraints for every agent. Furthermore, we propose novel scalable and theoretically justified multi-agent constrained policy optimization method that follows a sequential update scheme to optimize к-hop policies. Finally, we introduce practical constrained policy optimization algorithm called Scal-MAPPO-L and experimentally validate the effectiveness of the proposed algorithm on a collection of benchmark tasks.
Acknowledgements
This work is supported by the National Key Research and Development Program of China No.20200AA01061000) the National Natural Science Project of China and the Basic Research Program of Shanxi Province (No.202203022211294,
62376013),
References
[1] Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning in robotics: From learning- based control to safe reinforcement learning. Annual Review of Control, Robotics, & Autonomous Systems, 5:41 1444, 2022.
[2] Shangding Gu, Long Yang, Yali Du, Guang Chen, Florian Walter, Jun Wang, Yaodong Yang, and Alois Knoll. review of safe reinforcement learning: Methods, theory and applications. arXiv preprini arXiv: 10330, 2022.
[3] Wei Zhou, Dong Chen, Jun Yan, Zhaojian Li, Huilin Yin, and Wanchen Ge. Multi Agett reinforcement learning for cooperative lane changing of connected and autonomous vehicles in mixed traffic. Autonomous Intelligent Systems, 2(1):5, 2022.
[4] Wenqi Cui, Jiayi Li, and Baosen Zhang. Decentralized safe reinforcement learning for inverter- based voltage control. Electric Power Systems Research, 211: 100609,,,, 2022.
[5] Yu-Jia Chen, Deng-Ka Kai Chang, and Cheng Zhang. Autonomous tracking using swarm of uavs: constrained multi-agent reinforcement learning approach. IEEE Transactions on Vehicular Technology, 69(1 1: 13702-133777 2020.
[6] Kai-Chieh Hsu, Allen Ren, Duy P Nguyen, Anirudha Majumdar, and Jaime F Fisac. Sim-to- lab-to-real: Safe reinforcement learning with shielding and generalization guarantees. Artificial Intelligence, 31 10::1: 2023.
[7] Wenbo Zhang, Osbert Bastani, and Vijay Kumar. Mamps: Safe multi-agent reinforcement learning via model predictive shielding. arXiv preprint arXiv: /2639, 2019.
[8] Daniel Melcer, Christopher Amato, and Stavros Tripakis. Shield decentralization for safe multi-agent reinforcement learning. In NewrIPS, 2022.
[9] Chenyi Liu, Nan Geng, Vaneet Aggarwal, Tian Lan, Yuan Yang, and Mingwei Xu. Cmix: Deep multi-agent reinforcement learning with peak and average constraints. In ECMLL-PKDD, 2021.
[10] Shangding Gu, Jakub Grudzien Kuba, Yuanpei Chen, Yali Du, Long Yang, Alois Knoll, and Yaodong Yang. Safe multi-agent reinforcement learning for multi-robot control. Artificial Intelligence, 3 319:103905, 2023.
[11] Songtao Lu, Kaiqing Zhang, Tianyi Chen, Tamer Başar, and Lior Horesh. Decentralized policy gradient descent ascent for safe multi-agent reinforeement learning. In AAAI, 2021.
[12] Donghao Ying, Yunkai Zhang, Yuhao Ding, Alec Koppel, and Javad Lavaei. Scalable primal- dual actor-critic method for safe multi-agent rl with general utilities. In NuerIPS, 2023.
10

---

[13] Amir Dembo and Andrea Montanari. Gibbs measures and phase transitions on sparse random graphs. arXiv preprint arXiv:0910.5460, 2009.
[14] David Gamarnik. Correlation decay method for decision, optimization, and inference in large- scale networks. In Theory Driven by Influential Applications, pages 108-121. 2013.
[15] Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable multi-agent reinforcement learning for networked systems with average reward. In NeurIPS, 2020.
[16] Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang. and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. In ICLR, 2022.
[17] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In ICML,, 2015.
[18] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
[19] Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Plexre-Alexandr Kamienny, Philip Torr, Wendelin Boehmer, and Shimon Whiteson. Facmac: Factored multi-agent centralised policy gradients. In NeurIPS, 2021.
[20] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo cooperative multi-agent games. In NeurIPS, 2022.
[21] Javier Garefa and Diogo Shafie. Teaching humanoid robot to walk faster through safe reinforcement learning. Engineering Applications of Artificial Intelligence, 88: 88:103360, 2020.
[22] Shounak Datta, Yanjun Li, Matthew M Ruppert, Yuanfang Ren, Benjamin Shickel, Tezean Ozrazgat-Baslan Baslanti, Parisa Rashidi, and Azra Bihorac. Reinforcement learning in surgery. Surgery, (((1)))29-333))) 2021.
[23] Shangding Gu, Guang Chen, Lijun Zhang, Jing Hou, Yingbai Hu, and Alois Knoll. Constrained reinforcement learning for vehicle motion planning with topological reachability analysis. Robotics, 11)))81, 2022.
[24] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo R Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. In NeurIPS, 2020.
[25] Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In NeurIPS, 2018
[26] Yinlam Chow, Ofir Nachum, Edgar lyapunov-based approach to safe reinforcement learning. In NeurlPS, 2018.
and Mohammad Ghavamzadeh. A
[27] Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. Safe exploration for optimization with gaussian processes. In /CML, 2015.
[28] Aivar Sootla, Alexander Nooen-Rivvers Taher Jafferjee, Ziyan Wang, David H Mguni, Jun Wang, and Haitham Ammar. Sauté rl: Almost surely safe reinforcement learning using state augmentation. In ICML, 2022.
[29] Peter Sunchag, Guy Lever, Audrunas Gruslys. Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning. arXiv preprint (eXXxv1706.05255 2017.
[30] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder. Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In JCML, 2018.
[31] Sven Gronauer and Klaus Diepold. Multi-agent deep reinforcement learning: a survey. Artificial Intelligence Review, pages 1-49, 2022.

---

[32] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukeuoglu. Asynchronous methods for deep reinforcement learning. In ICMI,, 2016.
[33] S Whiteson, M Samvelyan, T Rashid, CS De Witt, G Farquhar, N Nardelli, TGJ Rudner, CM Hung, PHS Torr, and Foerster. The starcraft multi-agent challenge. In AAMAS, 2019.
[34] Wei Du and Shifei Ding. A survey on multi-agent deep reinforcement learning: from the perspective of challenges and applications. Artificial Intelligence Review, 54:3215-3238, 2021.
[35] Afshin Oroojlooy and Davood Hajinezhad. A review of cooperative multi-agent deep reinforce- ment learning. Applied Intelligence, (3(1)):3677-13722 2023.
[36] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Studies in Systems, Decision and Control, pages 321-384, 2021.
[37] Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In ICML, 1993.
[38] Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent cooperation and competition with deep reinforcement learning, arXiv preprint arXiv:1511.08777 2015.
[39] Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint wwxxv:2011.09533 2020.
[40] Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement learning. In ICLR, 2019.
[41] Tianshu Chu, Sandeep Chinchali, and Sachin Katti. Multi-agent reinforcement learning for networked system control. In ICLR, 2019.
[42] Guannan Qu, Adam Wierman, and Na Li. Scalable reinforcement learning for multi-agent 2019.
networked systems. arXiv preprint
[43] Yiheng Lin, Guannan Qu, Longbo Huang, and Adam Wierman. Multi-agent reinforcement learning in stochastic networked systems. In NeurIPS, 2021.
[44] Hans-Otto Georgii. Gibbs measures and phase transitions. Walter de Gruyter GmbH & Co. KG, Berlin, 2011.
[45] Alison L Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review, 70(3):419 435, 2002.
[46] Wenjun Mei, Shadi Mohagheghi, Sandro Zampieri, and Francesco Bullo. On the dynamics of deterministic epidemic propagation over networks. Annual Reviews in Control, 44:116-128, 2017.
[47] Alessandro Zocca. Temporal starvation in multi-channel esma networks: an analytical frame- work. ACM SIGMETRICS Performance Evaluation Review, 46(3):52-53, 2019.
[48] Guannan Qu and Na Li. Exploiting fast decaying and locality in multi multi-agent mdp with tree dependence structure. In CDC, 2019.
[49] Haotian Gu, Xin Guo, Xiaoli Wei, and Renyuan Xu. Mean-field controls with q-learning for cooperative marl: convergence and complexity analysis. SIAM Journal on Mathematics of Data Science, 3(4): 1618168-111 1196, 2021.
[50] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In NewrIPS, 2018.
[51] Changxi Zhu, Mehdi Dastani, and Shihan Wang. A survey multi-agent reinforcement learning with communication. arXiv preprint
2022.
12

---

[52] Junjie Sheng. Xiangfeng Wang, Bo Jin, Junchi Yan, Wenhao Li, Tsung- Tsung-Hui Chang, Jun Wang. and Hongyuan Zha. Learning structured communication for multi ageet reinforcement learning. Autonomous Agents and Mulli-Agent Systems, 36(2):50, 2022.
13

---

A Preliminary lemmas
Before proving propositions, corollaries, and theorems, need series of intermediate results foundation. Results similar to Lemmas and A.2 can be found in Chapter of [44], Lemma A..mmaA.3)mm is
extension of results from [15], Lemma is extension of Lemma A.2 found in [2] We state these lemmas and provide the corresponding proofs for completeness as follows.
Lemma A.I. Let S - {m, M) where S = XieNS' and m, M R. For every i E N, let u' and v² be two distributions on S¹. Let a and v be the respective product distributions. Let 8' (f(s)) s If (s's - fs" ).) Then, one have
[ss))(s) Ex [s)] S Drr Drv 61). o
(21)
IEN
Proof. We prove Lemma A.1 by induction. Note that 1 max E (h) - E. (1))
(rv(
2
M
an equivalent formulation of the total variation distance 45 [ 1. one have
For
E2 (f) (f)
E
+ m
- Eyy {
M + m
2
2
m
2f
M + m
2
M + m
Ey
E,,,
2
M
M m
M
M
M
max [M
Ex (h)
E,, (h)
2
Drv (n 1²) (t)
As induction assumption, assume that Lemma A.I holds for [ 1. Then, have
Eg - f())
BBt E Egzm f(s) - Eg wut E wmn f(s)
Bglnng Eg Eg f(s) Eg Epl Eg 2in (s)
Bet Eggm ((8) Egtay Eg 2m ((s)
Bgt mep Ext f (() Egtnyt Eg win f {s)
Reginnl Bg an ((s Rg Egg [s)
S Eg Bgam fs) Egan u f(s) + Exina (st) Ex F(st) E
where f(s!) Eganapan (s).
By induction assumption, one have
Ex Ea:map2in f(s) - Egam f(s)
Σ Drv (N (f (st..))
iTEN
<
Σ ieNN
Div (n² (1) (f).
Since
8'(J) sup Egannean / (s', 82 Egainayinn (5"), 2
x 21
sup Egen If (s 2
(s" (2n))
< sup
If (s), (2,,) (2m)
st,6" 22m
8 (f),
14

---

one have
[g) - Esnuf(s)
S Bat
E
DTv (0) + DTv DTV ()())))
SIEN
< DTv (u', of),
VEA
which concludes the induction.
Lemma A.2. Consider a Markov Chain with state s E S, where S = XIENS', and N (l,.....) is the set of agents. Suppose its transition probability factorizes
P(S
8p) = II P (si+1 1s)).
iEN
Let W& E Raxn be a matrix whose elements respect the condition
w'i 2 sup DTv (P' (-1s),s p (.15",s57)
si 3 3,55
EEjed e W S. NN, then one have
sup
DTV (Pi (. (-1s", ,',, , (- 1/8",5-²) - Σ W
(22)
jEl
and
sup DTv (P' (1s's5 ) p (.1s", 11), Se -ad(J.))
(23)
where d(J,i)) = min d(j i).
Proof. We prove the first claim of Lemma A.2 The first claim clearly holds [ = 1. As induction assumption, assume that the first claim holds for a set J. Then, it holds for J = J + (1}
pd (1s"",s")
(.1s/*
sup s) x 2,
DTv
pi (A| "41s"""-"") pi (A sii"" , ))
sup ACS' '3
pc (AIs" "
(A1s""s-")), pr (A
s-),))))
< sup
ACS' 2
Pd (A (AA1s",s~1)) ,8-,), pi (A sid (--)
+ sup ACS' 2 5
W Wik
NET
Σ
W
JEJ
The second claim follows immediately, since
3d(
Σ
Wi <
e BdGi <
Σ
edGiowis SC
JEJ
JET
JEN
and
Σ
W - Çe (d((J.).
JEJ
15

---

Lemma A.3. Consider the setting of Lemma A.2 For generic value of K. denote by Pt and Pt the distribution of with starting state, respectively, s = (N and š (NN,,NEE)) Then, if Ejer e S Ç. we have that Drv (p (p):P:)= S S
Mh ViEN.
Proof. We prove Lemma A.3 by induction. The case where t = 1 follows from Lemma A.2 As induction assumption, assume that Lemma Lemma holds for t. Then, one have
Egr 1a(s) P.- Ia(s)
Egup, Ear Pink) LA()) Bunp, (1s
Σ DTv (pi. 8 (F AA()))
JEN
Σ DTv (pi,D) wis
JEN
= =C'e- 8K
wii
JEN
S S e
where we used Lemma A.l in the first inequality.
Lemma A.4. Consider the setling of Lemma A.2 Let P (s'' = Ps: =s
So = s) and
8 pit = sup DTV (pit (188,8 pit (1855887)
si 2,55
If EjENN Wiis e
S G, we have
Σ JEN
3dlt.) &it ViEN.
(24)
Proof. We prove Lemma A.4
by induction. The claim holds for / 1= 1,
Σ
(d(t.)) 85 phi Σ
ad <
jEN
JEN
As induction assumption, we assume that the claim holds for Then, using Lemma A.I
83 pi,t11
sup
Ego 1615i, ()) Em s)1n(s)
ASSi
sup
( Eaw pi (.1x) La())
AC8
DTV (phil (ptit. (.108,5-)) phit (.15",,-')) 8 (Eon LA()))
sup
3 1,55 REN
8 ph.'
KEN
and using the inverse triangle inequality,
Σ
edlts) & pit++1
Od(id))
8 phit
JEN
jEN
KEN
Bd(i,H)
-(d((-)) g phot
NEN
JEN
Wikk
Bd(k.)) 8 pba
REN
JEN
$ c++1
which concludes the induction.
16

---

B Supplementary materials for Section 2
B.1 Spatial correlation decay
Exponential decay property 13 14), also known as spatial correlation decay, is a powerful property associated with local interactions, which says that the impact of agents each other decays exponen- tially in their graph distance. Over the past decades, many researchers have utilized spatial correlation property design scalable, distributed algorithms for optimization and control problems scenar- ios such as epidemics [46] and wireless communication 477. Inspired by the studies mentioned above, recent line of work [88 has formally considered spatial decay of correlation assumptions and proposes method that finds nearly optimal local policies. An application 49 with the same principles adopts the setting of mean-field MARL [50), which proposes an actor-critic algorithm with global convergence. However, unlike the mean-field setting, which requires an agent's 's transition scheme to be only affected by the mean effect from its neighbors and effective only when agents are homogeneous, we allow each agent to have different transition probabilities and local policies.
B.2 Regarding Assumptions 2.1
2.2
Assumption 2.1 portrays a common phenomenon: the transition dynamic of each agent is expo- nentially less sensitive to perturbations of the states and actions of more distant agents. This is commonly seen in scenarios involving wireless communication, epidemies, traffic, and so on 46 47
Assumptioo22.22mpppss imposess a design constraint for the policy class that encodes weaker correlation decay property than the assumptions on the nature of Assumption 2.1 Moreover, Assumption 2.2 reveals how much information is lost compared with access to the global state and allows us to consider a policy class with the necessary properties for the optimal policy under Assumption 2.1 Below, we use mathematical example to illustrate the relationship between the two assumptions.
Mathematical example: Firstly, we start from Assumption 2.1 letting ï max,,eN d (i, be the maximum distance between agent i and agent j. Define a set of differentiable functions [Jx SNz: , x A + K. 0 S.S. k), where K. C [-K, KK K]. K O, and set of parameters {ax, 2 0 0 < S R... Then, for each agent i, one have
8 (s, = Σ Canft (e)),
K==
exp (f' (s)
#' (a 8) ENEA exp (J (s, a'))
By tuning the parameters a,, we can make any policy belonging to this policy class respect Assump- tions 2.2 as we show the following. Let i E (O..... one have
. R), S, E S be such that SN² -SNj, then
||T((11) - (-15))
= Σ
(' 8) - a'
SEA
exp (f' (s, a)
exp (f (5,
Σ aEAA
EVEN exp (f (s, a()) EvEd exp (f a/))
EnEA: ENEE exp (f+ as) exp (l' (3, Enee exp (f (5, a)) exp (5 (s.a')
EvEr exp ( (s, a/)) E'ee exp (ʃ (5,
< EnEA ENEE lexp ( (s, a)) exp (/' (5, a²)) - exp ( (5, a)) exp ((((ss))))
Evee exp (s, a²)) Ever exp (fi(s,)) (s,
EnEAr lexp (5) a)) exp (s)
ExcArex exp ((((5
EnEAi (}, (s, a) exp (SuPre(Ga3) f' (s',a)
EnEA exp ())
17

---

E 2k(R-n) R) EREA - exp ())
f
EnEA exp a))
2k (k(k-n) Egg
Σ Ox ( (Bx2, Sw (s)2
M==++1
(k()m))
au ( (BN2) - fr (SNc,
n'=x+1
< 2KE 2k(n-n)
Ow'
1e x²=x+1
Denote that (5, = 2 Ex _x'=Nt1 Ow', 2K) and setting the parameters {ase (e((
small enough ensures that the policy respects Assumption 2.2
Remark B.1. The mathematical example illustrates the relationship between the Assumptions 2. and 2.2 It is evident from this mathematical example that Assumption 2.2 necessarily holds when Assumption 2. holds and the parameters & and / satisfy certain conditions. However, for the sake of more concise presentation, we treat it as separate assumption.
Remark B.2. When Assumption 2. holds, the numerical example can provide a reference basis for selecting the values of the parameters in Assumption 2.2 However, accurately determining the spatial decay of correlation for the dynamics remains a challenging engincering task. In this paper, empirically adopt conservative values.
Remark B.3. Assumption 2.2 implies that multi multi-agent environments must satisfy the requirement that the impact from far-away agents' states and actions is almost negligible for the agent's 's decision; in other words, an action of an agent has an instantaneous effect on the system only locally. We believe that this formulation realistically describes most multi-agent interactions in the real-world. Take multi-vehicle transportation as an example. For a vehicle traveling on the road, a far-away vehicle taking different actions or being in a different state will affect itself shortly thereafter, but the impact on the current policy is minimal. More examples are seen in wireless communication, epidemics, traffic, and other scenarios [46 47
Remark B.4. It is worth noting that the assumption of spatial correlation decay is not in direct conflict with well-known phenomena, e.g., Butterfly Effect, since two seemingly unrelated things can also have a significant impact on each other, generally occurring in different time domains.
C Supplementary materials for Section 3
C.1 Basic definitions
Regarding the state value function and the sttteacctoon value function, we give the following defini- tions.
Definition C.I. We define the state value function and the state-action value function in terms of reward
V* & Ea-T (s,
(25)
x
Q* a) A Ex p.
Σ
ot (R)s,, = =s a
(26)
Based on C.I one can expand to derive
(i(() = E, Ba-ine
[Q (s,
(27)
8
(s, = Eg IN ( 21000 xpaa
r' R(si, at) s, ag = a
(28)
18

---

Definition C.2. We define the jih state cost value function and state-action cost value function for agent follows
ViJ (s) f Eg p.a
(s a/)ss =
(29)
(s, a Ea--wa-- ss a
(s) a/)s0 = = a
(30)
C.2 The proof of Lamma 3.1
Proof. We write the multi-agent advantage function as in its definition, and then expand it in telescoping sum.
Ax (s, a) Qx (s.a) a) - (s)
n
1 la (s, a 1:) - 1:5 (s, (s,a" 1)]
Σ A (s, 1:11 ,a))
C.3 The proof of Proposition 3.3
Proof. Let s, E S, a. a A. such that for any agent E M, Sxg 3u2 and aw; ävg- According to Equation when only the state and action of the far-away agent are different, one have
(s, (5,
(Q' a) V=(s)) (Q, v (5)
(31)
= (s, a) (5, + (Vi(s) - v=
< (s, a) (5. a) V2(ss (z)
Next, we analyze Q (s, a) Q (s, a) and V*()) [=() separately.
Firstly, for (s, Q' (5, a) we have
Q (s, a) Q (5, a)
2
0 50 = 5,a. a) Σ
r R (St ar)
(s;, ar) TT = 5, 5,ag = a]
t=0
7' IE (sr, at)
T. 8,a
=a E R (Sc, ax) TT 5,80
7¹ Drv (p..P.)
where of and p are the distributions at time with starting point (s, a) and (5, ä), respectively. We use the result Lemma A.3 to bound Drv (pis Pt). The structure of our MDP implies that:
P(s St, ax) = II n' (a/41 (sgget) P (s s.).),))
iEN
Then, if Assumption 2.1 holds, the requirements Lemma A.3 are satisfied, one have DTV (pl. s
Sle -Be 8n and
- -
S
Σ
20
n' DTV (p
-e-9x
9x Σ x
75 e Br
(32)
- 7
19

---

where Ç is defined in Assumption 2.1
Let
8 O² as)
sup 222
Q (z),
Q (z,,2 2 2
and the MDP satisfies the condition of Lemma
A.4 one can obtain
Σ ( (Qt $
e S S x' 75
1-76 75
JEN
JEN
Secondly, building on Assumption 2.2 and Lemma obtain
A.4
we analyze
VV((s) - (i) can further
(8) (2(
(1a) Q (s. a) E (.B) (
(1s) 2% (s.a) a) Fawm( (5) (s. + E aa (5) (5, Ea (5,
S (1 Oz a) - (. a) + Bann( (5) (s, a) - Ba (5,
Σ Drv (T' (. (), T. ()) Q (s, a) + 1-76
75 Bx
JEN
(33)
75 e 8x
< Ee &e-Ae
BR
Pdl 8 (s) 1 75
JEN
75 Ee -Bx
76 -An
1 76
1 76
(1 + E)
e. -pe
1 7c
Then, bringing 32 and (33 into 31 we have
A4 a) A (5. a)
(s, Q', a)
(+()s (5)
E. 1a 2t (s.
E. as) + 2 2 a 1 (s, a) E E Q a)
E.
75 Ee
24c -x
(34)
$ 1 75
9x
1- 76
(2 + E)YS Ax
1 1-75
Finally, denoting (n, x)
12+5)75
1-yc e e-0). we can obtain the Proposition 3.3
C.4 The proof of Corollary
3.4
Proof. Firstly, according to Lamma and Definition 3.2 the following result holds when each agent adopts a sequential update scheme to optimize policy, i.e., we have
1 (7
I (#*)
1E 11 1:
A (s, a 1:i-1 a Bewy upot a
Are (SNY, a']
Eerpp al
114
A (s, a 2::111,a1)
Hawpy a' [1 (s,
(35)
+ +E Par aa
[A (s, a²) a²)] BznØaa'ns [A (5, a']]
E Egg ali
[A (s, a 1: at)] Exnp winzi [A (s,
1
+ Eg-Pp am
[1 (s, a')] Eg-pa [A (5, a²]l.
20

---

Then, based on Assumptions 2.2 we have
Es-p,. alliinn Li [A (s, a 1::-1 ,a9] - Egn ainas [A ||
E pai
( )²) A (s. a²)
Σ m  || (s. a')l
(36)
I E s
M
Σ
-
|
M = x
max | as)
< M
max DIv(F",
7 h=1
M
-9x
According to (34). we have
E St wet
[Ai (s. [s,] - B ~ [Ax (5, [5,a")]
E A (s, a)
A (5. a)
(37)
(2 + E)>S BBK
1 75
Then, bringing (36)
and 37
into (35
we have
1:4
π
T²')
I (#x)
Bapp,, 1il ril ti
E
[A (s, a 1i1-1 a²)] Ea-p, [A as))
Eamp a'nn'
[A (s. a²) a²)] -Ea- [A a5.
M'E e 9xx
(2 + E)>s e- -Bx
1 75
E
(2+ E)>s
1-7 +
e gm.
1-75
Finally, denoting (r/, ()
(2+5m5s (M'' + T-76
.0-)). we can obtain the Corollary 3.4
1--
C.5 The proof of Proposition 3.5
Proof. From 12 we can obtain -ry < L 1- (#1:-1,
x²) - Lig (T%) S n By the trust region
theorem in Theorem from 17 we have
J [ J (T))
2 E a
#t (x, a)] - DDDmaax
KI. (TT, 7)
Eg (x, a)] - Σ
Dimax (M'
1=1
a
n
E pm allin mldd AA (s, 1ii-1 a Σ
DDRL (T'
(L 1:1 c l::-1 .²) v DRRx (Λ² (²))
Lij (#*) - n - v D ( (+))))
i mi
(#*) - n/ 0²x - / DEL (F/))1t)
21

---

Then, when each agent sequentially solves the following optimization problem:
['4: (#x) - -165 Uz DKL (+))#t)
オ = arg max
#2
2y max
N1 Ar (SNx aa)
where
(1)
1-
M'E
+ (2+5)2
I-76 e
1/2
(1-7)²
and
DKL (T4] max No DEL (z'( 18N2): 4- (82))) we have J (
E==1 L (#%) nn'd" v DiL (m/1
C.6 The proof of Corollary 3.6
Proof. Firstly, by generalizing the result about the return in (14). one can derive how the expected costs change when the agents update their policies. Inspired by [IO], we provide the following lemma.
Lemma C.3. Let π and ß be joint policies. Let E N be an agent, and j E .l....mm) be an index of one of its costs. The following inequality holds
JJ(+) S JJ(TT) + T.j.r (57)
KL (T²
h=1
where L (5)) = Eg-p, a' wo [4i. (s. vz 24 max, at |A (s.aa)) (1-7)²
Proof. From the upper bound version of Theorem 1 of [17 applied to joint policies ा and æ, conclude that
JJ(+) S (T( + Ex mii [4), (s, a"]] + 4a²n max,,ax |A as,
(1 - 7)²
where a DTV (I 1:3 ( = max, DTV(T s); #l:(( s)).
Then, using Pinsker's inequality (p, < DKL 1), we obtain
27 max
|4j,r a²)
(j(T) S (i( + Egp giu m as) +
Dmne (n 1:1 x !
(1 7)²
where Dmax 1: π 1:;) max, (KL (. 1), i 1.
Notice that we have Eapp,,, wii [Aj. (s. a')l Ba-p ai [A). as) as the action of agents other that i do not change the value of the variable inside of the expectation. Furthermore,
Duax (π l: # 1l1 = max (KL( (: |ss, म (+,+
< max Σ
DKL. (x" (1)1))) 7" s))
A==
max (DRL (T |s) s)))
Dmax (Th, x²)
h=1
Setting v/ 27 max, a: /4 (s.a²)
finally obtain
(1-7)" 7)²
()+) < (J(
1/ (7') 5
D KL (T at)
22

---

Secondly, from 12 we can obtain -r/0" S ạ
( 1: _5)
- L' (Tt) S 1 n' By generalizing
the result, we can obtain -n" < 1 ( 1:i-1
.5)) -
L 1.o (T)) I r 8² Further, we can derive
the upper bounds about surrogate cost
(J(T) S ( + Li
D KL (x" 2²t)
h=1
S (TT + Lin. (+x) + 05 + V2.n Σ Dmax (
where L (5/) Egg uP almnt A4 a")) ()) = -M, 2.02
I-y + (2+5)5
M2
1-75 e .
27 max, a² Aj. (#yg Ny (1-7)²
and My is constant.
C.7
The proof of Theorem 3.7
Proof. Based on the conclusions in Proposition 3.5 and Corollary 3.6 we can derive that in order to realize reward performance improvement and satisfy safety constraints, agents have to sequentially maximize their surrogate returns and ensure that their surrogate costs stay below the corresponding safety thresholds. Meanwhile, they have to constrain the policy search small local neighborhoods (w.rt, mL distance). Therefore, the size of KI constraint in Equation (16 should be set as
( 1) (T))
n" V Σ
(Th. #x
KL
6 = min
min min hgt
15/5m²
Un
(TT) 1/ 21=1
Diax
(I #1
min min 15/5m"
(38)
where & E Na is the k-hop neighbors of agent i, and j E {l,..., m² } is its cost index.
Note that 5% is guaranteed to be non-negative if satisfies safety constraints; that is because then c) 2 Jh (Tr) for all h E N, and j E {1,.... m²) and the set (h h < i) is empty.
This formula for 6t., combined with Lemma 3.1 assures that the policies ग within 5% max-KL distance from गं. will not violate other agents' safety constraints, as long as the base joint policy æ did not violate them (which assures 8% 2 0). To see this, for every h 1.....i 1, and j 1...., m we have
Dmax (T S 5% 5 - (T) 1/2,0 (# 1000"
3n Ei Dmax (Th =x))
jix
which implies
(T) + 1. (#x) + 1" 6r + b
(The xt) + 2/ DiLa
(F #t) S ej.
(39)
KL.
By Corollary 3.6 the left-hand side of the inequality (39 is an upper bound of Jh ( , which implies that the update of agent does not violate the constraint of JJ. The fact that the constraints of J/. for h 2 i + are not violated, i.e..
(T) + UN
maxx (Ith, ah) + -U DRL (T #1) S scJ..
1=1
Therefore,
let (7/ =
M'g 1-7
+ 1-76 e
12-E)25
_-0) 3) (n" .))
=
MrS +
I-
(2+EM<
1-75
,e-))
ef 2-y max
.² A lays aaa
27 max,
N2 .nt [4) (#Nz aa)
N2
85.
[1-
23

---

Lb (#))
E
min minngi-1 minssism"
2 2:41 minl
of Ei= D (eg when the policy is updated by following se- quential update scheme, that is, each agent sequentially solves the following optimization problem:
(T
T. = arg max #
[1=g (#1) - 11000 DKL (T (m]l#t))
s.t.
( E 11x
DKL (Tis (xx) S 8% and
J3 (Txx + Liitt (ft) + ny" 2 + v DKL (I #/)) S Sc v
(5 T15)
KL
the joint policy has the monotonic improvement property, J ( 2 J (T), as well as it satisfies the safety constraints, Jj (#) S ejj, for any agent i N and its cost index j E .I....,,00
C.8 Algorithm
In this subsection, we provide the main pseudocode for Scalable MAPPO-Lagrangian (Scal-MAPPO- L), outlined in Algorithm
Algorithm Scalable MAPPO-Lagrangian
Stepsizes agg ax batch size B, number of agents n, episodes Z, steps per episode T, discount factor y, parameter K. Initialize: Actor networks ii......, 0 K.0 V-value network Xic.o.... Xx,0- V-cost networks NEW
Input:
(0,0)) EiEN,jEE,..... m,, Replay buffer B. 1: for 0, 1 do
2: Collect a set of trajectories by running the policies To..
3: Push transitions { {o}, ai, of rt) N, t E 7 into B.
4: Sample random minibatch of B transitions from B.
5: for = 1 do
6:
Initialize policy parameter % and Lagrangian multipliers X1. Vi W...e........
7:
Compute advantage function Á'(s, a²) and cost advantage functions Ai (s,
8:
Compute the parameters 17", 6, vi and v) V j E ( {1...., m').
9:
Compute the radius of the KL--onstraint 5x Compute the advantage function in (18).
10:
11:
Update policy according to (20).
Update V-value network and V-cost networks.
13:
end for
14:
end for
The algorithm has a simple idea that each agent independently optimizes the surrogate objective, which only depends its action and the state of its x-hop neighbors for each agent. In the actual exccution. we adopt the surrogate objective (20) instead of (16). It actually uses some approximations for the decentralized surrogate objective, the same as the MAPPO-L [IO]. Most of these approximations are traditional practices in RL, yet they may make it impossible for the practical algorithm to rigorously maintain the theoretical guarantees in Theorem 3.7 However, we need to argue that we should go one step further and provide a decentralized surrogate for decentralized learning with a convergence guarantee. We believe and expect that better practical method can be found based on this objective in future work.
24

---

D Supplementary materials for Section
D.1 Additional experimental results
In this paper, we compare the algorithm of our proposed (i.e., Scal-MAPPO-L. in Algorithm against other PPO family algorithms on several safe MARL tasks to evaluate their performance. Here, we provide some additional experimental results, which are illustrated in Figures 3
Ast 2
4
And D x
320
355
252
220
200
1.50
150
150
3.3
30
53
127
167
307
1650
IAPPO
Aworage Ea300d Rowwo
2750
ScaP L (ours)
MA-PO
020
1020
2350
830
800
2000
620
750
230
0.0
0.2
0.4
3,6
0.8
1.0
6.5
0.2
3.4
0.6
0.8
3.6
0.0
0.2
0.1
2.6
6.8
1.0
steps
Figure 3: Performance comparisons in terms cost and reward on three Safe Ant-v2 tasks. Each column subfigure represents a different task, and we plot the cost curves (the lower the better) in the upper row and the reward curves (the higher the better) in the bottom row for each task.
Coupled
Cousted
Coupled
400
603
103
IMAPO
M/PP3-4
Arreage Edlande Cod
Sox NAPOC- (ouns)
300
303
200
0.0
0.2
0.4
3.6
3.5
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
3000
3000
HARPO
Aneraqu Sww.dde Haward
2503
MAIIMAP (ous)
1500
1000
1000
500
503
502
0.2
0.4
5.6
0.0
0.6
0.4
0.0
Envirorment stops
1w7
Environment stops
107
Enviroommnn stogs
Figure 4: Performance comparisons in terms of cost and reward on three Safe Coupled HalfCheetah tasks.
Remark D.I. It is worth pointing out that, in our code, unlike the original, the global state consists of a patchwork of each agent's and the k-hopp information rather than a long state vector. This the main reason of the difference in performance from the original paper. As we consider decentralized learning, the agents in the experiments do not use parameter-sharing. In all experiments, the network architectures and common hyperparameters of our algorithm and MAPPO-L are the same for fair
25

---

comparison. All reported results are averaged over three or more random seeds, and the curves are smooth over time.
D.2 The computer resources and computational complexity
Computation resources: We executed our code on a computer with NVIDIA GeForce RTX 4090 (GPU) and Intel Core 19-13900K (CPU).
Computational complexity: The computational complexity of Scal-MAPPO-L (ours) is O(TNMHP), where T denotes the number of steps, N denotes the number of agents, M denotes the number of constraints, H denotes the number PPO-Epoch, and P denotes the number of policy parameters.
Besides, we test the running time of Scal-MAPPO-L. on Safe Manyagent Ant 6 x 1, Safe Ant 8 x 1, and Safe Coupled HalfCheetah 12 1. The running steps are 10 in each environment. When the parameter is maximized, the algorithm's 's average wall-clock times are 8.43h, 9.28h, and 11. 11.55,, respectively. is worth noting that the wall-clock times do not significantly down when K gradually decreases. This may be due to the fact that we have yet to consider the process of sending and receiving information realistically. However, based on the successful research conducted in the field of communication [51] 52), it is evident that algorithms requiring less communication undoubtedly have an advantage in terms reducing communication burden and enhancing applicability.
E
The discussion of limitations and impacts
E.1
Limitations
This paper is centered on theoretical analysis and also contains practical algorithms and simulation verification. The main results in the paper characterize the proposed method's performance in terms of safety constraints and joint policy improvement. Below, we discuss the limitations of the proposed approach for both theory and experiment aspects follows:
1) Our thcoretical results are based on the two assumptions about the spatial decay of correlation for the dynamics and the policies in Assumption 2. 2nd Assumption 2.2 Our conclusions may be useless when such assumptions do not hold, e.g.. the decisions of each agent are non-negligibly related to the decisions of all other agents. However, fortunately, existing works [46 47] have shown that many real-world situations satisfy both assumptions, so our study is still important and meaningful.
2) Our experiments show that Scal-MAPPO-L, with communication between a small number of neighbors, outperforms MAPPO-L in some cases, which we would like to see because it implies fewer communication requirements. However, we have yet to develop an equilibrium relationship between the amount communication and the performance, which we will focus on next.
F.2 Broader impacts
This paper presents work that aims to advance the field of RL, especially safe MARL. Our work has many positive societal impacts, such as providing a theoretical foundation for scalable Safe MARL, none of which we feel must be specifically highlighted. There are no negative societal impacts on our work.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Both the abstract and introduction include the claims made in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of the proposed approach for both theory and experiment aspects, which can be seen in Section E.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model sell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
This paper provide the full set of assumptions and complete (and correct) proof. Specifically, describe the two assumptions about the spatial correlation of the transition dynamics and policies in subsection 2.2 and provide complete proofs of the paper's propositions, corollaries, and theorems in Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide the pseudocode of Algorithm i Appendix C.8 and provide detailed description of the experiments in Section and Appendix D
Guidelines:
The answer means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce
28

---

the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d)
We recognize that reproducibility may be tricky in some cases, in which authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Question:
Answer: [Yes]
Justification:
The paper provide open access to the data and code in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cd cc/ public/guides/ http///oooSuumisseeeee hatps//guiaaass/SdSuuuuaasssaaao
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc//// http:cccpppppgggeeeeeeeeeee hwtlc//guiissseeeee / wtw.eeeeeeeeSSeeeeeeeeeeeee sooooiiiccipoiiciiiiiicooooiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: This paper states the experimental setup in Section more detailed setup can be found in Appendix D.I
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
29

---

Answer: [Yes]
Justification: In this paper, all reported results are averaged over three or more random seeds. The results are presented by error line plots and the curves are smooth over time.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative етror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The paper provide information on the computer resources in Appendix D.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics :tttus://neurppstt http::////rrrrpp..ppppiiiccceeee httpr//sss.cppullecectccccccllla
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
30

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses both potential positive societal impacts and negative societal impacts of the work performed Appendix E.2
Guidelines:
The answer means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
31

---

12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite the original paper that produced the code package.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datastss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide details of new assets in supplemental material..
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
32

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "oVmeItIL5K", "reviewer": "Reviewer_a1c1", "summary": "The paper proposed a scalable multi-agent constrained policy optimization for safe reinforcement learning. It is an extension of two previous work on safe reinforcement learning and scalable multi-agent reinforcement learning. The trust region policy updates and truncated policy/advantage function are combined to give theoritical performance bound. A practical algorithm based on PPO is also shown and the empirical results verifies the claimed performance.", "questions": "The theoritical results look okay to me, although I didn't check all the proofs. for the experimental results,\n1. For figure 1 and 2, what is the constraint on the average episodic cost? It will be more clear to draw a horizontal line showing that.\n2. The performance is still increasing at 1e7 steps, the algorithms might not converge. Can you explain a bit?", "limitations": "The authors addressed the limitation well.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The presentation is clear and easy to understand, the authors presented clearly the relation between this paper and the previous work.\n2. It is a very solid combination of the ideas in previous works, and extends the scalable multi-agent reinforcement learning idea to multi-agent safe reinforcement learning. It will be beneficial to the safe RL community.\n3. The theoretical results look correct to me.", "weaknesses": "There are all minor weaknesses in this paper.\n1. The author should discuss more clearly on how the assumptions are related to previous works, for example, the Dobrushin conditions in (1) and Assumption 2.1. They both appear in the previous scalable multi-agent reinforcement learning paper [1] but in slightly different formulations.\n\n2. The experiments are only on a smaller number of agents (for 12 agents, we don't really need a scalable algorithm to handle it).\n\n[1] Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable multi-agent reinforcement 374 learning for networked systems with average reward. In NeurIPS, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the valuable comments from the reviewer. We hope our responses below provide further clarity.\n\n> W1: The author should …… different formulations.\n\n> W2:The experiments …… algorithm to handle it).\n\n> Q2: The performance …… a bit?\n\nA: We thank the reviewer for appreciating our work and kindly refer the reviewer to our **General Response**, where we provide the discussion for the validity and applicability of the assumptions about spatial correlation decay and add new experimental results with more agents and more training steps.\n\n**Remark:** The safe MARL problem has received much attention from researchers in recent years. Unfortunately, the benchmark environment still needs to be developed. To the best of our knowledge, Safe Multi-Agent MuJoCo [1] is a popular safe MARL benchmarking environment. In addition, literature [2] designs an access control task with safety constraints under wireless communication, which has 25 agents. But they did not provide the experimental code. In the next version, we will strive to reproduce this wireless communication environment and provide the results of our experiments.\n\n> Q1: For figure 1 and 2, …… showing that.\n\nA: **Figure 1 and 2** show the experimental results on several safe tasks in the Safe MAMUJOCO environment, which preserves the agents, physics simulator, background environment, and reward function and comes with obstacles, like walls or pitfalls. Furthermore, the environment emits cost [1] with the increasing risk of an agent stumbling upon an obstacle. \n\nThe “average episode cost” represents the average cost per episode in a batch. We will fix this in the new version.\n\n**References:**\n\n[1]\tShangding Gu, Jakub Grudzien Kuba, Yuanpei Chen, Yali Du, Long Yang, Alois Knoll, and Yaodong Yang. Safe multi-agent reinforcement learning for multi-robot control. Artificial Intelligence, 319:103905, 2023.\n\n[2]\tDonghao Ying, Yunkai Zhang, Yuhao Ding, Alec Koppel, and Javad Lavaei. Scalable primal-dual actor-critic method for safe multi-agent rl with general utilities. In NuerIPS, 2023.", "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": "", "extra_scores": {}}, {"review_id": "fiqyZyAYkA", "reviewer": "Reviewer_UGAx", "summary": "the work proposes a scalable version of MAPPO-L for constrained policy optimization, taking into account that decays in the inter-dependence between agents in a Markov Game projects into bounded errors while limiting the information sharing between agents. The theoretical results transfer nicely from the two starting frameworks, and the authors propose some empirical corroboration.", "questions": "**Major**:\n- Can the authors discuss the validity of the assumptions? When would it be the case that $\\zeta \\in [0, 2/\\gamma]$? How would the condition of the policies be enforced while learning? Does it mean that the policies learned in the experiments are of the form in lines 522 in the Appendix? Are the assumptions valid in the instances of MAMUJOCO taken into account? \n\n- What do lines 259/260 stand for? what information in the environment do the authors refer to?\n\n- Code: would the authors provide a repository for the code? otherwise, the claims about the reproducibility of the work in the checklist are not very satisfied\n\n- Figure 1: with which value of k were the experiments done? Line 248 is not fully clear to me. Would the authors explain further? The performances of MAPPO-L do not match the performances of the original paper, why that?\n\n- Figure 2: Why is there a difference in performances between the two Manyagents 6x1 experiments in Figures 1 and 2?  The performances of MAPPO-L do not match the performances of the original paper, why that?\n\n- What is the meaning of the claims in lines 327, 328 about the differences with [15], [47], [12]?\n\n**Minor**:\n\n- What does $d^i_u$ in equation (17) stand for?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "**originality**:\nThe overall combination of known results from scalable algorithms and MAPPO-L might not be that original. Having said that, it is not trivial as well, so while not surprising, I would say it is not negligible, assuming that the authors fairly address the similarities in the related works (see weaknesses).\n\n**quality**: \nthe work reaches high quality in the analysis and the empirical corroboration is mostly convincing, out of some doubts to be clarified (see Questions)\n\n**clarity**:\nthe work is overall well-written, and the concepts are generally well-described and help to understand the contributions.\n\n**significance**:\nthe work addresses an important problem, that is how to build a more scalable version of algorithms from SOTA MARL algorithms.", "weaknesses": "**Major**:\n\n- In the related works section, I would expect an extensive and fair discussion of the difference between this work and works on scalable MARL and MAPPO-L. The work has value in being a combination of the two, but this needs to be clarified. For example, more comments on the differences/novelties in the proofs and results from works cited as [10], [15], [18], [47].\n\n- The experimental corroboration does not provide any useful info about the difference in computational/communication burden introduced by Scalable-MAPPO-L compared to MAPPO-L. Additionally, from Figure 2, the fact that using k=1 (almost IPPO-L then) is way enough to solve the problem would rather suggest that the tasks themselves are easy. \n\n**Minor**:\n- Section 2.2 : I would strongly suggest introducing the notion of agent graph somewhere, otherwise the $S_{N_i^k}$ and the notion of distance between agents might be hard to digest from scratch.\n\n- Eq 4/5 : I would suggest distinguishing the constants $\\beta_1$ and $\\beta_2$ (in case they are not different).\n\n- Eq. 10: I believe $A^j_\\pi$ should be $A^h_\\pi$.\n\n- Eq. 13: I would specify over which class of policies are arg-maximizing.\n\n- Theorem 3.7: I would suggest refactoring the constants, they are hard to read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the valuable comments from the reviewer. We hope our responses below provide further clarity.\n\n**Remark: Without further specification, we use \"[number]\" to refer to the corresponding reference in our paper.** \n\n> W1(Major): In the related …… cited as …….\n\nA: We re-clarify our technical contributions in the first point of our **General Response** and would like to provide a fair discussion with the existing literature, covering all relevant aspects and nuances, as follows. \n\nQu et al. [1] introduced the spatial correlation decay property into the field of MARL and carried out a series of fundamental results [2-4], which broadened the research avenues of scalable MARL. However, to the best of our knowledge, all of these studies [1-4] mainly focus on (natural) policy gradient methods with average rewards or general utilities and have not yet been combined with trust region methods, which rigorously enable RL agents to learn monotonically improving policies. Furthermore, only recent research [4] considers both safety and scalability for MARL. Our results build upon the scalable MARL family of works [1-4] and PPO-based (TRPO-based) MARL family of works [5-6]. \n\nThe **main differences** between this work and previous works are as follows:\n\n* Compared to the works on scalable MARL family [1-4], we integrate the bounds of the trust region method with the bounds of the advantage truncated and introduce the multi-agent advantage decomposition and the sequential policy update scheme [5-6]. Each agent's policy update only depends on the actions of the previous agent rather than on the actions of all $\\kappa$-hop neighboring agents.\n\n* Compared to TRPO-based MARL family [5-6], we focus on decentralized learning settings and develop a novel scalable and theoretically-justified multi-agent constrained policy optimization method. This method utilizes the rigorous bounds of the trust region method and the bounds of the truncated advantage function to provide a new local policy optimization objective for each agent. \n\n> W2(Major): The experimental …… are easy.  \n\nA: We provide information about the computational complexity in **Appendix D.2** and add new experimental results with more agents and more training steps in the fourth point of our **General Response**.\n\nIt is worth noting that the wall-clock times do not significantly down when $\\kappa$ gradually decreases. This is due to the fact that we have yet to consider the process of sending and receiving information realistically. However, based on the successful research conducted in the field of communication [7-8], it is evident that algorithms requiring less communication undoubtedly have an advantage in terms of reducing communication burden and enhancing applicability.\n\n> Regrading the 1~5 in minor weaknesses. \n\nA: Thank you for the valuable suggestions. In the next version, we will introduce the graph structure as the third point of our **General Response** and reorganize some of the symbols.\n\n> Q1(Major): Can the authors discuss …… taken into account?  \n\nA: We provide further discussion on the assumptions in the second point of our **General Response**.\n\n> Q2(Major): What do lines 259/260 …… refer to?\n\nA: We're really sorry for any confusion caused by not explaining things clearly. We rephrase it as follows: **Figure 2** shows the performance of Scal-MAPPO-L in different environments with varying values of $\\kappa$, where MAPPO-L accesses the global state. We have noticed that the algorithm's performance is consistently the lowest, and the cost is nearly the highest when $\\kappa=1$.\n> Q3(Major): Code: would …… not very satisfied.\n\nA: We have been submitted our code in the supporting material.\n\n> Q4(Major): Figure 1: with which …… why that?\n \nA: In **Figure 1**, we set that each agent in Scal-MAPPO-L can access the state of about half of the agents.  Specifically, $\\kappa = 1$ in Safe ManyAgent Ant ($2 \\times 3$), $\\kappa = 2$ in Safe ManyAgent Ant ($3 \\times 2$), and $\\kappa = 3$ in Safe ManyAgent Ant ($6 \\times 1$).\n\nFurthermore, the reason behind the discrepancy in performances between MAPPO-L and the original paper is attributed to the global state, which is a combination of each agent’s ID and the $\\kappa$-hop information rather than a long state vector in our code. We elaborate on this in **Appendix D**.\n\n> Q5(Major): Figure 2: Why is …… why that? \n\nA: The results in **Figure 1** were obtained from a different server with a single A100 GPU. Unfortunately, we missed the slight difference between them. In the next version, we are committed to presenting the results on the same computer for consistency.\n\nThe performance of MAPPO-L does not match the original paper for the same reason as the answer to Q4(Major).\n\n> Q6(Major): What is the meaning …… differences with ……? \n\nA: An elaboration about the compare with the existing literature [1-3] is re-reported in the answer to W1(Major).\n\n> Q1(Minor): What does $d^i_u$ in equation (17) stand for? \n\nA: $d^i_u$ in equation (17) stand for the cost-constraining value.\n\n**References:**\n\n[1]\tScalable reinforcement learning of localized policies for multi-agent networked systems. arXiv preprint arXiv:1912.02906, 2019.\n\n[2]\tScalable multi-agent reinforcement learning for networked systems with average reward. In NeurIPS, 2020.\n\n[3]\tMulti-agent reinforcement learning in stochastic networked systems. In NeurIPS, 2021.\n\n[4]\tScalable primal-dual actor-critic method for safe multi-agent rl with general utilities. In NuerIPS, 2023.\n\n[5]\tTrust region policy optimization in multi-agent reinforcement learning. In ICLR, 2021.\n\n[6]\tSafe multi-agent reinforcement learning for multi-robot control. Artificial Intelligence, 319:103905, 2023.\n\n[7]\tA survey of multi-agent reinforcement learning with communication. arXiv preprint arXiv:2203.08975, 2022.\n\n[8]\tLearning structured communication for multi-agent reinforcement learning. Autonomous Agents and Multi-Agent Systems, 36(2), p.50, 2022.", "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": "", "extra_scores": {}}, {"review_id": "S0XgoZPLYF", "reviewer": "Reviewer_GtLQ", "summary": "The paper studies the problem of constrained MARL in a cooperative setting and focus on the decentralized learning settings without global observability. The paper proposes a constrained policy optimization method and its practical version, Scal-MAPPO-L. Theoretical results are established for the dynamics/policy truncation and the trust-region subproblems. The effect of the proposed method is validated through numerical experiments.", "questions": "I mainly have the following questions.\n\n* Could the author make further clarifications about the technical contribution of the paper against [10]. What are the main difficulties met when extending the results in [10] to the current setting (after imposing the spatial decay of correlation assumption).\n\n* Could the author provide more justifications about why the methods proposed in the paper is better than the existing literature [11] and [12]. In the paper, the author mentions [11] imposes extra parameter-sharing constraint, which results in suboptimality. This sounds not convincing enough to me, because the method developed in this paper is also \"not optimal\". For the discussion about [12], I failed to understand the idea conveyed by the author, and hope the author could elaborate further.\n\n* The empirical algorithm Scal-MAPPO-L does not have any theoretical guarantee. I wonder is it possible to say anything about its performance guarantee (maybe under additional assumptions)?", "limitations": "The authors have discussed the limitations in appendix, which sounds reasonable to me.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-organized, and complete in structures. \n\n* In terms of theoretical contribution, the paper derives a monotone improvement property in the exact setting, i.e., when no parameterization is involved. The empirical algorithm, i.e., Scal-MAPPO-L, is proposed.\n\n* In terms of numerical experiments, the paper performs reasonable experiments to compare Scal-MAPPO-L with other PPO family algorithms (with code provided). The experimental results demonstrate Scal-MAPPO-L exhibits decent performance.", "weaknesses": "My major concern about the paper is regarding the novelty of the paper given the existing literature [10]. The paper shares many similarities with [10] (Safe multi-agent reinforcement learning for multi-robot control), including presentation and theoretical results. Although I understand that [10] considers a centralized setting with full observation, and the setting considered here is decentralized, I am not sure about the technical contribution of the paper beyond leveraging the spatial decay of correlation assumption.\n\nAlso, the introduction of the spatial decay of correlation is somewhat abrupt. The author seems did not mention anything about the graph structure for the agents before introducing the assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the valuable comments from the reviewer. We hope our responses below provide further clarity.\n\n**Remark: Without further specification, we use \"[number]\" to refer to the corresponding reference in our paper.**\n\n> W1: My major concern …… correlation assumption.\n\nA: We re-clarify our technical contributions in the first point of our **General Response** and provide more concrete technical contribution of the paper against [1] as follows:\n\n* We quantify the maximum information loss regarding the advantage truncation in **Proposition 3.3** by extending the theoretical results of the truncated Q in [2-3] and draw further the bound of surrogate return in **Corollary 3.4** under the spatial correlation decay assumptions (their proofs is reported in **Appendixes C.3-C.4**).\n\n* We provide a new local policy optimization objective for each agent by integrating the rigorous bounds of the trust region method and the bounds of the truncated advantage function (refer to **Proposition 3.5** and its proof in **Appendix C.5**). In addition, based on the upper-bound version of the trust region method, we obtain the upper bound of the safety constraints (refer to **Corollary 3.6** and its proof in **Appendix C.6**).\n\n* We develop a novel scalable multi-agent constrained policy optimization method that guarantees both satisfaction of safety constraints and monotonic performance improvement in **Theorem 3.7** with a sequential update scheme (its proof is reported in **Appendix C.7**).\n\n> W2: Also, the introduction …… introducing the assumption.\n\nA: Thank you for the valuable suggestions, we will introduce the graph structure and reorganize some of the symbols in the new version. A preliminary modification can be seen in the third point of our **General Response**.\n\n> Q1: Could the author …… correlation assumption). \n\nA: We re-clarify our technical contributions and main technical difficulties in the first point of our **General Response** and provide more concrete technical contribution of the paper against [1]  in the answer to W1(Major).\n\n> Q2: Could the author provide …… elaborate further. \n\nA: We would like to provide comprehensive justifications for comparing the existing literature [2] and [3] as follows.\n\n**Against [2]:** Safe Dec-PG [2] tackles distributed safe reinforcement learning problems, which implies the absence of a central controller to coordinate the agents. Both the rewards and constraints are only locally/privately known to each agent. Specifically, they decouple common reward functions and joint actions through a communication network to share information with neighboring agents. However, it is worth noting that their approach still assumes each agent can access the global state (which we do not have access to) and requires that the actions of all neighboring agents on that network be available (whereas we employ sequential updating).\n\n**Against [3]:** Literature [3] also proposes a scalable safe MARL approach based on the spatial decay assumption of the environment dynamics. The paper updates the policies of agents by the truncated gradient estimators, which depend on the local states and actions of the κ-hop neighboring agents. Despite this, the problem of non-stationarity within local interactions remains acute. However, we adopt the multi-agent advantage decomposition and the sequential policy update scheme from [1][4] when updating local policies. Specifically, the policy update of an agent depends only on the actions of previous agent in the sequence, rather than on the actions of all $\\kappa$-hop neighboring agents.\n\n> Q3: The empirical algorithm …… under additional assumptions)?\n\nA: Thank you for the valuable comments. We admit that some approximations of the surrogate objective are employed in the practical algorithms, as clarified in lines 224 in **Section 3.3**. Most of these approximations are traditional practices in RL.\n\nIn the actual execution, Scal-MAPPO-L may not rigorously maintain the theoretical guarantees in **Theorem 3.7**, which is mainly due to several reasons:\n\n* Uncertainty in neural networks: Neural networks are inherently uncertain and extracting useful information from many messages may lead to lower performance, especially for algorithms with rich information (the observation of agents).\n\n* A form of expected KL-divergence constraint: This approach is commonly used in RL to avoid computing KL-divergence at every step. However, it introduces sampling errors; fortunately, the sampling errors are recomputable/controllable.\n\nWe will consider how to solve the optimization problem in **Theorem 3.7** more precisely and try to provide theoretical guarantees in future work.\n\n**References:**\n\n[1]\tShangding Gu, Jakub Grudzien Kuba, Yuanpei Chen, Yali Du, Long Yang, Alois Knoll, and Yaodong Yang. Safe multi-agent reinforcement learning for multi-robot control. Artificial Intelligence, 319:103905, 2023.\n\n[2]\tSongtao Lu, Kaiqing Zhang, Tianyi Chen, Tamer Ba¸sar, and Lior Horesh. Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning. In AAAI, 2021.\n\n[3]\tDonghao Ying, Yunkai Zhang, Yuhao Ding, Alec Koppel, and Javad Lavaei. Scalable primal-dual actor-critic method for safe multi-agent rl with general utilities. In NuerIPS, 2023.\n\n[4]\tJakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimization in multi-agent reinforcement learning. In ICLR, 2021.", "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": "", "extra_scores": {}}]

Author rebuttal:
# General Response

We would like to express our sincere gratitude to the reviewers for reading our paper and providing valuable feedback. Below, we answer some common questions raised by the reviewers, including **the technical contributions**, **the assumptions about spatial correlation decay**, **the graph structure**, and **the new experimental results**. Please find our responses to other questions in the personalized rebuttals.

**Remark: Without further specification, we use "[number]" to refer to the corresponding reference in our paper.**

> Regarding the technical contribution of the paper. 

A: Our theoretical results build upon the scalable MARL family of works [1-3] and PPO-based (TRPO-based) MARL family of works [4-5]. Their solid and complete theoretical analyses provide a good research foundation for our work. Here, we would like to re-clarify our technical contributions. 

The main technical contributions are as follows:

* First, we quantify the maximum information loss regarding the advantage truncation based on two assumptions about the transition dynamics and policies. 

* Then, by integrating the rigorous bounds of the trust region method and the truncated advantage function, we provide a new local policy optimization objective for each agent. 

* Furthermore, we develop a novel scalable multi-agent constrained policy optimization method and prove that the safety constraints and joint policy improvement can be guaranteed. 

* In addition, we parameterize each agent’s policy and propose a practical algorithm called Scalable MAPPO-Lagrangian (Scal-MAPPO-L).

The main technical difficulties are as follows:

* How to quantify the information loss regarding the advantage truncation? (refer to **Proposition 3.3** and its proof)

* How to ensure the local policy updates are not overly conservative? (refer to **Proposition 3.5** and **Corollary 3.6** and their proofs)

* How to prove that the proposed method can consistently improve rewards and adhere to safety constraints at every iteration? (refer to **Theorem 3.7** and its proof)

> Regarding Assumption 2.1 and Assumption 2.2. 

A: We would like to provide further discussion on the assumptions about spatial correlation decay as follows:

* The parameter $W^{ij}$ in Dobrushin condition [6] reflects the extent to which the local transition probability of agent $i$ is affected by the state and action of agent $j$. **Assumption 2.1** amounts to requiring $W^{ij}$ decreases exponentially with the distance between any two agents $i$ and $j$, which has been used in previous works [1-3] about scalable MARL. This paper does not make it more stringent.

* From a theoretical perspective, our approach can be considered for most of safe MARL tasks, especially when there is a performance gap between independent learning and centralized learning.

* We provide a mathematical example to illustrate the relationship between the two assumptions in **Appendix B.2**. It is evident from this mathematical example that **Assumption 2.2** necessarily holds when **Assumption 2.1** holds and the parameters $\xi$ and $\beta$ satisfy certain conditions. However, in order to maintain a concise presentation, we introduce **Assumption 2.2**.

* When **Assumption 2.1** holds, the numerical example in lines 522 in the appendix can provide a reference basis for selecting the values of the parameters in **Assumption 2.2**. However, accurately determining the spatial decay of correlation for the dynamics remains a challenging engineering task. In this paper, we empirically adopt conservative values. 

> Regarding the graph structure under a network of agents.

A: We sincerely appreciate the suggestion from the reviewers to introduce the graph structure for networked multi-agent systems, and we accept it to make the paper read more smoothly. Specifically, in the new version, we will introduce the agent graph structure in the introduction section and redescribe the safe MARL problem in **Section 2.1** as follows:

Consider a safe MARL problem subject to multiple constraints, where each agent are associated with an underlying undirected graph $\mathcal{G}=$ $(\mathcal{N}, \mathcal{E})$. Here, $\mathcal{N}=\{1, \ldots, n\}$ is the set of agents and $\mathcal{E} \subset \mathcal{N} \times \mathcal{N}$ is the set of edges. The problem can be formulated as a constrained Markov game, ……

> Regarding the new experimental results.

A: We run new experiments to provide the results with more agents (for 17 agents in Safe Humanoid task) and more training steps ($1.5 \times 10^7$) and update the results in the PDF. All results are averaged over two random seeds, and the curves are smooth over time. We will continue our efforts to provide richer and more complete experimental results in the new version.

**References:**

[1]	Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable multi-agent reinforcement learning for networked systems with average reward. In NeurIPS, 2020.

[2]	Yiheng Lin, Guannan Qu, Longbo Huang, and Adam Wierman. Multi-agent reinforcement learning in stochastic networked systems. In NeurIPS, 2021.

[3]	Donghao Ying, Yunkai Zhang, Yuhao Ding, Alec Koppel, and Javad Lavaei. Scalable primal-dual actor-critic method for safe multi-agent rl with general utilities. In NuerIPS, 2023.

[4]	Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimization in multi-agent reinforcement learning. In ICLR, 2021.

[5]	Shangding Gu, Jakub Grudzien Kuba, Yuanpei Chen, Yali Du, Long Yang, Alois Knoll, and Yaodong Yang. Safe multi-agent reinforcement learning for multi-robot control. Artificial Intelligence, 319:103905, 2023.

[6]	Amir Dembo and Andrea Montanari. Gibbs measures and phase transitions on sparse random graphs. arXiv preprint arXiv:0910.5460, 2009.

Meta-review: The paper addresses the important problem of a constrained MARL. The theoretical results rely heavily on the spatial correlation decay assumption, which simplifies analysis greatly but is a realistic approximation in multiple practical scenarios. The theoretical analysis is used to motivate a practical decentralized algorithm. Numerical experiments illustrate the proposed algorithm is able to satisfy constraints as well as the centralised solution, and can also achieve similar reward to the centralised solution when the agents can access the observation of enough number of neighbours.

One limitation in the experiments is the use of small networks (up to 12 agents) and the lack of details on the network topology. However, the authors provided a still small but more convincing experiment with up to 17 agents during the rebuttal period. The authors have committed to provide details on the network topology, and they should include the new experiment (with details on computation time for completeness) in the camera ready version.

Overall, the paper is clearly written, establishes a new baseline for constrained MARL, and can inspire future research.
Decision: Accept (poster)