Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem
Authors: Fivos Kalogiannis
Jingming Yan
Ioannis Panageas
Venue: NeurIPS 2024 poster (2024)
Keywords: MARL
Convex RL
Nash Equilibrium
Non-smooth Optimization
Minimax Optimization
Hidden Convexity
Nonconvex-nonconcave
Markov Games
Stochastic Games
Learning in Games
Primary area: algorithmic_game_theory
TL;DR: We develop a policy gradient method to learn a Nash equilibrium in a MARL setting which encompasses both cooperation and competition

Abstract: We study the problem of learning a Nash equilibrium (NE) in Markov games which is a cornerstone in multi-agent reinforcement learning (MARL). In particular, we focus on infinite-horizon adversarial team Markov games (ATMGs) in which agents that share a common reward function compete against a single opponent, *the adversary*. These games unify two-player zero-sum Markov games and Markov potential games, resulting in a setting that encompasses both collaboration and competition. Kalogiannis et al. (2023) provided an efficient equilibrium computation algorithm for ATMGs which presumes knowledge of the reward and transition functions and has no sample complexity guarantees. We contribute a learning algorithm that utilizes MARL policy gradient methods with iteration and sample complexity that is polynomial in the approximation error $\epsilon$ and the natural parameters of the ATMG, resolving the main caveats of the solution by (Kalogiannis et al., 2023). It is worth noting that previously, the existence of learning algorithms for NE was known for Markov two-player zero-sum and potential games but not for ATMGs.
    
Seen through the lens of min-max optimization, computing a NE in these games consists a nonconvex--nonconcave saddle-point problem. Min-max optimization has received an extensive study. Nevertheless, the case of nonconvex--nonconcave landscapes remains elusive: in full generality, finding saddle-points is computationally intractable (Daskalakis et al., 2021). We circumvent the aforementioned intractability by developing techniques that exploit the hidden structure of the objective function via a nonconvex--concave reformulation. However, this introduces a challenge of a feasibility set with coupled constraints. We tackle these challenges by establishing novel techniques for optimizing weakly-smooth nonconvex functions, extending the framework of (Devolder et al., 2014).

Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Connww Min-Max Optimization Problem
Fivos Kalogiannis" University of California, Irvine Archimedes/Athena RC, Greece
Jingming Yan* University of California, Irvine
Ioannis Panageas
University of California, Irvine Archimedes/Athenaa RC, Greece
Abstract
We study the problem of learning Nash equilibrium (NE) in Markov games which is a cornerstone in multi-agent reinforcement learning (MARL). In particular, focus on infinite-horizon adversarial team Markov games (ATMGs) in which agents that share common reward function compete against a single opponent, the adversary. These games unify two-player zero-sum Markov games and Markov potential games, resulting in setting that encompasses both collaboration and competition. [65] provided an efficient equilibrium computation algorithm for ATMGs which presumes knowledge of the reward and transition functions and has no sample complexity guarantees. We contribute learning algorithm that utilizes MARL policy gradient methods with iteration and sample complexity that is polynomial in the approximation error and the natural parameters of the ATMG, resolving the main caveats of the solution by [65]. It is worth noting that previously, the existence learning algorithms for NE was known for Markov two-player zero-sum and potential games but not for ATMGs.
Seen through the lens of min-max optimization, computing a NE in these games consists a nonconvex-nonconcan saddle-point problem. Min-max optimization has received extensive study. Nevertheless, the of nonconvex-noneconaan landscapes remains elusive: in full generality, finding saddle-points is compu- tationally intractable [33]. We circumvent the aforementioned intractability by developing techniques that exploit the hidden structure of the objective function via canconvex-concar reformulation. However, this introduces the challenge of a feasibility set with coupled constraints. We tackle these challenges by establishing novel techniques for optimizing weakly-smooth nonconvex functions, extending the framework of [35].
Introduction
Multi-agent reinforcement learning (MARL) investigates behaviors of multiple interacting agents within a dynamic, shared environment where the actions of each agent not only impact their individual rewards but also the overall state of the system. MARL has introduced several practical techniques that have justifiably captured public interest in recent years, particularly in skill-intensive games like starcraft, go, chess, and poker [12, 97, 101, 79, 16, 15, 14, 86], where its empirical methods have
"Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

achieved super- performance. More recently, MARL methods combined with large language models has excelled in the game of Diplomacy [6]. Despite these practical achievements, theoretical understanding of MARL has lagged behind its empirical successes.
Markov games (MGs) [95] is rigorous and versatile mathematical structure that MARL employs to systematically formalize the strategic interactions in the dynamic settings [71]. These games extend Markov decision processes (MDPs) [88] to multiple agents, each making decisions and receiving rewards independently as the environment evolves. The joint decisions of the agents influence both individual rewards and the transition of the environment. MARL in general is occupied with leading the multi-agent system to a favorable outcome. Through the lens of game theory, the notion of "favorable outcome" is formally defined through concepts like a Nash equilibrium and (coarse) correlated equilibrium. Although computing Nash equilibria is generally computationally intractable- even in two-player games without states [28, 24] becomes tractable in fully cooperative settings like Markov potential games [1 14, 68] and is also tractable in competitive scenarios such as two-player zero-sum Markov games [27, 103, 17]. Recent advances [65] also show computational tractability in adversarial team Markov games (ATMGs) a context that combines both cooperative and competitive dynamics among agents. More specifically, an infinite-horizon adversarial team Markov game (ATMG) is Markov Game in which team players, compete against one adversary. Each of the team players receives the same reward and is equal to minus the reward of the adversary. ATMGs generalize both Markov zero-sum and potential games; the former can be viewed as ATMGs with n = 1, the latter by choosing the adversary to be dummy (having one action).
Nash equilibrium computation in ATMGs naturally leads to a min-max optimization problem. Min- max optimization has been deeply explored across game theory, optimization, and machine learning. The past decade it has witnessed a proliferation of min-max optimization applications, notably in areas like generative adversarial networks (GANs) [49]. robust machine learning [73], and adversarial training [50]. In these applications, the optimization objectives often involve nonconvex-noncoonaay functions which pose substantial challenges. Typically, the aim is to approximate saddle-points of [æx y). In normal form games, these points correspond to Nash equilibria. This correspondence also holds true for MGs due to the gradient domination property [3]. Although we cannot aspire to cover the vast quantity of works in MARL and optimization, select some representative works that we defer to Appendix A due to space constraints.
This paper aims to develop learning methods to approximate Nash equilibria in team Markov games by using only individual rewards and state observations as feedback, addressing the following question and answering one of the main caveats of the solutions provided in [65]:
Is it possible for agents to efficiently learn Nash equilibria in adversarial team Markov games, having only access to trajectory roll-out samples and (almost") ) no communication, i.e., independently?
1.1 Our Contributions
Let us provide some context before stating our main results. An Siinite-hhoizonn adversarial team Markov game (ATMG) is characterized by a finite state-space S, n team players, each equipped with a finite action-space A., E (1...., n), and one adversary with a finite action-space B. Each of the team players receives the same reward which is equal to minus the reward of the adversary. The adversary's 's value function is defined as the discounted expected sum of their rewards, where the discount factor 7 E [0, 1). An approximate Nash equilibrium is product distribution over policy space such that no agent can improve their value by unilaterally deviating. We propose a learning algorithm that has both iteration and sample complexity polynomial in the parameters of the Markov Game and returns approximate Nash equilibria.
Theorem 1.1 (Informal Version Theorem 3.3). There is a learning algorithm (ISPNG) that uses bundit feedbuck and guarantees convergence to e-approximate Nash equilibrium in adversarial
*We say "almost" as the agents need to take turns in updating their policies instead of making updates simultaneously. Nevertheless, the learning dynamics remain uncoupled.

---

team Markov games, the sample and iteration complexities of which are
poly 1S].
Is|.
A + B
We deem noteworthy that our algorithm manages to compute a Nash equilibrium in a Markov game, which combines opposing and shared agent interests, by only using number of iterations and samples that is polynomial in the approximation error and the description of the game. Further, manages to beat the curse of multi-agent [62]-i.e., its iteration and sample complexity depends on Σx=1 |4] instead of I Adl.
In order to achieve the latter contribution, we acquired convergence guarantees for stochastic projected gradient descent in nonconvex functions when the gradient is Hölder-continuous- notion of continuity weaker than that of Lipschitz. Finally, we contribute general result that guarantees convergence to a saddle-point in functions that are wouconree-hideensstooolyooavvn
1.2 Technical Overview
The problem of computing an approximate Nash equilibrium in an adversarial team Markov game boils down to computing an approximate saddle-point (xx", yy" of the adversary's value function V(x, y); see Definition 2.3. The variables denote the policies of the team, each member of which aims to individually minimize V. Moreover, y denotes the policy of the adversary who aims to maximize V. The equivalence between saddle-points and equilibria is due to (i) the game being zero-sum between the team and the adversary and (ii) the grudient domination property (see Lemma C.7) that holds per player, and has already been established in prior works [3, 68, 114]. In words, gradient domination in our setting implies that any approximate first-order stationary policy is also an upproximate best response for that player.
The problem of computing an approximate saddle-point (a+, y²) of the objective V V(x, y) poses com- putational challenges due to its can compute an approximate saddle-point (ax, , y²) of V, by first obtaining an approximate stationary point x of ((x) = max, V(x, y) through a Moreau envelope argument and then extending it to (x', y²). The proof extendibility uses involved arguments that utilize the Lagrange multipliers of a carefully chosen nonlinear program (for the stationary point x"), while the computation of y requires solving another linear program. It is worth noting that the aforementioned linear program presumes access the full description of the reward function and the transition model of the underlying Markov game when the team plays policy x". This fact prevents the possibility of casting this approach into a learning algorithm.
nonconcave nature. Previous work [65] showed that one
Our proposed (learning) algorithm bypasses the requirement for knowledge of the reward function and the transition model, and works under the bandit feedback framework. The first idea behind our algorithm to consider the adversary's value function as a function F of the adversary's 's state-action visitation measure X, F Fax, A) = (ax, y), and the addition of a regularizing term - S/2 |||] (u can be thought of as small positive scalar). As a result, the max function of the regularized value function,
(<xx)= == maxxeA(a) F (x. A) _ |x]]]_ is differentiable, where A(x) C A S||B] denotes the feasibility set of and depends on æ. Effectively, different policies, x, for the team induce a different single agent Markov decision process for the adversary. The addition of the regularizer allows us to apply Danskin's theorem on function with a unique maximizer circumventing the necessity of solving linear program; one only needs to approach that unique solution. To the best of our knowledge, this is the first work introducing a function of as a regularizing term.
By reformulating the regularized value function using state-action visitation measure A, the problem boils down learning an approximate saddle-point of sannconve--strongyy-oomm coupled constraints. Coupled constraints are a type of constraints that cannot be expressed as Cartesian product (the main well-studied setting in min-max optimization [63]). i.e., the feasibility set A(æ), depends on æ. The first challenge towards handling the coupled constraints is to argue that V Hölder-continuous which a notion of continuity weaker than Lipschitz continuity (see equivalently. VØ" is Hölder-continuous. seems unlikely that we could use Moreau envelope techniques to prove convergence of stochastic projected gradient descent on weakly- function. The next
function with
Definition 2..). Specifically, in Theorem 3.2, we show that 6² (xx) is weakly-smooth,
3

---

step of our proof is to transfer the reakly-smooth nonconvex optimization problem into smooth optimization problem with inexact gradient oracles, extending the techniques from [35] to nonconvex and constrained settings. Since we only allow each player to observe the reward they received and not the action chosen by the other players (including the adversary), one last challenge we have to deal with is the inability to estimate the state-action visitation measure À of the adversary, making the gradient inexact when computing (*"()) in both deterministic and stochastic settings.
Preliminaries
Starting, we will introduce the notation conventions we use and split the rest of the preliminaries into two subsections. Section 2.1 provides necessary definitions whereas Section 2.2 deals with the preliminaries of (adversarial team) Markov games and the notion of Nash equilibrium.
Notation. We denote [n] == m2). We use superscripts denote the (discrete) time index. and subscripts index the players. We use boldface for vectors and matrices; scalars will be denoted by lightface variables. We define || 1/112, || ||,, || so be the f2-norm, the -norm and the foo norm respectively. The simplex of probability vectors supported
finite set A is noted as A (AA). Unless specified otherwise, we denote ll2 by - Diamy denotes the diameter of a compact set in fz-distance. For simplicity in the exposition, dependencies that polynomial in the natural parameters of the problem and O(-) to further hide logarithmic factors; precise statements are given in the Appendix. For the convenience of the reader, comprehensive overview of our notation given in Table 1.
may sometimes use the (-)) notation to suppress
2.1 Basic Definitions and Facts
We commence this subsection by introducing a number of concepts and statements of mathematical analysis and optimization. We define Hölder continuity and the notion of a stationary point in constrained minimization and min-max optimization.
The notion of Hölder continuity of the gradient is weaker notion of Lipschitz gradient continuity. Definition 2.1 (p-Hölder continuous gradient). A function & Rd said have (lp, p)-
Hölder continuous gradient if for every 2, E TRd, holds that:
[[V((z) V S fp12 1065-211p 2'1
When p- 1, we retrieve the definition of an t-smooth function.
Throughout, following standard conventions, we will refer to functions for which the gradient is p-Hölder continuous with a relevant to our work.
weakly-smooth. We state the notions of first-order stationarity
Definition 2.2 (c-FOSP). In the context of the constrained minimization problem minzez d(2), point z E Z is said to be an c-approximate stationary point if.
(-V=0(z), - S, Vz E 2.
Similarly, we will define an e-approximate saddle-point for the constrained min-man max optimization problem min, maxy f(x, y).
Definition 2.3 (e-SP). Let a function X R. point (x, X y is said to be an e-approximate saddle-point (or e-FOSP for the min-max problem) if.
-V,((x (x' x) e, Vw X; (uf(x, v) (y)' - y) S e, Vy E v.
2.2 Adversarial Team Markov Games
An adversarial team Markov game is the Markov game extension normal-form adversarial team games [98]. The game takes place in an infinite-horizon discounted setting where team of identically- interested players compete against one adversarial player, the adversary. We can formally define an adversarial team Markov game tuple I'SS, In + 1], A, B, r, p). where:

---

S is the finite set of states, or state-space, with cardinality S = |S|;
In + 1] is the set of players, with the first n. players belonging to the team and the last one being the adversary;
A Xi= A; is the finite set of the team's joint actions (or, team's action-space), while
A the i-th player's action-space; respectively the adversary's s action-space; further,
A == [ |Ai and B = |B];
r : x B [0, 1] the adversary's reward function;
P: x A + (S) is transition probability function;
7 E [0, is the discount factor;
p E A(S) is the initial state distribution. We assume that is of full-support, p(s) >
0,
Every team player i E [n] gets the same reward and the sum of team players' rewards are equal to the adversary's loss, i.e., Σ Tr(8, a, -r(s, a, b).
2.2.1 Policies, Value Function, and Visitation Measures
In this part, we describe policy classes, the value function, and the state-action visitation measures. All of these notions are indispensable for our analysis.
Policy Definitions. For any agent a stationary policy n. is defined as mapping from any given state to probability distribution over possible actions, where æ. S 3 8 + (T(-1s) E ((A)). A policy n, is described as deterministic when, for any state, it selects a particular action with probability of 1. To simplify, denote the policy spaces for the team and the adversary as 1laam S + ((A) and 1lady + (B)) respectively. Additionally, the combined policy space for all participants can be represented as 11: S + A(A) A(B).
Direct Policy Parametrization. In the context of our work, we assume the strategy of direct policy representation for all players. Specifically, for each player i within the set [n], the policy space X, is defined as ((AA)s, with म; = æ, such that the probability of choosing action equals T (als). By the usual game-theoretic convention, π-; denotes the policy of all agents apart from For the adversary. y set as A(B)S, with Radv = y. so that ye.a = (alvs
state 8, &1,s,as
Having defined policies, we can introduce some standard shortcut notations such as r(s, x, y) = B(aN))(m))) a, b)], and the vectors r(x) E || r(x,y) E RIS| with r(x) = [Ba~a(r(s (r(s, a, b)]l and r(x,y) = [B(a,)))alr(ss a)]] Further, we define P( v) as P(s"ls, a. y) = (a, ( [P8',,, a, and the vector aP,,, e A(S) with P(s. (,s, y) = (B(a,))~<a (P('' a, b)]]
The Value Function. The value function V., for a given state s E S, is defined as the adversary's expected total discounted reward time under combined policy (Tuam: Wadv) from the policy space II, with x = Team being the aggregation policies (TI,.... n.). Formally, this is represented
= Ex.y
Σ Ar an, bn) so h=
where the expected value is calculated over the distribution of trajectories generated by the policies æ and y. If the initial state instead sampled from distribution p. the value function is expressed as Vo y) = Eg- (2, y)].
Visitation Measures. The important quantity of state-action visitation measures, or the expected discounted sum of visitations of a state-action pair.
Definition 2.4 (State-Action Visit. Measure). For any initial distribution p E A(S), transition matrix P,, a team policy æ. and a policy y E Y, we define the station-action visitation measure of the adversary A(y: æ) as follows:
20 7 P(s s. b|., y. y.
p).
A=0
5

---

Where x)) denotes the (s, b)th entry of xyy;
As will further discuss in the appendix (Appendix C.I), the correspondence between y and À is "I-1" for a fixed team policy æ. This property crucial for our contributions.
Reformulation of the Value Function. A key property of the value function Vp, is that it can be rewritten as a concave function of the state-action visitation measure:
Va y)
r(x) (y;;
Definition 2.5 (e-NE). product policy (x',y") X y called an e-approximate Nash equilibrium for when
Vp(=", "(=x","") ) S (0((a,,,= v²) + Vay N, Vi [n];
and
V'(a",," 2 V2p y')
Vy E EV.
2.2.2 The Gradient and Visitation Measure Estimators.
An essential element that led to the development of policy gradient methods is the policy gradient theorem [104]. Notably, it has enabled the design of fiite-sample gradient estimators. This technique fits well into the MARL independent learning protocol [27]. After all agents have proposed their policy, the MDP is acquire batches of trajectories from which all agents will observe the chain's state and their individual reward. These samples are utilized to estimate gradients.
The team agents implement batch version of the REINFORCE CE estimator whose definition is deferred to the Appendix C. As for the estimators that the adversary utilizes, we define the state-action visitation measure estimator and their gradient estimator closely following [113].
Definition 2.6 (State-Action Visitation Measure Estimator).. Let ex,b be the standard basis for the (s, b)th entry. Let = (sg, bo, $1, b1. ... HH-11 ,HH-1.b-1)) denote a trajectory with length H sampled under initial distribution p and policy y We define the estimator for X(y; x) with the trajectory the following
H-1
X(Tly) = Σ
7" Esp, bn.
h=0
By applying policy gradient theorem [104] along with the chain-rule, the gradient estimator for value-function that nonlinear X(y: computed by the following estimator [113].
Definition 2.7 (Gradient Estimator). Let (8o, bu, 81, bi, .8 -1, bH-1) denote trajectory with length H sampled under initial distribution and policy y. Let F(X(y) be the value function of the MDP w.r.t. A(y) and ())))( The estimator for gradient V ((())) using the sampled trajectory T is defined as
u(Tly:
Σ 2h bR) h=0
V log ((b(((sw))
Sufficient Exploration. A standard, while rather naive, technique of bounding the variance of the REINFORCE gradient estimator is using Ç-greedy policy parametrization. Effectively, every action in a player's dispose is played with a probability of at least Ç. For our convenience. we ensure sufficient exploration by a Ç-truncated simplex approach. Moreover, for a given feasibility set X, we denote X to be the (-truncated feasibility set.
Main Results
We present our main results in two different subsections. In Section 3.1 we manage to attain guarantees for convergence to an approximate stationary-point to constrained nonconvex optimization with an stochastic inexact gradient oracle- we do so by extending previous results of [35]. While in Section 3.2, we apply the latter results along with RL techniques in order to design the first learning algorithm that computes Nash equilibrium in ATMGs.

---

3.1 Stochastic Weakly-Smooth Nonconvex Optimization with Inexact Gradients
In this subsection we prove that projected gradient descent with a stohcastic inexact gradient oracle converges to an e-FOSP in nonconvex functions with Hölder continuous gradients. We will use this key result in subsequent sections. We begin by defining the inexact gradient oracle and its stochastic version.
Definition 3.1 (Inexact Gradient Oracle). Let a difserentiable function (0z) and its gradient V (b(2) (2). We call the vector-valued function g(z) a a0000--iii 0-inexact gradient oracle if.
l (z) v=(=)]l S 0, 2z.
Further, given a random variable & in some sample space E, we define a stochastic inexact gradient oracle G: E R2. We assume that the expected value this oracle will be equal a d-inexact gradient oracle g(z). Additionally to being unbiased (with respect to a a d-inexact gradient oracle), we assume its variance be bounded.
Assumption 3.1 (Unbiased and Bounded Variance). For variance parameter x² 0, the gradient oracle G, satisfies
[e = g(z) and Eg (IG((,))-g(z)) s
Following, we consider the simple update rule of Mini-Batch Inexact Stochastic Projected Grudient Descent, with batch size M 0 and g' M ΣØ G (z),6)),
++1 = Projz (z* ng')
(Inexact Stoch-PGD)
We can now state our convergence Theorem for (Inexact Stoch-PGD) whose proof we defer to the appendix.
Theorem 3.1 (Convergence to e-FOSP; Formally in Theorem B.1). Let Z - R be Lipschitz con- tinuous function with (f -Hööder continuous gradient and a desired accuracy c. Also, let a stochas- tic inexact first-order oracle G satisfying Assumption 3.1. The update rule (Inexact Stoch-PGD) 1-p
1+2
with step-size 17 = c iterations.
computes an e-approximate stationary point after T = 0
3.2 Learning Nash Equilibria in Adversarial Team Markov Games
In this subsection we state our contributed Algorithm 1, or ISPNG, which converges to an e-NE for any ATMG, I, with an iteration and sample complexity that scales polynomially with 1/c and the parameters of T. To simply describe the algorithm, the team players initialize their policies and then the following two steps are repeated for T iterations:
1. the adversary approximately maximizes a regularized version of their value function, V (ax, y) = r(x) Ayy: æ) 5 ||( x) using Algorithm and then
2. every agent independently performs gradient descent step on the value function.
During this process, all agents only bandit feedback information in order to estimate the gradients of the value function. We remark that the learning dynamics remain uncoupled. The only instance of communication between agents is the fact that the team and the adversary take turns when updating their policies. During their turn, the adversary approximately best-responds.
Of particular interest is the sub-routine of Algorithm 2, VIS-REG-PG. It is effectively a directly parameterized policy gradient method for an objective function that concave in the state-action visitation measure X(y: x)) [| The objective function is merely the original value func- tion plus quadratic term, |{y; 11? We remind the reader that due to the existence of this introduced regularizer, the utility of the adversary u "' (xx, y) = r(x) v'(y; In order to estimate gradient, the adversary needs to collect a number of trajectories, 7 (sp, bn, .1,..., -H-1, b 8t)), each of length H. Notably, the adversary only uses the empir- ical tate-action visitation measure for the purpose of gradient estimation of the regularized function.
7

---

Algorithm Independent Stochastic Policy-Vested-Grraieen (ISPNG)
Input: Accuracy > 0
1: Based on set stepsize 71. Ta iterations, batch size M, truncation parameter (z. and inner-loop aceuracy Cy > 0.
see Theorem C.3
2: 24 (s,a) a) I (s x A.
> for all agents E [n]]
3: for l 1, 1.2,.... To do
4:
y(1) - VIS-REG-PG((21 eey)
D see Algorithm
5:
9. (1) + REINFORCE xx((11) (1); ;M
> for all agents E [x]
6:
(x( 7T (1) + Projx.= (x.
> for all agents E [n]
7: end for
8: y (T++1)
t- VIS-REG-PG(a2=,.))
9: x² + ((")
> pick the best iterate
10: y + (1++1)
Algorithm 2 Visitation- Reguttii-eR Policy Gradient Algorithm (VIs-REG-PG)
Input: An MDP, joint strategy of the team and desired accuracy >> 0.
1: Based on e, set batch size K, sample traj. length H, stepsize Tyy truncation parameter Sy and see Theorem C.3
regularization coeff. v.
2: y 7 (s. b) + T8 V(,bb) E B.
3: for Epoch 1......, Ty do
4: Independently sample K trajectories, KC(1), of length H under policy (
Σ TEK())
5:
K
ut r(x) (1)
6:
7:
9y
(8)
- K
Σ g(Tly (1; ;u).
D I as in Definition 2.7.
7ER(!
y ((+1) Projseo (g NyyH )
8:
9: end for
3.3 Analyzing Independent Stochastic Policy-Nested-Gradien
Algorithm 1, ISPNG, is instance of nested-loop algorithm. As have already informally stated, ISPNG runs gradient descent on the regularized max function (x(x) maxxe [r(z)T> T - 5 ] for some parameter v. This function has Hölder-continuous gradi- ent and, such, the convergence proof is underpinned by Theorem 3.1. Formally state that: Theorem 3.2 (Grad. Contunuity of Reg-Max Function). function (x) be the maximum muntiin of the regularized value function of an ATMG, with regularization coefficient v >> It is the case that, (i) " is differentiable, (ii) V. th" is (1/2,41/2) (/22, Hööler continuous, iee,
4' (x)
V 4" (T)l S f1/2 | =x'1=
30n (E, with 112
i min, 1())(1-7)+
ISPNG manages to run gradient descent on function d though the agents can never observe the exact gradient of Φ" This is not only due to the randomness of gradient estimators but mainly because they cannot observe the adversary's 's actions and thus do not know the gradient w.r.t the regularizing term. Fortunately, the regularization coefficient plays second role in bounding the inexactness error the gradient estimates. For that reason, parameter v admits a careful tuning.
Finally, the differentiability of hh and the per-player gradient domination property of the V, implies that an e-FSSP x² and the corresponding best-response for the regularized value function, y", constitute an e-NE, leading to the main Theorem of this subsection:
8

---

Theorem 3.3 (Main Result; Formally in Theorem C.3), Given a desired accuracy > 0, Algorithm / outputs joint policy (x" .y" )r for which holds that,
E Vo(x" ,y¹) ofe
min V Vo
Vi e [n]] Se,
and
E max vo "o(",," ,') - V2 y") Se y y'EY
with a
number of
iterations and Ail+ [B], Dm T-7" min, d(s)
number of samples that are By Dm we denote the mismatch coeffi-
poly ( 111,
cient Dm = d=.a
(Definition C.2).
4
Minimax in Nonconvex-Hiidee-Sttongg Concave Functions
Finally, we would state more general result compared to that of Theorem 3.3. We consider the general min-max conconvex-nonconeav optimization problem, milge maXyey fa, y), when an additional structural assumption holds, i.e., when f is mimcoonee-iiddeensttogyyy-oooooo particular, function f admits a reformulation of the form,
In
( [r. u) == (xr c (u;))),
where function H nonconvex stroogg are closed and convex, while ((=;2) y + l4 is an invertible mapping parametrized by æ. Moreover, we will denote ((x)) == {u t c(y: æ), Vy y). We further assume that the mapping e and its inverse are
function defined on X' U. The sets X' and 4
continuous.. Specifically,
Assumption 4.1. For the mapping c and its inverse, c-1, 1, it holds that
|c(y; x) - dly::=')) S Le(l - æ'll + yyy - -'ll),, Va, x' Xiy.y's ey ||e (u; c- c (u':===) s (1|= æ'll 1|u w'll), Vo, x' X; uf u.
If this is the case, the maximizer u² (x) = argmax H (x, u), is Hölder continuous w.r.t. as stated by the following Theorem.
Theorem 4.1 (Formally in Theorem D.2). Let function f(x, y) be noncomex-hiidden-stone concave with a modulus of > O. Let also function be a Lu Lu-Lipschitz continuous and fy- smooth nonconvex nonconve--strongly-eeee strongly-concare reformulation of f with an invertible mapping e efor which Assumption 4.1 holds. Then,
| (x: u² "x'x())l < L, 1 2'112
Va, E X.
where, L, - (t).
Theorem 4.2 (Convergence to an e-SP: Formally in Theorem D.3). Let be a nondonvex-hidden strongly-concave function obeying the same assumptions f in Theorem 4.1 and 0. Further assume a maximization oracle with Ovve²) O(vee)-accuracy) -accuracy. There exists an algorithm that computes an t-approximate saddle-point (x. yy) by making = O ( calls to the maximization oracle. Also, the maximization oracle be implemented by stochastie gradient ascent with iteration complexity T' = yare ), and stepsize By 0()22).
5 Conclusion, Future Work, and Limitations
Conclusions
We expanded stochastic gradient techniques to be able to compute a stationary point constrained optimization nonconvex with weakly-smooth functions. We applied that result to design the first learning algorithm that computes 6-approximate Nash equilibrium in adversarial team Markov games using finite number of samples and iterations that scale polynomially with 1/e and the natural parameters of the game.

---

Future Work We believe that some questions that require further investigation are the following: (i) possible to extend the techniques of [34] establish convergence guarantees of stochastic gradient descent nonconvex functions with Hölder-continuous gradient without batch-sampling of the gradient? (ii) Can we design two-timescale gradient descent-ascen, scheme for ATMGs that converges to Nash equilibrium with best-iterate guarantees? (iii) Can we utilize some variance- reduction techniques to achieve better sample complexity for learning an e-NE in ATMGs?
The main limitations of our work are (i) the notion of independent learning as presented weaker than one presented in [27] 37]-iee, our algorithm has an "inner loop", (ii) the fact that we did not present example for which the function d fails to be smooth; hence, it is unclear if we can prove the smoothness of this function and achieve tighter analysis. The first item can be addressed in future work by developing two-timescal algorithmic approach. As for the second item, remark that even if it is the case that Q" is smooth for ATMGs, our provided convergence rates would be straightforwardly improved without any qualitative modification of the algorithm. Also, would like to highlight that this discussion is related to Remark 2.
Limitations
Acknowledgements
This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program. FK carried over part of the research during an Archimedes Research Internship. IP would like to acknowledge an ICS research award and a startup grant from UCI.
10

---

References
[1] P. Abbeel and A. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, page 1, 2004.
[2] J. Achiam, D. Held, A. Tamar, and P. Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22-31. PMLR, 2017.
[3] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-766 2021.
[4] E. Altman. Constrained Markov decision processes. Routledge, 2021.
[5] Q. Bai, A. S. Bedi, M. Agarwal, A. Koppel, and V. Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3682-3689, 2022.
[6] A. Bakhtin, N. Brown, E. Dinan, G. Farina, C. Flaherty, D. Fried, A. Goff, J. Gray, H. Hu, et al. Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science, 37866624):1067-0072 2022.
[7] N. Basilico, A. Celli, G. D. Nittis, and N. Gatti. Team- maxmin equilibrium: Efficiency bounds and algorithms. In S. Singh and S. Markovitch, editors, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, pages 356-362. AAAI Press, 2017.
[8] P. Bernhard and A. Rapaport. On a theorem of danskin with an application to a theorem of von neumann-sion. Nonlinear Analysis: Theory, Methods & Applications, 24(8):1163-115) 1181, 1995.
[9] L. Bisi, I. Sabbioni, E. Vittori, M. Papini, and M. Restelli. Risk-averse trust region optimization for reward-volatility reduction. arXiv preprint arXiv: 19t.0339229993 2019.
[10] J. Bolte, T. P. Nguyen, J. Peypouquet, and B. Suter. From error bounds to the complexity of first-order descent methods for convex functions, 2016
[11] C. Borgs, J. T. Chayes, N. Immorlica, A. Kalai, V. S. Mirrokni, and C. H. Papadimitriou. The myth of the folk theorem. Games Econ. Behav, 70(1):34-43, 2010.
[12] M. Bowling, N. Burch, M. Johanson, and O. Tammelin. Heads-up limit hold'en em poker is solved. Science, 347(6218):145-11)) 2015.
[13] K. Brantley, M. Dudik, T. Lykouris, S. Miryoosefi, M. Simchowitz, A. Slivkins, and W. Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. Ad- vances in Neural Information Processing Systems, 33:16315-16326 2020.
[14] N. Brown, A. Bakhtin, A. Lerer, and Q Gong. Combining deep reinforcement learning and search for Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
information games. In Advances in Neural Information Processing
[15] N. Brown and T. Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
[16] N. Brown and T. Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456):885- 890, 2019.
[17] Y. Cai, H. Luo, C.-Y. Wei, and W. Zheng. Uncoupled and convergent learning in two-player pero-sum markov games. In ICML 2023 Workshop The Many Facets of Preference- Bassd Learning, 2023.
[18] Y. Cai, A. Oikonomou, and W. Zheng. fimite-time last-iterate convergence for learning in multi-player games. In S. Koyejo, S. Mohamed, Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.

---

[19] V. Campos, A. Trott, C. Xiong, R. Socher, X. Giró-i Nieto, and J. Torres Explore, discover and learn: Unsupervised discovery of state-covering skills. In International Conference on Machine Learning, pages 1317-1327. PMLR, 2020.
[20] L. Carminati, F. Cacciamani, M. Ciccone, and N. Gatti. A marriage between adversarial team games and 2-player games: Enabling abstractions, no-regret learning, and subgame solving. In International Conference on Machine Learning. ICMI. 2022, volume 162 Proceedings of Machine Learning Research, pages 2638-2633 PMLR, 2022.
[21] Celli and N. Gatti. Computational results for extensive-form adversarial team games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[22] S. Cen, Y. Wei, and 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, pages 27952- 27964, 2021.
[23] Chen, Q. Zhang, and 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.
[24] X. Chen, X. Deng, and S. Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3):1:11-14:57, 2009.
[25] Y. Chow, A. Tamar, S. Mannor, and M. Pavone. Risk-sensitive and robust decision-makinn ovar optimization approach. Advances neural information processing systems, 28, 2015.
[26] F. C. Chu and J. Y. Halpern. On the np-completeness of finding an optimal strategy in games with common payoffs. Int. J. Game Theory, 30(1):99-106, 2001.
[27] C. Daskalakis, D. J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540, 2020.
[28] Daskalakis, W. Goldberg, and C. H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM J. Comput., 39(1):195-25)) 2599, 2009.
[29] Daskalakis, N. Golowich, and K. Zhang. The complexity of markov equilibrium in stochastic games. CoRR, abs/2204.03991, 2022.
[30] C. Daskalakis, A. Iyas, V. Syrgkanis. and H. Zeng. Training gans with optimism. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018
[31] C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In S. Bengio, H. M. Wallach, Larochelle, Grauman, N. -isa-hianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 9256-9266, 2018
[32] Daskalakis and Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In A. Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego California, USA, volume 124 of L.Ples, pages 27:1-27:16 Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2019.
[33] Daskalakis, S. Skoulakis, and M. Zampetakis. The complexity of constrained min-max optimization. In S. Khuller and V. V. Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1466-1478. ACM, 2021.
[34] D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal Optimization, 29(1)2007-239, 2019.
12

---

[35] O. Devolder, F. Glineur, and Y. Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2014.
[36] J. Diakonikolas, C. Daskalakis, and M. Jordan, Efficient methods for structured nonconvex- nonconcave min-max optimization, 2021.
[37] D. Ding, C.-Y. Wei, K. Zhang, and M. R. Jovanović. Independent policy gradient for large- scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. arXiv preprint arXiv:2202004129 2022.
[38] D. Drusvyatskiy and A. S. Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 43(3):919 948, 2018
[39] S. Emmons, C. Oesterheld, A. Critch, V. Conitzer, and S. Russell. For learning 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, pages 5924 5943. PMLR, 2022.
[40] L. Erez, T. Lancewicki, U. Sherman, T. Koren, and Y. Mansour. Regret minimization and convergence to equilibria in general-sum markov games. In International Conference Muchine Learning, pages 9343-9373, PMLR, 2023.
[41] B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine. Diversity is all you need: Learning skills without reward function. arXiv preprint 4rXiv:1802.06077 2018.
[42] G. Farina, A. Celli, N. Gatti, and T. Sandholm. Ex ante coordination and collusion in zero-sum multi-player extensive-form games. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, pages 9661-9671, 2018.
[43] I. Fatkhullin, N. He, and Y. Hu. Stochastic optimization under hidden convexity, 2023.
[44] T. Fiez, I.. Ratliff, F. Mazumdar, E. Faulkner, and A. Narang. Global convergence to local minmax equilibrium in classes of nonconvex zero-sum games. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 29049-29063. Curran Associates, Inc., 2021.
[45] L. Flokas, E.-V. Vlatakis Vlatakis-Gkaragkeee Gkaragkounis, and G. Piliouras. Solving min-max optimization with hidden structure via gradient descent ascent, 2021.
[46] Fox, S. M. McAleer, W. Overman, and Panageas. Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statisties, AISTATS 2022, volume 151 of Proceedings of Machine Learning Research, pages 4414 4425. PMLR, 2022.
[47] J. Garcia and F. Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
[48] U. Ghai, 7. Lu, and F. Hazan. Non-convex online learning via algorithmic equivalence. Advances in Neural Information Processing Systems, 35:22161-22172, 2022.
[49] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[50] I. Goodfellow, Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 1rXiv:1412.6572, 2014.
[51] E. Gorbunov, A. B. Taylor, and G. Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities.
Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NewrIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
13

---

[52] K. Gregor, D. J. Rezende, and D. Wierstra, Variational intrinsic control. arXiv preprint arXiv:1611.0757,, 2016.
[53] T. Groves. Incentives in teams. Econometrica, 41(4))617-631, 1973.
[54] K. A. Hansen, T. D. Hansen, P. B. Miltersen, and T. B. Sørensen. Approximability and parameterized complexity of minmax values. In International Workshop on Internet and Network Economics, pages 684 695. Springer, 2008.
[55] S. Hansen, W. Dabney, A. Barreto, T. Van de Wiele, D. Warde-Farley, and V. Mnih. Fast task inference with variational intrinsic successor features. arXiv preprint 1xXiv:9906005030 2019.
[56] S. Hart and A. Mas-Colell Uncoupled dynamics do not lead to nash equilibrium. American Economic Review, 93(5):1830-188 1836, 2003.
[57] E. Hazan, Kakade, K. Singh, and Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681-2691. PMLR, 2019.
[58] S. He, Y. Jiang, H. Zhang, Shao, and X. Ji. Wasserstein unsupervised reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6884-6892, 2022.
[59] Y.C.. Ho and K.-C. Chu. Team decision theory and information structures in optimal control problems-per part i. IEEE Transactions on Automatic Control, 17(1):15-2) 1972.
[60] J. Hu and M. P. Wellman. Multiagent reinforcement learning: Theoretical framework and an algorithm. In Proceedings of the Fifteenth International Conference on Machine Learning, ICML '8, page 242-250, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc.
[61] J. Hu and M. Wellman. Nash q-learning for general-sum stochastic games. Mach. Learn. Res., 4:1039-1069, 2003.
[62] C. Jin, Q. Liu, Y. Wang, and T. Yu. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint 0rXiv:2110.14553 2021.
[63] C. Jin, P. Netrapalli, and M. Jordan. What is local optimality in nonconvex-noncconcave minimax optimization? In International Conference on Machine Learning, pages 4889. PMLR, 2020.
[64] Y. Jin, V. Muthukumar, and A. Sidford. The complexity of anfinite-horizon general-sum stochastic games, arXiv preprint wxXiv:2204.04166, 2022.
[65] F. Kalogiannis, Anagnostides, I. Panageas, E.-V. Vlatakis Vlatakis-Gkaragee Gkaragkounis, V. Chatziafratis, and S. A. Stavroulakis. Efficiently computing nash equilibria in adversarial team markov games. The Eleventh International Conference on Learning Representations, 2023.
[66] F. Kalogiannis, E.-V. Vlatakis- GaaaaiiunGKaaaa.uuniii.. and I. Panageas. Teamwork makes von neumann work: Min-max optimization two-team zero-sum games. ICLR, 2023.
[67] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and moximal-gradionn methods under the tojjak-tojasiewizz condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pages 795-811 811.811. Springer, 2016.
[68] S. Leonardos, W. Overman, I. Panageas, and G. Piliouras. Global convergence of multi-agent policy gradient markov potential games. arXiv preprint arXiv:2 006691966.........1....1111... 2021.
[69] Q. Lin, Z. Lu, and L. Xiao. An accelerated proximal coordinate gradient method. Advances in Neural Information Processing Systems, 27, 2014.
[70] T. Lin, C. Jin, and Jordan. On gradient descent ascent for nonconvex-concave minimax problems, In International Conference Machine Learning, pages 6083-609) PMLR, 2020.
14

---

[71] M. L. Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[72] H. Liu and P. Abbeel. Aps: Active pretraining with successor features. In International Conference on Machine Learning, pages 6736-6747. PMLR, 2021.
[73] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:/706.06083, 2017.
[74] C. Maheshwari, M. Wu, D. Pai, and Sastry. Independent and decentralized learning in markov potential games, 2022.
[75] J. Marschak. Elements for theory of teams. Management Science, 1(2):127-137, 1955.
[76] P. Mertikopoulos, B. Lecouat. Zenati, C. Foo, V. Chandrasckhar. and G. Piliouras. Optimistic mirror descent in saddle-poin problems: Going the extra (gradient) mile. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[77] A. Mladenovie, I. Sakos, G. Gidel, and G. Piliouras. Generalized natural gradient flows in hidden convex-concave games and gans. In International Conference on Learning Representa- tions, 2021.
[78] A. Mokhtari, A. E. Ozdaglar, and Pattathil. A unified analysis extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In S. Chiappa and R. Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statisties, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 1497-1507. PMLR, 2020.
[79] M. Moravčík, M. Schmid, N. Burch, V. Lisy, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508 513, 2017.
[80] M. Mutti, R. De Santi, P. De Bartolomeis, and M. Restelli. Challenging common assumptions in convex reinforcement learning. Advances in Neural Information Processing Systems, 35:4489-4502, 2022.
[81] A. Nemirovski. Prox-mose Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[82] Y. Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming, 152(1):381 404, 2015.
[83] M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn. Solving a class of non- convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
[84] K. A. Oikonomidis, F. Laude, P. Latafat, A. Themelis, and P. Patrinos. Adaptive proximal gradient methods are universal without approximation. arXiv preprint arXhv:2402.06271, 2024.
[85] F. Orabona. Normalized gradients for all. arXiv preprint arXiv:2308. 002088.552111.. 2023.
[86] J. Perolat, B. de Vylder, D. Hennes, E. Tarassov, F. Strub, V. de Boer, P. Muller, J. T. Connor, N. Burch, T. Anthony, S. McAleer, R. Elie, S. H. Cen, Z. Wang, A. Gruslys, A. Malysheva, M. Khan, S. Ozair, F. Timbers, T. Pohlen, T. Eccles, M. Rowland, M. Lanctot, J.-B. Lespiau, B. Piot, S. Omidshafiei, E. Lockhart, L.. Sifre, N. Beauguerlange, R. Munos, D. Silver, S. Singh, D. Hassabis, and K. Tuyls. Mastering the game of stratego with model-free multiagent reinforcement learning. 2022.
[87] M. Piccione and A. Rubinstein. On the interpretation of decision problems with imperfect recall. Games and Economic Behavior, 20(1):3-24 1997.
15

---

[88] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley Sons, 2014.
[89] R. Radner. Team Decision Problems. The Annals of Mathematical Statistics, 33(3):857 - -81,, 1962.
[90] I. Sakos, E.-V. Vlatakis- Gaarakkiik, Mertikopoulos, and G. Piliouras. Exploiting hidden structures in non-convex games for convergence to nash equilibrium. Advances in Neural Information Processing Systems, 36, 2024.
[91] M. Sayin, K. Zhang, D. Leslie, T. Basar, and A. Ozdaglar. Decentralized q-learning in zero- markov games. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 18320-18334, Curran Associates, Inc., 2021.
[92] M. O. Sayin, Parise, and A. Ozdaglar. Fictitious play in zero-sum stochastic games. arXiv preprint arXiv:2010.04223, 2020.
[93] J. Schulman, S. Levine, P. Abbeel, M. I. Jordan, and P. Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 1889-1897. JMLR.org. 2015.
[94] L. Schulman and U. V. Vazirani. The duality gap for two-team zero-sum games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl- Leibniz-Zentruu fuer Informatik, 2017.
[95] L. Shapley. Stochastic games. Proceedings the national academy of sciences, 39(10):0095 100, 1953.
[96] A. Sharma, S. Gu, S. Levine, V. Kumar, and K. Hausman. Dynamics-aware unsupervised discovery of skills. arXiv preprint arXiv:1907.01657, 2019.
[97] D. Silver, J. Schrittwieser, K. Simonyan, Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap. F. Hui, L. Sifre, G. van den Driessche, T. Graepel, and D. Hassabis. Mastering the game of go without human knowledge. Nat.,
35047676):354-55, 2017.
[98] B. V. Stengel and D. Koller. Team- Team-maxmin equilibria. Games and Economic Behavior, 21(1-2):309-3 321, 1997.
[99] Tamar, Y. Chow, M. Ghavamzadeh, and Mannor. Policy gradient for coherent risk measures. Advances in neural information processing systems, 28, 2015.
[100] A. Tamar and S. Mannor. Variance adjusted actor critic algorithms. arXiv preprint 3rXiv:1310.3697, 2013.
[101] O. Vinyals, 1. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, Powell, T. Ewalds, P. Georgiev, J. Oh, D. Horgan, M. Kroiss, Danihelka, A. Huang, L. Sifre, T. Cai, J. P. Agapiou, M. Jaderberg, A. S. Vezhnevets. R. Leblond, T. Pohlen, V. Dalibard, Budden, Y. Sulsky, J. Molloy, T. Paine, Ç. Gülçchre. Z. Wang. T. Pfaff, Y. Wu, R. Ring. D. Yogatama, D. Wünsch, K. McKinney. O. Smith, T. Schaul, T. P. Lillicrap, Kavukcuoglu, D. Hassabis, C. Apps, and D. Silver. Grandmaster level in starcraft using multi-agent reinforcement learning. Nat., 575(7782)350-354 2019.
[102] J. von Neumann and O. Morgenstem. Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition). Princeton University Press, 2007.
[103] C.-Y. Wei, C.W.. Lee, M. Zhang, and H. Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. M. Belkin and S. Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4259-4299, PMLR, 15-19 Aug 1.21.
16

---

[104] J. Williams, Simple statistical coadieet-followingg algorithms for connectionist reinforcement learning. Machine learning. 8:229-256, 1992.
comnectionsstreifforeemmn
[105] J. Yang, N. Kiyavash, and N. He. Global convergence and variance-reduced optimization for class of nonconvex-nonconcave minimax problems. arXiv preprint arXiv:2002. 09621, 2020.
[106] M. Yashtini. On the global convergence rate of the gradient descent method for functions with hölder continuous gradients. Optimization letters, 10:1361-1370, 2016.
[107] T. Yu, Y. Tian, J. Zhang, and S. Sra. Provably efficient algorithms for multi-objective com- petitive rl. In International Conference on Machine Learning, pages 12167-12176. PMLR, 2021.
[108] T. Zahavy, B. O' O'Donoghue, G. Desjardins, and S. Singh. Reward is enough for convex mdps. Advances in Neural Information Processing Systems, 14:25746-257599 2021.
[109] T. Zahavy, Schroecker, Behbahani, K. Baumli, S. Flennerhag, S. Hou, and S. Singh. Discovering policies with domino: Diversity optimization maintaining near optimality. arXiv preprint 22X::2205..3521,, 2022.
[110] B. H. Zhang, G. Farina, and T. Sandholm. Team belief DAG form: A concise representation for team-correlated game-theoretic decision making. CoRR, abs/2202.00789, 2022.
[111] B. H. Zhang and T. Sandholm. Team correlated equilibria in zero-sum extensive-form games via tree decompositions. CoRR, abs/2109.05284, 2021.
[112] J. Zhang. A. Koppel, A. S. Bedi, C. Szepesvari, and M. Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances Neural Information Processing Systems, 33:4572-44455
2020.
[113] J. Zhang, C. Ni, C. Szepesvari, M. Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Neural Information Processing Systems, 34:2228-222 22440, 2021.
[114] R. Zhang, Z. Ren, and N. Li. Gradient play in stochastic games: stationary points, convergence, and sample complexity. arXiv preprint arXiv:2 20t::2006.0098, 2021.
[115] S. 5.Zhang, B. Liu, and S. Whiteson. Mean-variance policy iteration for aver-averse reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11905-10913, 2021.
[116] Y. Zhang and B. An. Computing team-maxmin equilibria in zero-sum multiplayer extensive- form games. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pages 1318-2325, AAAI Press, 2020.
[117] Y. Zhang and B. An. Converging team-maxmin equilibria in zero-sum multiplayer games. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, volume 119 of Proceedings of Machine Learning Research, pages 11033-1 11043. PMLR, 2020.
17

---

Appendix
Table of Contents
A Further Related Work
18
A.1 Team Games
18
A.2 Reinforeement Learning
19
A.3 Optimization
19
B Nonconvex Weakly-Smooth Constrained Optimization
20
B.1 Auxiliary Lemmas
20
B.2 Stochastic PGD with Inexact Gradients
21
C Adversarial Team Markov Games
25
Further Background on Markov Decision Processes
27
C.2 Auxiliary Lemmas
30
Continuity the maximizers
31
C,4 Analysis of ISPNG: Proof of Theorem 3.3
34
Visitation Regullrizee Policy Gradient Analysis
37
C.6 Regarding the Gradient and Visitation Estimators
42
D Noncoures HiideerssrongyyyCoCee Optimization
51
A Further Related Work
We accommodate this section to mention brief collection of related literature in the fields of team games, reinforcement learning, and optimization. The literature is vast and we can only manage to mention some representative works.
A.1 Team Games
Research team games has been major focus in economic and group decision theory for decades [75, 53, 89, 59]. A key modern reference [98], which introduced the team-maxmin equilibrium (TME) for normal-form games, where the team's strategy maximizes their minimal expected payoff against any adversary response. Despite their optimality. TMEs are computationally intractable even for 3-player team games [54, 11]. Recently, practical algorithms have been developed for multiplayer games [117, 116, 7]. Team equilibria are also relevant to two-player zero-sum games with imperfect recall [87].
Due to TME's intractability, TMECor, a relaxed equilibrium concept involving a correlation device, has been studied [42, 21, 117. 1 111, 110, 20J. ТMECor permits correlated strategies but can be impractical in certain scenarios [98]. TMECor is also NP-hard for imperfect-informaate extensive- form games (EFGs) [26], although fixed-panc sacelpparametee-tactaaleeee (FPT) algorithms have been developed for specific EFG classes [111, 110].
The computational aspects of standard Nash equilibrium (NE) in adversarial team games are not well-understood, even in normal-form games. Von Neumann's minimax theorem [102] does not apply to team games, rendering traditional methods ineffective. [94] characterized the duality gap between teams, while [66] was shown that standard no-regret learning dynamics, such as gradient descent and optimistic Hedge, may fail to converge to mixed NE in binary-action adversarial team games.
18

---

A.2 Reinforcement Learning
Multiagent RL Nash equilibrium computation has been central in multiagent RL.. Notable algo- rithms, such as Nash-Q [60, 61]. guarantee convergence to Nash equilibria only under strict game conditions. The behavior of independent policy gradient methods [93] remains poorly understood. The impossibility result by the authors of [56] precludes universal convergence to Nash equilibria even in normal-form games, aligning with the computational intractability (PPAD-compllteness) of Nash equilibria in two-player general-sum games [28, 24]. Surprisingly, recent work shows similar hardness in turn-based stochastic games, making (stationary) CCEs intractable [29, 64].
Thus, research has focused on specific game classes, like Markov potential games [68, 37. 1 23, 74, 46] or two-player zero-sum Markov games [27, 103, 91, 22, 92]. As noted, adversarial Markov team games can unify and extend these settings. Identifying multi-agent settings where Nash equilibria are efficiently computable is key open problem (see, e.g., [27]). Recent guarantees for convergence to Nash equilibria have been found in symmetric games, including symmetric team games [39]. Additionally, weaker solution concepts, relaxing either Markovian stationarity properties, have gained attention [29, 62].
Convex RL Maximizing value function regularized by term that is strongly-concnt with respect to the state-action visitation measure is an instance of a convex RL. problem. In that sense, our work is also related to that strain of literature. Convex RL [108, 1 112] is framework that generalizes standard MDP problems by considering the optimization of an objective function that is convex (or concave) in the state (or state-action) visitation measures that the agent's policies induce. The value function of standard RL has an objective function linear to that measure. Common well-known problems that are unified below the lens of convex are (i) agent maximizes the entropy of the state visitation measure, (ii) imitation learning [1], where an agent minimizes the distance of the state visitation measure their policy induces and the one induced by an expert. (iii) risk-averse RL [47] where the agent optimizes an objective function that is sensitive
RL [57], where the
to the tail behavior of the agent and not merely their expected behavior [100, 99, 25, 9, 115, 80], (iv) constrained RL [4], where an agent optimizes their value function while making sure to satisfy a number of constraints that are dependent on their state-action visitation measure [5, 107, 13, 2]. (v) diverse skills discovery, where the goal is to drive learning agents to acquire a diverse set of emergent skills [19, 41, 52, 55, 58, 72, 96, 109].
A.3 Optimization
Min-max Optimization Min-max optimization studies problems of the form mingex maxyey f(x, When the objective function is convex in æ and concave in y. the corresponding variational inequality (VI) is monotone, and a wide range of algorithms have been proposed for computing an approximate saddle-point see, e.g., [81, 69].
is also known that standard Gradient Descent/ Pexcent/Ascent Ascent (GDA) exhibits time-averaged convergence while the actual trajectory of iterates might cycle [30, 31]. Methods like Extra Gradient or techniques such as optimism are used to ensure convergence [30, 31, 32, 76, 78, 18, 51].
For more general objectives, we know how to compute approximate saddle-points when the weak Minty Property is satisfied [36] and for functions where one (or both) side satisfies the Pl.condition [83, 44, 105]. On the negative side, we know that the problem in its full generality (nonconvex- nonconcave landscape with coupled linear constraints) computationally intractable [33].
Chndeen-Covvxx Optimization This nascent field of optimization [43, 48] considers nonconvex objectives that can be reformulated, through a change of variables, into a convex objective. Further, in the context of game theory, the notion of coddenn-monotoiinn has made its appearance in [45] and the subsequent works [77, 90].
Weakly-Smooth Optimization The majority of references that we encounter for weakly-smoode minimization assume convexity and concern the unconstrained setting. We mention the important references of [35, 82] while also more recent works [106, 85, 84].
19

---

B Nonconvex Weakly-Smooth Constrained Optimization
In this section we prove that stochastic projected gradient descent with an stochastic inexact oracle converges to an e-FOSP in functions with Hölder continuous gradient. We complement this section with the proof of folklore lemmas of constrained optimization that show that the "gradient mapping" (Definition B. is appropriate surrogate of stationarity also for the family of functions we consider. Definition B.1 (Gradient Mapping). We define the gradient mapping and stochastic gradient mapping, Ty and fy to be:
r (2) 1 (2 -rooj (z (1 179 (z))), with shorthand notation, r/ = r,,(2)
7
(z) = 1 7
(zPoj (z ( (z)()))), similarly. F. = fz)(2)
B.1 Auxiliary Lemmas
In general, demonstrating that the gradient mapping is an adequate surrogate of stationarity in differentiable constraint optimization relies on the Lipschitz continuity of the function. We make sure that this is the case when the gradient is only Hölder continuous with p < 1.
Lemma B.1 (Inexact-Gradien) Mapping as a Stationarity Surrogate). If ||r,, & e for some E Z, it holds that:
< (-Vo(zt),z' zt) S S0+ + Eypee
max 2'E2, ||s
where = Projz (z (z)).
Proof. In (Inexact Stoch-PGD), (lg(z) vo(z)]l s 0, Vz E Z. Since xt = Projz - -ng(2)), it holds that
2 argmin z'ez
{112- (z -=g()))1
Due to the optimality condition, we have
1 g(2)) E eNz(2*), x2 (
where (z) is the normal cone of 2 at 2, N2(2)= = [0l 2' -2) S 20,22' E 2}. From the latter, we can conclude that
+ 17
VØ(z)
- (-Vo(z + +((2)) E NZ(x*)
17
E EN2(xt) + +B ())
17
xt + Vo(z))
1 ( NN(22t) +B (0)
Vo(zt)- - x 2 Vo(())
(1)
1
17
"
Now, we bound
|zt - x + 1 [o(z) - 1 /V((zt)
z - z + 1 -v(2z) - 1 - S
1 - =|| V(((2= - vo(2+)]|
1 = + Lg 1 z =1?
t p.
S +
1
Therefore we have
vo(z+) E N2(x*) + B + n2= N2( lopPeP)
The latter display implies the statement of the lemma.
20

---

We immediately have the following corollary,
Corollary B.1. For any 2 E Z, denote z == -Projz (= (z-ng(z)). E [|,,, S
implies that
E
max x''2 + (-Vo(z)), x*)
S n/ EpTPe..
B.2 Stochastic PGD with Inexact Gradients
The folklore proof of gradient descent for nonconvex functions relies on the Lipschitz continuity of the gradient to prove convergence Lipschitz continuous but continuous in the weaker notion of Hölder continuity implies the following fact that we will eventually use prove a "descent lemma".
first-order stationary point. When the gradient are not
Fact B.I. Let function Φ Z + with (p, (p, &p)-Hölder continuous gradient. Then, it is the case that for all 2, z',
lp 1 1+
10(z') - 0(=) (VS(=), z)1 S ||= =11
Following [35], we discuss functions with Hölder-continuous gradient (see Definition 2.1) through the framework of inexact oracle. We show that the answer (ø(z), Vo(=)) of an exact oracle for nonconvex function satisfying Hölder gradient continuity can be translated into some "inexact" information for smooth function. Parameters 6, l' in Proposition B.1 can treated as "inexactness" parameters and will be chosen appropriate parameters of the exponent of Hölder continuity.
Proposition B.1. For given 8, lp. and a tuning of l'
it holds that for any x, x',
&p ||x 2'1| 1'11ttp
x x' 5.
1 p
2
Proof. We let = || x'|l.
By choosing the optimal l'' we verify that
max x
{ lp 1t0 -8x -6x = lp
Epp
p
Le
p
ITP
11+p"
26
p
8 i+p
L- T#F
Where in the inequality we use the fact that
1-p 2[T+p)
< for 0 S p S 1. Setting
yields the desired inequality.
Now, we can use Proposition B.1 as in place of the "descent-lemma" to Theorem C.3 to prove convergence an c-FOSP.
Theorem B.1. Let ④ Z + R be (p, E Eww-kallly smooth nonconvex function. Further, assume a stochastic inexact gradient oracle 9- Lee, holds that TE. [](()) g(=)] = 0 and
=[]](z) g < at for some g Z + Z" where [|g(z) - V<(=)]l S 9, Vz E Z.
a²
plementing T updates of the form (Inexact Stoch-PGD) using 9 and a stepsize nj = + guarantees that:
T-1
Σ 0
2 <
8e
E ④ (=())=
+
80"
+ 88 tr - + 4
8 8 T
M
postpone the proof state a corollary that might help the reader gain some intuition on how the itcration complexity scales with p.
21

---

Corollary B.2. Let Ø, 9. the update rule of (Inexact Stoch-PGD) as in Theorem B.1, and stepsize " 2 For 1t drawn uniformly random from [L,..., T", it holds that:
88p
E Φ (=')
0²) + 166 tH 8 8 800
180
E
M
where r.j = rg. Furthermore, by setting the parameters as T 2
8 P
Fl
(c(o(=")] x¹) 5 (3)
ie
1 8, and M
9a 22
it is guaranteed that there will exist 1' E {0..... T - 1) such that
Blr,(=") ) Se.
Proof. For the first claim,
x= Projz (2" [g(2"")
E
=
E
17
x Proiz (st - -ng
< 21
1
Projz (2""-118 -ng(=')) - Projz (z" ng(2z"))
+ 2F
$ 2E
[|
27
+ 21E
|1 22" ng(2")) --2" -ng(2())
2E [| 27
|1(22 g( =(="))1? "//
+ 21E
Se (E ( (29) -0")
+ 166, 1 2 8 808
1802
JTFIT
M
Where the last inequality follows from Theorem B.1 and the fact that E [100()) g(x)]| s t. By setting the parameters as in the corollary, we have B(r,(("')) )] $ c.
L
Remark 1. With the same parameters choose in Corollary B.2, Lemma B.1 guarantees that for any p E (0, 1), (2(( is a sufficient surrogate for stationarity. In particular. (z,(z) S implies that
88-
-Vo(zt) E N2(2+)++ + B
+
E
Ep
Finally, we state one more auxiliary claim before proceeding the proof of Theorem C.3.
Claim B.1. Consider an iterate of (Inexact Stoch-PGD), z². Also, define x Projz (z* - -2g(2)). where g is the graadettg oracle. the case that,
|| 2 S 17 M
Proof. The proof follows easily from arguments we have already used,
F
|| 1++
2 + 11²
E |Projz (2* ng"") Projz (2* - "1g')) [1
|lng* - -ng" |1
< E
= E
||g' gf ||
< n7² o²
M
22

---

Proof of Theorem B.1
Proof. Since l1g(z) vo(z)] & 0, from the weakly condition, we have
o (2 S 00(²)) + (V 21 - -z²) +
4p <0(2)) + (4 1t1 =²²)=
|| - x²1 2²112tp
+p
-x'112+ +8
(1)
2
tnm2²
=0xx) + (0 (x')
x²) + (Vo(z') g(x²), 2 2+1 -2²)+ +
||
2
+
2
= =x(²)) - 77 - (774))
1 +
(2)
2
=d(2) 7 - (Vo(22) =(2"),
1n22 +8
2
s <0(2') 7/ ||
+ -
- -g (x) ()) -9())))))))))
1n12 2= +8
+ 2
(3)
< (('') - v ||
+ 17 (g (2') - g (z'), + " [|((== (00(z))-9(11)) 9(21)|| -
" |ill + 1
+ 2
| || +8
(4)
2
11) 877
2/2 2
| + (Ā - (=)),
m/) 7 0 +
(5)
1) 11p
s <0(2')
1
2
+ 17 (g (x*) g (z') r (g (x*) - (z'), r 7 0² + 8.
Where
(1) is because of Proposition B.1;
in (2), we plug-in the definition of A
(3) uses the fact that ((((2'), P4)) S - ||%;
(4) is due to Young's 's inequality;
in (5), we plug-in the error bound on the inexact-gradient oracle |/ Vo(z) - -g(2)]² s 0.
Continuing we have
① (2
nn12
< 0(xx)=
17
|| -1)))))))(()))))))))
- -9) -
2
2
+ 11
002
+
2
2
s 0(2²)
11
||al|| + ((()))))))))))++)(()+)))) (2 + " n + 8.
2
2
2
23

---

Summing for t = .....,T- 1,
11
11 (n
Σ ④ (2')
|| + (g -9 1 (=') .1)) = g (z') (z')
2
2
2 0T 8T.
This is equivalent to
T-1 7 (nn²))
||
2 2
T-1
$ (x0) - o (xT)+ + Σ -g rh) (z)l((z) - g (x))1²)
D0T O8T
+ 2
{ - 6- + Σ
(1 .r)) + 1 (z') g (21) + !7 7
+T. -
2
0=0
Taking expectations, we have
T-1
2
1=0
E ④6 (29)
nB (g (=9) xi)l +n (x') (z') 9 (=9))²)
5T + = 102TT
0²
$ 0 (29) 00 + T + 8T + 7 TTPT.
2
By setting +
1 it holds that 2p
T Σ E 11
88 (E 1 (2º) "Φ")
+
802
+ 88'6 + 402
M
8e, -e E p (z²)] σ²))
80²
88 861+0 _ + 432.
M
This completes the proof.
24

---

C Adversarial Team Markov Games
In this section we the formal proofs of our claims regarding ATMGs. Before proceeding, let us provide roadmap of the current section:
offer a concise summary of our ATMG-related notation. We proceed to present a number of crucial facts regarding MDPs in Appendix C.1. In particular, facts regarding the state-action visitation measure.
Beginning, in Table
In Appendix C.3, demonstrate that the regularized value function has unique maximizer that changes in föölder-continuus way w.r.t. to team policies æ. This leads to the Hölder- continuity of the gradient of the regularized maximum function & (see Theorem C.2).
Having established the latter, in Section 3.2 we invoke the results on gradient descent for nonconvex functions with Hölder continuous gradient to get our main theorem regarding e-NE learning in ATMGs (Theorem C.3).
The tuning of the parameters of Theorem C.3 is supported by (i) Appendix C.5, where we get precise guarantees for maximizing the regularizing value function w.r.t. the adversary's policy (Theorem C.4) (ii) Appendix C.6, where we define and analyze the gradient estimators used by the agents of the MG.
25

---

Table 1: Notation
Parameters of the model:
S
State space
N
Set of players
Reward function of the adversary
Number of players in the team
A
Action space of player of the team Team's 8 joint action space
A
Action space of the adversary
A,
Number of actions available to player i of the team
B
Number of actions available the adversary
X
The set of feasible directly parameterized policies of player i: X; ((A,)
=
x
The set of feasible directly parameterized policies of the team: X =
X i=1 X;
The set feasible directly parameterized policies of the adversary player: = (B)
F(s"ss, a,
Probability transitioning from state to s' under the action profile
(a, b)
F(2,9) y)
The (row-stochastic) transition matrix of Markov chain induced by
(æ, y)
y (s) xr)
Discount factor
The (un-oormalized) state visitation measure for policy (æ, y)
The state-action visitation measure of the adversary when the team is playing policy
V(x, y). (2 y) (x y), o (x,
The value vector per-state, the expected value under initial distribution
The regularized value vector per-state, the expected value under initial distribution p
trajectory of states and joint actions of the Markov game
Estimators:
single estimate of the state-action visitation measure
The estimator of the state-action visitation measure single estimate of the gradient
g
9y
The estimator of the gradient
Parameters:
Ly
Lipschitz constant of the value function Vp('; Smoothness constant of the value function V. (-))) Distribution mismatch coefficient
ly
Dm
Additional notation:
(xx
Maximum of the value function given æ: Φ(x) maxyey Vo y) Maximum of the regularized value function given a: (x(x)
maxyey (x, y)
26

---

C.1 Further Background on Markov Decision Processes
We need additional preliminaries on Markov decision processes (MDPs). Specifically, we will discuss the properties of the (discounted) state and state-action visitation measure. These measures represent the "discounted" expected amount of time the Markov beain-inducet by the players' fixed policies-spend at state 8 (respectively, at state action pair (s. b)) starting from initial state s'. Each visit is weighted by discount factor 7/, where h is the visit time, Notably, in [3] it is defined as probability measure, meaning that for an initial state distribution p. the discounted state visitation distribution sums to I. For convenience, we will use the unnormalized definition from [88, Chapter 6. 6.10], which sums to I-
LL This is why we refer to it as a measure instead of a distribution.
Definition C.1 (State Visit. Measure). Given an initial state distribution p A(S) and a stationary joint policy π E II, we define the state visitation frequency d as follows:
yth P(sh = S|T, = 8).
h=0
Additionally, expanding the definition, we define oi (s) Ezuu [d] (s))
For convenience, the expression dz.' (s) is utilized to represent the state visitation measure resulting from the policies (æ, y) E X x V Fact C.I. Let MDP, M(S. B, IP, r, 7). Let p л E ((B))5), For the corresponding state-action visitation measure X E Sx B
and the state visitation measure di E R$, it holds that,
(T) dz (s),
b), Vs E S, vh E B.
quantity that is important in contemporary RL literature is that of the mismatch coefficient which we formally define here.
Definition C.2 (Distribution Mismatch Coefficient). Let p A(S) be a full-support distribution over states, and II be the joint set of policies. We define the distribution mismatch coefficient D as
d
Dm sup TEll
00
where d= denotes element-wise division.
The following theorem that relates policies and visitation measures is essential analysis. Theorem C.1 (188, Theorem 6.9.1]). Consider an adversarial Markov game and a fixed team policy
(i) Any y E y defines a feusible state-action visitation measure À E TR|S] B1; namely, )x,(y;;)) = Ep(s) Ey (0* P(s()) = s, s,6(0 b x, s()) = 8)
SES
(ii) Any feasible state-action visitation measure X defines a feasible y E Y; namely, X(s,b)
Ms.b ==
EVEB Ms, V(s S B.
Further, for any such y E y it holds that \x,((y: = A(s, v(s,b) E E x B, where A(y: x) is the induced discounted state-action measure.
An implication of the latter theorem is the fact that A(: x) is "1-1" mapping between policies and visitation measures. Following, we see that this mapping is also Lipschizz-comtinuuus and smooth (see Lemmas C.I to C.3).
Lemma C.1. For any initial distribution P E ASS), function V, is L-Lipschitz and Ł-smooth with
Σm [1-7)
[A++IB| and l 2>(%% 7
[1 in other words
A + B
Vo(a,, y) - Vo(w', (('',''''' 1/1l
(( y) (a' y Il: [( y) (a', ,''ll
(1 -7)2
27 (Σ i=1 |A, + [B]]
VVV((2,)) VV,(a y²'ll /
- (1-7)3
27

---

Proof. The proof follows from Lemma 4.4 in [68].
Lemma C.2. Let À E R Si BI be the state-action visitation measure for the adversary, then À is Txx-Lipschitz continuous and Ex-smooth w.r.t policy (z. Specifically, have
| (y: x) -(/:=")) | [, |4 + [B] (1|x x'1l + 1 y'll).
7)
and
2|S 1/2 [ |iil
|B)
VA (3':''')1
(1 x' + ly y
7)3
Proof.
Each As can be considered as value function for the given state and the reward function rrraa, ,b) ( B). Then by applying Lemma C.I, have
Ail + B
De, (y: - As.b (v':
(1 x'1l
+ 11 y'll).
(6)
(1 7)2
27 (2, |A + 1B1)
|V (3) - (y':
(I| x' + 11 y (II
(7)
(1 7)3
From Equation (6) we get
VE, A + B
[x - X3''2x)) 3
(1|= x'1l 11 y/1l).
(1 11-79 7)2
This implies
- S V | (3) A (3/': 1l
v //||B/// E, A + B
(||ar x:'| || + 11 y
(1- ?-
S| (Ex + [B])
(11 x'1l + 11 y ())
71
Similarly, from Equation (7), we have
27 (E, |Ail |B1) (1 7)3
|v (1;
VA. VA,, (3':2')11
[1| x'll e'I1 11 - -/ll)).
Thus
VIS
V Ve (3:x) - Vd.. (3':
max SES
27
B
( |A + (8])
(1|== x'll + 11l - v'll).
Where ||-1|p denotes the Frobenius norm of the matrix. Finally, we have
VA (y: m)
VA (y':
< VV
y
a:)
V (y);
2TV S B
Σ ; [4.1 + [B])
(| x'1l + 11 -'1l)
(1 7)
27v SS| (E Adl + [B])
(|| - x'll + 11 3 I))
(1 (1- 7)3
2 2/151 |S| (E, 1A,1 + 1B))3
(| x'1 + 11 2'1l).
7137)3
28

---

Lemma C.3. Consider Ainv (A(y; == dev(aw))
Σy (u:a)) which is function that maps the adversary's s
state-action visitation measure Xyy x) E ((x:) to the adversary's policy y E y. For any fixed team policy æ. Any is - -Lisschiz continuous with respect À where Lx max p[s[(1-7)'
Specifically, it holds that
y w'll S Aam () x))1;
Proof. Take the partial derivative of Ann((A) we have
θ Aa.
Aa.b
Dds, Ev As,
Ev Ae,
E W )e,or
da.
+
En As,
Ens )oyar)
1
< max .ES
+
p(s))
p(s)(1 -7) $
max .E$ ((s)(1-7)
This implies the Lipschitz L continuity.
The Regularized Value Function.
Lemma C.4. Function V (z. v) = (x. v) - 1 (1:=))1 is Li-Lsschhitz continuous and mm-smooth, where Ly L+ + 2(122 and ly -+ श| + v13.
2
Proof. For Lipschitz continuity, we have
(V v) ""(2,/2) y')l
(V 3) Va(2'' ,y')l + 2
|| - )|
| (y:
V2 3) Vo(2', (o(x')/))= + max 2
V
|| (y: x||| |1 x)) - || (3/3
a.y
(2, y) Vo(x', ,')),"')+
v
2 1 [A ()):z)>>(((::2)) 23/:2²))
L+ VLA
2(1 ) (1 æ x') || + | y v'll).
For smoothness, denote the Jacobian matrix of X 2)) w.r. to (ax by Ja( y), it holds that
Ve (A)))))) V || (3': x1)1 11
(1:0)) JA y) A (3') T J w/))
I A (2: JA(E, 3) x)) T J2 3/)
+ |A(U:)) T Jx(2', y²) (g/: T JA l/)
W A (y: J 3) JA
A (3)) x) > (3/: ||| || y'll
Ja( v) JA + >> mm X X JJx (a' ,y''l
(8)
lx
+ Lx 1x) (1|= x'1 + |1 2 II)
<
1 1-9
29

---

Where in (8) we used the fact that |Ja(2', y')ll - L2. We conclude that
V (2, y) - Vaz yz)ll
VVp(2.y) VVp(2', 8/) +
V A y: x)| V 1 (y''
VVVp(,, y) - VVG(a', w/)ll
V y x)
Vo V
2
vlx
+ vI3
2(1 - -7) 2 (||= z'll + 1- 1l)))
Finally, compute the Lipschitz continuity parameter of the reward vector that already used in our previous claims. Lemma C.S. Let rax) be the reward function for the adversary when the team is playing policy Then it holds that
[r(x)) r(x')l )l| - Ly | æ'11,
where L, v E [A + B).
Proof.
||((x)) - r(('')l S v | ((x) ro00
/ [S||B] max (r(s, xz, b) r(s, x', b)
|S||8] > Aillla æ'll
(9)
$ Vis
Σ 11l+ 1101001100 1100 2'11
Where (9) follows from Claim D.9. in [65].
C.2 Auxiliary Lemmas
Bounding the stationarity error on the truncated simplex. The (-truncated simplex, A is defined a the set of all probability vectors with no entry smaller than ( > 0. More formally, for given dimension m and a 0 S the (-truncated simplex is defined to be
m
A m.
F4
2
C.
34
Lemma C.6. [40, Lemma 15] Let A, be the t-tunncteed m-simplex. If0 S. < n there exists æx A m. such that || æz|| < 25m.
S 2m then for all
Proposition C.1 (Stationarity on the trunc. simplex). Let an L Ly-Lsscctitz continuous differentiable function f m -> R. Also, let an c-approximate stationary point æg when the feasibility set is the truncated simplex A m. such that
(-VS( a - mx) S, Vak m.
Then, xe is an (E + 22mL, ( stationnayy point when the entire simplex is considered, i.e, (- Vf(xx)) x - xx) S + 2CmLy,
Vo E A.
Consider a' E A m. such that x - a'6l s 2Cm, such point exists due Lemma C.6, we have
Proof.
(-Vf(x))) x- -xx) = (- (-V V[(c)) -xx) + (----V (-V)(()). x -x'()
c 2GmL,-
30

---

Where in the last inequality we use the fact that for all a Amis, we have (- (-Vf(az)) 2/ x5c and | (ax))) S L.g-
From stationarity to optimality.
Lemma C.7 (Gradient Domination). Let a single-agent MDP with action-space A and directly- parametrized policy æ E AC (A)) Then it holds that
!s! (AA)
1 Dm max (x' (x'-x) x)) [VVVV((() + 2D 2DmLIs|IALL a'EA((A)18)
(x( V2(2))= =*EA(1))
max
1-7
-
Proof. The proof follows easily from Proposition C.I and the gradient domination property [3. Lemma 4.1].
C.3
Continuity of the maximizers
We begin this section by firstly introducing proposition which we will leverage in Lemma C.8. Proposition C.2. Consider the inequality of the form ax²² S -Xx 7X where À and X are variables and a. 3, y are coefficients. Under the constraints that a, 3, Y, A, X 2 O, there is no solution of the form ex for any finite constant 0.
Proof. Solving the quadratic inequality for À gives:
0 sSsO 8x + Vx Vx(4a) 3²x)
2a
Bx+ xx(10)+8*x)
We search for positive constant such that A <
S CX, or equivalently,
20
1
4ar
3+
32
C.
2a
By observing that when a, B, y are all positive constants and as + 0, + co, we conclude that no such finite constant e exists.
We first define the maximizer for the regularized function r(x) T - ||l Since the function is strongly-coneave A, the maximizing is unique. Specifically we denote
X (x) = argmax (x) T X |
(10)
XE\(z)
Now we are ready to show an important lemma regarding X >*))).
Lemma C.8 (Continuity of the max. of reg. functions). For any adversarial Markov game r, Ax))) defined in (10) is (1/2, I..)- continuous, specifically
(x*(x)) X (æ2)) - L, || x2 1/212/2
where L,
1/4 w1 31/2
SS]
1/2
- A&
|B))
Proof.
Consider team policies, æ1, 22 It holds true for the unique maximizers the adversary's regularized value function that,
of
(r(z1) - -.>))=x>x))) -x1()=)) (A1 A1-A((a xx-x((x11) 0. Ay E A(x1):
(11)
(r(0z) (elzz)->\'ll - (22 (A2 - (x2))) S 0, ayg E A(x2),
where A(x) the set of feasible state-action visitation measures of the adversary given team's policy æ. To bound the distance between the two vectors X >((x)), X (x2). we observe that for any measure
À A(æ1) U A(x2), there exist measure X A(æ1) that shares the same adversary's 'ss policy y as
31

---

in X. It then follows from Lemma C.2 that | - x|| - LA ||| - x2ll. Therefore we have for all
X E A(z1),
- (x))(z)))
= (r(0)) - (x11))) (A-A) (A-A1)
+ (r(#1)) v21()1)) T (π1 -x)(=)
S STAV/SIB (1 (1+1_>) |00 x2l1-
v'
(12)
Where the last inequality follows from (11) and the fact that ||r(z)
1 (x))
1
visiiBi (1 (1x) for any x E N. Similarly, it also holds that for all X A(æ1),
(r(ma)= (222)
(A (xx2) S Lx || B
1 v
|aa - 11211 -
(13)
Plugging in Ā + (32) and Ā + (21) into (12) and (13) respectively
(r(z)) - 1 ((tz))>>>((()))) (x1)) (A'(22) - X (a1)) - LA |
1+
| -2212 ll
1 7
- (zz)) (r(02) - (xX()) (X(=))-X(()) s L
11 1 1-7)
1
|x] x2 ||.
Adding the two inequalities results in
-A (211) ((r(z))- (r(zz)) 12 (x2)) ) (A1(2)) - (xx))
S $2LAV1811 B|
1 I 1 || - x211.
(14)
On the other hand, since r(xx) x - / 21 is v-strongly concave in X, we have for all \ E A(x1).
(A1 xxx))) ((1(z))) - v\1) (r(z1) - (x1)) + w/| - (x111 S 0.
We again use the fact that for every X E X, it holds that there exists X E A(x1) s.t. o 1-1-11 S
L 21 #2|- Therefore it holds that for any X E A,
0 (A - X) (m))) (r(()) - vb +
-
+ + A1 + (A - X) - x²
= -(A (x))) + (AI-A)) T ((f(z)) - + (A- A)) - (r(x1) - (x11))
-A-
+ 21 + -/| - (z=))| +2v (N1 - X,- - -=((x)))
(A - (x11)) ((r(z)) - / + A - 1)) - -r((1) '2 (z1))
| A 1 - || +2 ( -X x==))
+ A1 - x) T ((F(z)) - ~ + ( - x)) (
- -xX(x=)))
Rearranging, we have
A A (x11) T ((F(z))- - -vx) -(r(m))- -xd())))) + + - (xx)))
x v ( (²11)) T (X-
X1)
{| - x122 2v (1 X, - X(x1))
22
A - ())(((((z - vx + v(ā x)) - (r(x1) - VA xa((a)))
We bound Q4, S22, and Z3 separately.
32

---

* For Ω1, since | S Lx x1 I211, we have
Q $ / (Λ - (((a))) ! (A- / X (z11)| 지 X
2v
- i V|S|IBi
LA||E1 - x2/1.
Where we use the fact that | (m) ||
-
X + (a))l and ||||| S ||ll = 1-
1.
For 92 only the second term is possibly non-negative, it holds that
2
P - - Xx=)) Tx 22 - VSsBBB
Resulting in
4v
02 S
Li -22ll-
1 -
For Ωg:
2 S (1 -)) T- (()))))
2v
- "I- B| - x2ll.
Finally, by putting the bounds of f2, 02, P2 and setting 1/
8v
L we have for all
I-7
Xe A,
-X +1| (X (X- xxx))) T ((r(z)) - v + ( 11 Ø2ll. (15)
Concluding, we plug X + (222) in (15), resulting
(A*(22) - (=)))) ((r(z)) - =x²()))) - - -(at))~)>~<x=))) + (1) - X (x1))) 2
I L'|l Ø2
(16)
Adding (14) and (16), we have
2L, B|
1 1+ ( | + - x211
2 (A7(22) - (((1))) ((r(2)) - -VX (r(22) - vx (x²)))
+ +X2(22) (x))) ((r(z))- - =\ =>²(2)) - (r(#)) VX (xx()))) (x2)) (=1))
- (x2) - x²x=)) (r(z)) ~vx")=))) - -(r(2))-AA'(a))) -VA'
Rearranging we get
- ((x))) -X(x)) ((((0))- - (22())) - (r(x)) - V2 v22(222))
-
+ [' 22l1
$ I., (x2)) - X (x11 (x11]|[a> x:2l + I."I x1 a2ll.
where I" 2 1-) L + I' 2+ 10x VISIBBIA
By setting À [xx - Xx ||| and X ||ا| Ezll- we consider the inequality vx2 <
L, + L with coefficients v, Ly. L" > 0 and variables À and x. Choosing a <- v. +- Ly, and 7 < L" then Proposition C.2 implies that X >((x) is not Lipschitz-continuuus w.r. the team policy
3x+ xx+ S cxp, where
x. Hence, we consider a solution of the form 0 S X
2 0.
2a
We choose p 3 since it yields the best convergence rate from Theorem B. Solving the above inequality with p gives that
33

---

if X = 0, the inequality holds trivially;
if X 0, have
3x Vx(4ar + 82xx
BVX
V40y+ B²x
2
2a
2a
Since = ||0| - -22l S Vn / = /n//S,, by plugging in the coefficients, we have
1 c= - 2L2XX + 4vL" < 2(n)
111 7/3/22 /
Σ |Aul +
[
By setting L, = c, we conclude that
|A - X (x2)) < L, || x211'/?
We are now ready to show that (xx)) is weakly-smooth.
Theorem C.2 (Hölder Continuous Max Value Func.). Let function & (x) be the maximum function of the regularized value function, &² (x) == maxyey Vp y). It is the case that,
Th is differentiable,
Vu is (1/2, (1/2,21/2) -Hölder continuous, ie,
V (x)
V
(2'20 &1/22 22111/2
30n (E, with f1/2 umin, p(s)(1
()
Proof. Since (x) has unique maximizer E Aax) by applying Danskin's Theorem [8] and "1-1" correspondence between À and (Theorem C.1), we have
(')) - V t"
V (ax)ll V/ (x))) VaVi y(>(('))))
S l, (I(x x - æ'll + 1 (x)) - (x')il)
S l, (1I x'll + LA | (=
$ e, (2n|5)) & + L L.) || x'11à.
Where in the last inequality used Lemma C.8 and the fact that || =''ll I 2n SS. Plugging in the coefficients in Lemma C.S, Lemma C.3, and Lemma C.4, it yields that
30 (E, +
V V 2 (x')l
min, p(s) - 7) || - 2'1
C.4 Analysis of ISPNG: Proof of Theorem 3.3
In this part we show that Algorithm 1 converges to an c-NE. Essentially, Algorithm implements projected gradient descent on the regularized maximum function &" X R with stochastic d-inexact gradient oracle. Function & is Hölder-continuous (see Theorem C.2) and as such we can invoke Theorem C.3 to prove convergence to e-FOSP.
The inexactness of the gradient oracle, 0, is the sum of two eтrо sources:
1. the fact that the adversary can only approximately maximize the regularized value function p (æt, z) the iteration and sample complexity of maximizing (zx is provided in Theo- rem C.4;
34

---

2. the exact estimation of V requires estimation of the adversary's 's policy as we assume that the agents do not observe each other's actions this impossible. Nevertheless, in Lemma C.9 is proven that the inexactness error is bounded and controlled through the regularizer's coefficient
After quantifying 9 as the function of the latter terms, the optimality gap of Algorithm 2 and term that scales with (v), we can tune the rest of the parameters accordingly.
The resulting c-FOSP, thanks to the gradient domination property (Lemmaa C.7), corresponds to an e-NE.
Bounding the error of the inexact gradient. Following, we prove that the inexactness error of the gradient oracle bounded by a function the controllable parameter v.
Lemma C.9 (Inexact gradient). Let V (x, y) Vo(az y) 5 Σ. (s)(s() v²(x)
argmax, (VP (x. }) and g(x) Vz (x, (z)). Then, it holds that
0|8| (E=z |A.1 + (B1)
ll (..)(,,)))2
(1-7)3
Proof. We observe that
l1g(x)) - V V (a, w)1l = V (-2 |((:))))1)
|1 a)) ||
Where in the last inequality we use the fact that ||||| I - and V2)(y:)) S Lx-
Learning an e-NE. We can now compile the intermediate statements guarantee that ISPNG computes an c-NE for any desired accuracy c > within a finite number of iterations and samples.
Theorem C.3. Consider an adversarial team Markov game and Algorithmm ISPNG, with an outer-loop parameter tuning of:
T 1061683200D n 2 EE (4+++18))
[min, p()))
(min.
7/
33177600.D n 2 D>> (11)))
(1-7)&c
Ca
(D., 14, +1
max (1-s)) (E))) (A.1+18))
.M
(1 (1-7)20(min,, ,(3))a,3
Is
2
Also, let the tuning of the inner-loop subroutine Algorithm 2 (VIS-REG-PG) be:
(1-2)²
v S8D...S1 IA: +
Tr ò
Dd 1S (A.1+18))) (1-7)")mmn, p(a)]=2 -
(122) min, 444
Jly 978447237120D4
(1-7) 1i 2
Sy
1843202 m. S |4.++
K 19365101568D 1S (I 1411
(min, P2
35

---

2293235712 12 LA.1 18.1+180*) (1-7)² p(8))
log
It is the case that the output of the algorithm, (x" y²), will be e-NE in expectation. Specifically, we have
E Vole" ,0))
[ Vola"" yy) Volx0" .30) Se
min m/E2;
Volae x vn))
se,
and
E
max y'Ey
Proof. Let x", y be the final output of the algorithm, from Lemma C.7, we have
E
Vo(=", ,²)
min EiEt;
vo(x( 3²))
2D 1 |Aiil + BB) L
Dm
E
max (- VVp(2*" ,,0a==_,00 ,y") (ar[-x)))
1-9 7
7
$ -
D
max x
(a"' (a) (xr 2;}
+ LxDiamx.
2D
|A + BI) L
+
(17)
1
Where (17) follows from Lemma C.9. As for the first term of (17), let us define y (x) = yrgmaxyey Vp (2x y) and x = Projx (x*
(xt-11_ The VV (x" (x')-))) Then it holds that,
E max { (-
(x" y²)) (a. -m:)]
E
max xx
(-VV
(x+))) (ar) x²))
+VVV
VV (2=" yy")) (ar! - ae{-=a)]
VV
(ad x2))} + L, |||05 x0.
max !!
[||
V
(z
VV" 34 ||] Diamx,
(18)
< max
(-
(of - x x + LuIE || - x1||]
ly
[E
||| ||
x= + E
||]) Diamx:
(19)
E max
(-VV% (w. 
(of x }}}}} T.y [||a mill]
x!!
ly EE || x² ||] + (x= (x E (1le y" III) Diamx;-
Where
Equation (18) is due || (x. v) < Lw;
Equation (19) follows from the fact that (a y) is e, smooth.
36

---

By choosing parameters specified above and combining Corollaries B.1 and B.2, Theorem C.4, Lemma C.12, and Claim B.I, we have the desired result. On the other hand, since
E max V0(=", 3²) Vo(x", 33) D'EN
= E
max (2 y') Ve veee")") y'Ey
+ (1 71-
v
E V y (x=)) V (2", yy))
+ 1
(20)
-7)²
v
I b yy (x") y 71-
Where in (20) we use the fact that || < (1-7)2 Combining Theorem C.4, Lemma C.12, and choosing parameters specified above gives the desired result.
C,5 Eistation-Regularizze Policy Gradient Analysis
In this section, we consider the direct parameterization for the policy of the adversary. For any policy E V, for any state & E S and any action b E B, we have
y(bls) V/,b-
Where Vs.b denotes (s, b)th entry of the policy vector y. In this section, we mainly focus solving the following policy optimization problem:
max V (z. y) max {r(=) X(y
(21)
yEyE
Where X(y; x) is the state-action visitation measure under policy y in Definition 2.4. r(x)) is the induced pay-off vector for the adversary when the team is playing according to strategy x and v is the regularization coefficient. Then by policy gradient theorem [113], denote F* (>(y: x)) Vp (z, y)
we have
V F x)) x)) (r(x)) x)(
8
V log ((6hlsm)) )
Ep.y
Σ
hh (r(x) v)(y:
Given the direct parameterization, we can show the following lemmas: Lemma C.10. For any adversarial policy y and state-action pair (s, b), we have V log u(bss)] 1 t. [[V log (bbss)] < 2 and v (A(y: x))| S (1-1) + (1->) for any fixed æ.
Proof. By direct parameterization y(bls) Vs.b, we have
| y log (b) = V y log Vo,cll
= Ca.b
(22)
Yo,b S"
Where es,b denotes the standard basis for the (s. b)th entry. Similarly, we have
? log (b()))] =
diag
(23)
2
VE.6
Where diag(-) denotes the standard diagonal matrix. For the policy gradient, we show that
| (A(r
V x))]
(r(x)- - =X(r:)))||
P
(r(#))nbs> -D(y): mnnnd
V. log vog (ew)
h=0
<
h
(1 +
- (h + 1) 1)-
(24)
1 1-
h=0
V
<
+
(1
(1 - 33
Where (24) is due to (22).
37

---

Before we proceed to show the convergence towards global optimality for (21), we first define the notion of Moreau envelope and the proximal point.
Definition C.3 (Moreau Envelope and Proximal Point). For any y ys, we use 2))1o
denote the Moreau envelope of function F" (X(y;; x)) such that
3 2 [((zz))) - -X(x
(1/((A(v: = max
F ('(((()))))
=EY;
Moreover, we define the proximal point $1/3 of Moreau envelope as following:
(F((((1))))
8 [|(z;))) - (x::
ÿ == argmax
Now we proceed to show the following lemma: Lemma C.11. When running Algorithm 2, for any 1 0, we have
(+)) 20011
S(1 m) ()) - 000 + +2(1 - n, + nylu) CCS" "
1 (1)
+ t || v
0b;')"² (0(0)
Where C33 = V ||||||
GH
Proof.
|10 [1
Prois Proi
+oo (0)))
(25)
<E |10 (1) +0
=E
[| [1- 5)18
-11100000000000000000000 =F
-10-0,,91000
-2
-17")))))
+
(26)
Where (25) follows from Lemma 3.2 in [34]. For the first part of (26), we have
(1 - 33 - g(()) + Tu (V Vy x)) F' (A(y
=(1 - 3/ () 0/01 + n VyF x))
x))
+ 2(1 m13)) (4 600 V F'
V,F ( 00 :x)))
<(1 - m 3)2 (1))) g0o + tnge (1())) g(0) |
+ + m,, m -10)0 g10l| (27)
=(1 3)
(1 + 2
1-m03/
|1000 -/001/2
1 1-
Where (27) follows from Lemma C.4. By setting ny. 8 such that 2nylr < we have
ny 2
and
1-7,8
n
S
2
|11 (1- ()) thy (V (x))
< (1- (00) - 1/00
(28)
38

---

For the third part in (26), we have
2(1 http::/wwwwaaaa//ooo///////aaaaa (A())))))) 26 1b/1)/1/001
(
S2 Xan.aaaniiiiiiiiaaaaaaaaaaaaaaaa F
() )11100
$00-=//00||4t,011100000001011110 Σ²(1 (. C27
(29)
(30)
Where
C3
|S| (1-7)
(29) follows from Lemma C.4;
(30) is due to Lemma C.14.
Combine (26), (28), and (30), we have
E
y 1 g/0l (
<(1 ny,33 -
+ (113)m((1 nylx) C2r"
+ EE
()
- (1))
We then show the result for convergence optimality for (21). Theorem C.4. By setting Tyy
and H 2loe(1/ve) I-y
After running Algorithm 2 for
10 D
T = O Gol log (2)
E log (t) iterations, we have Uee
E
(N(tti)) F (T( S
Where y the unique maximizer for the optimization problem (21).
Proof. From Theorem in [43], by setting 3 = =4e,, S 2nyeu and ny S Sr,
2.
Then for any
yX, we have
F. / (A( (1+1) ;0)))
Fn (A(2; x)) -(1 (1+ + 3 g y 1++1) 2
1|= -11+
1
(00) 2 =1²
>E
1+
2
FO m)) - -(1 + s1 - 11 (0) -g(t) 1//1/9 [|]
2
11
2 E
9
g(و) x z|² 2ny (1 + +)(11 - 3) + ng)r) )- C2n
|| FM ; )(00) /|² (0)))
(1 + 8)
(31)
Where (31) is due Lemma C.11. By setting n 1+ S 2, and + +
2. we have (1 s)(1 n1, By
3 From Theorem in [43], we get n
E Fi ( (c+)))
+ oFF"(A(y(;a)) BT,TE || ( - -0b0>|||
2(1 - a)) 1V (ty
333 a²
(1 (1- aw
11)00:00 \(vē; |||
E
A
21, a)(1 + m)()) C
21yy
2
39

---

Define A, = EE (A(N2 x)) -iiy ( (X( [x)]] by setting
313 a²
(1-o)ow
S 0, we
2ny
have
A441 (1-a)) B [ (A(x
/ (1(1)
+2n -a)(1 [x) C3
|| (A
-6 /// 13/10) = o²², we get
Summing over I iterations, and denote E
Ar S (1 (1--a) a)= Ao 1 02
2ny (1 a)(1 + nolv) Cg
a
By setting H ([ve( S min
2gglur
way 212
and My = ge,
2 ve
after
10
Ainc
Polaaa T=
(foBbr
log (c)
l 2 log ()))
v
vee
iterations, get Ar S Where o²
+ C2 72H C1
(T~7)ęT: C2
57
(I- C3.
126H²
(-- Since F" (X(y; is smooth with respect to the state-action visitation measure Xyy m). We have
v B
6H
Ar = E
Fd (A(U(i))) (A
3 |(2; (7) xx)
=
E
("(U((;:))) x))
max ZE)
F ((((x;;)))
2
+ 3
[ - 2(y) 27
2 E
(*(NE(Z: - F" (A (3) x))
2
= E Fd ('(((( - F" -F"(((())
Therefore
E ('(((((:))) - - -F'(A(())aa)) s SArS Sc.
Define 3² E y such that y argmax {r(x)) (r(at)T((p) A(y: x)) 1 [1y((; (?).. We bound the
distance between the the optimal 3² and (T) from Algorithm 2.
Lemma C.12. For any y E y/, EE F" - FC (A((r=))))
S <, then we have
E Ellyy - ylll < LAna (V BLABB (
V
Proof. Since F" #)((y:=)) is v-strongly concave with respect to A(y: x)) we have
('(((((:=)) > F" (*(())=))) + FV x)) A(vē:z) - A(v:
+, 2 |AU{ - My:z)
(32)
=A*()(y;;))) x)) | - A(y: 1|
Where (32) holds because A(yद; 2r) is the optimal solution for F" (A(g);; for any y E V. Therefore
2 v
2
2e
[1)(();;)) - A(3; -
V
FV -
S v
40

---

From the definition of x) it holds that for all yç E )', we have
VA VxF"(Xug; m)), a))2:a) Muy;;))) 0. Combine with Lemma C.6 and consider
y² E V, we have
V F F" (A()): x)) ((((: x)) (z)
V~ F" (A(UE: m) (v ) + (((;: :x))
(33)
(-VXF" x)), x) A((;:z)) +(- (-VAF"(A(yf;: x)), X(y;: :()"=
(A(U?; z)). (y);z) \(1":z))
VAF" m||| ()( >(y";=))
4LX|BIC
(34)
1-7
Where
in (33) yg E YX chosen such that l1y - -ysll S 2[|B] according to C.6;
(34) holds because V| (A)ll I 1-7 and x(y;,)) is Lx-coniinuous.
Since (A) is v-strongly concave w.r.t X, have
//2
V
((y;; A(y"; =)]l
< F" (A(9); x)) F" FM (A(y"=))) (V=:"((((((: ar) - >(y²;;)))
1-7
Thus conclude that
E E1
y/1l _ A EE [1IA(y x)y;
s L Aaa
(1|((y';;)) A(y;i + E [|);(];;) >(yr=))]))
8Ta|BIs (1-7)z
2c
DAw
+
41

---

C.6 Regarding the Gradient and Visitation Estimators
In this subsection we will quantify the bias and variance of the gradient and state-action visitation estimators used in Algorithms 1 and 2. In particular, REINFORCE:
the gradient estimator for team agents is implemented by sampling a trajectory with horizon length, H, that is drawn from geometric distribution for the team, and while, the state-action visitation estimators that the adversary uses come from sampled trajectories a fixed horizon length H.
In the former case, the estimator is unbiased while in the second case the bias decays exponentially in H.
C.6.1 REINFORCE for Vanilla Policy Gradient
In the present work, the team agents only need implement batch version of REINFORCE [104].
That is, they get estimates g
ΣM (t)
g where:
M
H3
H, Σ h=1
V Vlog vi (alt)))s(hs))
(REINFORCE)
with each Hj a random variable following geometric distribution with parameter (1 7)-
Although the authors of [27] use Ç-greedy parametrization in order to bound the variance of the estimator, policies drawn from the (-truncated simplex imply the same inequality needed to bound the variance. Hence, we invoke the corresponding lemma.
Lemma C.13 ([27, Lemma 2J). When Equation (REINFORCE) is implemented with H following geometric distribution with a parameter 7, and agent l selects policies from the (-truncated simplex on each state, is the case that the gradient estimates satisfy:
(t) 9
Va,
Vo(xx 10(xx.10 8²) = 0;
11]
E
V Vo
< 24 C(1
C.6.2 Gradient Estimation for Visitation- Policy Gradient
In this subsection we will describe (i) a state-action visitation estimator with bounded bias and variance and (ii) a gradient estimator of the regularized value function whose bias and variance are also bounded.
Bounding the variance the a gradient estimator with a deterministic choice of H was significantly less demanding than doing with randomized choice. This comes at the cost with non-zero bias that nevertheless decays exponentially in H. For any policy of the adversary E Y, we introduce the H-horizon truncated state-action visitation measure
1
(y:
=
Σ
nh P(s = s. = bly, 80 ~ p).
(35)
h=0
Where (H,,,((y; denotes the (s, b)th entry of ) For any reward vector we have
H-1
(V [y)dn(
E
Σ th (rss
V log (bog)(()))))))))
y: 80 ~
C.6.3 Controlling the Estimation Bias and Variance
In this subsection we will present detailed analysis regarding estimators defined in Definition 2.6. Definition 2.7, and the ones used in Algorithm 2. Particularly, Lemma C.14 14 we bound the bias of aforementioned estimators. This bias is inevitable for our analysis due to the fact
42

---

sampling trajectories of a finite length H over an infinite horizon. Proceeding to Lemma C.16 and Lemma C.17, we bound the variance of the state-action distribution measure estimator X and the gradient estimator g3 (t) w.r.t their biased means. Finally, in Lemma C.18, bound the distance
between the gradient estimator g and the actual gradient Vy F (X()))))
Lemma C.14 (Bounded Bias of the Estimators). For any adversary's policy y V. We let 7 (s0, by. $1, b1. 11... -:-1, b1) be an H-length trajectory sampled from y, then we have T v) = A (y:: x)) and Erwy (Ā( ff r) = V (y: x)]] r. This implies that in Algo-
Erwy
rithm 2, E { A (z x) and E gv = (g T (()), Moreover, we have:
[210]]
((y(0;=)) m0) S -ー and
TE
E 99
(E)
Vy ( < (1- + uftuel
(1-1P + (|- ,7
Proof. From the definition, we have
Erny [((111)] (2:
Er [((rl::))] [v)
Therefore,
E | = [V 100 E [1) = (1(0000;
Then it holds that
B [ (()(0);))
A 1 (0 (0)) (0)
y h. Plsh b, bly 80 p) bn
< H
())
h=0
Similarly, we have
E [000 - Fy F" (AQ
V (xd))()(().00))) (0 (A(
V (1
[
V " mm)
(VAP"(Am (1) ;=)) (0
<
+|( - -V VA
(36)
43

---

For the first part in the above inequality, we have
V (2)
(VAF" (A (0)) VAFr(A((y))))
#-1
Σ 7t
(OF (a))))((();a))
aF
(
@dor.nn Dhhenton
V. log y (0) (bN
1=0
h'=0
V2 - Vx (A ;x))
Vy log ( (bwr (bwllss) lsw)
h=0
\/==0
(z)
V. log (b) (bw-lsw) (sw))
(bw
0=0
M
(y)
A(3 x1)1
(h + 1) ?
(37)
h=0
V
(y
(
(1 (1-7)
V
ΣΣ
x P(sn = bn bby so p)
(1 (1-7)3p
s.b h-11
[1 (1- 7
V
(38)
For the second part in (36), we have
V Ty :0))
- [Vv))(r(0=0))] V F2F
OF (F())))))
E
?
V. log ((w
Oden.b
h=H
V' 1
(h+ + 1).
1-7)
b=
V
II
11 +1
(1-
1
5
1
.
7
H +1
vH +u++
19
(39)
7)
(1->){<
(1 7)35
Combining (36), (38), and (39), we get the result.
Before we proceed to analyze the variance of the estimators, we first show the Lipschitz continuity of the gradient estimator.
Lemma C.15. Let 7 = {su, by, $1 by ... 8H-11 b be an arbitrary H-length trajectory. The
gradient estimator satisfies
For any policy y, for any reward vectors rn and r2,
Tū(Tly:) ((T(y1 S (1 (1-7) |||, - -r21
For any policies yı and y2, for any reward vectors r.
1
(gg(Tly1))) g( 5 (1-7)
1 y2
(1 (1- x)- (3
44

---

Proof.
--1
)
Σ
7"hh (ri(sn: bn) (r2(sh: bn))
V. log ((wwlol))
h=0
H-1
bb |r_ T2lloc (
(40)
hm0
$
-||r -22lloo
(1 r)
(9((1y11 ()) g( r)ll
Σ r(sh, bn)
V y log y2 (bnr Vy log ye (og
n1
<
Σ
7 r(hh, bn) (h + 1)
x2 1191 -22l
(41)
h=0
(1 + )nm))
|1y/ y2l
(1 - 2)
(1 7)p2 + (1 (1- ) 11y1 -22ll-
1
Where
(40) follows from (22);
(41) is because of (23).
Now we analyze the variance of the estimators in the algorithm, we start with showing the following lemma.
Lemma C.16 (Bounded Var. of Visit. Estimator). For (+) in Algorithm 2, the variance is bounded. holds that
E |1 - (0
< K 7)²²
Where A (z)) is the truncated state-action visitation measure for (() defined in (35)
Proof. holds that
|0000 - (y 11 =E
E
\(rl)(0) - Aur xx)
TEK:
{(Tll)(0)) - (0) 119 2
E
(42)
K
< 1
||((TER 11]
E
(43)
K
(44)
K(1 - 7)2
Where:
(42) is due to [210]
>x (y)(0)) (1) and the fact that trajectories J E K(()) are indepen-
dently sampled;
45

---

(43) is because the variance is bounded by the second moment;
1 (44) is because [{(r)\))| & T-
Now we analyze the variance of gradient estimator " by providing the following lemma:
Lemma C.17 (Bounded Var. of Grad. Estimator).
For ( in Algorithm 2, we have
[=)) xcool S K(1 - 22²² K(1 <21-2)52 + (1)
G
9v2
E
K(1 2)
Proof. We denote r" = ViFV (AH((1 (x)) = =((x)= - vA (1; x)) Then we have
((()) 27
E
9y
(t)
[
=E
Σ
((
1
Σ
(1;l)));r))
+
1 K
Σ 0(Tly)();
K
K
tEK(
TEKe
TEKiO
+ Ve "--- - (edd)(e (20) (0))) 12
A (e) (z)
S3E
Σ
( x2))
- g( (0)
K
TEKOO
27
+ 3E
Σ g(T (( - v (2) x"
K
TEK(()
27
(y) r- (1 (0))
+ 3E
(45)
Where (45) is due
inequality. For the first part in (45), we have
E
(((
g (0
K
TEKOO
Σ
[( - ((T (t)
(46)
K
TEK())
1
|((()) [|((t))-+) r*
E
(47)
(1 - 3)
22
||/000 A (3)
(48)
11 7)4c2
2²
(49)
K(1 K(1-7)662
Where:
(46) is due to Cauchy-Schwarz inequality:
(47) follows from Lemma C.15;
(48) follows the same proof as in (37);
46

---

(49) is because of Lemma C.16.
For the second part in (45), it holds that,
E
1
Σ
g(rly((;;)))
- V ee (x))))))())) p-
K
TEXT
(1()0))))) [x)dn(o((:00)) r.
E
(50)
K
| y 10 r )
E
(51)
K
H Σ x r- bn)
V log (bwlsw) )(
Σ Wt'mo
E
K
h=
#-1
1 / ) 5 (h +1
2
S K
Σ h=0
(+11-)
(52)
K(1 - 7)52 + u²
2v
+
(53)
K[1 2)²
K(1->)0 22
Where
(50) is due to Lemma C.14 and the fact that trajectories r are independently sampled;
(5 l) is because variance is bounded by second moment;
(52) follows from (22).
Finally for the last part in (45), we have
V V H (y)00 r. ~' =( ""co|""" 20001"
E
(r (p---(0)) /
E
V 21
A 11 (2 (1)))
H-1
<E
Σ 7 ||| m(00 1x0
Σ
V log y 10 (bnr (sp:))
M==
(h (h+1)) 2)
EE' || A (0)) 11]
Σ
(54)
D2
1
(55)
(1 (1- S2
K(1 7)2
12
(56)
K(1 - 766
Where
(54) is due to (22) and (37);
(55) is because of Lemma C.16.
47

---

Combine (45), (49), (53) and (56), we get
E
[vdu(o(()
V
T
x000
31²
2v
v²
32?
+3
[(1 7)
K(1-1)
K(1 7112
K(1 ((1-7)862)
K(1 22
3
6y
9v2
+
+
K(1 -))
K(1 7)82
K(1 ?2²
After bounding the variance of g in Algorithm 2, we can prove the following lemma
Lemma C.18 (Bounded Dist. with Actual Grad.). Consider (()) and gy in Algorithm holds that
(t)
E 1
C - + C2 -22
K
Where
57
C2 = 126H²
C (1 76-)
(1 (1- 7)
Proof.
Let r = =etr*==xt VxF" (1 = r(x) - (x))))
E
V. (A(((0))))
(
(x)))))())=) (0)) + (v)=(1(0022)) ,00 ( r
+
V
A (3/ (0) ;0)=
x" -- VyF (A F (1) x3)
000 V (0d [0o] T
<3E
m.1))
(0) m00 - (e))) .x)] r-
3E
V (0)
- (
(y xx))
(57)
Notice that the first part (57) is bounded in Lemma C.17 and the second part bounded (56). For the last part, observe that
48

---

V ())m(((())))) :0) r - ) xx))
[2>(()(0)=3)) (z)) -
-
:AF"))()))))))) 2
[odN(o
VAF (A(g)) (1=F""=10000)))-=="""""=1
((VAnr(o():))) :00) - -(0))(0(:)0)1') ( (); ;x1)
3 (y x) |
2
(A=(
x))
+2 == - V
2
V (x) xz)
(58)
Where (58) is follows from Cauchy-Schwarz inequality. For the first part, we have
V [y)=(((0)))) " (AH(B()) V (A(g()) x))
/h 10)00 - (h (1+1) 5 2
X(y
(59)
h==
y²
[ x0)
(1 7)²
Where (59) is because of (37). Since
2
( - -0)))))))))00)))))))))))))))))) ;20
Σ
Σ
IPss = =. = 61y)0) 500 ~ p)
1==
b,b
2
H
1
h=
2H
(1 - 7)22
We have
V [V)An(((): " (TXP" (V (A
1|
1/2
5 (1 (1-7) 72
,2211 (60)
For the second part in (58), it holds that
VXFT (Xg())))
E
7 V 1 (A(y 2)))
Σ
v. log (0) (bb (6m))s)))
W==
1
1t
v
-h -(h+1) 1)-7))
1 1-7)
1=
1
1+ 1-7
(2 (1-7)² +
-72"1
(1- 7)4
112
2u(H
+12
(H 112 +1
2v
(1- (1-2)0) ) -2211
u²
+
+
(61)
(1-
(1- (1-7)'²
71-))
(1 - 52
49

---

Combine (58), (60), and (61) we get
Vy>n(1())))) mn)
r² (Xg)(((()))=
(H 1)2
20
(1 (1-2))²2 + (2 + 1)2 +1
2v
(1 (1- ) ggaH. (62)
2v²
2
+
+
(1 (1->)
(1-7)
(1 (1-
Now combine Lemma C.17, (56), (57), and (62), we get
9 7yF"(A(B)))) (0 (A()) 11/
C1 K
E
-
+ C2 722
50

---

D Noncorva-Fiideee-Srrngy-CCCC Optimization
In this section we generalize results the more general setting of any constrained min-max optimization problem of the form m maxyey when f is nonconve--iidee-tttoog---oooo In partieular:
Theorem D.2 we prove the differentiability and Hölder continuity of the max function ((x) = maxyey [a( y) by utilizing the Hölder continuity of the maximizers w.r.t. to æ (Theorem D.1).
Finally, in Theorem D.3 we prove that Algorithm 3 (SGDMAX) [70, Algorithm 4] with an appropriate tuning converges to an c-SP for nonconvex sancoonve-hhidee--oee hidden-coneave functions.
We begin by stating the assumptions we make. Assumption D.1. Let f be function defined on X' x y where and y are compact convex sets. T-Lipschitz continuous and E-smooth.
Assumption D.2. Let be "1-1" mapping between y and compact convex set 2/ parameterized by X. Further, we assume that and its inverse c are Tu-- and 1..-s-Lipschhtzz continuous.
Assumption D.3. Let H be a nonconvex- nonconvex-strongly weresssttooooyocnceeeeeeeee concave reformulation of f (as in Assumption D.1) for mapping (as in Assumption D.2). We assume H to be L -ipscchit continuous and & smooth.
Moving on, we can show that the maximizers u² are Hölder continuous w.r.t. to σ.
Theorem D.1 (Continuity of the maximizers). Let a function noncomvex-nonconcee function f.c, c, H as in Assumptions D.I to D.3. We define u² (xx == argmaxust((a) H (x, u), then it is the case that
|| (x1) u (x2)) S L. ||] x221 x/211/2
Where T, = 2n (BEHV Diamxx + 2/ v1 21 Diamp + 2v 20
Proof.
Consider any æ 22 E X, since un is the maximizer, it holds that
W (æ), u (x1)) (u1 - u² (x1)) S O, Vui E e((x)); V (x u (x²)) (u2 ux s O, Yus U(x2)).
We now consider w that belong to the set = U(x1) (2(())) We observe that due to the Lipschitz mapping, for every ū E U. there exist a in u(xi)) such that || - -ulll S Lellær - =22l. Similar argument holds for U2 ((x2). Therefore, from previous two inequalities,
have
H (æ), u (xi)) (u - u² (xi)) < Labn - 22 H (æ22 u (x22) ux=))) & To | 22l
Vu E U
Vu E 17.
Where in the above inequalities used the fact that V (z, u) < LH. We plug in : +- (x2)
and ū + u² (x1) accordingly.
H (I1, u² (x1)) (mx) u (x1)) < LLL | xzll,
V (x2, u (x2)) (m)())) - u (x2)) S Labn ||=] - æz2l-
Adding the two inequalities results in,
(VH (I1, u² (x1)) VH (z2, u² (zz)) (u (x11 u (x1)) S 2L x2ll. (63)
Since Hxx,)) :) is v-strongly concave in u for all æ. it holds that
(u1 - u (xx))) VH (æ1, u1) V (æ1, u² (x1))) + v||ue - u² (xxx)111 50 Yui e U(x1).
We again consider feasibility set : W. Since for every : U. there exists u, e u(x1) s.t. | æ2|l. We have
||u unll & Teelay
(u) + (u . - (x1))) (VH(#1, u1) + (VH(œ1, σ) - VH([I, - VH (H( u (æ,, (x1))
+ vl|u + (u u 2 (z 1 s0, Vu {(xx))
51

---

We rearrange the latter display into
ū u² (x1)) (VH(21, τ) - (H 2 (x11)) + v 2212))
$ - (u u (2:1))
(VH(z,, un) - ,
(I) u) T VH((1, u1)
(x 2 (x1))
f1a
v/ Uu zil
2v (ui
u. u (x1)
We bound 12 G2 and Ωg separately.
For S4, have
(u (xi))
un)
v Diamy Lu - u/l
Diamy Lo ||a|| - =x2l
For Ω2 it holds that
(u u) (VH(z1, un)
(H( (x()))) S Le x1 x2ll En Diamy.
For Ω3 since the first term is always non-positive, we only need to bound the second term:
(u) U. π (x1)))
S [1 ग || u (x1)))
s Le || x x2ll Diama.
Combining S2 S22 and 22, conclude that
(u u (m1)) T
(H),,, u) - (H(m), u (z1)) + 21/2 (x1)))
$ (1 + 11 L. Diamy || x22|
(64)
Plugging in + uz (x>)) in (64) and combine with (63), we get
(x2) u² (x11) 2 (u" (x:2 u (x:)) (VH (22, u (x²2) VH (011, un (x22)
L" [2 Tz2l
< LHllu' (z2) u (x: || xzel + ["|x x1 x2
Where I," = 2l + T.T
Similarly to Lemma C.8, we can set À |lu' u u"(x))) and x || 22 and consider the
inequality 2 < f Ax x. We aim to find the solution of the form &xx+ "" + S cxX. By setting L, = e and solve for e gives
1
L.
26 L.))mi + 2v Diamx + 2/v(11 v(1
2v
Finally, we show that & is differentiable and Hölder-continuous. Theorem D.2. Let function & be ((x)= == maxueu(()) (H u)}. Its gradient 44 is (1/2, (1/2)- Hölder continuous,
(V(()) - v s l1/2 x - 2'11
where 21/2 ((1 La-1 ) Diamx + L.-1 l.
52

---

Proof.
(T(x))
[o(x')] = / ( (w)(::)) V - |
<| x'll +
<1 - =''ll fLe (1 = ||
(65)
s (1+ Lc-1) )e || x'll La- L.e | x'1
(66)
$ (1 + L--1) 1) Diamx + Lo- Ii+ a x''|
Where
in (65) we invoke the Lipschitz continuity of function c (-); (66) follows from Theorem D.I.
Following, SGDMAX is presented where we assume stochastic gradient oracle G (G2r Gy) X' x x Rd that is unbiased and has a bounded variance:
Algorithm 3 SGDMAX
Input: Initialization (0), stepsize Yu. Tr iterations, batch size M, oracle accuracy Ç.
1: for + 1, , do
2: (()) max-oracle (fax((),
3:
(t)) क
Σラ M G. (x(t-1),, y(1) c(t)
4: (+)) Projx a
(t-1) nag
5: end for
6: y (T+1) max-oracle ((()!())))) .)::s)
Finally, we can state the theorem of convergence to an e-approximate saddle-point. Theorem D.3. Let function f as the one in Theorem D.I. For desired accuracy >> 0, Algorithm
f2
(SGDMAX) with tuning T. =
12., max-oracle accuracy Ç =
kc 2z
and a batch
c3
size of M = max {1,
96" 2 guarantees that there exists a t E [T], such that,
Vaf (m!(() (y (x' - x(()) S e, Var E X;
yd (zo(t), +2)) ((') < Ay' E E..
Further, the max-oracle, of accuracy Ç. can be implemented by Ty Ō (
I2v
+
1gtta 2)
Laa
iterations
Live )
of stochastic projected gradient ascent with a step size Fly min UL
1oL0²
Proof. The proof follows easily from the proof of projected gradient ascent in hidden-strongly- concave function found [43, Theorem 6] and Theorems B. and D.2.
Remark It has been shown that when a function f enjoys hidden-streen soidden-ttrongy--ee strongly-concave reformulation. it satisfies global the Proximal-PP PP condition (or equivalently, global KL condition) [43, 67]. While the equivalence between global KL condition and quadratic growth condition has been proven [10, 38] when is concave, to the authors' best knowledge, this equivalence still remains unclear when f is nonconcave. This means that we cannot use [83] to prove the smoothness of the maximum function when the feasibility set of the maximizing variable is constrained.
53

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: As claimed in the abstraction and introduction, main contribution is the design and analysis of a learning algorithm for Adversarial Team Markov Games with polynomial iteration and sample complexity (in the parameters of the underlying Markov Game); this is captured by Theorem 3.3.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of our work are captured in conclusion and future work for investiga- tion. Moreover, all necessary assumptions have been properly cited.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to vi- olations of these assumptions (e.g.. independence assumptions, noiseless settings, model well- well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to teeccttt--text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by review- ers grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
54

---

Answer: [Yes]
Justification: The proof of the main result and auxiliary claims and lemmas can be found in the appendix and are properly referenced. All the assumptions have been properly defined in the Preliminaries section and section 3, 4, e.g., Assumption 4.1.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), relcasing of model checkpoint, or other means that are appropriate to the research performed.
Depending the contribution, reproducibility
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how construct the dataset).
model (e.g., large language model), then there should
(d) We recognize that reproducibility may be tricky in some cases. in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
55

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: http:////iis...ppppaaaeeeeeeecee
guides http://odeeummiiinnoooo.ooo....e
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:// for more details.
nips. cttccc//puue htc//uulic//aee wwwlc//ggii///eee /ileee/bodSuubiic.. coaeinsssioooolli
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars. confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
56

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric eтror bars that would yield results that are of range (e.g, negative error rates). If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /estps:/nnettee http///errippppppppee ips cc/ppblccc/haiicttiieei....eeeed
Question:
Answer: [Yes]
Justification: The paper is of theoretical nature about learning Nash equilibria in Markov Games. The authors believe that the paper is aligned with NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is of theoretical nature about learning Nash equilibria in Markov Games. The authors do not foresee any societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed. If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
57

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology heing used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models). used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package wwerrssithhodee should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
58

---

Researchers should communicate the details of the dataset/ccoeemmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
59


Reviews:
[{"review_id": "YTXwzQDUfx", "reviewer": "Reviewer_YssW", "summary": "This paper considers the problem of independent policy gradient learning in adversarial team markov games (ATMGs). In such games, a team of agents with identical reward functions aim to compete against a single adversary whose reward function is the negation of the team's. The paper consider the setting where the MG has unknown transitions and reward functions, and the players can only obtain information about it by sampling trajectories and observing the resulting states and rewards. The main result (Theorem 3.3) gives an efficient algorithm which produces a policy which is an epsilon-Nash equilibrium of the ATMG, in which the players act independently, and which requires a number of samples which is polynomial in the number of states, actions, horizon, 1/epsilon, and distribution mismatch coefficient.", "questions": "See \"weaknesses\" above.", "limitations": "The paper should be updated to address (A) + (D) in the weaknesses section above (both of which can be fixed by changing a couple of sentences).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Previously it was only known how to compute a NE in an ATMG in the presence of known transitions and rewards ([65] in the paper). Although the algorithm in [65] is a gradient descent-style algorithm, the present paper makes a convincing argument that the existing approach is insufficient (essentially because one cannot solve a certain linear program exactly).\n\n- As such, the paper introduces several new ideas. One key idea is the regularization of the adversary's value function by the squared l_2 norm of their *state visitation distribution* (denoted by lambda in the paper). This ensures that the adversary's value function is strongly convex as a function of their visitation distribution, which facilities Danskin theorem-type arguments.\n\n- As a result of the above idea, the \"max-function\" of the team's value function (i.e., the regularized value the team receives if the adversary best-responds) turns out to only be Holder-continuous (not Lipschitz continuous, as is typically the case). The paper then proves a new convergence result for gradient descent on nonconvex Holder-continuous functions (which seems to use similar ideas to previous work [35] in the convex case, but is nice to have written out).", "weaknesses": "(A) One weakness is that the algorithm has an \"inner loop\", in which the adversary must run several steps for each step of the team. This is in contrast to, e.g., [27], which has a stronger notion of independent learning (i.e., without an inner loop).\n\n(B) It would be nice to have some more description about why Algorithm 2 works: in particular, it's not immediately clear how to interpret the updates to r(x) (ie subtracting nu * \\hat lambda) in line 4. Since r(x) does not depend on y, this doesn't seem exactly like what GD is doing?\n\n(C) To support the paper's claim that Moreau envelope techniques do not apply, it would be nice to have some result giving an example where Phi^nu(x) is *not* weakly convex (as typically in such situations one would expect Moreau envelope techniques to work).\n\n(D) The paper claims prominently (e.g. in the abstract) it solves \"the main open question from [65]\". I could not find any reference in [65] to the open question which the paper claims to solve. The paper should be updated to either say where specifically that open question is stated, or else rephrase the claim (which is misleading if [65] does not state this explicitly as an open problem).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b4QDIEwWRx", "reviewer": "Reviewer_LXfR", "summary": "This paper investigates the identification of NE in ATMGs. The authors explore the underlying landscape, leveraging optimization theory to effectively solve this problem.", "questions": "check weaknesses", "limitations": "check weaknesses", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Theorem 3.1 stands out with significant contribution. Writing is very clear.", "weaknesses": "The other theorems, in my view, merely adapt the MARL problem to a specific instance of an optimization problem (with an observation of hidden structure). The paper does not leverage the special structure of Markov Games (or Team Markov Games). Nonetheless, I appreciate the paper's clarity in writing and its theoretical contributions.\n\nI have read the paper thoroughly, and while it presents a significant contribution, I believe it might not be the best fit for NeurIPS. The authors address a very classical optimization problem and apply their findings to an Adversarial Team Markov Game. Although Theorem 3.1 is particularly impressive, the subsequent theorems follow from it primarily due to the compactness and finite state and action space of MARL. This paper, lacking experimental results, seems more suitable for an optimization journal. I know several MG theory papers are already accepted to NeurIPS, even without any experiment. To be clear, I do not want to discourage authors about the fit for the venue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their precious time, suggestions, and their encouraging comments.\n\n> *“The other theorems, in my view, merely adapt the MARL problem to a specific instance of an optimization problem (with an observation of hidden structure). The paper does not leverage the special structure of Markov Games (or Team Markov Games).”*\n\nIndeed, we formalize an established MARL problem as a minmax optimization problem. This is a tradition that goes back to Von Neumann study of two-player zero-sum games long before the Nash ‘51 paper.\n\nWe manage to tackle a MARL/AGT problem by utilizing techniques that are virtually omnipresent in (MA)RL; namely, policy gradient methods. We tweak them just enough to guarantee convergence and provable guarantees, but they still remain genuine MARL techniques. In fact, many technicalities and novelty of this paper are embedded in the theoretical analysis of the given provable guarantees.\n\nAs we stress throughout, without leveraging the structure of the ATMG, our techniques would not work. The character of the structure in most of our arguments is dominant. \nIt is precisely the ATMG structure that allows the application of a nested loop policy gradient algorithm (ISPNG) with each team agents taking one gradient step simultaneously after the adversary best-responds.\n Without the ATMG structure we would not be able to establish the nonconvex--hidden-convex structure of the minmax problem at hand.\nThe structure of the problem allows us to transform it to nonconvex–hidden-*strongly*-convex problem using the regularizer on a quantity that has a natural meaning for this problem.\nWe adopt the $\\ell_2$ regularizer because its gradient is merely proportional to the state-action visitation measure and we can get a nearly-unbiased gradient estimator of the resulting function that also has bounded variance given the policy of the adversary lies in the $\\zeta$-truncated simplex.\n\n> *”The authors address a very classical optimization problem and apply their findings to an Adversarial Team Markov Game. “*\n\nMany problems of learning NE in Markov games (in both single-agent and multi-agent settings) boil down to an optimization problem of finding a stationary point of a nonconvex-nonconcave function [1]. In fact, we started off solving this particular problem of learning a NE in ATMGs and later extended it to a optimization setting that is more general.\n\nIndeed, theorem 3.1 is a cornerstone. But in order for us to be able to use it we need to formally prove that team agents performing gradient steps on the value function after the adversary best responds is equivalent to performing gradient steps on a nonconvex function with Holder continuous gradient.\n\nEvenmore, we need to design the gradient estimators and bound their variance and inexactness errors.\n\n>*”Although Theorem 3.1 is particularly impressive, the subsequent theorems follow from it primarily due to the compactness and finite state and action space of MARL. “*\n\nDespite the significant contribution of Theorem 3.1, it only tackles the problem of stochastic constrained optimization of a function whose gradient is merely Holder-continuous, but not in an ATMG setting. Thus, a lot of extra work is needed in order to prove that the function $\\Phi^\\nu$ is indeed a function that is differentiable with Holder-continuous gradient and also quantifying the Holder constant and exponent $(\\ell_p, p)$. Indeed, one of our main contribution is to prove the gradient of $\\Phi^{\\nu}$ is Holder-continuous and the techniques we use for the analysis is novel and of significant theoretical value. \n\nMoreover, we want to respect the requirement that players will only get samples of trajectories as feedback and will not share explicit information about each other's policies. This means that for the team agents they can never get the exact gradient of $\\Phi^\\nu$ even if they had an infinite number of sample-trajectories at hand. Please also see the global rebuttal “Novelty in our paper”. \n\nWith all the difficulties mentioned above, we managed to prove that projected gradient descent with stochastic inexact gradient converges to a stationary point when the function has Holder continuous gradient. Specifically, we prove that the team agents do not need an exact estimate of the gradient as long as the error can be controlled. We put a lot of effort in bounding this error which also affects the Holder-constant of the function $\\Phi^\\nu$.\n\n\n> *”This paper, lacking experimental results, seems more suitable for an optimization journal. I know several MG theory papers are already accepted to NeurIPS, even without any experiment. To be clear, I do not want to discourage authors about the fit for the venue.”*\n\nWe will add numerical results but we agree with you that a lot of papers that are published in ICML, ICLR, NeurIPS, COLT do not necessarily need them. We strongly believe this conference is a good fit as attested by the multitude of theoretical MARL/AGT papers that get published every year even without experiments. Also see the rebuttal for reviewer hE5h for a list of papers of the same scope that where published in these conferences.\n\n\nWe thank the reviewer again for their time. Perhaps after reading our replies they can reconsider the score they gave us.\n\nBest regards,\n\nThe authors\n\n[1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1–76, 2021", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hvKZrDH55n", "reviewer": "Reviewer_LYwL", "summary": "This papers addresses learning equilibria in adversarial team Markov games, where a team of agents sharing a common reward function competes against a single adversary. Previously, [65] addressed this problem for the model-based case with no sample complexity guarantees. On the other hand, this paper presents a learning algorithm for model-free cases with bandit feedback and provide polynomial sample complexity guarantees.", "questions": "- What are the practical applications of adversarial team Markov games where learning equilibrium via the algorithm presented can be of interest? For example, step 3 in Algorithm 1 uses REINFORCE with the batch size of M where all agents, including the adversary, keep playing according to fix strategy $(x^{t-1},y^t)$ so that the team members can collect samples and estimate $\\hat{g}_i^t$. This contradicts with the adversarial nature of the adversary. Therefore, are we considering a simulated environment where we coordinate the team members and the adversary to learn some equilibrium of the underlying game? \n- Adversarial team Markov games reduce to team Markov games if the adversary has a single action, and two-agent zero-sum Markov games if the team is a singleton. Can we say something similar for the algorithm presented? In other words, if the adversary is a non-strategic player with a single action, does the algorithm presented reduce to a known learning algorithm for team Markov games (or Markov potential games)? If the team has a single player, does the algorithm reduce to a known learning algorithm for two-agent zero-sum Markov games? If the answer is no, what are the differences? \n- Can the authors rewrite the algorithm descriptions? For example, what is the function VIS-REG-PG? Is it the steps from 2 to 6 or the entire for loop in Algorithm 2? This is confusing since Algorithm 1 and 2 have different epoch numbers $T_x$ and $T_y$.\n- Can the authors provide numerical examples? A comparison with the algorithm of [65] would also be very helpful to observe the impact of model-free and bandit-feedback cases on the convergence.", "limitations": "The limitations of the paper has not been discussed separately in an explicit way. The paper (1) requires the coordination of agents including the adversary in playing the same strategy for sampling trajectories in the estimation of some parameters important for the team members though this contradicts with the adversarial nature of the adversary, and (2) provides possibly very large bounds on the number of gradient updates and the sample complexities. (1) is important for addressing the model-free and bandit-feedback cases. (2) is essentially like asymptotic guarantees from a practical perspective. Those are the major limitations since addressing model-free and bandit-feedback cases, and providing sample complexity bounds are the main contributions of this paper compared to [65].", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-organized. We can see the effort to make the complex ideas accessible for the reader.\n- There is a comprehensive literature review citing more than a hundred papers.", "weaknesses": "- Algorithm descriptions, i.e., Algorithms 1 and 2, are confusing. For example, Algorithm 1 uses VIS-REG-PG as a function. However, VIS-REG-PG has not been presented as a function getting x as an input in Algorithm 2. The function REINFORCE has not been provided explicitly. Although REINFORCE is well-known, its explicit description in the paper could improve the paper's completeness.\n- Though the learning dynamics are claimed to be uncoupled, the agents including the adversary coordinate in collecting samples by playing according to some fixed strategy for some predetermined batch sizes. This contradicts with the adversarial nature of the adversary. Collecting samples is essential for model-free and bandit-feedback scenarios, which is a major contribution of the paper compared to [65].\n- The bounds on the number of gradient updates and the total sample complexity in the main result, Theorem 3.3, depend on (possibly) very large constant terms since they are proportional to $\\frac{1}{(1-\\gamma)^{57}\\epsilon^{10}}$ and $\\frac{1}{(1-\\gamma)^{93}\\epsilon^{16}}$, respectively. This may not be feasible for many practical applications, e.g., when the discount factor is close to $1$ and we want small approximation error $\\epsilon\\approx 0$. This is a limitation because another major contribution of this paper compared to [65] is the sample complexity bounds.\n- No numerical example is provided. Since the bounds appear large, numerical examples can give a better idea whether the algorithm presented is feasible for practical applications or not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their suggestions and comments and the time they took to review our work.\n\nWe would appreciate it if the reviewer reconsidered adding in the strengths of our paper any of the following:\n\n(i) The proof of convergence of inexact projected gradient descent for nonconvex optimization problems where the function has merely Holder-continuous gradients (Theorem 3.1).\n\n(ii) The elaborate way we managed to utilize standard MARL to prove convergence to a NE by utilizing finite samples.\n\n(iii) The way we proved that the MARL problem at hand boils down to optimizing a nonconvex function with Holder continuous gradients while we respect the requirement of minimal communication among agents during training.\n\n(iv) The involved mathematical arguments we use throughout the paper.\n\nBefore proceeding we ask the reviewer to see  Global Rebuttal:”Self-play is inevitable” for some clarifying points.\n\n\nFollowing we answer the weaknesses and questions the reviewer pointed out.\n\n> *”Algorithm descriptions, i.e., Algorithms 1 and 2, are confusing. For example, Algorithm 1 uses VIS-REG-PG as a function [..] The function REINFORCE has not been provided explicitly.”*\n\nThank you for pointing this out. Algorithm 2 should take as input the MDP that results from fixing the team players’ policies and return the optimal policy. As for the REINFORCE estimator please see section C.6.1.\n\n\n>*” The bounds on the number of gradient updates and the total sample complexity in the main result, Theorem 3.3, depend on (possibly) very large constant terms [...]. This is a limitation because another major contribution of this paper compared to [65] is the sample complexity bounds.”*\n\nIndeed, the dependence on the natural parameters of the game is large. Nevertheless, it does not stray a lot further than previous work in this field [2] and most importantly remains polynomial and beats the curse of the multiagents (it is polynomial in the number of players and the sum of individual action space sizes)! \n\nWe remind the author that these are upper bound for the worst case. Empirical performance need not be as bad and the theoretical guarantees might be tightened. Unquestionably though, we offer the first polynomial sample complexity guarantee and this can possibly motivate further work to tighten the analysis and design more efficient algorithms.\n\n\n> **Q**: What are the practical applications of adversarial team Markov games where learning equilibrium via the algorithm presented can be of interest? For example, step 3 in Algorithm 1 uses REINFORCE with the batch size of M where all agents, including the adversary, keep playing according to fix strategy so that the team members can collect samples and estimate . This contradicts with the adversarial nature of the adversary. Therefore, are we considering a simulated environment where we coordinate the team members and the adversary to learn some equilibrium of the underlying game?\n\nAnd also\n\n>*”Though the learning dynamics are claimed to be uncoupled, the agents including the adversary coordinate in collecting samples [..]. This contradicts with the adversarial nature of the adversary. Collecting samples is essential for model-free and bandit-feedback scenarios, which is a major contribution of the paper compared to [65].”*\n\nPlease see global rebuttal. The adversary should not be confused with what this name signifies in online optimization; it is merely the player that wants to maximze the function. \n\nFreezing in order to collect samples is commonplace in MARL theory papers and probably inevitable, see Global Rebuttal:Self-play is inevitable as to why.\n\n> **Q**: [...] does the algorithm presented reduce to a known learning algorithm for team Markov games (or Markov potential games)? If the team has a single player, does the algorithm reduce to a known learning algorithm for two-agent zero-sum Markov games? [...]?\nWhen the adversary has a singleton action, our algorithm is the same as the one proposed in [2] and computes a NE in any (Markov) potential game. Moreover, it handles utility functions that are not smooth but are merely Holder-continuous (a significantly weakened notion of continuity).\n\nIn the case that the team is singleton, our algorithm guarantees convergence to a NE of the underlying game. It is novel but suboptimal compared to the recent policy gradient methods that are designed for two-player zero-sum Markov games.\n\n > **Q**: Can the authors rewrite the algorithm descriptions? For example, what is the function VIS-REG-PG? Is it the steps from 2 to 6 or the entire for loop in Algorithm 2? This is confusing since Algorithm 1 and 2 have different epoch numbers $T_x$ and $T_y$ .\n\nThank you for pointing this out. The tuning of the parameters is precisely stated in Theorem C.3. We will revise our draft to make the pseudo-code to reflect that.\n\n> **Q**: Can the authors provide numerical examples? A comparison with the algorithm of [65] would also be very helpful to observe the impact of model-free and bandit-feedback cases on the convergence.\n\nWe will provide numerical experiments. Nevertheless, we would like to point out that not all theoretical papers need experiments. Comparing with [65] will of course give worse convergence rates as we are comparing full-information feedback versus inexact and stochastic feedback for a nonconvex optimization problem.\n\nWe again thank the reviewer for their comments and suggestions. We would deeply appreciate if they considered increasing their score.\n\nBest regards,\n\nThe authors\n\n[1] Daskalakis, C., Foster, D.J. and Golowich, N., 2020. Independent policy gradient methods for competitive reinforcement learning. NeurIPS\n\n[2] Leonardos, S., Overman, W., Panageas, I. and Piliouras, G., Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games. ICLR", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OscvpOesm7", "reviewer": "Reviewer_mZxv", "summary": "This paper provides multi-agent RL policy gradient method with polynomial guarantees (iteration and sample complexity) for the adversarial team Markov games problem setting.", "questions": "na", "limitations": "na", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper addresses the main open question from https://openreview.net/forum?id=mjzm6btqgV, that is, developing a policy gradient learning algorithm for the adversarial team Markov games problem. The paper is well-written.", "weaknesses": "After the first pass of this work, I did not have many weaknesses for this work as it *made good progress* from the recent ICLR 2023 work https://openreview.net/forum?id=mjzm6btqgV.\n\nBut after the following point:\n\n- Theorem 3.3, the main result, the polynomial dependence of both sample complexity and iterations on the **all** parameters is huge! Even with $\\gamma=0.9$, sample complexity scales as $10^{93}$. The number of atoms in the current universe scales as approx $10^{84}$. *This is disregarding other factors such as states, actions, etc into sample complexity!* Whereas, most practical MARL works like Diplomacy [6], Starcraft (https://deepmind.google/discover/blog/alphastar-mastering-the-real-time-strategy-game-starcraft-ii/), etc, beat human players at a reasonable training time (approx hours/days?). Moreover, ICLR 2023 work https://openreview.net/forum?id=mjzm6btqgV sample complexity scales as $10^{32}$ (all parameters included in this)\n\nI just can't get over what side I should choose: happy for such learning algorithm for ATMG problem or unsatisfied with the tools used with such huge *polynomial (but almost exponential with 10s of states, for example)* suboptimal guarantees.\n\nTo err on the side of this work and ML community progress, I am open to hearing any defense for this. Towards this, I am looking forward to your reply to the below two points. \n\n- Maybe one way is to show hardness results on some finite state-action ATMGs?\n- Please highlight some technical innovations in this work compared to the zero-sum MG sample complexity analysis. Are there points of improvement to be made?\n\nFuture work statement from line 329:\n\n> variance-reduction techniques to achieve a better sample complexity\n\nIs there any conjecture as to how much VR methods save in terms of sample complexity?\n\nAs I am in a dilemma, my current score reflects that. I'll update it after the authors-reviewers discussion period. Thanks!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the author for their comments that motivated us to reflect on our work. Following, we try to address your concerns.\n> *\"Theorem 3.3, the main result, the polynomial dependence of both sample complexity and iterations on the all parameters is huge! [..] This is disregarding other factors such as states, actions, etc into sample complexity![..] Moreover, ICLR 2023 work [..] sample complexity scales as (all parameters included in this)\"*\n\nFirst, the ICLR'23 work does not provide sample complexity results; their algorithm assumes access to a gradient oracle. Second, we want to remind the reviewer that the bounds we provide are upper bounds for the worst case. Empirical performance may be a lot better -- compare this to the exponential worst-case complexity of the simplex algorithm for linear programming.\n\nMaybe the bounds can be tightened but they remain the first polynomial bounds in the sample complexity and iteration complexity without access to the reward and transition functions. We remind the reviewer that providing polynomial guarantees with large coefficients are not uncommon for theoretical works that aim to learn a NE in MGs. For example, a highly-cited previous work [2], has a dependence that scales up to $10^{48.5}$ for a much simpler setting.\n\n> *”most practical MARL works [..] beat human players at a reasonable training time” (approx hours/days?)*\n\nThis is a very interesting point. Achieving super-human performance is easier than computing a Nash equilibrium. In order to achieve super-human performance, an AI agent needs only to be able to optimize against its opponents’ best responses. This is known as a Stackelberg equilibrium problem, which can be solved in polynomial time even for a general-sum game [1]. \n\n> *”I just can't get over what side I should choose: happy for such learning algorithm for ATMG problem or unsatisfied with the tools used with such huge polynomial (but almost exponential with 10s of states, for example) suboptimal guarantees.”*\n\nWe stress that polynomial complexity is a very important theoretical qualitative and has quantitative differences from an exponential one. Whether our guarantee on the upper-bound of the worst-case is suboptimal is up to discussion and it should be formally argued (see global rebuttal). The degrees of the polynomial are not significantly larger than previous work on simpler settings [2].\n\n>*”Maybe one way is to show hardness results on some finite state-action ATMGs?”*\n\nProving some lower bounds for the complexity of computing a NE in ATMGs is a very interesting future research direction. However, this paper aims to give the first theoretical polynomial upper bounds for model-free learning of NE in ATMGs. Notwithstanding, deriving some lower bounds goes very well beyond the scope of our paper and would probably be a standalone result for a new paper.\n\n>*”Please highlight some technical innovations in this work compared to the zero-sum MG sample complexity analysis. Are there points of improvement to be made?”*\n\nWe  highlight the technical challenges we faced and overcame.\n\nNamely, all of the following properties hold in a zero-sum MG:\n\n(i) the duality gap is zero as proven by Shapley; i.e., $\\min_x \\max_y V(x,y) = \\max_y \\min_x V(x,y)$\n\n(ii) the value of all Nash equilibria is the same\n\n(iii) the NEs are exchangeable, e.g. let two NEs $(x,y)$ and $(x’,y’)$. Then, policy profiles $(x’,y)$ and $(x,y’)$ will also be an NE.\n\n(iv) the optimization landscape is that of a hidden-convex–hidden-concave function.\n\n(v) any Markovian coarse-correlated equilibrium policy can be marginalized to a product policy that will be a NE.\n\nOn the other hand, (i)-(v) generally fail to hold for ATMGs even when the game has only one state (i.e., in normal-form games).\n(i)-(iii) are indispensable in the design and guarantees of existing algorithms for zero-sum MGs and since they fail to hold for ATMGs, they cannot be utilized.\n\nDespite all these challenges, we manage to show that we do not need access to the reward and transition functions of the game in order to compute a NE. Additionally, this task can be achieved when the agents only collect a finite number of sample trajectories.\n\nTo do so, we introduce a double-loop policy gradient algorithm. In the inner-loop the adversary optimizes a regularized function and in the outer loop the team player take independent gradient steps.\n\nThe key difference between our work and [65] is that of the regularization. Our work remains the first to show that such regularization makes the outer-loop process equivalent to optimizing a nonconvex function with Holder continuous gradients (a significantly weaker property compared to the omnipresent assumption of Lipschitz continuity in ML and RL settings).  Further, the team agents have inexact gradient feedback.\nThe *inexactness* is due to the gradient of the regularizer is not zero w.r.t. the team agents’ policies and the team agents have no information about the regularizer (otherwise we would allow a significant communication among agents). \n\nBut:\n\nThe stochasticity error (bias and variance) are bounded by standard techniques (the REINFORCE gradient estimator along $\\zeta$-greedy parametrization).\n\nThe inexactness error is controlled by very carefully choice of the regularizing coefficient so that it strikes a balance to not make the Holder constant too large while maintaining a inexactness error small (these two objectives are in tension with each other).\n\nWe again thank the reviewer for their time and giving us the chance to elucidate our work. We hope that we have made parts of our work clearer and easier to evaluate. We would really appreciate if you would consider raising our score.\n\nBest regards,\n\nThe authors\n\n[1] Conitzer, V. and Sandholm, T., 2006, June. Computing the optimal strategy to commit to. EC\n\n[2] Daskalakis, C., Foster, D.J. and Golowich, N., 2020. Independent policy gradient methods for competitive reinforcement learning. NeurIPS", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UQgjkFKtJr", "reviewer": "Reviewer_hE5h", "summary": "The paper studies policy gradient methods for computing a Nash equilibrium in adversarial team Markov games. The authors employ an occupancy measure-based regularization to deal with this non-convex minimax optimization problem. They develop a policy gradient method that allows all team members to take policy gradient steps independently, while the adversary takes regularized policy gradient steps. The authors prove that this new method finds a near Nash equilibrium in polynomial iteration/sample complexities, under some mild conditions. The authors further show the tractability of computing a near saddle point for a class of structured non-convex minimax optimization problems.", "questions": "Here are other questions for improvement.\n\n- What rewards do team take? It is not clear from Section 2.2.\n\n- What is reformulation in line 207? a confusing inter product notation. \n\n- unclear notation: $\\Delta(\\mathcal{A})$, $\\boldsymbol{r}(\\boldsymbol{x})$, $\\hat{\\boldsymbol{g}}_i$, $\\mathcal{K}^{(t)}$, $\\boldsymbol{x}^{(T)}$, etc.\n\n- Why do you need $\\zeta$-greedy policy? How does policy gradient projection work in Algorithms 1-2? \n\n- wrong index: $k\\in[n]$ lines 3-4 of Algorithm 1.", "limitations": "No", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- The authors propose a policy gradient method to find a near Nash equilibrium of adversarial team Markov games, with polynomial iteration/sample complexities. This policy gradient method appear to be new for this problem. \n\n- A new regularization technique is introduced for the adversarial player, which avoids using linear programming in the existing method.", "weaknesses": "- The paper has several writing issues: (i) Introduction with two paragraphs is discouraged for NeurIPS; (ii) Technical overview is verbose, and not all the content is original to this paper; (iii) The preliminary section is cumbersome and contains confusing notation for occupancy measures; (iv) The connection between stochastic gradient and team problems in Section 3 reads ambiguous; (v) The results in Section 4 are not directly related to adversarial team games.\n\n- The motivation for using the policy gradient method to solve adversarial team Markov games is not explained from the perspective of application. It is hard to evaluate the broad impact of this work.\n\n- The motivation for using regularization based on occupancy measures is not well presented. The authors implement regularization directly in Algorithm 1 without explaining the reasons behind it.\n\n- It is not clear why bandit feedback is important in adversarial team Markov games since the proposed policy gradient method assumes simulated game-play, which is not a typical online learning algorithm. \n\n- The proposed policy gradient method assumes policy coordination between team and adversary, which often is not the case in practice. \n\n- Except for regularization for the adversarial player, other techniques are quite standard for policy gradient methods. The novelty of the proposed method is limited or the effectiveness of regularization should be emphasized. \n\n- The polynomial iteration/sample complexities of the proposed policy gradient method are highly sub-optimal in terms of rates and problem dependence.\n\n- The proposed policy gradient method is limited to problems with small state/action spaces, leading dimension scalability issue. \n\n- Conditions for Theorem 3.3 to hold are not explained, hiding limitations of the proposed policy gradient method. Also, the proof of Theorem 3.3 in Appendix should be presented in a more readable way. \n\n- There are no experimental justifications of the proposed policy gradient method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable time and recommendations. We are committed to enhancing the quality of our draft and will incorporate your suggestions.\nBeginning, could the reviewer specify what they find lacking in our paper's soundness? Soundness in a theoretical paper pertains to the correctness of mathematical arguments, and we are eager to identify any flaws in our reasoning.\nWe proceed to answer the reviewer’s questions and comment on the highlighted weaknesses:\n\n> **Q**: What rewards do team take?\n\nEvery agent $i$ gets a reward $r_i = - \\frac{1}{n} r$. And it holds that $\\sum_{i}^n r_i + r = 0$.\n\n> **Q** : What is reformulation in line 207? \n\nThe reformulation in line 207 is the very common reformulation of the value function from a function of the policy to a funciton of the state-action measures, see Section 2 in [1].  It is equal to $\\sum_{s,b}r(s,x,b)\\lambda(s,b) = r(x)^\\top \\lambda$. See comments for a simple explanation.\n\n> **Q** : Why do you need $\\zeta$-greedy policy? How does policy gradient projection work in Algorithms 1-2?\n\nThe $\\zeta$-greedy policy ensures that the variance of the reinforce gradient estimator is bounded. See lines 222-226.\n\nAlmost identical to project to the non-truncated simplex, for a potentially infeasible $x^+ = x - \\eta \\nabla f(x)$, projection is defined as the $ \\arg \\min_{x' \\in \\mathcal{X_\\zeta} } \\frac{1}{2} || {x^+ - x'} || ^2  $. This optimization problem is solved in polynomial time using quadratic programming.\n\n\n> **Q** :  wrong index: $k\\in[n]$ lines 3-4 of Algorithm 1.\n\nThank you for pointing this out, it is $i\\in[n]$.\n\n> unclear notation: $\\Delta(\\mathcal{A}), \\boldsymbol{r}(\\boldsymbol{x}), \\hat{\\boldsymbol{g}}_i, \\mathcal{K}^{(t)}, \\boldsymbol{x}^{(T)}$ etc.\n\nWe will add more definitions\n \n$\\Delta(\\mathcal{A})$: the very standard notation of a simplex supported on $\\mathcal{A}$.\n\n$\\boldsymbol{r}(\\boldsymbol{x}) \\in \\mathbb{R}^{|\\mathcal{S}| \\times |\\mathcal{B}|}$ is the expected reward of the adversary.\n\n$ \\mathcal{K}^{(t)} $ is a batch of trajectories.\n\n$\\hat{\\boldsymbol{g}}_i $ is the gradient estimate at a given iteration of the algorithm.\n\n$\\boldsymbol{x}^{(T)}$ is the vector of the concatenated policies of the team at iteration $T$.\n\n---\n\nWith regards to the highlighted weaknesses of our paper:\n> *\"(ii) Technical overview is verbose, and not all the content is original to this paper\"*\n\nWe present a detailed technical overview, using various tools to address nonconvex-nonconcave minmax problem challenges. This clarity helps readers grasp the necessity and functionality of our arguments.\nWhile not all content is entirely original, as typical in most papers, our work builds on and advances existing research through rigorous scientific dialogue.\n\n>*”The results in Section 4 are not directly related to adversarial team games.”*\n\nWe dedicated a separate section to generalize our results particularly. They are directly related from an optimization perspective.\n\n> *\"The motivation for using regularization based on occupancy measures is not well presented. The authors implement regularization directly in Algorithm 1 without explaining the reasons behind it.\"*\n\nWe believe this is inaccurate. We have actually dedicated multiple lines of our text for this purpose. Namely:\n* In the Technical Overview: Lines 107-132\n* Lines 281-285\n* Section C.3\n* Lines 982-1004\n\n> *“It is not clear why bandit feedback is important in adversarial team Markov games since [...]”*\n\nSee global rebuttal (Self-Play is Inevitable).\n\nThis assumption is inaccurate. Coordination only occurs during the learning process: players pause policy updates to collect trajectory samples, a standard practice in most theoretical AGT/MARL papers (e.g., [5-13]). The adversary optimizes its policy before team agents independently perform a gradient step. The first is a common standard in our field, and the second is a minor assumption.\n\n>*\"The motivation for using the policy gradient method to solve adversarial team Markov games is not explained from the perspective of application\"*\n\nPlease see global rebuttal (Importance of Policy Gradient Methods).\n\n> *”no experimental justifications”*\n\nSee global rebuttal.\n\n> *” Except for regularization for the adversarial player, other techniques are quite standard for policy gradient methods…”*\n\nWe use standard techniques policy gradient techniques on purpose. The idea of this paper was to take methods that are broadly utilized in (MA)RL and prove that they can be minorly tweaked to get provable guarantees for the very challenging task of computing a NE. \n\nPlease see the “Novelty in our paper” note in the global rebuttal.\n\n> *”The polynomial iteration/sample complexities of the proposed policy gradient method are highly sub-optimal in terms of rates and problem dependence.”*\n\nThis work offers the first proof that an algorithm of polynomial sample complexity exists for NE in ATMGs. We cannot accept the sub-optimality claim without any formal argument.\n\nAlso, see the global rebuttal.\n\n> *\"The proposed policy gradient method is limited to problems with small state/action spaces, leading dimension scalability issue.\n\"*\n\nRL methods typically don't scale well with large action and state spaces unless function approximation is used along certain extra assumptions on the MDP/MG. Recently, function approximation in multi-agent reinforcement learning (MARL) has gained theoretical interest. See [3] for recent results.\n\n\n> *”Conditions for Theorem 3.3 to hold are not explained, hiding limitations of the proposed policy gradient method. Also, the proof of Theorem 3.3 in Appendix should be presented in a more readable way.“*\n\nWe do not hide any limitations. The conditions for theorem 3.3 to hold is merely that the Markov game follows the structure of an ATMG as defined in Section 2. This theorem is general.\n\nIn lines 981-996 we offer a small summary of the steps of our arguments. We welcome more suggestions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their valuable comments. We will integrate their suggestions and corrections in our next draft.  

As a disclaimer, our focus is on the theoretical advancements in algorithmic game theory and multi-agent reinforcement learning (MARL). We explicitly do not make claims about the immediate practicality of our algorithms. While our experiments (see accompanying PDF) suggest favorable empirical performance, a full assessment of their practical utility lies beyond the scope of this paper. 


__Novelty in our paper__

Our main novelty lies in the techniques we use to get guarantees of adding regularizer to the adversary’s maximization routine. Here are the challenges we addressed:

1. Independent gradient steps by both players can diverge from the NE. In [4], adversary best-responses before team agents' gradient steps lead to a function $\Phi(x) = \max_{y} V(x,y)$, converging to a strategy $x^*$. Extending to NE $x^*, y^*$ requires knowledge of reward and transition functions, making it a planning problem, not RL. Additionally, $\Phi$ is not differentiable.

2.  Our work introduces a state-action occupancy regularizer and further proves that $\Phi^\nu$ is differentiable but has a Hölder-continuous (non-Lipschitz) gradient.

3. Unlike the ubiquitous Lipschitz-gradient assumption in RL and ML, we prove that stochastic projected gradient descent can converge to a stationary point in a constrained nonconvex optimization problem with a Holder gradient.

4. Agents are only allowed to observe their own reward and state trajectory samples. This disables team agents to get an exact gradient of the regularized function $\Phi^\nu$. (This inexactness comes from the fact that estimating the gradient of the regularizer requires observing the adversary’s actions)

5. Nevertheless, the coefficient of the regularizer controls the error between the gradient the team agents estimate and the real gradient of the function.

6. In Section 4, we show that our results can be significantly generalized to the setting of any minmax optimization problem of a nonconvex--hidden-strongly-concave objective.


__Importance of Policy Gradient Methods__

Policy gradient (PG) and policy optimization (PO) methods have dominated modern RL theory and practice. The policy gradient methods of PPO and TRPO are widely used by practitioners (e..g OpenAI).

In MARL, PG/PO methods manage to *break the curse of multi-agents* (the complexity scales exponentially with the number of players) and require minimal to no communication between agents. Further, PG/PO methods can be used alongside neural networks.

We tackle the case of tabular ATMGs with policy gradient methods making significant headspace towards the provable convergence of methods that involves neural nets.

__Self-Play is Inevitable__

In [1], it was proven that there is no computationally efficient algorithm that achieves no-regret even in 2-player 0-sum MGs. This means that self-play inevitable. We follow the *independent learning protocol* that is ubiquitous in contemporary MARL theory (e.g. [2], [3]).

Bandit feedback is a term that refers to only getting feedback for the action the agent takes. It does not need to be reserved for the online learning optimization framework. All agents collect samples of trajectories and then estimate their gradients. The adversary is the name of player that maximizes the value that the team tries to minimize. The adversary of an ATMG should not be confused with what "adversary" signifies in online optimization. ($r_{adversary} = \sum_{i=1}^{n}r_{player-i}$).

__Polynomial Iteration and Sample Complexity__

We emphasize that our work contributes *the first algorithm with sample complexity bounds that are polynomial* in the number of players, $1/\epsilon$, the sum of the action-space sizes, $\gamma$, and other relevant parameters. [4] did not offer any sample complexity bounds. Previously, it was not even known whether this is possible and we cannot know how --if at all-- suboptimal this algorithm is without any formal reasoning and arguments. It is fair that the reviewers formally argue why our bound is suboptimal -- what optimization lower bound is invoked and serves as the benchmark to compare to?

In theoretical research, demonstrating that polynomial iteration/sample complexity holds is always of significant interest, regardless of the polynomial's degree. From a theoretical computer science perspective, the gap between exponential and polynomial complexity is abysmal. For example, the discovery of an algorithm for the Traveling Salesman Problem with a complexity of even $O(n^{10,000})$ would revolutionize our understanding of computer science.

For the significantly simpler setting of two-player zero-sum MG the sample complexity of the algorithm in [2] scales with $1/(1-\gamma)^{48.5}$ and $\epsilon^{-12.5}$.

__Experiments__

We present the confidence intervals of the best-iterate's NE-Gap across iterations and the NE-Gap for every iteration of ISPNG when running in randomly generated games, where $S=4, \gamma=0.9, |A_1| = |A_2| = |B| = 3$, transition and reward functions are randomly generated. We observe that in these games the algorithm converges to a NE much faster than the proposed theoretical upper bound. See the accompanying plots.

Sincerely,

The authors


---

[1] Bai, Y., Jin, C. and Yu, T., 2020. Near-optimal reinforcement learning with self-play. NeurIPS

[2] Daskalakis, C., Foster, D.J. and Golowich, N., 2020. Independent policy gradient methods for competitive reinforcement learning. NeurIPS

[3] Ding, D., Wei, C.Y., Zhang, K. and Jovanovic, M., 2022, June. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. ICML

[4] Kalogiannis, F., Anagnostides, I., Panageas, I., Vlatakis-Gkaragkounis, E.V., Chatziafratis, V. and Stavroulakis, S.A., Efficiently Computing Nash Equilibria in Adversarial Team Markov Games. ICLR

Meta-review: This paper considers the problem independent learning/decentralized equilibrium computation in multi-agent reinforcement learning (MARL). The paper focuses on infinite-horizon adversarial team Markov games (ATMGs), where a collection of agents with a common reward function compete against a single opponent (the "adversary"). The main result is to provide a new decentralized learning algorithm based on independent policy gradient methods which achieves polynomial sample complexity in finite state spaces. This addresses a question left open by Kalogiannis et al (2023), who give similar guarantees under the additional assumption that rewards and dynamics are known.

This paper makes a solid and clear contribution by providing the first finite-sample guarantees for independent learning in ATMGs. The core techniques in the paper, which apply to non-convex/hidden-concave min-max optimization with non-Lipschitz gradients, are also likely to have broader interest to the optimization theory community. 

The initial set of reviewers generally agreed with the significance of the main results, they raised a number of small issues, including 1) poor polynomial dependence on parameters in the sample complexity guarantees, and 2) the fact that while the algorithm is decentralized, it requires players to follow a set schedule. However, these drawbacks are somewhat superficial, and they are shared by all prior work from this line of research (e.g., Daskalakis et al. (2020)). 

Since the paper received borderline scores and the reviews above had limited depth, I recruited an expert reviewer (YssW) who has worked directly on this topic during the final discussion period. They agreed that the techniques in this paper are novel and non-trivial, and championed acceptance. I agree with this conclusion. While it would certainly be interesting to see these issues raised by the other reviewers addressed in future work, I believe this work merits acceptance in its current state. 

I strongly encourage the authors to address the comments raised by reviewer YssW in the final revision, as well as highlight the limitations of the work raised by other reviewers (e.g., large polynomial sample complexity) up front.
Decision: Accept (poster)