On the Hardness of Constrained Cooperative Multi-Agent Reinforcement Learning
Authors: Ziyi Chen
Yi Zhou
Heng Huang
Venue: ICLR 2024 poster (2024)
Keywords: Multi-Agent Reinforcement Learning
Constrained reinforcement learning
Primal-Dual
Duality gap
Primal algorithm
Primary area: reinforcement learning

Abstract: Constrained cooperative multi-agent reinforcement learning (MARL) is an emerging learning framework that has been widely applied to manage multi-agent systems, and many primal-dual type algorithms have been developed for it. However, the convergence of primal-dual algorithms crucially relies on strong duality -- a condition that has not been formally proved in constrained cooperative MARL. In this work, we prove that strong duality fails to hold in constrained cooperative MARL, by revealing a nonconvex quadratic type constraint on the occupation measure induced by the product policy. Consequently, our reanalysis of the primal-dual algorithm shows that its convergence rate is hindered by the nonzero duality gap. Then, we propose a decentralized primal approach for constrained cooperative MARL to avoid the duality gap, and our analysis shows that its convergence is hindered by another gap induced by the advantage functions. Moreover, we compare these two types of algorithms via concrete examples, and show that neither of them always outperforms the other one. Our study reveals that constrained cooperative MARL is generally a challenging and highly nonconvex problem, and its fundamental structure is very different from that of single-agent constrained RL.

Published as a conference paper at ICLR 2024
ON THE DUALITY GAP OF CONSTRAINED COOPERA- TIVE MULTI-AGENT REINFORCEMENT LEARNING
Ziyi Chen, Heng Huang
Yi Zhou
Department of Computer Science University of Maryland College Park, MD 20742, USA (zc286, heng) @mmd edu
Department Electrical and Computer Engineering University of Utah Salt Lake City, UT 84112, USA yi 21..hou@uuthh.ee edu
ABSTRACT
Constrained cooperative multi-agent reinforcement learning (MARL) an emerg- ing learning framework that has been widely applied to manage multi-agent sys- tems, and many primal-dual type algorithms have been developed for it. However, the convergence of primal-dual algorithms crucially relies on strong duality condition that has not been formally proved constrained cooperative MARL. In this work, prove that strong duality fails to hold in constrained cooperative MARL, by revealing a nonconvex quadratic type constraint on the occupation mea- sure induced by the product policy. Consequently, our reanalysis of the primal-dual algorithm shows that its convergence rate is hindered by the nonzero duality gap. Then, we propose decentralized primal approach for constrained cooperative MARL to avoid the duality gap, and our analysis shows that its convergence is hindered by another gap induced by the advantage functions. Moreover, we com- pare these two types of algorithms via concrete examples, and show that neither them always outperforms the other one. Our study reveals that constrained cooperative MARL is generally a challenging and highly nonconvex problem, and fundamental structure very different from that of single-agent constrained RL.
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) (Zhang al., 2018: Oroojlooy and Ha- jinezhad 2022 Chen et al. 2022) is popular learning framework where multiple agents interact with a dynamic environment independently and communicate with each other to collaboratively optimize their policies to gain more rewards. It has wide range of applications including coordination of drones (Hammami et al., 2019: Jeon et al,, 2022), autonomous vehicles (Garces et al. 2023). and directional sensors (Xu et al. 2020), etc.
Recently, cooperative MARL has been further generalized to constrained cooperative MARL - a more practical setting with safety constraints, in which the agents learn gain rewards while constraining their behavior to reduce certain safety-related costs (Diddigi et al.) 2019 Oroojlooy and Hajinezhad 2022). This is an important generalization of cooperative MARL that fits many applications. For example, in multi-agent autonomous driving (Shalev-Shwartz et al. 2016), the pursuit of fluent traflic flow should always obey speed limits and guarantee safety. In drone navigation (Hammami et al., 2019), the drones are subject to constraints on bandwidth and battery power.
In the existing literature, the mainstream approach for solving constrained cooperative MARL problems is primal-dual algorithm (Diddigi et al.) 2019; Gu et al. 2021] Lu et al.) [02T]] Yang al. 2023, Ying et al. 2023),, which applies alternating updates to optimize the Lagrange function associated with the constrained cooperative MARL problem. This is a classic and popular algorithm for solving constrained optimization problems, and it is well-known that its convergence crucially relies on strong duality condition of the underlying problem, which has been shown to hold for constrained convex optimization problems (Bertsekas) 2014) and constrained RL problems (i.e., constrained cooperative MARL with single agent) (Altman 2004 Paternain et al. 2211). However, strong duality has not been formally validated in constrained cooperative MARL, and therefore leaving convergence of the existing primal-dual type algorithms obscure. In fact, constrained cooperative

---

Published as a conference paper at ICLR 2024
MARL can be more challenging than the special case of cooperative MARL (without any safety constraint), since intuitively the optimal product policy of cooperative MARL can be ruled out by the complex safety constraints. Hence, we are motivated to study the following fundamental problem.
Q1: Does strong duality hold for constrained cooperative MARL? Is constrained cooperative MARL more challenging than its special cases of cooperative MARL and constrained RL!
The existing convergence analysis of primal-dual algorithms for constrained cooperative MARL developed in (Lu et al., [202:: Ying et al.) (023) does not validate the strong duality condition, and moreover, does not characterize the desired constraint violation and optimality of the output policy. Instead, they only establish convergence result to certain stationary point with vanishing gradient norm. In particular, Yang et al. (2023) decomposes the agents' policy into a base policy and a perturbation policy, and only the convergence of the perturbation policy update established given fixed base policy. This result does not characterize the convergence of the full algorithm. In contrast, the convergence of primal-dual algorithms very well understood in the special case of constrained RL (with a single agent). There, strong duality has been shown to hold, and the convergence rates of constraint violation and optimality gap have been established (Li et al. 2021 Xu et al. 2021). Therefore, we are further motivated to explore the following problem.
Q2: If strong duality fails to hold in constrained cooperative MARI, how does the duality gap affect the convergence of the primal-duc dual algorithm? Moreover, can we develop alternative algorithm with convergence rates that do not depend on the duality gap?
1.1 OUR CONTRIBUTIONS
In this work, we provide comprehensive answers to the above questions, and show that constrained cooperative MARL is more challenging than its special cases of cooperative MARL and constrained RL. We summarize our contributions below.
We reformulate the constrained cooperative MARL problem as a constrained optimization problem on the occupation measure associated with the agents' product policy. It turns out that the reformulated optimization problem involves a linear objective function, some linear inequality constraints and certain highly nonconvex quadratic constraints, which are induced by the independence of the agents' product policy in the occupation measure space. To the best of our knowledge, such a nonconvex optimization problem has no known polynomial-tne time algorithm. In contrast, both constrained RL and cooperative MARL, as special cases of constrained cooperative MARL, have provably convergent polynomial-tine algorithms. This indicates that the strong duality of constrained RL may no longer hold in constrained cooperative MARL, as elaborated the next point.
We further construct example to show that constrained cooperative MARL problems can have strictly positive duality gap. Then, we reanalyze the convergence of the primal-dual algorithm in con- strained cooperative MARL,, and establish the first correct convergence rate result that characterizes the impact of duality gap on the constraint violation and optimality of the output policy.
We then propose decentralized primal algorithm that utilizes decentralized natural policy gradient (NPG) updates to directly solve constrained cooperative MARL problems in their primal forms and thus avoids the duality gap. We develop new technical tools and tight bounds to analyze the convergence of this algorithm, and prove that both the constraint violation and the optimality gap
converge at the sub-linear rate r(1- T((" + maxe C+) ). where M denotes the number of agents and (1-))²²
ÇA denotes an advantage gap induced by the global and local advantage functions. We will show that this advantage gap vanishes if and only if the Q function satisfies certain factorization structure (See Appendix H for more details). particular, in the single-agent case, the convergence rates of our primal al algorithm strictly improve those of the existing CRPO primal algorithm (Xu et al. 2021) by convergence results with existing works on constrained cooperative MARL in Table [in in Appendix j
factor of / viS| [|[]]A[(1 - 7). We compare
Lastly, compare the primal-dual algorithm with the primal algorithm and show that neither of them always outperforms the other in constrained cooperative MARL, both theoretically and experimentally. Specifically, we construct an example where the primal-dual algorithm always generates infcasible policy whereas the primal algorithm converges to the optimal policy at a sublinear rate, vice versa. In particular, the examples we construct involve highly nonconcave constrained maximization problems,
2

---

Published as a conference paper at ICLR 2024
making it challenging study the convergence of the primal algorithm. Instead of using convex optimization analysis techniques, we prove the convergence two highly nonconvex potential functions via mulli-statement induction in various cases.
1.2 RELATED WORK
Cooperative MARL:
Cooperative MARL has two tasks of interest, policy evaluation and policy
optimization. Policy evaluation has been solved by temporal difference type algorithms, including
(Wai et al. 2018 Doan et al., 20199) Wang et al., 2020; (Snn et al. |020 Liu and Olshevsky (2023) for
on-poliey evaluation and (Macua et al. 2014 Stanković and Stanković 2016] Cassano
al. 2020
Chen et al. 2021c) for off-policy evaluation. Multiple algorithms have been proposed to solve policy
optimization problem, including actor-critic (Foerster et al. [018 Lin et al. 2019; Suttle ct al. 2019
Ma ct al.
202 Chen et al. 2022 Luo and Li| (022), natural actor-critic (Chen et al. 2022
Luo and
Li 2022). p. fitted-Q Q (Zhang et al. 2020), value iteration (Chen et al. (021a) etc.
Constrained Markov Decision Processes: Constrained RL proposed by (Altman 2004) is
particular case of constrained cooperative MARL with safety constraints but only one agent. Primal-
dual algorithms are also popular for constrained RI. (Achiam et al. 2017 Tessler et al., 2018 Altman
2004; Yang et af. 2019 Yu et al., 2019; Stooke et al.) 2020 Ding et al. 2020 2021 Li et al. (021)
There are also other kinds of algorithms for constrained RL, including Lyapunov function based
algorithm (Chow et al., 2018 2019). interior point methods (Liu et al., 2020). policy network that
encodes safety constraints (Dalal al. 2018), and CRPO algorithm (Xu et al. 2021
See (Gu et al.
2022 for a comprehensive review of constrained RL.
Other constrained cooperative MARL frameworks: We mainly focus on the main-stream con- strained cooperative MARL framework (T) with lower bounds on the total discounted safety score. Some other constrained cooperative MARL frameworks have also been proposed. For example, the constrained cooperative MARL framework in (Liu et al. (021) has partially observable states and bounds the total discounted safety score as well as the instantancous safety score. [Sheng et al. (2023) proposes a primal-dual algorithm for constrained cooperative MARL with upper bound on the probability of safety violation. Mondal et al. (2022) uses a mean-field approximation to constrained cooperative MARL with very large number of agents, which reduces multi-agent policy to a centralized policy, and this approximated problem is solved by a natural policy gradient- based primal-dual algorithm. [Shang et al. (2023) proposes constrained cooperative MARI. framework for collaborative multi-phase tasks where each agent focuses on its own value and safety, and proposes a primal algorithm without theoretical analysis.
CHALLENGE OF CONSTRAINED COOPERATIVE MARL
We consider the standard setting of constrained cooperative MARL (Yang al. 2023 Diddigi et al.) 2019; Gu et al. 2021] Lu et al. 2021). ,, in which M agents explore and make decisions in a common environment. They communicate with each other via a decentralized network G ([M). E) where [M] {1, 2,..., M) denotes the set of agents and & denotes the set of communication links.
At time every agent m observes the global environment state 8, E S and accordingly takes an action a, (m) E (m) based on its own policy π (-]st.) These agents' policies are independent, and therefore their joint action a; = =aa_",... ;...: ((() A is generated by the product policy (m) |sz). Then, the state 8, transfers to a new state $t+1 ~ P(-|s az) (agls:) == I _ (a. following the state transition kernel P. and every agent m receives reward (m) (m) (st, az) and various safety scores ri = rik (m)) (st, ae) (k = 1,..., K), which are assumed to be in (0, 1] throughout. The goal of constrained cooperative MARL is find the optimal product policy that maximizes the cumulative average reward under various safety constraints, that is,
7 'Foo so ~ p].
(Constrained cooperative MARL):
max product policy
Vo(T) = E,
(I)
s.t. VT(TT) := E, Σ
7 The ~ p 2 Ex,
k= == I,..,, K,
1=0
3

---

Published as a conference paper at ICLR 2024
where the value functions (T{ 1/ = O,..., K denote the expected accumulation of the agents' average reward/safety scores Th.t = 1. E 1k
(m) with a discount factor E (0, 1), Ek IR
M
denotes the threshold for the k-th safety constraint, and p is the initial state distribution.
When there is no safety constraint, problem [1 reduces to a standard cooperative MARL problem that can be solved by many decentralized policy optimization algorithms (Zhang et al. 2018 Chen al. 2022). On the other hand, when there is only single agent, problem (1) reduces standard constrained RL problem that can be solved by primal-dual algorithms (Altman 2004 Achiam et al. 2017 Ding et al.) 2021]. However,
show next, when imposing safety constraints on multiple cooperative agents, the problem becomes more challenging.
To illustrate the challenges solve problem (T), associated with policy x, where 7 denotes the probability of visiting a certain (s, a) under и.
we rewrite it using the following occupation measures
:= (=(ssa)==11--
Σ 7 (s 8,0, 0 p), (s)(s) = (x,(s,))
1=0
In particular, there is an almost one-to-one correspondence between a policy and its occupation measure Un (s, a), since <alss
[=(a.a] if (*) (otherwise, (--ss) can be any distribution on
v=(8)
A). Then, the value function VI((Tt) in can be rewritten as linear function (vx) as follows.
Vi(TT) = V(((m) ==
(s),,a))
8,0
where as) = M7 Em (/ (s. a) denotes the average reward/safety score. However, in the multi-agent setting, V/ associated with a product policy æ needs to satisfy the following additional complex constraints. Below, a(mm) denotes the joint action of all the agents except agent m.
(1=)
the following con- strained optimization problem on function v S x A - TR. That is, u is the optimal solution to the following problem if and only if v = Vy where the optimal product policy of the problem (I)
Theorem 1.
The constrained cooperative MARL problem ( is equivalent
1
max FFl(s,a)ue (s)
1 1-7
8,0
s.t. (Occupation constraints):
v 020,
Σ v(s,a)=1 1, Ev(s' = -1 (11 + >> a((ss)) Vs
8.0
3,a
(Product policy constraints):
v(s, a) Ev(s,a')=) Σ
v(s, (m(()) (a(mm)_aal//) a(lmm))) Σ
(s, (mm ammm))) Vs,
a((m)
a(Omm)
(Safety constraints):
Σ [(((s,))(s.0)2 1,2,....,
7 Note that both the objective function and the safety constraints rewritten using 3 The occupation constraints are standard for any occupation measure v. The challenge is to introduce the product policy constraints, which is equivalent to that the corresponding joint policy is product policy. To do this, we observe that joint policy π is product policy if and only if (Tass) n (((n) (a(m) (s))((()) (a(vm))s) for all m, and also observe that the occupation measure satisfies u= a) = Mr(s) (r) (a(m))s)) (T) (a (a(h)))s) Based on these two observations, we can show that any occupation measure uy associated with product policy n if and only v*(s,a) a) Ear
Proof Sketch of Theorem
Uz (s, [m((m), a(mm))) Earrmy vz (s, (m())) ((())))) for all 8, a. L.
Theorem shows that the constrained cooperative MARL problem 1 is equivalent to optimization problem with quadratic equality constraints, which are induced by the product structure of the joint policy. Unfortunately, optimization problems with both linear and quadratic equality constraints
4

---

Published as a conference paper at ICLR 2024
highly nonconvex and there is no known polynomial-timg algorithm. Moreover, some studies argued that it is probably an -ooclleet problem (Murty and Kabadi, 1987). Thus, constrained cooperative MARL is a challenging problem due to the presence of safety and product policy constraints, and we further illustrate this point in the perspective of duality gap in the next section.
As comparison, both the constrained RL problem (with single agent) and the cooperative MARL problem (without safety constraints), as special cases of the constrained cooperative MARL problem, can be solved in polynomial-time. To briefly explain, note that the constrained RL problem is equivalent to the problem (4) without the quadratic product policy constraints (not required in the single agent case), and the problem is simply a linear programming problem that can be solved in polynomial time (Altman 2004). For the cooperative MARL problem, it is equivalent to the problem (4) without the safety constraints. In this case, it is well known that the problem always has an optimal product policy that is both deterministic and greedy, which can be obtained by standard value iteration or policy iteration approaches (Agarwal et al. 2022).
DUALITY GAP AND PRIMAL-DUAL ALGORITHM
In the existing literature, the mainstream studies proposed apply the popular primal-dual algorithm to solve constrained cooperative MARL problems (Diddigi et al.) 2019: Gu et al.] [2021] Lu et al.
2021: Yang et al.) 2023 Ying et al. 2023). However, this algorithm converges only when the strong duality holds, which has not been formally justified in the constrained cooperative MARL setting. In
this section, we prove that constrained cooperative MARL problems can have strictly positive duality
gap, and consequently the primal-dus algorithm does not have exact convergence guarantee.
3.1 CONSTRAINED COOPERATIVE MARL HAS NONZERO DUALITY GAP
The constrained cooperative MARL problem is equivalent to the following optimization problem.
K
max min L(Tr A) Vo\ + I
Au V+(T) - -Ex],
(5)
AERK
A=
where L(T,, A) denotes the Lagrange function with multiplier A = DA,...., Ax] The primal-dual algorithm is based on key assumption that the following duality gap equals zero
(Duality gap): A min max L(T, A) max min L(x, A). AER
(6)
AER
In the special case of a single agent, the problem reduces to a constrained RL problem that has been shown to have zero duality gap (Altman| 2004 Paternain al. 2019). This can be easily seen by rewriting L(T,, A) = Vo(v>) + -k=n Av (v(V)()=) - Ex] using 33. which reduces to a bilinear function of (Vn, A) E V x K Since both of the sets V := {ux i is a policy) and IK are convex sets, zero duality gap follows from the standard minmax theorem (Lemma 9.2 of (Altman (004h). However, in constrained cooperative MARL, the set V changes to Vp == {v> ir a product policy), ). which is nonconvex due the product policy constraints in Theorem Consequently, the duality gap A does not necessarily equal zero, which is formally proved in the following fact.
Fact 1. Constrained cooperative MARI. problems can have a strictly positive duality gap.
Alatur et al. [202) also obtains a similar result of positive duality gap for constrained Markov potential game with competitive agents. Their result applies to constrained cooperative MARL when all the agents use the same reward function rn- Moreover, can be easily seen that the duality gap has constant upper bound A < I- as TR,t E 10,
Remark:
Proof Sketch of Fact 7 We construct Example I (see Appendix A and show that it has positive duality gap A 3 (see Appendix C for the detailed proof). The reward ((m)) and safety scores ri (1)) of this example are carefully selected based on the key observation that A > 0 if and only if every optimal joint policy 7* of the constrained cooperative MARL problem (I) is non- non-product policy. To elaborate, we show the following equivalent conditions on the Lagrange function.
min
L(T, min max
L(TT, X)
max min L(T, A) Vo(T"),
XERA product policy 5 XERR joint policy
joint policy x AERK
5

---

Published as a conference paper at ICLR 2024
where (i) holds since maXproduct policy n L(T,, A) is essentially cooperative MARL problem, which has an optimal deterministic policy that also solves māXjoint policy x L(T, 2), and (ii) fol- lows from the strong duality of constrained RL. Hence, A > 0 if and only if Vo(T*) > maxproduct policy Min TT(TT,) A) = Vo(T²) where лt" is an optimal product policy of the con- strained cooperative MARL problem which implies that मt cannot be product policy.
3.2 REANALYSIS OF PRIMAL-DUAL ALGORITHM
Based on the positive duality gap result, we are further motivated to reanalyze the convergence guarantee of the primal-dual algorithm for constrained cooperative MARL. Throughout, we adopt the following standard Slater's 's condition (Paternain et al. 2019; Ding et al., 2020 2021).
Assumption (Slater's condition). There exists a policy ã and constants 6g > 0 such that V& Ex + 6% for all k = 1, ,,...,, K.
The primal-dual algorithm is a popular method for solving constrained RL type problems. We present the algorithm updates in Algorithm whose main idea is to optimize the Largrange function ( A) alternatively between π and A. Specifically, in the primal update step (line 4), we fix À and update the policy x by solving the subproblem max, L(T, A). In particular, define the surrogate reward
Tx. == Fo. + Ek= ARTR,t and then the subproblem reduces to a standard cooperative MARL problem with this surrogate reward. One can apply any of the existing MARL algorithms to solve this subproblem up to arbitrary precision é > O, e.g., decentralized policy gradient (Bai et al. 2021 and decentralized actor-critic (Zhang al., 2018 Heredia and Mou| 2019;CChen Chen al. 2020 2022). Moreover, in the dual update step (line 6). we fix and update À by solving the subproblem MInA L(T, A) via projected gradient descent. Note that for the policy evaluation step line 5, one
can apply the existing decentralized TD learning algorithms (Sun et al. 2020 Chen et al. (021c).
We obtain the following new convergence result of Algorithm T in constrained cooperative MARL.
Theorem 2. Consider constrained cooperative MARL problem with duality gap A, and let Assump-
tion 7 hold. Apply the primal-dual Algorithm to solve it with hyperparameters Ak,max 5x(1-))
-
KEK
maxx - 2T At.maa)) B 1-1--177 (1-7) 2KT E k= X R.mx
K
We obtain the following results on optimality gap and constraint violation (()+= max(:; (,)))
7
K
1
2T
22
K
Xk.aa EG (x(TT)))
X2
24A
(8)
1
2T
R.max
Furthermore, using the decentralized natural actor-critic algorithm (Chen et al. 2022 to obtain Te and model-based policy evaluation (Li et al. 2020) to obtain (Te.... the sample complexity is O(E -5 Imm ) to achieve Vo(T*) - EylVo (TT.) Se and Ek= du Myx (i((T))) 2A
Theorem 2 shows that in constrained cooperative MARL, the optimality gap Vo(TT) (Vo( of the primal-due algorithm achieves a sub-linear convergence rate (L/VTT). Moreover, the constraint violation Σx=1 1E (Ex Vi Vi(T))) converges at similar rate, but up a convergence error that depends on the duality gap A of the problem. Therefore, it is possible that the algorithm converges to a sub-optimal policy that strictly violates the safety constraints.
K
Comparison with the existing art. We note that the above sub-linear convergence rates match those of primal-dual algorithm in single-agent constrained RL (A = 0) (Ding et al. 2020 2021). Moreover, compared with the existing studies of the primal-dual algorithm for constrained cooperative MARL that only establish convergence to stationary points (Lu et al. 2021 Ying et al.) 2023), our Theorem 2 directly characterizes the optimality and constraint violation of the output policy ny. To the best of our knowledge, this is the first convergence result of the primal-dual algorithm in constrained cooperative MARL that characterizes the impact of the nonzero duality gap A.

---

Published as a conference paper at ICLR 2024
Algorithm 1 Primal-Dual Algorithm
Proof logic. The proof logic
mainly follows that of primal-dual
I: Inputs: 61, E2, 8 > 0, Ag. > 0 for = 1,..., K, for k
algorithm in constrained RL
2: Initialize: λε
K.
(Ding et al. 2020). However,
3: for iterations 1 = 0, 1, .,,,,...7 ,T
do
since the duality gap A > 0, we need to adopt a different bound for any product policy v'. i.e. L(T', I max, L(x, X*) Vo(a*) A, where X* E
4: Solve the cooperative MARL problem with surrogate reward xx Obtain an Ea-acuue solution T,, i.c.,
max L(T, Ad) - L( 20) S c1
(9)
arg xeRk max; L(T, A).
5: Perform TD learning to estimate (TT) such that (Tx)) (v)))))V(((m))) 62. Update the multipliers for k = 1,2,- .,2,..., K using pro- jected gradient descent as follows.
and n² is the optimal product policy of the constrained coop- erative MARL problem ( The above bound is used to bound the constraint violation of the policies n' ne obtained by the primal-dual algorithm, and also bound X via n' = 7 in Assumption (See Lemma D in Appendix for detail). The duality gap A in the above bound further affects the subsequent proof.
6:
A = Proj (0. me Me, ((V Ex)]- (10)
7: end for
8: Output: कp. with T uniform {0.1...., T 13.
DECENTRALIZED PRIMAL ALGORITHM
In this section, we propose primal-based algorithm for constrained cooperative MARL whose convergence does not involve the duality gap. Our algorithm extends the centralized CRPO algo- rithm (Xu et al. 2021) to the constrained cooperative setting, and involves new designs to enable decentralized implementation and new proof techniques that lead to improved convergence rates.
Our decentralized primal algorithm is presented in Algorithm 2 To explain, the main idea is to use (decentralized) TD learning to estimate the value functions (T.))) associated with the safety scores and select one that violates its constraint threshold by pre-determined amount value function. If no such violation exists, then we select Vn as the target value function. After that, we update the current policy n, using a decentralized natural policy gradient algorithm based on the selected target value function. Compared to the existing CRPO algorithm for single-agent constrained RL (Xu al.) (022), our algorithm design introduces several new elements. To elaborate, we update the agents' product policies via the following decentralized natural policy gradient (NPG) update
the target
(m)) क (a(m))s) o. ((m (mm))))) exp (aQ(" ( s, ( (m)); Vs, (m))(m)
(11)
where a > is the stepsize and (mm) (I; s,:s, a(m) is an estimation of the local Q function Qt (m) (T; 8, a(m)) Ex Ei T' e 800
(m) afmi]. which can be efficiently estimated by sample average estimation of Q (m) (T; (m)) = () +VV (TT;s)) (a(mm)) ~ (-(s))-)s), s' ~ P(-(s,a)] (Wei et al. 2021| Chen et al. 2021b). lb). In particular, such decentralized update is crucial for performing optimization in the product policy space. Moreover, when we estimate the value functions (Vi (T.(T.))) ) in line 5, we randomly permute their order and break the loop once target value function is found. This helps avoid the undesirable situation where the same value function is frequently selected so that the policy stays stationary point (possibly infeasible) in the policy update (TT). and also reduces computation. As a comparison, the CRPO algorithm requires to estimate (TT) for all k 1,2, : K in every iteration, and therefore is less efficient.
Next, define the advantage gap CA := sup..a. Ax s, a) - ΣME (m)) (T: s, am))))), which (IT; (m)
corresponds to the gap between the local advantage function A(m)) (T;; s, a (m)) = ((m)) (I:; (I: (())) V& (TT: s) and the global advantage function AA(T; a) Qx( Vi(T:s).
7

---

Published as a conference paper at ICLR 2024
Theorem 3. Apply Algorithm 2 with = O(V MT 62 =((
M E3
O
1o7
M 77 =00 0(V T max KAEK Ck
(see Appendix foor details). Then the output policy Tे.. satisfies
(1-9)²
Co T(1 7)3 + (1 (1-
M
Vo(*")- - [=]1o(=T))>$
(12)
T(1 7)5 & (+-II(V((TT) S s0(
M
MaxISRSK CA
= ,...., K.
(13)
(1 (1-
Furthermore, using the model-based policy evaluation (Li et al.
2020j to obtain Va (Te)) and
Qla!) (Tei 8, alm)), the sample complexity is O(e-A) achieve Vo [V([6(T)) I O(e (1-7)²)
and Σ K kmm Ak, (0eEEEE((TTT)) (
maxxskeR Co
(1-7)²
Theorem shows that both the optimality gap and the constraint violation converge at the sublinear rate O (TLMM/TI1/// 7) up to certain convergence errors that depend on the advantage gaps Çk- Thus, the above convergence result has very different nature from that of the primal-dual algorithm, which involves the problem's 's duality gap A instead. Moreover, ÇR vanishes if and only if the Q function satisfies certain factorization structure (See Appendix for more details) (Guestrin et al.) 2001; Son et al. 2019 Rashid et al. 2020). Therefore, when the Q function can be approximated by a factorized form, St is small, so the primal algorithm preferable the primal-dual algorithm.
Comparison with the existing art. In the single-agent case M = 1, the advantage gap Sk vanishes, and the convergence rates in Theorem 3 reduce to O(VM/T(L ()))))) which strictly improves that of the CRPO algorithm (Xu et al. 2021 by a factor of v /SS ||) (1) for large state and action spaces ! In particular, this improvement crucially relies on proving our new Lemma 3 which proves Ma
the bound Vx, (m++1; p²) V&, (T+; p²) ) πI-7}3 + 2Maes that tightens the corresponding bound in
(I-7)²
Xu et al.
2021 by factor of O(1/[|S] - 7))) using two novel techniques as elaborated below.
Technical novelty. First, denote ps. p/C as the distributions of state s; under n,, and M4+1, respectively. Then, by Markov decision process, we can show that - I max, ||
llp1 Palli. which implies that lIp! - -P:ll1 I imax, [ T.(-1s)]l Hence, we have
Vhe (') Vk, (TG = -i= E.a The (s.
(a))) S (1 - 7) max, ( -+((1>)]]1,
where the second inequality upper bounds E. by max, without introducing the factor [S]. Second, we further prove the following non-trivial tight bound
(-(3)) S SMM Eotoo ( ( (a(m)) mi (m) (a(m)|ss) | (-1s)
M mm=11
> al maxx((m) Qx, (Iee: 8, (0 (m)) mim) Qu, ( (, (m)))
where the inequality is obtained by taking "(t (a in the update rule (II as a function of a and bounding 2 = (s(m) (see the proof of Lemma 2 for details). This bound upper bounds (m by max Qi, (Tri ((m)) minl.(m) Qn, (Tri (m))). In contrast, (Xu et al. 2021) uses the Lipschitz property Ve, (Te+1: p') - Vk. (Tei p') 1 w welle under the softmax policy parameterization Ti (als)) x explwe(s. a)). However, this further leads the upper bound [[w411 - well2 = a 2 (mA v )lla & ||||A| that is much looser than our
|| | - Telli-
5 PRIMAL-DUAL ALGORITHM V.S. PRIMAL ALGORITHM
We have shown that the primal-dual Algorithm I and the primal Algorithm 2 suffer from non- vanishing convergence errors that depend on the duality gap and the advantage gap, respectively. Next, we show that each of the two algorithms can offer advantages over the other in certain scenarios.
Thee convergence rates of CRPO established in Xu et al. 2021 should be O O
[SILA|),
In the proof
of their Lemma 7, (iii) should have used the update rule M++1 w. - c but they used Mr+1 w. oQ
8

---

Published as a conference paper at ICLR 2024
Algorithm 2 Decentralized Primal Algorithm
First, revisit Example and show that Algorithm 2 outperforms Algorithm inn the following theorem. Here, the product policy xe is fully characterized by pt ==
1: Inputs: a, 2,,2,53 <3 > 0,
2: Initialize: Policy To.
3: for primal iterations = , do
(2) (0]s) and qe := n. (22) (0]s).
4: Let k2 +
Te
5: for k 02 (1), ..... ox(K) where oe is random
Theorem 4. In Example [ if we run Algorithm 7 with E1 = E2 O, then the generated policy ne. is infeasible for all t. In contrast, if we run Algorithm 2 with 62 C3
permutation on {1, 2, .... K] do
6:
Perform TD learning to estimate (m,)) such that [Va Vie(Te)) 62.
a I 10-3 7:
If (m,) Ek- 17, let h; k and break.
-6x and an initial policy that sat-
8:
end for
isfies 3 S po S 70 and 0.06 s Pogo S 0.135, then the generated pol-
9:
for agents = 1,,,... ...,, .,, M in parallel do
Estimate ② (m)) (IT; s()))) such that
10:
icy for all t 2 1/2 In 20m) is feasible
1(m)) (Ts; alm) ((!)) (m S c3-
and close to the optimal solution (1 4) with max (pp- 1 1) < 14a.
11:
Update local policy to T2+1 following the decentralized NPG update rule 11..
Technical novelty: The major challenge to prove Theorem lies in the conver-
12: end for
13: end for
gence analysis of ATgorithm 2 in Exam-
14: Output: कं. with T uniform
(0stsT-11 0}.
[ which can be written as a noncon- cave constrained maximization problem
(37). Moreover, the primal update rule differs for K = 0, 1, 2. Hence, we cannot follow the standard convergence analysis for convex optimization. Instead, we utilize the multiplicative structure of the (42) and (43) to obtain the convergence of the potential functions
primal updates of Pa and q: in Eqs.
P.q: and Et 1 and 1, respectively. To elaborate, we prove the statement (A,): ja S P. $ fa. 1 whenever
T6
and 0.06 < P:dt < 0.135, and the statement (Ct): Pc+1 1 S (1 1..-0.0 0.079a) qr
ge-1
E: - 1| > 5cx via inductions that (At), (Ct) + (A++1) and that (At) = (C₂). In particular,
16 (A,) = (C²) proved in 4 separate cases: either p. 2 9: or Pt < qt. and either P:o: 2 1 + 3a
or Pro:: < To + 3a. (Ac), (Ct) imply that Pr - 1 S 10a for a certain T S
In(a 1)). To -1 1| S 10a; Vt 2 T, it suffices prove Pt+1 Pt I 4.66a, that the ring further show that 9t
4.12 q
area 5a < P1 - 1 S 10x is sufficiently wide to drag Pt. back towards 1. The convergence rate of
di
Pett is proved similarly via inductions in two separate cases where peq:: 2 16 +3a or pelt < is +3a.
Next, we prove that Algorithm outperforms Aggorihmmiin Example (See Appendix Aj. Theorem 5. In Example 2 Algorithm Jobtains the optimal policy in one iteration. In contrast, if we run Algorithmp [2) with 62 = cg 7 O and an initial policy that satisfies po + 40 = 1, then the generated policy ne infeasible for all
Since Example 2 is also a nonconcave maximization problem, proving the infeasibility of the function value (Tr)) obtained by the primal algorithm also cannot follow the standard convex optimization convergence analysis. Instead, we prove that pt. + Q: = via induction and show the constraint violation Vi (T.) 4p. (1- - p.) < < E1.
In Appendix A we conduct simulations to verify the above theoretical comparison of both algorithms.
CONCLUSION
In this work, we have shown that constrained cooperative MARL is highly nonconvex problem that is more challenging than cooperative MARL and single-agent constrained RL the occupation measure space. Due to the challenges, the strong duality condition required by the mainstream primal-dual algorithms no longer holds in constrained cooperative MARL. Therefore, we reanalyze the convergence rates of the primal-dual algorithms with nonzero duality gap. Then, we propose decentralized primal algorithm for constrained cooperative MARL to avoid the duality gap, and our analysis shows that its convergence is hindered by another gap induced by the advantage functions. We expect that our study will spark new research directions in multi-agen RL, and motivate to design better al algorithms with rigorous convergence guarantee for constrained cooperative MARI..

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The work of Ziyi Chen at Utah and Yi Zhou was supported in part by U.S. National Science Foundation under the Grants CCF-2106216, DMS-2134223 and ECCS- 2237830 (CAREER). Ziyi Chen at UMD and Heng Huang were partially supported by NSF IIS 2347592, 2347604, 2348159, 2348169, DBI 2405416, CCF 2348306, CNS 2347617.
REFERENCES
Achiam, J., Held, D., Tamar, A., and Abbeel, (2017). Constrained policy optimization. Proc.
International conference machine learning (ICML), pages 22-31.
Agarwal, A., Jiang. N., Kakade, S. M., and Sun, W. (2022). Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tèch. Rep, 32. htttps://rtthean ..k.s..pf
ok. 3k.github.o www.o//eteeeoorroooooooooooooooo
Alatur, P., Ramponi, G., He, N., and Krause, A. (2023). Provably learning nash policies in constrained markov potential games. ArXiv:2306.07749
Altman, E. (2004). Constrained Markov decision processes. CRC press.
https://ww/
sop
www.mal//maaaasase..... pdf
Bai, Q., Agarwal, M., and Aggarwal, V. (2021). Joint optimization of multi-objective reinforcement learning with policy gradient based algorithm. ArXiv:2105.14122
Bertsekas, D. P. (2014). Constrained optimization and Lagrange multiplier methods. Academic press.
Cassano, L., Yuan, K., and Sayed, A. H. (2020). Multi-agent fully decentralized value function learning with linear convergence rates. IEEE Transactions on Automatic Control.
Chen, B., Xu, M., Liu, Z., Li, L., and Zhao, D. (2020). Delay-aware multi-agent reinforcement learning. ArXiv:2005.0544:
Chen, M., Li, Y., Wang. E., Yang, Z., Wang, Z., and Zhao, (2021a). Pessimism meets invariance: Provably efficient offline mean-field multi-agent rl. Advances in Neural Information Processing Systems, 34:17913-17977
Chen, Z.. Ma. S., and Zhou, Y. (2021b). Sample efficient stochastic policy extragradient algorithm for zero-sum markov game. In International Conference on Learning Representations.
Chen, 7., Zhou, Y., and Chen, R. (2021c). Multi-agent off-policy td learning: Finite-time analysis with near-optimal sample complexity and communication complexity. ArXiv:2103.13147,
Chen, Z., Zhou, Y., Chen, R.-R., and Zou, S. (2022). Sample and communication-effiieee decen- tralized actor-critic algorithms with finite-time analysis. In International Conference on Machine Learning, pages 3794 3834. PMLR.
Chow, Y., Nachum, O., Duenez-Guzman E., and Ghavamzadeh, M. (2018). A lyapunov-based approach to safe reinforcement learning. In Proc. Advances in neural information processing systems (Neurips), volume 31.
Chow, Y., Nachum, O., Faust, A., Duzmaz-Guzman, E., and Ghavamzadeh, M. (2019). Lyapunov- based safe policy optimization for continuous control. ArXiv:1901.1000
Dalal, G., Dvijotham, K., Vecerik, M., Hester, T., Paduraru, C., and Tassa, Y. (2018), Safe exploration in continuous action spaces. ArXiv:1801.0875
Diddigi, R. B., Reddy, D. S. K., KJ, P., and Bhatnagar, S. (2019). Actor-critic algorithms for con- strained multi-agent reinforcement learning. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgen Systems, pages 1931-1933.
10

---

Published as a conference paper at ICLR 2024
Ding, D., Wei, X., Yang, Z., Wang. Z., and Jovanovic, M. (2021). Provably efficient safe exploration via primal-dual policy optimization. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3304-3312.
Ding, D., Zhang. K., Basar, T., and Jovanovic, M. R. (2020). Natural policy gradient primal method for constrained markov decision processes. In Proc. International Conference on Neural Information Processing Systems (Neurips), volume 2020.
Doan, T., Maguluri, S., and Romberg, J. (2019). Finite-time analysis of distributed TD(O) with linear function approximation on multi-agent reinforcement learning. In Proc. International Conference Machine Learning (ICMI.), volume 97, pages 1626-1635.
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S. (2018). Counterfactual multi- agent policy gradients. In Proc. Association for the Advancement of Artificial Intelligence (AAAI), volume 32.
Garces, D., Bhattacharya, S., Gil, S., and Bertsekas, D. (2023). Multiagent reinforcement learning for autonomous routing and pickup problem with adaptation to variable demand. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 3524-3531. IEEE.
Gu, S., Kuba, J. G., Wen, M., Chen, R., Wang, Z., Tian, Z., Wang, J., Knoll, A., and Yang, Y. (2021). Multi-agent constrained policy optimisation. ArXiv:2110.02993.
Gu, S., Yang, L., Du, Y., Chen, G., Walter, F., Wang. J., Yang, Y., and Knoll, A. (2022). A review of safe reinforcement learning: Methods, theory and applications. arXiv preprint arXiv:2205. 10330.
Guestrin, C., Koller, D., and Parr, R. (2001). Multiagent planning with factored mdps. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, pages I
Hammami, E., Afif, H., Moungla, H., and Kamel, A. (2019). Drone-assistee cellular networks: multi-agent reinforcement learning approach. In ICC 2019-2019 IEEE International Conference on Communications (ICC), pages 1-6. IEEE.
Heredia, P. C. and Mou, S. (2019). Distributed multi-agent reinforcement learning by actor-critic method. PapersppesOOn,,ne, 52(20):363-366
Jeon, S., Lee, H., Kaliappan, V. K., Nguyen, T. A. Jo. H., Cho, H., and Min, D. (2022). Multiagent reinforcement learning based on fusion-min www.-mmmtoo-atteenlileeit attention-critic for multiple-unmanned- unwanned- vehicle navigation control. Energies, 15(19):7426.
Kakade, S. M. and Langford, J. (2002). Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, pages 267-274.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020). Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 1261-12872
Li, T., Guan, Z., Zou, S., Xu, T., Liang, Y., and Lan, G. (2021). Faster algorithm and sharper analysis for constrained markov decision process. A0Xiv:2110.1033
Lin, Y., Zhang, K., Yang, Z., Wang. Z., Başar, T., Sandhu, R., and Liu, J. (2019). A communication- efficient multi-agent actor-critic algorithm for distributed reinforcement learning, In 2019 IEEE 58th Conference Decision and Control (CDC), pages 5562-5567.
Liu, C., Geng, N., Aggarwal, V., Lan, T., Yang, Y., and Xu, M. (2021). Cmix: Deep multi-agent reinforcement learning with peak and average constraints. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part 1 21, pages 157-173. Springer.
Liu, R. and Olshevsky, A. (2023). Distributed td (0) with almost no communication. IEEE Control
Systems Letters.
11

---

Published as a conference paper at ICLR 2024
Liu, Y., Ding, J., and Liu, X. (2020). Ipo: Interior-point policy optimization under constraints. In Proc. the AAAI Conference on Artificial Intelligence (AAAI), volume 34, pages 4940-4947.
Lu, S., Zhang, K., Chen, T., Başar, T., and Horesh, L. (2021). Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8767-8775.
Luo, Q. and Li, X. (2022). Finite-time analysis of decentralized single-timescale actor-critic. 3rXhv:2200.057333.
Ma, X., Yang, Y., Li, C., Lu, Y., Zhao, Q. and Yang, J. (2021). Modeling the interaction between agents in cooperative ageti reinforcement learning. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pages 853-861.
Macua, V., Chen, J., Zazo, S., and Sayed, A. H. (2014). Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control, 1005):1200-1274.
Mondal, W. U., Aggarwal, V., and Ukkusuri, V. (2022). Mean-field approximation of cooperative constrained multi-agent reinforcement learning (cmarl). ArXiv:2209.074377
Murty, K. G. and Kabadi, S. N. (1987). Some np-complete problems in quadratic and nonlinear programming. Mathematical Programming: Series A and B, (9(2))117-119.
Oroojlooy, A. and Hajinezhad, D. (2022). A review of cooperative multi-agent deep reinforcement learning. Applied Intelligence, pages 1-46.
Paternain, S., Chamon, L. F., Calvo-Fullana, M., and Ribeiro, A. (2019), Constrained reinforcement learning has zero duality gap. In Proc. International Conference on Neural Information Processing Systems (Neurips), pages 7555-7565.
Rashid, T., Samvelyan, M., De Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. (2020). Monotonic value function factorisation for deep multi-agent reinforcement learning. The Journal of Machine Learning Research, 21(1):7234-7244
Sawarr-Shwartz, S., Shammah, S., and Shashua, A. (2016). Safe, multi-agent, reinforcement learning for autonomous driving. ArXiv:1610.03295.
Shang, X., Xu, T., Karamouzas, I., and Kallmann, M. (2023). Constraint- multi-agent re- inforcement learning for collaborative tasks. Computer Animation and Virtual Worlds, page e2182.
Sheng. J., Wang, L., Yang. F., Qiao, B., Dong, H., Wang, X., Jin, B., Wang, J., Qin, S., Rajmohan, S., et al. (2023). Learning cooperative oversubscription for cloud by chance-constrained multi-agent reinforcement learning. In Proceedings of the ACM Web Conference 2023, pages 2927-2936.
Son, K., Kim, D., Kang, J., Hostallero, D. E., and Yi, Y. (2019). Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. International Conference on Machine Learning, pages 5887-5896.
Stanković, M. and Stanković, S. S. (2016). Multi-agent temporal-difference learning with linear function approximation: Weak convergence under time-varyine varying network topologies. In Proc. American Control Conference (ACC), pages 167-172.
Stooke, A., Achiam, J., and Abbeel, P. (2020). Responsive safety in reinforcement learning by pid lagrangian methods. Proc. International Conference on Machine Learning (ICML), pages 9133-9143.
Sun, J., Wang, G., Giannakis, G. B., Yang, Q. and Yang. Z. (2020). Finite-time analysis of learning with linear function approximation. In International
decentralized temporal-differtt Conference on Artificial Intelligence and Statisties, pages 1485-4495 PMLR.
Suttle, W. Yang. Z., Zhang, K., Wang, Z., Basar, T., and Liu, J. (2019). multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. ArXiv: /903.0637.
12

---

Published as a conference paper at ICLR 2024
Tessler, C., Mankowitz, D. J., and Mannor, S. (2018). Reward constrained policy optimization. In Proc. International Conference on Learning Representations (ICML).
Wai, H.-T., Yang, Z., Wang, Z., and Hong, M. (2018), Multi-agent reinforcement learning via double averaging primal-dual optimization. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 9672-9683.
Wang, G., Lu, S., Giannakis, G. B., Tesauro, G., and Sun, J. (2020). Decentralized td tracking with linear function approximation and its finite-time analysis. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 13762-13772.
Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. (2021). Last-iterate convergence of decentralized op- timistic gradient descent/ascent in infinite-horizon competitive markov games. In Proc. Conference Learning Theory (COLT).
Xu, J., Zhong, F., and Wang. (2020). Learning multi-agent coordination for enhancing target coverage in directional sensor networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 10053-10064.
Xu, T., Liang, Y., and Lan, (2021). Crpo: new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480-11491. PMLR.
Yang, T.-Y., Rosca, J., Narasimhan, K., and Ramadge, P. J. (2019). Projection-based constrained policy optimization, In Proc. International Conference Learning Representations (ICLR).
Yang, Z., Jin, H., Ding, R., You, H., Fan, G., Wang, X., and Zhou, (2023). Decom: Decomposed policy for constrained cooperative multi-agent reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10861-10870.
Ying, D., Zhang, Y., Ding, Y., Koppel, A., and Lavaei, J. (2023). Scalable primal-dual actor-critic method for safe agget rl with general utilities. ArXiv:2305.17568
Yu, M., Yang, Z., Kolar, M., and Wang. Z. (2019). Convergent policy optimization for safe reinforce- ment learning. Proc. Advances in Neural Information Processing Systems (Neurips), 32.
Zhang, K., Yang, Z., Liu, H., Zhang, T., and Basar, T. (2018). Fully decentralized multi-agent reinforcement learning with networked agents. In Proc. International Conference on Machine Learning (ICML), pages 5872-5881.
Zhang. K., Yang, Z., Liu, H., Zhang. T., and Başar, T. (2020). Finite- analysis for decentralized cooperative multi-agent reinforcement learning from batch data. PFAC--apersOnLLnee, 53(2): 1049 1056.
13

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
Numeric Examples and Experiments
14
B Proof of Theorem
|
15
C Proof of Fact
16
D Proof of Theorem
17
E Proof 3
20
F Proof of Theorem
24
G Proof of Theorem
30
Equivalent condition of (c
31
Supporting Lemmas
32
Comparison of Convergence Results Constrained Cooperative MARL
36
K
Experiment Constrained Grid-world
36
A NUMERIC EXAMPLES AND EXPERIMENTS
In this section, we implement the primal-dual algorithm (Algorithm I and the primal algorithm (Algorithm 2 to the following two numeric examples verify Theorems and
Example 1. Consider a constrained cooperative MARL problem with two agents, single state S = {s}. Both agents share the same action space A = (0, 1} and the same reward and safety scores listed below. The discount factor y and the safety thresholds are & ε2 = $.-
0
(m) (8. (s, [0, 1, r (T)) 0)) 1,
r2 (s, (0, 0))
(m)
r (m)
(s, (0,1) 0, (mm (s, [0, 11) 0, (m)
(s. (0, 1]) 0
To (s, [1,0) = 0. r (s, [1. 0)) O, (m)) (s. [1, 0)) = 0
(m)
(m)
r (mm) (s, [1, 1]) = 1, ri
(m)) (s, [1, 1)) = O, r (s. [1, 1)) = 1
Example 2, Consider modifying Example 7 so that both agents share the following reward and a single safety score. The safety threshold is E 1.8.
88 (0,0)) = 1, (m) (s, [0,0) =
0
8s [0, 1)) = 0, r (m) (s, (s) [0,
mm) (s, (1,0) 0, (mm [1,0)
To (m)
(s. [1, 1)) O,
r (m) (s. (1, 1.
For Example [ we implement the primal Algorithm 2 with 10 20 0, -60, and
try various initial policies (Po. 9o) E {00.45, 0.3), (0.2, 0.3). 0.3), (0.25, 0.25), (0.35, 0.35)) which satisfy the conditions of Theorem 4 We obtain the results shown in the first five figures of
14

---

Published as a conference paper at ICLR 2024
10- 16..0118.6..11
No..1=122... 5.53
6.3
4.44
20--0...3311
0.00
120
0:20
6.0-
6.30
Go- (32,0
6.9
KAN T1m
0.28
1,00
5001
LoWU uoey Duth 10at 2030
CAT una Like Lher
060
2008
LoKE GiR
LIAB A000
6.8-
10v9//-1033.00
130
sofecy threstokh 6
(bx m0w.4)/mm0.3..... 0.331
p1 0250
RJ (0.35,0050000 0.35.
10.3003
0.0
PL. 02-00) 133,0.8
U.. 12.30
616
630
(886
Figure 1: Results of the primal algorithm Examples [the first 5 figures) and (the last figure).
Figure
The first two figures at the top of Figure 1 Iindicate that (Pc: with various initializations
converge to the same value which is close to the optimal solution ( 4). The top right figure of
Figure shows that (T( converges and is close to the optimal value 5
7. The first two figures the
bottom Figure show that the policy m. is feasible (i.e., (TT) 2 E1, V2(TT)) 2 {2) after 2 2500 iterations. In contrast, we implement the primal-dual Algorithm [ with
3 = 0.1, <1 62 = 0 and initial multiplier À = 0j. The policy parameter (Pt. 9.) alternates between (1, and (0, 0). both of which are infeasible since they satisfy (2(TT)) These results verify Theorem
& and (1(m,) 0 < &1 respectively.
For Example we implement the primal Algorithm 2 with 0.1, 02 C3 7 = 0, and try various initial policies (Pu. (o) E {(0, 1). (0.2, 0.8). (0.4, 0.6), (0.7, 0.3), (0.9. 0.1)} which satisfy the conditions of Theorem 5 The learning curve of the value function V (m( is shown in the last figure of Figure It can be seen that V1 (Tx) is always far below the safety threshold & = 1.8. In contrast, implementing the primal-dual Algorithm with a
0.1. e E2 and initial multiplier A = O, we obtain (Pt, 4:) = (1, 1) which is the optimal solution to Example 2 These results verify Theorem
B PROOF OF THEOREM
Proof for the product policy constraints: We will first prove that n is product policy if and only if Ps satisfies the product policy constraints in Eq. (4)
Note that the following equality always holds for 1x of any joint policy
17 a
(8, - Σ
Uz (s, (a'(m) amm)))
Σ u (s, [a(m)) a((mml))
(s) Σ
Vr (s)
Σ
Ux (s) , amm))lss)
(m)
Σ un (())T((((()) [(m))sss)] a((mm
(T)(ss)))) ((m)) (
(14)
where ii) uses (s,
e (s) and (ii) uses nt x(m)(al
Eartms V (s) at (ls)) and
== Emrmm T ([aa
a(im)]]ss.
If n is product policy, then <[ass) = n ((mm) (x))))))) (m))))))) where a x()m)(a
IT +m (mm) (a((m)))))) which implies that Eq. (14) equals O, i.e. Us satisfies the product
M
policy constraints in Eq. (4.
15

---

Published as a conference paper at ICLR 2024
Conversely, suppose that V/ satisfies the product policy constraints in Eq. i... Eq. Then for any state s, consider the following two cases.
14 equals 0.
If (s)))) o O, we have {[ass) = x (mv (a((m) s) (m)) (a(m)|s) ss) which means for any agent m, a a(im)
and a (m) are independent given s. Therefore, a!!), aa2), ,...,, (M) are independent under the policy (-1ss) which means π (als) = MM n (m) (s(
If vx (s) = 0, <(-ss) can be arbitrarily defined, and thus we can define it such that the product policy condition π (a s) I===1=
M
= ((m))(
(a()))) holds.
Therefore, can be a product policy if Vsx satisfies the product policy constraints.
Proof of equivalence between the problems 1 and (4): Suppose x² is the optimal product policy for the constrained cooperative MARL problem (T). Then V/* satisfies the occupation constraints in problem 4 based on Theorem 3.2 of (Altman 2004). and further satisfies the product policy constraints as π is product policy. Therefore V/-- is a feasible point of the problem
Then consider any function v' S x A + that satisfies all the constraints of the problem (4) Since v' satisfies the occupation constraints, v' = V- for some policy T' based on Theorem 3.2 of (Altman 2004). As proved above, since Vz" satisfies the product policy constraints, x' is a product policy. Also,
the safety constraint Vi((T) (i) - E.,a (s, (s, a) 2 & (k = I,.... K) holds where (i) uses Eq. 2 Therefore, n is a feasible policy i.e., T- s,a al)(s))))ss a) S - Σ.,a ro(s, a)uz- (s, a). Since /' an arbitrary feasible point the feasible point V-- is also the optimal solution to the problem
policy of the problem I and thus we have Vo(TT) < Vo(=*),
of the problem
Conversely, suppose v² :
SSx x A + R is the optimal solution to the problem
(4) Then V²
satisfies the occupation constraints and product policy constraints of the problem for some product policy x². Hence, the safety constraint V*(**)
4 v Vx-
Σ 0,0 FA (, (s,a)
(k = 11=1.... .,. K) means '' is a feasible product policy of the problem
For any feasible product policy x' of the problem (T). Vr satisfies the occupation constraints and prod- uet policy constraints, as well as the safety constraints that 1 Es.a Tx (s, = Vi((T) 2
EN (A: = ,,...,K, Due to the optimality of v" = Vx*. we have - Σs, Fols, (() < - E. To,s, a)vx (s, a), i.e. Vo(=') S Vo(=*). Hence, the feasible policy "' is also the optimal solution to the problem
C PROOF OF FACT
We repeat Example I as follows.
Example 1. Consider a constrained cooperative MARL problem with two agents, a single state S= {s}. Both agents share the same action space A(m) {0, 1} and the same reward and safety scores listed below. The discount factor is 7 = and the safety thresholds are & = ε2 =
0 (s, ()) = 1, (m) (s, ()) = 1, r (mm) (s, (0, =
(mm)
(m)
(m) [0, 1]) = 0, r2 (mm) (s, (0, 1)) = 0 (s, [0, 1]) = 0, (m) (s,
rb (m)
(s, [1,0] 0)) = O, (m) [1, O, r2 (m) [1, 0)) 0
r0 (m) (8, [1, [I) 1, (m) (s, (m [1.1] O, (m) (s. [1, 1J) =1
In the above example, any product policy x (als) = ) (a (a)))ss can be fully charac- terized by p = n (0]s) and 9 π (2) (0)s). Then the aim of the constrained cooperative MARL problem in Example can be formulated
max Vo(a)) == 2pq 2(1-p)( p) 9) P.9E(0.1]
1
s.t. VT((T) = 2pq 2 8
V2(T) = 2(1 - p1 (1 - 9) 1
16

---

Published as a conference paper at ICLR 2024
The above problem has two optimal solutions, p 9 and 9 (= 2- Therefore, maXprodua pulicy x min x [(t, A) 4
3 Both of them have
Now consider the following dual problem.
min max L(T, A) ;= 2p + A1) + 2(1 - 12) AER p.ge/0,11
(Ai + +1)+
(15)
Fixing R. (0x L(T, X) is equivalent to
2+ + )0= p
+ A2
1 1 A2
max p.
2 \1 + X/
If 1432 ] (i.e. A x2), then the above problem has solution p" = which yields 24
= 2(1 + A1) - (A1 + >2); Otherwise if À < 22. D- = q" = 0 which yields "(p",""; = 2(1+ - Hence, maxp.qE[0.1] L(T, A) + 2 max(A1, )2) - [A1 A2). which has minimizer [0, 0j and the corresponding value min maxp.ge(o.11 L( 2) =
As a result,
D PROOF OF THEOREM
Note that since Fh. E [0, 1]. the value function (T( has the following bound for all policy ι and k = 0, 1....... K.
S Vi(TT) Ex
8
y Tke 80 pl S -
1
(16)
Hence, the norm of ((T) = [v)( VK((=) E 1j has the following bound
VK [V())) 1-7
(17)
Furthermore, Assumption I iimplis that there is a feasible product policy ग such that 0 S & S V*()),, so the norm of = : [k] R has the following bound
VK
|El - [V) =
(18)
1 1-7
Then,
< |
(114+1112 (1ae13))
(I1^ - ((((TT)) = (1eel1
(40)
T-1
T-1
23
Σ
No AT ((TT)) + + Σ
(I(( v(T)) + [ + [1El))
1=0
(iv)
T-1
T-1
xT - - ((T)) + 332 (2VK
I 23
Σ
(V - v(TT)) 2
Σ
1- + t2vKK)
1=0
(2)
8KT
< 23 Σ (V((*))-((C + 3r2
Ak,max
(1 71- + 2KT
(19)
k=1
where (i) uses the initialization Ao 0. (ii) uses the update rule (00) (iii) uses triangular inequality,
and (iv) uses (..().) Vi((+a)) 62. Eqs. (17) and (8). d 0 as well the constraint that
17

---

Published as a conference paper at ICLR 2024
V(=*) 2 & satisfied by the optimal policy x¹ of the constrained cooperative MARL problem in Eq. ( and (v) uses At [0, Ak.max| (based on the update rule (TO) as well as ((((T)) V& (x((T))) S eg.
Rearranging the above inequality, we obtain that
K
4KT3
- S Te2
mama +
+ KT
(20)
(1-
Note that
0 2
max L(TT A1) I(
(e1 T(me, A1) (x))
(e1 + Vo(T.)) Vo(T*) + xr (V(m))-V(T)) V(T*)))
(21)
K
4KT3
(a + Vo(T)) - Vo(+T)) + Té²
Ak,
+ KT
(1 (1-
k=1
where (i) uses Eq. (9), (ii) uses the definition of the Lagrange function in Eq. (5 and (iii) uses Eq. 20 Rearranging the above inequality yields that
Vo(T*) E, [V(TT(T)
Σ
- Vo(TT))
4Kg
62
Ak,max
71-
+ + K33
(
K
2T
k,max
where ii) uses the
hyperparameter choices
I-
1
K 2T
2k=1
X2
K.max
T P..Ba = (1- (
2KT Ek=1 Mmm This proves the optimality
K
X2
27(2 Ak. A
gap in Eq.
Next, we will prove the convergence rate (8) of the constraint violation.
For any Ā = (ãI:...; [xx] E [0, AR. max)) |K it holds that
D 212
(
S A1 - -V(()T)) - 5) -11²
(8)
| X1p - 23(4 T) (V -) - 23(A: - -((
+ (T)) - V( )| + [++]+ + +11E11
(08)
| - x|2 - 23(A. ()T(())))) (V(T.) -E) + 2,82
A max + f (eVV +
+B32(22
2vK
1 1-
k=
K
8K332
< |4 212 2
23( - (V - E) + 2,862
Ak.max + +2K +
(1 71-
where (i) uses the update rule 10) and X E [0, max) (ii) uses triangular inequality, (iii) uses
Net 7h [0, max), (Tee) Vi ( 62, Eqs. (77) and (8) Telescoping the above inequality
18

---

Published as a conference paper at ICLR 2024
over t = 0, 1, I....,TT
T 1 and using λu O, obtain that
T-1
4TK
8 Σ (Me - 2) (V.) - E) - |
T
Mam + KT3
(22)
(1- 71-
1=0
Since V(x*) 2 & and E R Eq. 21
implies that
T-1
8
Σ
N
(
S B
(el + Vo(TT) Vo(TT))
(23)
[=0
t=0
Summing up Eqs.
and 23 yields that
T-1
X (5 ((t))
T-1
K
4KT
$ 3 Σ
(e1 + Vo(TT) - Vo(TT)) + [|]²
TBe
Av + +KT32 22+
(1 71- (24)
1=
k
Note that
Vi(TT) = max min L(TT A)
A
max L(TT X²) -
1(Te)>")
Vo(Te) + (V((T)) -E) - A (0))
- T - V(m))) -
(25)
where (i) uses the definition of the duality gap A in Eq. 6 (ii) uses the definition of the Lagrange function (5) and (iii) uses X R Substituting the above inequality into Eq. (24) and rearranging it, we obtain that
8
- (g-V(AA)) - (X v(Ti))+)
t=0
< BT + + 1 |ス|2 + T3e
Σ
A + KT +
4KT
(26)
(1 (1-
R=1
Using Eq. (64) and selecting du Ax.max (V2((TT)))) S Ex where 11-} is an indicator function, obtain that
K
N (Ex - (x(T))
2
Substituting the above inequality into Eq. (26 yields that
Ak.max (Ex Vx((T))
< STT + G)) + 1712 + TBe2 Σ
K
A max + KT332 +
3KT
2
(1 71
(
K
K
4KT32
< BT(A + +E1) +2
Σ
22
maxx + TBe2
Ak.max KT + (1-7)²²
A=
19

---

Published as a conference paper at ICLR 2024
where (i) uses ||al = Σx= X I 4 X maax Finally, by dividing both sides of the above
inequality by T3, we prove the convergence rate (8) of the constraint violation as follows.
K
Aa. By - Vi((T))++
AR.max (Ex= Vx(TTe))
K
K
8K3
5 2A + 2c1 +
Ra. max + 252
max + KBe -
T3
(1 (1-7)²
1=1
22
K
< 2A +
X k,max
1-71 7
27
where i uses the hyperparameter choices 61
I-
1
27
K k
2k=
k,max
c2
2T d mar S - (1-
7) 2KT Σx=
X2 k,max
Furthermore, for any é > O, implementing Algorithm for T ) iterations, the output policy Th. satisfies the following convergence results based on the convergence rates 7 and (8).
k=1 X x.max = O
7
K
7c
Vo(TT) - -x([V(
X2 kamax
22
22
K
Ak.max Ak.maxEryEf. (TT))
X2
maaxx + S 2A 24.
2T
Each iteration of Algorithm Jsses decentralized natural critic algorithm (Chen et al. 2022) to obtain ne and model-based policy evaluation (Li et al. 2020 to obtain (Te), which require
O 3 lne and O(Ez²) samples to achieve precisions
K
O(e) and
27
Kmax
ΣK X2 max
62 1 V 2T(EK dg.mna O(e) respectively. Hence, the sample complexity of Algorithm
TO Inne + +2² ()((( -3 In + (5ne=
E PROOF OF THEOREM 3
First, we list the hyperparameter choices of Algorithm 2 as follows.
7)3
MT Banny Kl.[T (-18)
(27)
ME KL [L[TT((110) (11))
maxi Cn
1)
(28)
T(1 7)
(1 7)
M ME KL |T' (-0=)\[=0(-1ss)
(29)
T(1 75
63 7) )) KL (-1s) (T(ss
(30)
MT
Specifically, I we choose the number of iterations 7> > (1 (1-7)²
M Bewn KL[x- (-|s)]] mo ( |s)]
Furthermore, we select uniform policy To such that mo(als) = [a then KL [-|s)(- mo [s)] -
In |A| and thus only require T > (1- In |A| to let $ 1.
20

---

Published as a conference paper at ICLR 2024
Based on Eq. 75 we have
In
Z (m)
(+)
- -VV, (Tei 8)
In
Σ t
(m)) (a (m) (s) exp (aQi, (me) s, (m)))) a aV. (TTis)
a((m)
(m) (a (s) In exp (aQ (m) (mT) (, mmm))) aVV, (T)
@/m)
mm)
(a (m)
(s) Ch m3) (T (Tris, d(lm)) - Q (Iez 8, 8, (m)))
T
(m)
(m) k (Ty) a (m)) Q (m)) ( (l)))) 2 -003:
a max k
which means
1
In (()) (m (s) - (Teis) + E3 2 0.
(31)
a
Therefore, we have
- (VKc
Vsa (T(:
E Eg
Ake (T))
M
(1)
E Exoretio
Te+1 (a (mm) (mm))s(((()))) (Tiss (tris,amm) - Vis ( 8))
m=1 af))
Th- (m (m) (s) (alm)ss) (Q!e (Tri (eris,alm)) Qire) ( ( 8, mm)
alm)
M
+ Eg Ee
Asr (T
A (m) (Tr: (Trris,al almm))
m=
(156)
2
M
( In ((())) (s) Vkk (miis)
1
Σ
"iti (a(m))s) (s) In
(m)
+ (a (m())) (s
(m))
a
t (m))
(a(mm) 8)
a(m)
M
max (m)) (Tre 8, am))) - -Q(tm (Tissa ( - -GA
(m)
m=
(6n)
E Be
Σ
(
a
In (m) (s) (s)
(T(:s) tes) - -2MEs Cke
m=1
M
(1 In 2/!²) (s) (m)
(1 (1-7)E Esnp'
Va, (Teis) + c3)
-2Mcs -Ke
where (i) denotes the occupation measure P4+1:p' (1 7)
(s, s|sp
and uses the performance difference lemma (Lemma 6.1 of Kakade and Langford p)02 (ii)
uses (mm) (T): s, (,)))
((m)) (Ti s, a (m)) Vk. (Tiis) (iii) uses the policy update rule (76)
and Ge = sups,a.7 AA 8, a)
Σ M
Σm=1 A(m) (T; )) (iv) uses (L(T (m( (-|+)][T( (I7)) (-1s))
Eato m (a (m))))s)) In me (m) (a())) (s)
(m)
0 and max g((m)
12
ke (me: 8, (m)) of()) (m 8, (m)) S
(
(a(m)]s)
C3, and (v) uses Eq. (31) and De+1:p (s) 2 (1 >)ppsss). The above inequality can be rearranged as follows.
M
E Egnp'
Σ
In 2 (m) (() ac3s (T.(i))
2aMEs
+ aGit +
< 1-7
Val (T(
1 1-7
21

---

Published as a conference paper at ICLR 2024
(0) 2aMes
acke +a
Ma
+ 2Macs
+
1-7
1-7
(1 (1-98 7)3
(1 7)2
(6) aCk;
4Maa3 7 (1-7)²
Ma²
(32)
(1-
where uses Eq. 69) and (ii) uses a S 1. Then, we have Eanny [KL T (+1+] (-13) - KL (++))|[
In x² [alss) - In x (al Te (a)s)
Egwey Bawo
Te+1(als))
M
In Tt (m)) (a (s)))s)) - In m (a [s)]
EEs aowey
m=1
In Zi (mm)
mmm)m) (s) + aes - aVi,(( + a V.a. (Tris) acs aQQa.) (Aee (Te: s, a mm))
Eg Bs
(i) a6ki
4.aa3
+ Ma²
M
aB aBs
Σ
(Q(m) (Te (Teis, 8, alma) Via (Te::))
7
(1 - 7)3
(1-
(00)
aSki
4Mac3
+ Ma²
M
A (Te;; 8, ml)
(m)
+
7
(1-
713
m=1
(60)
aCk,
4Mae3
Ma²
+ (1-7)3
....s arwss As, (T)) asn.
1 1-7
(1-
aCk,
4Macs
+ Ma?
+
a(1 - (Vn, - Vka (TT)).
(33)
1-7 7)-
(1 7)3
where (i) uses the update rule (66), (ii) uses max 12(m)) (mee alm)) - (m)) (mz3 (m)) s
(32) for p' = Vx', (iii) uses the definition of the advantage function that k. (115 8, a (m)) ol(mm) (Tt; 8, a (m))
and Eq.
(m)
(m() kr (TE;s) (iv) denotes that &e- sups.a.r |A 8,)= a)-
Em= A(m)) (TT 8, a ((m))) )| and (v) uses I 1 as well as the performance difference lemma (Lemma
6.1 of Kakade and Langford )2002) which implies that Eggarer Ake (T(; 8, a) (1 7) (V2 (T*)
Vi, (m. Rearranging and averaging the above inequality (33 over 1. 0, 1,..., 1, we obtain that
Sk.
4Mc3
Ma
Vh. (TT"
Vha (Te))
T
(1 7
(1 7)3
(1 7)
1=0
Egny,-
(34)
To(1 77)
Denote 2₂-- = (0 < 1 < - k2 k). Then based on the design of Algorithm 2 for any ( E No (including 7) and 1 < k K, we have Vi(eTe 2 E 7, so the convergence rate (13 of the constraint violation can be proved as follows.
(TTT) 2 (x(TT) - [x(Tg) V((TTT)
(1)
E 17 C2
(0) Ex 0/
ME KL |T (-1s) T-(sss)]
maxissks Ct. (1 1--7) 7)2
T(1 7)
where (i) uses (m.) 2 &a - 7 and [[((T)) - Vi((m))] S e2, and (ii) uses the hyperparameter choices
(28) and 29). Conversely, for any E N4. (1 < & < K), we have VI((TT)) < E < Vv (T²)
so a similar way we can prove that
Vi(mm)) < Vi((T)
(M((m)) - Va(mm)) S Vo(=²) n 62
(35)
22

---

Published as a conference paper at ICLR 2024
Substituting Eq. 35
into Eq. 34).
obtain that
Esny.- KL x (-|s)]|[=00
Ta(1 77)
Σ (Vo(TT)) - -V((T))
Co
4M
Ma
T
(1 7))
(1 7)3
(1 (1-
LENO
K
Gk
4Mc
Ma
+
(i((TT)) - Vi((Te)
(1 (1-
(1 7/3
(1 71-
1EN
1 Σ
5o
4Mcx
Ma
(o((T))- - V(((TT))
T KE
(1 (1-7)3
(1 77)3
(1 (1-
K
maxisksK SK
4Mcs
Ma
+
(1-
(1 (1-7)3
(1 (1-
1EN
(0) 1
7 Σ
Vo(==) - Vo((T))
50
4M
Ma
(1 7)
(1 7)3
(1-
1NNo
T Wool
(n) - C2
maxisA5K& Gk
4Mc3
Ma
+
(1 (1-7) 7)2
(1-7)
(1 (1-
where (i) uses Eq.
35 and (ii) uses Σx= [W&l = - Nol Substituting the hyperparameters
choices 27
(30) into the above inequality, obtain that
1 Σ (Vo(T*) - (T,))) 5c2 - 2Gu +
202(T (Wol)
2
(36)
T
(1 (1-7) (1-
T
LENo
If No = 0), then Eq. (36) above implies the contradiction that [Wo] 2 T 2 > 0. Hence, .o * 0.
Then we prove the convergence rate (12 of the policy optimality in the following two cases.
(Case 1) EIENN (Vo(TT) (T.)).) 5E2
0, then Eq. (36 implies that [V Σ
(1-7)*
2
and that EIENG (Vo(T*) VO(TT) 5E2-
I T Teg. Then the convergence rate 12) can be
(1-1)3
proved as follows
B(Vo(TT) - Vo(TTT)
Σ ((6(T=)--((mm)))
Wo
BENO
(Vo(TT)) Vo(Te) - 5622 (1 (1-
2Go
+ 562 +
2Go
Wol
(1 (1-
LENo
Té2
2Go
< T/2
+ +52 +
(1 71-
2Co
M M
2Co +
s 7c2 + (1 7/-
=VV
T(1 71
21-
(Case 2) If ErENS (Vo(T*) - Vo(TT)) - 562
Co
< 0, then the convergence rate
12 can be
[1-pp²
proved follows.
B(Vo(TT)) - Vo(TT))
2Go
2ço
Σ (Vo(TT) Vo(TT)) 5e2
5e2
Wol LEAO
(1 - (1-
(1-7)²
2ço
MESWEY KL(T (-|s)||
2Go
3 550g +
(1 73 VV
+
T(1 75
(1 7)2
23

---

Published as a conference paper at ICLR 2024
Furthermore, for any > O, the output policy xy- of Algorithm 2 after T Ole 2) iterations satisfies the following convergence results based on the convergence rates (12) and (1
Vo(=T) - By T(1 7) 7)s
M
+ (1 (1-
((->))><((Et )
Co
s0(ct
c+ (1 (1- (1-
Go
&k [x
maxISASK SA
<0(et (1 7-
SaxI CR
1 k K.
T(1 - 7)) (1 7)
Each iteration of Algorithm 2 uses model-based policy evaluation (Chen et al. 2022 to obtain (T.)
and !!m) (ITE: 8, ( which require O and (EE ?) samples to achieve precisions E2 = (())
(by substituting T = O into Eq. 29 and E3 ((e) (by substituting T = ( into Eq.
(30) respectively. Therefore, the sample complexity of Algorithm is
TO( +g² = )((3) + +6 = (c-))
F PROOF OF THEOREM 4
We repeat Example as follows.
Example 1. Consider a constrained cooperative MARL problem with two agents, a single state
S {s}. Both agents share the same action space A {0, 1} and the same reward and safety
scores listed below. The discount factor is 7 = 2 and the safety thresholds are & = & =
r (s, [0,0]) = 1,
"1
(m) (s) 0]) = 1,
r2 (s, [0, 0)) = 0
To
(m) (s, [0, 1]) 0, 1 (s [0, 1]) O,
(s,
r2 (s, [0, 1]) 0
(m)
(m)) (s, [1, = 0, (m) (s [1,0) O, (s) [1, 0)) = 0
0 (s, [1, = 1, r (m) 1]) = O, r2 (s. [1, 1]) =1
(mm)
In the above example, any product policy Ta s) 7 by x (0)s) E [0, and n (2)) (0|s) E [0. 1]. Then the aim of the constrained cooperative
can be parameterized
MARL problem in Example can be formulated
max Vo(T) = 2pq + 2(1 (1 4) p.0E(0.1]
1
s.t. Vi((T) = 2pq 2 8
(37)
1
V²(x) = 2(1 - -1 - q) 2 8
Proof for the primal-dual algorithm: Since 61 = 0, (Pe. qt in the primal-dual algorithm (Algorithm
D is obtained by solving arg max, L(TT, Ax). In Appendix B we have obtained that (pr, 4:) (1, 1) where Vi =1 1>> E if X₁ 2 X2 and (pr, (t) = (0, 0) where V2(TT)) = Ea if \1 < X2. Hence, the policy n, is infeasible for all L.
Update rules of the primal algorithm for Example
Next, we analyze the primal algorithm (Algorithm 2 on Example I Note that there is only one state 8 in Example so (T) = V*(()))),, and thus the local Q function can be computed by Bellman equation as follows.
Qhe (mi (m))
Σ amm)
n x(mm) (a())))))) (7W())
(38)
Hence, the NPG update rule
becomes
(m) (0)s) exp (aQ(m) (m) T
ky (mI3 8, 0))
(m) (0]s)
(m)) (0|s) exp (aQ (m)
(TT s, 0)) + म.
(m)
(1|s) exp (aα (m))
hr (Te 1))
ky
24

---

Published as a conference paper at ICLR 2024
(m)
(0|s)
tt
(39)
(m) (0|s) + q mmm
(1|s) exp (aQ (. (Tei s, aQ (Tei s, 0))
where (i) uses 1 (T; s, a (m)) - Qt
)| - = 0. Note that Eq. 38 implies that
2 11) (msss, ( 1) - 22 (Tr; s, 0)
(Fn. [1.0]] - (s, [0, 01)) + (1- (Fx, [1. [1,
(s, (0,
(40)
2 (mis, 1) Q/
0/ (T;; 0)
(r (s, [0, 1]) Fhe (s, [0, 0)) +1 (1 (T) (s: [1, 1]) Fk, (s. (1,0))
(41)
(m) (s, a) defined by Example into the 40 and as well as the expressions of rk
Substituting Eqs.
update rule
39
we further obtain the following update rules of pa m (1) (0]s) and q: m 2)
(0
Pt
if le 0
Pr + (1 Pt) exp (a(1 20.))
P++1
Pt + (1 Pt) exp cige)"
Pt
if kr 1
(42)
Pt
if hr 2
Pr (1
Pt) exp (a(1 -.)))
4:
if le 0
q: + (1 q:) exp (a(1 2p:))
Gt
g++1
4: + (1 4t)) exp ( ap:)
if hip =
(43)
qt
if he = 2
1t (1 2:) exp (a(1 pc))
Next, we prove the convergence of the above primal update rules (42 and 433 the optimal solution
p.q 1. Starting from an initial policy satisfying _ <
2 %o and 0.06 S Pu9o S 0.135, we
will prove the following three useful statements for all
(A:): 0.06 S P.q. I 0.135 and < P S 1.5, which implies that Pt, E [0.2, 0.45].
4t
Pig. (Br): If prg: 2 16 = T6 + 3a, Pr+ Pr+10++1 S 1oo.1lo Otherwise, P++14++1 2 1-0.196
pig.
(Ct): If pt ge 1 > 5a, then p++1
1: 1 S 0.079a)
-1/
Since (Ao) holds, we will prove the above three statements by proving the induction arguments that (B,), (C2) = (A++1) and that (A,) + (B.), (C²).
Upper bound the change of PeZ: and Et under (Aş): Next, will prove that under the statement zt (Ac). the change of the potential functions Pegt and Es will always be upper bounded by Oaa). Substituting M and Eg = 0 into Eq. (68). we have
M
(m)) r++1 (a (m())))) ss) mm(m//
(m)) (a!
12
((m)
2/pt+1 Pel + 2/ qel < Ma
1 1- + +2ez))
4ax
(44)
Therefore, we have
Pt+1 1
|P44 9t) qe ge(ptt1 Pr))
Peg.
Pige
(4)
(1))
< 17|p Pel + 17| - 9el 5 34a,
(45)
and
Pc+1 Pt
gt++1 g:
25

---

Published as a conference paper at ICLR 2024
go - -Pr) -p))-po D pr(gr+1 - 9t)
90+19
(#ix)
(lpt+1 - Pel + 14++1 - -+l))
0.43
(fv)
4.66a,
(46)
where (i) uses 1 9: S 1 and p.q: 2 0.06 (based on (A,)), (ii) and (iv) use Eq. (44, and (iii) uses
Pr, 9t S 0.45 and 1 2 o gr 0r1 gel 2 (g: 2a) 2 (0.45)(0.43) (based on Eq. (44))
Proof of (At), (B.), (C+) = (A-1): Based on the statement (Ae), we will prove that 0.06 v
Po+194+1 S 0.135 in the following two cases of Prlk-
(Case 1) If 0.06 S P: to 3a, then one hand, based on the statement (B,), Pc+
Prt: 2 0.06. On the other hand, based on Eq. (45), we have P++1 S (1 + 340)) S
(1+34a) (16 + 3a) 0.135.
(Case II) If L
+ 30 S Pegt 0.135, then on one hand, based on the statement (B.), pr+ gc+1 5
T5
Prq: 0.135. On the other hand, based Eq. 455). we have Pr-1 2 (1 34a Pr
(1-34 34 x 10-3) 1 > 0.06.
Then, we prove that 2
S P++1 < 1.5 in the following two cases of Pt 9."
3 1111
(Case 1) If P - > 5a, then based on the statement (Ct), we have
| - -
1.5 = 0.5 which implies that Po-1
S 1.5. Then suppose Pit1 qr-1
3 S Er which along with qe"
g++1
Eq. 466 implies that Pt
Pull
+ 4.66a
S 3/3 + 4.66 x 10-3 < 1. Hence, based the statement
q 9++1
(C.).
1 11 1 2s ie.. 111l
P= which contradicts with P:11
<
< Rs Therefore,
9++1
q--1 ge"
g++1
q
Pr+1 S 1.5 holds in Case I.
9++1
(Case II) If
Pt
5a; then based on Eq. (46). we have
qt
Pt-1 1
5
Pt
1
Pt+1
Pt
9.666a < 9.66 10-3,
(47)
4++1
Qt
16+1
qt
which implies that
<
p++1
<
1.5.
3
4++1
Proof of (A,) = (Be), (Ct): Since Pt: qi (0.2,0.45) and 17 - 60 2 -0.006, the corresponding
value function V2((T,) = 2(1 Pt) qr) 2 2(0.55)² > ī - 17. Hence, we only need to consider
the following two cases, (T((T)) 2
(i.e., K₁ = 0) and V1 < _/ (i.e., ke = 1).
(Case I) If (T+) = 2p:q: 2 1/2 then the case k. = 0 of the update rules 42 and 43 is implemented. We will first bound the involved terms exp (a(1 2q:)) and exp (a(1 2pr)) as follows.
(1) exp (a(1 - -24() S exp(() S 1 exp(0.6)))
(8)
(H1)
S 1 + 0.70,
(48)
(iv)
(v)
cxp (a(1 -24))) 2 exp(0.1a)
2 1 + 0.10,
(49)
where (i) and (iv) use qe E [0.2, 0.45]. (ii) and (v) use ex = 1+ f d' S xe and e 2 1 1+ respectively for any x 2 0, and (iii) uses a S 10-3 3 In a similar way, we can obtain that
+ 0.1a S exp (a(1 1 22p)) S + 0.7a.
(50)
As the case ky = 0 of the update rules 42 and (43 is implemented, we have
PeRe
[pt + (1 pt) exp (a(1 -
((((((-gg))) 24:))| [ + (1- ge) exp - (p(1-2p)))
Pt+ 11+1
(5)
[p + (1 (1) 0.1a)) (9 + (1- 91 (1+0.1))
[1 + 0.1 pt)] [1 0.1 g:)]
26

---

Published as a conference paper at ICLR 2024
(88 2 (1 + 0.055a)²
+ 0.11a,
(51)
where uses Eqs. (49) and 50 and (ii) uses Pt. q: S 0.45.
When P: 2 we have
Pt+1
Q++1
Pt Qt + (1 - q() exp (a(1 2p:))
-
St Pt (1 Pt) exp (a(1 2qt))
Pt qt + (1 - pt) exp (a(1 - 2q:)) - (1 - qt) exp exp (a(1 (
Pr
at
Pt + (1 pt) exp (a(1 - (2:))
Pe (1- 4t) cxp (a(1 - -2q)) -exp (a(1 2pr))] -pp -9)) exp (a(1 2q.)) 1]
Pt
Pt + - Pt) exp (a(1 24:))
gr
qr
(69)
P:
Pt (0.55)2a(p:
(1)) 0.7 9c)
41
1+
(8))
Pt
Pt -1)
0.079a
qt
S (1 0.079k)
Pt - 1):
(52)
where (i) uses the case K of the update rules (42) and (43). (ii) uses q: 0.45, Pt - qt 2
Eq. (88) and exp (a(1 - 2q()) exp (a(1 - 2p:)) 2 (a( ②e) 2 0, (iii) uses a S 10 3 and
Pe 2 0.2. Similarly, when pt ge. we have
1 P1+1
9c+1
[1+ (1-9)) (exp(a(1 -exp Pt P (1 Pı) exp (a(1 - 29())
exp (a(1-2q)) - pc) [xxp -1]
= 1
Pr (0.55)2a(( - PPt) 0.7ax(ut P.)
< 1
qt qt
1+ 0.7a
< 1 0.079app: (1
qt
Ft
(1 0.079a) 1
Pt
(53)
where (i) uses S 0.45.
(Case If (Te) 2p:q: < 17, then the case he of the update rules implemented. Hence, we obtain that
422 and
43 is
Pige
[pt + - (1-P)) -x)( (q: + +(1 - q:) exp(-app) (1-
P+414++1
(6)
x [pt + (1 -11-p)) p.) -1 [g. + (1 - (1) 0.19a)
[1 0.19a - 1111-pp]][[11_ 0.19 - -q)
(4) 0.1ca) < 0.2a + 0. ((i))
0.19a,
(54)
where (i) uses the following Eq. (55). (ii) uses Pt, at S 0.45, and (iii) uses a S 10 10-3
1
exp(-o01) atg.
(aqq))
2
(10 (10-3) (0.45)
< 1 - aqq +
aq
2
27

---

Published as a conference paper at ICLR 2024
S 1 - 0.999qq -0.99a(0.2) 1 1 0.19a.
(55)
When Ps 2 9t, we have
Pt+1
qt+1
( Pt Qt + (1 - 9r) eexpp=aapp
-
Qt Pt + Pt) exp( -(()t)
Pt qi + (1 Pt) exp(-aq)) (1 qi) exp( -1
Pt
1
qt
Pt + (1 - pt) exp(-aap
Pt (1 - gr) exp(=axy) - [xp(=)p:)] + (pr - 2:) 11l-eep(--ap
Pt
qt
P: (1 pe) exp( (aaqq)
(6)
Pt
1
Pt
(0.95(() q1) 0.19A q.)
q:
qt
(11)
pt
Ph -1)
0.14a
qt
9t
< - (1-0.140) 0.14a)
- 1).
(56)
9t
where (i) uses the case hę- = 1 of the update rules (42 and 43
(ii) uses qi S 0.45, Pt qt 2 0, Eq.
(55) and the following Eq. (57). (iii) uses a S 10 and p. E [0.2, 0.45].
exp(- (aq)) - exp( axp: app(-ap))a(p - q.) 2 a(1 ap:) - -4) 2 0.99a 4t) (57)
Similarly, when Pt < qr. we have
P++1
9-+1
= 1 (1 +
(1-9t) [ (xpp(-ap)) exp(-aqi) + (g. - -p) caall-exp(ppppp -a)))
qt
Dt pt) exp(-caqt)
$ (1 - 0.114)((1
Pt q
(58)
Now we will integrate the above two cases. Statement (B, follows by combining Eqs. 51 and (54) Cases and II respectively. Combining Eqs. (52) & (53) in Case and Eqs. (56) (58) in Case II, we obtain that Eq. (52) always holds whenever pt 2 qi and Eq. (53) always holds whenever pt qt-
Note that when P1 > 5a, Eq. (46) implics that 21 and PETL have the same sign. In this
9r11 case, we can further combine Eqs. (2) and (53) and obtain the following inequality, which proves
the statement (Ct).
P++1 1 s (1 - 0.079a)
Pt. 1 1/.
a++1
Proof of the convergence rate for Ped: - 1
Next, we will prove that Ti { ptlp 1s
< 6a) <
in the following three cases.
(Case I < Pugo 16 S 6a, then Ti = 0.
(Case II) If 16 6a < Pogo < 0.135, then we have 16 + 6a < pege & 0.135 for all 0 1 1
Otherwise, there must exists 0 < t < Ti - such that 16 + 6a < peg: I 0.135 and P1+14++1 < 16*
SO P
1/16 < 1 34a (since a 5 10-3) which contradicts with Eq. (45). Therefore,
Peft
T/16+6a 6a
1 <
1 ba < Pet:
& 0.135 for all 0 < t T 1, so based on the statement (B.), we have
16
16
1
Pogo
0.135
< PT. 10T (1 + 0.110)7--1
S
16
(1 7
28

---

Published as a conference paper at ICLR 2024
which implies that
2.16 In(1 + 0.11a)
7.1
Ti S 1+
S1+
where we use S 10-3
(Case III) If 0.06 < Pude <
T6
1 then similarly we can prove that 0.06 S Pe
<
T6
1 for all
S t Ti 1. Hence, based on the statement (Bt), we have
1 PT PT- 2
Pogo
0.06
_
(59)
16
0.190 21
0.19a))
which implies that
In
T1 111
Im(1 0.19a)
a
where we use a < 10-3
Next, will prove that 0 P:q. < 6a for all 2 T1 via induction. It holds at t Ti based on the definition of Ti. Then suppose P:q: 1 I 6a holds for certain Ti and will prove that 0 S P++ 1++1 - S 6ar in the following two cases.
+ I 6a, then on one hand, based on the statement (Bt), we have (Case 1) If 3a S Prtt- T6
1++1 S Prtt S To
+ 6a. On the other hand, based on Eq. (45) P++14+1 2 (1 340:) 2
(1 0.034) > 0.06.
16
(Case II) O S P. To < 3xx then on one hand, based on the statement (B.), we have P++1 2 On the other hand, based on Eq. 45 Pt410+41 (1+34a)ppa S (1+34x) 10 +3a) S
Pe 2 1
16'
6a.
16
As result, S Peя. 18 S 6a for all 2 Ti.
Proof of the convergence rate for Pt + 1:
Next, we will prove that T3 = {t: p (Ct), we have
1 s 10a)
< a
In ) Then based on the statement
10c
<
PT--1
< (1 0.0799)77>-11
7--1
(1 -0--00 0.079a)
(T2-1
go
2
where
uses
Pu < 1.5. The above inequality along with S 10-3 implies that 3
T2 14 In(20a)
13
In
In(1 - 0..07aa)
a
20
Next, we will prove that [t 1| < 10a for / 2 and suppose that it holds for certain 2 T2. Then if
T2 by induction. This holds for / T2
I 5a, Eq. (46) implies that
qi
Pi+1 - 1 9++1
< Ps - 1| + 4.66a < 10a; Otherwise, if 5a <
Pr
1
S 10a, then the statement (C,)
implics that P++1 1| ge++1
S Rt
1| < 10a. Hence, Pr-1 1
< Pt 1| < 10a always holds and
ge
thus have proved that
Pt
S 10a for all
In
T2-
Obtain the final convergence rates: Combining the convergence rates for P: + 16 and P: + 1. we obtain that 0 S Pelt 16
1 < 6a and | 1 s 10a for all 2 13 In (2))) Therefore, we
conclude the proof by providing the ranges of pt, ge and the lower bounds of Vi(TT,) and Vz(T)) for
t 20 as follows.
Pt v piq:
Pt E di
[ 110a,, ( + 6a) (1 10a) _ [1] 2a, + 14a
29

---

Published as a conference paper at ICLR 2024
Prgt Q: 1
(
Pt
E V
1/16
V
1/16 + 6a
S
20, +
14x
91
1+ 10a"
1 - 10a
4
4
where the Iwo use a I 10-3, Therefore, we can prove that n, is feasible as follows.
(i((T() 2p19: 16 E1:
(2(TT)) = 2(1 - (1) - q:) = - 2(((p + q1) + 2p:qt 2 2 2(2 28a
(1)
1 (6) 1
+
>
E2.
8 8
where (i) uses Pr: 9t 2 14a and p.g. 2 TO. and (ii) uses a S 10-3
G PROOF OF THEOREM 5
Example 2 is equivalent the following constrained optimization problem
max [-
Vo(T) = 2pg
(60)
s.t. Vi((T) == 2pq + + p) q) 2 1.8
which has the unique optimal solution p q = 1.
Proof for the primal-dual algorithm: For the problem computed as follows.
600 the Lagrange function 5 can be
L( A) = VV(TT) + (
2pq + >1 + 2(1 p) q) 1.8)
= 2(1 + +221) 22 + 9) 0.2A
d1 ) )
X1
2x
2(1 + 2X1) (p 2
+ 0.2
1 2x1
1+ 2
For all \ > 0.
1 so arg maxp.g L(TT A) = {(1,, 1)}. Therefore, the primal-dual algorithm always achieves the optimal solution p = q = 1 in the first iteration.
142A;
Proof for the primal algorithm: In the same way as the proof of item 1 for Example the update rules of the primal algorithm as follows.
we obtain
Pr
if hi = 0
Pe + (1 Pt) exp (- -xqee)
Pt+1
(61)
Pt
if Ke 1
Pt (1
Pe) exp (a(1 22())
St
if hi =
Q: + (1 (:) exp ( ap:)
g++1
(62)
q:
if kg = 1
9: (1 q:) exp (a(1 2p:
With initialization Po + go = and po E [0.1, 0.9). we will first prove that Pt + 9: by induction.
Suppose Pt + 9: holds for centain f. Then V (m,) 2p 2(1 p:) ạt) 4pp -11-p)) p:) S 1 < & = 1.8. Hence, the case h; = of the update rules (2) and (43 is implemented which implies that
Pt
Pit1 + 9:+1
+
Pt (1 pt)
exp (a(1 2qt))
9t + (1 qt) exp (a(1 2p:))
Pt.
1 - Pt
+
Pt (1
Pt)
exp (a(1 - -24:))
Pt. + Dt exp (a(24, 1))
(1 pt) exp (a(1 - -2q1) ))
Pt
+
1.
Pt (1 Pe) exp (((1))ye)
(1 pt) exp (a(1 2q:)) Pt
Hence, Ps + qe = 1, which proves that (T(T) = 2p.9: + 2(1 p1)(1 - 9) = 4p, - -p.) $ 1
1.8 for all L.
30

---

Published as a conference paper at ICLR 2024
H EQUIVALENT CONDITION OF ÇA- = 0
Theorem 6. C1 if and only if the Q function has the commonty used factorization structure
below (Guestrin et al.) 2001 Son et al.) 2019 Rashid et al. 2020
Qu(ms,,))= Σ 2am
(Ti (Tis,a (m)).
(63)
Proof. Proof of "if": Suppose Eq. (63 holds. Then for any s, and product policy have
M
A
(m) (T; (7 (m))
m=1
10 mm) (T; (m)) Ve(T;:)]
(mm)) (alim) (T; Vx((TT;) ())
a (3ree
M
M
(( s)
Σ
(mm') ( (T;;),a(m?)
(T;(T);)
m= 1 mmm)
m'=1
M
M
7 71mm) (a(lm))))) 2 ( (T;; s (m)) +
Σ
Qam! (1;3, (V:ss
m=1 allm)
x (a (IT: (T::s,a) almi)
(1m))
Σ
Σ
Σ
(mm))
( (
- VVV(TT))
m=1 =1,m am alm)
M
M
M
(TT;
(
Σ
Σ
(m( (T: mm))))
k
m=1
mn =1 m=m, m=1.mmgm amm)
M
Qu(F;s,a) a) - VT((T;)) + (M (M- 11 1)(
Σ
Σ
(mm (atta))))))) (T, (T; amm)))
(m²)
-M -MM-1)V4 (1)
M
(v0)
A + (M- (M) 1)
ΣΣΣ Σ
(1mm (I;; (T;;,,
ml a(m²) almm)
(M - (T;
M
(na)
A + +(M -1)-(( Σ Σ (als))
am::))(mm))) - ())
m
= + (M - -1) Σ T(als) Qmm) (T, (T))s) (M -1)Ve(T;;)
(wii))
Ax(T,8 + (M - 1) [(ass)[((Tsss)))) - (M - (1)V((TTT;)))
A
31

---

Published as a conference paper at ICLR 2024
where (i) uses the definition of the local advantage function A (T:; 8, a ml))) (ii) uses the rela- a dl)))] where x (a(m))a( := II mmm== x(m²) (a(m))s) denotes the policy of all the agents except the agent m. which can
tionship that (mm)) (TT; 8, a(()) = Eatoo f=a
be seen from the definition of the local Q function Q((T) (TT; 8, alm)) ET Ei T (80
8, 00 = mm))] and the global Q function Q!nh) (1; EE, Ei=o 7 8, 0g a]. (iii) = 1, (vi) uses the definition of the advantage function ATT 8, a) == Qu(T; a) - (T; and uses Eacimy ((lm)((( (a((mm)) (1()m)/)))))))))))))){)) = 1, T (als) for the joint action a = (a(m), aa almm)) and (ix) uses a). This indicates that Si- = O.
(v) and (viti) use Eq. (63), (iv) uses Eorns (a)))
(vii) uses (a (m² ( (|)) (1mm)) (a (s)))))))))))))))))))())
(T(TT::) 8) = E. 7
Proof of "only if": If SA= O, then As(Tis,a) Em= A!Tm) (T:: s, a Hence, we can prove Eq. (63) as follows.
M
M
Q,(T;S,a) = VA(TT:)+ + ( = Vi(TT:)+ +
Σ
1
(Ti (T:s)a(m)
= Σ
(m)) (x; (m)))
m=1
m=1
where (iTT (T; = (m;s, + 1
M (i(TT:))
I SUPPORTING LEMMAS
Lemma 1. Any optimal Lagrange multiplier X E arg minxeRN max L(T, A) satisfies the following range.
X
S AK. max ==
+ On
k 1, K.
(64)
2
8z(1 7)
Proof. Use the policy से in Assumption (i.e., Vi((T) >
EL + 5ς) and denote *" as the optimal Then have
solution to the constrained cooperative MARL problem ①g.
Vo(T*)
max min I.TT, A) AER
max L(T, x²) -A
> L( - A
Vo( + Σ (V(Va(F) -x) -x)-A -A
(a8)
K
2 A
k=1
where (i) and (iii) use Va(T)) E [0, 1/ - 7)] since (s a) E [00,]. 1]. (ii) uses the definition of the
duality gap A in Eq. (6. and (iii) also uses \ 0 and (T((T) E + ôg. Since Xi. 6z O, the above inequality implies Eq. (64).
d For any probability vector p Rdd (every entry ps 2 and Ek Pk 1) and any b Rd, denote the probability vector q E Rd with entries qu Σd Ei=1
Lemma 2.
Then the distance
between p and q has the following upper bound.
l1g pll
Σ 1ak- pkl Umax Umin
(65)
where brax g by and buin min giga by-
32

---

Published as a conference paper at ICLR 2024
Proof. For t [0, and & = 1,2,.................... .,,,,, d, define the following function
Σ D
uk (1)
(66)
which has the following derivative bound.
Phb ebbne tbe E/=1 P3
P 1b Dg j= o11Debbe
(x((
(2i=1 pyelos)
Σ/= j=1 Pb by )e00)))
EE/= Pyettyy )2
Ph tbe
23 Pj bbx byleth
(2/=1 Pjeths) D )2
Phe (bmax - bminn) Ej= pjeth id E===1 D)e
the (bmax bmin)
(67)
j-=1 Si=1Djethy
As result,
d
L 2/ (f)tt)
{
Ok p&l
Σ (1) vo)
Σ k=1
S
Σ (v((t) S 6max 6min.
Next, we change initial state distribution P to be any state distribution p', and replace the value function (T( (defined in Eq. (I) and occupation measure V/+1 Vx (defined in Eq. 2 with Vespp (T) and 1/41:p/ respectively to emphasis their dependence on p'.
Lemma 3. The policy ne and index ki generated from Algorithm satisfy the following bounds for any state E S.
Σ m== a(m)
Σ
(m) (a("))s)) S Ma ( (a(m))s) m.( me+
(a(1-- + 203)
1
(68)
1-
Ma
2Maxaa
VA, (M+4150)) Vk, (mG (')
(69)
71 1-7
Proof. First, consider two MDPs {S,, A. h. (S AT following the same transition kernel P and policies Ne and T respectively. Then the state transition distribution of the two MDPs are P(S S' = s) En P(s'ls, (a)((())))) and p' (s(''ss) P(S
respectively p(s'ls) s'|S' = 8) = E. P(s" a), (a)s) respectively. Denote p, and pt as the distribution of S, and S respectively under the same initial distribution po = p6 p'. Then we have
||p411 Pitill1 = Σ (54) Pit1(s')]
Σ (p'(5'(s)pp(s)) - p(s'(s)p((ss)
Σ [p((s)(p'(ss)))) p(51ls))
-((sss))) + +Σ Ep(s(1s)6((s) pp((s)
E ((s))''()))))) -(()))))))>)(()))))))))))
p(5(ls) -p((s)
Edl(s) ΣΣ (() (als) (alss) + llf - -pali
< max ||Te (-|s) no (15)) + 11 - pill1-
(70)
33

---

Published as a conference paper at ICLR 2024
Since P6- Pu, iterating the above inequality yields that
ll Pill1 S i max [| m. (-(+)))]n-
(71)
8
Hence, the state occupation measure difference can be upper bounded as follows.
U|e 1:0 (-) Mesp" (-1l1 1 (1 (1-7)
y llp Pilla
(1 7) max (++1) Te(-15)l1 Σ iny
max ||T (-|s) Te. T-(+ss]]11
(72)
where (i) uses Eq. (7I) and (ii) uses the fact that the function f(7) Lin 7" = (1-7)-1 has the following derivative
- = b (1-
(73)
1=0
Therefore, the state action occupation measure difference can be bounded follows.
|| (s.) - Vtpp/ (:, 1112
Σ |141:p' (s) Pep (e (s)s)
Σ PL41: (s) nr(a|s)] + Σ [e((a))) (s) Vt:p (s)
8,0
s,a
M1+1:p [T)][ - (-(1s)] + |1241;100))) - 12s00 (-)112
(8)
< max | (-1s) Te(+s)]l1 + 1-7 max (115) - =e(-1s)]11
7
max (11))(11))))))))))))))))() m.(115)11,,
(74)
where uses Eq.
72
To bound the policy difference [|+=) Te(-1s)l11. we rewrite the NPG rule [1 as follows
z (s) Σ n
(m) (am(m) (s exp (aQ( (Te s, (at)))
(75)
(mm)
(m)
(a (m
(m) xt41
(a (1m) (s)
me
exp (aQ (अ 8, am))))
(76)
7 (m)
Therefore,
|e+ (:1s) --((-s)))l
Σ
(m) Lii (m()))s) (s)
II m=l
(m)
(m(mm)))) [s)
m
M
m
M
m
M II m=m!
(a (s)
mt
(m) (m(())]s)
II
me+1 (a (a (m)))))
s)
(m)
(a (m)
m
m=1
m=m +1
m=1
M
M
(m) s)
(m) ( (a(m)|s)) mmm (al (m())))s)) n (m') (m') (a
π
m
m=m!+ +1
(12) (a(m))s) (s)
. (m) (a (m) [m)) |s]
pmn)
34

---

Published as a conference paper at ICLR 2024
M
(m)) (Tg; ( min (m)) (m))
(Tz 8, a (m))
max a())
m=l
M
(m)) kr (mii - min (m)) a(m)
2arra (Te; 8, al!))
S
max a(m)
m=1
+ 2 max (2/m)) (Teis,a(m)) Qbm (Tei ((ris,a(m))) a(m)
(iv)
Ma
+ 203)
(77)
where
(i) uses the following relation for any joint action a where (m) II IIm= "f (m) (a(m)) [s), (ii) and (iv) prove Eq. (iii) applies Lemma
m' (me)
" M+1 (a(m)) (s)
m=1
where the (mm))th entries of vectors p, b, q E Rildm are oe (m)) (m)) s). (mez 8, ml)) and
m)
(a (m) respectively, and (iii) uses (m)) (T: (m)) (m)) E [0, 1/(1 7)] since Thet E [0,
M
M
- =
(a) - -ma
S
C (a) 11
mY
m/=1
As result, Eq. (69) can be proved as follows.
Vi, (T++1iP') - Vva (Te:p')
Σ
Fh (s, a) [ut+1:00 (8, a) - Vep (s, a)]
5,a
(
|| (1. - 1/ (11111
(1))
(1 7)² max ( (-(118)ll
Ma
2Macs
(1 (1- + (1 7)
where (i) uses FR. (8, E [0, 1J. (ii) uses Eq. 74 and (iii) uses Eq. 77
35

---

Published as a conference paper at ICLR 2024
J COMPARISON OF CONVERGENCE RESULTS ON CONSTRAINED COOPERATIVE MARL
Table 1: Comparison of Convergence Results on Constrained Cooperative MARL
Works
Algorithm
Assumptions
Convergence measure
bounded reward,
Lu et al.
2021
primal-dual
Lipschitz continuity,
gradient
Slater's 's condition bounded reward, Lipschitz continuity,
Ying al. (0233
primal-dual
gradient
bounded optimal
Lagrange multiplier"
Fixing base policy, perturbation policy in compact convex space Lipschitz continuity
convergence of perturbation policy
Yang et al.
2023
primal-dual
bounded reward
constraint violation optimality gap constraint violation
Algorithm Ours)
primal-dual
Slater's condition
Algorithm 2 (Ours)
primal
bounded reward
optimality gap
K EXPERIMENT ON CONSTRAINED GRID-WORLD
We slightly adapt the constrained grid-world task (Diddigi
al. 2019) where two agents explore the 4 grid-world
in Figure 2 The agents start from position 3 and aim at the target T1. Both agents can observe their positions and accordingly select move up, down, left right. If an agent m has reached the destination (target 11), then will always
12
13
14
15
8
9
10
11
stay there and obtains reward (m) 0 regardless of the selected action. If an agent is at a non-target marginal grid and the action points outside the grid, then the agent stays there and obtains reward -5 (For example, an agent will stay position 7 if it selects move right.). In all the other cases, the agent moves one step and obtains reward -1. The safety score (((m)) -1 for both agents
4
5
6
7
0
1
2
3
1,2 if they collide a non-targes position (including initial position 3). Otherwise, (m)
Ti,t = 0. The discount factor is 0.9 and the safety threshold is ı -1, which allows no collision between the agents except at the initial time. Therefore, the optimal solution is to let the agents deterministically select the two paths shown in Figure 2 respecivelly with Vo(=) = -2.6695 and Vi (T) 11 which indicates that this problem has zero duality gap.
Figure 2: Constrained grid-world.
We compare the non-stochastic versions of the primal-dual algorithm (Algorithm T. the primal algorithm (Algorithm (2) and the centralized nested actor-critic (CNAC) algorithm (Diddigi et al. 2019) on this constrained grid-world task where transition kernel and reward/safety score functions are available. Specifically, in Algorithm
D we use 50 value iterations to obtain the greedy policy Te. exactly evaluate (m.) = V*(=.) I- Σ..a Fo a)ua, (8. a) where the occupation measure Mx, (s,a) is known be the stationary distribution of the mixed transition kernel (- a) := (-|s, a) (1-7))(() and update the multipliers with stepsize 3 = and threshold X A1_max 10. In
Algorithm 2 we also exactly evaluate (i() Vie(m)) and ()(²) (mT 8, (m)) = (m)) ( s, (m))
and select stepsize a = 1 and tolerance 7) = 10-3 The CNAC algorithm essentially follows the duilal-dual framework (Algorithm except that the policy n. updated with one projected
36

---

Published as a conference paper at ICLR 2024
stochastic policy gradient ascent step follows.
π f Projv, [T
Here, Vp is the product policy space, and we use the exact policy gradient V (T, A,) = V=L(T, and select stepsize 0.2. The update rule of the multipliers for the CNAC algorithm is the same as that for our primal-dual algorithm.
We implement these algorithms for 100 iterations. The initial policy of each agent at each state is randomly generated from Dirichlet distribution Dir( (, 1, 1). We plot the learning curves of (T( and (Te) in Figure 3 It be seen from Figure that all these algorithms converge fast the feasible region V1 (
within 10 iterations. As to optimality, our primal-dual algorithm -2.6695 within iterations and 70 iterations respectively. The CNAC algorithm converges to a sub-optimal value (o(T)) & -4.5 within 10 iterations, since it uses policy gradient ascent update which may stuck a stationary point.
and primal algorithm converge to the optimal value (o
-12-
-14
Volle!
-1.5-
-10
Our Primal-Dual Aigorithm
-12
Our Primel-Dual Algorithm
Our Primal Algarithm
-14
CNAC Algorithm
Primal Algorithm
Threshold & = 110 minV (m)
Algorithm
16-
Ve -2.0895 of the optimel poth.
-24
20
40
60
80
100
100
Figure 3: Results on the constrained grid task with constraint V1(TT) 2 1.
Furthermore, decrease the threshold & to -111, where the deterministic paths in Figure 2 become near-optimal and the duality gap becomes nonzero. We implement these algorithms for 100 iterations using the same initial policy that for the threshold uses stepsize B = and 50 value iterations. Our primal algorithm uses stepsize a = 0.4 and tolerance 0.8 and 3 1. From the result in Figure 4
-1. Our primal-dual algorithm
" 10-3 The CNAC algorithm uses stepsizes we can see that all the algorithms become less stable in the constrained-related value V/1 (Tr) and occasionally falls below the threshold -1.1 due the nonzero duality gap. Regarding the objective (T our primal-dual algorithm and primal algorithm converge to the near-optimal value, and primal-dual converges faster, but CNAC converges lower sub-optimal value.
Volmn)
-1.
-10
-1.8
Our Primal-Dual Algorithm
-12
Our Primal-Dual Algorithm
-2.0
Our Primal Algorithm
-14
CNAC Algorithm
Primel Algoritim
-2.-
Threshold & -11
Algorithi
-16-
Vs 22 66.5 the near-optimal peth.
mjnV.(m) -1
20
40
60
80
100
20
100
Figure 4: Results on the constrained grid task with constraint Vi(TT) 2 -1.1.
37


Reviews:
[{"review_id": "IAeIWq4btR", "reviewer": "Reviewer_ditR", "summary": "The paper first examines whether strong duality holds for the constrained cooperative MARL setting (a problem which has been studied in previous works). In contrast to the constrained single agent case where strong duality holds, the authors reformulate the constrained cooperative MARL problem as a constrained optimization problem on the occupation measure associated with the agents’ product policy, and prove that strong duality does not hold for constrained MARL case, because of the existence of non convex constraints (related to the product joint policy). They establish the first convergence rate result that characterizes the impact of duality gap on the constraint violation and optimality of the output policy of the Primal-Dual algorithm. In particular, both the optimality gap and the constraint violation converge at a similar sub-linear rate, but the latter up to a convergence error that depends on the duality gap of the problem. Furthermore, the paper proposes a primal-based algorithm for constrained cooperative MARL with the convergence not involving the duality gap, based on decentralized NPG policy updates. In particular, the authors show that both the optimality gap and the constraint violation converge at the sublinear rate, up to certain convergence errors that depend on defined advantage gaps. The authors also show that these advantage gaps vanish if and only if the Q-function has a certain factorization scheme. Last but not least, the paper explicitly compares the two algorithms and proves that each of the two algorithms can be better than the other in certain scenarios.", "questions": "I have the following questions regarding some technical details of the paper:\n- In the proof of Theorem 3, the authors have assigned $\\lambda_k$ with a value larger than $\\lambda_{k,{max}}$ (page 19). Can the authors be more explicit about why they are able to assign $\\lambda_k$ with such a value?\n- In the proof of Theorem 7, can the authors be more explicit about the proof steps and explain what $\\pi_{\\omega}$ and $\\omega$ are?\n- In the proof of Lemma 3, can the authors be more explicit about the last inequality of page 33?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The paper is well-motivated, since strong duality has not been validated in previous constrained cooperative MARL works and the duality gap is crucial for the convergence of the Primal-Dual Algorithm.\n- The paper is very well-written and easy-to-follow with concrete examples and good intuition of the examined algorithms.\n- The paper introduces some novel technical elements, such as the upper bounds in inequalities (17) and (19) on page 8.", "weaknesses": "- The assumption of the decomposition schema of the Q-function, that the advantage gaps depend on, seems limiting. Is the assumption necessary to ensure the computational tractability of the problem? Moreover, in practice, similar assumptions (on the linear decomposition of the Q-function) can harm performance, even in the unconstrained setting (e.g. see the comparison between VDN and QMIX (Rashid et al. 2020)).\n- It is not clear by the authors if the paper can be compared with other state-of-the-art algorithms (if exist) in terms of the optimality gap (in the constrained cooperative MARL setting).", "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": "", "extra_scores": {}}, {"review_id": "uo2OA59fta", "reviewer": "Reviewer_WbB4", "summary": "This work concerns a problem of MARL known as Constrained Cooperative MARL (CC-MARL). In such a setting, multiple agents share a common reward function that depends on joint action and the transitions of the underlying MDP depend on that joint action as well; further, apart from striving to maximize the expected discounted cumulative rewards they will get, the agents attempt to minimize a set of constraints. Those constraints in fact concern the expected discounted cumulative costs.\n\nExisting literature has offered results for correlated policies -- rather than product ones. The authors demonstrate that the problem of CC-MARL admits a formulation as a mathematical program with nonconvex (bilinear) constraints which is known to be NP-hard, in the general case. In general, in such a case, a solution of the CC-MARL is a product policy that will have an approximately zero single-agent optimality gap and constraint violation. The optimality gap is just the gain a single agent can have by unilaterally deviating from the joint output policy and the constraint violation is the amount by which a constraint is violated.\n\nThen, the authors demonstrate how the existing primal-dual algorithmic framework only manages to provide a bound on the constraint violation that depends on the *duality gap* of the underlying lagrangian function. This means that existing art can only offer solutions that could potentially have a constraint violation as large as the maximum possible discounted cumulative reward.\n\nFinally, the authors design an algorithm based on the single-agent RL CRPO algorithm. Convergence is proven using a potential/Lyapunov function argument. The optimality and constraint violation bounds depend on a quantity known as the *advantage gap*. The advantage gap in turn is zero if and only if the q-functions can be decomposed in a sum of functions that only depends on single-agent actions.", "questions": "What were the main challenges you faced in proving a definitive refined hardness result?\n\nWhat would be the advantage gap if the reward functions admitted a network-separable structure and the transitions were additive?\n\nDo you think that the dependence on the advantage gap is tight? Can it be improved, or is it yet another indication of the hardness of approximation of solutions of constrained cooperative MARL problem solutions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors extend previous work that existed only for the case of correlated policy optimization to a product policy setting. They even improve single-agent RL bounds for the CRPO algorithm.\n\nThe paper offers a rather rich exposition of previous theoretical results in the literature of (constrained) cooperative RL.", "weaknesses": "A weakness of the authors' result is the lack of a definitive answer as to the hardness of the problem of Constrained Cooperative MARL. Indeed, the fact that the optimization program corresponds to a mathematical program with bilinear constraint functions is an indication of its potential hardness, yet there is a multitude of refined computational complexity classes that it could belong to. Is the problem *total*, i.e., is the problem guaranteed to have a solution? If so, it will belong to the TFNP complexity class. Then, does it belong to some known classes such as PPAD, PPA, CLS, PLS?\n\nI believe the paper has merit in extending previous results that considered correlated policies to quantifying the effect of being restricted to product policies. That being said, the narrative and even the title of the introductory text could benefit by stressing this fact rather than putting the focus on the hardness, since there is no definitive answer of the computational complexity.", "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": "", "extra_scores": {}}, {"review_id": "NAWglhvJjg", "reviewer": "Reviewer_Ycbe", "summary": "The paper provides a comprehensive analysis of the strong duality condition in constrained cooperative Multi-Agent Reinforcement Learning (MARL), (for the first time) revealing its failure to hold and its impact on convergence rates of primal-dual algorithms. Then the authors presents/proposes a new decentralized primal algorithm to avoid the duality gap in constrained cooperative MARL. But their analysis shows that the convergence of this new algorithm is hindered by another gap induced by the advantage functions.The authors contribute to the understanding of the complexity of the constrained cooperative MARL problem by comparing it to cooperative MARL and single-agent constrained RL, and It is rigorously showed in this paper that constrained cooperative MARL is fundamentally harder than its special cases of cooperative MARL and constrained RL. Note that, before this work, strong duality has not been formally validated in constrained cooperative MARL, and therefore leaving convergence of the existing primal-dual type algorithms obscure.", "questions": "see weakness section comments.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n\nThe problem studied in this paper is important and interesting, and the valuable findings here could be beneficial to MARL research community.\n\nThe paper provides a comprehensive analysis of the strong duality condition in constrained cooperative Multi-Agent Reinforcement Learning (MARL), (for the first time) revealing its failure to hold and its impact on convergence rates of primal-dual algorithms.And then the authors present/propose a new decentralized primal algorithm to avoid the duality gap in constrained cooperative MARL.\n\nThe authors compare the primal-dual algorithm with the primal algorithm and show that neither of them always outperforms the other in constrained cooperative MARL, both theoretically and experimentally. Such theoretical and empirical  analysis are valuable to better understand hardness of constrained cooperative MARL and the performances of different algorithms.\n\nThe authors contribute to better understanding of the complexity of the constrained cooperative MARL problem by comparing it to cooperative MARL and single-agent constrained RL.", "weaknesses": "The authors identify and reveal the issue about the previous primal-dual algorithms for constrained cooperative MARL, which is valuable, but the contribution would be much more significant if the authors could also propose a solution to successfully solve this identified problem . \n\nThe authors did attempt to propose a new decentralized primal algorithm to resolve the detected issue/challenge, but it seems no much success of the proposed solution. The proposed decentralized primal algorithm's convergence is hindered by a gap induced by the advantage functions, which can be seen as a major limitation. The comparison of the proposed decentralized primal-dual algorithm with the existing primal-dual algorithm doesn't seem to clearly indicate that the proposed new approach is a consistently superior approach, which makes the paper's contribution less significant.\n\nThe paper is highly theoretical, and comprehensive empirical validation/comparison of the proposed solutions are mostly missing. It would be great to also see some more comprehensive empirical experiment analysis on broad representative tasks (rather than just some very limited extreme case examples in current manuscript).\n\n(Though I have to admit that, although the authors are not able to successfully propose a solution to solve the issue, (for the first time) identifying this important problem/issue about  primal-dual algorithms for constrained cooperative MARL itself might be already quite valuable, and its contribution might possibly enough for publication on ICLR. Though if they are able to also provide a successful solution (in addition to identifying the problem), it would be a much stronger paper.)", "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": "", "extra_scores": {}}, {"review_id": "tcBbqFcVUV", "reviewer": "Reviewer_MmRm", "summary": "The paper studies cooperative multi-agent RL problems in which all agents aim to maximize the average reward value function subject to a constraint on the average safety value functions. The authors provide a counter-example to show that the strong duality fails. Nevertheless, the authors extend two existing constrained policy search methods in the single-agent setting to cooperative multi-agent RL under constraints and prove their non-asymptotic optimality gap and constrained violation error bounds. The authors also investigate the pros and cons of the two methods in numerical examples.", "questions": "- Is the non-product form of optimal policy the only reason for the duality gap? Does there exist a more fundamental metric that can characterize the cause of the duality gap?   \n\n- As shown in convergence analysis, the effect of the duality gap in different algorithms can be different. Does this suggest a better way to design algorithms? Is it possible to remove such gap dependence?  \n\n- The advantages of the two algorithms are discussed in terms of policy iterates, which are stronger than the output policy in algorithms. Is it possible to show them in convergence theory?  \n\n- As mentioned, prior works also studied constrained cooperative Markov games and the authors have improved the analysis. Can the authors illustrate the analysis differences due to the lack of zero duality gap? It is useful if the authors could compare assumptions and results with them in a table.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written, and statements are supported by justifications. \n\n- The authors show the existence of a strict duality gap in a simple example of cooperative constrained MDPs. This structural property reveals the limitations of methods in the single-agent case, which is useful for developing new algorithms.\n\n- The authors present a primal-dual algorithm and investigate its limitation by revealing the dependence of error bounds on the duality gap.      \n\n- The authors also present a primal algorithm that works in a decentralized way, and provide finite-time error bounds on the optimality gap and constraint violation. \n\n- Numerical examples are provided to show that either one can perform better than the other.", "weaknesses": "- For the duality, the authors didn't discuss the connection to the duality of constrained Markov potential games: Provably Learning Nash Policies in Constrained Markov Potential Games. Since constrained cooperative Markov games are a particular case, a non-zero duality gap directly follows. \n\n- Due to the non-zero duality gap, the proposed two algorithms suffer some gaps caused by the multi-agent and constraint coupling. It is more expected that the primal-dual algorithm suffers a duality gap. The primal algorithm has a dependence on an advantage gap that is less expected. It is not clear if these gaps are necessary and which one is better. \n\n- It is interesting to check the policy iterate convergence of two algorithms in simple examples. If this can be proved for the algorithms under certain conditions, it would be more beneficial to guide the practice.\n\n- Experiments are done with artificial examples. It is favorable to check the performance of the two actor-critic algorithms for solving real constrained tasks, and compare it with existing methods as mentioned.", "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": "", "extra_scores": {}}, {"review_id": "5wBH0Kqb73", "reviewer": "Reviewer_2Wr4", "summary": "This paper studies the hardness of constrained cooperative multi-agent reinforcement learning. In particular, it argues that there is a strictly positive duality gap. In addition, neither primal-dual or primal algorithms are strictly better than the other one.", "questions": "The paper seems to want to say that the problem is NP-hard but stops short. It seems that the quadratic equality is more of an analogy rather than equivalence to standard optimization problems. It would be good to make this more precise.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper addresses an important question. \n+ The paper is well-written. \n+ The results seem correct and the explanations and theorems make intuitive sense.", "weaknesses": "- The bound $\\Delta$ seems to be trivial? It just comes from the geometric sum and assuming that the risk at each step is less than 1?\n- I'm not sure I see the only if part of Theorem 7. \n- It would be good to offer some advice on when to use which type of algorithm. \n- Some simulation would be helpful to illustrate the results.", "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": "", "extra_scores": {}}, {"review_id": "32orOKi2H0", "reviewer": "Reviewer_fuRV", "summary": "The paper studies a constrained MARL problem, where a group of agents operate independently in an MDP and jointly optimize a reward function. There are safty constraints that must be satisfied by their joint policy as well. The first focus of the paper is on the hardness of the problem, where the authors showed that strong duality does not hold. The authors then propose a decentralized primal approach to solve the problem. Via examples, it is illustrated either the decentralized primal algorithm or the primal-dual algorithm outperform the other in all cases.", "questions": "Is the problem known to be hard without the safety constraints (with only the product constraints)? How much is known about this in the literature?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem studied is interesting and relevant to the topics of ICLR. The authors made efforts to derive rigorous analyses of the problem.", "weaknesses": "From a computational perspective, the statements regarding the hardness of the studied problem are rather loose. Theorem 1 shows that the problem can be reduced to an optimization problem with quadratic constraints, which is in general hard. But nevertheless this doesn't imply the constrained MARL problem is also hard (for that requires a reduction in the other direction, i.e., quadratic optimization can be reduced to the studied MARL problem). Statements such as \"some studies argued that it is **probably** an NP-complete problem\" and  \"Thus, constrained cooperative MARL is a hard problem due to the presence of safety and product policy constraints\" are very loose. It also unclear whether the hardness comes from the safety constraints or the product constraints. Results in the subsequent sections do not seem to provide any clear message regarding the computational complexity of the problem, nor the time complexity of the algorithms discussed. Overall, the insights provided are a bit limited.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)