Year: 2021

Abstract:
Developing reinforcement learning algorithms that satisfy safety constraints is becoming increasingly important in real-world applications. In multi-agent reinforcement learning (MARL) settings, policy optimisation with safety awareness is particularly challenging because each individual agent has to not only meet its own safety constraints, but also consider those of others so that their joint behaviour can be guaranteed safe. Despite its importance, the problem of safe multiagent learning has not been rigorously studied; very few solutions have been proposed, nor a sharable testing environment or benchmarks. To fill these gaps, in this work, we formulate the safe MARL problem as a constrained Markov game and solve it with policy optimisation methods. Our solutions—Multi-Agent Constrained Policy Optimisation (MACPO) and MAPPO-Lagrangian—leverage the theories from both constrained policy optimisation and multi-agent trust region learning. Crucially, our methods enjoy theoretical guarantees of both monotonic improvement in reward and satisfaction of safety constraints at every iteration. To examine the effectiveness of our methods, we develop the benchmark suite of Safe Multi-Agent MuJoCo that involves a variety of MARL baselines. Experimental results justify that MACPO/MAPPO-Lagrangian can consistently satisfy safety constraints, meanwhile achieving comparable performance to strong baselines.1

heading: 1 INTRODUCTION
text: In recent years, reinforcement learning (RL) techniques have achieved remarkable successes on a variety of complex tasks (Silver et al., 2016; 2017; Vinyals et al., 2019). Powered by deep neural networks, deep RL enables learning sophisticated behaviours. On the other hand, deploying neural networks turns the optimisation procedure from policy space to parameter space; this enables gradient-based methods to be applied (Sutton et al., 1999; Lillicrap et al., 2015; Schulman et al., 2017). For policy gradient methods, at every iteration, the parameters of a policy network are updated in the direction of the gradient that maximises return.
However, policies that are purely optimised for reward maximisation are rarely applicable to realworld problems. In many applications, an agent is often required not to visit certain states or take certain actions, which are thought of as “unsafe” either for itself or for other elements in the background (Moldovan & Abbeel, 2012; Achiam et al., 2017). For instance, a robot carrying materials in a warehouse should not damage its parts while delivering an item to a shelf, nor should a selfdriving car cross on the red light while rushing towards its destination (Shalev-Shwartz et al., 2016). To tackle these issues, Safe RL (Moldovan & Abbeel, 2012; Garcıa & Fernández, 2015) is proposed, aiming to develop algorithms that learn policies that satisfy safety constraints. Despite the additional requirement of safety on solutions, algorithms with convergence guarantees have been proposed (Xu et al., 2021; Wei et al., 2021).
Developing safe policies for multi-agent systems is a challenging task. Part of the difficulty comes from solving multi-agent reinforcement learning (MARL) problems itself (Deng et al., 2021); more importantly, tackling safety in MARL is hard because each individual agent has to not only consider its own safety constraints, which already may conflict its reward maximisation, but also consider the safety constraints of others so that their joint behaviour is guaranteed to be safe. As a result, there are very few solutions that offer effective learning algorithms for safe MARL problems. In fact, many of the existing methods focus on learning to cooperate (Foerster et al., 2018; Rashid et al., 2018;
1Paper homepage including Videos and Code: https://sites.google.com/view/macpo
Yang & Wang, 2020). However, they often require certain structures on the solution; for example, Rashid et al. (2018) and Yang et al. (2020) adopt greedy maximisation on the local component of a monotonic joint value function, and Foerster et al. (2018) estimates the policy gradient based on the counterfactual value from a joint critic. Therefore, it is unclear how to directly incorporate safety constraints into these solution frameworks. Consequently, developing agents’ collaborations towards reward maximisation under safety constraints remains an unsolved problem.
The goal of this paper is to increase practicality of MARL algorithms through endowing them with safety awareness. For this purpose, we introduce a general framework to formulate safe MARL problems, and solve them through multi-agent policy optimisation methods. Our solutions leverage techniques from both constrained policy optimisation (Achiam et al., 2017) and multi-agent trust region learning (Kuba et al., 2021a). The resulting algorithm attains properties of both monotonic improvement guarantee and constraints satisfaction guarantee at every iteration during training. To execute the optimisation objectives, we introduce two practical deep MARL algorithms: MACPO and MAPPO-Lagrangian. As a side contribution, we also develop the first safe MARL benchmark within the MuJoCo environment, which include a variety of MARL baseline algorithms. We evaluate MACPO and MAPPO-Lagrangian on a series of tasks, and results clearly confirm the effectiveness of our solutions both in terms of constraints satisfaction and reward maximisation. To our best knowledge, MACPO and MAPPO-Lagrangian are the first safety-aware model-free MARL algorithms that work effectively in the challenging MuJoCo tasks with safety constraints.

heading: 2 RELATED WORK
text: Considering safety in the development of AI is a long-standing topic (Amodei et al., 2016). When it comes to safe reinforcement learning (Garcıa & Fernández, 2015), a commonly used framework is Constrained Markov Decision Processes (CMDPs) (Altman, 1999). In a CMDP, at every step, in addition to the reward, the environment emits costs associated with certain constraints. As a result, the learning agent must try to satisfy those constraints while maximising the total reward. In general, the cost from the environment can be thought of as a measure of safety. Under the framework of CMDP, a safe policy is the one that explores the environment safely by keeping the total costs under certain thresholds. To tackle the learning problem in CMDPs, Achiam et al. (2017) introduced Constrained Policy Optimisation (CPO), which updates agent’s policy under the trust region constraint (Schulman et al., 2015) to maximise surrogate return while obeying surrogate cost constraints. However, solving a constrained optimisation at every iteration of CPO can be cumbersome for implementation. An alternative solution is to apply primal-dual methods, giving rise to methods like TRPO-Lagrangian and PPO-Lagrangian (Ray et al., 2019). Although these methods achieve impressive performance in terms of safety, the performance in terms of reward is poor (Ray et al., 2019). Another class of algorithms that solves CMDPs is by Chow et al. (2018; 2019); these algorithms leverage the theoretical property of the Lyapunov functions and propose safe value iteration and policy gradient procedures. In contrast to CPO, Chow et al. (2018; 2019) can work with off-policy methods; they also can be trained end-to-end with no need for line search.
Safe multi-agent learning is an emerging research domain. Despite its importance (Shalev-Shwartz et al., 2016), there are few solutions that work with MARL in a model-free setting. The majority of methods are designed for robotics learning. For example, the technique of barrier certificates (Borrmann et al., 2015; Ames et al., 2016; Qin et al., 2020) or model predictive shielding (Zhang et al., 2019) from control theory is used to model safety. These methods, however, are specifically derived for robotics applications; they either are supervised learning based approaches, or require specific assumptions on the state space and environment dynamics. Moreover, due to the lack of a benchmark suite for safe MARL algorithms, the generalisation ability of those methods is unclear. The most related work to ours is Safe Dec-PG (Lu et al., 2021) where they used the primal-dual framework to find the saddle point between maximising reward and minimising cost. In particular, they proposed a decentralised policy descent-ascent method through a consensus network. However, reaching a consensus equivalently imposes an extra constraint of parameter sharing among neighbouring agents, which could yield suboptimal solutions (Kuba et al., 2021a). Furthermore, multi-agent policy gradient methods can suffer from high variance (Kuba et al., 2021b). In contrast, our methods employ trust region optimisation and do not assume any parameter sharing.
HATRPO (Kuba et al., 2021a) introduced the first multi-agent trust region method that enjoys theoretically-justified monotonic improvement guarantee. Its key idea is to make agents follow a
sequential policy update scheme so that the expected joint advantage will always be positive, thus increasing reward. In this work, we show how to further develop this theory and derive a protocol which, in addition to the monotonic improvement, also guarantees to satisfy the safety constraint at every iteration during learning. The resulting algorithm (Algorithm 1) successfully attains theoretical guarantees of both monotonic improvement in reward and satisfaction of safety constraints.

heading: 3 PROBLEM FORMULATION: CONSTRAINED MARKOV GAME
text: We formulate the safe MARL problem as a constrained Markov game 〈N ,S,A, p, d0, W, ',C, c〉. Here, N = {1, . . . , =} is the set of agents, S is the state space, A = ∏=8=1A8 is the product of the agents’ action spaces, known as the joint action space, p : S ×A × S → ℝ is the probabilistic transition function, d0 is the initial state distribution, W ∈ [0, 1) is the discount factor, ' : S×A → ℝ is the joint reward function, C = { 8
9 }8∈N1≤ 9≤<8 is the set of sets of cost functions (every agent 8 has < 8
cost functions) of the form 8 9 : S ×A8 → ℝ, and finally the set of corresponding cost-constraining values is given by c = {28
9 }8∈N1≤ 9≤<8 . At time step C, the agents are in a state sC , and every agent 8 takes
an action a8C according to its policy c 8 (a8 |sC ). Together with other agents’ actions, it gives a joint action aC = (a1C , . . . , a=C ) and the joint policy π(a|s) = ∏= 8=1 c
8 (a8 |s). The agents receive the reward '(sC , aC ), meanwhile each agent 8 pays the costs 89 (sC , a8C ), ∀ 9 = 1, . . . , <8 . The environment then transits to a new state sC+1 ∼ p(·|sC , aC ). In this paper, we consider a fully-cooperative setting where all agents share the same reward function, aiming to maximise the expected total reward of
(π) , s0∼d0 ,a0:∞∼π,s1:∞∼p [ ∞∑ C=0 WC'(sC , aC ) ] ,
meanwhile trying to satisfy every agent 8’s safety constraints, written as 89 (π) , s0∼d0 ,a0:∞∼π,s1:∞∼p [ ∞∑ C=0 WC 89 (sC , a8C ) ] ≤ 289 , ∀ 9 = 1, . . . , <8 . (1)
We define the state-action value and the state-value functions in terms of reward as &π (B,a) , s1:∞∼p,a1:∞∼π [ ∞∑ C=0 WC'(sC , aC ) s0 = B, a0 = a] , and +π (B) , a∼π [&π (B, a)] .
The joint policies π that satisfy the Inequality (1) are referred to as feasible. Notably, in the above formulation, although the action a8C of agent 8 does not directly influence the costs { :9 (sC , a:C )}< :
9=1 of other agents : ≠ 8, the action a8C will implicitly influence their total costs due to the dependence on the next state sC+1 2. For the 9 th cost function of agent 8, we define the 9 th state-action cost value function and the state cost value function as
&89 ,π (B, 08) , a−8∼π−8 ,s1:∞∼p,a1:∞∼π [ ∞∑ C=0 WC 89 (sC , a8C ) s0 = B, a80 = 08] ,
and, + 89 ,π (B) , a∼π,s1:∞∼p,a1:∞∼π [ ∞∑ C=0 WC 89 (sC , a8C ) s0 = B] , respectively.
Notably, the cost value functions &8 9 ,π and + 8 9 ,π , although similar to traditional &π and +π , involve extra indices 8 and 9 ; the superscript 8 denotes an agent, and the subscript 9 denotes its 9 th cost.
Throughout this work, we pay a close attention to the contribution to performance from different subsets of agents, therefore, we introduce the following notations. We denote an arbitrary subset
2We believe that this formulation realistically describes multi-agent interactions in the real-world; an action of an agent has an instantaneous effect on the system only locally, but the rest of agents may suffer from its consequences at later stages. For example, consider a car that crosses on the red light, although other cars may not be at risk of riding into pedestrians immediately, the induced traffic may cause hazards soon later.
{81, . . . , 8ℎ} of agents as 81:ℎ; we write −81:ℎ to refer to its complement. Given the agent subset 81:ℎ , we define the multi-agent state-action value function:
&81:ℎπ (B,a81:ℎ ) , a−81:ℎ∼π−81:ℎ [ &π (s,a81:ℎ , a−81:ℎ ) ] .
On top of it, the multi-agent advantage function 3 is defined as follows, 81:ℎπ ( B,a 91:: ,a81:ℎ ) , & 91:: ,81:ℎπ ( B,a 91:: ,a81:ℎ ) −& 91::π ( B,a 91:: ) . (2)
An interesting fact about the above multi-agent advantage function is that any advantage 81:ℎπ can be written as a sum of sequentially-unfolding multi-agent advantages of individual agents, that is, Lemma 1 (Multi-Agent Advantage Decomposition, Kuba et al. (2021b)). For any state B ∈ S, subset of agents 81:ℎ ⊆ N , and joint action a81:ℎ , the following identity holds
81:ℎπ ( B,a81:ℎ ) = ℎ∑ 9=1 8 9 π ( B,a81: 9−1 , 08 9 ) .

heading: 4 MULTI-AGENT CONSTRAINED POLICY OPTIMISATION
text: In this section, we first present a theoretically-justified safe multi-agent policy iteration procedure, which leverages multi-agent trust region learning and constrained policy optimisation to solve constrained Markov games. Based on this, we propose two practical deep MARL algorithms, enabling optimising neural-network based policies that satisfy safety constraints. Throughout this work, we refer the symbols π and π̄ to be the “current” and the “new” joint policies, respectively.

heading: 4.1 MULTI-AGENT TRUST REGION LEARNING WITH CONSTRAINTS
text: Kuba et al. (2021a) introduced the first multi-agent trust region method—HATRPO—that enjoys theoretically-justified monotonic improvement guarantee. Specifically, it relies on the multi-agent advantage decomposition in Lemma 1, and the “surrogate” return that is given as follows. Definition 1. Let π be a joint policy, π̄81:ℎ−1 be some other joint policy of agents 81:ℎ−1, and ĉ8ℎ be a policy of agent 8ℎ . Then we define
!81:ℎπ ( π̄81:ℎ−1 , ĉ8ℎ ) , s∼dπ ,a81:ℎ−1∼π̄81:ℎ−1 ,a8ℎ∼ ĉ8ℎ [ 8ℎπ ( s, a81:ℎ−1 , a8ℎ ) ] .
With the above definition, we can see that Lemma 1 allows for decomposing the joint surrogate return !π (π̄) , s∼dπ ,a∼π̄ [ π (s, a)] into a sum over surrogates of ! 81:ℎ π (π̄81:ℎ−1 , c̄8ℎ ), for ℎ = 1, . . . , =. This can be used to justify that if agents, with a joint policy π, update their policies by following a sequential update scheme, that is, if each agent in the subset 81:ℎ sequentially solves the following optimisation problem:
c̄8ℎ = max ĉ8ℎ
!81:ℎπ ( π̄81:ℎ−1 , ĉ8ℎ ) − a maxKL ( c8ℎ , ĉ8ℎ ) ,
where a = 4WmaxB,a | π (B,a) |
(1 − W)2 , and maxKL (c 8ℎ , ĉ8ℎ ) , max B KL (c8ℎ (·|B), ĉ8ℎ (·|B)),
then the resulting joint policy π̄ will surely improve the expected return, i.e., (π̄) ≥ (π) (see the proof in Kuba et al. (2021a, Lemma 2)). We know that due to the penalty term maxKL (c
8ℎ , ĉ8ℎ ), the new policy c̄8ℎ will stay close (w.r.t max-KL distance) to c8ℎ .
For the safety constraints, we can extend Definition 1 to incorporate the “surrogate” cost, thus allowing us to study the cost functions in addition to the return. Definition 2. Let π be a joint policy, and c̄8 be some other policy of agent 8. Then, for any of its costs of index 9 ∈ {1, . . . , <8}, we define
!89 ,π ( c̄8 ) = s∼dπ ,a8∼ c̄8 [ 89 ,π ( s, a8 ) ] .
3We would like to highlight that these multi-agent functions of &81:ℎπ and 81:ℎ π , although involve agents in
superscripts, describe values w.r.t the reward rather than costs since they do not involve cost subscripts.
By generalising the result about the surrogate return in Equation (1), we can derive how the expected costs change when the agents update their policies. Specifically, we provide the following lemma.
Lemma 2. Let π and π̄ be joint policies. Let 8 ∈ N be an agent, and 9 ∈ {1, . . . , <8} be an index of one of its costs. The following inequality holds
89 (π̄) ≤ 89 (π) + !89 ,π ( c̄8 ) + a89 =∑ ℎ=1 maxKL ( cℎ , c̄ℎ ) , where a89 = 4WmaxB,08 | 89 ,π (B, 08) | (1 − W)2 .
See proof in Appendix A. The above lemma suggests that, as long as the distances between the policies cℎ and c̄ℎ , ∀ℎ ∈ N , are sufficiently small, then the change in the 9 th cost of agent 8, i.e., 8 9 (π̄) − 8 9 (π), is controlled by the surrogate !8
9 ,π (c̄8). Importantly, this surrogate is independent of other agents’ new policies. Hence, when the changes in policies of all agents are sufficiently small, each agent 8 can learn a better policy c̄8 by only considering its own surrogate return and surrogate costs. To summarise, we provide the following algorithm that guarantees both safety constraints satisfaction and monotonic performance improvement.
Algorithm 1: Safe Multi-Agent Policy Iteration with Monotonic Improvement Property 1: Initialise a safe joint policy π0 = (c10, . . . , c = 0 ).
2: for : = 0, 1, . . . do 3: Compute the advantage functions π: (B,a) and 89 ,π: (B, 0
8), for all state-(joint)action pairs (B,a), agents 8, and constraints 9 ∈ {1, . . . , <8}.
4: Compute a = 4WmaxB,a | π: (B,a) |(1−W)2 , and a 8 9 = 4Wmax B,08 | 8 9,π: (B,08) | (1−W)2 , ∀8 ∈ N , 9 = 1, . . . , < 8 . 5: Draw a permutaion 81:= of agents at random. 6: for ℎ = 1 : = do 7: Compute the radius of the KL-constraint X8ℎ // see Appendix B for the setup of X8ℎ . 8: Make an update c8ℎ :+1 = arg maxc8ℎ ∈Π8ℎ [ ! 81:ℎ π: ( c 81:ℎ−1 :+1 , c 8ℎ ) − a maxKL ( c 8ℎ : , c8ℎ )] ,
where Π8ℎ is a subset of safe policies of agent 8ℎ , given by
Π 8ℎ = { c8ℎ ∈ Π8ℎ
maxKL (c8ℎ: , c8ℎ ) ≤ X8ℎ , and 8ℎ 9 (π: ) + !8ℎ9 ,π: (c 8ℎ ) + a8ℎ 9 maxKL (c 8ℎ : , c8ℎ ) ≤ 28ℎ 9 − ℎ−1∑ ;=1 a 8; 9 maxKL (c 8; : , c8; ),∀ 9 = 1, . . . , <8ℎ } .
9: end for 10: end for
In the above algorithm, in addition to sequentially maximising agents’ surrogate returns, the agents must assure that their surrogate costs stay below the corresponding safety thresholds. Meanwhile, they have to constrain their policy search to small local neighbourhoods (w.r.t max-KL distance). As such, Algorithm 1 demonstrates two desirable properties: reward performance improvement and satisfaction of safety constraints, which we justify in the following theorem.
Theorem 1. If a sequence of joint policies (π: )∞:=0 is obtained from Algorithm 1, then it has the monotonic improvement property, (π:+1) ≥ (π: ), as well as it satisfies the safety constraints, 8 9 (π: ) ≤ 289 , for all : ∈ ℕ, 8 ∈ N , and 9 ∈ {1, . . . , <8}.
See proof in Appendix B. The above theorem assures that agents that follow Algorithm 1 will only explore safe policies; meanwhile, every new policy will be guaranteed to result in performance improvement. These two properties hold under the conditions that only restrictive policy updates are made; this is due to the KL-penalty term in every agent’s objective (i.e., a maxKL (c 8ℎ : , c8ℎ )), as well as the constraints on cost surrogates (i.e., the conditions in Π 8ℎ ). In practice, it can be intractable to
evaluate KL ( c 8ℎ : (·|B), c8ℎ (·|B) ) at every state in order to compute maxKL (c 8ℎ : , c8ℎ ). In the following subsections, we describe how we can approximate Algorithm 1 in the case of parameterised policies, similar to TRPO/PPO implementations (Schulman et al., 2015; 2017).

heading: 4.2 MACPO: MULTI-AGENT CONSTRAINED POLICY OPTIMISATION
text: Here we focus on the practical settings where large state and action spaces prevent agents from designating policies c8 (·|B) for each state separately. To handle this, we parameterise each agent’s c8
\ 8
by a neural network \8 . Correspondingly, the joint policies πθ are parametrised by θ = (\1, . . . , \=). Let’s recall that at every iteration of Algorithm 1, every agent 8ℎ maximises its surrogate return with a KL-penalty, subject to surrogate cost constraint. Yet, direct computation of the max-KL constraint is intractable in practical settings, as it would require computation of KL-divergence at every single state. Instead, one can relax it by adopting a form of expected KL-constraint KL (c8ℎ: , c
8ℎ ) ≤ X where KL (c8ℎ: , c 8ℎ ) , s∼dπ: [ KL (c8ℎ: (·|s), c 8ℎ (·|s)) ] . Such an expectation can be approximated by stochastic sampling. As a result, the optimisation problem solved by agent 8ℎ is written as
\ 8ℎ :+1 = arg max
\ 8ℎ
s∼dπθ: ,a 81:ℎ−1∼π81:ℎ−1
θ 81:ℎ−1 :+1
,a8ℎ∼c8ℎ \ 8ℎ
[ 8ℎπθ: ( s, a81:ℎ−1 , a8ℎ ) ] s.t. 8ℎ
9
( πθ: ) + s∼dπθ: ,a8ℎ∼c 8ℎ
\ 8ℎ :
[ 8ℎ 9 ,πθ: ( s, a8ℎ ) ] ≤ 28ℎ 9 , ∀ 9 ∈ {1, . . . , <8ℎ },
and KL ( c 8ℎ : , c8ℎ ) ≤ X. (3)
We can further approximate Equation (3) by Taylor expansion of the optimisation objective and cost constraints up to the first order, and the KL-divergence up to the second order. Consequently, the optimisation problem can be written as
\ 8ℎ :+1 = arg max
\ 8ℎ
( g8ℎ )) ( \8ℎ − \8ℎ
: ) s.t. 38ℎ
9 + ( b8ℎ 9 )) ( \8ℎ − \8ℎ : ) ≤ 0, 9 = 1, . . . , <
and 1 2
( \8ℎ − \8ℎ
:
)) H 8ℎ ( \8ℎ − \8ℎ
:
) ≤ X, (4)
where g8ℎ is the gradient of the objective of agent 8ℎ in Equation (3), 389 = 8 9 (πθ: ) − 289 , and H 8ℎ = ∇2 \ 8ℎ KL (c8ℎ
\ 8ℎ :
, c8ℎ ) \ 8ℎ=\
8ℎ :
is the Hessian of the average KL divergence of agent 8ℎ , and b 8ℎ 9
is the gradient of agent of the 9 th constraint of agent 8ℎ .
Similar to Chow et al. (2017) and Achiam et al. (2017), one can take a primal-dual optimisation approach to solve the linear quadratic optimisation in Equation (4). Specifically, the dual form can be written as:
max _8ℎ ≥0,v8ℎ 0 −1 2_8ℎ
[ (g8ℎ )) (H 8ℎ )−1g8ℎ − 2(r8ℎ )) v8ℎ + (v8ℎ ))S8ℎ ] + (v8ℎ )) c8ℎ − _ 8ℎX
2 , where r8ℎ , (g8ℎ )) (H 8ℎ )−1B8ℎ ,B8ℎ = [ b8ℎ1 , . . . , b 8ℎ < ] and S8ℎ , (B8ℎ )) (H 8ℎ )−1B8ℎ . (5)
Given the solution to the dual form in Equation (5), i.e., _8ℎ∗ and v 8ℎ ∗ , the solution to the primal problem in Equation (4) can thus be written by
\ 8ℎ ∗ = \ 8ℎ : + 1 _ 8ℎ ∗
( H 8ℎ )−1 ( g8ℎ −B8ℎv8ℎ∗ ) .
In practice, we use backtracking line search starting at 1/_8ℎ∗ to choose the step size of the above update. Furthermore, we note that the optimisation step in Equation (4) is an approximation to the original problem from Equation (3); therefore, it is possible that an infeasible policy c
\ 8ℎ :+1
will be
generated. Fortunately, as the policy optimisation takes place in the trust region of c8ℎ \ 8ℎ : , the size of update is small, and a feasible policy can be easily recovered. In particular, for problems with one safety constraint, i.e., <8ℎ = 1, one can recover a feasible policy by applying a TRPO step on the cost surrogate, written as
\ 8ℎ :+1 = \ 8ℎ : − U 9
√ 2X
b8ℎ) (H 8ℎ )−1b8ℎ ( H 8ℎ )−1 b8ℎ (6)
where U 9 is adjusted through backtracking line search. To put it together, we refer to this algorithm as MACPO, and provide its pseudocode in Appendix D.

heading: 4.3 MAPPO-LAGRANGIAN
text: In addition to MACPO, one can use Lagrangian multipliers in place of optimisation with linear and quadratic constraints to solve Equation (3). The Lagrangian method is simple to implement, and it does not require computations of the Hessian H 8ℎ whose size grows quadratically with the dimension of the parameter vector \8ℎ .
Before we proceed, let us briefly recall the optimisation procedure with a Lagrangian multiplier. Suppose that our goal is to maximise a bounded real-valued function 5 (G) under a constraint 6(G); maxG 5 (G), s.t. 6(G) ≤ 0. We can introduce a scalar variable _ and reformulate the optimisation by
max G min _≥0 5 (G) − _6(G). (7)
Suppose that G+ satisfies 6(G+) > 0. This immediately implies that −_6(G+) → −∞, as _ → +∞, and so Equation (7) equals −∞ for G = G+. On the other hand, if G− satisfies 6(G−) ≤ 0, we have that −_6(G−) ≥ 0, with equality only for _ = 0. In that case, the optimisation objective’s value equals 5 (G−) > −∞. Hence, the only candidate solutions to the problem are those G that satisfy the constraint 6(G) ≤ 0, and the objective matches with 5 (G). We can employ the above trick to the constrained optimisation problem from Equation (3) by subsuming the cost constraints into the optimisation objective with Lagrangian multipliers. As such, agent 8ℎ computes _̄ 8ℎ
1:<8ℎ and \ 8ℎ :+1 to solve the following min-max optimisation problem
min _ 8ℎ
1:<8ℎ ≥0
max \ 8ℎ [ s∼dπθ: ,a
81:ℎ−1∼π81:ℎ−1 θ 81:ℎ−1 :+1 ,a8ℎ∼c8ℎ \ 8ℎ
[ 8ℎπθ: ( s, a81:ℎ−1 , a8ℎ ) ] − <8ℎ∑ D=1 _8ℎD ( s∼dπθ: ,a 8ℎ∼c8ℎ \ 8ℎ [ 8ℎD,πθ: ( s, a8ℎ ) ] + 38ℎD ) ] ,
s.t. KL ( c 8ℎ
\ 8ℎ :
, c 8ℎ
\ 8ℎ
) ≤ X. (8)
Although the objective from Equation (8) is affine in the Lagrangian multipliers _8ℎD (D = 1, . . . , <8ℎ ), which enables gradient-based optimisation solutions, computing the KL-divergence constraint still complicates the overall process. To handle this, one can further simplify it by adopting the PPO-clip objective (Schulman et al., 2017), which enables replacing the KL-divergence constraint with the clip operator, and update the policy parameter with first-order methods. We do so by defining
8ℎ , (_) πθ:
( B,a81:ℎ−1 , 08ℎ ) , 8ℎπθ: ( B,a81:ℎ−1 , 08ℎ ) − <8ℎ∑ D=1 _8ℎD ( 8ℎD,πθ: ( B, 08ℎ ) + 38ℎD ) ,
and rewriting the Equation (8) as
min _ 8ℎ
1:<8ℎ ≥0
max \ 8ℎ s∼dπθ: ,a 81:ℎ−1∼π81:ℎ−1
θ 81:ℎ−1 :+1
,a8ℎ∼c8ℎ \ 8ℎ
[ 8ℎ , (_) πθ: ( s, a81:ℎ−1 , a8ℎ ) ] ,
s.t. KL ( c 8ℎ
\ 8ℎ :
, c 8ℎ
\ 8ℎ
) ≤ X. (9)
The objective in Equation (9) takes a form of an expectation with quadratic constraint on the policy. Up to the error of approximation of KL-constraint with the clip operator, it can be equivalently transformed into an optimisation of a clipping objective. Finally, the objective takes the form of
s∼dπθ: ,a 81:ℎ−1∼π81:ℎ−1
θ 81:ℎ−1 :+1 ,a8ℎ∼c8ℎ \ 8ℎ :
[ min ( c 8ℎ \ 8ℎ (a8ℎ |s)
c 8ℎ
\ 8ℎ :
(a8ℎ |s) 8ℎ , (_) πθ:
( s, a81:ℎ−1 , a8ℎ ) ,
clip ( c 8ℎ \ 8ℎ (a8ℎ |s)
c 8ℎ
\ 8ℎ :
(a8ℎ |s) , 1 ± n
) 8ℎ , (_) πθ: ( s, a81:ℎ−1 , a8ℎ ) )] . (10)
The clip operator replaces the policy ratio with 1 − n , or 1 + n , depending on whether its value is below or above the threshold interval. As such, agent 8ℎ can learn within its trust region by updating \8ℎ to maximise Equation (10), while the Lagrangian multipliers are updated towards the direction opposite to their gradients of Equation (8), which can be computed analytically. We refer to this algorithm as MAPPO-Lagrangian, and give a detailed pseudocode of it in Appendix E.

heading: 5 EXPERIMENTS
text: Although MARL researchers have long had a variety of environments to test different algorithms, such as StarCraftII (Samvelyan et al., 2019) and Multi-Agent MuJoCo (Peng et al., 2020), no public safe MARL benchmark has been proposed; this impedes researchers from evaluating and benchmarking safety-aware multi-agent learning methods. As a key contribution of this paper, we introduce Safe Multi-Agent MuJoCo Benchmark, a safety-aware extension of the MuJoCo environment that is designed for safe MARL research. We show example tasks in Figure 1, in our environment, safety-aware agents have to learn not only skilful manipulations of a robot, but also to avoid crashing into unsafe obstacles and positions. For more details of the setup, please refer to Appendix F.
We use Safe MAMuJoCo to examine if the MACPO/MAPPO-Lagrangian agents can satisfy their safety constraints and cooperatively learn to achieve high rewards, compared to existing MARL algorithms. Notably, our proposed methods adopt two different approaches for achieving safety. MACPO reaches safety via hard constraints and backtracking line search, while MAPPOLagrangian maintains a rather soft safety awareness by performing gradient descents on the PPOclip objective. Figure 2 shows cost and reward performance comparisons between MACPO, MAPPO-Lagrangian, MAPPO (Yu et al., 2021), IPPO (de Witt et al., 2020), and HAPPO (Kuba et al., 2021a) algorithms on three challenging tasks. Figure 2 should be interpreted at three-folds; each subfigure represents a different robot, within each subfigure, three task setups in terms of multiagent control are considered, for each task, we plot the cost curves (the lower the better) in the upper row, and plot the reward curves (the higher the better) in the bottom row. Detailed hyperparameter settings are described in Appendix H.
The experiments reveal that both MACPO and MAPPO-Lagrangian quickly learn to satisfy safety constraints, and keep their explorations within the feasible policy space. This stands in contrast to IPPO, MAPPO, and HAPPO which largely violate the constraints thus being unsafe. Furthermore, our algorithms achieve comparable reward scores; both methods are often better than IPPO. In general, the performance (in terms of reward) of MAPPO-Lagrangian is better than of MACPO; moreover, MAPPO-Lagrangian outperforms the unconstrained MAPPO on challenging Ant tasks. We note that on none of the tasks the reward of HAPPO was exceeded though it is unsafe.

heading: 6 CONCLUSION
text: In this paper, we tackled multi-agent policy optimisation problems with safety constraints. Central to our findings is the safe multi-agent policy iteration procedure that attains theoretically-justified monotonic improvement guarantee and constraints satisfaction guarantee at every iteration during learning. Based on this, we proposed two practical algorithms: MACPO and MAPPO-Lagrangian. To demonstrate their effectiveness, we introduced a new benchmark suite of Safe Multi-Agent MuJoCo and compared our methods against strong MARL baselines. Results show that both of our methods can significantly outperform existing state-of-the-art methods such as IPPO, MAPPO and HAPPO in terms of safety, meanwhile maintaining comparable performance in terms of reward.

heading: A Proofs of preliminary results 14

heading: B Auxiliary Results for Algorithm 1 15

heading: C Auxiliary Results for Implementation of MACPO 17

heading: D MACPO 18

heading: E MAPPO-Lagrangian 19

heading: F Safe Multi-Agent MuJoCo 20

heading: G Experiments in Safe Many-Agent Ant Environments 21
text: H Details of Settings for Experiments 22

heading: A PROOFS OF PRELIMINARY RESULTS
text: Lemma 1 (Multi-Agent Advantage Decomposition, Kuba et al. (2021b)). For any state B ∈ S, subset of agents 81:ℎ ⊆ N , and joint action a81:ℎ , the following identity holds
81:ℎπ ( B,a81:ℎ ) = ℎ∑ 9=1 8 9 π ( B,a81: 9−1 , 08 9 ) .
Proof. We write the multi-agent advantage as in its definition, and expand it in a telescoping sum. 81:ℎπ ( B,a81:ℎ ) = &81:ℎπ ( B,a81:ℎ ) −+π (B)
= ℎ∑ 9=1 [ & 81: 9 π ( B,a81: 9 ) −&81: 9−1π ( B,a81: 9−1 ) ] =
ℎ∑ 9=1 8 9 π ( B,a81: 9−1 , 08 9 ) .
Lemma 2. Let π and π̄ be joint policies. Let 8 ∈ N be an agent, and 9 ∈ {1, . . . , <8} be an index of one of its costs. The following inequality holds
89 (π̄) ≤ 89 (π) + !89 ,π ( c̄8 ) + a89 =∑ ℎ=1 maxKL ( cℎ , c̄ℎ ) , where a89 = 4WmaxB,08 | 89 ,π (B, 08) | (1 − W)2 .
Proof. From the proof of Theorem 1 from Schulman et al. (2015) (in particular, equations (41)-(45)), applied to joint policies π and π̄, we conclude that
89 (π̄) ≤ 89 (π) + s∼dπ ,a∼π̄ [ 89 ,π (s, a8) ] + 4U2WmaxB,08 | 89 ,π (B, 08) | (1 − W)2 ,
where U = maxTV (π, π̄) = maxB TV (π(·|B), π̄(·|B)) .
Using the inequality TV (?, @)2 ≤ KL (?, @) (Pollard, 2000; Schulman et al., 2015), we obtain
89 (π̄) ≤ 89 (π) + s∼dπ ,a∼π̄ [ 89 ,π (s, a8) ] + 4WmaxB,08 | 89 ,π (B, 08) | (1 − W)2 maxKL (π, π̄),
where maxKL (π, π̄) = maxB KL (π(·|B), π̄(·|B)) . Notice now that we have s∼dπ ,a∼π̄ [ 8 9 ,π (s, a8) ] = s∼dπ ,a8∼ c̄8 [ 8 9 ,π (s, a8) ] , and
maxKL (π, π̄) = maxB KL (π(·|B), π̄(·|B)) = maxB ( =∑ ;=1 KL ( c; (·|B), c̄; (·|B) )) ≤
=∑ ;=1 max B KL ( c; (·|B), c̄; (·|B) ) = =∑ ;=1 maxKL ( c; , c̄; ) . (11)
Setting a8 9 =
4Wmax B,08 | 8 9,π (B,08) |
(1−W)2 , we finally obtain
89 (π̄) ≤ 89 (π) + !89 ,π ( c̄8 ) + a89 =∑ ;=1 maxKL ( c; , c̄; ) .

heading: B AUXILIARY RESULTS FOR ALGORITHM 1
text: Remark 1. In Algorithm 1, we compute the size of KL constraint as
X8ℎ = min { min ;≤ℎ−1 min 1≤ 9≤<; 2 8; 9 − 8; 9 (π: ) − !8;9 ,π: (c 8; :+1) − a 8; 9 ∑ℎ−1 D=1 max KL (c D : , cD :+1)
a 8; 9
,
min ;≥ℎ+1 min 1≤ 9≤<;
2 8; 9 − 8; 9 (π: ) − a8;9 ∑ℎ−1 D=1 max KL (c D : , cD :+1)
a 8; 9
} .
Note that X81 (i.e., ℎ = 1) is guaranteed to be non-negative if π: satisfies safety constraints; that is because then 28;
9 ≥ 8; 9 (π: ) for all ; and 9 , and the set {; | ;<ℎ} is empty.
This formula for X8ℎ , combined with Lemma 2, assures that the policies c8ℎ within X8ℎ max-KL distance from c8ℎ
: will not violate other agents’ safety constraints, as long as the base joint policy
π: did not violate them (which assures X81 ≥ 0). To see this, notice that for every ; = 1, . . . , ℎ − 1, and 9 = 1, . . . , <; ,
maxKL (c 8ℎ : , c8ℎ ) ≤ X8ℎ ≤
2 8; 9 − 8; 9 (π: ) − !8;9 ,π: (c 8; :+1) − a 8; 9 ∑ℎ−1 D=1 max KL (c D : , cD :+1)
a 8; 9
,
implies 8; 9 (π: ) + !8;9 ,π: (c 8; :+1) + a 8; 9 ℎ−1∑ D=1 maxKL (c D : , c D :+1) + a 8; 9 maxKL (c 8ℎ : , c8ℎ ) ≤ 28; 9 .
By Lemma 2, the left-hand side of the above inequality is an upper bound of 8; 9 (π81:ℎ−1 :+1 , c 8ℎ ,π−81:ℎ : ), which implies that the update of agent 8ℎ doesn’t violate the constraint of 8; 9 . The fact that the constraints of 8; 9 for ; ≥ ℎ + 1 are not violated, i.e.,
8; 9 (π: ) + a8;9 ℎ−1∑ D=1 maxKL (c D : , c D :+1) + a 8; 9 maxKL (c 8ℎ : , c8ℎ ) ≤ 28; 9 , (12)
is analogous.
Theorem 1. If a sequence of joint policies (π: )∞:=0 is obtained from Algorithm 1, then it has the monotonic improvement property, (π:+1) ≥ (π: ), as well as it satisfies the safety constraints, 8 9 (π: ) ≤ 289 , for all : ∈ ℕ, 8 ∈ N , and 9 ∈ {1, . . . , <8}.
Proof. Safety constraints are assured to be met by Remark 1. It suffices to show the monotonic improvement property. Notice that at every iteration : of Algorithm 1, c8ℎ
: ∈ Π8ℎ . Clearly
maxKL (c 8ℎ : , c 8ℎ : ) = 0 ≤ X8ℎ . Moreover,
8ℎ 9 (π: ) + !8ℎ9 ,π: (c 8ℎ : ) + a8ℎ 9 maxKL (c 8ℎ : , c 8ℎ : ) = 8ℎ 9 (π: ) ≤ 28ℎ9 − a 8ℎ 9 ℎ−1∑ ;=1 maxKL (c 8; : , c 8; :+1),
where the inequality is guaranteed by updates of previous agents, as described in Remark 1 (Inequality 12). By Theorem 1 from Schulman et al. (2015), we have
(π:+1) ≥ (π: ) + s∼dπ: ,a∼π:+1 [ π: (s, a) ] − a maxKL (π: ,π:+1),
which by Equation 11 is lower-bounded by ≥ (π: ) + s∼dπ: ,a∼π:+1 [ π: (s, a) ] − =∑ ℎ=1 a maxKL (c 8ℎ : , c 8ℎ :+1)
which by Lemma 1 equals = (π: ) + =∑ ℎ=1 s∼dπ: ,a81:ℎ∼π 81:ℎ :+1 [ 8ℎπ: (s, a 81:ℎ−1 , a8ℎ ) ] − =∑ ℎ=1 a maxKL (c 8ℎ : , c 8ℎ :+1)
= (π: ) + =∑ ℎ=1 ( !81:ℎπ: (π 81:ℎ−1 :+1 , c 8ℎ :+1) − a max KL (c 8ℎ : , c 8ℎ :+1) ) , (13)
and as for every ℎ, c8ℎ :+1 is the argmax, this is lower-bounded by ≥ (π: ) + =∑ ℎ=1 ( !81:ℎπ: (π 81:ℎ−1 :+1 , c 8ℎ : ) − a maxKL (c 8ℎ : , c 8ℎ : ) ) ,
which, as follows from Definition 1, equals = J (πk ) + =∑ ℎ=1 0 = (π: ), which finishes the proof.

heading: C AUXILIARY RESULTS FOR IMPLEMENTATION OF MACPO
text: Theorem 2. The solution to the following problem
p∗ = min G g)x
s.t. b)x + 2 ≤ 0 x)Hx ≤ X,
where g, b,x ∈ ℝ=, 2, X ∈ ℝ, X > 0,H ∈ =, andH 0. When there is at least one strictly feasible point, the optimal point x∗ satisfies:
x∗ = − 1 _∗ H−1
( g) + E∗b ) where _∗ and E∗ are defined by
E∗ = ( _∗2 − A B ) +
_∗ = arg max _≥0
{ 50 (_) , 12_ ( A2 B − @ ) + _2 ( 22 B − X ) − A2 B if _2 − A > 0
51 (_) , − 12 ( @ _ + _X ) otherwise
where q = g)H−1g, r = g)H−1b, and s = b)H−1b.
Furthermore, let Λ0 , {_ | _2 − A > 0, _ ≥ 0}, and Λ1 , {_ | _2 − A ≤ 0, _ ≥ 0}. The value of _∗ satisfies
_∗ ∈ _0∗ , Proj ©« √ @ − A2/B X − 22/B ,Λ0 ª®¬ , _1∗ , Proj (√ @ X ,Λ1 ) (14) where _∗ = _0∗ if 50 ( _0∗ ) > 51 ( _1∗ ) and _∗ = _∗ otherwise, and Proj(0,S) is the projection of a point G on to a set S. Note the projection of a point G ∈ ℝ onto a convex segment of ℝ, [0, 1], has value Proj(G, [0, 1]) = max(0,min(1, G)).
Proof. See Achiam et al. (2017) (Appendix 10.2).

heading: D MACPO
text: Algorithm 2: MACPO 1: Input: Stepsize U, batch size , number of: agents =, episodes , steps per episode ) , possible
steps in line search !. 2: Initialize: Actor networks {\80, ∀8 ∈ N}, Global V-value network {q0}, Individual +
8-cost networks {q8
9 ,0}8=1:=, 9=1:<, Replay buffer B 3: for : = 0, 1, . . . , − 1 do 4: Collect a set of trajectories by running the joint policy πθ: = (c1\1
:
, . . . , c= \= : ). 5: Push transitions {(>8C , 08C , >8C+1, AC ),∀8 ∈ N , C ∈ )} into B. 6: Sample a random minibatch of " transitions from B. 7: Compute advantage function ̂(s, a) based on global V-value network with GAE. 8: Compute cost-advantage functions ̂8
9 (s, a8) based on individual + 8-cost critics with GAE.
9: Draw a random permutation of agents 81:=. 10: Set " 81 (s, a) = ̂(s, a). 11: for agent 8ℎ = 81, . . . , 8= do 12: Estimate the gradient of the agent’s maximisation objective
ĝ8ℎ : = 1 ∑ 1=1 )∑ C=1 ∇ \ 8ℎ : log c8ℎ \ 8ℎ : ( 0 8ℎ C | > 8ℎ C ) " 81:ℎ (BC ,aC ).
13: for 9 = 1, . . . , <8ℎ do 14: Estimate the gradient of the agent’s 9 th cost
b̂8ℎ 9 = 1 ∑ 1=1 )∑ C=1 ∇ \ 8ℎ : log c8ℎ \ 8ℎ : ( 0 8ℎ C |> 8ℎ C ) ̂ 8ℎ 9 (BC , 08ℎC ).
15: end for 16: Set B̂8ℎ = [ b̂8ℎ1 , . . . , b̂ 8ℎ < ] . 17: Compute Ĥ 8ℎ : , the Hessian of the average KL-divergence
1 ) ∑ 1=1 )∑ C=1 KL ( c 8ℎ \ 8ℎ : (·|>8ℎC ), c 8ℎ \ 8ℎ (·|>8ℎC ) ) .
18: Solve the dual (5) for _8ℎ∗ , v 8ℎ ∗ .
Use the conjugate gradient algorithm to compute the update direction x8ℎ : = (Ĥ 8ℎ : )−1 ( g8ℎ : − B̂8ℎv8ℎ∗ ) ,
19: Update agent 8ℎ’s policy by \ 8ℎ :+1 = \
8ℎ : + U 9 _ 8ℎ ∗ x̂8ℎ : ,
where 9 ∈ {0, 1, . . . , !} is the smallest such 9 which improves the sample loss, and satisfies the sample constraints, found by the backtracking line search.
20: if the approximate is not feasible then 21: Use equation (6) to recover policy \8ℎ
:+1 from unfeasible points. 22: end if 23: Compute " 81:ℎ+1 (s, a) = c 8ℎ \ 8ℎ :+1 (a8ℎ |o8ℎ )
c 8ℎ
\ 8ℎ :
(a8ℎ |o8ℎ ) " 81:ℎ (sC , aC ). //Unless ℎ = =.
24: end for 25: Update V-value network by following formula:
26: q:+1 = arg minq 1N 1 ) N∑ ==1 )∑ C=0 ( +q (BC ) − '̂C )2 27: end for

heading: E MAPPO-LAGRANGIAN
text: Algorithm 3: MAPPO-Lagrangian 1: Input: Stepsizes U\ , U_, batch size , number of: agents =, episodes , steps per episode ) ,
discount factor W. 2: Initialize: Actor networks {\80, ∀8 ∈ N}, Global V-value network {q0},
V-cost networks {q8 9 ,0} 8∈N 1≤ 9≤<8 , Replay buffer B.
3: for : = 0, 1, . . . , − 1 do 4: Collect a set of trajectories by running the joint policy πθ: = (c1\1
:
, . . . , c= \= : ). 5: Push transitions {(>8C , 08C , >8C+1, AC ),∀8 ∈ N , C ∈ )} into B. 6: Sample a random minibatch of transitions from B. 7: Compute advantage function ̂(s, a) based on global V-value network with GAE. 8: Compute cost advantage functions ̂8
9 (s, a8) for all agents and costs,
based on V-cost networks with GAE. 9: Draw a random permutation of agents 81:=.
10: Set " 81 (s, a) = ̂(s, a). 11: for agent 8ℎ = 81, . . . , 8= do 12: Initialise a policy parameter \8ℎ = \8ℎ
: ,
and Lagrangian multipliers _8ℎ 9 = 0, ∀ 9 = 1, . . . , <8ℎ .
13: Make the Lagrangian modification step of objective construction " 8ℎ , (_) (sC , aC ) = " 8ℎ (sC , aC ) − =∑ 9=1 _ 8ℎ 9 ̂ 8ℎ 9 (sC , a8ℎC ). 14: for 4 = 1, . . . , 4PPO do 15: Differentiate the Lagrangian PPO-Clip objective
Δ\ 8ℎ = ∇\ 8ℎ 1 ∑ 1=1 )∑ C=0 min ©« c 8ℎ \ 8ℎ ( 0 8ℎ C |> 8ℎ C ) c 8ℎ \ 8ℎ : ( 0 8ℎ C |> 8ℎ C )" 8ℎ , (_) (BC ,aC ), clip ©« c 8ℎ \ 8ℎ ( 0 8ℎ C |> 8ℎ C ) c 8ℎ \ 8ℎ : ( 0 8ℎ C |> 8ℎ C ) , 1 ± nª®¬" 8ℎ , (_) (BC ,aC )ª®¬. 16: Update temprorarily the actor paramaters \8ℎ ← \8ℎ + U\Δ\ 8ℎ . 17: for 9 = 1, . . . , <8ℎ do 18: Approximate the constraint violation
3 8ℎ 9 = 1 ) ∑ 1=1 )∑ C=1 +̂ 8ℎ 9 (BC ) − 28ℎ9 .
19: Differentiate the constraint
Δ_8ℎ 9 = −1 ∑ 1=1 ©«38ℎ9 (1 − W) + )∑ C=0 c 8ℎ \ 8ℎ (08ℎC |> 8ℎ C ) c 8ℎ \ 8ℎ : (08ℎC |> 8ℎ C ) ̂ 8ℎ 9 (BC , 08ℎC ) ª®¬. 20: end for 21: for 9 = 1, . . . , <8ℎ do 22: Update temporarily the Lagrangian multiplier
_ 8ℎ 9 ← ReLU ( _ 8ℎ 9 − U_Δ_8ℎ9 ) .
23: end for 24: end for 25: Update the actor parameter \8ℎ
:+1 = \ 8ℎ .
26: Compute " 8ℎ+1 (s, a) = c 8ℎ \ 8ℎ :+1 (a8ℎ |o8ℎ )
c 8ℎ
\ 8ℎ :
(a8ℎ |o8ℎ ) " 8ℎ (s, a). //Unless ℎ = =.
27: end for 28: Update V-value network (and V-cost networks analogously) by following formula:
29: q:+1 = arg minq 1 ) ∑ 1=1 )∑ C=0 ( +q (BC ) − '̂C )2 30: end for

heading: F SAFE MULTI-AGENT MUJOCO
text: Safe MAMuJoCo is an extension of MAMuJoCo (Peng et al., 2020). In particular, the background environment, agents, physics simulator, and the reward function are preserved. However, as oppose to its predecessor, Safe MAMuJoCo environments come with obstacles, like walls or bombs. Furthermore, with the increasing risk of an agent stumbling upon an obstacle, the environment emits cost (Brockman et al., 2016). According to the scheme from Zanger et al. (2021), we characterise the cost functions for each task below.
MANYAGENT ANT & ANT
The width of the corridor set by two walls is 9<(ManyAgent Ant), The width of the corridor set by three folding line walls with an angle of 30 degrees is 10<(Ant). The environment emits the cost of 1 for an agent, if the distance between the robot and the wall is less than 1.8<, or when the robot topples over. This can be described as
cC = { 0, for 0.2 ≤ ztorso ,C+1 ≤ 1.0 and
xtorso ,C+1 − xwall 2 ≥ 1.8 1, otherwise .
where ztorso ,C+1 is the robot’s torso’s I-coordinate, and xtorso ,C+1 is the robot’s torso’s G-coordinate, at time C + 1; xwall is the G-coordinate of the wall.
HALFCHEETAH & COUPLE HALFCHEETAH
In these tasks, the agents move inside a corridor (which constraints their movement, but does not induce costs). Together with them, there are bombs moving inside the corridor. If an agent finds itself too close to a bomb, the distance between an agent and a bomb is less than 9<, a cost of 1 will be emitted.
cC = { 0, for
ytorso ,C+1 − yobstacle 2 ≥ 9 1, otherwise .
where ytorso ,C+1 is the H-coordinate of the robot’s torso, and yobstacle is the H-coordinate of the moving obstacle.

heading: G EXPERIMENTS IN SAFE MANY-AGENT ANT ENVIRONMENTS
text: We provide additional results on the Safe Many-Agent ant tasks.
The width of the corridor is 12<; its walls fold at the angle of 30 degrees. The environment emits the cost of 1 for an agent, if the distance between the robot and the wall is less than 1.8<, or when the robot topples over. This can be described as
cC = { 0, for 0.2 ≤ ztorso ,C+1 ≤ 1.0 and
xtorso ,C+1 − xwall 2 ≥ 1.8 1, otherwise .
where ztorso ,C+1 is the robot’s torso’s I-coordinate, and xtorso ,C+1 is the robot’s torso’s G-coordinate, at time C + 1; xwall is the G-coordinate of the wall.

heading: H DETAILS OF SETTINGS FOR EXPERIMENTS
text: In this section, we introduce the details of settings for our experiments. The code is available at https://github.com/Anonymous-ICLR2022/ Multi-Agent-Constrained-Policy-Optimisation

Review summaries:
This paper studies the safe RL in the multi-agent setting. Specifically, the author leverage the theories from constrained policy optimization and multi-agent trust region learning to propose two algorithms: MACPO and MAPPO-Lagrangian. From the theoretical side, the author shows that in the idea setting, the proposed algorithm is guarantee to improve the objective function at iteration and the constraint satisfications can always be guaranteed. The author also demonstrate the effectiveness of their proposed algorithms in the new environment named "Safe MAMuJoCo".

This paper considers the multi-agent reinforcement learning (MARL) problem with safety constraints. The authors proposed two methods, Multi-Agent Constrained Policy Optimisation (MACPO) and MAPPO-Lagrangian, by leveraging the theories from both constrained policy optimization and multi-agent trust-region learning. Their method is shown valid both theoretically and empirically. My main concerns lie in their novelty compared with existing literature and the problem set.