Finding Correlated Equilibrium of Constrained Markov Game: A Primal-Dual Approach
Authors: Ziyi Chen
Shaocong Ma
Yi Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: constrained Markov game
correlated equilibrium
strong duality
reinforcement learning
primal-dual algorithm

Abstract: Constrained Markov game is a fundamental problem that covers many applications, where multiple players compete with each other under behavioral constraints. The existing literature has proved the existence of Nash equilibrium for constrained Markov games, which turns out to be PPAD-complete and cannot be computed in polynomial time. In this work, we propose a surrogate notion of correlated equilibrium (CE) for constrained Markov games that can be computed in polynomial time, and study its fundamental properties. We show that the modification structure of CE of constrained Markov games is fundamentally different from that of unconstrained Markov games. Moreover, we prove that the corresponding Lagrangian function has zero duality gap. Based on this result, we develop the first primal-dual algorithm that provably converges to CE of constrained Markov games. In particular, we prove that both the duality gap and the constraint violation of the output policy converge at the rate $\mathcal{O}(\frac{1}{\sqrt{T}})$. Moreover, when adopting the V-learning algorithm as the subroutine in the primal update, our algorithm achieves an approximate CE with $\epsilon$ duality gap with the sample complexity $\mathcal{O}(H^9|\mathcal{S}||\mathcal{A}|^{2} \epsilon^{-4})$.

Finding Correlated Equilibrium of Constrained Markov Game: A Primal-Dual Approach
Ziyi Chen, Shaocong Ma, Yi Zhou Department of Electrical and Computer Engineering
University of Utah Salt lake city, UT 84112 fu1276972, s. ma, yi zhou)
Abstract
Constrained Markov game is fundamental problem that covers many applications, where multiple agents compete with each other under behavioral constraints. The existing literature has proved the existence of Nash equilibrium for constrained Markov games, which turns out to be PPAD-complete and cannot be computed in polynomial time. In this work, propose surrogate notion of correlated equilibrium (CE) for constrained Markov games that can be computed in polyno- mial time, and study its fundamental properties. We show that the modification structure of CE of constrained Markov games is fundamentally different from that of unconstrained Markov games. Moreover, we prove that the corresponding Lagrangian function has zero duality gap. Based on these results, we develop the first primal-dual algorithm that provably converges CE of constrained Markov games. In particular, we prove that both the duality gap and the constraint violation of the output policy converge at the rate O /T Moreover, when adopting the V-learning algorithm as the subroutine in the primal update, our algorithm achieves approximate CE with duality gap with the sample complexity O S.Ac (.)
Introduction
Markov game [43] is fundamental problem in game theory where multiple agents compete with each other by interacting with dynamic environment. It has broad applications in diverse fields,
including board games (44) inverse reinforcement learning [61] market pricing (34] etc.
In the existing literature, the goal of Markov game is often formulated achieving Nash equilibrium (NE) a product policy under which no agent can benefit via deviating from its own policy alone. Although NE has been shown exist for general Markov games (22) computing NE turns out be except for some special
a PPAD-complete problem that cannot be solved in polynomial time 17 32
or potential structure 33 58) This further motivates researchers to consider other surrogate notions of equilibrium that are slightly weaker than
Markov games with zero-sum structure [6] 2T 63 64
NE but are computationally tractable, and correlated equilibrium (CE) is such a classic and popular surrogate notion [40] (see Section (2 for the formal definition) for which many convergent and efficient algorithms have been developed very recently (71 46).
While Markov game has been well studied, its formulation has limited applicability to real-life applications where the behavior of agents is usually subject to certain constraints. For example, in an uplink time division multiple access (TDMA) cognitive radio network, each user's total latency cannot exceed a threshold average (62]
anti-jamming system, the jammer aims to jam ligitimate signal transmitter under average power constraint (27). To overcome this limitation, constrained Markov game has been introduced where agents compete with each other under local behavioral constraints encoded by state value functions ( However, most existing works on
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

constrained Markov game only studied Nash equilibrium (NE) that is PPAD- to compute
3 24 30 45 48 52 59 60 62] and a tractable notion of correlated equilibrium (CE) has not been formally defined for constrained Markov games. To the best of our knowledge, (26) is the only work that explored CE in constrained Markov games. However, they define CE based on the unconstrained Lagrangian function associated with the constrained Markov game, which does not correspond to an equilibrium of the original constrained Markov game, Therefore, the goal of this work is to formally define a tractable notion of CE for constrained Markov games, study its fundamental properties and develop provably convergent and computation-efficin algorithms for achieving such an equilibrium, we further elaborate below.
To achieve this goal, we need to explore and address several fundamental problems. First, while one can generalize the definition of CE of Markov game to the constrained case, it may possess fundamentally different structures due to the presence of constraints. Specifically, as we introduce later in Definition 2.1] modification (of actions) is a key structure of CE. In standard Markov games (without constraints), CE is equivalent under both stochastic and deterministic modifications. However, it is unclear if such equivalence still holds in constrained Markov games, which critically affects the formal definition of CE as well as the algorithm design. Second, a classic and powerful tool to handle constrained problems is the strong duality of the associated Lagrangian, which has been established for NE of constrained Markov games 62). Thus, we are inspired to explore strong duality holds for CE of constrained Markov games, which is challenging problem due to the complex modification structure of CE and the nonconvex Lagrangian. Lastly, once we have a comprehensive understanding of the above two problems, we can hope for a provably convergent and efficient primal-dual algorithm for finding CE of constrained Markov games. In particular, it is much desired to analyze the non-asymptotic convergence rate and sample complexity of the proposed algorithm, as the existing algorithms for constrained Markov games either lack convergence guarantee (30) or only have asymptotic convergence guarantee 62]
1.1 Our Contributions
We define a notion of CE for constrained Markov games generalization of the CE for Markov games. It is defined as an equilibrium at which no feasible stochastic modification of the joint policy from any agent alone can improve the associated value function (see Definition 3.2). Such generalized CE turns out to possess a structure of modification that is fundamentally different from the CE of Markov games. Specifically, we prove in Theorem [ that our proposed CE for constrained Markov games is strictly stronger with stochastic modification than with deterministic modification. As comparison, the CE of Markov games is equivalent with both types of modifications. This fact motivates defining CE with stochastic modification for constrained Markov games, which further lays the foundation for developing the strong duality result and the primal-dual algorithm later.
We study the Lagrangian function associated with the proposed CE for constrained Markov games and prove that it has zero duality gap (See Theorem 3) Such a result is the key for developing a convergent primal-dus
algorithm. Compared with the strong duality established in the existing works 2 30 42 the proof of our result for constrained Markov games requires new technical developments. To elaborate, the existing works yield Lagrangian functions that are defined over the entire unconstrained policy space. As comparison, our Lagrangian function is defined over the set of stochastically modified policies, which corresponds to subset of the policy space over which the Lagrangian function is nonconvex. To address this challenge, we transform the Lagrangian function from the policy space to the corresponding space of probability measures on episodes induced by the stochastically modified policies. We show that the transformed Lagrangian function is linear and the transformed space is convex and compact, which further implies the desired strong duality.
Then, we propose the first primal-dual algorithm that provably converges to CE of constrained Markov games. In particular, the primal update of our algorithm requires to compute an approximate CE of an unconstrained Markov game associated with the Lagrangian function, which can be efficiently solved by many existing algorithms, e.g., V-learning [3 [46) and Nash Value Iteration (37). We prove that both the duality gap and the constraint violation of the output policy produced by our algorithm converge at the rate O ( ). where T denotes the number of iterations. This rate is comparable
to that of the primal-dual algorithm for single-agent constrained reinforcement learning [18] 19). Moreover, when adopting the V-learning algorithm as the subroutine in the primal update, our algorithm achieves an approximate CE with duality gap and constrained violation with the sample

---

complexity OAH where H denotes the episode length, S, A denote the cardinality of the state space and action space, respectively.
1.2 Other Related Work
Markoy game: (53) introduced coarse correlated equilibrium (CCE) for Markov game that is weaker than CE. Many algorithms such as V-learning [31 46) and Nash Value Iteration (37] can achieve an approximate CCE with finite time convergence guarantee. Various other Markov game settings studied mean-field Markov game with a large number of agents. In a Stackelberg game 88 50]. agents are partitioned into leaders and followers. The followers select the best response to the leaders' actions, and the leaders' goal is achieve Stackelberg cquilibrium which corresponds to the leaders' optimal strategy. Strategic game can be seen as a special case of Markov game without state and transition [41). Extensive-form game (10 23 33 65
have also been studied. For example, 14 25
can be seen as a special case of Markov game where any state can only be reached from a unique state at the previous step due the tree structure of the game.
Constrained reinforcement learning: Single-agent constrained reinforcement learning (RL) is a single-agent RL problem with behavioral constraints. It is usually formulated as constrained Markov decision process [2). which can be seen as special case of constrained Markov game with only one agent. Various primal-dual algorithms have been proposed for single-agent constrained RL [12 18 19881196666 39 56. Other types of algorithms include Lyapunov-base algorithms that use Lyapunov functions [2] interior point methods that use logarithmic barrier functions (38), policy network with a special layer to encode constraints [15), and primal algorithms that update the policy via alternatively maximizing the objective function and minimizing the violated constraints (54)
2 Preliminaries of Markov Game
We consider M agents playing a Markov game over a finite time horizon of episode length H. Specifically, at every time step h = L...., H, the agents observe a global state E S of the environ- ment, where S denotes the state space. Then, the agents take joint action as =[o .....,........................ a (M0 following a joint stochastic policy nı (-181:h, (1:(k-1)), which corresponds to a distribution on the joint action space A := II A(m²) and depends on the past states $1th := {st t== and past actions 41:(k-1) == {at M After that, the global state of the environment transfers to a new state sh+1 fol- lowing the state transition kernel P(-|s), aA),, and each agent m receives local reward ro.h (sh, an) from the environment. We note that here the joint policy πтi can be non-product (i.c., cannot be factorized into product of independent policies associated with the agents) and non-Markov policy.
In the above Markov game, each agent collects its own rewards over the episodes. Denote p the initial state distribution, we can define the following value function associated with agent m.
H (sh. an) $1 p]:
(T) := E
(m)
(1)
which corresponds to the expected cumulative reward received by agent m under joint policy π == (TT) ) M== and initial state s. The goal of agent is to optimize its own policy xr (mm) {m(mm) l==1
in order to maximize its associated value function (()") However, since every agent's 's value function is also affected by the other agents' policies and actions, the agents must compete with each other to gain more rewards until they reach certain equilibrium. Here, we introduce two popular equilibrium notions that will be discussed throughout the paper.
Nash Equilibrium (NE). A joint policy ı is called an NE if the following two conditions are met: (i) for any time step h, the joint policy Th is product policy that can be factorized into a product (1) of independent policies, i.e., Ty - x .... x n ((a)) so that the agents take independent actions;
(Mf)
(ii) For any agent m with any associated policy ((m)), it holds that vi() (x) 2 vi("m) (7()) (1")).
Here, ((m) denotes the joint policy of all the other agents excluding the agent m, and 'x" means
that ((m) is independent from x/ (((m))
In other words, at NE, no agent can improve its value function by deviating from its associated policy. In the existing literature, it has been shown that computing NE is PPAD-complete problem [7 32
3

---

for which it is not possible to develop polynomial -imee algorithms, This observation has motivated researchers to propose a surrogate correlated equilibrium (CE) notion [40]. Before introducing the formal definition of CE, we first define the following stochastic modification operator.
((m) as agent m 'ss action Definition 2.1 (Stochastic modification). For any time step h, denote O₁, induced by joint policy The Given the past states and actions s 01:(h-1), stochastic modification
(m)) (associated with agent m.) is distribution that randomly maps dj to another action al!") Ph
(1n)
i.., aj ~@h (m)) (-|s1:h, a1h-1,0 (mm)), Moreover, we denote Uh (m) as the joint policy modified
(mm)
(m) i.e., Th first generates a joint action On := (a) aaa
(m)
(im)), and then (l())) modifies dg to
(m)
by Un
another 1
(mm) random. We also denote ((m) -00h J/=1
(m) 1 ((m)
:= ( (im)
TT Th]h-1-
Correlated Equilibrium (CE), A joint policy π is called a CE if for any agent m and any stochastic modification ((m), it holds that 1/ (xr) m/(m) (d(m) x).
Intuitively, at CE, no agent can improve its value function by modifying its own action induced by the joint CE policy. Compare to NE policies, CE policies do not require joint independence among all the agents. fact, it has been shown that any NE policy is guaranteed to be a CE policy 61,37|48 and hence CE is a weaker equilibrium notion than NE, Moreover, CE can be reformulated as linear programming and therefore is computationally tractable.
3 Correlated Equilibrium of Constrained Markov Game
In this section, we introduce constrained Markov game a generalization of the standard Markov game with constraints agents' behavior. We then propose and study new notion of correlated equilibrium for constrained Markov games.
3.1 Constrained Markov Game
In many real-life Markov games, the behavior of the agents is usually restricted by certain constraints, e.g., constraints on total time delay, average power, etc. This motivates us consider a constrained version of Markov game [2]. Constrained Markov game follows the same state/action transition as that of the standard Markov game introduced in Section 2 The key difference is that, after the state transition at each time step / in a constrained Markov game, every agent m receives dm +1
number of rewards {r (m)) (St: an) an)) 5== Here, the accumulation of the reward ((m)) corresponds the
target that agent m aims maximize. The other rewards (r(m) ydm, are introduced to encode the behavioral constraints of agent In this paper, consider the type of covering constraints on the
accumulation of the rewards (m) (sh, / over the episode, which impose constraints on the long-term behavior of agents. More specifically, define the following value functions associated with the reward functions of agent m:
(m) (sh, an)(s1 ~p]. j= j......,d
(m) jA
(T)
E
Every agent m aims optimize its own policy (1n) via the following constrained Markov game.
(Constrained Markov Game):
max V- (m)))()) (I)) s.t. v((m (I)) 2 dm)) j 1.....,d, dm-
(mm)
where (c/m))( y I denote the thresholds of the constraints (mm (T) 2 (m) Intuitively, the constraints on the value functions implicitly impose constraints on the joint policy म, and all the agents aim to maximize their target value functions and achieve certain equilibrium under their local constraints.
3.2
Nash Equilibrium and Correlated Equilibrium
For constrained Markov games, we can define the following notion of Nash equilibrium (NE) that similar to the standard Nash equilibrium but takes into account the constraints 27 45
51 55 60)

---

Definition 3.1 (NE of constrained Markov game). For a constrained Markov game, joint policy π called an NE the following conditions are met: (i) for any time step h. the joint policy Th is product policy that can be factorized into a product of independent policies; (ii) a is feasible, i.e, it satisfies the constraints of all the agents; (ūi) For any agent m with any associated policy 7/m) such
that ((m) x 700m)) is feasible, it holds that (/ (TT) 2 v/ (7(m) x (1mm)).
Compared with the NE of Markov game defined in Section 2 NE of constrained Markov game further requires the joint policies π and ((m) x (1mm)) to be feasible. It has been shown that such an NE exists for general constrained Markov games 4. Moreover, since constrained Markov game generalizes the Markov game, computing NE of constrained Markov game is also PPADD-complete problem. Therefore, we are motivated to propose the following surrogate notion of correlated equilibrium (CE).
Definition 3.2 (CE of constrained Markov game). For a constrained Markov game, joint policy π called a CE if the following conditions hold: (i) x is feusible, i.e., it satisfies the constraints of all the agents; (ii) for any agent and any stochastic modification (5tm) such that df di/m) o is feasible,
it holds that Vo (T) 2 v/(m)) (cf(m) o T)).
In particular, if π is product policy, it can be seen that (f()) I is also product policy and then CE would reduce to NE. Therefore, the above definition of CE generalizes NE of constrained Markov games. We note that (26) also defined CE for constrained Markov games, but in very different aspect. Specifically, they only defined CE based on the unconstrained Markov game associated with Lagrange function (i.e., with surrogate reward defined in eq. (8), which does not necessarily require and di(m)) π to be feasible but our Definition 3.2 requires. Therefore, the existing CE proposed in [26] essentially follows the CE of unconstrained Markov games, whose definition is stated after our Definition 1. Moreover, [26] defined CE based on the state-action value function and consider stationary Markov policies in the discounted infinite horizon setting, whereas we define CE based on the state value function and consider non-Markov policies in the finite horizon setting.
It may seem that the CE in Definition 3.2 is straightforward generalization of that of the standard Markov game. However, it turns out to possess a fundamentally different structure of the modification operator at the equilibrium point due to the presence of constraints, as elaborated in the following fundamental result. Throughout the paper, we call a stochastic modification operator deterministic if its pdf is supported on a single action.
Theorem 1 (Modification of CE).
1. For unconstrained Markov games. If policy x satisfies that V/(") (TT) 2 f/(m) (p(m) o TT) for any agent m and any deterministic modification (5(m), then nt must be a CE.
2. For constrained Markov games. Even if a feasible policy satisfies that v.(m) (T) (m) (d((m) T) for any agent m and any feasible deterministic modification ((m),, may not be a CE.
Theorem I shows that the structure of modification at the CE of Markov games is different from that of constrained Markov games. To elaborate item 1, recall that a CE policy π of a Markov game is defined to satisfy ((m) 2 ((()()( o TT for any stochastic modification ((()) (see Section 2. Since stochastic modifications include deterministic modifications, item I proves that CE of Markov games can always be achieved by deterministic modification. Therefore, it suffices to define CE of Markov games using deterministic modifications, as adopted by many existing works (3] As comparison, item 2 shows that for constrained Markov games, the CE defined using deterministic modification is in general weaker than the CE defined using stochastic modification (see Definition 3.2). which is the focus of this paper. More importantly, as we show later in Theorem 2 defining CE of constrained Markov games using stochastic modification allows us to establish a strong duality result, which is the key to develop convergent primal-dual algorithms.
The proof of Theorem D is non-trivial and we provide a proof sketch here. To prove item 1, our strategy is to construct a simple deterministic modification of (((m) (see Appendix for the construction) for any optimal stochastic modification (im) and show that they achieve the same optimal value function, i.c., vi("")( (d(m)) o π) = v/(">) (σfm) TT) To show this, we transform the value functions from the policy space to the space of probability measure P- of episodes induced by the associated policy, i.e., (((m) (=) (x(m) (px) (see eq. (22). so that the transformed value function (((m) linear
in Pa- Then we consider the extrapolated probability measure p> == Xpptmion + (1 >) >)P Pitiioo and
show that there exists x < 0 such that PA is measure induced by a modified policy ((m)) for
5

---

certain proper stochastic modification (m)) This together with the linearity of (²(m) proves item 1. To prove item 2. we construct a counterexample of constrained Markov game such that its CE under stochastic modification is shown to be strictly stronger than its CE under deterministic modification.
4 A Primal-Dual Algorithm for Constrained Markov Game
In this section, we develop a primal-dual algorithm for finding correlated equilibrium (CE) of general constrained Markov games. Throughout this section, simplify the notation, we denote ((m) (अ) = [V] (m),....
v/lm) (iT) as the collection of all the value functions in the constraints, dm (ml) as the collection of all the thresholds of the constraints.
and denote cm = [c] cdm
4.1 Strong Duality for Correlated Equilibrium
Consider any feasible policy æ of a constrained Markov game, i.e., v(()(()) 2 clm) holds entrywise. The CE of constrained Markov game is related to the following constrained optimization problem.
For 1,...,M, M,
max stochastic (b(m)
Vo (m))
(g( TT s.t. (mm) (a()m) π) 2 (m),
(4)
where '2' applies entrywise and the maximization is taken over all stochastic modifications. To further explain, define the following duality gap for every agent m.
((() (T)
max
Vo (m)) (s((m) πT) - (m) (T),
(5)
Feasible d(mm)
where modification (5(m) is called feasible if gi(m) nT satisfies the constraint in eq. 4 Clearly, we have (mm) (Tr) 2 0 as the identity modification (i.e., gj(m) π T) is feasible. Moreover, it can be seen that is a CE of constrained Markov game if and only if max D(m) (T) = 0.
Since the problem in eq. (4) takes a constrained form, is natural to consider its equivalent Lagrangian formulation, which is written below.
max min gi(m)
L (mm) (1(mm) o n, (mm) (0" x) + (mm) (())((())))
(V(m)((f(m)) o OT) - -m))),)) (6)
A(re ERam dm
where ((m) R is the dual variable. In order to develop convergent primal-dual algorithms for solving the constrained problem, fundamental problem that needs to be addressed is the duality gap of the above Lagrangian function. In conventional constrained convex optimization [9]. strong duality can be achieved under a Slater's condition, which requires the existence a strictly feasible point under the constraints. Recently, this condition has also been introduced to establish strong duality for single-agent constrained reinforeement learning [18] 19| 42). For constrained Markov game, we introduce the following Slater-type condition study its duality gap.
Assumption 1 (Slater's condition). For any agent and any joint policy n, there exists a stochastic modification (f(m) such that (m)(())))) T) c(m) 2 e(m) for some strictly positive g(m).
The above Slater's condition assumes that agents can always find strictly feasible stochastic modification, regardless of the joint policy. Such a condition is closely related to the existing Slater- type condition for constrained Markov games 3 4 (5). which replaces the modification operator ((m) by an independent local policy 7(m) and is used to study NE. With the above Slater's condition, we are able to establish the following strong duality result for constrained Markov game.
Theorem 2 (Strong duality). Let Assumption hold. Then, strong duality holds for constrained Markov games, i.e., for any joint policy x and any agent m,
max min (im) (g)()) nT ((m)) = ((m) AR
min max I, (m) (d(mm) o n. ((m)). Xim2 Rm (6m)
To the best of our knowledge, such a strong duality result has not been established before for CE of constrained Markov games, and later we show that this is essential for developing primal-dual algorithm for finding CE of constrained Markov games. In particular, compared to the strong duality results of single-agent constrained RL 42 and those for finding Nash equilibrium (NE) of

---

constrained Markov game [30], the proof of Theorem I for finding CE of constrained Markov game substantially different and more challenging, as we elaborate below.
Technical novelty. Note that the constrained settings considered in the aforementioned existing works (2 32 lead to Lagrangian functions defined over the entire unconstrained policy space, which is clearly convex and helps establish the strong duality result. As a comparison, in order to find CE, our Lagrangian function L (mm) a nonlinear function in ((m) and is defined over the set of modified policies ()l(m) o т <5(m) is stochastic modification) for a fixed и. Such a set is subset of the entire policy space and is not easy to analyze directly. To overcome this challenge,
first rewrite L (m) (á5()) nI A (m)) as (mm) (Palm)on: (()) (see eq. (23)). which is function of Patmoos the probability measure of the episode ($1.H. 01:H) induced by the modified policy o(T²) o Since we showed that (mm) is linear in both of its arguments, strong duality would follow if we can prove that the domain of the first argument convex and compact set, and the proof of this result requires substantial effort. More specifically, to prove convexity we need to show that the convex combination Apotomoo + (1 () for any
== [Poimlor : (5(m) is stochastic modification) is a
À E [o, 1] and any modifications ((mm), ((()) is a valid probability measure of the episode induced by certain modified policy, and to prove compactness we need to show the closedness of any converging sequence {P ( jA-- To prove these claims, we need to study the fundamental properties of the
measure Pr, and the modified measure Potm)or in Lemma A.1 and Lemma
B.1
4.2 A Primal-Dual Algorithm for Finding Correlated Equilibrium
Based the strong duality result in Theorem 2 finding CE of constrained Markov game is equivalent to solving the minimax optimization problem in eq. 7 for all agents m, which can be effectively solved by a primal-dual algorithm that alternatively updates the primal variable ((m) and the dual variable ((m), While ((m) can be updated using the standard projected dual descent update, the update of d(m) requires further exploration as we elaborate below.
Specifically, with fixed X(m), the primal update needs to solve the optimization problem [m) maxg(m) ((m) (6((m) æ,, A(m)). Denote rh2 (s, a) := [ri, as. d (s, as)" as the col-
lection of the rewards associated with the constraints, and define the following weighted surrogate
reward ( and its associated value function v((T).
R(m) (sh: ax) == =To,A (sh, an) + (mx) rh ((m)
(sk, (sk) an),
(8)
H
v(() (T) = E
R
(m)) A (sh, (sh,
r].
h=1
Then, the optimization problem of the primal update can be rewritten follows.
max L (m²) (m) o π., X(m) = max d(m)
{ (m) (d((m) π (m)T (())
(10)
g(m)
Interestingly, the problem max V (m) (m)m) TT) can be understood as finding CE of uncon-
strained Markov game with associated reward R/ and value function (((m) Therefore, to perform the primal update, we can apply any black-box algorithm for finding CE of unconstrained Markov games to update the policy. particular, some existing popular algorithms include the V-learning algorithm [31 [6) and the Nash Value Iteration algorithm [37], both of which can output policy that achieves duuality gap (defined in eq. (TT) with provable finite-time time complexities.
We summarize this primal-dual algorithm in Algorithm I which alternatively updates the policy me via finding approximated CE of an unconstrained Markov game (with fixed X (m)),, and updates
X (m) via projected dual descent (with fixed T.). In particular, the projection set (mm) C IRd must
contain the optimal dual variable and also be bounded to ensure a bounded surrogate reward (m)
We give specific choice of A (m) in the next convergence analysis Section 5
use occupation measure induced by policy instead of the joint probability measure Pa. as they consider stationary Markov policies that select action at based on the current state st.
30 42
7

---

Algorithm Primal-Dual Algorithm for Finding CE of Constrained Markov Game C R dm for all m I,..,,... M.
Input: 6 > 0;AA(m) (m)
Initialize: Xmm) = 0 for all m 1.....M.. M.
for iterations t = 0, 1, T do
Let X (m)) 6- 2 (m)) Solve unconstrained Markov game with rewards R( (defined in eq.
and obtain an approximate CE policy mi that satisfies
max (m) (g(m) mT) (/ (T))
Vm 1,..,,M. M.
(11)
Update x(m) via the following projected dual descent step
A+1
(m)
pmoj
(2(mL) (7(((m) -m)))) Vm 1,.., M.
(12)
end
Output: Ty where i sampled from {0, 1, I,....,TTT uniformly at random.
Comparison to the existing art. Some existing works have developed other primal-dut algorithms with different primal policy improvement updates for constrained Markov games. For example, value iteration (Algorithm 11.1 [62]), simultaneous perturbation stochastic approximation (Algorithm 11.2 of (62) ) and policy gradient (30) are used as the primal update to find NE of constrained Markov games, and Q-learning [26) is used as the primal update to find CE of the Lagrangian function associated with the constrained Markov game. However, none of these works have established non- asymptotic convergence rate and sample complexity for the proposed algorithms. As comparison, our Algorithm can any black-box primal update that compute approximate CE of unconstrained Markov games, and enjoys a provable non-asymptotic convergence rate and low sample complexity as we show in the next section.
5 Convergence Analysis and Sample Complexity
In this section, we analyze the non con-asymptotic convergence rate of the primal-dual Algorithm Then, adopt the V-lcarning algorithm [31] the primal update of Algorithm!] []] and derive the overall sample complexity required by Algorithm to achieve an approximate CE with duality gap.
We adopt the following assumption of bounded reward that is commonly adopted in the analysis of constrained RL
[T8 42), Markov game [31 37|46] and constrained Markov game (26).
Assumption 2 (Bounded reward). For all agents m 1.... M, there exists constant r j.max (m)
(m)
such that 0 < j.K < m for all < < H and 0 j < dm-
we choose the following projection set A (m) for Algorithm 1 In particular, we prove in Lemma E.T that such a set contains the optimal dual variable.
Under Assumptions and
(m))
0,
2Hr (m²)
si (m))
0,max
X
0,
2Hr
O,max
(m))
(m)
x
0,
2Hr
0.max
(m)
C
Rm
(13)
Sd...
Theorem 3 (Convergence rate). Let Assumptions 7 and hold. Run Algoritim ffo T iterations with stepsize 1 = J and projection set A (m)) defined in eq. 13). Then, the output policy achieves the following duality gap (defined in eq. 55))
2(H (HRR )2
B(D(m) [T)] <
+e, Vm =
(14)
VT
where R((mn) = V dmn (m) )2, Moreover, define the constraint violation of the output policy mi as W(m) (TT) = E)
dm (m)) ) (m) (m) (((m) (mz)) where (a) == max(0,a). We obtain that
2H
(m)
[5] (m) ((()))- -2 2H (HRRM ((
E ((((mm)TTT)
mmax
Vm L...,M. (15)
T, VT
(m)
H
(mn) 0,

---

The above theorem shows that both the duality gap and the constraint violation associated with the output policy converge at the rate Of O'77 + E), where e the target duality gap of the unconstrained
Markov game in the primal update. In particular, a larger slackness {c/mm) J.m implies a faster convergence of the constraint violation. These convergence rates are comparable to those of primal- dual algorithms for single-agent constrained RL. [18] 39], and the analysis is a generalization of the single-agent case. Specifically, the updated policy ne the primal-dual algorithm for single-agent constrained RL is an approximate maximizer of the value function under the constraints, whereas the Te our case corresponds to an approximate CE at which all agents can benefit little (up to e) by modifying their own actions alone. Particularly for each agent, the duality gap convergence criterion eq. (TT) can be understood as a convergence criterion of single-agent constrained RI,, and there the proof logic partially follows the analysis of single-agent case [19].
As our Algorithm M can adopt any existing algorithm for unconstrained Markov games in the primal update, we consider adopting the V-learning algorithm developed in (3I.. This is a decentralized algorithm that incrementally updates the state value functions, which are further used to update the agents' policies via adversarial bandit algorithms. In particular, thanks to the use of state value function, it requires much less memory than other algorithms based on state-action value functions (26). In Theorem 7 of (31). it is proved that the V-learning algorithm achieves approximate CE with duality gap for any unconstrained Markov game with the state-of-the-art sample complexity SAH where O hides the logarithm factors and 5 = (S], A = max [A(m)) correspond to the cardinality of the state space and action space, respectively. We then obtain the following sample complexity result.
Corollary 5.1 (Sample complexity). Let Theorem hold and assume Fo 2 H. Ap- ply the V-learning algorithm
(m)
(37) to the primal update of Algorithm 7 and choose T
max, 4e (H Blnnk )² (1
)-2 + H HRm)) ? Then, the output policy Ty achieves 1==16 (5)
dm
m))
max (B(D(M) (Tp)), B[W (T=)l) 2e with the sample complexity Ö(H'SA²E-
To the best of our knowledge, this is the first finite-time sample complexity result establsihed for constrained Markov games. Next, we compare our sample complexity with that of two popular RL algorithms. The first one is the V-learning algorithm [3T] developed for finding CE of unconstrained
Markov games, and it achieves the sfate-of-the-at sample complexity Ō SA2 The infor- mation theoretical lower bound is 22H 2) [31]. As a comparison, the sample complexity of our primal-dual V-learning algorithm is higher since we require additional projected dual descent steps (12) to account for the constraints. The other one is the basic primal-dual algorithm for solving single-agent constrained RL problems, which uses natural policy gradient in the primal update and achieves the state-of-the-art sample complexity O(e-1) [7] Such a complexity has the same
dependence on e as the sample complexity of our algorithm.
6 Conclusion
In this work, we propose a surrogate notion of correlated equilibrium (CE) for constrained Markov games and show that it possesses a fundamentally different cnnfferentmmdiineee modification structure from that of CE of Markov game. Moreover, we prove that the corresponding Lagrangian function has zero duality gap. Based on this result, we develop the first primal-dual algorithm that provably converges to CE of constrained Markov games with the convergence rate O ). Moreover, when adopting the
VT
V-learning algorithm as the subroutine in the primal update, our algorithm achieves an approximate CE with duality gap with the sample complexity D(H"SAA 4). Limitations: In this work, we only develop the basic primal-dual algorithm for constrained Markov games. An interesting future direction is to develop other advanced algorithms such as Nesterov's momentum-accellenn accelerated primal-due algorithms. Negative social impacts: This is fundamental theoretical study and does not have any potential negative social impact.
Acknowledgment
The work of 7. Chen, S. Ma and Y. Zhou was supported part by U.S. National Science Foundation under the Grants CCF-2106216 and 2M3-2134223,

---

References
[1] Achiam, D. Held, A. Tamar, and P. Abbeel. Constrained policy optimization. In Proc. International conference machine learning (ICML), pages 22-31, 2017.
[2] E. Altman. Constrained Markov decision processes: stochastic modeling. Routledge, 1999.
[3] E. Altman, K. Avrachenkov, N. Bonncau, M. Debbah, R. El-Azouzi, and D. S. Menasche. Constrained cost-coupled stochastic games with independent state processes. Operations Research Letters, 36(2):660-164, 2008.
[4] E. Altman and A. Shwartz. Constrained markov games: Nash equilibria. In Advances in dynamic games and applications, pages 213-221, 2000.
[5] E. Altman and E. Solan. Constrained games: The impact of the attitude to adversary's ' constraints. IEEE Transactions on Automatic Control, 54(10):445-22400 2009.
[6] J. Alvarez-Ment and O. Hernández-Lerma, Existence of nash equilibria for constrained stochastic games. Mathematical Methods of Operations Research, 63(2):261-285, 2006.
[7] Q Bai, A. S. Bedi, and V. Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm. arXiv preprint arXiv:2206.000 05850, 2022.
[8] Y. Bai, C. Jin, H. Wang, and C. Xiong. Sample-efficient learning of stackelberg equilibria in general-sum games. Proc. Advances in Neural Information Processing Systems (Neurips), 34, 2021.
[9] D. P. Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
[10] A. Celli, A. Marchesi, G. Farina, and N. Gatti. No-regret learning dynamics for extensive-form correlated equilibrium. Proc. Advances in Neural Information Processing Systems (Neurips), 2737222,,7,, 2020.
[11] Z. Chen, S. Ma, and Y. Zhou. Sample efficient stochastic policy extragradient algorithm for zero-sum markov game. In Proc. International Conference on Learning Representations (ICLR), 2022.
[12] Y. Chow, O. Nachum, E. Duenez-Guzman, and M. Ghavamzadeh. A lyapunov-based approach to safe reinforcement learning. In Proc. Advances in neural information processing systems (Neurips), volume 31, 2018.
[13] Y. Chow, O. Nachum, A. Faust, E. Duenez- and M. Ghavamzadeh. Lyapunov- bassdd safe policy optimization for continuous control. ArXiv:1901,1003: 2019.
[14] K. Cui and H. Koeppl. Learning graphon mean field games and approximate nash equilibria. ArXiv:2112.0 12.01280 2021.
[15] G. Dalal, K. Dvijotham, M. Vecerik, T. Hester, C. Paduraru, and Y. Tassa. Safe exploration in continuous action spaces. ArXiv:1801.08757 2018.
[16] C. Daskalakis, D. J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning. In Proc. Advances in Neural Information Processing Systems (Neurips), volume 33, 2020.
[17] X. Deng, Y. Li, D. H. Mguni, J. Wang. and Y. Yang. On the complexity of computing markov perfect equilibrium in general-sume sum stochastic games. ArXiv:2109.01995, 2021.
[18] D. Ding, X. Wei, Z. Yang, Z. Wang, and M. Jovanovic. Provably efficient safe exploration via prim policy optimization. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3304-3312, 2021.
[19] D. Ding, K. Zhang, T. Basar, and M. R. Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. In Proc. International Conference on Neural Information Processing Systems (Neurips), volume 2020. 2020.
[20] F. Dufour and T. Rantto. Stationary markov nash equilibria for nonzero-sum constrained arat markov games. 200i::2299.130000 2021.
[21] Fan, Z. Wang, Y. Xie, and Yang. A theoretical analysis of deep q-learning. Proc. Learning for Dynamics and Control (L4DC), pages 486-489, 2020.
10

---

[22] J. Filar and K. Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
[23] A. Gilpin and T.. Sandholm. Finding equilibria in large sequential games of imperfect infor- mation. In Proceedings of the 7th ACM conference Electronic commerce, pages 160-169, 2006.
[24] E. Remmez-Ramirez, K. Najim, and A. Poznyak. Saddle-point calculation for constrained finite markov chains. Journal of Economic Dynamics and Control,
2003.
[25] X. Guo, A. Hu, R. Xu, and Zhang. Learning mean-field games. Proc. Advances in Neural Information Processing Systems (Neurips), 32:4966 097496666777,,, 2019.
[26] V. Hakami and M. Dehghan. Learning stationary correlated equilibria in constrained general- sum stochastic games. IEEE Transactions on Cybernetics, 4607):1440-164, 2015.
[27] M. K. Hanawal, M. Model-Rahman and M. Krunz. Joint adaptation frequency hopping and transmission rate for anti-jamming wireless systems. IEEE Transactions on Mobile Computing, 15(9):2247-2259 2015.
[28] A. Jaškiewiez and A. S. Nowak. Constrained discounted stochastic games. ArXiv:2112.07960
2021.
[29] A. Jaškiewiez and A. Nowak. On approximate and weak correlated equilibria in constrained discounted stochastic games. ArXiv:2201 200::2000000 2022.
[30] X. Jiang, S. Chen, J. Yang, H. Hu, and Z. Zhang. Finding the equilibrium for continuous constrained markov games under the average criteria. IEEE Transactions on Automatic Control, 65(12):5399 54066 2020.
[31] C. Jin, Q. Liu, Y. Wang, and T. Yu. V-leaming-a simple, efficient, decentralized algorithm for multiagent rl. ArXiv:21 10. 14555, 2021.
[32] Y. Jin, V. Muthukumar, and A. Sidford. The complexity of infinite-horizon general-sum stochastic games. ArXiv:2204.04 0416,, 2022.
[33] D. Koller and Megiddo. The complexity of two-person zero-sum games in extensive form. Games and economic behavior, (4):528-555) 1992.
[34] V. Kononen and E. Oja. Asymmetric multiagent reinforcement learning in pricing applications. In Proc. IEEE International Joint Conference on Neural Networks (IEEE Cat. No. 04CH37541), volume 2, pages 1097-1102, 2004.
[35] S. Leonardos, W. Overman, I. Panageas, and G. Piliouras. Global convergence of multi-agent policy gradient in markov potential games. 1xXiv:2/06.09663 2021.
[36] T. Li, Z. Guan, S. Zou, T. Xu, Y. Liang, and G. Lan. Faster algorithm and sharper analysis for constrained markov decision process. ArXiv:21100 10. 10..5511, 2021.
[37] Q. Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis model- based reinforcement learning with self-play. In Proc. International Conference on Machine Learning (ICML), pages 7001-7010, 2021.
[38] Y. Liu, J. Ding, and X. Liu. Ipo: Interior-point policy optimization under constraints. In Proc. the AAAI Conference on Artificial Intelligence (AAAI), volume 34, pages 4940-4947, 2020.
[39] W. Mao and T. Başar, Provably efficient reinforcement learning in decentralized general-sum markov games. Dynamic Games and Applications, pages 1-22, 2022.
[40] H. Moulin and J.-P. Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3):201-
221, 1978.
[41] M. J. Osborne and A. Rubinstein. course in game theory. MIT press, 1994.
[42] S. Paternain, L. F. Chamon, M. Calvo-Fullana, and A. Ribeiro. Constrained reinforcement learning has zero duality gap. In Proc. International Conference on Neural Information Processing Systems (Neurips), pages 7555-7565, 2019.
[43] I.. S. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1100, 1953.

---

[44] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai. A. Bolton, et al. Mastering the game of go without human knowledge. nature, (50(7676))354-355) 2017.
[45] V. V. Singh and N. Hemachandra. A mathematical programming based characterization of nash equilibria of some constrained stochastic games. ArXiv: ArXXiv/200..1 1672, 2012.
[46] Z. Song, S. Mei, and Y. Bai. When can learn general-sum markov games with a large number of players sample-efficietly ArXiv:2110.0418. 2021.
[47] A. Stooke, J. Achiam, and Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In Proc. International Conference on Machine Learning (ICML), pages 1133-9143, 2020.
[48] H. Tembine, E. Altman, R. ElAzouzi, and Y. Hayel. Stochastic population games with individual independent states and coupled constraints. In Proc. the 3rd International Conference on Performance Evaluation Methodologies and Tools, pages 1-10, 2008.
[49] C. Tessler, D. J. Mankowitz, and S. Mannor. Reward constrained policy optimization. In Proc. International Conference on Learning Representations (ICML), 2018.
[50] D. Vasal. Stochastic stackelberg games. ArXiv:2005.00 01997, 2020.
[51] Q. Wei. Constrained expected average stochastic games for continuous time jump processes. Applied Mathematics & Optimization, 83(3):1277-1309, 2021.
[52] Q. Wei and X. Chen. Constrained stochastic games with the average payoff criteria. Operations Research Letters, 43(1):83-888 2015.
[53] Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In Proc. Conference on learning theory (COL.T), pages 3674-3683 2020.
[54] T. Xu, Y. Liang, and G. Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In Proc. International Conference on Machine Learning (ICML), pages 11480-11491, 2021.
[55] V. G. Yaji and S. Bhatnagar. Necessary and sufficient conditions for optimality in constrained general sum stochastic games. Systems & Control Letters, 85:8-15, 2015.
(56) T.-Y. Yang, J. Rosca, K. Narasimhan, and P. J. Ramadge. Projection-based constrained policy optimization. In Proc. International Conference on Learning Representations (ICLR), 2019.
[57] M. Yu, Z. Yang, M. Kolar, and Z. Wang. Convergent policy optimization for safe reinforcement learning. Proc. Advances in Neural Information Processing Systems (Neurips), 32, 2019.
[58] R. Zhang, 7. Ren, and N. Li. Gradient play in multi-agent markov stochastic games: Stationary points and convergence. ArXiv:2 000.00099....... 2021.
[59] W. Zhang. Continuous-tinn constrained stochastic games under the discounted cost criteria. Applied Mathematics & Optimization, 7(2)):75-296, 2018.
[60] W. Zhang, B. Wang, and D. Chen. Continuous-ting constrained stochastic games with average criteria. Operations Research Letters, 46(1):109-115, 2018
[61] X. Zhang, K. Zhang, E. Miehling, and T. Basar. Non-cooperative inverse reinforcement learning.
In Proc. Advances in Neural Information Processing Systems (Neurips), volume 32, pages 9487-9497, 2019.
[62] Y. Zhang and M. Guizani. Game theory for wireless communications and networking. CRC press, 2011.
[63] Y. Zhao, Y. Tian, J. D. Lee, and S. S. Du. Provably efficient policy gradient methods for two-player zero-sum markov games. 10Xix:2102.08003 2021.
[64] Y. 7hu and D. Zhao. Online minimax q network learning for two-player zero-sum markov games. IEEE Transactions on Neural Nenworks and Learning Systems, 2020.
[65] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20, 2007.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the "Conclusion" section.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the "Conclusion" section.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "yfikYhc5Sj", "reviewer": "Reviewer_jkm3", "summary": "This paper proposes a primal-dual algorithm for solving for correlated equilibria (CE) in Constrained markov games. This can be seen either as (a) an extension of (nash) constrained markov games (or MDPs) to CE, or (b) adding constraints to an unconstrained CE for Markov games. The primary technical contribution is in Theorem 2, which shows strong duality and points towards a primal dual algorithm.The authors also study convergence rates and sample complexity.\n", "questions": "1. My understanding is that the existence of a constrained CE may not exist. Is it true that a constrained Nash exists, a constrained CE would as well. Furthermore, are there cases where a constrained CE exists, but not for constrained Nash?\n\n2. The authors introduce CE as a surrogate for Nash. However, amongst many game theorists, CE is in and of itself an equilibrium concept that is of interest, and involves a trusted mediator giving recommendations to players (or cryptographic protocols). Most frequently, one can maximize social welfare while maintaining incentive compatibility. I would think that one can easily force this objective in, by adding lower bounds on social welfare as a constraint for each player while performing binary search on social welfare. Is there a cleaner way of selecting between various constrained CE?\n\n3. Again, related to the classical definition of a CE (i.e., with a mediator). The setting here is one with finite horizon. Given that the authors allow for nonstationary strategies, the game can technically be unrolled (albeit incurring exponential blowup) into a tree. From this perspective, the concept of a CE is actually very similar to that of an extensive-form correlated equilibrium (for extensive form games), with the major difference being that players (or the mediator) does not observe past recommendations (even if they do actions). Can the authors comment about whether their method would apply to this variant of CE?\n", "limitations": "-", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is fairly clearly written and easy to follow. There are a fair number of minor spelling or grammatical errors, but these do not impede the reader.\n\nThe target audience is relatively niche and probably only of interest to those interested in constrained markov games. The technical contributions (a primal dual algorithm) are somewhat “standard” but non-trivial and interesting in their own right. Both Theorems 1.1 and 1.2 are unsurprising for those familiar with general-sum markov (or extensive-form) games, but is of interest to those who come from a single-player MDP background. The form of the primal update (11) is somewhat disappointing given that we essentially solve for a new unconstrained CE in each iteration, but perhaps that is unavoidable.\n\nNote: I am unable to comment much on the technical soundness of the authors’ claims, especially since this is a paper with lengthy proofs.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lLUQNH04B7A", "reviewer": "Reviewer_ddwR", "summary": "This paper examines Constrained Markov games.\nIt proposes: \n(1) a notion of correlated equilibrium for Markov games\ndemonstrating the shortcoming of a deterministic modification function\n\n(2) under the assumption of the satisfaction of Slater condition, a zero-duality gap is proven for CE in Markov games in finite-horizon with a non-deterministic modification function\n\n(3) the problem of finding a CE policy for each agent is written as a mathematical program with appropriate inequality constraints and the modification function as variables. After the Lagrangian function has been formed, the Lagrangian is written as a function of probability measures of the episodes induced by applying the modification function on the policy. It then follows that the Lagrangian is convex w.r.t to these variables. \n\n(4) from this point forward, a a primal-dual optimization algorithm can be applied. a part of the \"primal\" loop can be interpreted as the problem of finding a CE in an unconstrained Markov game which allows   \n\n", "questions": "Can the authors argue in what settings the authors results carry over to Nash equilibria? I know this is  hard question, I guess it is interesting for future consideration.", "limitations": "This is theoretical work", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall the paper is well-written and I think it is above the acceptance bar.\n\nThe main strength are: \n- The result about non-asymptotic convergence (they provide rates which is really interesting).\n- The above allows the authors to talk about sample complexity.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OYWkwQY49X8", "reviewer": "Reviewer_ybg9", "summary": "This paper studies correlated equilibrium in Markov games with linear constraints. The authors start with a strong duality theorem for CE in constrained Markov games, which enables them to design a primal-dual algorithm that uses a unconstrained CE algorithm as a subroutine. The primal-dual algorithm is shown to have a $O(1/\\sqrt{T})$ convergence rate in $T$ iterations, and when V-learning is used as the solver, an $O(H^9SA^2\\epsilon^{-4})$ sample complexity bound.", "questions": "Is it possible to output an approximate CE that is strictly feasible? The answer seems to be true for constrained MDPs.", "limitations": "Limitations and potential societal impact have been adequately addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper establishes a reasonable formulation for correlated equilibrium in constrained Markov games, which captures this important concept and as far as I know is novel.\n- The proposed primal-dual algorithm is compatible with essentially any black-box CE solver.\n- The theoretical results seem sound and novel.\n\nWeaknesses:\n- The $O(1/\\epsilon^4)$ sample complexity bound seems a bit loose, given that works in constrained MDP provide $O(1/\\epsilon^2)$ rates. It might be due to V-learning being used as a black-box algorithm that is initialized tabula rasa each step. It seems to me that this can be improved by using a less black-box approach, perhaps by using model-based algorithms.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hi__gTunQeN", "reviewer": "Reviewer_zKK3", "summary": "This paper deals with correlated equilibria in constrained Markov games over a finite horizon. The authors provide a sound definition of correlated equilibria for these type of games  that differs from previous definitions and show how to compute them using a primal-dual algorithm, similar to existing algorithms, albeit in a different context.", "questions": "\nThe fact that the  stochastic and deterministic cases differ when constraints are added should not come as a surprise.\nThe same is true for Makov processes with one player: With no constraints, the optimal policy is deterministic while for Markov decision processes with linear constraints, the optimal policy are randomized. Actually, in this case, the number of randomizations is equal to the number of constraints. One wonders is a similar property holds here.\n\n\n\n", "limitations": "This work is mainly theoretical with no direct societal impact. However, as mentioned in the strength/weaknesses section, a motivation and a discussion on possible applications of this work is missing. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- One contribution of this paper is a proper definition of correlated equilibria in Markov games over a finite horizon. The new definition is both natural and general. \n\n- The idea of using measures as the state is nice and elegant: It transforms the problem into a linear one.\n\n- The analysis of the performance of the algorithm is state of the art, even if the dependence in $H^9$ looks rather extreme, so that the performance of the algorithm in practice will be limited.\n\n\n\n\nWeaknesses:\n\n- The difference with previous definitions of correlated equilibria is mentioned several times but the reader fails to see exactly what  this difference is. The authors could have given the former definition  formally so that the reader can grasp this difference precisely. Here this is kept informal.\n- This confusion lasts when the algorithm is presented as the first one to compute the correlated equilibria. If the definition is new and the notion of correlated equilibria is also different from previous attempts, then why is this algorithm qualified as the first one? It should be by essence. The same remark holds for Theorem 2 on strong duality. If the definition is new, surely strong duality has not been established before.\n\n- The restriction to finite horizon games is definitely a limitation. Why have the discounted and/or long run behavior not been investigated? The finite horizon case is easier technically than both of these cases, and also less useful in practice.\n\n- The motivation is lacking in the following sense: What kind of applications do the authors have in mind for constrained Markov games.\nThe brief mention of ressource constraints is not satisfying because these are usually hard constraints and not constraints that only hold in expectation as this is the case here. So far, this reviewer could not think of  any clear application to this framework.\n\n\n\n-Finally, a discussion on the limitations of the last result on the sampling complexity  could be added. The sample complexity is only given for the expected gap and the expected contraint violation instead of for the true values. Also the bound is $H^9 \\varepsilon^{-4} $ is not compared with similar cases. \n\n\n\n\n\n\n\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2xDjwG_6bd4", "reviewer": "Reviewer_z16W", "summary": "The paper proposes a notion of correlated equilibrium (CE) for constrained Markov games, and a primal-dual algorithm to approximate one CE in such setting. The authors show that the algorithm guarantees duality gap and constraint violation of order $O(T^{-1/2})$. Finally, they study the sample complexity of the algorithm with a particular choice of subroutine for the primal update. ", "questions": "[Q1] The motivating examples (e.g., lines 29-32) seem to be all related to settings with resource-consumption (i.e., packing) constraints. However, from eq. 3 and Assumption 2 (from which we have $r_{j,h}^{(m)}\\ge 0$), my understanding is that the model only describes covering constraints (the cumulative r_{j,h} has to be at least a certain value). Is there any technical issue preventing you from addressing both kind of constraints? I don’t think that’s necessarily a problem, but it should be clarified. \n\n[Q2] Regarding Assumption 1: assuming an exact knowledge of $\\xi$ seems a bit restrictive. What would happen if the algorithm had access only to a lower-bound on the feasibility parameter $\\xi$? Do you think the analysis would carry over? As a last comment regarding Assumption 1, I’m wondering what are its practical implications. In order to clarify this, it would be good to provide at least one practical example where such assumption is satisfied. \n\n[Q3] On theorem 3. The authors claim that cumulative constraint violation is sublinear in T. However, I’m wondering what happens if the feasibility parameters $\\xi$ of Slater’s condition are allowed to take arbitrarily small values. For example, what if $\\xi_j^(m)$ were all equal to 1/T? It seems to me that the bound on constraint violation would not be sublinear in T. Is this correct? If so, I think that assumptions on the values allowed for $\\xi$ should be better described.\n\n[Q4] Is there any known lower bound to the sample complexity of the problem of Corollary 5.1? It not clear how tight is that bound. ", "limitations": "limitations were discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem is interesting and the paper is clear and well written. The set of results provided in order to reach Theorem 3 is analogous to what is done in other works using primal-dual algorithms for online optimization with long-term constraints. However, I think the application of such techniques to the setting of constrained Markov games is novel and worth being studied. \n\nThere are a few points that should probably be clarified (see Questions). I’m willing to increase my score after reading the authors’ response (especially regarding Q3).\n\n(one small typo at line 768: “it yield”)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept