Multi-Agent Constrained Policy Optimisation 
Authors: Shangding Gu
Jakub Grudzien Kuba
Muning Wen
Ruiqing Chen
Ziyan Wang
Zheng Tian
Jun Wang
Alois Knoll
Yaodong Yang
Venue: ICLR 2022 Submitted (2022)
Keywords: Safe Multi-Agent Reinforcement Learning
Safe Multi-Agent Trust Region Policy Optimisation
Safe Multi-Agent Proximal Policy Optimisation
Constrained Policy Optimisation

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 multi-agent 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.

Under review as a conference paper at ICLR 2022
MULTI-AGENT CONSTRAINED POLICY OPTIMISATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Developing reinforcement learning algorithms that that satisfy safety constraints is be- coming increasingly important in real-world applications. In multi-agent rein- forcement 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 be- haviour be guaranteed safe. Despite its importance, the problem of safe multi- agent learning has not been rigorously studied; very few solutions have been pro- posed, nor sharable testing environment 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 strained Policy Optimisation (MACPO) and HAAPPO-Larrangian leveergg 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 MARL baselines. Experimental results justify that MACPO//APPO-Lagrrn constraints, meanwhile achieving comparable performance to strong baselines."
-Muli--gent Con-
consistently satisfy safety
INTRODUCTION
In recent years, reinforcement learning (RI. 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 neu- ral 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 up- dated in the direction of the gradient that maximises return.
However, policies that purely optimised for reward maximisation rarely applicable real- world 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 back- ground (Moldovan & Abbeel, 2012; Achiam et al., 2017). For instance, robot carrying materials a warehouse should not damage its parts while delivering an item shelf, nor should a self- driving car cross on the red light while rushing towards its destination (Shalev-Shwant et al., 2016). To tackle these issues, Safe RL (Moldovan & Abbeel, 2012; Gareia & Ferná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 al., 2021).
Developing safe policies for multi-agent systems is a challenging task. Part 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;
Paper homepage including Videos Code: hat /// //st // tes .oogg oom/vv' ew/ ew/macpo

---

Under review as a conference paper at ICLR 2022
Yang & Wang, 2020). However, they often require certain structures the solution; for example, Rashid et al. (2018) and Yang et al. (2020) adopt greedy maximisation on the local component of 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' collahorations 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 bench- mark within the MuJoCo environment, which include a variety of MARL baseline algorithms. We evaluate MACPO and MAPPO- MAPPO-Lagrangian fectiveness 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 MuloCo tasks with safety constraints.
series of tasks, and results clearly confirm the ef-
RELATED WORK
Considering safety in the development of Al is a long-standing topic (Amodei et al., 2016). When comes to safe reinforcement learning (Garcia & Fernández, 2015), a commonly used framework is Constrained Markov Decision Processes (CMDPs) (Altman, 1999). In 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, 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-agen learning is an emerging research domain. Despite its importance (Shalev- Shwartz al., 2016), there few solutions that work with MARI. in 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 decentralised policy descent-ascent method through a consensus network. How- ever, 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, 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-justffeeed monotonic improvement guarantee. Its key idea is to make agents follow
2

---

Under review as a conference paper at ICLR 2022
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 every iteration during learning. The resulting algorithm (Algorithm 1) successfully attains theoreti- cal guarantees of both monotonic improvement in reward and satisfaction of safety constraints.
3 PROBLEM FORMULATION: CONSTRAINED MARKOV GAME
We formulate the safe MARL problem as constrained Markov game S, A, p.p", C) Here, N = .n} is the set of agents, S the state space, A [T==1 म' the product of the agents' action spaces, known as the joint action space, p S x A x S R is the probabilistic transition function, , is the initial state distribution, y E [0. 1) is the discount factor, SXX - R the joint reward function, C (C))ss)mm sm is the set of sets of cost functions (every agent has m²
cost functions) of the form C₁ S R, and finally the set of corresponding cost-constraining values is given by c= (c/) isj At time step i, the agents are a state S,, and every agent takes an action af according to its policy r' (s Together with other agents' actions, it gives a joint action a, = (a...... a/") and the joint policy (aas)) = IT; x' (a'ls). The agents receive the reward R(,, a,), meanwhile each agent pays the costs (s. a/), Vj = l,..., m'. The environment then transits to new state S,+1 ~ p(lss, a,). In this paper, we consider fully-cooperative setting where all agents share the same reward function, aiming maximise the expected total reward of
( A Exg-p
R(s, a,)
meanwhile trying to satisfy every agent i's safety constraints, written as
(TT 2 Expp' Ao
Σ
a))
20
s cfj.
m'
(I)
We define the state-action value and the state-value functions in terms of reward as
y' (R)s,, s. =a]. and V*(s) A Fa-x (Qx
(s, A E B - po
The joint policies π that satisfy the Inequality (1) are referred to as feasible. Notably, in the above formulation, although the action af of agent i does not directly influence the costs (C),,, a ) of other agents + the action aद will implicitly influence their total costs due to the dependence on the next state S,+1 2. For the fth cost function of agent we define the jth state-action cost value function and the state cost value function as
(s, A En-tar Maa
s. s. =aa Σ Y (s).a))
and, (s) 2 Ba-T. Paal T
Σ r' () s0==00 =s] respectively. 1=0
Notably, the cost value functions 2/,,. and V j. although similar to traditional Qx and Vz, involve extra indices and j: the superseript denotes an agent, and the subscript j denotes its 7th 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
We believe that this formulation realistically describes ageti- 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 car that crosses on the red light, although other cars may be risk of riding into pedestrians immediately, the induced traffic may hazards later.
3

---

Under review as a conference paper at ICLR 2022
ff....., in of agents as finh's write 1f to refer to its complement. Given the agent subset 11:hs we define the malti-agent state-action value function:
2 (s, a ff Ba fh 1 a fi a ahm)]
On top of it, the multi-agent advantage function is defined follows,
A lu (s, fix a a² _ @ (s, a1 a - Q (s, a
(2)
An interesting fact about the above multi-agent advantage function is that any advantage A can be written as sum of sequentially
multi-agent advantages of individual agents, that is,
Lemma 1 (Multi-Agent Advantage Decomposition, Kuba et al. (2021b)). For any state S, subset of agents i E N, and joint action alth,, the following identity holds
h
ffil (s, afti
Σ
a .dt).
MULTI-AGENT CONSTRAINED POLICY OPTIMISATION
In this section, we first present a theoretically-justffee safe multi-agent policy iteration procedure, which leverages multi-agent trust region learning and constrained policy optimisation to solve con- strained 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, refer the symbols π and मे to be the "current" and the "new" joint policies, respectively.
4.1 MULTI-AGENT TRUST REGION LEARNING WITH CONSTRAINTS
Kuba et al. (2021a) introduced the first agent trust region method HATRPO that enjoys pheoreticallyjjustffe monotonic improvement guarantee. Specifically, it relies on the multi-agent advantage decomposition in Lemma I, and the "surrogate" return that is given as follows.
Definition 1. Let π be a joint policy, म (ina- be some other joint policy of agents f1 and 4t be policy of agent in. Then we define
L Luk (7 iu 1'1) A as-pnaalta-- -/1--111-1---///- 26th [A (s, fite- a²" )
With the above definition, we can see that Lemma allows for decomposing the joint surrogate return L (T) a- [ a)] into a sum over surrogates of L (ffis-1,#()) for h I.....n. n. This can be used justify that if agents, with joint policy π,, update their policies by following sequential update scheme, that is, if each agent in the subset i1sh sequentially solves the following optimisation problem:
- max 1ith (f/ 8thh mum (rthh, A²h). *
4y max,, IA a))
where y
and D (x A'n) max DEL (n (-1s), (-Iss)),
(1-y)2
then the resulting joint policy म will surely improve the expected return, i.e., (( ) 2 ((T)) (see the proof Kuba al. (2021a, Lemma 2)). We know that due the penalty term D (T²" *h),, the new policy Hh will stay close (w.zt max-KL distance) -"
For the safety constraints, we can extend Definition I to incorporate the "surrogate" cost, thus al- lowing us to study the cost functions addition to the return.
Definition 2. Let be joint policy, and म! be some other policy of agent i. Then, for any of its costs of index E (1...., m² }, we define
1) (5') - E.ppp
A/ as.
We would like to highlight that these multi-agent functions of O'1 and ALth although involve agents in superscripts, describe values the reward rather than costs since they do involve cost subscripts.
4

---

Under review as a conference paper at ICLR 2022
By generalising the result about the surrogate return in Equation (I), we can derive how the expected costs change when the agents update their policies. Specifically, we provide the following lemma.
Lemma 2. Let at and it be joint policies. Let i E N be an agent, and j (l.....m) be an index of one of is costs. The following inequality holds
4y maxx, |4 a')
11(+) - (T( + 1 (F)) + +2
D
max
KL (x" x²"). where v/
(1 7)2
See proof in Appendix A. The above lemma suggests that, as long as the distances between the policies x² and H², Yh N, are sufficiently small, then the change in the jth cost of agent i, i.e., - is controlled by the surrogate L', (7'). Importantly, this surrogate is independent of other agents' new policies. Hence, when the changes in policies of all agents sufficiently small, each agent can learn a better policy ø' 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 To = (TT...... T())
2: for k 0, I.... do
3: Compute the advantage functions Arg (s, a) and A J. (s, a'), for all state- pairs m²). 4: Compute y 4y maks,a IA (5,0)) and vi my a 1A (s,at)) (1-y)²
(s, a), agents i, and constraints j E (I....,m)).
Vi Vi N.J I.....m'.
(1-x)²
5: Draw permutaion 11:0 of agents random.
6: for == do
7: Compute the radius of the KL-constraint 8th II see Appendix B for the setup of 8
8: Make an update x = arg max x'n ent"
Lie (nata- _x")) v.D th x K1. (*
where I is subset of safe policies of agent in. given by
DRLL (x x² s 8hh and T f E I
h-1
J/ (TTL)
m. (zth) + v/ man ( xhh) c
Σ v
(xt) (),, Vj =I..., m²th
KL
1=1
9: end for 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.rt max-KL distance). As such, Algorithm 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 (TT)) is obtained from Algorithm then it has the monotonic improvement property, J(TK+1) 2 J(Tx), as well as it satisfies the safety constraints, (T(TT)) S for all k E N.i N. and j E (I.....m").
See proof in Appendix B. The above theorem assures that agents that follow Algorithm I will only explore safe policies; meanwhile, every new policy will be guaranteed result 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 's objective (i.c., yD (n²) x²")), as well
as the constraints on cost surrogates (i.e., the conditions in II"), In practice, it can be intractable to evaluate D (nth (-Is), Thhh (-1s)) every state in order compute Dmax (nrhe x²*). ) In the following subsections, we describe how we can approximate Algorithm in the case of parameterised policies, similar to TRPO/PPO implementations (Schulman al., 2015; 2017).
5

---

Under review as a conference paper at ICLR 2022
4.2 MACPO: MULTI-AGENT CONSTRAINED POLICY OPTIMISATION
Here we focus on the practical settings where large state and action spaces prevent agents from des- ignating policies x' r-(ss) for each state separately. To handle this, we parameterise each agent's xr' or by a neural network 0'_ Correspondingly, the joint policies B are parametrised by 0 =
00).
Let's recall that every iteration of Algorithm every agent i, maximises its surrogate return with a KL-penalty, subject to surrogate cost constraint. Yet, direct computation of the max-KL. constraint intractable in practical settings, it would require computation of KI. Kl--divereence at every single state. Instead, one can relax it by adopting a form of expected KL-constraint D ( x²h) s where DKL( xTh) å Ex-por [DxL (T x- (-Is))] Such an expectation can be approximated by stochastic sampling. As result, the optimisation problem solved by agent in is written as
o arg max E g/n
A Toz
(s. afinn-,,
s-pmos a/ fuh-1 d'tth-1
o'n
s.t. 1/t (TT,,) + s-prop allwss A4 (A d
(s.aft)
s scy, vj (1, m!.
and DKL ( x²hh 5.
(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
8hh k+1 arg max (g (0th -
s.t. dh + (b)2)) (8th - -8%² ) S.
l......,
and 10th ) H (8th 0/% 56
(4) where 9t is the gradient of the objective of agent in in Equation (3), di = (T)) c/,, and H = V2 Ghh (T (1") ooh the Hessian the average KL divergence of agent in, and b"r
d/
is the gradient of agent of the 1hh constraint of agent in-
Similar Chow al. (2017) and Achiam et al. (2017), one can take primal-dual optimisation approach to solve the linear quadratic optimisation in Equation (4). Specifically, the dual form can be written as:
"(gh)²" (H*)-1g" 2( 8t + (v"h)² 5hh + (v"h)² ( dh 2
max 20
2
where b A (g - Bhh = 1 b/h and S (B")² -I
(5)
Given the solution to the dual form in Equation (5), i.e., 2h and !h the solution to the primal problem in Equation (4) can thus be written by
8 = 60hh (H") -B"h"""))
In practice, we use backtracking line search starting at 1/2" to choose the step size of the above update. Furthermore, we note that the optimisation step in Equation (4) is an approximation the original problem from Equation (3); therefore, it is possible that an infeasible policy ge will be
generated. Fortunately, as the policy optimisation takes place the trust region of th the size of 8% update is small, and a feasible policy can be easily recovered. In particular, for problems with one safety constraint, i.e., m 1, one can recover a feasible policy by applying a TRPO step on the cost surrogate, written
28
1 0% - -aa bin? (Hin)-1
( -bh
(6)

---

Under review as a conference paper at ICLR 2022
where a is adjusted through backtracking line search. To put it together, refer to this algorithm as MACPO, and provide its pseudocode in Appendix D.
4.3 MAPPO-LAGRANGIAN
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 simple to implement, and it does not require computations of the Hessian Ht whose size grows quadratically with the dimension of the parameter vector 6th.
Before proceed, let us briefly recall the optimisation procedure with Lagrangian multiplier. Suppose that our goal is to maximise a bounded real-valued function f(x) under constraint gxx); maxx (xx,, s.t. g (xx) s O. We can introduce scalar variable and reformulate the optimisation by max min f(x) - Ag(x).
(7)
120
Suppose that x, satisfies g(xx) > O. This immediately implies that -xg(xx) - -00, as +00, and Equation (7) equals -oo for xt, On the other hand, if satisfies g(x_) S O, have that (x_(x_) 2 O, with equality only for 2 O. In that case, the optimisation objective's value equals f(x)) > -c0, Hence, the only candidate solutions to the problem are those x that satisfy the constraint gxx s 0, and the objective matches with f(x).
We can employ the above trick to the constrained optimisation problem from Equation (3) by sub- suming the cost constraints into the optimisation objective with Lagrangian multipliers. As such, agent computes 1 and L+1 to solve the following min-max optimisation problem
Tamh'
AAlto, (s. asa aaa1
min max 2h
Pea a aih-
11h-1
20 0%
n'n
(Alimor (s. (s. {
IB
saproo s-proy stn
uml
s.t. DKL (1
5.
(8)
0%
Although the objective from Equation (8) affine the Lagrangian multipliers 2 (u = l.... m²) which enables gradient-basse based optimisation solutions, computing the KL-divergence constraint still complicates the overall process. To handle this, one can further simplify 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
(nr(d) (s. a
fite-1 ,a')) a Ao (s, ia-1 ,a"")
Σ 4=1
2in
(Ali
(s.a") d%
Amez
and rewriting the Equation (8)
min a Lomhh
max EE
s-Pno a 11 11--1
1/4 o1
AA
(s, 2in--1 ati)] a5.
20
8th
1120-1
s.t. D H
n S 6.
The objective in Equation (9) takes a form of expectation with quadratic constraint the policy. Up to the error of approximation of KL-constraint with the clip operator, it can be equivalently transformed into an optimisation of clipping objective. Finally, the objective takes the form of
(a (s) 4'h
B s-pang a a 91h-- 2/k 1n
min
(n-((0) A
(s. a fib--1 _ a²))
(ath Is)
201
th clip
(ath
+ A (s, as, 12a) ]]
ohh
(10)
(a'n 8

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
Figure/ 1: Example tasks in Safe Multi-Agent MuloCo Environment. (a): Safe 2x4-Ant, (b); Safe 4x2-Ant, (c): Safe 2x3-HaliCheetah. Body parts different colours are controlled by different agents. Agents jointly learn to manipulate the robot, while avoiding crashing into unsafe red areas.
The clip operator replaces the policy ratio with 1 6, or + depending on whether its value is below above the threshold interval. As such, agent 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- MAAPPO-Laraanginn, and give a detailed pseudocode of it in Appendix E.
5 EXPERIMENTS
Although MARI researchers have long had variety of environments to test different algorithms, such as StarCraftII (Samvelyan et al., 2019) and Multi-gentt MuJoCo (Peng et al., 2020), no public safe MARL benchmark has been proposed: this impedes researchers from evaluating and bench- marking safety-aware multi-agent learning methods. As a key contribution of this paper, we intro- duce Safe Multi-Agent MuJoCo Benchmark, 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-awar agents have learn not only skilful manipulations of 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//APPO-Lagrannee 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 MAPPO- Lagrangian maintains rather soft safety awareness by performing gradient descents on the PPO- clip 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 three-folds; each subfigure represents a different robot, within each subfigure, three task setups in terms multi- agent control are considered, for each task, we plot the 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.
agents can satisfy
The experiments reveal that both MACPO and MAPPO-Lagrangiaa quickly learn to satisfy safety constraints, and keep their explorations within the feasible policy space. This stands in contrast 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-Lagrange 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.
is better than of MACPO;
6 CONCLUSION
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 theoreticalll-justffee monotonic improvement guarantee and constraints satisfaction guarantee at every iteration during learning. Based on this, we proposed two practical algorithms: MACPO and MAPPO-Lagranginn To demonstrate their effectiveness, we introduced a new benchmark suite of Safe Multi-Agent Mu- JoCo and compared our methods against strong MARI. haselines. Results show that both of our methods can significantly outperform existing state-of-the-ar methods such as IPPO, MAPPO and HAPPO in terms of safety, meanwhile maintaining comparable performance in terms of reward.
8

---

Under review as a conference paper at ICLR 2022
ManyAgent Ant 2x3
ManyAgent Ant 3x2
ManyAgent Ant 6x2
Auarage Ephodd Cvxt
404
Ruarage Epkode Dent
MAGRO oeend
Epkode
WAPAD- (huro
Environment steps
Environment steps
Environment stops
ManyAgent Ant 2x3
ManyAgent Ant 3x2
ManyAgent Ant 6x2
Averogg Epiicde Reward
JWPC sg LOISTOS MOwarO
VATRO
MA-F3 tours
FPO
Environment steps
Environment steps
Environment steps
(a) Safe AanyAgent Ant: 2x3-Agent (left), 3x2-Agent (middle), 6x 6x1-Agent (right)
Ant
2x4d
Episnde Oest
Avarage Epicade CxeT
PACPP rouns) MARRC- (eart) PPO
Avarage Ephinde
Environment stops
Environment steps
Environment stops
Average Eplods Roward
Average Epicode Roward
300
VALPF rour))
MARAD- (evrrs
PTO
1.0
00
Environment steps
Environment steps
Environment steps
(b) Safe Ant: 2x4-Agent (left), 4x2-Agent (middle), 2x4d 2x4d-Agent (right)
HallCheetah
HallCheetah
Avorage Eqiladd Cont
Episode
MARRO (ouum
Ausrage
Environment
Environment
Environment
HalfChectah
HalfCheetah
Average Eplocde Reward
600
Average Epicode Reward
HAPPO
MARAC- (eart PPC
Average
Environment
Environment
"Enviionment steps
Safe HalfCheetah: 2x3-Agent (left), 3x2-Agent (middle), 6x1 6x1-Agent (right)
Figure 2: Performance comparisons on tasks of Safe ManyAgent Ant, Safe Ant, and Safe HalfChee- tah terms of cost (the first row) and reward (the second row). The safety constraint values are: for Many Agent Ant, 0.2 for Ant, and for HalfCheetah. Our methods consistently achieve almost zero costs, thus satisfying safe constraints, on all tasks. In terms of reward, our methods outperform IPPO and MAPPO on some tasks but underperform HAPPO, which is also unsafe algorithm.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference Machine Learning, pp. 22-31. PMLR, 2017.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Aaron D Ames, Xiangru Xu, Jessy W Grizzle, and Paulo Tabuada. Control barrier function based quadratic programs for safety critical systems. IEEE Transactions on Automatic Control, 62(8): 3861-3876, 2016.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Con- crete problems in ai safety. arXiv preprint arXiv: 1606. 06565, 2016.
Urs Bormann,, Li Wang, Aaron D Ames, and Magnus Egerstedt. Control barrier certificates for safe swarm behavior. WFAC-PaperSOnL.ine, 48(27):68873 2015.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained re- inforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18 (1):6070-6120, 2017.
Yinlam Chow, Ofir Nachum, Edgar
and Mohammad Ghavamzadeh. A Iyapunov-
based approach safe reinforcement learning. arXiv preprint arXiv:1805.007703 2018.
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. Lyapunov-based safe policy optimization for continuous control. arXiv preprint 1rXiv:1901.10031, 2019.
Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:2011.0955 2020.
Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, and Yaodong Yang. On the complex- ity of computing markov perfect equilibrium in general-sum stochastic games. arXiv preprint arXiv:2 2021.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Javier Garcia and Fernando Fernández. A comprehensive survey on safe reinforcement learning.
Journal of Machine Learning Research, 16(1):1437-1480, 2015.
Jakub Grudzien Kuba, Ruiqing Chen, Munning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. arXiv preprint arXiv:2 109. /251, 2021a.
Jakub Grudzien Kuba, Muning Wen, Yaodong Yang, Linghui Meng, Shangding Gu, Haifeng Zhang, David Henry Mguni, and Jun Wang. Settling the variance of multi- policy gradients. arXiv preprint
2021b.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:/509.0000 2015.
Songtao Lu, Kaiqing Zhang, Tianyi Chen, Tamer Basar, and Lior Horesh. Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8767-8775, 2021.
Teodor Mihai Moldovan and Pieter Abbeel. Safe exploration in markov decision processes. In Pro- ceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1451-1458, 2012.
10

---

Under review as a conference paper at ICLR 2022
Bei Peng. Tabish Rashid, Christian A Schroeder de Witt, Torr, Wendelin Böhmer, and Shimon Whiteson. Facmac: Factored multi- centralised policy gradients. arXiv preprint arXiv:2003.06709, 2020.
Kamienny, Philip HS
David Pollard. Asymptopia: an exposition of statistical asymptotic theory. 2000. URL http://www. stat. yale. eluupollard/booksyymppppppu 2000.
Zengyi Qin, Kaiqing Zhang, Yuxiao Chen, Jingkai Chen, and Chuchu Fan. Learning safe multi-agent control with decentralized neural barrier certificates. In International Conference on Learning Representations, 2020.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and
Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforce- ment learning. In International Conference on Machine Learning, pp. 4295-4304. PMIR, 2018.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep reinforcement learning. arXiv preprint arXiv: 1910.0170,, 2019.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob Foerster, and Shimon Whiteson. 2019.
The starcraft multi-agent challenge. arXiv preprint
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning. pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.066: 2017.
Shai Shalev-Shwards Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03225, 2016.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwiesee, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484-488) 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-335 2017.
Richard Sutton, David McAllester, Satinder P Singh, Yishay Mansour, al. Policy gradient methods for reinforcement learning with function approximation. In NIPs, volume 99, pp. 1057- 1063. Citeseer, 1999.
Oriol Vinyals, Igor Babuschkin, Wojeiech Czamnekki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 375(7782)350--35, 2019.
Honghao Wei, Xin Liu, and Lei Ying. A provably-efficiiet model-free algorithm for constrained markov decision processes. arXiv preprint arXiv:2106.01577. 2021.
Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning. pp- 11480-11491. PMLR. 2021.
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theo- retical perspective. arXiv preprint vrXiv:2011.0058. 2020.
Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang. Multi-agent determinantal q-learning. In International Conference on Machine Learning, pp- 10757-10766. PMLR, 2020.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXi::2103.01955, 2021.
11

---

Under review as a conference paper at ICLR 2022
Moritz A. Zanger, Karam Daaboul, and J. Marius Zöllner. Safe continuous control with constrained mosel-based policy optimization, 2021.
Wenbo Zhang, Osbert Bastani, and Vijay Kumar. Mamps: Safe multi-agent reinforcement learning via model predictive shielding. arXiv preprint arXiv: 12639, 2019.
12

---

Under review as a conference paper at ICLR 2022
Appendices
A Proofs of preliminary results
14
Auxiliary Results for Algorithm
15
C Auxiliary Results for Implementation of MACPO
17
D MACPO
18
MAPPO-Lagrangian
19
F Safe Multi-Agent MuJoCo
20
G Experiments in Safe Many-Agent Ant Environments
21
Details of Settings for Experiments
22
13

---

Under review as a conference paper at ICLR 2022
A PROOFS OF PRELIMINARY RESULTS
Lemma 1 (Multi-Agent Advantage Decomposition, Kuba et al. (2021b)). For any state S, subset of agents 11sh S N, and joint action alia, the following identity holds
h
A (s, a affin = Σ 1
Proof. We write the multi-agent advantage as in its definition, and expand it in a telescoping sum. huu (s, a du))
t (s, a all)) V (s)
ty (s, a')) -x fiust (s, (s.a
A (s, a'aiv-11
Lemma 2. Let and N be joint policies. Let N be an agent, and (I.....m')) be an index of one of its costs. The following inequality holds
4y max IA), a')l
(+) s )J) + Lj (x') + t,
max [xth H²),. where v/
(1 (1-
Proof. From the proof of Theorem from Schulman et (2015) (in particular, equations (41)-(45)), applied to joint policies π and म. we conclude that
4a2y max,.at 14), (s,
()(+) s (TT) Es-pa a A (s, at)
(1-7)2
where
a = DTv (TT, π. max D Drv (TT-)s),
Using the inequality Drv(p.q)2 DKL q) (Pollard, 2000; Schulman et al., 2015), we obtain
T)(T)) s (J((T) Es- u- At (s. at) 4y max |A),n (s,
Kl. (T, R),
(1 (1-
where
D kl. (TT, H) max DKL (r(-1s))+(-ls)))
Notice now that we have Es-pm.a- # A j. (s,
Es-paai-
A (f,
(s, (s. and
DKL. (st (1s) ((1)) T πt) = max DRI. (TT(1)), +((1s) max Σ
D max KL.
1=1
max DKL (zr (-(ss, ((1ss)
max
(11)
KL
4y max, IA (s.a")
Setting v)
we finally obtain
(1-y)²
1)(()) (T( + L/,, (7') rf
max
( x
14

---

Under review as a conference paper at ICLR 2022
B AUXILIARY RESULTS FOR ALGORITHM
Remark 1. In Algorithm I, we compute the size of KL constraint as
-4
Lj (xt vi Enenl Da (T R x
8hh min
min 1sh | 1s
min
vij (TTK) -vy) Exell D (xt Tull min
min
12hel Isjsm!
Note that 8 (i.e, 1) is guaranteed to be non-negative if Ti satisfies safety constraints; that because then of 2 J (TTK) for all and j, and the set {I I<h) is empty.
This formula for 8th, combined with Lemma 2, assures that the policies xhhh within 8hh max-KL. distance from xhl will not violate other agents' safety constraints, long the base joint policy a did not violate them (which assures 8 0). To this, notice that for every I,..., 1, and j =1,, I!....,, m
D max (Tt rit) S 8th -H(
L/ (T vi Eu- D T
KL.
implies (TRR) + L. (I ) v Σ KL (Tt. x1( + vt, D'u (IT,, ,/ s ct.
By Lemma 2, the lest-hand side of the above inequality is an upper bound of 1it ( diceol which implies that the update of agent in doesn't violate the constraint of Jj. The fact that the constraints of 14 for I Z h + are not violated, iee.
k+l ,xth T -iise)
1/ (Tx) + v
D max (T Rll x(t1)) + v Dme (TH S ctj.
(12)
is analogous.
k=n is obtained from Algorithm 1, then it has the monotonic improvement property, J(TK+1) J(TT), as well as satisfies the safety constraints, (T((T))) s cj for all k E N.iE N. and E (1,....m')
Theorem 1. If a sequence of joint policies (TT)
Proof. Safety constraints are assured to be met by Remark 1. It suffices to show the mono- tonic improvement property. Notice that at every iteration k of Algorithm 1, atf I Clearly D DRu , 0 z 8"h Moreover,
1/1 (TTx) 1/ (x((2) / D max ( x 5 (TW) scy "/ Σ
D max T m
1=1
15

---

Under review as a conference paper at ICLR 2022
where the inequality is guaranteed by updates of previous agents, described in Remark 1 (Inequal- ity 12). By Theorem from Schulman et al. (2015), we have
ax- ((TR+1)) ((TR)+ Ex-pae a mx-t [ (s. - mAN (Tg, Tk+1),
which by Equation 11 is lower-bounded by
((TE) Es-pan mm (ATee (s, a)]
Σ 1=1
vD mux (# a+t1
which by Lemma equals
=](Tx))
E Via m [Atte (s, afittt,,a""
> n=1
v max KL. (xt x
h=1
n linh-
=((T))+
(T
R.1 vDKL max (xO 2 )
(13)
1=11
and as for every h, in is the argmax, this is lower-bounded by
2 J(TT))
Σ
me E+1 ATE
hahe vD vD (x x
which, as follows from Definition equals
Σ 0 J(TR), which finishes the proof.
= =[(Tk)+
hm1
16

---

Under review as a conference paper at ICLR 2022
C AUXILIARY RESULTS FOR IMPLEMENTATION OF MACPO
Theorem 2. The solution to the following problem
p = m-=mmng g" x
s.t. b² x
x H S 6,
where g. b, E R", R², "e,,,,,R,,, > 0, H S" and H O. When there least one strictly feasible point, the optimal point x' satisfies:
H (g" + tr.b)
=-=-
= d.
where d, and v. are defined by
V. hC-
fa(1) A 1 1/
2 - - -
27 q
- 0 otherwise
d. arg max
(al & - + 16)
where q= g" H. r H g" H and 6²' H-
Furthermore, let Aa & (a dc 0,1 0), and A - 12 do r 0,1 0). The value of A, satisfies
9 9-12/s
q ( /g.
E 2a Proj
18- c2/1 Da .h e Proj
(14)
where d, = 1 if fa (A2) > fb (1 and d. = d, otherwise, and Proj(a, S) is the projection of point S. Note the projection of a point x E R onto convex segment of IR, [a, b), has value Proj(x, [a, b]) max(a, x))).
Proof. See Achiam al. (2017) (Appendix 10.2).
17

---

Under review as a conference paper at ICLR 2022
D MACPO
Algorithm 2: MACPO
1: Input: Stepsize a, batch size B, number of: agents n, episodes K, steps per episode 7 possible steps in line search L.
2: Initialize: Actor networks (%) Vi e N), Global V-value network {Øn), Individual Vi-cost
networks {Ør (0,.iiitmm.f:mm Replay buffer B
3: for k 0, I,...,K-- 1
4: Collect a set of trajectories by running the joint policy Te, (TT) op...... Top)
rr). 5: Push transitions {(o),. aj of . Vi E N. T) into B.
6:
Sample a random minibatch M transitions from B.
7:
Compute advantage function Á(s, a) based on global V-value network with GAE.
8:
Compute cost-advantage functions Â (s. a!) based on individual V'-cost critics with GAE.
9: Draw a random permutation of agents ij:--
Set M (s, a) A(s. a).
11: for agent in = i1.....f, do Estimate the gradient of the agent's maximisation objective
g
Σ Σ
B
T
log
(a." o (s,,
b=
fml
for j ..... n do Estimate the gradient of the agent's jth cost
14:
B
Σ
B
Σ
T
log th
( 10 A'i (S aft) 8th
15:
end for
Set Thh 8thh
17:
Compute fri the Hessian of the average KL-divergence
Σ
DKL
Thth dhh
(loo"), 8 (loft)
b=1r=1
Solve the dual (5) for d Use the conjugate gradient algorithm to compute the update direction
(H
g ('v))
Update agent in 's policy by
m in = 0h =
1 k
where j (0, I.....,) L} is the smallest such j 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%h from unfeasible points.
end if
(oth
Compute Mi (s
M (S,, a,). I/Unless h
n
24:
end for
Update V-value network by following formula: N
26:
1u+l = arg min + Σ Σ (Vo(s,) R,)
n=l F=))
27: end for
18

---

Under review as a conference paper at ICLR 2022
E MAPPO-LAGRANGIAN
Algorithm 3: MAPPO-Lagrangian
1: Input: Stepsizes ae, a. batch size B, number of: agents episodes K, steps per episode T, discount factor y.
2: Initialize: Actor networks 1%/ Vi E N), Global V-value network {Φo}.
V-cost networks (d) 1.00 Isj Replay buffer B.
3: for = 1, K.......-1.1. do
4: Collect set of trajectories by running the joint policy ne, (Tr) of
T Tpp)
5: Push transitions {(o). a' rr). Vi E N, E T) into B.
6: Sample random minibatch of B transitions from B.
7:
Compute advantage function Á(s. a) based on global V-value network with GAE, Compute cost advantage functions A/ (s. a²) for all agents and costs, based on V-cost networks with GAE.
8:
9:
Draw a random permutation of agents inm-
10: Set M (s, a) = Á(s a).
11:
for agent i, -1.....i, in do
12:
Initialise policy parameter 6th = 0%
and Lagrangian multipliers 1 = O, j.j = I......... ...........
13:
Make the Lagrangian modification step of objective construction
(d) (2) (s,, a,) M (s) a,) as,
14:
for e = I,..., PPO do Differentiate the Lagrangian PPO-Clip objective
15:
A gh
B T
(a"" 10 oin
4h 10.
V o B
Σ
Σ 1=0
min
Mhn
ar), clip
l0 +
Mh.ldd (Ne, an)
10
16:
Update temprorarily the actor paramaters
8th
8th + aeAghn.
17:
for j = I...., mf do
Approximate the constraint violation
B Vin (s:) -cy
d
Σ
BT
b=li=l
19:
Differentiate the constraint
Ad
B = Σ
d (1-))
Σ
T
(a 1ot1)
A (st.
In
(a." 10!")
b=1
1=0
20:
end for
21:
for j = 1,..., th do
22:
Update temporarily the Lagrangian multiplier
1ht - ReLU (4 ),11%)
23:
end for end for
24:
25:
Update the actor parameter x
1/h ghn (ath (ota)
26:
Compute M (s, a) = (nth (o%)
M (s, a). //Unless h
10th)
27:
end for
28:
Update V-value network (and V-cost networks analogously) by following formula: 8 T
Σ Σ (Vo(s)) - R,)²
29:
di+1 = arg min BT
b=1
30:
end for
19

---

Under review as a conference paper at ICLR 2022
F SAFE MULTI-AGENT MuJoCo
Safe MAMuloCo is an extension of MAMuloCo (Peng et al., 2020). In particular, the background environment, agents, physics simulator, and the reward function preserved. However, oppose to its predecessor, Safe MAMuJoCo environments come with obstacles, like walls or bombs. Fur- thermore. with the increasing risk of an agent stumbling upon 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 walls is Og(Manyggent Ant), The width of the corridor by three folding line walls with an angle of 30 degrees is (0m(An), The environment emits the cost of for an agent, if the distance between the robot and the wall is less than 1.8m, when the robot topples over. This can be described as
( c, [ 1, otherwise
0. for 0.2 I Stono ,+1 1.0 and | ,141 :walll 112 1.8
where Ztonso ,141 is the robot's torso's z-coordinate, and Ptorso ,+11 is the robot's torso's x-coordinate, at time + 1; &wall is the x-coordinate the wall.
Figure ManyAgent Ant 3x2 with corridor and Ant 4x2 with three corridors.
HALFCHBETAH & COUPLE HALFCHEETAH
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 agent finds itself too close to a bomb, the distance between an agent and bomb is less than 9m, a cost of will be emitted.
00 for || .141 Yoostacie||2
1. otherwise
where Yooso .+1 is the y-coordinate of the robot's torso, and Yobstacle is the y-coordinate of the moving obstacle.
Figure 4: HalfCheetah 2x3 and Couple HalfCheetah 1P1.
20

---

Under review as a conference paper at ICLR 2022
G EXPERIMENTS IN SAFE MANY-AGENT ANT ENVIRONMENTS
We provide additional results on the Safe Many-Agent ant tasks.
The width of the corridor is 12m; its walls fold at the angle of 30 degrees. The environment emits the cost of for an agent, if the distance between the robot and the wall is less than 1.8m, or when the robot topples over. This can be described
0. for 0.2 S Storso ,41 $ 1.0 and Dioroo ,441 @wall l12 2 1.8
4 =
otherwise
where Ztorso ,+11 is the robot's torso's z-coordinate, and Furso .+11 is the robot's torso's x-coordinate, time 1; wall the x-coordinate of the wall.
Figure 5: Many-Agent Ant 3x2 with two folding line walls.
ManyAgent
ManyAgent Ant
Manykkann
MA7PO
Avseaae Clnst
Auveagg Epikoole Case
sour))
PPO
Enviroment
Enviromment
steps
Mangkgent
ManyAgent
ManyAgent 6xc1
Average Episode Roward
1000
Average Epicode Roward
Average Roward
HATPO
VARR
P90
84
62.
04
steps
steps
Figure 6: Performance comparisons on tasks of Safe ManyAgent Ant in terms of cost (the first row)
and reward (the second row). The safety constraint values set to 10, Our algorithms are the only ones that learn the safety constraints, while achieving satisfying performance in terms of the reward.
21

---

Under review as a conference paper at ICLR 2022
H DETAILS OF SETTINGS FOR EXPERIMENTS
this section, we introduce The code available https://github. http///oomooss--ciie Multi
In
the details
settings for our experiments.
hyperparameters
value
hyperparameters
value
hyperparameters
value
critic Ir gamma
5e-3
optimizer
Adam
mini-batch
40
0.99
optim eps
le-5
batch size
16000
gain
0.01
hidden layer
training threads
4
std coef
0.5
actor network
mlp
rollout threads
16
std coef
eval episodes
32
episode length
1000
activation
ReLU
hidden layer dim
64
max grad norm
Table 1: Common hyperparameters used for MAPPO-Lagrangian, MAPPO, HAPPO, IPPO, and MACPO in the Safe Multi-Agent MuJoCo domain
Algorithms
MAPPO-Lagrannian
MAPPO
НАРPО
IPPO
MACPO
actor Ir ppo epoch kl-threshold
9e-5
9e-5
9e-5
9e-5
5
5
5
5
/
/
/
0.0065
ppo-clip
0.2
0.2
0.2
0.2
Lagrangian coef
0.78
/
Lagrangian Ir
le-3
/
fraction
/
0.5
fraction coef
0.27
Table 2: Different hyperparameters used for MAPPO-Lagrangian, MAPPO, HAPPO, IPPO, and MACPO in the Safe Multi-Agent MuloCo domain.
task
value
task
value
task
value
Ant(2x4)
0.2
Ant(4x2)
0.2
Ant(2x4d)
0.2
HaffCheetah(2x3)
5
HalfCheetah(3x22)
5
HalfCheetah(6x1)
5
ManyAgent Ant(2x3)
ManyAgent Ant(3x2)
ManyAgent Ant(6x1)
1
Table 3: Safety bound used for MACPO in the Safe Multi- MuJoCo domain
22


Reviews:
[{"review_id": "hyQfLOzG2I0", "reviewer": "Reviewer_rBTj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n1. This paper addressed an interesting and important question in MARL, i.e., how to learn the optimal policy with certain constraints.\n\n2. Their method was shown to be valid and promising both theoretically and empirically.\n\n**Weaknesses**\n\n1. The main idea of this work is to combine and extend [1] and [2], while there is no sufficient discussion on the methodological and theoretical contribution of this work beyond these two cited works. More necessary elaboration and justification should be made to solid the novelty of this paper.\n\n[1] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In\nInternational Conference on Machine Learning, pp. 22–31. PMLR, 2017.\n\n[2] Jakub Grudzien Kuba, Ruiqing Chen, Munning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. arXiv preprint arXiv:2109.11251, 2021a.\n\n2. This paper particularly cares about a safe constraint, while the relationship between cost and reward is not very clear. Based on MAPPO-Lagrangian where the authors use a hard constraint on satisfying the safe condition, it seems that the cost itself is more important than reward. However, in the real application, there may exist a trade-off between cost and reward. I felt some human preference or domain knowledge as required for the constraint optimization literature.\n \n", "summary_of_the_paper": "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.", "summary_of_the_review": "I think this is a borderline paper that addressed an important question with reasonably good performance while lacking necessary elaboration and justification on their novelty, as commented in my 'Main Review'. I am willing to upgrade if my concerns can be addressed during the rebuttal period.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZVY6mBuY09E", "reviewer": "Reviewer_Aw6n", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe algorithms are described well, and evaluations are provided. The problem is important.\n\nWeaknesses:\n1. Missing literature: For single agent, authors are suggested to see CRPO Xu et al. (2021), PDSC Chen et al. (2021), Triple-Q Wei et al. (2021), CSPDA Bai et al. (2021). \n2. For multi-agent, see ECML paper https://2021.ecmlpkdd.org/wp-content/uploads/2021/07/sub_181.pdf which also gives a model-free approach. Comparisons between the approaches are needed.\n3. There are no guarantees for the proposed approach. The combination of approaches does not seem to have enough novelty. \n4. Although the constraints mentioned in Section 3 has the form of  \"average constraints\". I think what actually used in the experiments can be seen as a \"peak constraint\".  So I'm curious about  the performance of the algorithms  in plain \"average constraints\"(e.g. if the Cost function can return cost less than 0 when c_j=0). Moreover, since the constraint in experiments is \"peak constraint\", why not compare the two proposed algorithms to the simple baseline that add penalty toward the global reward once the constraint is violated.  \n", "summary_of_the_paper": "This paper proposes two algorithms for multi-agent reinforcement learning with constraints using policy optimization based approaches. The evaluations of the proposed approaches are provided. ", "summary_of_the_review": "It would be good to compare with the ECML paper approach mentioned above for scalability and performance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XU153Hft_UA", "reviewer": "Reviewer_MyQj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nThis paper proposes two interesting algorithms to solve the safe RL problem in the multi-agent setting based on CPO, PPO and primal-dual approches. The author provides theoretical guarantee for their proposed algorithm (Thm 1). The effectiveness of their proposed algorithms is supported by extensive experiments.\n\nWeakness: \n\n1. More discussions are need to highlight the novelty and challenging compare with CPO (Achiam 2017).\n\n2. The theoretical result (Thm1) can be improved if the author can provide quantitative characterization of policy improvement and constraint satisfication similar to Proposition 1 and Proposition 2 in CPO (Achiam 2017), respectively.\n\n2. The experiment part misses some details, which I list below:\n\n    (1) It is not clear how to apply the algorithm MACPO in the multi-constrains setting in experiment since solving eq. (4) in the multi- constraints setting is very challenging.\n\n    (2) It is also not clear how MACPO updates the policy at the beginning of the algorithm, when the initialization point is infeasible. From the theoretical results, it seems that the constraint satisfications can only be guaranteed after the algorithm enter into the feasible region.\n\n2. The update rule of MACPO and MAPPO-LAGRANGIAN seems to be not efficient when the algorithm is not feasible. Because in the infeasible region we hope the algorithm can enter into the feasible region as soon as possible. Therefore, instead of optimizing a mixed objective function of both reward and cost, we may want to only minizing the cost.", "summary_of_the_paper": "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\".", "summary_of_the_review": "I can consider raise my score if the author can address my question in the \"main review\".", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses safe multi-agent reinforcement learning and makes two key contributions. First is a safety concerned multi agent benchmark, which is an extension of MAMuJoCo. Second, is the formulation and two solution to safety MARL problem. The authors pose safe MARL, and MARL problem with safety constraints, as a constrained Markov game.

The safety constrained MARL is an important, difficult, and understudied problem. The problem is more difficult that the single agent safe RL because of the non-stationarity in the MARL setting, which renders any theoretical guaranties conditioned on the assumptions of the behaviors of other agents. The authors are right to point out the lack of the benchmarks in the space. 

That said, reflecting on the reviewers' feedback and my own reading of the paper, this paper is attempting to do too much (benchmark, problem formulation, and two methods), in too little space, and is falling short. For example, the benchmark is an important contribution, but it is barely mentioned in the main text of the paper. If this was fully safety benchmark paper, there is an opportunity to go beyond MAMuJoCo, which feels like a forced multi-agent problem, and construct a safety benchmark with energy constraints, cooperative and competitive tasks etc... If this was fully methods paper, there would be an opportunity for more in-depth analysis of the results that the reviewers' pointed out. In it's current form, the paper feels like proposing a benchmark not grounded in a real world problem, and then a method to solve the problem.

I would suggest the authors to either:
- submit the paper to a journal where a space constraint would not be in a way, or
- split it into two papers, a more comprehensive benchmark, and methods paper evaluated on more difficult problems. 

Minor:
- Please update the literature. Some of the papers have been published, and they are cited as Arxiv papers.
Decision: Reject