Efficiently Computing Nash Equilibria in Adversarial Team Markov Games
Authors: Fivos Kalogiannis
Ioannis Anagnostides
Ioannis Panageas
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Vaggos Chatziafratis
Stelios Andrew Stavroulakis
Venue: ICLR 2023 notable top 5% (2023)
Keywords: multiagent-reinforcement-learning.marl
rl
reinforcement-learning
learning-in-games
optimization
game-theory
policy-gradient

Abstract:     Computing Nash equilibrium policies is a central problem in multi-agent reinforcement learning that has received extensive attention both in theory and in practice. However, in light of computational intractability barriers in general-sum games, provable guarantees have been thus far either limited to fully competitive or cooperative scenarios or impose strong assumptions that are difficult to meet in most practical applications.
    
    In this work, we depart from those prior results by investigating infinite-horizon \emph{adversarial team Markov games}, a natural and well-motivated class of games in which a team of identically-interested players---in the absence of any explicit coordination or communication---is competing against an adversarial player. This setting allows for a unifying treatment of zero-sum Markov games and Markov potential games, and serves as a step to model more realistic strategic interactions that feature both competing and cooperative interests. Our main contribution is the first algorithm for computing stationary $\epsilon$-approximate Nash equilibria in adversarial team Markov games with computational complexity that is polynomial in all the natural parameters of the game, as well as $1/\epsilon$.
    
    The proposed algorithm is based on performing independent policy gradient steps for each player in the team, in tandem with best responses from the side of the adversary; in turn, the policy for the adversary is then obtained by solving a carefully constructed linear program. Our analysis leverages non-standard techniques to establish the KKT optimality conditions for a nonlinear program with nonconvex constraints, thereby leading to a natural interpretation of the induced Lagrange multipliers.

Published as a conference paper at ICLR 2023
EFFICIENTLY COMPUTING NASH EQUILIBRIA IN ADVERSARIAL TEAM MARKOV GAMES
Fivos Kalogiannis UC Irvine
loannis Anagnostides
loannis Panageas UC Irvine
Carnegie Mellon University
Emmanouil V. KaaaakisSS
Vaggos Chatziafratis UC Santa Cruz
Stelios Stavroulakis UC Irvine
Columbia University
ABSTRACT
Computing Nash equilibrium policies is a central problem in multi-agent rein- forcement learning that has received extensive attention both in theory and in practice. However, in light of computational intractability barriers in general-sum games, provable guarantees have been thus far either limited fully competitive or cooperative scenarios, or impose strong assumptions that are difficult to meet in most practical applications. In this work, we depart from those prior results by investigating infinite-horizon adversarial team Markov games, natural and well-motivated class of games in which team of identically- -nnterelly players- in the absence of any explicit coordination against an adversarial player. This setting allows for a unifying treatment zero-sum Markov games and Markov potential games, and serves as step to model more realistic strategic interactions that feature both competing and cooperative interests. Our main contribution is the first algorithm for computing stationary e-approximate Nash equilibria in adversarial team Markov games with computational complexity that is polynomial in all the natural parameters of the game, as well as 1/e. The proposed algorithm is based on performing independent policy gradient steps for each player the team, in tandem with best responses from the side of the adversary; in turn, the policy for the adversary is then obtained by solving a carefully constructed linear program. Our analysis leverages non-stande nta-standard techniques to establish the KKT optimality conditions for nonlinear program with nonconvex constraints, thereby leading to a natural interpretation of the induced Lagrange multipliers.
communication- is competing
INTRODUCTION
Multi-agent reinforcement learning (MARL) offers a principled framework for analyzing competi- tive interactions in dynamic and stateful environments in which agents' actions affect both the state of the world and the rewards of the other players. Strategic reasoning in such complex multi-agent settings has been guided by game-the principles, leading to many recent landmark results in benchmark domains in (Bowling et al., 2015; Silver et al., 2017: Vinyals et al., 2019; Moravčík et al., 2017; Brown & Sandholm, 2019; 2018; Brown et al., 2020; Perolat et al., 2022). Most of these remarkable advances rely on scalable and decentralized algorithms for computing Nash equilib- ria (Nash, 1951) standard game-theorene notion of rationality-in in two-player zero-sum games.
Nevertheless, while single-agent RL has enjoyed rapid theoretical progress over the last few years (e.g., see (Jin et al., 2018; Agarwal et al., 2020; Li et al., 2021; Luo al., 2019; Sidford et al., 2018), and references therein), a comprehensive understanding of the multi-agent landscape still remains elusive. Indeed, provable guarantees for efficiently computing Nash equilibria have been thus far limited to either fully competitive settings, such as two-player zero-sum games (Daskalakis et al., 2020; Wei et al., 2021; Sayin et al., 2021; Cen et al., 2021: Sayin et al., 2020: Condon, 1993), or environments in which agents are striving to coordinate towards a common global objective (Claus
"Correspondence ipanagea ca. ucc...i.... .edu.

---

Published as a conference paper at ICLR 2023
& Boutilier, 1998; Wang & Sandholm, 2002: Leonardos al., 2021; Ding et al., 2022; Zhang al,, 2021b; Chen et al., 2022; Maheshwari et al., 2022; Fox et al., 2022).
However, many real-world applications feature both shared and competing interests between the agents. Efficient algorithms for computing Nash equilibria in such settings are much more searce, and typically impose restrictive assumptions that are difficult to meet in most applications (Hu & Wellman, 2003; Bowling, 2000). In fact, even in stateless two-player (normal-form) games, computing approximate Nash equilibria is computationally intractable (Daskalakis et al., 2009; Rubinstein, 2017; Chen et al., 2009; Etessami & Yannakakis, 2010)~subject to well-believed complexity-theome assumptions. As result, is common investigate equilibrium concepts that are more permissive than Nash equilibria, such as coarse correlated equilibria (CCE) (Au- mann, 1974; Moulin & Vial, 1978). Unfortunately, recent work has established strong lower bounds for computing even approximate (stationary) CCEs in turn-based stochastic two-player games (Daskalakis al., 2022; Jin et al., 2022). Those negative results raise a central question:
Are there natural mulli-agent environments incorporating both competing and shared interests for which we can establish efficient algorithms for computing (stationary) Nash equilibria?
Our work makes concrete progress in this fundamental direction. Specifically, we establish the first efficient algorithm leading to Nash equilibria in adversarial team Markov games, well-motivated and natural multi-agent setting in which a team of agents with a common objective is facing a competing adversary.
1.1
OUR RESULTS
Before we state our main result, let us first briefly introduce the setting of adversarial team Markov games; more precise description deferred Section 2. 1. To address Question (*),, we study an infinite-horizon Markov (stochastic) game with finite state space S in which team of agents NA = [n] with a common objective function is competing against a single adversary with opposing interests. Every agent & [n]] has (finite) set of available actions As. while B represents the adversary's set of actions. We will also let 7 E [0, 1) be the discounting factor. Our goal will be to compute (approximate) Nash equilibrium; that is, strategy profile that player can improve via a unilateral deviation (see Definition 1). In this context, our main contribution the first polynomial time algorithm for computing Nash equilibria in adversarial team Markov games:
Theorem 1.1 (Informal). There is algorithm (IPGMAX) that, for any > O, computes approximate stationary Nash equilibrium in adversarial leam Markov games, and runs time
1 1 2
poly |S)
As
13]
A few remarks are in order. First, our guarantee significantly extends and unifies prior results that only applied to either two-player zero-sum Markov games or to Markov potential games; both of those settings can be cast as special cases of adversarial team Markov games (see Section 2.3). Further, the complexity of our algorithm, specified in Theorem 1.1, scales only with ΣKEN |Asl instead of IL lA bypassing what is often referred to as the curse of multi-agents (Jin et al., 2021). Indeed, viewing the team single "meta-player" would induce action space of size IlKE |A+), which is exponential in even if each agent in the team has only two actions. In fact, our algorithm operates without requiring any (explicit) form of coordination or communication be- tween the members of the team (beyond the structure of the game), a feature that has been motivated in practical applications (von Stengel & Koller, 1997). Namely, scenarios which communication or coordination between the members of the team is either overly expensive, or even infeasible; for an depth discussion regarding this point we refer (Schulman Vazirani, 2017).
1.2 OVERVIEW OF TECHNIQUES
To establish Theorem 1.1. we propose natural and decentraliezd algorithm we refer to as Inde- pendent Policy GradientMax (IPGMAX). IPGMAX works in turns. First, each player in the team performs one independent policy gradient step on their value function with an appropriately selected
2

---

Published as a conference paper at ICLR 2023
learning rate 0. In turn, the adversary best responds to the current policy of the team. This change is repeated for a sufficiently large number of iterations T. Finally, IPGMAX includes an auxiliary subroutine, namely AdwNashPolicy// (y) which computes the Nash policy of the adver- sary; this will be justified by Proposition 1.1 we describe below.
Our analysis builds on the techniques of Lin et al. (2020) developed for the saddle-point problem mingex maxyey (a; y) for characterizing GDMAX. Specifically, GDMAX consists of perform- ing gradient descent steps, specifically on the function d(x)) = maXyey (ax y). Lin et al. (2020) showed that GDMAX converges to point (œ, y (f)) such that de is an approximate first-order sta- tionary point of the Moreau envelope (see Definition 3.1) of ((x), while y (.) is best response to 2. Now if f(x. -) is strongly-concave one can show (by Danskin's 's theorem) that (á, y (ar) is an approximate first-order stationary point of f. However, our setting introduces further challenges since the value function Vo (Teem,, Tadv) is nonconvex-monconcan
For this reason, we take a more refined approach. We first show in Proposition 3.1 that IPGMAX is guaranteed to converge to policy profile (fam -) such that &ram is e-nearly stationary point of m. Vp teamm: adv). Then, the next key step and the crux of the analysis is to show that म Team can be extended to an -pprrxiiie Nash equilibrium policy:
Proposition 1.1 (Informal). ream is an c-nearly stationary point of max VT(Tiemm, Tadv ). there exists policy for the adversary aady that (Heam, A is an a(ppaaprrx Nash equilibrium.
In the special case of normal-form games, a similar extension theorem was recently obtained by Anagnostides et al. (2023). In particular, that result was derived by employing fairly standard linear programming techniques. contrast, our more general setting introduces several new chal- lenges, not least due to the
nonconcctty of the objective function.
Indeed, our analysis leverages more refined techniques stemming from nonlinear programming. More precisely, while we make use of standard policy gradient properties, similar to the single-agent MDP setting (Agarwal et al., 2021; Xiao, 2022), our analysis does not rely on the so-called gradient- dominance property (Bhandari & Russo, 2019), as that property does not hold in a team- caam-wise sense. Instead, inspired by an alternative proof of Shapley's 's theorem (Shapley, 1953) for two-person zero- sum Markov games (Filar & Vrieze, 2012, Chapter 3), we employ mathematical programming. One of the central challenges is that the induced nonlinear program has a set of nonconvex constraints. As such, even the existence of (nonnegative) Lagrange multipliers satisfying the KKT conditions is not guaranteed, thereby necessitating more refined analysis techniques.
To this end, we employ the Arrow-HHuriz--Un Uzawa constraint qualification (Theorem A.1) in order to establish that the local optima are contained in the set of KKT points (Corollary B.1). Then, we leverage the structure of adversarial team Markov games characterize the induced Lagrange multipliers, showing that a subset of these can be used to establish Proposition 1.1; incidentally, this also leads to an efficient algorithm for computing a (near-) )optimal policy of the adversary. Finally, we also remark that controlling the approximation eиror- an inherent barrier under policy gradient methods-in Proposition 1.1 turns out to be challenging. We bypass this issue by constructing "relaxed" programs that incorporate some imprecision in the constraints. A more detailed overview of our algorithm and the analysis is given in Section
PRELIMINARIES
In this section, we introduce the relevant background and our notation. Section 2.1 describes ad- versarial team Markov games. Section 2.2 then defines some key concepts from multi-agent MDPs, while Section 2.3 describes a generalization of adversarial team Markov games, beyond identically- interested team players, allowing for a richer structure in the utilities of the team namelyy adver- sarial Markov potential games.
Notation. We let [n] == [l...... n). We use superscripts to denote the (discrete) time index, and subscripts to index the players. We use boldface for vectors and matrices; scalars will be denoted by lightface variables. We denote by I| := ||. || the Euclidean norm. For simplicity in the exposition, may sometimes use the (-) notation to suppress dependencies that polynomial in the natural parameters of the game; precise statements are given in the Appendix. For the convenience of the reader, comprehensive overview of our notation is given in A.3.
3

---

Published as a conference paper at ICLR 2023
2.1 ADVERSARIAL TEAM MARKOV GAMES
An adversarial leam Markov game (or an adversarial team stochastic game) is the Markov game extension of static, normal-form adversarial team games (Von Stengel & Koller, 1997). The game is assumed to take place in an infinite-horizon discounted setting in which a team of identically- interested agents gain what the adversary loses. Formally, the game is represented by a tuple G = (S,N, A, r, p) whose components are defined as follows.
is a finite and nonempty set of states, with cardinality == [S];
N is the set of players, partitioned into set of n team agents_V, == [n] and single adversary
A is the action space each player the team k E [n]. so that A == Xxe(n) As, while is
the action space of the adversary. We also let A = [Ax and B -B]:"
r: S x A x B + (0, 1) is the (deterministic) instantaneous reward functionn representing the (normalized) payoff of the adversary, so that for any (s,a,b) a,,b))) E Ax
n
r(s, a. b) + Σ
rk(s, =0
and for any & E [n].
(s a, b) (s, a.
(2)
P P:Sx x B + A(S) is the transition functionn, so that P(s'|s, a, b) denotes the probability of transitioning to state s' E when the current state is S under the action profile (a. b) E A x B;
function,
Y [0, 1) is the discount factor; and E A(S) is the initial state distribution over the state space. We will assume that p is full- support, meaning that p(s) > for all E S.
In other words, an adversarial team Markov game is subclass of general-sum infinite-horizon multi-agent discounted MDPs under the restriction that all but a single (adversarial) player have identical interests (see (2)), and the game is globally zero-sum-in the sense of (1). As we point out in Section 2.3, (2) can be relaxed in order to capture (adversarial) Markov potential games (Definition 2.2), without qualitatively altering our results.
2.2 POLICIES, VALUE FUNCTION, AND NASH EQUILIBRIA
Policies. A stationary-the that is, time-invariant-pplice πe for an agent l is a function mapping given state distribution say that T& is deterministic if for every state there is some action that is selected with probability under policy π. For convenience, we will let 1leam S A(A) and 1a S A(B) denote the policy space for the team and the adversary respectively. We may also write II: S - ( ( denote the joint policy space of all agents.
available actions, T& S 9
( E A(Ax). We will
Direct Parametrization. Throughout this paper we will assume that players employ direct policy parametrization. That is, for each player & E [n]]. we let Xr == ((As)s and π Ty so that Tk,s,a T [a]s). Similarly, for the adversary, we let ) = ( and Tadv y that Ya.o Tade Tadv(als)) (als). (Extending our results to other policy parameterizations, such as soft-max (Agarwal et al., 2021), is left for future work.)
Value Function. The value function V. : 1 (II,...., nu. aadv) ) + defined as the expected cumulative discounted reward received by the adversary under the joint policy (Tieam, Taav)) II and the initial state & E S, where Tream = ( ,T)) In symbols,
V.( π team: advv)
E (Teeas
(r((s(0) (,0,,,0))s
(3)
'To ease notation, and without any essential loss of generality, we will assume throughout that the action space does not depend on the state. Asssming that the reward is positive without any loss of generality (see Claim D.6).
4

---

Published as a conference paper at ICLR 2023
where the expectation is taken the trajectory distribution induced by Team and aadv- When the initial state is drawn from a distribution p, the value function takes the form Vip (Tream: Tadv) =
Egup (TTTammm= Tadv)
Nash Equilibrium. Our main goal is to compute joint policy profile that is an (approximate) Nash equilibrium, a standard equilibrium concept in game theory formalized below.
Definition 2.1 (Nash equilibrium). A joint policy profile (Tieam Tade) E II is an E-approximate Nash equilibrium, for c. 0, if
(Tam: Tādi vp Tcams π adv)
Vo((TT π p): add) + E, Ak E [n], VT E IIg, ol Teamm πI adv) E,
VT' ad 11
That is, a joint policy profile is (approximate) Nash equilibrium if unilateral deviation from a player can result in non-negligible-mae more than additive improvement for that player. Nash equilibria always exist multi-agent stochastic games (Fink, 1964); our main result implies an (efficient) constructive proof of that fact for the special case of adversarial team Markov games.
2.3 ADVERSARIAL MARKOV POTENTIAL GAMES
A recent line of work has extended the fundamental class of potential normal-form games (Monderer & Shapley, 1996) Markov potential games (Marden, 2012: Macua al., 2018; Leonardos al., 2021: Ding et al., 2022; Zhang et al., 2021 b; Chen et al., 2022: Maheshwari et al., 2022; Fox et al., 2022). Importantly, our results readily carry over even if players in the team are not necessarily identically interested, but instead, there is some underlying potential function for the team; we will refer to such games as udversarial Markov potential gumes, formally introduced below.
Definition 2.2. An adversarial Markov potential game G (S.N, A, B, (rktkejn),PP P. multi-agen discounted MDP that shares all the properties of adversarial team Markov games (Sec- tion 1), with the exception that (2) is relaxed that there exists a potential function 4., Vs S such that for any addy E Nadv
T (TT,, -K: T addv)
4, (T kT' π -h: addr)) Vk, π -K Rade) - Vk.o (TT πI π Wadv);
for every agent k E [m], every state E S, and all policies Thi Tu E 11, and π π II
3 MAIN RESULT
In this section, we sketch the main pieces required in the proof of our main result, Theorem 1.1. We begin by describing our algorithm Section 3.1. Next, in Section 3.2, we characterize the strategy a X' for the team returned by IPGMAX, while Section 3.3 completes the proof by establishing that can be efficiently extended to an approximate Nash equilibrium. The formal proof of Theorem 1.1 is deferred to the Appendix.
3.1 OUR ALGORITHM
In this subsection, we describe in detail our algorithm for computing e-approximate Nash equilibria, IPGMAX, in adversarial team Markov games (Algorithm 1). IPGMAX takes as input a precision
parameter O (Line 1) and an initial strategy for the team (æ= x (0) E X =
X== X (Line 2). The algorithm then proceeds in two phases:
In the first phase the team players are performing independent policy gradient steps (Line 7) with learning rate n, as defined in Line 3, while the adversary is then best responding to their joint strategy (Line 6). Both these steps can be performed in polynomial time under oracle access to the game (see Remark 2). This process is repeated for 7' iterations, with T as defined in Line 4. We note that Proj (-) in Line 7 stands for the Euclidean projection, ensuring that a
each player selects valid strategy. The first phase is completed in Line 9, where according to the iterate at time t", for some 0 < t* < T 1. As we explain in Section 3.2, selecting uniformly at random practical and theoretically sound way of setting !*.
5

---

Published as a conference paper at ICLR 2023
In the second phase determine a strategy y E y so that (æ, 9) is an -aproxxpoo Nash equilibrium. This is accomplished in the subroutine AdvNashPolicy/ program-from the perspective of the adversary- that has polynomial size. Our analysis of the second phase of IPGMAX can be found in Section 3.3.
fixing the strategy of the team E X, and the main goal is to
which consists of solving linear
is worth stressing that under gradient feedback, IPGMAX requires no communication or coordi- nation between the players in the team.
Algorithm Independent Policy GradientMax (IPGMAX)
Precision > 0
2: Initial Strategy (0) X
2(1-7))
3: Learning rate vj = 32S " (Ei- A
5125 D (E AL+B)'
4: Number of iterations T
(11--)
5: for t 1.2,.... T
6:
y <- arg maxyey V V (zo(1-1),)) y)
7:
(1) Projx, 2 -n/Va Ne (z(((t-1) ,((1))))
(1-1)
for all agents i [n]]
8: end for
9: & (!")
10: y + RdVNashPolicy((d)
> defined in Algorithm
return (&. 9)
3.2 ANALYZING INDEPENDENT POLICY GRADIENTMAX
In this subsection, we establish that IPGMAX finds an c-nearly stationary point â of o(x) = maxyey Vz, y) in a number iterations T that is polynomial in the natural parameters of the game, well as 1/e; this is formalized in Proposition 3.1.
First, we note the by-now standard property that the value function V, is L-Lipschitz continuous and Ê-smooth, where L = VE A and l == 15 (Lemma C.I). An important observation for the analysis is that IPGMAX is essentially performing gradient descent steps on ((x). However, the challenge is that Φ(x) is not necessarily differentiable; thus, our analysis relies on the Moreau envelope of Φ, defined as follows.
(1-3)²
(1-7)3
Definition 3.1 (Moreau Envelope). Let ((x) maxyey Vplar, y). For any < x < 1 the Moreau envelope Φx of o is defined as
| x0(12
Φ* xx(x)= = min a'
d(z)) + 2A
(4)
We will let = 28-
Crucially, the Moreau envelope dx. introduced in (4), is f-strongly convex; this follows imme- diately from the fact that o(x) is k-weakly conver, in the sense that o(x) + |22 is convex (see Lemma A.1). A related notion that will be useful to measure the progress of IPGMAX is the proxi- mal mapping of function f. defined as prox, X' タ æ + arg min {f(x') ) + ] ]| =
the proximal point of (2(2) is well-defined since á is f-weakly convex (Proposition A.1). We are now ready to state the convergence guarantee of IPGMAX.
(1-y)* Proposition 3.1. Consider any c > 0. If n 2c2 7) and T 8 Ag m)2 there exists an iterate t*, with 0 < t" < T 1, such that [x())) x((")) I c, where a((") = prox (xx(*))
The proof relies on the techniques of Lin et al. (2020), and it deferred to Appendix C. The main takeaway is that O11/et) iterations suffice in order to reach e-nearly stationary point of o in the sense that e-far in l distance from its proximal point. A delicate issue here is that Proposition 3.1 only gives a best-iterate guarantee, and identifying that iterate might introduce

---

Published as a conference paper at ICLR 2023
substantial computational overhead. To address this, also show in Corollary C.1 that by randomly selecting [[o]{1/6)] iterates over the I repetitions of IPGMAX, we are guaranteed to recover an c- nearly stationary point with probability at least 1 6, for any 8 >> 0.
3.3 EFFICIENT EXTENSION TO NASH EQUILIBRIA
In this subsection, we establish that any e-nearly stationary point & of ó, can be extended to an eaprrxiapo Nash equilibrium (ě, ÿ) for any adversarial team Markov game, where ÿ y is the strategy for the adversary. Further, we show that y can be computed in polynomial time through a carefully constructed linear program. This "extendibility" argument significantly extends seminal characterization of Von Stengel & Koller (1997), and it is the crux in the analysis towards establishing our main result, Theorem 1.1.
To this end, the techniques we leverage are more involved compared to (Von Stengel & Koller, 1997), and revolve around nonlinear programming. Specifically, in the spirit of (Filar & Vrieze, 2012, Chapter 3), the starting point of our argument is the following nonlinear program with variables
(x, v) E X x S
min Ep(s)u(s) + El|x 2112
RES
s.t. b) +
Σ s'ES
P(s'lss 2, S uss), V(s.b) E E
(Q1)
(Q-NLP)
2 1 = 1, v(k, E [n] x S; and (Q2)
Kk,.aa 20, 0. Ak [m], (s. E S Ak. (Q3)
Here, we have overloaded notation so that r(s, x. b) = Easa, [r(s, a. b] and P(s' 8, æ. b)) = Ba-a,, [P(s'|s, a, b)]. For fixed strategy E X' for the team, this program describes the (discounted) MDP faced by the adversary. central challenge in this formulation lies in the eenconvexity-noncomeaae
of the constraint functions, witnessed by the multilinear constraint (QI). Importantly, unlike standard MDP formulations, we have incorporated a quadratic regularizer the objective function; this term ensures the following property.
Proposition 3.2. For any fixed x E X, there is a unique optimal solution w² to (Q-NT.).. Further, if à = prox (/(e) (œ) and e E RSS is the corresponding optimal, then (it, 6) is the global optimum of (Q-NLP).
The uniqueness of the associated value vector a consequence of Bellman's optimality equation, while the optimality of the proximal point follows by realizing that (Q-NLP) is an equivalent for- mulation of the proximal mapping. These steps are formalized in Appendix B.2. Having established the optimality of (i, t). the next step is to show the existence of nonnegative Lagrange multipliers satisfying the KKT conditions (recall Definition A.2); this is non-trivial due to the nonconvexity of the feasibility set of (Q-NLP).
To do so, we leverage the so-called Arrov-Hurwicz-Uaann Uzawa constraint qualification (Theo- rem A.1)-a form of "regularity condition" for a nonconvex program. Indeed, in Lemma B.3 we show that any feasible point of (Q-NLP) satisfies that constraint qualification, thereby implying the existence of nonnegative Lagrange multipliers satisfying the KKT conditions for any local optimum (Corollary B. and in particular for (œ, ö):
Proposition 3.3. There exist nonnegative Lagrange multipliers satisfying the KKT conditions at (Ø. 8).
Now the upshot is that subset of those Lagrange multipliers Á E S can be used to establish the extendibility to Nash equilibrium. Indeed, our next step makes this explicit: We construct linear program whose sole goal is to identify such multipliers, which in turn will allow us to efficiently compute admissible strategy for the adversary ÿ. However, determining X exactly seems too ambitious. For one, IPGMAX only granted us access to é but not to ă. On the other hand, the Lagrange multipliers are induced by (ă, ū). To address this, the constraints of our linear program phrased in terms of (ft, i), instead of (ø, 6), while to guarantee feasibility
7

---

Published as a conference paper at ICLR 2023
appropriately relax all the constraints of the linear program; this relaxation does not introduce large error since || æll I < (Proposition 3.1), and the underlying constraint functions are Lipschitz continuous- witth constants that depend favorably on the game G; we formalize that in Lemma B.4. This leads to our main theorem, summarized below (see Theorem B.1 for a precise statement).
Theorem 3.1. Let & be an e-nearly stationary point of Φ. There exist a linear program, (L.Padv), such that:
(i) It has size that is polynomial in G, and all the coefficients depend on the (single-agent) MDP faced by the adversary when the team is playing a fixed strategy i;; and
(ii) It is always feasible, and any solution induces strategy y such that (0. ÿ) is an ((e)- approximate Nash equilibrium.
The proof of this theorem carefully leverages the structure of adversarial team Markov games, along with the KKT conditions we previously established in Proposition 3.3. The algorithm for computing the policy for the adversary is summarized in Algorithm 2 of Appendix B. A delicate issue with Theorem 3.1, and in particular with the solution of (LP adv),,, whether one can indeed esficiently simulate the environment faced by the adversary. Indeed, in the absence of any structure, deter- mining the coefficients of the linear program could scale exponentially with the number of players; this is related to a well-known issue in computational game theory, revolving around the exponen- tial blow-up of the input space as the number of players increases (Papadimitriou & Roughgarden, 2008). As is standard, we bypass this by assuming access to natural oracles that ensure we can efficiently simulate the environment faced by the adversary (Remark 2).
4 FURTHER RELATED WORK
In this section, we highlight certain key lines of work that relate to results in the context of adversarial team Markov games. We stress that the related literature on multi-agent reinforcement learning (MARL) is too vast to even attempt faithfully cover here. For some excellent recent overviews of the area, we refer the interested reader to (Yang & Wang, 2020; Zhang et al., 2021a) and the extensive lists of references therein.
Team Games. The study of team games has been a prolific topic of research in economic theory and group decision theory for many decades; see, e.g., (Marschak, 1955; Groves, 1973; Radner, 1962; Ho Chu, 1972). A more modern key reference point to our work is the seminal paper of Von Stengel & Koller (1997) that introduced the notion of team-maxmin equilibrium (TME) in the context of normal-form games. A TME profile is a mixed strategy for each team member so that the minimal expected team payoff over all possible responses of the adversary-wil potentially knows the play of the team-is the maximum possible. While TME's enjoy number of compelling properties, being the optimal equilibria for the team given the lack of coordination, they suffer from computational intractability even in 3-player team games (Hansen et al., 2008; Borgs et al., 2010).² Nevertheless, practical algorithms have been recently proposed and studied for computing them in multiplayer games (Zhang& & An, 2020a;b; Basilico et al., 2017). It worth pointing out that team equílibria are also useful for extensive-form two-player zero-sum games where one of the players has imperfect recall (Piccione & Rubinstein, 1997).
The intractability of TME has motivated the study of a relaxed equilibrium concept that incorporates a correlation device (Farina et al., 2018; Celli & Gatti, 2018: Basilico et al., 2017; Zhang & An, 2020b; Zhang Sandholm, 2021: Zhang al., 2022b; Carminati et al., 2022: Zhang et al., 2022a); namely, TMECor. In TMECor players are allowed to select correlated strategies. Despite the many compelling aspects of TMECor as a solution concept in team games, even ex ante coordination or correlated randomization beyond the structure of the game itself-can can be overly expensive or even infeasible in many applications (Von Stengel & Koller, 1997). Further, even TMECor is NP- extensive-form games (EFGs) (Chu (FPT) algorithms have recently emerged for natural classes of EFGs (Zhang& & Sandholm, 2021; Zhang et al., 2022b).
hard to compute (in the worst-case) for imperfecttinfoommaiiie & Halpern, 2001), although seeedd--armmtee-treeee
Hansen al. (2008); Borgs et al. (2010) establish FNP-hardness and inapproximahility for general 3- player games, but their argument readily applies to 3-player team games as well.
8

---

Published as a conference paper at ICLR 2023
On the other hand, the computational aspects of the standard Nash equilibrium (NE) in adversarial team games is not well-understood, even in normal-form games. In fact, it is worth pointing out that Von Neumann's celebrated minimax theorem (von Neumann & Morgenstern, 2007) does not apply in team games, rendering traditional techniques employed in two-player zero-sum games of little use. Indeed, Schulman & Vazirani (2017) provided a precise characterization of the duality gap between the two teams based on the natural parameters of the problem, while Kalogiannis et al. (2021) showed that standard no-regret learning dynamics such as gradient descent and optimistic Hedge could fail to stabilize to mixed NE even in binary-action adversarial team games. Finally, we should also point out that although from a complexity-theoren
standpoint our main result (The- orem I.1) establishes a fully polynomial time approximate scheme (FP),S), since the dependence on the approximation error e is poly(1 /e), )), an improvement to poly(log(1/e) is precluded even in normal-form games unless CLS S P (an unlikely event); this follows as adversarial team games cap- ture potential games (Kalogiannis et al., 2021), )), wherein computing mixed Nash equilibria is known to be complete for the class CLS = PPAD n PLS (Babichenko & Rubinstein, 2021).
Multi-agent RL. Computing Nash equilibria has been central endeavor in multi-agent RL. While some algorithms have been proposed, perhaps most notably the Nash-Q algorithm (Hu & Wellman, 1998; 2003), convergence to Nash equilibria is only guaranteed under severe restrictions game. More broadly, the long-term behavior of independent policy gradient methods (Schulman et al., 2015) is still not well-understood. Before all else, from the impossibility result of Hart & Mas-Colell, universal convergence to Nash equilibria is precluded even for normal-form games; this is aligned with the computational intractability (PPAD-completeness) of Nash equilibria even in two-player general-sum games (Daskalakis et al.. 2009; Chen et al., 2009). Surprisingly, recent work has also established hardness results in turn-based stochastic games, rendering even the weaker notion of (stationary) CCEs intractable (Daskalakis et al., 2022; Jin et al., 2022).
the
As a result, the existing literature has inevitably focused on specific classes of games, such as Markov potential games (Leonardos et al., 2021; Ding et al., 2022; Zhang et al., 2021 Chen et al., 2022: Maheshwari et al., 2022; Fox et al., 2022) or two-player zero-sum Markov games (Daskalakis et al., 2020; Wei et al., 2021: Sayin et al., 2021; Cen et al., 2021; Sayin et al., 2020). As we pointed out earlier, adversarial Markov team games can unify and extend those settings (Section 2.3). More broadly, identifying multi-agent settings for which Nash equilibria are provably efficiently com- putable is recognized as an important open problem in the literature (see, e.g., (Daskalakis et al., 2020)), boiling down to one of the main research question of this paper (Question ())). We also remark that certain guarantees for convergence to Nash equilibria have been recently obtained in class of symmetric games (Emmons al., weaker solution concepts relaxing either the Markovian or the stationarity properties have also re- cently attracted attention (Daskalakis et al., 2022; Jin et al., 2021).
symmetric team games. Finally,
5 CONCLUSIONS
Our main contribution in this paper is the first polynomial algorithm for computing (stationary) Nash equilibria in adversarial team Markov games, important class of games in which team of uncoordinated but centtically-nntrestter players is competing against an adversarial player. We argued that this setting serves as a step towards modeling more realistic multi-agent applications that feature both competing and cooperative interests.
There are many interesting directions for future research. One caveat of our main algorithm (IPGMAX) is that it requires a separate subroutine for computing the optimal policy of the adversary. is plausible that a carefully designed two-timescale policy gradient method can efficiently reach a Nash equilibrium, which would yield fully model-free algorithms for ad adversarial team Markov games by obviating the need to solve a linear program. Techniques from the literature on constrained MDPs (Ying et al., 2022) could also be useful for computing the policy of the ad- versary in a more scalable way. Furthermore, exploring different solution concepts- berepts-beyondd Nash cquilibria-could also be a fruitful avenue for the future. Indeed, allowing some limited form of cor- relation between the players in the team could lead to more efficient algorithms; whether that form of coordination is justified (arguably) depends to large extent the application at hand. Finally, returning to Question +)) ), a more ambitious agenda revolves around understanding the fundamental structure of games for which computing Nash equilibria is provably computationally tractable.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We are grateful to the anonymous ICLR reviewers for their valuable feedback. Ioannis Anagnostides thanks Gabriele Farina and Brian H. Zhang for helpful discussions. Ioannis Panageas would like to acknowledge a start-up grant. Part of this project was done while he was a visiting research scien- tist the Simons Institute for the Theory of Computing for the program "Learning and Games". Vaggos Chatziafratis was supported by start-up grant of UC Santa Cruz, the Foundations of Data Science Institute (FODSI) fellowship at MIT and Northeastern, and part of this work was carried out at the Simons Institute for the Theory of Computing. Emmanouil V. Vlatakis Vlatakis-Gkaragkoun Gkaragkounis is grateful for financial support by the Google-Simons Fellowship. Pancretan Association of Amer- Algorithms and Geometry. This project was completed while
ica and Simons Collaboration he was a visiting research fellow at the Simons Institute for the Theory Computing. Addition- ally, he would like to acknowledge the following series of NSF-CCF grants under the numbers 066397001177188711111331111188
REFERENCES
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. Conference on Learning Theory, COLT 2020, 9-12 July 2020, volume 125 of Proceedings of Machine Learning Research, pp. 64-66. PMLR, 2020.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Ioannis Anagnostides, Fivos Kalogiannis, Ioannis Panageas, Emmanouil- Vasileios Vlatakis- Gkaragkounis, and Stephen McAleer. Algorithms and complexity for computing nash equilibria in adversarial team games. CoRR, abs/2301.0211 2023.
Kenneth J Arrow, Leonid Hurwicz, and Hirofumi Uzawa. Constraint qualifications in maximization problems. Naval Research Logistics Quarterly, 8(2)1155-11, 1961.
Robert Aumann. Subjectivity and correlation randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974.
Yakov Babichenko and Aviad Rubinstein. Settling the complexity of nash equilibrium congestion games. In STOC 21: 53rd Anmual ACM SIGACT Symposium on Theory of Computing, 2021, pp- 1426-1437. ACM, 2021. doi: 10. 145/3406325.3451033
Nicola Basilico, Andrea Celli, Giuseppe De Nittis, and Nicola Gatti. Team-maxmin equilibrium: Efficiency bounds and algorithms. In Satinder Singh and Shaul Markovitch (eds.), Proceedings of the Phirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, pp. 356-362. AAAI Press, 2017
MS Bazaraa, JJ Goode, and CM Shetty. Constraint qualifications revisited. Management Science, 18(9):567-573, 1972.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint exxiv:9966 0776, 2019.
Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, and Christos H. Papadimitriou. The myth of the folk theorem. Games Econ. Behav,, 70(1):34-43 2010. doi: 10.
Michael Bowling. Convergence problems of general-sum multiagent reinforcement learning. In In Proceedings of the Seventeenth International Conference on Machine Learning, pp. 89-94. Morgan Kaufmann, 2000.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold em poker is solved. Science, 347(6218): 2015. doi: 10.1 1tt.ciinne.11994999.
10

---

Published as a conference paper at ICLR 2023
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374))418 4244, 2018. doi:
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019. doi: 10.1 10.1126/science.ayy24000
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfect-informatio games. In Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
Luca Carminati, Federico Cacciamani, Marco Ciccone, and Nicola Gatti. A marriage between ad- versarial team games and 2-player games: Enabling abstractions, no-regret learning, and subgame solving. In International Conference on Machine Learning, ICMI. 2022, volume 162 of Proceed- ings of Machine Learning Research, pp. 2638-2657, PMLR, 2022.
Andrea Celli and Nicola Gatti. Computational results for extensive-form adversarial team games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, pp. 27952-27964, 2021.
Dingyang Chen, Qi Zhang, and Thinh T. Doan. Convergence and price of anarchy guarantees of the softmax policy gradient in markov potential games. In Decision Awareness in Reinforcement Learning Workshop at ICML 2022, 2022.
Xi Chen, Xiaotie Deng, and Shang-Hus Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, (6:3)::4:1114:577 2009. doi: 10. 10.1145/1115111.1116611
Francis C. Chu and Joseph Y. Halpern. On the np-completeness of finding optimal strategy in games with common payoffs. Int. J. Game Theory, 30(1):99-106, 2001. doi: 10.1007/ s001820 1001820100066.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multia- gent systems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 98, pp. 746-752. AAAI Press / The MIT Press, 1998.
Anne Condon. On algorithms for simple stochastic games. In Advances in Computational Com- plexity Theory, volume 13 of DIMACS Series Discrete Mathematics and Theoretical Computer Science, pp. 51-73. American Mathematical Society, 1993.
Constantinos Daskalakis, Alex Fabrikant, and Christos H. Papadimitriou. The game world is flat: The complexity of nash equilirria in succinct games. In Automata, Languages and Programming, 33rd International Colloquiun, ICALP 2006, volume 4051 I of Lecture Notes in Computer Science, pp. 514. Springer, 2006. doi: 10. 1007/1 1786986), 45.
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM J. Comput., 39(1):195-25) 2009. doi: 10. 137/070699652.
Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33: 5527-5540, 2020.
Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of markov equilib- rium in stochastic games. CoRR, abs/2204.03991, 2022. doi: (0.48550/axxxx220043399.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, (9:2722773, 20119.

---

Published as a conference paper at ICLR 2023
Dongsheng Ding, Chen- Yu Wei, Kaiqing Zhang, and Mihailo R Jovanovié. Independent policy gra- dient for large-scale markov potential games: Sharper rates, function approximation, and game- agnostic convergence. arXiv preprint arXiv:2202.0411 2022.
Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematicall Programming. 178(1):503-55) 558, 2019.
Scott Emmons, Caspar Oesterheld, Andrew Critch, Vincent Conitzer, and Stuart Russell. For learn- ing in symmetric teams, local optima are global nash equilibria. In International Conference on Machine Learning, ICML. 2022, volume 162 of Proceedings of Machine Learning Research, pp- 5924-5944 PMLR, 2022.
Kousha Etessami and Mihalis Yannakakis. On the complexity of nash equilibria and other fixed points. SIAM Comput., 39(6): 2010. doi: 10.11377080720826.
Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. Ex ante coordination and collusion in zero-sum multi-player extensive-form games. In Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurlPS 2018. pp. 9661-9671, 2018.
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
A. M. Fink. Equilibrium in stochastic n-person game. Journal of Science of the Hiroshima University, Series A-I (Mathematics), 28(1):89 93, 1964. doi: 10.32917/hmj/ httpm///mmmm//1/111111 (ttin///22119999 135588
Roy Fox, Stephen M. McAleer, Will Overman, and Ioannis Panageas. Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, volume 151 of Proceedings of Machine Learning Re- search, pp. 4414 4425. PMLR, 2022.
Giorgio Giorgi et al. A guided tour in constraint qualifications for nonlinear programming under differentiabilityy assumptions. Technical report, University of Pavia, Department of Economics and Management, 2018.
Theodore Groves. Incentives in teams. Econometrica, 41(4):617-6311 1973.
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen. Approximability and parameterized complexity of minmax values. In International Workshop on Internei and Network Economics, pp. 684-695. Springer, 2008.
Sergiu Hart and Andreu Mas-Colell. Uncoupled dynamics do not lead to nash equilibrium. American Economic Review, 93(5): 1800)183333-666 2003.
Yu-Chi Ho and K ai-Chhin Chu. Team decision theory and information structures in optimal control problems-part i. IEEE Transactions Automatic Control, 17(1):15-22, 1972. doi: 10.1109
19C.1977.10998800
Wassily Hoeffding and J. Wolfowitz. Distinguishability of Sets of Distributions. The Annals of Mathematical Statistics, 29(3):700 - 718, 1958.
Junling Hu and Michael P. Wellman. Multiagent reinforcement learning: Theoretical framework and an algorithm. Proceedings of the Fifieenth International Conference on Muchine Learning, ICML 198, pp. 240, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc.
Junling Hu and Michael P. Wellman. Nash g-larnnigg for general-sum stochastic games. J. Mach. Learn. Res., 4:1039 1069, 2003.
Wan Huang and Bernhard von Stengel. Computing an extensive-form correlated equilibrium in polynomial time. In Internet and Network Economics, 4th International Workshop, WINE 2008, volume 5385 of Lecture Notes in Computer Science, pp. 506-513. Springer, 2008, doi: 10.1007/ 998-3-540-92188-11 56.
12

---

Published as a conference paper at ICLR 2023
Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael I. Jordan. Is q-learning provably effi- cient? In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018. NeurIPS 2018. pp. 4868 4878, 2018. 2018.
Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. What local optimality in nonconvex- nonconcave minimax optimization? In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, volume 119 of Proceedings of Machine Learning Research, pp- 4880-4889. PMLR, 2020.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning simple, efficient, decentral- ized algorithm for multiagent rl. arXiv preprint arXiv:21 14555, 2021.
Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The complexity of infiite-hhorizon general-sum stochastic games. arXiv preprint arXiv:2204.044 000000044666 2022.
Fivos Kalogiannis, Emmanouil- Vasileios Vlatakis- Manakis-Gkaragkounii and loannis Panageas. Teamwork makes von neumann work: Min-max optimization in two-team zero-sum games. arXiv preprint arXiv:2111.04178, 2021.
Hamaanoul-VVasileios
Stefanos Leonardos, Will Overman, Joannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient markov potential games. arXiv preprint arXiv:2 0/90., 2021.
Yuanzhi Li, Ruosong Wang, and Lin Yang. Settling the Morizonnddpendenne of sample complexity in reinforcement learning. In 62nd IEEE Annual Symposium Foundations Computer Science, FOCS 202/, pp. 965-9766 IEEE, 2021. doi: 10. 19.100990CCS52999222222 000097.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-coneat mini- max problems. In International Conference on Machine Learning, pp. 6083-6093, PMLR, 2020.
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorith- mie framework for model- deep reinforcement learning with theoretical guarantees. In 7th International Conference on Learning Representations, ICI. 2019. OpenReview.net, 2019.
Sergio Valcarcel Macua, Javier Zazo, and Santiago Zazo. Learning parametric closed-loop policies markov potential games. arXiv preprint arXiv: wow.:080200999 2018.
Chinmay Maheshwari, Manxi Wu, Druv Pai, and Shankar Sastry. Independent and decentralized learning in markov potential games, 2022.
Olvi L Mangasarian. Nonlinear programming. SIAM, 1994.
Jason Marden. State based potential games. Automatica, 48(12):3075-3088 2012.
J. Marschak. Elements for a theory of teams. Management Science, 1(2): 1955.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124- 143, 1996.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 35666337::008-511, 2017. doi: 10.1 126/science. aam6960.
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-4):201- 221, 1978.
Katta G Murty and Santosh N Kabadi. Some np-complete problems in quadratic and nonlinear programming. Technical report, 1985.
John Nash. Non-cooperative games. Annals of mathematics, pp- 286-295, 1951.
Christos H. Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi multi-player
games. J. ACM, 14:11:14:11 2008. doi: 10.11497/3777799911777722
13

---

Published as a conference paper at ICLR 2023
Julien Perolat, Bart de Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen, Zhe Wang, Audrunas Gruslys, Aleksandra Malysheva, Mina Khan, Sherjil Ozair, Finbarr Timbers, Toby Pohlen, Tom Eceles, Mark Rowland, Marc Lanctot, Jean-Baptiste Lespiau, Bilal Piot, Shayegan Omidshafiei, Edward Lockhart, Laurent Sifre, Nathalie Beauguerlange, Remi Munos, David Silver, Satinder Singh, Demis Hassabis, and Karl Tuyls. Mastering the game of stratego with model-free multiagent reinforcement learning, 2022.
Michele Piccione and Ariel Rubinstein. On the interpretation of decision problems with imperfect recall. Games and Economic Behavior, 20(1):3-24, 1997. doi: https://doi.org/ 1006/game.
1997.0536.
Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
R. Radner. Team Decision Problems. The Annals of Mathematical Statistics, 33(3):857 881, 1962. doi: 10.214//mm/1117704555.
Tyrrell Rockafellar. Convex analysis, volume 18. Princeton university press, 1970.
Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. SIGecom Exch., 15(2):45-49, 2017. doi: 10. N0.1145/305558933055555 33055596.
Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar, Decentral- ized q-learning in zero-sum markov games. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, vol- ume 34, pp. 18320-18334 Curran Associates, Inc., 2021.
Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. Fictitious play in zero-sum stochastic games. arXiv preprini wrXiv:2010.04223,, 2020.
John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference Machine Learn- ing. ICML 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1889-1897. JMLR. 2015.
Leonard Schulman and Umesh V Vazirani. The duality gap for two-team zero-sum games. In 8th Inmovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik, 2017.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Process- ing Systems 2018, pp. 5192-5202, 2018.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lilli- crap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nat., 550(7676::344359) 2017. doi: 10. 00.1038/mature24270.
Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom Le Paine, Çaglar Gülçehre, Ziyu Wang, To- bias Pfaff, Yuhuai Wu, Roman Ring. Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap. Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft II using multi-agent reinforcement learning. Nat., 575(7782):350-835 354, 2019. doi: 10.1008//41 586-019-1111 11-6-19--722--2
14

---

Published as a conference paper at ICLR 2023
John Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition). Princeton University Press, 2007. doi: doi:10.1515/ 9781400829460.
Bernhard von Stengel and Daphne Koller. Team-maxmin equilibria. Games and Economic Behavior, 21(1):309331, 1997. doi: https://doi.org/10.. wwt.or///....////..../ 1006/gmme. http://amm..99....m. 1997.0527.
Bernhard Von Stengel and Daphne Koller. Team-maxmin equilibria. Games and Economic Behav- ior, 21(1-2):309-33 -21, 1997.
Okko Jan Vrieze. Stochastic games with finite state and action spaces. CWI tracts, 1987.
Xiaofeng Wang and Tuomas Sandholm. Reinforcement learning to play an optimal nash equilib- rium in team markov games. In Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, NIPS 2002, December 9-14, 2002, pp. 1571-1578, MIT Press, 2002.
Chen-Yu Yu Wei, Chung-Wer Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 1259-42991 PMLR, 15- 19 Aug 2021.
Lin Xiao. On the convergence rates of policy gradient methods. arXiv preprint arX1v:2201.07443, 2022.
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theo- retical perspective. arXiv preprint (rXiv:2011.0058. 2020.
Yinyu Ye. The simplex and policy-iteration methods are strongly polynomial for the markov deci- sion problem with a fixed discount rate. Mathematics of Operations Research, 36(4);593-603, 2011.
Donghao Ying, Mengzi Guo, Yuhao Ding, Javad Lavaei, et al. Policy-based primal-dual methods for convex constrained markov decision processes. arXiv preprint arXiv:2205.10715 2022.
Brian Hu Zhang and Tuomas Sandholm. Team correlated equilibria in zero-sum extensive-form games via tree decompositions. CORR, 0tt/2219900284. 2021.
Brian Hu Zhang, Luca Carminati, Federico Caceiamani, Gabriele Farina, Pierriccardo Olivieri, Nicola Gatti, and Tuomas Sandholm. Subgame solving in adversarial team games. In Neural Information Processing Systems (NeurIPS), 2022a.
Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Team belief DAG form: A concise rep- resentation for team-correlated game-theoretic decision making. CoRR, abs/2202.00789, 2022b.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp-
321-384, 2021a.
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: stationary points, con- vergence, and sample complexity. arXiv preprint arXiv:2106.00198, 2021b.
Youzhi Zhang and Bo An. Converging to team-maxmin equilibria in zero-sum multiplayer games. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, volume 119, pp. 11033-11043, PMLR, 2020a.
Youzhi Zhang and Bo An. Computing nam-maxmin equilibria zero-sum multiplayer extensive- form games. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pp- 2318-2325, AAAI Press, 2020b.
15


Reviews:
[{"review_id": "twJixwP2en", "reviewer": "Reviewer_1bpS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers multi-agent Markov games; specifically, the problem of computing a Nash equilibrium. Even in normal-form games, it is computationally intractable to compute a Nash equilibrium in two-player general-sum games, much less in games with more players. In this paper, the game is restricted to coalition of players with a common adversary, so-called \"adversarial team Markov games\". In addition to the case when the coalition shares a common objective, the results extend to the case in which the objectives of the coalition share a common potential function (Markov potential games). ", "summary_of_the_review": "Based on the above strengths and weaknesses, the paper clearly is in the \"Accept\" category.", "strength_and_weaknesses": "# Strengths\n- The paper introduces the first poly-time algorithm to compute a Nash equilibrium in the setting of adversarial team Markov games. Computing a Nash equilibrium is an important practical problem, but unfortunately the general-case is difficult. Therefore, it is useful and relevant to consider special cases such as the coalition considered here.\n- The algorithm has good scaling with the action sets of each agent; that is, it scales with their sum rather than the product.\n- The techniques used to obtain this result are well described at an overview level and compared to the most relevant related work which is to compute a Nash equilibrium in the analogous normal-form setting. The challenges in generalizing the normal-form setting to Markov game include: nonlinear program with a set of nonconvex constraints, which requires the Arrow-Hurwiz-Uzawa constraint qualification technique.\n\n# Weaknesses\n- The type of game considered is very special. It is only a modest generalization of two-player zero-sum games. More practical would be algorithms that have exponential worst-case but still run on practical examples of n-player Markov games. Still, any generalizations from fully cooperative or competitive two-player games are welcome.\n- The practical scalability of the algorithm is not evaluated. Although it is polynomial, the number of iterations looks very large from inspection of the pseudocode.  Still, this is a theoretical work, so this isn't too significant of a weakness.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "T4VHUDABob", "reviewer": "Reviewer_S2Qp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies a zero-sum team Markov game. In the game, a team of agents compete with an adversary. Agents in the team have the same reward function, and the sum of the team and the adversary's rewards is zero. The paper in particualr looks at a class of potential games. The main contribution of the paper is to propose a set of algorithms to compute a stationary epsilon-Nash equilibrium of the game. ", "summary_of_the_review": "A paper on a well-motivated problem, overall well written but with some issues on the clarifty. Results are comprehensive and very technical, but with some weaknesses that raise questions about how meaningful the results are, which may or may not be crucial. ", "strength_and_weaknesses": "Strength: \n\nThe problem is well-motivated and the paper is written well overall. The proposed approach to computing an approximate Nash equilibrium looks non-trivial and brings in many interesting concepts. The authors also provide a good summary about the related work.\n\nWeakness: \n\n- Section 3.3 could have been improved to make the main idea clearer. It is unclear to me what is the main advantage of the proposed methods? In particular, why not just solve Q-NLP without the regularizer in the objective function, which gives a Nash equilibrium directly and seems much more manageable than the current formulation?  \n\n- The approach relies on an oracle to tackle a computational obstacle, which may be crucial. This further deepens the question of how meaningful the proposed methods are compared with solving Q-NLP without the regularizer --- now that there's an oracle to use, so supposedly it also simplifies the problem of solving Q-NLP without the regularizer.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-6NkJnUU1U", "reviewer": "Reviewer_V4b6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides an efficient algorithm to compute the Nash Equilibria in an adversarial team Markov game. Specifially, in this zero sum Markov game, a team of players try to gain reward as much as possible, and an adversary tries to lose reward as less as possible. The authors propose an algorithm called IPGMAX. In this algorithm, all the team players will first do policy gradient descent for several steps, and this procedure returns the team players' policies in Nash Equilibria. Then the algorithm uses a procedure to look for the response of the adversarial policy (to the team players' policies). The authors show that, team players' policies as well as the the response of the adversarial policy form a Nash Equilibria, and the time cost of the algorithm is polynomial, which can be much better than the exponential ones in prior works. ", "summary_of_the_review": "Overall, I have some questions about the algorithm in this paper, and give the score of \"weak accept\". I'd like to see the answers from the authors and I will change my score if the answers are convincing. \n\n=========After Rebuttal=========\n\nThe rebuttal explains about the details, and now I can understand how the algorithm works. I believe those details should also be included in the final version, so that the readers can easily understand it as well. \n\nMy remaining concerns (which are also mentioned by the other reviewers) are about the existance of the oracle and whether the given complexity upper bound is tight. I think some further works about the tightness could be done in the future. \n\nOverall, I agree that this work is an important step in efficiently looking for the Nash Equilibria in Marcov Games, and I would like change my score to \"accept\".\n", "strength_and_weaknesses": "Strength\n\nLooking for Nash Equilibrias in Markov Game is an important task, and reducing the time complexity from exponential to polynomial is also a significant contribution.\n\nWeaknesses\n\nThere are many parts not very clear in the IPGMAX algorithm (for details please see the questions below)\n\nMy Questions\n\n1. Proposition 3.1 shows that there must exists such a $t^*$, and Corollary C.1 shows that with high probability, there is one such $t^*$ in the randomly chosen set. However, it is still not very clear to me that how you can find this $t^*$ is this set. Do you mean that it is easy (with low computation cost) to check whether $x^{t}$ is good or not? How much is the computation cost here?\n\n2. In line 6 of Algorithm 1, we need to look for the best response of the adversary. What is the computation cost here?\n\n3. In line 7 of Algorithm 1, we need to compute the gradient of $V_{\\rho}$. What is the computation cost here?\n\n4. It is mentioned that the IPGMAX algorithm is a decentralized one (which may avoid communications between players), but I am wondering whether line 6 and line 7 in Algorithm 1 could be done without any communications? Do you mean that these steps could be done even if all the players (e.g. the team players) do not know others' policies in the last time step?\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%