Multi-Agent First Order Constrained Optimization in Policy Space
Authors: Youpeng Zhao
Yaodong Yang
Zhenbo Lu
Wengang Zhou
Houqiang Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Safe Multi-agent Reinforcement Learning
constrained policy optimisation
first-order optimisation

Abstract: In the realm of multi-agent reinforcement learning (MARL), achieving high performance is crucial for a successful multi-agent system.
Meanwhile, the ability to avoid unsafe actions is becoming an urgent and imperative problem to solve for real-life applications. 
Whereas, it is still challenging to develop a safety-aware method for multi-agent systems in MARL. In this work, we introduce a novel approach called Multi-Agent First Order Constrained Optimization in Policy Space (MAFOCOPS), which effectively addresses the dual objectives of attaining satisfactory performance and enforcing safety constraints. Using data generated from the current policy, MAFOCOPS first finds the optimal update policy by solving a constrained optimization problem in the nonparameterized policy space. Then, the update policy is projected back into the parametric policy space to achieve a feasible policy. Notably, our method is first-order in nature, ensuring the ease of implementation, and exhibits an approximate upper bound on the worst-case constraint violation. Empirical results show that our approach achieves remarkable performance while satisfying safe constraints on several safe MARL benchmarks.

Multi-Agent First Order Constrained Optimization in Policy Space
Youpeng Zhao', Yaodong Yang" Zhenbo Lu Wengang Zhou Houqiang Li
University of Science and Technology of China, Institute for AI, Peking University Institute of Artificial Intelligence, Hefei Comprehensive National Science Center zyp123@mail ustc. edu. en, yaodong . yangēpku edu. luzhenbo@iai. ustc. edu. cn, {zhwg, lihq)oustc. edu. cn
Abstract
In the realm of multi-agent reinforcement learning (MARL), achieving high per- formance is crucial for successful multi-agent system. Meanwhile, the ability to avoid unsafe actions is becoming an urgent and imperative problem to solve for real-life applications. Whereas, it is still challenging to develop safety- method for multi-agent systems in MARL. In this work, we introduce a novel approach called Multi-Agent First Order Constrained Optimization in Policy Space (MAFOCOPS), which effectively addresses the dual objectives of attaining satis- factory performance and enforcing safety constraints. Using data generated from the current policy, MAFOCOPS first finds the optimal update policy by solving constrained optimization problem in the nonparameterized policy space. Then, the update policy is projected back into the parametric policy space to achieve feasible policy. Notably, our method is first-order in nature, ensuring the ease of implementation, and exhibits an approximate upper bound on the worst-case constraint violation. Empirical results show that our approach achieves remarkable performance while satisfying safe constraints on several safe MARL benchmarks.
1 Introduction
Cooperative multi-agent systems play a significant role in various domains, where a group of agents coordinate with each other accomplish tasks and collaboratively optimize cumulative rewards for the team 2] Such a setting is frequently employed in many real-life scenarios such as robotics 3] autonomous vehicles
4 traffic light control [5] and the smart grid [6] Thanks to the recent remarkable advance of reinforcement learning techniques in various complex tasks 17-9, multi-agent reinforcement learning (MARL) has attracted substantial attention and quite few algorithms have been proposed, including value-based methods (0H14) and policy gradient methods (15H18). Despite the notable achievement in academia, most MARL algorithms prioritize policy optimization solely for reward maximization, while disregarding potential negative or harmful consequences resulting from the agents' behaviors. Consequently, these methods can not be directly deployed in practice. In reality, many applications often require the agents to refrain from taking certain actions visiting particular states [19 20). For instance, an unmanned car must adhere to traffic regulations by not crossing red light, even while pursuing its destination, in order to prioritize safety.
To address the above issues, researchers have been devoted developing algorithms that learn policies which adhere to safety constraints and great progress has been made in single-agent RL setting (20-- 23 However, is still a daunting challenge develop safe policies for multi-agent systems. Because of the existence of multiple agents, the environment may suffer from non non-stationarity due to simultaneously learning agents, posing negliggl challenge to the training process. Moreover, ensuring safety in MARL is highly intricate. To provide a better depiction of the inherent challenges,
"Correponniigg authors: Yaodong Yang and Zhenbo Lu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Policy Space for Agent 1
Policy Space for Agent 2
0.83
1.429
-0.500
1.140
-0.286
Safe area for agent-1
0.857
857
00500
consider safety
500
0.286
Safe area for agent 2
Update direction
consider safety
0000
140
0,857
500
0.286
-0.500
-0.85 -0.857
-1.140
-1.29
Joint Safe Area
-08857
2500
Updato direction
0.286
0,500
0.857
Figure/ I: An example to illustrate the challenges in safe MARL. Reward distribution is presented in the policy space for each agent. Green rectangles delineate the individual safe areas for each agent and the blue ones depict the joint safe area. Green arrows symbolize the update direction for each agent whereas the dashed ones signify the intended update direction if each agent solely considers its own objectives and the crosses represent that the dashed update direction is unsuitable in safe MARI..
we show an illustrative example in Figure [ This figure showcases the policy space for each agent, wherein the reward distribution is presented. The green rectangles delineate the individual safe areas for each agent and the blue ones depict the joint safe area. The green arrows symbolize the update direction for each agent, whereas the dashed ones signify the intended update direction if each agent solely considers its own objectives. When agents are randomly initialized, they naturally tend to update the policy along the dashed line arrows to maximize the reward. However, due to the presence of safety constraints, they must adjust their updates along the solid line arrows to ensure their policies fall within the safe area. This is non-trivial as it may conflict with their goal of reward maximization. Furthermore, after individually addressing their safety constraints, the agents must also consider the safety constraints of others to collectively converge to the joint safe area, adding more complexity to the optimization process for the entire system. The interplay of these factors underscores the inherent difficulties in solving the problem of safe MARL.
Recently, as a notable advancement in the field of safe MARL, Multi-Agent Constrained Policy Optimization (MACPO) [24] has been proposed as safe and effective solution. MACPO attains the properties of both monotonic improvement guarantee and safety constraints satisfaction guarantee at every iteration during training. However, this algorithm involves solving an optimisation problem using Taylor approximations and inverting a high-dimensional Fisher information matrix. As a result, the computation is very complex and the policy update often becomes infeasible. To alleviate this issue, it requires additional recovery steps, which, however, sometimes causes updates to be backtracked and samples be wasted.
Taking inspiration from the sequential policy update scheme introduced in HATRPO 18] we have devised simpler approach to incorporate safety constraints in solving safe MARL problems compared with MACPO. The resulting algorithm, Multi-Agent First Order Constrained Optimization in Policy Space (MAFOCOPS), aims address the following question of how achieve the best constraint-satisfying policy update given the current policy for each agent. Our method follows a two- step process to give solution to this problem. First, based on the theoretical foundations presented in MACPO, we demonstrate that the best policy update has a near-closed form solution when attempting to solve the optimal policy in the nonparametric policy space. Subsequently, we project the policy back into the parametric policy space as direct evaluation of the optimal policy is usually not feasible. This can be realized by sampling from the current policy and evaluating a loss function between the parameterized policy and the optimal policy obtained in the nonparametric policy space. Notably, our algorithm only employs first-order approximations, making it straightforward has an approximate upper bound for worst-case constraint violation. To validate the effectiveness of our approach, we conduct experiments on two safe MARL benchmarks proposed by 124), namely Safe MAMuJoCo and Safe MAIG. The experimental results demonstrate the superior performance of MAFOCOPS compared to MACPO, despite being a simpler algorithm.
implement, and
2

---

2 Related Work
Safety has become a crucial and longstanding concern in the field of reinforcement learning 22 In this section, we discuss recent advancements in the domain of safe RL for multi-agent environments.
The realm of safe multi-agent reinforcement learning is nascent area of research that has gained increasing importance [26]. Several attempts have been made to tackle safe MARL, but most existing approaches have limitations. For example, CMIX [7 leverages the value function decomposition method and modifies the reward function to account for constraint violations, yet this algorithm fails
to provide safety guarantees during training. Another approach is Safe Dec-PG [28] which proposes a decentralized policy gradient descent-ascent method by means of a consensus network and employs primal-dual framework to balance reward maximization and cost minimization. Nevertheless, the consensus requirement in this work equivalently imposes an extra constraint of parameter sharing among neighbouring agents, potentially leading to sub-optimal policy [18). It noteworthy that most current safe MARL methods are tailored to robotics tasks, utilizing techniques such as barrier certificates 129 30 or model predictive shielding [1] to address safety issues. These methods,
however, are specifically designed for robotics applications. Besides, they often require supervised learning based approaches or specific assumptions concerning the state space and environment
dynamics.
As recent remarkable solution, MACPO 24 incorporates a sequential policy update scheme. This algorithm develops the multi-agent trust region learning based on CPO (20) and provides theoretical guarantees of both monotonic improvement in reward and compliance with cost constraints in a multi-agent setting. To achieve practical solutions to the safe MARL problems, the policy for each agent needs to be parameterized with a neural network, which effectively represents the policy in policy space. However, achieving parameterized policies in MACPO involves solving optimization problems using first and second-order Taylor approximation, which includes taking the inverse of Fisher information matrix, and the computation is implemented by the conjugate gradient method [32]. These operations can introduce nonnegligible approximation errors, thereby compelling MACPO to undertake additional steps during each update in the training process in order to recover from constraint violations. In contrast, our algorithm takes different approach by solving the optimization problem within the nonparametric space and then projecting the results back into the parameter space. By leveraging a simple first-order method to eliminate the approximation error, our algorithm ultimately outperforms MACPO.
3 Problem Formulation
A safe MARL problem can be formulated as a Constrained Markov Decision process, which is described by tuple denoted as < S,S,A, p, P 7, R. C, >, Here, A 21,2.... .... denotes the set of agents involved in the system, S is the state space, A = II A represents the product of the action spaces of agents, i.e., joint action space, p : S x A x S + R is the probabilistic transition function, pa is the initial state distribution and 7 E [0, 1) is the discounted factor. The team reward function R: S x A- + R maps state and joint actions to a scalar reward while C {Cj) VEN isimmi is the set of sets of cost functions denoted in the form Cj S A' + R (every agent has m' cost viE
functions). The set of corresponding cost-constraining values is given by c = {c) (c))isM; is At time step f, the multi-agent system is situated in state and every agent i selects an action at based on its policy T' ra'1 [s), forming a joint action ag = .a..... ..... ..f".))a))))) and joint policy π T(a ss) = 11 xr (a*) This leads the environment to transit to new state 8141 p(-|se, ae) according the probabilistic transition function and the system receives the reward R(st, ae) while each agent: incurs individual cally-cooperative multi-agent setting where all
costs C₁ Vjj ..... m'. This study focuses agents share the same reward function, aimed at maximizing the expected total reward:
J(T)
F E aoise B.
n't R(ss, ac)]
Moreover, we impose that each agent i satisfies its safety constraint, which is defined as
(T) 2 Enorg an ao
Y Cs,, at)l S cs. Vj 1, 1,..., ,mm
t=0
3

---

We define the auteencction value and the state-value function in terms of reward as
(s( A Es p.
r R(s;, at)]so = s, do = a), (s) - Eawt (ax,,
It's worth noting even though the action aj taken by agent does not directly impact the costs {C* (st, )= of other agents k * from the above formulation, the total costs still be influenced by this action implicitly due to its influence on the subsequent state 8t+1- This formulation captures the realistic multi-agent interactions in real world. For instance, when car runs red light, although other cars may not be immediately endangered by this action, the resulting disruption in traffic flow may lead potential hazards later on. To illustrate the jeh cost function of agent we express the corresponding state-action cost value function and the state cost value function as below:
Q (s, A Ea- w
Σ
(C) = =s = =a',,
t=
(8) A aa
(st, = s].
Notably, although similar in form traditional QT and Vr,, the cost value function Qj.v and Vj.= involve additional indices and where the subscript refers to an agent and j denotes the jth cost.
Motivated by the sequential policy update scheme, we pay close attention to determining the con- tribution of different subsets of agents to overall performance in this study. We denote an arbitrary subset fir.... in } of agents as 11:h while -i1:h refers its complement. Given the agent subset iich, we define the multi-agent state-action value function:
1'2n (s, alin) & Ea-ina 1Q a LIA a =.
Furthermore, for disjoint sets iish and jı:k, the multi-agent advantage function is defined as follows: * (s, a= a (ni)) A Quiaefis (x, " a a²*.))
Q#** (x, (x.))
An interesting and critical observation concerning the aforementioned multi-agent advantage function is that the advantage A can be written as the sum of sequentially-umfoo multi-agent advantages of individual agents, that is,
Lemma 1 (Multi-agent advantage decomposition [8] For any state s E S, subsets of agents iL E A and joint action af the following identity holds
1 (s, a (2:
( (8
j=1
4 Method
Expanding on the above foundational concepts and the derivatives of multi-agent trust region learning with constraints, MACPO provided important insight. It highlighted that when the policy changes for all agents are sufficiently small, each agent can learn a better policy æ' by only considering its own surrogate return and costs, which is consistent with the sequential policy update scheme. In work. building upon the formulas in MACPO, we can deduce that, for agent én and the index of its cost functions j. given the joint policy no, at the kth iteration and updated policies of the previous fi-h-1 the new policy obtained by solving the following optimization agent sets 11 namely T0a11 problem:
marimize E
smptoe . -hhh-w inh-i Nor aahnoii 14 (s, aaaa--i,a"
x/-¹
(To.) + Fes- wrnnth (A) (s, S c/ t..,.... mm
(2)
(xI Tbt S.
(3)
where (T ; A Esmpto, [DKz (T)) (-1s), To (-1s))]- A simple proof presented in Ap-
pendix A When solving the optimization problem we use two-step approach:

---

Ain-1 find an 1. For agent ih, when provided with the joint policy Th, and updated policy Tossi optimal update policy ri*** in the nonparameterized policy space, denoted by
2. Project the policy found in previous step back into parameterized policy space Hy by solving for the closest policy me IIg obtain "02+1* Here we consider the set of parameterized policies IIg = {To E { E which allows for evaluation and sampling.
4.1 Finding the Optimal Update Policy
In the first step, aim to find the optimal nonparameterized policy and propose the following solutions (see Appendix B for proof):
Theorem 1. For agent in, we define b/th = - (TTO). If naa is feasible policy, the optimal policy takes the form
th (als) = The (als)
Zagios , (s) cxpp 2,j (nron (s, (4h vy (s, (9.a"*))3
(4)
where Ma,, (s, (s.a"") = f - a---- [A (s, alia 1, 1, (cdh)l.Za,.v) ,0 (s) is the partition function that #k+1 ensures Equation to be valid probability distribution, and A, as well as vy are solutions the following optimization problem:
min $22220
2 + 1sbb" N E whth [logZaj.es (+)]
(5)
The structure the optimal policy exhibits an intuitive nature, as it assigns a substantial probability mass to regions of the state-action space with high returns. This allocation is counterbalanced by penalty term multiplied by the cost advantage. Another desirable property of the optimal update policy is that for feasible policy Te. it has an upper bound for worst-case guarantee for cost constraint satisfaction according to Lemma.2 in MACPO 24
4.2 Approximating the Optimal Update Policy
When addressing the optimization problem 1 о
the first step, the optimal update policy for agent in may not necessarily reside within parameterized policy space 1lg. Consequently, evaluating or sampling from this policy becomes unfeasible. To this end, in the second step, we need to project the optimal update policy back into the parameterized policy space by minimizing the loss function:
L(() Es-epre [Dxz (m) || (s)).
(6)
In this context, T. E Il represents some projected policy that serves as an approximation of the optimal update policy. To minimize this loss function, first-order methods can be employed. In doing so, we can leverage the following result as useful tool in our optimization efforts:
Corollary 1. The gradient of [()) takes the form
vo = EaNener (DD (+])""1)))"
(7)
where
Vorthh (als) (als) (Maay -v,
VoDKa
VoDKL 11
E tn
(s.a"))
X, aawith
To (a|s)
(8)
The proof is shown in Appendix
It's to be noted that 27 can be estimated by sampling from the trajectories generated by policy πo.- which allows us to train our policy using stochastic gradients, key aspect of our methodology. This corollary serves as guiding framework for our algorithm. At every iteration, we begin with a policy To,, utilizing to generate trajectories and collect relevant data. Subsequently, we employ this data in conjunction with 5 to estimate A; and My. We then draw minibatch from the collected data to estimate (() as outlined in Corollary After taking gradient step using Equation 27 another minibatch and repeat the process.
we draw
5

---

4.3 Practical Implementation
For agent in, solving the dual problems presented in in computationally challenging when dealing with large state/action spaces as calculating the partition function Zx,,,, (s) often involves evaluating a high-dimensional integral or sum. Moreover, >, and By are dependent on the iteration is and need to be adjusted at every iteration to ensure the effectiveness of optimization.
Based on the structure of the optimal update policy, it is observed that X; - O, xh*** tends to be greedy while the policy becomes more exploratory when X5 increases. We note that X, exhibits
similarities the temperature term utilized in maximum entropy reinforcement learning 333 Fixed
values of À have been demonstrated to yield reasonable outcomes in training [34 35 22 In practical implementations, we have observed favorable results by using fixed A through hyperparameter
sweeps. However continuous adaptation of 2 during training is necessary to ensure cost constraint satisfaction. In this regard, we appeal to an intuitive heuristic based on primal-dual gradient methods 36 to determine the appropriate value of V/- Recall that by strong duality, the optimal > and 2 minimizes the dual function 5 which we will denote by L(r Nz) Then we can adopt gradient descent W.E. U/ to minimize (xrha, >j."g) as follows:
Corollary 2. The derivative of L(Tr'i,, >3., U2) w.r. Us is
aL(m"h" :y., 67" E Ex-pre oth whaath wh (alo)) (s,ath)
(9)
Ovg
The proof is shown in Appendix D
The last term in the gradient expression poses a challenge since π T may not locate in parameterized policy space, leading direct evaluation of the term to be infeasible. Nevertheless, due to the proximity between To and nh*** enforced by the KI. divergence constraint, it's reasonable to assume that (s, (s,a²)) = O. In practice, we have
Ea-prer a' [A), (s, a²")] ]]
R E SsmRao aahhaaih to T
observed that setting this term to zero yields favorable outcomes, which gives the update term as follows:
V2 + projlu, alch - (hhh
(10)
"i
where a is the step size to control the magnitude of the update. The projection operator proju, ensures that vj remains within the interval [0. Dmma]] with Vmaz chosen to prevent v, from being excessively large. In practical applications, the estimation of J (Tre)) can be accomplished using Monte Carlo methods by leveraging trajectories collected from .O... This approach aligns with the update rule employed in MACPO (24] We recall that in 4 Vy acts as a cost penalty term where increasing vj makes the likelihood of state-action pairs with higher costs being sampled by + diminish. Consequently, the update rule presented in exhibits intuitive characteristic: it raises Vj if J (To.)) > dih,, indicating violation of the cost constraint for TO. and reduces V/ otherwise. Using the proposed update rule, Uj can be updated before updating the policy parameter T
To be noted, our algorithm a first-order method, which implies that the approximations made are accurate only around the initial condition (i.e., TT T ). To better enforce this condition, we have introduced a per-state acceptance indicator function I [(s)) = Dzz(" w 25) to 27 This
function helps in rejecting sampled states whose DKL(T,) = [s] is too large, thereby improving the accuracy of the gradient update. The resulting sample gradient update equation is as follows:
(orth (ozlss) Amyh (ay1ss)
VoT(O)=
Σ VoDrL 1=1
[ss]
(Amo, (s,0"") - 1y A mee, (s. (s."))))) (11)
N
where N is the number of samples collected using policy Te.. The estimates of the advantages
functions for the returns and costs, denoted as iiTe, and A.i. are obtained from critic networks referring to MACPO. We estimate these advantages using Generalized Advantage Estimator (GAE) 37 and apply stochastic gradient descent using [I] During the training process, our algorithm employs the early stopping criterion to ensure that the updated policy satisfies the trust region constraint. Specifically, this criterion is defined as N value network, we minimize the Mean Square Error (MSE) between the output and target value. The procedure of our algorithm is presented in the Appendix E
E DKL(=T" [ [ > 8. To update the

---

(a)
(b)
(c)
(d)
Figure 2: Example tasks in Safe MAMuJoCo and Safe MAIG. HalfCheetah, (c): Safe 2x3-ManyAgen Ant, (d): ShadowHandOver. In each of these tasks, the body parts of the robots are controlled by different agents. Agents collaborate to manipulate the robot while ensuring that the safety constraints are not violated.
(a): Safe 2x4-Ant, (b): Safe 2x3-
Experiments
We evaluate the effectiveness of our algorithm on two benchmarks of safe MARL: Safe MAMuJoCo and Safe Multi-Agent Isaac Gym (MAIG). The former is a safety-awan modification of MAMuloCo
38.. where there exist obstacles in the environment. Meanwhile, Safe MAIG is developed on top of Issac Gym [39]. GPU-based platform for robotics tasks. Being an extension of DexterourHands (40) Safe MAIG requires agents to control the robot hands while optimizing both the reward and safety performance. We present some example tasks in Figure 5 and more details about the environments are introduced in the appendix.
While our primary aim is to propose simpler alternative to MACPO, we also evaluate the perfor- mance of MAPPO-Lagrangian (MAPPO-L), which is put forward alongside MACPO (24]. This method adopts Lagrangian multipliers to solve optimization problems in MACPO. Without the requirements of repetitive computation of the Hessian matrix whose size grows quadratically with the dimension of the parameter vector, the Lagrangian method is also first-order and simple to implement. However, unlike MACPO and MAFOCOPS, whether this algorithm satisfies any worst-case constraint guarantees remains unknown. In addition, we compare the results of our algorithm with two standard MARL baseline algorithms, namely MAPPO an] HAPPO [8]. Both sets of experiments are carried out using the MACPO codebase and our experiments are conducted on GeForce RTX 3090 GPUS. More implementation details can be found in supplementary materials.
5.1 Performance on Safe MAMuJoCo
In this section, we select several experiment scenarios of Safe MAMuJoCo and execute each algorithm for 10 million samples per task. The cost thresholds are determined by taking 50% of the cost achieved by standard MARL algorithms after million sample runs. To be noted, while most training parameters remain the same as those in the codebase, such as the learning rate and settings of optimizers, we adjusted some certain hyperparameters associated with the cost thresholds to make the algorithms best suit the experiment scenarios. It noteworthy that the performance of MAPPO-L highly relies on the Lagrangian coefficient, rendering it more sensitive to the hyperparameters. In light of this observation, we adopt distinct hyperparameters for MAPPO-L in different categories of tasks. In contrast, the other two safe MARL algorithms are implemented with uniform hyperparameter settings across experimental scenarios this benchmark, indicating their potential efficacy.
Due to page limit, we present partial results of our experiments in Figures 3 and more results can be seen in Appendix G The experimental results show that all the safety-aware algorithms are able to satisfy the safety constraints while our proposed MAFOCOPS manages to achieve the best overall performance across all tasks. Even when our method achieves similar performance to the other two algorithms in HalfCheetah scenarios, it still exhibits faster learning, demonstrating the advantages of our approach. For HAAPO-Lagranggaal we note that this baseline algorithm always achieves a similar performance as MAPPO, except in HalfCheetah scenarios where the cost threshold significantly smaller compared to cost achieved by HAPPO and MAPPO. This may due to being built upon Lagrangian multiplier combined with standard MARL algorithms, leading to a performance more similar safety-unawan MARI algorithms. addition, from our discussion about MAPPO-L algorithm,
that M. MAPPO-Lagrangii
know that it maintains a rather soft safety
7

---

Manyhgennt www.ett..ot 2033
ManyAgent Avrt 3x3
ManyAgest And det
Aze 24d5
Marrydigent Avri
Mirry Peggett 2002
Manryggenn Artt
Aurt Zooldd
(a) ManyAgent Ant 2x3, ManyAgent Ant 3x2, ManyAgent Ant 1x Ant 2x4d
Ant
4x2
HallChestuh 2x3
HutiCheotah
Ha 2033
HraltCheattn
(b) Ant 2x4, Ant 4x2, HalfCheetah 2x3, HalfCheetah 3x2
Figure 3: Performance comparisons on tasks of Safe ManyAgent Ant, Ant, and HalfCheetah in terms of cost and reward. The safety constraint values for these presented tasks are set to be 25, 50 and 30, respectively. The solid line shows the median performance across 5 seeds and the shaded areas correspond to the 25-75% percentiles.
awareness, but the other two algorithms reaches safety via hard constraints. Therefore, MACPO and MAFOCOPS possess more promising properties, thus being the focus of our study.
Interestingly, our intuition suggests that a higher number of agents usually leads to increased com- plexity of the environment and hence worse performance. However, this phenomenon is not always observed. We assume that this because, the same type of map, the multi-agent system has to control the same robot, and the number of agents determines how the robot is partitioned. Fewer agents means that each agent has to control more parts of the robot, making the difficulty of the envi- ronment non- non-lincarly dependent on the number of agents. Whereas, in scenarios of 6x1 Many Ant, we still note that as the number of agents increases, there exists a degradation in the performance of MACPO, which can attributed to the complexity of the computation worsening with the growth in the number of agents. As for MAFOCOPS, our first-order method shows stronger resistance to task complexity, showing the advantages of our algorithm when coping with multi-agent problems. What's 's more, we provide videos of the trained policies of both our algorithm and MACPO in the supplementary materials to intuitively demonstrate the benefits that our approach brings.
5.2 Performance on Safe MAIG
Apart from experiments in Safe MAMuJoCo, we also conduct experiments in the Safe MAIG benchmark. In this part of experiment, the cost thresholds are set as 25% of the cost obtained by standard MARL algorithms after running for one-tenth of the entire training process. The total training settings are the same those in Safe MAMuloCo, while some specific hyperparameter values are adjusted considering the great difference between these two experiment environments.
Experiment results in this benchmark are presented in Figure
Under this complicated environment,
8

---

Shad Dhar
Onvirnmtent beiiee
Figure 4: Performance comparisons on tasks of Safe MAIG. The safety constraint value for Shad- owHandOver is set to be 15 and that for another task set to be 110. The solid line shows the median performance across 5 seeds and the shaded areas correspond to the 25-75% percentiles.
it can be observed that the soft constraint algorithm, MAPPO-L, exhibits delay in guaranteeing safety. Notably, in ShadowHanddeOOriettaii task, experiences sudden drop in cost, which significantly impacts the reward. Conversely, although similar phenomenon occurs with MAFOCOPS, our method manages to optimize the reward in this condition and attains an acceptable performance. Although the reward of MACPO remains relatively stable, its final performance is not as favorable as our method. The different performance between MAPPO-L and the other two algorithms indicates that the property of upper bound violation is important in safe reinforcement learning, which also demonstrates the significance our work.
5.3 Efficiency Analysis between MAFOCOPS and MACPO
As a first-order method, our MAFOCOPS not only eliminates the approximation errors when solving the optimization problems, leading better performance, but also significantly reduces the compu- tation cost. In this part, we evaluate the memory cost and frame per second (FPS), which is often adopted measure the training efficiency of reinforcement learning algorithms, between MAFOCPS and MACPO. For simplicity, we adopt memory monitor tools to track memory utilization after 200000 samples and record the average FPS metric.
Due to the page limit, the results are shown in Appendix of supplementary materials. From the results, it is evident that our algorithm obtains substantial improvement in computational efficiency and shows the ability to effectively save memory resources, especially when the number of agents grows. Consequently, we can infer that when confronted with tasks with multiple agents, second-order algorithms may be ill-suited due to their substantial computational costs. In contrast, our proposed method can successfully address such scenarios without succumbing to the computational burden.
5.4 Sensitivity Analysis
Based on the description provided in Section 4 it is apparent that the Lagrange multipliers, X and Pmoz. are crucial to the performance of our approach. In addition, analyzing the sensitivity of our algorithm to changes in the safety bound is also meaningful. Hence, we seek to investigate the sensitivity of our algorithm to these hyperparameters we conduct some ablation studies using some scenarios of Safe MAMuJoCo and more details are presented in Appendix
well the safety bound. In this way,
Considering the intricacy of multi-agent environments, it is difficult to delineate the correlation between the performance of our method and the hyperparameters A3 and Vmaz- Nonetheless, choosing hyperparameters in proximity outcomes. Moreover, our approach's 's effectiveness is relatively insensitive to variations in these hyppeaarameeerr values. As an illustration, even setting Pmaz oo does not significantly affect the reward achieved by our method, only resulting in an average 6.7% degradation. This finding indicates the robustness of our method, and further underscores its superiority over other approaches. What's 's more, from the sensitivity of our method to safety bound, we learn that although the reward performance of MAFOCOPS decreases with the stricter safety constraints, the algorithm's 's overall effectiveness remains unchanged across different safety levels.
the optimal values that we employed typically leads to favorable
6 Conclusion
In this paper, we introduce novel method for training multi-agent systems while incorporating safety constraints. Building upon the problem formulation and sequential update scheme established in the

---

MACPO framework (24], our algorithm offers rigorous theoretical guarantees and relies exclusively on first-order optimization techniques, thereby ensuring simplicity its implementation. Different from MACPO, which relies on second-order optimization to achieve parameterized policies, our work proposes a fundamentally different way to tackle the optimization problem, complemented by the comprehensive provision of derivatives. The empirical experiment results demonstrate the outstanding performance and computation efficiency of our algorithm, compared to the more intricate second-order method. To sum up, our paper offers novel and distinct contribution to the realm of safe multi-agent reinforcement learning, as evidenced by the distinctions in methodology, proofs, and experimental results in comparison with previous work.
Because the benchmarks we adopt only return one cost for agents, the performance of our algorithm across multiple costs is not evaluated. In the future, we plan to test our approach in more environments and physical settings. Moreover, there exist a number of promising prospects for future research such as incorporating off-policy data to further enhance the training efficiency. Designing methods aimed at offline settings, which precludes interactions with environments, represents another valuable direction for study.
Acknowledgments
This work is supported by National Key R&D Program of China under Contract 2022ZD01 19802 as well as National Natural Science Foundation of China under Contract 61836011, I. What's more, it is funded by Collective Intelligence & Collaboration Laboratory (Open Fund Project No. QXZ23014101) and by Young Elite Scientists Sponsorship Program by CAST 2022QNRC001. Besides, this work is also supported by GPU cluster built by MCC Lab of Information Science and Technology Institution, USTC, and the Supercomputing Center of the USTC.
References
[1] L. Busoniu, R. Babuska, and B. De Schutter, "A comprehensive survey of multiagent rein- forcement learning." IEEE Transactions on Systems, Man, and Cybernetics, vol. 38, no. 2, pp. 156-172. 2008.
[2] K. Tuyls and G. Weiss, "Multiagent learning: Basics, challenges, and prospects." " Al Magazine, vol. 33, no. 3, pp. 41-41, 2012.
[3] A. O. Al-Abbasi, A. Ghosh, and V. Aggarwal, "Deeppool: Distributed model-free freel-freeuue algorithm for ride-sharing using deep reinforcement learning," IEEE Transactions on Intelligent Transporta- tion Systems, vol. 20, no. 12, pp. 4714-4727, 2019.
[4] Y. Cao, W. Yu, W. Ren, and G. Chen, "An overview of recent progress in the study of distributed multi-agent coordination," IEEE Transactions on Industrial Informatics, vol. 9, no. 1, pp. 427-438, 2012.
[5] T. Wu, P. Zhou, K. Liu, Y. Yuan, X. Wang, H. Huang, and D. O. Wu, "Multi-agent deep reinforcement learning for urban traffic light control in vehicular networks," IEEE Transactions on Vehicular Technology, vol. 69, no. 8, pp. 8243-8256 2020.
[6] K. Zhang, Z. Yang, and T. Başar, "Decentralized multi-agent reinforcement learning with net- worked agents: recent advances." Frontiers of Information Technology & Electronic Engineering, vol. 22, no. 6, pp. 802-812 02-814,77 2021.
[7] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot et al., "Mastering the game of go with deep neural networks and tree search," Nature, vol. 529, 7587, pp. 484-489, 2016.
[8] Y. Yang, L. Yu, Y. Bai, J. Wang. W. Zhang. Y. Wen, and Y. Yu, "A study of ai population dynamics with million-agent reinforcement learning," arXiv preprint arXiv: (eee::179004111 2017.
[9] C. Berner, G. Brockman, B. Chan, V. Cheung, P. Debiak, C. Dennison, D. Farhi, Q. Fis- cher, S. Hashme, C. Hesse, R. J6zefowiez, S. Gray, C. Olsson, J. Pachocki, M. Petrov, H. P. de Oliveira Pinto, J. Raiman, T. Salimans, J. Schlatter, J. Schneider, S. Sidor, I. Sutskever,
10

---

J. Tang, F. Wolski, and S. Zhang, "Dota 2 with large scale deep reinforcement learning." arXiv preprint arXiv: 1rXiv:1912.06680, 2019.
[10] Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls et al., "Value-decomposition networks for cooperative multi- agent learning based on team reward." in International Conference on Autonomous Agents and MultiAgent Systems, 2018, pp. 2085-2087.
[11] T. Rashid, M. Samvelyan, C. Schroeder, G. Farquhar, J. Foerster, and S. Whiteson, "Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning." in Inter- national Conference on Machine Learning, 2018, pp. 4295-430K 4304.
[12] K. Son, D. Kim, W. J. Kang, D. E. Hostallero, and Y. Yi, "Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning." in International Conference on Machine Learning. 2019, pp. 5887-5896.
[13] Y. Yang, J. Hao, B. Liao, K. Shao, G. Chen, W. Liu, and H. Tang, "Qatten: A general framework for cooperative multiagent reinforcement learning." arXiv preprint (rXXi:2002.03932 2020.
[14] Wang, Ren, T. Liu, Y. Yu, and Zhang, "Qplex: Duplex dueling multi-agent q-learning." in International Conference on Learning Representations, 2021.
[15] R. Lowe, Y. Wu, A. Tamar, J. Harb, O. P. Abbeel, and I. Mordatch, "Multi-agent actor-critic for mixed cooperative-competiiiii environments," in Advances in Neural Information Processing Systems, vol. 30, 2017, pp. 6379-6390.
[16] Foerster, G. Farquhar, T. Afouras. N. Nardelli, and S. Whiteson, "Counterfactual multi-agent policy gradients," in AAAI Conference on Artificial Intelligence, vol. 32, no. 1, 2018.
[17] Y. Wang, B. Han, T. Wang, H. Dong, and C. Zhang, "Dop: Off-policy multi-agent decomposed policy gradients," in International Conference on Learning Representations, 2021.
[18] J. G. Kuba, R. Chen, M. Wen, Y. Wen, F. Sun, J. Wang, and Y. Yang, "Trust region policy optimisation in multi-agent reinforcement learning," in International Conference on Learning Representations, 2022.
[19] T. M. Moldovan and P. Abbeel, "Safe exploration in markov decision processes," in International Conference on Machine Learning, 2012, pp. 1451-1458.
[20] J. Achiam, D. Held, A. Tamar, and P. Abbeel, "Constrained policy optimization," in International Conference Machine Learning, 2017, pp. 22-31.
[21] A. Ray, Achiam, and D. Amodei, "Benchmarking safe exploration in deep reinforcement learning," arXiv preprint arXiv:1910.01700 vol. 7, no. 1, p. 2, 2019.
[22] Y. Zhang, Q. Vuong, and K. Ross, "First order constrained optimization in policy space," Advances in Neurul Information Processing Systems, vol. 33, pp. 15 338-155 349, 2020.
[23] T. Xu, Y. Liang, and G. Lan, "Crpo: A new approach for safe reinforcement learning with convergence guarantee," " in International Conference on Machine Learning, 2021, pp. 11 480- 11 491.
[24] S. Gu, J. G. Kuba, Y. Chen, Y. Du, L. Yang, A. Knoll, and Y. Yang. "Safe multi-agent reinforcement learning for multi-robot control," Artificial Intelligence, p. 103905, 2023.
[25] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané, "Concrete problems in ai safety," arXiv preprint 1606.066666 2016.
[26] S. Shalev-Shwartz, S. Shammah, and A. Shashua, "Safe, multi-agent, reinforcement learning for autonomous driving," arXiv preprint arXiv:1610.03295 2016.
[27] C. Liu, N. Geng, V. Aggarwal, T. Lan, Y. Yang, and M. Xu, "Cmix: Deep multi-agent rein- forcement learning with peak and average constraints," in Machine Learning and Knowledge Discovery in Databases, 2021, pp. 157-173.

---

[28] Lu, K. Zhang. T. Chen. T. Başar, and L. Horesh, "Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning," in AAAI Conference on Artificial Intelligence. vol. 35, no. 10, 2021, pp. 8767-8775.
[29] U. Bormann, L. Wang, A. D. Ames, and M. Egerstedt, "Control barrier certificates for safe swarm behavior," IFAC- Pape-sepesO,n,,ne, vol. 48, no. 27, pp. 68-76, 2015.
[30] Z. Qin, K. Zhang, Y. Chen, J. Chen, and C. Fan, "Learning safe aagti control with decentralized neural barrier certificates," arXiv preprint arXiv:2101.05436, 2021.
[31] W. Zhang, O. Bastani, and Kumar, "Mamps: Safe multi-agent reinforcement learning via model predictive shielding," arXiv preprint wrXiv:1910.12633 2019.
[32] J. L. Nazareth, "Conjugate gradient method," Wiley Interdiscipllnaary Reviews: Computational Statistics, vol. no. 3, pp. 348-353, 2009.
[33] B. D. Ziebart, A. L. Maas, J. A. Bagnell, A. K. Dey et al., "Maximum entropy inverse reinforce- ment learning." in Aaai, vol. 8. Chicago, IL. USA, 2008, pp- 1433-1438.
[34] J. Schulman, X. Chen, and P. Abbeel, "Equivalence between policy gradients and soft q-learning." arXiv preprint arXiv: 170.006440, 2017.
[35] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine, "Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor," in International Conference on Machine Learning, 2018, pp. 1861-1870.
[36] D. P. Bertsekas, Constrained optimization and Lagrange multiplier methods. 2014.
Academic press,
[37] Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, "High-diimensional continuous control using generalized advantage estimation," arXiv preprint arXiv:1506.02448. 2015.
[38] C. S. de Witt, B. Peng, P.-A. Kamienny, P. Torr, W. Böhmer, and S. Whiteson, "Deep multi- agent reinforcement learning for decentralized continuous cooperative control," arXiv preprint arXiv:2003.06709, vol. 19, 2020.
[39] V. Makoviychuk, L. Wawrzyniak, Y. Guo, M. Lu, K. Storey, M. Macklin, D. Hoeller, N. Rudin, A. Allshire, A. Handa et al., "Isaac gym: High performance gpu-based physics simulation for robot learning," " arXiv preprint arXiv:2108. 10470, 2021.
[40] Y. Chen, T. Wu, Wang, X. Feng, Jiang, Z. Lu, S. McAleer, H. Dong, S.-C. Zhu, and Y. Yang, "Towards human-level bimanual dexterous manipulation with reinforcement learning," Advances in Neural Information Processing Systems, vol. 35, pp. 5150-5163, 2022.
[41] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu, "The surprising effectiveness of ppo in cooperative multi-agent games," Advances in Neural Information Processing Systems, vol. 35, pp. 24 616 1-14 624, 2022.
[42] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, "Trust region policy optimization," in International conference on machine learning, 2015, pp. 1889-1897.
[43] I. Csiszár and Körner, Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, 2011.
[44] S. Boyd, S. P. Boyd, and L. Vandenberghe, Corvex optimization. Cambridge university press, 2004.
12

---

A Proof of the Optimization problem
According to the problem formulation, we give definition of the "surrogate" cost, which aligns with what is employed in MACPO (24]:
Definition, Let be joint policy, and म² be some other policy of agent i.Then for any of its costs of index j E 1,..., m', we define
T.j. (TT) Fo af [Aj (s,
In this way, consider л and म be joint policies, E N be an agent and E 1, m² be an index of one of its costs. From the proof of Theorem 1 in TRPO (42,, (in particular, equations (41) (45)), applying to joint policies π and म, we can conclude that
4a2rmazss, [A] (s,a'))
JJ(TT) S (T) + Eerp a~* (1,
(12)
(1-
where = DTVE (T; क) = max, DrV ( (-18), オ (-18)). According to the definition of total variance
divergence, defined by (pll)) = 1 Σ, PP: Ril. we can know that Drv(pllg) Drv (gllp).
Using Pinsker's incquality Drv Drv(pllo) (pllg)²
DeL(p 2
we can change the order of policy in the
divergence computation and obtain:
2 s. 14), (8, a')l
(J(T) S (TT + Ex-on an ( a')]
DRL ( nT).
(13)
(1-
It's to be noted that Earpx a~* [A} j.r (s, = F at other agents than do not change the value of the variable inside of the expectation. Fur- thermore, DRat (T) = max, max, (T(((s) (-1s)) = max, (Ein DxI( (-1s), s
( [At (s, (8, a')] as the actions of
Ei= mar, D (F n' (1(s)))) Ei= DRL (#', T'). Setting v) 2ymar, 14 (s.a'))
can finally obtain:
))(+)) S (T(+T + Jim +
DEL KL ( (T)
(14)
1=1
The aforementioned equation is similar to Lemma 2 in MACPO, with the only difference being the order of policies in the Kullback-Leibler (KL) divergence term. However, this variation does impact the subsequent derivations. To this end, we can establish the ultimate optimization problem
presented in our work follows:
marimize E
2h11 aahnothh [A (s,a"h a (s,
(15)
pompoo a alnn f1in11
s.I.Jgh (Tow)) + E Fampror a whawth (4 Jooo (s, x
Vj vi, ,
(16)
( =b.)) (00) 5
(17)
where DKI mha) A Eampao (1g (-1s), T8 (-1s))]
B Proof of Theorem 1
We first demonstrate the optimization problem to be solved when finding optimization problem within nonparameterized policy space:
marimize E
4h sompoon a fis Iad ish-1 atonthh 14th, (s.a stia-1 ,aa")
(18)
s.t.J." (Trw.) + E Eampror ana wo [4th J, (s, at c/h VjE,,.... m
(19)
D (T mbt <
(20)
Proof. We initiate our analysis by demonstrating the convexity of Problem 18 20 is convex w.E.t th Here we know that πe, and E+1 are given and 3 (TT..) remains constant w.E.t. thh In this
13

---

way, E
oe aa a w hi--1 s wttowii [A%, (s, aith 1, ,,a"h) )] and E Ex-pro at [4 Jimo, (s, a% ]] 41
are similar so that we only need to consider the latter one. We can divide this formula like this: Eg Ee-pre, ahh woth [A]. J. (s, = E. Proer (s) En TLM (a"x J,me, (8, (h) where Prea, (6) represents state visitation frequencies. We easily know that Pree, (s) is not affected by オ²h Similarly, for each action of agent in. the AliToL (s, is also not relative to n²" To this end, when Te, and g'T1A-1 are given, E Esp wath wort [A), J, (s,a") ) is convex to .² Applying these analysis, the convexity of Equation 18 and 19 can be confirmed. Concerning constraint 20 can be rewritten as E. PTor Ds) ( " 0g S 6. Notably, KL divergence is convex w.E.. its first argument, hence constraint 20 can be represented as a linear combination of convex functions, confirming its convexity as well. As neg fulfills constraint 19 and serves as interior point within the set defined by constraint 20] therefore Slater's 's constraint qualification holds and strong duality holds.
4+11
Based on above discussion, we can solve for the optimal value for the problem 18
20
p" by solving
the corresponding dual problem. We define 1// = =c J1h (TO,,) ), then
L(T,, v;) = 2,6 + vib + Es-omor [B IMTORT min-1 antn aehnathh [Aih, (8, a a ,a")
(21)
Uj -jEainnai (A) (8, >zD (1
Therefore,
p = max min [[T,, Uz.
= min mar L(T, vz) 25 Miy Ell
(22)
Niz Ell 20
where we invoked strong duality in the second equality. According to the theory of convex optimiza- tion 44, if π fxx Xj. uz are optimal for 22 nin* also optimal for Problem 18
Consider the inner maximization problem in 22 we can decompose this problem into separate problems, one for each s.
marimizell in with (E NM Rin
(A (s, afin-1, aa" }] - Uj AiA (s,
4
1041
(23)
Xy (als) loggzh (als))] Σ th (als) =
As E a -1 [A (s, atnin- ,aa is irrelevant to Th we rename this term as n (s, )
1111
for simplicity. This is clearly convex optimization problem which can be solved using a simple Lagrangian argument. We can then get
G(a Σ th (a)e) (s, ath) Vi mjimo, (s, (( logmz; (als)) + 5
S
(24)
where Ç is the Lagrange multiplier associated with the constraint Σ Th (als) 1. Differentiating G(TT) w.r. for some a:
aG
nito (s,a"") Uy A mii (s, X, ((logT"" logmtt (als)) +
(25)
O (a|s)
Set 25 to and similar to FOCOPS, we can know
x in* (als) = To
T0 (als)
(x),0()) expl (Mmog (s, - A. (s, ))}
(26)
where Zay.z (s) is the partition function that ensures xin* to be probability function, iee.
E. iha (alss) 1. Putting this nr" back into equation 22 we can get
p" min 21o + 136 + Eanpaon aonnmin mnte, (s, (s,ath) 12 viAti (s,a' "((logr"""0dd logT (als))]
min 2,0 + b,b + Eampaon wo (nth (s, aha - 1/ A m. (s,a")) Ay(1ogT in (als) log A
(MATo, (s, atm)- Ui mj, (x, log (als))]
= min 2,0 + vzble + ->gErppTo athwiin [log (s) Ar,050
14

---

What's more, we give a simple description to show that for feasible policy TØ,, the optimal policy update x/a* has upper bound for worst-case guarantee for cost constraint satisfaction. For agent in. according to Equation [4| after getting the optimal joint update policy for all agents, (j(T*) S (TT + Li (*****++ +. >i= DRL"(T"* mb.) can be obtained. According to the definition of 1g (T') and the constraint 16 in the optimization problem, we can know that (TT.)) + I.j, me (17h*)) S cjh,, thus leading to JJ(TT) I C + =ujt Σi=1 DRL (1'", = In addition, can know that the kl divergence between update policy and To, for each agent / has an Σi= 8'
upper bound, which we call 8², To this end, we achieve JJ((=) S ch 2ymaz Jymaz,.cl49 ...
(1-2)²
which is the upper bound for worst-case guarantee for cost constraint satisfaction. According to the result, we know that with agents, the upper bound for worst-case guarantee is higher, which means that optimization for more agents is more challenging, consistent with our intuition.
C Proof of Corollary 1
Corollary 1. The gradient of L(f) takes the form
VoL(O) Esriron
VoDxL (1
(27)
where
Vong (als)
ToDki(Tj" || [>>)> = VoDKL(TT" (1 amito
E Aj
(77O,
jito, (s,a ))
Tea (als)
(28)
Proof.
Using the definition of KI. divergence, we note that
DKL(TT in [| = -
To in (als)logm in* (als)+ (als)) Σ
T in
(als)logmz (als) = H(mb" n i/
[>]] [>] H [s]
(29)
where (TT [s] is the entropy and H x [s] is the cross-entropy. We expand the cross-entropy term which gives us:
H HTT 2h n dn* [s] - Σ ts (als)logr"" (als)
TH (a|s)
Σ n (als) log(
expt X; (Nror v. (s)))
Σ Tt (a|s) log (a|s) + 1og Log (s)
Σ X,
1
T is (als) (NTo, (s, 1 1y (s,a²h)
Then put this term back into Equatior29
DEL (r/" [[<]
Σ mo (a|s) logm (a|s) + Σ 78" (al (loggh) (als) + log Zxgiuss (s)
Th in (als) (Noro (5,
Uj 1y Alt (s,a²
T (a|s)
( (
+ Zo (s) X,
E amitth th in
(1 -
Uj uiAlito, (s,
th T0 (a|s)
In this way, take the gradient on both sides and we can get:
VOny (als) Fan The (als)
VoDKL 1[""" = VoDKL( [| Ai
E
(170,
(s, (s,a")))
(30)
15

---

D Proof of Corollary 2
Corollary 2. The derivative of L Uz) wet By is
aL(T'M* ,,,,,,,,,,, Vz) b3. E Esmpro aa a't Sighnwtt (als) (s,at*
(31)
Ovy
Proof. From the definition of L( , Ajs (z) and above discussion, we can know that
L( Uz) = min A,,9,20
250 + 1z AgFa s athwrrh (logZxy.en (*)
(32)
The first two terms is an affine function for vs we focus on the expectation in the last term.
@m (als)
To (als)
deapl 1 x, (MiTo (8, - Uy V3A (8, ath )))
(2gsos (8)
Rzy,oy (5)
du3
abyy,u, (5)
expl
(TTO (s, - vy (s, (3)aa))))
X,
dv,
For simplicity, we record eapl x (Niro (t, UsAliTTO (8, (8, as e(x), so n xhh((aa)) (als)
Tep (alo)
th
e(x).. In this way.
(x) (0)
On In (als)
Te in (als)
A A0t0 (8,
(A), e(xx) 8Z,, )Zy,,e1 (8)
du,
My (8)
(33)
A mog
(8, (8,
Glog Z,,, T, (8)
(al()
2tn (als)
X
au,
Therefore, the derivative of the expectation in the last term of L(xih* ,z) can be written as:
i n xhh((ll))
E Poo alhwarth [logZr,
(s)] F
Bampoo :atn #k
Ov, Toe (als) log T,,,,, (s))
iv;
in
1
Dr'''' (als)
Glog Z,, 2y Us (s)
F sumpon
Pay (6) + mmnn((as)) (a|s) log 7
(als)
Ou;
(als)
Ajimo, (s,
Olog us (5) log ZrogZ (s) +
Glog Zx, (5)
E campee
log TogZZ (s)
a a'hoot H4
TB (a|s)
Aj
dv,
Ov.
A'a jo
(8, 5h
Blog (5) log 2 Zyy (3)) + Blog (5) Ou,
-E chhor'
log LogZsy.u (5 (s)
Xj
Ou,
In addition, according to the definition of Zrg.os. we can get:
07),w1(())
in (a (als)ezz sssppp T
(Nro, (s,0th - V. (s, )1
Ov,
ov,
A'h J,
(s,
A Alimon (s, TØe (als) c(x) (x),)>)))))) (s)
Σ
thh (als)
X/ -(x)==) Σ
Zxy,e( (s)
1 j.
(8,
n (an)(als) (ala()/))).) (x).
Zrgez (5)
Eithwris (A mo (s, (s,a"))))
Aj
What's more
Blog (s)
0Zyy,,,
1 Eahnnat [A)TTO, (s,
(34)
Ov, Ov:
Zxyius (s)
Ag
16

---

Putting this result to above equation, we can get
Eampeo a'haatt [log 2,,,,, (s)]
0u,
A m -Ex-pro atwww' (a|s]]
(s, logZsg.n (s) + Alitor (s,
Ajimos (s,
log ,,,,, (8)
Xj
1
ESMPTo alh hooth (ale) (al)) (s, a.
)j To sum up, the derivative of My to function L(T Uz) can be written:
aL(T'" )3. byr Es-prn ott with (als) LA), Ji (5,
(35)
Ovj
where 1/ = ccg- - -Jpx (Te)). this way, we can update Uy by Uj +- proju, |1s - -a(ch- (TTw)))
E Procedure of MAFOCOPS
In this section, describe the procedure of our algorithm, outlined in Algorithm hyperparameters for each agent are identical throughout the algorithm.
To be noted,
Algorithm 1 MAFOCOPS
Require:
number of agents n, number of updates K, minibatch size B, temperature { ssimm initial cost constraint parameter {リy Wrsismmm' cost constraint parameter bound Umazz learning rate for cost constraint parameter dy,, trust region bound 8, cost bound 6, Initialize, policy networks { i E WV,, global value network { and cost value networks (0).0015)smi' replay buffer
1:
2: for = 0, I,... do
T save the data into the buffer and sample batch of data; 4: Estimate the C-returs Je by averaging over the cost return for all episodes.
3: Generate trajectories
5: Compute the advantage functions Ame, (s,a) and A j.m (8, a²) using GAE;
6: Draw a permutation iim of agents at random.
7:
Set M (s, a) = Amo, (s,a)
8:
for agent Ln = i1, 22,
in do Update vy by // by Vy + proju, |/3 - alc, -
9:
C (Tor 1)1.j = -,.... m
10:
for K epochs do
for each minibatch data of size B do
12:
Update value networks (and cost value networks analogously) by minimizing the MSE 22 where ft is the target return.
loss Φk+1 argmin& Eto Update policy network by the derived equation of VoL (Eq. 11. where îireg (s, a'h)
is estimated by Mi (s.
14:
end for
15:
DxL(TT Break end
" ( 2 then
16:
17:
18:
end for
* (a'alo'k)
19:
Compute Mi (8,
Mbaa (s, unless ht
2h (ata)or))
20:
end for
21:
end for
Experiment Environment Introduction
In this section, we introduce the environments that we adopt in the experiments.
17

---

TI/Z
(a)
(b)
(c)
Figure 5: Specific tasks in Safe MAMuloCo. (a): Ant Task: Ant 4x2 with three folding Jagged (30%) line walls, (b): HalfCheetah Task: HalfCheetah 2x3 with the moving obstacles, (c): ManyAgent Ant Task: ManyAgent Ant 2x3 inside one folding line walls (corridor width is 9 m).
F.1 Safe MAMuJoCo
This environment is an extension of MAMuJoCo 38) maintaining the background environment, agents, physics simulator, and reward function. However, the Safe MAMuloCo setting, additional obstacles such as walls or pitfalls are introduced, and the environment emits cost with the increasing risk of an agent stumbling upon an obstacle. Here, we mainly introduce the scenarios that we employ in our work and present them in Figure
Many Aget Ant task & Ant task The corridor in the environment is bounded by two walls, with a width of 9 m for ManyAgem Ant and 10 m for Ant. The environment emits the cost of I for an agent, if the distance between the robot and the wall is less than 1.8 m, or when the robot topples over, which can be described as
1, 0.2 S 2torso,t41 S 1.0, Frot > 0.7, Storso,t+1 Ewaull 112 2 1.8
Ct =
O, otherwise
(36)
where Ztorso,t+1 and 1torso,t+1 is the robot's torso's z-coordinate and mndd-ooo x-coordinate at time t + 1, Prot the robot's rotation's 's z-coordinate and Twall denotes the x-coordinate of the wall.
HalfCheetah task In these maps, the HalfCheetah agents move inside a corridor (which constraints their movement, but does not induce costs). Concurrently, there are pitfalls within the corridor that also move. When an agent is too close to a pitfall, specifically when the distance between an agent and pitfall less than m, a cost of will be emitted.
{
1, ytorso,t+1 Yobstacte | 2
c
-
0,
otherwise
(37)
where the y-coordinate of the robot's torso is represented by ytorso, and yobstacle denotes the y-coordinate of the moving obstacles.
F.2 Safe Multi-Agent Isaac Gym
This environment builds upon Issac Gym platform (3)] renowned for its GPU-accelerated capabili- ties, and leverages the powerful Nvidia PhysX engine. Extending from the existing framework of HanterousHands (40), Safe MAIG requires agents control the robot hands while optimizing both the reward and safety performance. Similarly, we also give an introduction of the specific scenarios in our experimental evaluations.
ShadowHandOver This task revolves around dual-hand setup, with each hand occupying fixed position. The primary objective entails the first hand, holding object, navigating suitable trajectory to transfer the item to the second hand while the second hand aims to acquire a successful grasp of the object. To be noted, this task incorporates safety constraints pertaining to the range of motion one of the fingers on the first hand. Formally, the cost function can be expressed as follows:
c: (
1, b. {
||Fa4.411l= 2 0.1
(38)
otherwise
where Fat.411 1 is the first hand's ' fourth fingers's motion degree.
18

---

ShadowHand Within the context of this task, both hands are equipped with two items. The fundamental objective for the agents is to execute rotational movements between these two items around each other and the safety constraints remain the same as Equation 38
Ant 244
And 2o4d
Art 4x2
Avt
Figure 6: Performance comparisons on tasks of Ant 2x4, 2x4d, 4x2 and 8x1. The safety bound is 50, except for Ant 8x1 whose cost threshold is set as 70. The solid line shows the median performance across 5 seeds and the shaded areas correspond to the 25-75% percentiles.
G Performance on Safe MAMuJoCo
In this section, we present the comprehensive results of experiments in Safe MAMuloCo environment in Figure 6 It can be observed that our proposed MAFOCOPS consistently demonstrates superior overall performance across all tasks. Even when our method achieves similar performance compared to the other two algorithms the advantages of our approach. As is discussed in the Experiment section, MAPPO-L algorithm always achieves the similar performance as MAPPO, except in HalfChectah scenarios where the cost threshold is significantly smaller compared to cost achieved by HAPPO and MAPPO. This may be due to that MAPPO- Lagraniannn being built upon Lagrangian multiplier combined with standard MARL algorithms, leading to performance more similar to safety-unaware MARL algorithms. Regarding the other two hard constraint algorithm, their performance would degrade with the increasing number of agents. However, MAFOCOPS consistently outperforms MACPO, proving the effectiveness of our method. What's 's more, we provide additional videos of the trained policies of both our algorithm and MACPO in supplementary materials.
HalfCheetah scenarios, still exhibits faster learning, demonstrating
2x3
HaltCheetah
HaltCheetah
meppe
20.2
luguos
marzzs
HaltChoetah
HatCheetah
HaltCheotah Exx1
2004 1o0
1004
Figure 7: Performance comparisons on tasks of HalfCheetah 2x3, 3x2 and 6. The safety bound is 30. The solid line shows the median performance across 5 seeds and the shaded areas correspond to the 25-75% percentiles.
19

---

ManyAgent Ant 2x3
ManyAgent Ant 3x2
ManyAgent Ant 6x1
Bestagg
Rediromment slepe (etllion)
Enarrnmment (elllion)
ManyAgent Ant 2xc
Manyygant Art 3x2
ManyAgant Art tx11
2004
Figure 8: Performance comparisons on tasks of Many Ant 2x3, 3x2 and 6x1. The safety bound is 25. The solid line shows the median performance across 5 seeds and the shaded areas correspond to the 25-75% percentiles.
Many/Agentt Ant
ManyAgeet
ManyAgent Ant 8k1
100
Enappo
5004
Meroee Gbbate Coal
poun
ManrAgent
Manrygeent Aust dock
ManyyAgent
AN Galoodk Thaaee
Figure 9: Performance comparisons on tasks of ManyAgent Ant 2x4, 4x2 and 8x1. The safety bound 80. The solid line shows the median performance across seeds and the shaded areas correspond to the 25-75% percentiles.
H Efficiency Analysis
In this section, we evaluate the training efficiency, which is measured by frame per second (FPS), and the memory cost between MACPO and our MAFOCOPS. To be specific, we record the time and samples spent for each update to calculate average FPS and employ memory monitor tools to track memory utilization after 200000 samples. To ensure fair comparison, both algorithms are executed on the same GPU device, thereby minimizing the influence of other variables. The results obtained from these evaluations places. Based on the obtained results, it is evident that an increase in the number of agents leads to noticeable escalation in computational cost for MACPO. Whereas, our algorithm showcases substantial improvement in computational efficiency and demonstrates the ability to effectively conserve memory resources, especially in scenarios involving larger number of agents.
presented in Table [ and Table 2 with precision of two decimal
I Sensitivity Analysis
We test the sensitivity of our algorithm to hyperparameters, ie.,, Xj and Mmnan as well as the safety bound. To be noted, because the benchmarks that we adopt only involve single cost, we only need to set one value for Ay and Pmag. In future works, may explore the performance of our method in
20

---

Scenarios
Ant Task
HaltCheetah Task
Config
2x4d
2x4
4x2
8x1
2x3
3x2
6x
FPS
MACPO
231
218
130
73
298
192
106
MAFOCOPS
322
270
160
115
340
229
162
Improvement($)
39.39
23.85
23.08
57.53
14.09
19.27
52.83
Scenarios
ManyAgen Ant Task
Config
2x3
3x2
6x1
2x4
4x2
8x1
FPS
MACPO
244
167
98
233
135
73
MAFOCOPS
271
249
149
253
193
115
Improvement($))
11.07
49.10
52.04
9.05
42.96
57.53
Table 1: Average FPS between MACPO and MAFOCOPS and the bold results demonstrate the improvement brings by our algorithm.
Scenarios
Ant Task
HalfCheeath Taks
Config
2x4d
2x4
4x2
8x1
2x3
6x
Memory (MiB)
MACPO
18.85
23.60
31.24
66.25
16.54
30.20
52.08
MAFOCOPS
18.97
21.82
24.23
56.99
19.34
27.26
39.15
Saved Memory
-0.12
1.77
7.01
9.26
-2.80
2.93
12.93
Scenarios
ManyAgent Ant Task
Config
2x3
3x2
6x1
2x4
8x1
Memory (MiB)
MACPO
25.32
32.64
55.27
27.31
38.90
65.02
MAFOCOPS
24.45
30.88
44.38
24.62
34.73
60.71
Saved Memory
0.87
1.76
10.89
2.69
4.17
4.31
Table Memory cost of MACPO and MAFOCOPS and the bold results demonstrate the memory saved by our algorithm.
environments with multiple costs. We choose several scenarios in Safe MAMuJoCo to conduct the ablation studies.
The sensitivity to the hyperparameters is evaluated across several different values for X, and Umaz while keeping all other parameters fixed. For ease of comparison, the return and cost achieved by [18), namely if our method yields a return of z and HAPPO achieves y' The results report the final performance of the models after training for 10 million steps and are showcased in Table 3 and Table 4 with a precision of three decimal places. Given the complexity inherent in multi-agent environments, it is difficult to delineate the correlation between the performance of our method and the hyperparameters X and Vman. It can be observed that different scenarios have different sensitivity these hyperparameters from the results. Overall, the reward achieved under different settings relatively insensitive as even setting these parameters across broad range only leads to an average degradation of less than 10%. On the other hand, the cost may be more sensitive these parameters, highlighting the inherent challenges in ensuring safety guarantees in safe multi-agent reinforeement learning some degree.
normalized the results based
return of y. the normalized result reported as 2
Furthermore, select some maps to examine the sensitivity of our algorithm the safety bound. To be mentioned, hyperparameters in this experiment remain unchanged as the main experiments. From the results depicted in Figure I0, we can see that setting the safety bound too high could lead to increased oscillations in cost performance, although it may yield better reward performance. This observation is reasonable since higher safety bounds may allow agents to explore actions with potentially higher returns but less safety. If the safety bound is low enough, the agents will take actions that are definitely safe, leading less vibration. Whereas, from a global perspective, the effectiveness of algorithm remains consistent across these different safety levels. In general,
21

---

Ant 2x4
HalfCheetah 2x3
ManyAgent Ant 2x3
ManyAgent Ant 2x4
All envs
Reward
Cost
Reward
Cust
Reward
Cost
Reward
Cost
Reward
Cost
0.913
0.212
0.599
0.049
0.889
0.137
0.781
0.082
0.796
0.120
0.975
0.188
0.658
0.056
0.946
0.131
0.882
0.212
0.865
0.147
2.2
0.964
0.091
0.668
0.049
0.947
0.090
0.802
0.166
0.845
0.099
0.983
0.183
0.699
0.073
0.958
0.059
0.879
0.178
0.880
0.123
1.004
0.113
0.694
0.078
0.871
0.070
0.784
0.267
0.838
0.132
Table 3:
Performance of MAFOCOPS for different and the "all envs" column presents the averaged
performance across these four scenarios.
Ant 2x4
Ant 2x4d
Ant 4x2
Avtrage Eptose Ouel
Wewene Menaie Sghodd Cral
Epkoid
Ervironmeent steps (uéliion)
Ervironment steps (peilionn)
Enviromment steps teailion)
Ant 2x4
Ant 2x4d
Ant 4xc2
Aetragge Ealoste Sowward
Metraage Epioode Reward
2002
2003
5002
1003
Ereinrmennt steps (eeilion]
Ervironment steps Ordilion
Enstromment stapo (mvillir))
staps (millinn)
Figure 10: Performance comparisons Ant 2x4, 2x4d, 4x2 with different safety bound.
need to strike a balance between ensuring safety and achieving a good reward performance when applying safe RI. algorithms.
Ant 2x4
HalfCheetah
2x3
Many Agent Ant 2x3
ManyAgent Ant 2x4
All cnvs
Umar
Reward
Cost
Reward
Cost
Reward
Cost
Reward
Cost
Reward
Cost
1.042
0.074
0.680
0.029
0.981
0.067
0.859
0.328
0.891
0.125
0.964
0.091
0.668
0.049
0.947
0.090
0.802
0.166
0.845
0.099
0.908
0.222
0.627
0.040
0.962
0.137
0.910
0.206
0.852
0.151
0.923
0.097
0.579
0.042
0.936
0.077
0.844
0.123
0.821
0.085
0.793
0.175
0.606
0.063
1.013
0.102
0.800
0.256
0.803
0.149
0.873
0,209
0,588
0.048
0.959
0.100
0.749
0,146
0.792
0.126
Table 4:
Performance of MAFOCOPS for different Pmaar and the "all envs" column presents the averaged performance across these four scenarios.
Details of Settings for Experiments
The majority of settings have been described in detail in the Experiments section; however, we provide some additional information here. As our implementation is based on the codebase provided by MACPO (24), and thus most hyperparameters remain consistent with their original values. For MAFOCOPS, the Lagrange multipliers, namely and Vmax, we utilize are 2.2 and 1.3, respectively, which can found in Table 3 and For the other two safe MARL algorithms, MACPO and MAPPÒ-
I., we modify the relevant hyperparameters to ensure their compatibility with the safety bound As mentioned in the Experiments section, for the two benchmarks, adopt distinct hyperparameters
22

---

for MAPPO-L in different categories of tasks, as the safety bound is relative to the cost achieved by standard MARL algorithms. However, MAFOCOPS and MACPO both use unchanged parameters. indicating the robustness of these two methods. We present the specific hyperparameters that we use our experiments in Table (as most parameters are unchanged, we only report the changed ones or unique parameters in our algorithm).
Safe MAMuJoCo
MACPO
MAPPO-L
MAFOCOPS
kl-threshold
0.008
0.0125
lambda lagr
[0.38", 0.46", 0.59%, 0.52
/
/
2.2
Vmaa Ir
1.3
0.00005
fraction coef
0.3
/ 256
minibatch size
update numbers
5
Safe MAIG
MACPO
MAPPO-L
MAFOCOPS
kl-threshold lambda lagr
0.009
0.01
[0.14%. 0.68*]
/
lagrangian coef rate
/
[le 7 9e 7
/
2
Vmna 1 Ir fraction coef minibatch size
1.4
0.001
0.26
8192
update numbers
3
Table 5: Different hyperparameters used for MACPO, MAPPO-L and MAFOCOPS. As MAPPO-L employs different hyperparameters, the changed ones are represented in the list. In Safe MAMuJoCo domains, means Ant tasks, b corresponds to HalfCheetah tasks, represents ManyAgent Ant 2x3 tasks and represents denotes ManyAgent Ant 2x4 tasks. Safe MAIG domains, represents ShadowHandOver task and b denotes ShadowHHandReOrienaatoo task.
23


Reviews:
[{"review_id": "VT4LqJnuaW", "reviewer": "Reviewer_DYiL", "summary": "The paper proposes a new method called first-order constraint optimization in multi-agent policy space (MAFOCOPS), which solves constraint optimization problems in a non-parametric policy space and then projects the updated policy back into the parametric policy space to achieve feasible strategies that meet safety constraints. Experimental results show that the proposed method has achieved remarkable performance while satisfying safe constraints on multiple safe MARL benchmarks.\n", "questions": "1. How can we select the best hyperparameter values for a new environment which hasn’t been met before, is there any search method like grid search or multi-arm bandit?\n\n2. Is it possible to introduce more baseline algorithms for comparison?\n\n3. I didn’t see a detailed explanation of whether MAFOCOPS uses Monte Carlo return or bootstrap return in the Safe-Multi-Agent-Isaac-Gym in the paper. I am curious if this factor will have a significant impact on the results. If possible, please provide experimental results using these different target returns.\n", "limitations": "The penultimate section of the paper contains a discussion of the main limitations. The method itself should not have a direct negative outcome. However, note that in practical applications they could occur. Some examples and ways to address them could be discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a new method called Multi-Agent First Order Constrained Optimization in Policy Space (MAFOCOPS) to address the challenge of developing safety-aware methods for multi-agent reinforcement learning (MARL). The proposed approach solves the constrained optimization problem in a non-parametric policy space and then projects the updated policy back into a parametric policy space, ensuring feasible policies that satisfy safety constraints. \n\nThe MAFOCOPS method has first-order characteristics, making it relatively easy to implement compared to more complex optimization methods. Additionally, it provides an approximate upper bound for constraint violations in worst-case scenarios. Experimental results demonstrate that the MAFOCOPS method achieves significant performance improvements in multiple safety MARL benchmarks while simultaneously satisfying safety constraints. This indicates that the proposed approach effectively balances performance and safety considerations. Unlike existing safety MARL methods that are often tailored to specific tasks or rely on specific assumptions and techniques, the MAFOCOPS method is designed to be applicable to a wide range of multi-agent systems and tasks. This generalizability enhances the practicality and versatility of the proposed approach.\n", "weaknesses": "The performance of the method is sensitive to certain hyperparameters, such as the Lagrange multipliers and the safety bound. While the paper claims that the method is relatively insensitive to variations in these hyperparameter values, it would be helpful to provide a more detailed analysis of the sensitivity and its impact on performance. \n\nThe paper does not provide information on the implementation details of the proposed method, such as the specific algorithms used for policy optimization or the computational complexity of the method. Providing these details would help in assessing the practical feasibility and efficiency of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Q1*:The performance of the method is sensitive to certain hyperparameters, such as the Lagrange multipliers and the safety bound. While the paper claims that the method is relatively insensitive to variations in these hyperparameter values, it would be helpful to provide a more detailed analysis of the sensitivity and its impact on performance.\n\n*A1*:Due to the page limit, the results of our sensitivity analysis is presented in the appendix. Considering the complexity of multi-agent environments, establishing a precise correlation between the performance of our algorithm the Lagrange multipliers $\\lambda_j$ and $\\nu_{max}$ is difficult. It can be observed that different scenarios have different sensitivity to these hyperparameters from the results. Overall, the reward achieved under different settings is relatively insensitive as even setting these parameters across a broad range only leads to an average degradation of less than 10\\%. On the other hand, the cost may be more sensitive to these parameters,  highlighting the inherent challenges in ensuring safety guarantees in safe multi-agent reinforcement learning to some degree.\n\nAs for the safety bound, we can see that setting it too high could lead to increased oscillations in cost performance, although it may yield better reward performance. This observation is reasonable since higher safety bounds may allow agents to explore actions with potentially higher returns but less safety. If the safety bound is low enough, the agents will take actions that are definitely safe, leading to less vibration. Whereas, from a global perspective, the effectiveness of our algorithm remains consistent across these different safety levels. In general, we need to strike a balance between ensuring safety and achieving a good reward performance when applying the method.\n\n*Q2*:The paper does not provide information on the implementation details of the proposed method, such as the specific algorithms used for policy optimization or the computational complexity of the method. Providing these details would help in assessing the practical feasibility and efficiency of the proposed approach.\n\n*A2*:Thank you for your advice and we will provide more analysis in future revision. In fact, we introduce some details about our algorithms in Section 4.3 and specific algorithms in the appendix. Here we also introduce some basic information for convenience. For the training process, after initialising the needed parameters and networks, we can utilize the models to generate data and then estimate the advantages. Then the update of $\\nu_j$ is performed using Equation (10) in the manuscript. After that, we can update the value networks using Mean Square Error loss and update policy networks using the equations of $\\nabla_\\theta L(\\theta)$, which is expressed in Equation (11). During the training, our algorithm also employs the early stopping criterion to ensure that the updated policy satisfies the trust region constraint. In addition, the computational complexity of our algorithm is $\\mathcal{O}$$(NKMHP)$, where $N$ denotes the number of agents, $K$ denotes the number of update times in every epoch, $M$ denotes the number of training steps, $H$ denotes the number of constraints and $P$ denotes the number of parameters.\n\n*Q3*: How can we select the best hyperparameter values for a new environment which hasn't been met before, is there any search method like grid search or multi-arm bandit?\n\n*A3*: In our work, when we conduct the experiments in a new environment, we use grid search to select the hyperparameters, which is a commonly used method for hyperparameter tuning.\n\n*Q4*: Is it possible to introduce more baseline algorithms for comparison?\n\n*A4*: As we mentioned in our work, the realm of safe multi-agent reinforcement learning is a nascent area of research and there are limited related works available. What's more, most current algorithms have certain limitations or are tailed for robotics tasks, whose settings are very different from our work. In this way, we choose to adopt the state-of-the-art (SOTA) algorithms in this field, namely MACPO and MAPPO-Lagrangian [1], as the baseline algorithms, which are published in the well-known journal, Artificial Intelligence. We think that the comparison with these two baseline methods are convincing to prove the effectiveness of our algorithm.\n\n*Q5*: I didn't see a detailed explanation of whether MAFOCOPS uses Monte Carlo return or bootstrap return in the Safe-Multi-Agent-Isaac-Gym in the paper. I am curious if this factor will have a significant impact on the results. If possible, please provide experimental results using these different target returns.\n\n*A5*: Thank you for your advice. In fact, as is mentioned in our work, we use Generalized Advantage Estimator (GAE) [2] to estimate the advantages. As Monte Carlo return is known to have low bias but high variance while bootstrap return has low variance but high bias, GAE is a method that can achieve a balance, making it be widely adopted to estimate return in policy-based methods. Considering that the baseline algorithms both use this method for advantages estimation, we also utilize it based on its effectiveness and compatibility with our approach. As the hyperparameters of GAE remain the same across our experiments, we believe that the superior performance of our approach is sufficient evidence of its effectiveness.\n\n[1]  S. Gu, J. G. Kuba, Y. Chen, Y. Du, L. Yang, A. Knoll, and Y. Yang, “Safe multi-agent reinforcement learning for multi-robot control,” Artificial Intelligence, p. 103905, 2023.\n[2]  J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, “High-dimensional continuous control using generalized advantage estimation,” arXiv preprint arXiv:1506.02438, 2015.\n    "}, {"review_id": "AKX5dZA8V8", "reviewer": "Reviewer_fTdt", "summary": "The paper builds over previous work (1) to construct a safe policy optimization algorithm based on first-order methods. It shows empirical improvement over some baselines.", "questions": "I don't have questions", "limitations": "I didn't find any section where the limitations of the proposed method were addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "\n# quality \n\nThe quality of this work is fairly satisfactory, as all the needed theory is introduced and a practical counterpart is proposed.\n\n# clarity\n\nThe exposition is clear\n\n\n\n", "weaknesses": "# originality\nThe work seems not to be much original since it consists of a fair extension of a previously cited paper.\n\n# significance\n\nI might say that the work does not seem significant enough compared to related works. For instance, one positive fact referred to in the abstract (upper bound violation) is a direct property of using the previous algorithm with an additional constraint.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Q1*: The work seems not to be much original since it consists of a fair extension of a previously cited paper.\n\n*A1*: We believe our work is not merely an extension of a previously cited paper, which we think you refer to MACPO. As is discussed in the paper, although MACPO offers an impressive solution for safe multi-agent reinforcement learning, it does owns some limitations. For example, achieving parameterized policies involves second order optimization, resulting in complex computation and implementations. Furthermore, the approximation during the optimization process will bring nonnegligible approximation error, necessitating additional steps during each update in the training process to recover from constraint violations. In contrast, our work proposes a fundamentally different way to tackle the optimization problem, where we provide full derivatives. We design a two-step approach to solve the optimization problem and prove that we can successfully employ first order method for the optimization. This significant departure from MACPO's methodology sets our work apart from the previously cited paper.\nTo reinforce the distinctiveness of our contribution, we conduct extensive experiments to compare our algorithm with MACPO, from the performance to the computing efficiency. The results from these experiments also highlight the outstanding performance of our algorithm. To sum up, we think our work offers a novel and distinct contribution to the field of safe multi-agent reinforcement learning, as evidenced by the differences in methodology, proofs, and experimental results when compared to the previously cited paper.\n\n*Q2*: I might say that the work does not seem significant enough compared to related works. For instance, one positive fact referred to in the abstract (upper bound violation) is a direct property of using the previous algorithm with an additional constraint.\n\n*A2*: As is introduced in our work, safe multi-agent reinforcement learning holds vital significance as many applications often require the agents to refrain from taking certain actions or visiting particular states in real world. Among related research, MACPO achieves the state-of-the-art performance. But compared to this second-order method, our work not only achieves superior performance but also improve the computation efficiency, with rigorous theoretical guarantees and relying exclusively on first-order optimization techniques. These advantages are crucial, particularly when dealing with large state/action spaces and complex scenarios. Regarding the mentioned upper bound violation, it serves as an important security guarantee in safe reinforcement learning, ensuring the degree of constraint violation can be controlled within a certain range even in  worst-case scenarios. It should be noted that this property is not a direct consequence of using an additional constraint as the addition of such a constraint could also lead to potential violations. Taking MAPPO-Lagrangian as an example, as a soft constraint algorithm, whether this algorithm satisfies any worst-case constraint guarantees remains  unknown. The empirical results in Safe Multi-Agent-Isaac-Gym obviously shows that it exhibits a delay in guaranteeing safety and even a sudden drop in performance when enforcing the safety constraint. This indicates that the property of upper bound violation is important, which also demonstrating the significance of our work.\n\nFinally, thank you again for your comments. If some of your concerns are addressed, you could consider raising the rating. This is very important for us and we will appreciate it very much."}, {"review_id": "fTLFiu6e8q", "reviewer": "Reviewer_eMiG", "summary": "This paper proposes a first-order method to solve the safety-constrained multi-agent policy optimization problem. The method is evaluated on two benchmarks and shows better performance over the baselines.", "questions": "- Please see the above *Weakness* section.", "limitations": "- The correctness of the proposed method seems skeptical. Several important steps in the derivation are confusing or taken as granted without sufficient argument. ", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The studied problem is important and might interest the community.\n-  The writing is easy to follow.", "weaknesses": "- My main concern is about the correctness of the derivation in the proposed method. The proof of *Throrem 1* says both *Equation (7)*, the objective and *Equation (8)*, the cost constraint, are **linear** *w.r.t.* $\\pi^{i_h}$, which looks strange to me. The equations involve advantage estimation which definitely has a non-linear relationship with $\\pi^{i_h}$. Why would it be linear?\n\n\n- When solving the optimization problem, in *Corollary 2*, the expectation of the advantage over the optimal policy $\\pi^{i_h\\ast}$ is assumed to be zero. The advantage means the performance improvement of the optimal policy. How can it be reasonable to assume it to be zero? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Q1*: My main concern is about the correctness of the derivation in the proposed method. The proof of Theorem 1 says both Equation (7), the objective and Equation (8), the cost constraint, are linear w.r.t. $\\pi^{i_h}$, which looks strange to me. The equations involve advantage estimation which definitely has a non-linear relationship with  $\\pi^{i_h}$. Why would it be linear?\n\n*A1*: We apologize for the confusion caused by the incorrect description in the proof of Theorem 1. As the policy for an agent is actually a distribution, it may be inappropriate to say the objective (Eq.7)and cost constraint (Eq.8) are linear w.r.t. $\\pi^{i_h}$. We appreciate your attention to this matter. In fact, the core intention is to demonstrate that the Problem (7) and (8) are convex. Here, because $\\boldsymbol{\\pi_{\\theta_k}}$ and $\\theta_{k+1}^{i_{1:h-1}}$ are given, $E_{s \\sim \\rho_{\\boldsymbol{\\pi_{\\theta_k}}},a^{i_{1:h-1}}\\sim \\pi_{\\theta_{k+1}}^{i_{1:h-1}},a^{i_h}\\sim \\pi^{}i_h}[A_{\\boldsymbol{\\pi_{\\theta_k}}}^{i_h}(s, a^{i_{1:h-1}}, a^{i_h})]$ is similar to $E_{s \\sim \\rho_{\\boldsymbol{\\pi_{\\theta_k}}},a^{i_h}\\sim \\pi^{i_h}}[A_{j,\\boldsymbol{\\pi_{\\theta_k}}}^{i_h}(s, a^{i_h})]$ so that we only consider the latter one. We can divide the formula like this: $E_{s \\sim \\rho_{\\boldsymbol{\\pi_{\\theta_k}}},a^{i_h}\\sim \\pi^{i_h}}[A_{j,\\boldsymbol{\\pi_{\\theta_k}}}^{i_h}(s, a^{i_h})] =\\sum_s \\rho_{\\boldsymbol{\\pi_{\\theta_k}}}(s) \\sum_{a^{i_h}} \\pi^{i_h}(a^{i_h}|s) A_{j,\\boldsymbol{\\pi_{\\theta_k}}}^{i_h}(s, a^{i_h})$, where $\\rho_{\\boldsymbol{\\pi_{\\theta_k}}}(s)$ represents state visitation frequencies. We easily know that $\\rho_{\\boldsymbol{\\pi_{\\theta_k}}}(s)$ is not affected by $\\pi^{i_h}$. Similarly, for each action of agent $i_h$, the $A_{j,\\boldsymbol{\\pi_{\\theta_k}}}^{i_h}(s, a^{i_h})$ is also not relative to $\\pi^{i_h}$. To this end, when $\\boldsymbol{\\pi_{\\theta_k}}$ and $\\theta_{k+1}^{i_{1:h-1}}$ are given, $E_{s \\sim \\rho_{\\boldsymbol{\\pi_{\\theta_k}}},a^{i_h}\\sim \\pi^{i_h}}[A_{j,\\boldsymbol{\\pi_{\\theta_k}}}^{i_h}(s, a^{i_h})]$ is convex to $\\pi^{i_h}$. The same analysis applies to Equation (7) as well, confirming the convexity of both the objective and the cost constraint.  What's more, the good performance can also show the correctness of our algorithm to some degree.\n\n*Q2*:  When solving the optimization problem, in Corollary 2, the expectation of the advantage over the optimal policy $\\pi^{i_h*}$ is assumed to be zero. The advantage means the performance improvement of the optimal policy. How can it be reasonable to assume it to be zero?\n\n*A2*: We are sorry that we may have omitted some derivation process in the manuscript. As we employ an intuitive heuristic based on primal-dual gradient methods [1], we apply the gradient descent method to estimate $\\nu_j$ during the optimization for agent $i_h$. As for the last term in the gradient expression, direct evaluation may be infeasible since $\\pi^{i_h*}$ may not locate in parameterized policy space. However, we can know that the optimal policy $\\pi^{i_h*}$ satisfies the constraint of Equation (3). This allows us to assume that $\\pi^{i_h*}$ and $\\pi_{\\theta_k}^{i_h}$ are very close. Following the definitions in reinforcement learning, we can know $A_\\pi(s,a)=Q_\\pi(s,a)-V_\\pi(s)$ and $V_\\pi(s)=\\sum_a \\pi(s,a) Q_\\pi(s,a) =E_{a \\sim \\pi}[Q_\\pi(s,a) ]$, we can easily know the $E_{a \\sim \\pi}[A_\\pi(s,a)]=\\sum_a \\pi(s,a) A_\\pi(s,a)=\\sum_a \\pi(s,a) Q_\\pi(s,a)-\\sum_a \\pi(s,a) V_\\pi(s)=\\sum_a \\pi(s,a) Q_\\pi(s,a) -V_\\pi(s)=0$. To this end, we can adopt $\\pi_{\\theta_k}^{i_h}$ to approximate the expectation of advantage over $\\pi^{i_h*}$ and get $E_{s \\sim \\rho_{\\boldsymbol{\\pi_{\\theta_k}}},a^{i_h} \\sim \\pi^{i_h*}}[A_{j,\\boldsymbol{\\pi_{\\theta_k}}}^{i_h}(s, a^{i_h})] \\approx E_{s \\sim \\rho_{\\boldsymbol{\\pi_{\\theta_k}}},a^{i_h} \\sim \\pi_{\\theta_k}^{i_h}}[A_{j,\\boldsymbol{\\pi_{\\theta_k}}}^{i_h}(s, a^{i_h})]=0$.\n\nThis approximation may bring some error so that we also introduce a per-state acceptance indicator function $I(s_j)=\\boldsymbol{1}\\_{D\\_{KL}(\\pi\\_\\theta^{i_h},\\pi\\_{\\theta_k}^{i_h}) \\leq \\delta}$ to enforce the constraint that updated policy remains close to $\\pi_{\\theta_k}^{i_h}$. Our experimental results also demonstrate that the proposed approximation is reasonable and leads to satisfactory performance in practice.\n\nFinally, thank you again for your comments. We will incorporate your suggestions and describe our method more clearly in our next revision. If some of your concerns are addressed, you could consider raising the rating. This is very important for us and we will appreciate it very much.\n\n[1] D. P. Bertsekas, Constrained optimization and Lagrange multiplier methods. Academic press, 2014."}, {"review_id": "sIjfDL19TE", "reviewer": "Reviewer_VTR2", "summary": "The paper introduces a fresh approach to tackle the problem of safe Multi-Agent Reinforcement Learning (MARL) within a fully-cooperative multi-agent environment where all agents share a common reward function. The authors propose a novel algorithm known as Multi-Agent First Order Constrained Optimization in Policy Space (MAFOCOPS). This algorithm aims to maximize the expected total reward while ensuring each agent adheres to its safety constraint. The authors claim that MAFOCOPS is easy to implement and provides an approximate upper bound for worst-case constraint violation. To demonstrate its effectiveness, the paper conducts experiments on two safe MARL benchmarks, Safe MAMuJoCo and Safe MAIG. The results show that MAFOCOPS outperforms MACPO. ", "questions": "1.\tThe paper acknowledges that solving the dual problems presented in the optimization process is computationally challenging when dealing with large state/action spaces. Calculating the partition function often involves evaluating a high-dimensional integral or sum, which can be computationally intensive. Moreover, the parameters λj and νj are dependent on the iteration k and need to be adjusted at every iteration to ensure the effectiveness of optimization. This adds to the complexity of the implementation. It would be beneficial if the authors could provide more details on how they plan to address these challenges in practical implementations. Are there any strategies or methods that could be used to reduce the computational complexity?\n\n2.\tThe paper mentions that the proposed method only employs first-order approximations, making it straightforward to implement. However, could the use of only first-order approximations limit the accuracy or effectiveness of the method in certain scenarios?\n\n3.\tThe paper mentions that the proposed method has an approximate upper bound for worst-case constraint violation. Could the authors elaborate more on what this upper bound is and how it was determined?\n\n4.\tThe paper discusses the use of a two-step process to solve the optimization problem. Could there be potential issues with this approach, such as the possibility of getting stuck in local optima?\n", "limitations": "Based on the information extracted from the paper, the authors have acknowledged some limitations of their work. They mention that due to the benchmarks they used, the performance of their algorithm across multiple costs was not evaluated. They also express their intention to test their approach in more environments and physical settings in the future.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.\tThe paper introduces a unique approach to multi-agent reinforcement learning, focusing on a fully-cooperative setting. It provides a new perspective on the problem by considering the influence of an agent's action on the total costs, even if it doesn't directly impact the costs of other agents. This approach captures the realistic multi-agent interactions in the real world, such as the disruption in traffic flow caused by a car running a red light.\n\n2.\tThe paper is well-structured and provides a clear explanation of the proposed method. It also includes a proof in the appendix, demonstrating the mathematical rigor of the work. The paper also compares its method with other algorithms, showing that it maintains a soft safety awareness, unlike other algorithms that reach safety via hard constraints.\n\n3.\tThe approach is significant as it provides a new perspective on multi-agent reinforcement learning, considering the influence of an agent's action on the total costs. The empirical results demonstrate the outstanding performance and computational efficiency of the proposed method, compared to more intricate second-order methods. The paper also suggests future work, planning to test the approach in more environments and physical settings.\n", "weaknesses": "The paper does not evaluate the performance of the algorithm across multiple costs. The benchmarks adopted only return one cost for agents, which limits the comprehensiveness of the evaluation. This could potentially mask some weaknesses or limitations of the proposed method when dealing with multiple costs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Q1*: It would be beneficial if the authors could provide more details on how they plan to address computational complexity in practice. Are there any strategies or methods that could be used to reduce the computational complexity?\n\n*A1*: We introduce the implementation of these two hyperparameters in the Section 4.3. In fact, we note that $\\lambda_j$ is similar to the temperature term utilized in maximum entropy RL [1].  Previous studies have shown that fixed values of $\\lambda$ can yield reasonable outcomes [2]. Therefore, in practice, we adopt fixed $\\lambda_j$ through grid search, allowing us to strike a balance between computational efficiency and model performance.\n\nAs for $\\nu_j$, we derive Corollary 2, which enables us to apply gradient descent method to optimize this parameter. In practice, we use Equation (10) to update $\\nu_j$. The equation exhibits an intuitive characteristic: it raises $\\nu_j$ if $J_j^{i_h}(\\boldsymbol{\\pi_{\\theta_k}}) > c_j^{i_h}$, indicating a violation of the cost constraint, and reduces $\\nu_j$ otherwise. Aligning with the update rule employed in MACPO to estimate $J_j^{i_h}(\\boldsymbol{\\pi_{\\theta_k}})$, $\\nu_j$ can be updated during training, which is shown in the Procedure of our algorithm in the Appendix. We think using these strategies can greatly reduce the computational complexity. The efficiency analysis can also illustrate the efficiency of these strategies in some way.\n\n*Q2*: The paper mentions that the proposed method only employs first-order approximations, making it straightforward to implement. However, could the use of only first-order approximations limit the accuracy or effectiveness of the method in certain scenarios?\n\n*A2*: We acknowledge that first-order approximations may introduce a trade-off between efficiency and accuracy. However, we would like to emphasize that despite employing first-order approximations, our method exhibits superior empirical performance compared to baseline algorithms.  This indicates that the approximations are not detrimental to the overall effectiveness of our approach. Meanwhile, second-order methods will introduce many approximation errors, so whether they are more accurate than first-order methods is hard to determine. Moreover, one of the significant strengths of our method is its obvious improved efficiency compared to MACPO, where the use of first-order approximations is crucial. Even if in some certain scenarios using only first-order approximations may limit the accuracy, we believe that our approach can strike a well-balanced compromise between efficiency and accuracy. \n\n*Q3*: The paper mentions that the proposed method has an approximate upper bound for worst-case constraint violation. Could the authors elaborate more on what this upper bound is and how it was determined?\n\n*A3*: Due to the page limit, the approximate upper bound is given in the Appendix. Here we give a brief description due to character limit. For each agent $i$, after getting the optimal joint update policy for all agents, $J_j^i(\\boldsymbol{\\pi^*}) \\leq J_j^i(\\boldsymbol{\\pi_{\\theta_k}}) + L_{j, \\boldsymbol{\\pi_{\\theta_k}}}^i(\\pi^{i_h*}) + \\nu_j^{i_h} \\sum_{l=1}^n D_{KL}^{max}(\\pi^{l*}, \\pi_{\\theta_k}^l)$ can be obtained, where $L_{j, \\boldsymbol{\\pi}}^i(\\bar{\\pi}^i) = E_{s \\sim \\rho_{\\boldsymbol{\\pi}}, a^i \\sim \\bar{\\pi}^i}[A_{j,\\boldsymbol{\\pi}}^i(s,a^i)]$. Considering the constraint in the optimization problem, we can know that $J_j^i(\\boldsymbol{\\pi^*}) \\leq c_j^{i_h}+ \\nu_j^{i_h} \\sum_{l=1}^n D_{KL}^{max}(\\pi^{l*}, \\pi_{\\theta_k}^l)$. Besides,  the kl divergence for each $l$ has an upper bound, which we call $\\delta^l$. To this end, we achieve $J_j^i(\\boldsymbol{\\pi^*}) \\leq c_j^{i_h} + \\frac{2 \\gamma max_{s,a^i}|A^i_{j.\\boldsymbol{\\pi}}(s,a^i)|}{(1-\\gamma)^2} \\sum_{l=1}^n \\delta^l$ , which is the upper bound for worst-case constraint violation. This bound indicates that with more agents, the optimization becomes more challenging, aligning with our intuition.\n\n*Q4*: The paper discusses the use of a two-step process to solve the optimization problem. Could there be potential issues with this approach, such as the possibility of getting stuck in local optima?\n\n*A4*: We appreciate your comments and understand your concern. In fact, the idea of solving problems in nonparametric space and then projecting back into the parameter space has been successfully applied to tackle various challenging problems. For instance, Abdolmaleki et al. [3] takes the view of ''inference view'' of policy search and attempts to find the desired policy via the EM algorithm. Montgomery et al. [4] develop a guided policy update method and provide theoretical guarantees on the bounded error in the projection step. In addition, Supervised Policy Update (SPU) [5] solves a constrained optimization problem in the nonparameteric policy space and then converts the optimal policy to a parameterized one using supervised regression. These previous works provide theoretical foundations for our methodology. Furthermore, the performance of our algorithm in extensive experiments supports the validity of our approach, showing that the two-step process does not lead our method to getting stuck in local optima or other significant issues.\n\n[1] B. D. Ziebart et al., “Maximum entropy inverse reinforcement learning.” in Aaai, vol. 8. 2008, pp. 1433–1.\n\n[2] T. Haarnoja et al, “Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor,” in International Conference on Machine Learning, 2018, pp. 1861–1870.\n\n[3]A. Abdolmaleki et al, “Maximum a posteriori policy optimisation,” in International Conference on Learning Representations, 2018.\n\n[4] W. H. Montgomery and S. Levine, “Guided policy search via approximate mirror descent,” Advances in Neural Information Processing Systems, vol. 29, 2016.\n\n[5] Q. Vuong et al, “Supervised policy update for deep reinforcement learning,” in International Conference on Learning Representations, 2018."}]

Author rebuttal:
Thank all reviewers for your time and valuable suggestions. We hope our rebuttal could address your concerns. We would appreciate it if you could re-evaluate our submission and we are looking forward to discussions if you have any other concerns.

Meta-review: The paper proposes Multi-Agent First Order Constrained Optimization in Policy Space (MAFOCOPS), an safety-aware algorithm for multi-agent reinforcement learning (MARL). The proposed approach solves the non-parametric constrained optimization problem and projects the policy back into a parametric policy space to enforce safety. The idea of this algorithm is quite interesting and novel in the MARL domain. The first-order method implemented is also practical and easy enough to implement, with experimental results showing significant performance improvements. I agree with most reviewers that the studied problem is important and the paper is by far quite well-written.

Some reviewers express concerns on the theoretical contribution, which makes this paper ending up with an overall borderline score. But on the overall, I still think the merits of this paper (problem motivation/formulation, proposed algorithms, experiments) outweigh the downsides raised and therefore recommend acceptance
Decision: Accept (poster)