Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem

Authors: fivos  kalogiannis
jingming  yan
ioannis  panageas
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:49:52

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).

Main paper: 
 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 achieved super-human 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 a 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 a "favorable outcome" is formally defined through concepts like a Nash equilibrium and a (coarse) correlated equilibrium. Although computing Nash equilibria is generally computationally intractable-even in two-player games without states [28, 24] --it becomes tractable in fully cooperative settings like Markov potential games [114, 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 a Markov Game in which n 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. Minmax 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-nonconcave functions which pose substantial challenges. Typically, the aim is to approximate saddle-points of f (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, we 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?(⋆)Let us provide some context before stating our main results. An infinite-horizon adversarial team Markov game (ATMG) is characterized by a finite state-space S, n team players, each equipped with a finite action-space A i , i ∈ {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 value function is defined as the discounted expected sum of their rewards, where the discount factor is γ ∈ [0, 1). An approximate Nash equilibrium is a 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 of Theorem 3.3). There is a learning algorithm (ISPNG) that uses bandit feedback and guarantees convergence to an ϵ-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 arepoly 1 ϵ , |S|, n k=1 |A i | + |B|, 1 1 -γ .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 a number of iterations and samples that is polynomial in the approximation error and the description of the game. Further, it manages to beat the curse of multi-agents [62] -i.e., its iteration and sample complexity depends onn k=1 |A i | instead of n k=1 |A i |.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-a notion of continuity weaker than that of Lipschitz. Finally, we contribute a general result that guarantees convergence to a saddle-point in functions that are nonconvex-hidden-strongly-concave.The problem of computing an approximate Nash equilibrium in an adversarial team Markov game boils down to computing an approximate saddle-point (x * , y * ) of the adversary's value function V (x, y); see Definition 2.3. The variables x 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 gradient 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 approximate best response for that player.The problem of computing an approximate saddle-point (x * , y * ) of the objective V (x, y) poses computational challenges due to its nonconvex-nonconcave nature. Previous work [65] showed that one can compute an approximate saddle-point (x * , y * ) of V , by first obtaining an approximate stationary point x * of Φ(x) = max y V (x, y) through a Moreau envelope argument and then extending it to (x * , y * ). The proof of 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 to 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.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 is to consider the adversary's value function as a function F of the adversary's state-action visitation measure λ, F (x, λ) := V (x, y), and the addition of a regularizing term -ν 2 ∥λ∥ 2 (ν can be thought of as a small positive scalar). As a result, the max function of the regularized value function, Φ ν (x) := max λ∈Λ(x) F (x, λ) -ν 2 ∥λ∥ 2 , is differentiable, where Λ(x) ⊆ ∆ |S||B| denotes the feasibility set of λ and depends on x. 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 a function with a unique maximizer circumventing the necessity of solving a 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 λ, the problem boils down to learning an approximate saddle-point of a nonconvex-strongly-concave function with coupled constraints. Coupled constraints are a type of constraints that cannot be expressed as a Cartesian product (the main well-studied setting in min-max optimization [63] ), i.e., the feasibility set Λ(x), depends on x. The first challenge towards handling the coupled constraints is to argue that ∇Φ ν is Hölder-continuous which is a notion of continuity weaker than Lipschitz continuity (see Definition 2.1). Specifically, in Theorem 3.2, we show that Φ ν (x) is weakly-smooth, or equivalently, ∇Φ ν is Hölder-continuous. It seems unlikely that we could use Moreau envelope techniques to prove convergence of stochastic projected gradient descent on a weakly-smooth function. The next step of our proof is to transfer the weakly-smooth nonconvex optimization problem into a 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 ∇Φ ν (x) in both deterministic and stochastic settings.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 chain-induced by the players' fixed policies-spends at state s (respectively, at a state action pair (s, b)) starting from initial state s ′ . Each visit is weighted by a discount factor γ h , where h is the visit time. Notably, in [3] it is defined as a probability measure, meaning that for an initial state distribution ρ, the discounted state visitation distribution sums to 1. For convenience, we will use the unnormalized definition from [88, Chapter 6.10], which sums to 1 1-γ . 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 ρ ∈ ∆(S) and a stationary joint policy π ∈ Π, we define the state visitation frequency d π s as follows:d π s (s) = ∞ h=0 γ h P(s h = s|π, s 0 = s).Additionally, expanding the definition, we defined π ρ (s) = E s∼ρ [d π s (s)] .For convenience, the expression d x,y ρ (s) is utilized to represent the state visitation measure resulting from the policies (x, y) ∈ X × Y. Fact C.1. Let MDP, M(S, B, P, r, γ). Let a policy π ∈ ∆(B) |S| . For the corresponding state-action visitation measure λ ∈ R S×B and the state visitation measured π ρ ∈ R S , it holds that, λ s,b (π) = d π ρ (s)π(s, b), ∀s ∈ S, ∀b ∈ B.A 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 ρ ∈ ∆(S) be a full-support distribution over states, and Π be the joint set of policies. We define the distribution mismatch coefficient D asD m := sup π∈Π d π ρ ρ ∞ ,whered π ρρ denotes element-wise division.The following theorem that relates policies and visitation measures is essential to our analysis. An implication of the latter theorem is the fact that λ(•; x) is a "1-1" mapping between policies and visitation measures. Following, we see that this mapping is also Lipschitz-continuous and smooth (see Lemmas C.1 to C.3). Lemma C.1. For any initial distribution ρ ∈ ∆(S), function V ρ is L-Lipschitz and ℓ-smooth withL := √ n i=1 |Ai|+|B| (1-γ) 2and ℓ :=2γ( n i=1 |Ai|+|B|) (1-γ) 3, in other words|V ρ (x, y) -V ρ (x ′ , y ′ )| ≤ n i=1 |A i | + |B| (1 -γ) 2 ∥(x, y) -(x ′ , y ′ )∥ ; ∥∇V ρ (x, y) -∇V ρ (x ′ , y ′ )∥ ≤ 2γ ( n i=1 |A i | + |B|) (1 -γ) 3 ∥(x, y) -(x ′ , y ′ )∥ .Proof. The proof follows from Lemma 4.4 in [68] .Lemma C.2. Let λ ∈ R |S||B| be the state-action visitation measure for the adversary, then λ is L λ -Lipschitz continuous and ℓ λ -smooth w.r.t to policy (x, y). Specifically, we haveEQUATIONEQUATION(1 -γ) 3 (∥x -x ′ ∥ + ∥y -y ′ ∥) .Proof. Each λ s,b can be considered as a value function for the given state s and the reward functionis r(a ′ , b ′ ) = 1(b = b ′ ).Then by applying Lemma C.1, we haveEQUATIONEQUATIONFrom Equation ( 6) we get∥λ (y; x) -λ (y ′ ; x ′ )∥ ∞ ≤ i |A i | + |B| (1 -γ) 2 • (∥x -x ′ ∥ + ∥y -y ′ ∥) .This implies∥λ (y; x) -λ (y ′ ; x ′ )∥ ≤ |S||B| ∥λ (y; x) -λ (y ′ ; x ′ )∥ ∞ ≤ |S||B| i |A i | + |B| (1 -γ) 2 • (∥x -x ′ ∥ + ∥y -y ′ ∥) ≤ |S| ( i |A i | + |B|) (1 -γ) 2 • (∥x -x ′ ∥ + ∥y -y ′ ∥) .Similarly, from Equation ( 7), we have∥∇λ s,b (y; x) -∇λ s,b (y ′ ; x ′ )∥ ≤ 2γ ( i |A i | + |B|) (1 -γ) 3 • (∥x -x ′ ∥ + ∥y -y ′ ∥) . Thus ∥∇λ (y; x) -∇λ (y ′ ; x ′ )∥ F ≤ |S||B| • max s∈S,b∈B ∥∇λ s,b (y; x) -∇λ s,b (y ′ ; x ′ )∥ ≤ 2γ |S||B| ( i |A i | + |B|) (1 -γ) 3 • (∥x -x ′ ∥ + ∥y -y ′ ∥) .Where ∥•∥ F denotes the Frobenius norm of the matrix. Finally, we have∥∇λ (y; x) -∇λ (y ′ ; x ′ )∥ ≤ ∥∇λ (y; x) -∇λ (y ′ ; x ′ )∥ F ≤ 2γ |S||B| ( i |A i | + |B|) (1 -γ) 3 • (∥x -x ′ ∥ + ∥y -y ′ ∥) ≤ 2γ |S| ( i |A i | + |B|) 3 (1 -γ) 3 • (∥x -x ′ ∥ + ∥y -y ′ ∥) ≤ 2 |S| ( i |A i | + |B|) 3 (1 -γ) 3 • (∥x -x ′ ∥ + ∥y -y ′ ∥) . Lemma C.3. Consider λ inv (λ(y; x)) := λ s,b (y;x) b ′ λ s,b ′ (y;x), which is a function that maps the adversary's state-action visitation measure λ(y; x) ∈ Λ(x) to the adversary's policy y ∈ Y. For any fixed team policy x, λ inv is L λinv -Lipschitz continuous with respect λ where L λinv = max s∈S 2 ρ(s)(1-γ) . Specifically, it holds that ∥y -y ′ ∥ ≤ L λinv ∥λ(y; x) -λ(y ′ ; x)∥ .Proof. Take the partial derivative of λ inv (λ), we have∂ ∂λ s,b λ s,b b ′ λ s,b ′ = 1 b ′ λ s,b ′ - λ s,b ( b ′ λ s,b ′ ) ≤ 1 b ′ λ s,b ′ + λ s,b ( b ′ λ s,b ′ ) ≤ max s∈S 1 ρ(s) + 1 ρ(s)(1 -γ) ≤ max s∈S 2 ρ(s)(1 -γ) .This implies the Lipschitz continuity.The Regularized Value Function.Lemma C.4. Function V ν ρ (x, y) := V ν ρ (x, y) -ν 2 ∥λ (y; x)∥ 2 is L ν -Lipschitz continuous and ℓ ν -smooth, where L ν := L + νL λ 2(1-γ) and ℓ ν := ℓ + νℓ λ 2(1-γ) + νL 2 λ 2 .Proof. For Lipschitz continuity, we haveV ν ρ (x, y) -V ν ρ (x ′ , y ′ ) ≤ |V ρ (x, y) -V ρ (x ′ , y ′ )| + ν 2 ∥λ (y; x)∥ 2 -∥λ (y ′ ; x ′ )∥ 2 ≤ |V ρ (x, y) -V ρ (x ′ , y ′ )| + ν 2 max x,y ∥λ (y; x)∥ • ∥λ (y; x)∥ -∥λ (y ′ ; x ′ )∥ ≤ |V ρ (x, y) -V ρ (x ′ , y ′ )| + ν 2 • 1 1 -γ ∥λ (y; x) -λ (y ′ ; x ′ )∥ ≤ L + νL λ 2(1 -γ) • (∥x -x ′ ∥ + ∥y -y ′ ∥) .For smoothness, denote the Jacobian matrix of λ(y; x) w.r.t to (x, y) by J λ (x, y), it holds thatEQUATION≤ ℓ λ 1 -γ + L λ • L λ • (∥x -x ′ ∥ + ∥y -y ′ ∥).Where in (8) we used the fact that ∥J λ (x ′ , y ′ )∥ ≤ L λ . We conclude that∇V ν ρ (x, y) -∇V ν ρ (x ′ , y ′ ) = ∇V ρ (x, y) -∇V ρ (x ′ , y ′ ) + ν 2 ∇ x ∥λ (y; x)∥ 2 -∇ x ∥λ (y ′ ; x ′ )∥ 2 ≤ ∥∇V ρ (x, y) -∇V ρ (x ′ , y ′ )∥ + ν 2 ∇ x ∥λ (y; x)∥ 2 -∇ x ∥λ (y ′ ; x ′ )∥ 2 ≤ ℓ + νℓ λ 2(1 -γ) + νL 2 λ 2 • (∥x -x ′ ∥ + ∥y -y ′ ∥).Finally, we compute the Lipschitz continuity parameter of the reward vector that we already used in our previous claims. Lemma C.5. Let r(x) be the reward function for the adversary when the team is playing policy x.Then it holds that ∥r(x) -r(x ′ )∥ ≤ L r ∥x -x ′ ∥ , where L r = √ S ( n i=1 |A i | + B) .Proof.∥r(x) -r(x ′ )∥ ≤ |S||B|∥r(x) -r(x ′ )∥ ∞ = |S||B| max s,b |r(s, x, b) -r(s, x ′ , b)| = |S||B| i=1 |A i |∥x -x ′ ∥ (9) ≤ |S| n i=1 |A i | + B ∥x -x ′ ∥.Where (9) follows from Claim D.9. in [65] . 
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] := {1, . . . , n}. We use superscripts to denote the (discrete) time index, and subscripts to index the players. We use boldface for vectors and matrices; scalars will be denoted by lightface variables. We define 1 .∥ • ∥ 2 , ∥ • ∥ 1 , ∥ • ∥ ∞ to be the ℓ 2 -norm,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 a weaker notion of Lipschitz gradient continuity. Definition 2.1 (p-Hölder continuous gradient). A function ϕ : R d → R is said to have a (ℓ p , p)-Hölder continuous gradient if for every z, z ′ ∈ R d , it holds that:∥∇ϕ(z) -∇ϕ(z ′ )∥ 2 ≤ ℓ p ∥z -z ′ ∥ p 2 .When p = 1, we retrieve the definition of an ℓ-smooth function.Throughout, following standard conventions, we will refer to functions for which the gradient is p-Hölder continuous with a p < 1 as weakly-smooth. We state the notions of first-order stationarity relevant to our work. Definition 2.2 (ϵ-FOSP). In the context of the constrained minimization problem min z∈Z ϕ(z), a point z ∈ Z is said to be an ϵ-approximate stationary point if,⟨-∇ z ϕ(z), z ′ -z⟩ ≤ ϵ, ∀z ′ ∈ Z.Similarly, we will define an ϵ-approximate saddle-point for the constrained min-max optimization problem min X max Y f (x, y).Definition 2.3 (ϵ-SP). Let a function f : X × Y → R. A point (x, y) ∈ X × Y is said to be an ϵ-approximate saddle-point (or ϵ-FOSP for the min-max problem) if, -∇ x f (x, y) ⊤ (x ′ -x) ≤ ϵ, ∀x ′ ∈ X ; ∇ y f (x, y) ⊤ (y ′ -y) ≤ ϵ, ∀y ′ ∈ Y.An adversarial team Markov game is the Markov game extension of normal-form adversarial team games [98] . The game takes place in an infinite-horizon discounted setting where a team of identicallyinterested players compete against one adversarial player, the adversary. We can formally define an adversarial team Markov game as a tuple Γ(S, [n + 1], A, B, r, P, γ, ρ), where:• S is the finite set of states, or state-space, with cardinality S := |S|; • [n + 1] is the set of players, with the first n players belonging to the team and the last one being the adversary;• A = × n i=1 A i is the finite set of the team's joint actions (or, team's action-space), while A i is the i-th player's action-space; respectively B is the adversary's action-space; further,A := max i∈[n] |A i | and B := |B|; • r : S × A × B → [0, 1] is the adversary's reward function; • P : S × A × B → ∆(S) is transition probability function; • γ ∈ [0, 1) is the discount factor; • ρ ∈ ∆(S)is the initial state distribution. We assume that ρ is of full-support, ρ(s) > 0, ∀s ∈ S.Every team player i ∈ [n] gets the same reward and the sum of team players' rewards are equal to the adversary's loss, i.e.,n i=1 r i (s, a, b) = -r(s, a, b).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 i, a stationary policy π i is defined as a mapping from any given state to a probability distribution over possible actions, whereπ i : S ∋ s → π i (•|s) ∈ ∆(A i ).A policy π i is described as deterministic when, for any state, it selects a particular action with probability of 1. To simplify, we denote the policy spaces for the team and the adversary as Π team : S → ∆(A) and Π adv : S → ∆(B), respectively. Additionally, the combined policy space for all participants can be represented as Π : S → ∆(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 i is defined as ∆(A i ) S , with π i = x i , such that the probability of choosing action a in state s, x i,s,a , equals π i (a|s). By the usual game-theoretic convention, π -i denotes the policy of all agents apart from i. For the adversary, Y is set as ∆(B) S , with π adv = y, so that y s,a = π adv (a|s).Having defined policies, we can introduce some standard shortcut notations such as r(s, The Value Function. The value function V s , for a given state s ∈ S, is defined as the adversary's expected total discounted reward over time under a combined policy (π team , π adv ) from the policy space Π, with x = π team being the aggregation of policies (π 1 , . . . , π n ). Formally, this is represented asV s (x, y) := E x,y ∞ h=0 γ h r(s h , a h , b h ) s 0 = s ,where the expected value is calculated over the distribution of trajectories generated by the policies x and y. If the initial state is instead sampled from a distribution ρ, the value function is expressed asV ρ (x, y) = E s∼ρ [V s (x, 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 ρ ∈ ∆(S), transition matrix P, a team policy x, and a policy y ∈ Y, we define the station-action visitation measure of the adversary λ(y; x) as follows:λ s,b (y; x) := ∞ h=0 γ h P(s h = s, b h = b|x, y, s 0 ∼ ρ).Where λ s,b (y; x) denotes the (s, b) th entry of λ(y; x).As we will further discuss in the appendix (Appendix C.1), the correspondence between y and λ is "1-1" for a fixed team policy x. This property is crucial for our contributions.A key property of the value function V ρ is that it can be rewritten as a concave function of the state-action visitation measure:V ρ (x, y) = r(x) ⊤ λ(y; x).Definition 2.5 (ϵ-NE). A product policy x * , y * ∈ X × Y is called an ϵ-approximate Nash equilibrium for an ϵ ≥ 0, whenV ρ (x * , y * ) ≤ V ρ ((x ′ i , x * -i ), y * + ϵ, ∀x ′ i ∈ X i , ∀i ∈ [n]; and V ρ (x * , y * ) ≥ V ρ (x * , y ′ ) -ϵ, ∀y ′ ∈ Y.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 finite-sample gradient estimators. This technique fits well into the MARL independent learning protocol [27] . After all agents have proposed their policy, the MDP is run to 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 a batch version of the REINFORCE estimator whose definition is deferred to the Appendix C.6.1. As for the estimators that the adversary utilizes, we define the state-action visitation measure estimator and their gradient estimator closely following [113] . By applying policy gradient theorem [104] along with the chain-rule, the gradient estimator for a value-function that is nonlinear in λ(y; x), is computed by the following estimator [113] .Definition 2.7 (Gradient Estimator). Let τ = (s 0 , b 0 , s 1 , b 1 , • • • , s H-1 , b H-1) denote a trajectory with length H sampled under initial distribution ρ and policy y. Let F (λ(y)) be the value function of the MDP w.r.t. λ(y) and u := ∇ λ F (λ(y)). The estimator for gradient ∇ y F (λ(y)) using the sampled trajectory τ is defined asg(τ |y; u) := H-1 h=0 γ h • u(s h , b h ) • h h ′ =0 ∇ y log y(b h ′ |s h ′ ) .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 a Nash equilibrium in ATMGs.In this subsection we prove that projected gradient descent with a stohcastic inexact gradient oracle converges to an ϵ-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 differentiable function ϕ(z) and its gradient ∇ϕ(z).We call the vector-valued function g(z) a ϑ-inexact gradient oracle if, ∥g(z) -∇ϕ(z)∥ ≤ ϑ, ∀z.Further, given a random variable ξ in some sample space Ξ, we define a stochastic inexact gradient oracle G : Z × Ξ → R d . We assume that the expected value of this oracle will be equal to a ϑ-inexact gradient oracle g(z). Additionally to being unbiased (with respect to a ϑ-inexact gradient oracle), we assume its variance to be bounded. Assumption 3.1 (Unbiased and Bounded Variance). For a variance parameter σ 2 > 0, the gradient oracle G, satisfiesE ξ [G(z, ξ)] = g(z) and E ξ ∥G(z, ξ) -g(z)∥ 2 ≤ σ 2 .Following, we consider the simple update rule of Mini-Batch Inexact Stochastic Projected Gradient Descent, with a batch size M > 0 and ĝt = 1M M j=1 G z t , ξ t j , z t+1 = Proj Z z t -η ĝt . (Inexact Stoch-PGD)We can now state our convergence Theorem for (Inexact Stoch-PGD) whose proof we defer to the appendix. , computes an ϵ-approximate stationary point after T = O ϵ -1+p p iterations.In this subsection we state our contributed Algorithm 1, or ISPNG, which converges to an ϵ-NE for any ATMG, Γ, with an iteration and sample complexity that scales polynomially with 1/ϵ and the parameters of Γ. 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 ν ρ (x, y) := r(x) ⊤ λ(y; x) -ν 2 ∥λ(y; x)∥ 2 , using Algorithm 2, and then 2. every agent independently performs a gradient descent step on the value function.During this process, all agents use 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 is concave in the state-action visitation measure λ(y; x) ∈ R |S||B| . The objective function is merely the original value function plus a quadratic term, -ν 2 ∥λ(y; x)∥ 2 . We remind the reader that due to the existence of this introduced regularizer, the utility of the adversary u = ∇ λ(y;x) F ν ρ (x, y) = r(x) -νλ(y; x). In order to estimate a gradient, the adversary needs to collect a number of trajectories, τ = (s 0 , b 0 , s 1 , . . . , s H-1 , b H-1 , s H ), each of length H. Notably, the adversary only uses the empirical state-action visitation measure for the purpose of gradient estimation of the regularized function. y (0) (s, b) ← 1 |B| , ∀(s, b) ∈ S × B. 3: for Epoch t ← 0, 1, . . . , T y do 4:Independently sample K trajectories, K (t) , of length H under policy y (t) . 5:λ(t) ← 1 K τ ∈K (t) λ(τ |y (t) ), 6: u ← r(x) -ν λ(t) . 7: ĝ(t) y ← 1 K τ ∈K (t)g(τ |y (t) ; u). ▷ g as in Definition 2.7.y (t+1) ← Proj Y ζy (y (t) + η y ĝ(t) y ). 9: end forAlgorithm 1, or ISPNG, is an instance of a nested-loop algorithm. As we have already informally stated, ISPNG runs gradient descent on the regularized max function Φ ν (x) = max λ∈Λ(x) r(x) ⊤ λν 2 ∥λ∥ 2 for some parameter ν. This function has Hölder-continuous gradient and, as such, the convergence proof is underpinned by Theorem 3.1. Formally we state that: Theorem 3.2 (Grad. Contunuity of Reg-Max Function). Let function Φ ν (x) be the maximum function of the regularized value function of an ATMG, with regularization coefficient ν > 0. It is the case that, (i)EQUATION.ISPNG manages to run gradient descent on function Φ ν 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 actions and thus do not know the gradient w.r.t the regularizing term. Fortunately, the regularization coefficient plays a second role in bounding the inexactness error of the gradient estimates. For that reason, parameter ν admits a careful tuning.Finally, the differentiability of Φ ν and the per-player gradient domination property of the V ρ implies that an ϵ-FOSP x * and the corresponding best-response for the regularized value function, y * , constitute an ϵ-NE, leading to the main Theorem of this subsection:Theorem 3.3 (Main Result; Formally in Theorem C.3). Given a desired accuracy ϵ > 0, Algorithm 1 outputs a joint policy (x * , y * ) for which it holds that,E V ρ (x * , y * ) -min x ′ i ∈Xi V ρ (x ′ i , x * -i , y * ) ≤ ϵ, ∀i ∈ [n];and E max y ′ ∈Y V ρ (x * , y ′ ) -V ρ (x * , y * ) ≤ ϵ,|A i | + |B|, D m , 1 1-γ , 1 mins ρ(s) . By D m we denote the mismatch coeffi- cient D m := d x,y ρ ρ ∞ (Definition C.2).4 Minimax in Nonconvex-Hidden-Strongly-Concave FunctionsFinally, we would state a more general result compared to that of Theorem 3.3. We consider the general min-max nonconvex-nonconcave optimization problem, min x∈X max y∈Y f (x, y), when an additional structural assumption holds, i.e., when f is nonconvex-hidden-strongly-concave. In particular, function f admits a reformulation of the form,H(x, u) := f x, c -1 (u; x) ,where function H is a nonconvex-strongly-concave function defined on X × U. The sets X and U are closed and convex, while c(•; x) : Y → U is an invertible mapping parametrized by x. Moreover, we will denote U(x) := {u|u = c(y; x), ∀y ∈ Y}. We further assume that the mapping c and its inverse are Lipschitz-continuous. Specifically, Assumption 4.1. For the mapping c and its inverse, c -1 , it holds that∥c(y; x) -c(y ′ ; x ′ )∥ ≤ L c (∥x -x ′ ∥ + ∥y -y ′ ∥), ∀x, x ′ ∈ X ; y, y ′ ∈ Y c -1 (u; x) -c -1 (u ′ ; x ′ ) ≤ L c -1 (∥x -x ′ ∥ + ∥u -u ′ ∥), ∀x, x ′ ∈ X ; u, u ′ ∈ U.If this is the case, the maximizer u ⋆ (x) := argmax u∈U (x) H(x, u), is Hölder continuous w.r.t. x as stated by the following Theorem. Theorem 4.1 (Formally in Theorem D.2). Let function f (x, y) be nonconvex-hidden-stronglyconcave with a modulus of ν > 0. Let also function H be a L H -Lipschitz continuous and ℓ Hsmooth nonconvex-strongly-concave reformulation of f with an invertible mapping c for which Assumption 4.1 holds. Then,∥u ⋆ (x) -u ⋆ (x ′ )∥ ≤ L ⋆ ∥x -x ′ ∥ 1 2 , ∀x, x ′ ∈ X .where, L ⋆ = O 1 ν . Theorem 4.2 (Convergence to an ϵ-SP; Formally in Theorem D.3). Let f be a nonconvex-hiddenstrongly-concave function obeying to the same assumptions as f in Theorem 4.1 and ϵ > 0. Further assume a maximization oracle with O(νϵ 2 )-accuracy. There exists an algorithm that computes an ϵ-approximate saddle-point (x * , y * ) by making T = O 1 ν 2 ϵ 3 calls to the maximization oracle. Also, the maximization oracle can be implemented by stochastic gradient ascent with iteration complexityT ′ = Õ 1 ν 3 ϵ 2 , and stepsize η y = O(ν 2 ϵ 2 ). 
conclusion, future work, and limitations: 
 Conclusions We expanded stochastic gradient techniques to be able to compute a stationary point in constrained optimization of nonconvex with weakly-smooth functions. We applied that result to design the first learning algorithm that computes an ϵ-approximate Nash equilibrium in adversarial team Markov games using a finite number of samples and iterations that scale polynomially with 1/ϵ and the natural parameters of the game. 
 
 Appendix: We believe that some questions that require further investigation are the following: (i) Is it possible to extend the techniques of [34] to establish convergence guarantees of stochastic gradient descent on nonconvex functions with Hölder-continuous gradient without batch-sampling of the gradient? (ii) Can we design a two-timescale gradient descent-ascent scheme for ATMGs that converges to a Nash equilibrium with best-iterate guarantees? (iii) Can we utilize some variancereduction techniques to achieve a better sample complexity for learning an ϵ-NE in ATMGs?Limitations The main limitations of our work are (i) the notion of independent learning as presented is weaker than the one presented in [27] i.e., our algorithm has an "inner loop", (ii) the fact that we did not present an example for which the function Φ ν 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 a two-timescale algorithmic approach. As for the second item, we remark that even if it is the case that Φ ν is smooth for ATMGs, our provided convergence rates would be straightforwardly improved without any qualitative modification of the algorithm. Also, we would like to highlight that this discussion is related to Remark 2.Multiagent RL Nash equilibrium computation has been central in multiagent RL. Notable algorithms, 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-completeness) 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, 114, 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 a 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 or stationarity properties, have gained attention [29, 62] .Convex RL Maximizing a value function regularized by a term that is strongly-concave 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, 112] is a 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) "pure-exploration" RL [57] , where the 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 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] .Min-max Optimization Min-max optimization studies problems of the form min x∈X max y∈Y f (x, y). When the objective function f is convex in x 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] .It is also known that standard Gradient Descent/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 PŁcondition [83, 44, 105] . On the negative side, we know that the problem in its full generality (nonconvexnonconcave landscape with coupled linear constraints) is computationally intractable [33] .Hidden-Convex 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 hidden-monotonicity has made its appearance in [45] and the subsequent works [77, 90] .Weakly-Smooth Optimization The majority of references that we encounter for weakly-smooth minimization assume convexity and concern the unconstrained setting. We mention the important references of [35, 82] while also more recent works [106, 85, 84] .In this section we prove that stochastic projected gradient descent with an stochastic inexact oracle converges to an ϵ-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.1) is an 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, r η and rη , to be:• r η (z) := 1 η (z -Proj Z (z -ηg (z))), with a shorthand notation, r t η := r η (z ) ;• rη (z) := 1 η (z -Proj Z (z -η ĝ(z))), similarly, rt η := rη (z ) .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-Gradient Mapping as a Stationarity Surrogate). If r η (z) ≤ ϵ for some z ∈ Z, it holds that:max z ′ ∈Z,∥z ′ -z + ∥≤1 -∇ϕ(z + ), z ′ -z + ≤ ϑ + η 2 ϵ + ℓ p η p ϵ p ,where z + := Proj Z (z -ηg(z)).Proof.In (Inexact Stoch-PGD), ∥g(z) -∇ϕ(z)∥ ≤ ϑ, ∀z ∈ Z. Since z + := Proj Z (z -ηg(z)), it holds that z + = argmin z ′ ∈Z ∥z ′ -(z -ηg(z))∥ 2 .Due to the optimality condition, we have-z + -z + 1 η g(z) ∈ N Z (z + ),where N Z (z) is the normal cone of Z at z, N Z (z) := {v| ⟨v, z ′ -z⟩ ≤ 0, ∀z ′ ∈ Z}. From the latter, we can conclude that-z + -z + 1 η ∇ϕ(z) - 1 η (-∇ϕ(z) + g(z)) ∈ N Z (z + ) -z + -z + 1 η ∇ϕ(z) ∈ N Z (z + ) + B ϑ η - 1 η ∇ϕ(z + ) -z + -z + 1 η ∇ϕ(z) - 1 η ∇ϕ(z + ) ∈ N Z (z + ) + B ϑ η . Now, we bound z + -z + 1 η ∇ϕ(z) -1 η ∇ϕ(z + ) , z + -z + 1 η ∇ϕ(z) - 1 η ∇ϕ(z + ) ≤ z + -z + 1 η ∇ϕ(z) -∇ϕ(z + ) ≤ z + -z + ℓ p η z + -z p ≤ ηϵ + ℓ p η 1-p ϵ p .Therefore we have-∇ϕ(z + ) ∈ N Z (z + ) + B ϑ + η 2 ϵ + ℓ p η p ϵ p .The latter display implies the statement of the lemma.We immediately have the following corollary,Corollary B.1. For any z ∈ Z, denote z + := Proj Z (z -ηg(z)). E r η (z) ≤ ϵ implies that E max z ′ ∈Z,∥z ′ -z + ∥≤1 -∇ϕ(z + ), z ′ -z + ≤ ϑ + η 2 ϵ + ℓ p η p ϵ p .The folklore proof of gradient descent for nonconvex functions relies on the Lipschitz continuity of the gradient to prove convergence to a first-order stationary point. When the gradient are not Lipschitz continuous but continuous in the weaker notion of Hölder continuity implies the following fact that we will eventually use to prove a "descent lemma".Fact B.1. Let a function ϕ : Z → R with (p, ℓ p )-Hölder continuous gradient. Then, it is the case that for all z, z ′ ,|ϕ(z ′ ) -ϕ(z) + ⟨∇f (z), z ′ -z⟩| ≤ ℓ p 1 + p ∥z ′ -z∥ 1+p .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), ∇ϕ(z)) of an exact oracle for a nonconvex function satisfying Hölder gradient continuity can be translated into some "inexact" information for a smooth function. Parameters δ, ℓ ′ in Proposition B.1 can be treated as "inexactness" parameters and will be chosen as appropriate parameters of the exponent p of Hölder continuity.Proposition B.1. For given δ, ℓ p , and a tuning ofℓ ′ := ℓ 2 1+p p δ 1-p 1+p, it holds that for any x, x ′ ,ℓ p 1 + p ∥x -x ′ ∥ 1+p ≤ ℓ ′ 2 ∥x -x ′ ∥ 2 + δ.Proof. We let χ := ∥x -x ′ ∥. By choosing the optimal ℓ ′ we can verify that2 max χ≥0 ℓ p 1 + p χ -1+p -δχ -2 = ℓ p ℓ p 2δ • 1 -p 1 + p 1-p 1+p ≤ ℓ 2 1+p p δ 1-p 1+p .Where in the inequality we use the fact that 1-p 2(1+p) 1-p 1+p ≤ 1 for 0 ≤ p ≤ 1. Setting ℓ ′ = ℓ 2 1+p pE ∥ĝ(z) -g(z)∥ 2 ≤ σ 2M for some g : Z → Z * where ∥g(z) -∇ϕ(z)∥ ≤ ϑ, ∀z ∈ Z. Implementing T updates of the form (Inexact Stoch-PGD) using ĝ and a stepsize η = 1 2ℓ ′ guarantees that:1 T T -1 t=0 E rt η 2 ≤ 8ℓ 2 1+p p E ϕ z 0 -ϕ * δ 1-p 1+p T + 8σ 2 M + 8ℓ 2 1+p p δ 2p 1+p + 4ϑ 2 .We postpone the proof to state a corollary that might help the reader gain some intuition on how the iteration complexity scales with p.Corollary B.2. Let ϕ, ĝ, the update rule of (Inexact Stoch-PGD) as in Theorem B.1, and stepsize η = ( ϵ 1-p 2 3-2p •ℓp ) 1 p . For t * drawn uniformly at random from [1, . . . , T ], it holds that:E r * η 2 ≤ 8ℓ 2 1+p p E ϕ z 0 -ϕ * δ 1-p 1+p T + 16ℓ 2 1+p p δ 2p 1+p + 8ϑ 2 + 18σ 2 M ,where r * η := r t * η . Furthermore, by setting the parameters as T ≥8 1+p p ℓ 1 p p (E[ϕ(z 0 )]-ϕ * ) ϵ 1+p p , δ ≤ ( ϵ 8 ) 1+p p ℓ 1 p p , ϑ ≤ ϵ 8 , and M ≥ 9σ 2 2ϵ 2 , it is guaranteed that there will exist a t ⋆ ∈ {0, . . . , T -1} such that E[r η (z t ⋆ )] ≤ ϵ. Proof. For the first claim, E r * η 2 = E 1 η z t * -Proj Z z t * -ηg(z t * ) 2 ≤ 2E 1 η z t * -Proj Z z t * -η ĝ(z t * ) 2 + 2E 1 η Proj Z z t * -η ĝ(z t * ) -Proj Z z t * -ηg(z t * ) 2 ≤ 2E r * η 2 + 2E 1 η z t * -η ĝ(z t * ) -z t * -ηg(z t * ) 2 = 2E r * η 2 + 2E ĝ(z t * ) -g(z t * ) 2 ≤ 8ℓ 2 1+p p E ϕ z 0 -ϕ * δ 1-p 1+p T + 16ℓ 2 1+p p δ 2p 1+p + 8ϑ 2 + 18σ 2 M .Where the last inequality follows from Theorem B.1 and the fact that E ∥ĝ(z) -g(z)∥ 2 ≤ σ 2 M . By setting the parameters as in the corollary, we have E[r η (z t ⋆ )] ≤ ϵ.Remark 1. With the same parameters we choose in Corollary B.2, Lemma B.1 guarantees that for any p ∈ (0, 1], r η (z) is a sufficient surrogate for stationarity. In particular, r η (z) ≤ ϵ implies that-∇ϕ(z + ) ∈ N Z (z + ) + B 8 1-p ℓ p 2 p + 9 ϵ .Finally, we state one more auxiliary claim before proceeding to the proof of Theorem C.3. Claim B.1. Consider an iterate of (Inexact Stoch-PGD), z t . Also, define z + = Proj Z (z t -ηg(z)), where g is the inexact-gradient oracle. It is the case that,z t+1 -z + ≤ η 2 σ 2 M .Proof. The proof follows easily from arguments we have already used,E z t+1 -z + 2 = E Proj Z z t -η ĝt -Proj Z z t -ηg t 2 ≤ E η ĝt -ηg t 2 = η 2 E ĝt -g t 2 ≤ η 2 σ 2 M .Proof of Theorem B.1Proof. Since ∥g(z) -∇ϕ(z)∥ ≤ ϑ, from the weakly-smooth condition, we haveEQUATION≤ ϕ(z t ) - η 2 - ℓ ′ η 2 2 rt η 2 + η ĝ z t -g z t , r t η + η ĝ z t -g z t , rt η -r t η + η 2 ϑ 2 + δ.• (1) is because of Proposition B.1;• in (2), we plug-in the definition of rt η ;• (3) uses the fact that -ĝ(z t ), rt η ≤ -1 η rt η 2 ;• (4) is due to Young's inequality;• in (5), we plug-in the error bound on the inexact-gradient oracle ∥∇ϕ(z) -g(z)∥ 2 ≤ ϑ.ϕ z t+1 ≤ ϕ(z t ) - η 2 - ℓ ′ η 2 2 rt η 2 + η ĝ z t -g z t , r t η + η ĝ z t -g z t , rt η -r t η + η 2 ϑ 2 + δ ≤ ϕ(z t ) - η 2 - ℓ ′ η 2 2 rt η 2 + η ĝ z t -g z t , r t η + η ĝ z t -g z t 2 + η 2 ϑ 2 + δ.Summing for t = 0, . . . , T -1,T -1 t=0 ϕ z t+1 ≤ T -1 t=0 ϕ z t - η 2 - ℓ ′ η 2 2 ∥r t η ∥ 2 + η ĝ z t -g z t , r t η + η ĝ z t -g z t 2 + η 2 ϑ 2 T + δT.T -1 t=0 η 2 - ℓ ′ η 2 2 rt η 2 ≤ ϕ z 0 -ϕ z T + T -1 t=0 η ĝ z t -g z t , r t η + η ĝ z t -g z t 2 + η 2 ϑ 2 T + δT ≤ ϕ z 0 -ϕ * + T -1 t=0 η ĝ z t -g z t , r t η + η ĝ z t -g z t 2 + η 2 ϑ 2 T + δT.Taking expectations, we haveη 2 - ℓ ′ η 2 2 T -1 t=0 E rt η 2 ≤ E ϕ z 0 -ϕ * + T -1 t=0 ηE ĝ z t -g z t , r t η + ηE ĝ z t -g z t 2 + δT + η 2 ϑ 2 T ≤ E ϕ z 0 -ϕ * + η σ 2 M T + δT + η 2 ϑ 2 T.By setting η ← 1 2ℓ ′ , it holds that1 T T -1 t=0 E rt η 2 ≤ 8ℓ ′ E ϕ z 0 -ϕ * T + 8σ 2 M + 8ℓ ′ δ + 4ϑ 2 = 8ℓ 2 1+p p E ϕ z 0 -ϕ * δ 1-p 1+p T + 8σ 2 M + 8ℓ 2 1+p p δ 2p 1+p + 4ϑ 2 .This completes the proof.In this section we the formal proofs of our claims regarding ATMGs. Before proceeding, let us provide a roadmap of the current section:• Beginning, in Table 1 we offer a concise summary of our ATMG-related notation.• We proceed to present a number of crucial facts regarding MDPs in Appendix C. 1 The set of feasible directly parameterized policies of player i:X i := ∆(A i ) S XThe set of feasible directly parameterized policies of the team:X := × n i=1 X i YThe set of feasible directly parameterized policies of the adversary player:Y := (B) S P(s ′ |s, a, b)Probability of transitioning from state s to s ′ under the action profile (a, b) P(x, y)The (row-stochastic) transition matrix of the Markov chain induced by (x, y) γ Discount factor d x,y s0 (s)The (un-normalized) state visitation measure for policy (x, y) λ(y; x)The state-action visitation measure of the adversary when the team is playing policy x V (x, y), V ρ (x, y)The value vector per-state, the expected value under initial distribution ρ V ν (x, y), V ν ρ (x, y)The regularized value vector per-state, the expected value under initial distribution ρ τ A trajectory of states and joint actions of the Markov game Estimators: λ A single estimate of the state-action visitation measure λThe estimator of the state-action visitation measure g A single estimate of the gradient ĝyThe estimator of the gradient Parameters:L V Lipschitz constant of the value function V ρ (•, •) ℓ V Smoothness constant of the value function V ρ (•, •) D mDistribution mismatch coefficient Additional notation:Φ(x)Maximum of the value function given x:Φ(x) = max y∈Y V ρ (x, y) Φ ν (x)Maximum of the regularized value function given x:Φ ν (x) = max y∈Y V ν ρ (x, y) C.Bounding the stationarity error on the truncated simplex. The ζ-truncated simplex, ∆ m,ζ is defined a the set of all probability vectors with no entry smaller than ζ > 0. More formally, for a given dimension m and a 0 < ζ ≤ 1 m , the ζ-truncated simplex is defined to be ∆ m,ζ = x x i ≥ ζ,-∇f (x ζ ), x ′ ζ -x ζ ≤ ϵ, ∀x ′ ζ ∈ ∆ m,ζ . Then, x ζ is an (ϵ + 2ζmL f )-stationary point when the entire simplex is considered, i.e, ⟨-∇f (x ζ ), x -x ζ ⟩ ≤ ϵ + 2ζmL f , ∀x ∈ ∆ m . Proof. Consider x ′ ζ ∈ ∆ m,ζ such that x -x ′ ζ ≤ 2ζm, such point exists due to Lemma C.6, we have ⟨-∇f (x ζ ), x -x ζ ⟩ = -∇f (x ζ ), x ′ ζ -x ζ + -∇f (x ζ ), x -x ′ ζ ≤ ϵ + 2ζmL f .Where in the last inequality we use the fact that for allx ′ ζ ∈ ∆ m,ζ , we have -∇f (x ζ ), x ′ ζ -x ζ ≤ ϵ and ∥∇f (x ζ )∥ ≤ L f .From stationarity to optimality. Lemma C.7 (Gradient Domination). Let a single-agent MDP with action-space A and directlyparametrized policy x ∈ ∆ ζ (A)|S| . Then it holds thatmax x ⋆ ∈∆(A) |S| V ρ (x ⋆ ) -V ρ (x) ≤ 1 1 -γ D m max x ′ ∈∆ ζ (A) |S| (x ′ -x) ⊤ ∇ x V ρ (x) + 2D m ζ|S||A|L 1 -γ .Proof. The proof follows easily from Proposition C.1 and the gradient domination property [3, Lemma 4.1].We begin this section by firstly introducing a proposition which we will leverage in Lemma C.8. Proposition C.2. Consider the inequality of the form αλ 2 ≤ βλχ + γχ where λ and χ are variables and α, β, γ are coefficients. Under the constraints that α, β, γ, λ, χ ≥ 0, there is no solution of the form λ ≤ cχ for any finite constant c ≥ 0.Proof. Solving the quadratic inequality for λ gives:0 ≤ λ ≤ βχ + χ(4αγ + β 2 χ) 2α .We search for a positive constant c such that λ≤ βχ+ √ χ(4αγ+β 2 χ) 2α≤ cχ, or equivalently,1 2α β + 4αγ χ + β 2 ≤ c.By observing that when α, β, γ are all positive constants and as χ → 0, c → ∞, we conclude that no such finite constant c exists.We first define the maximizer for the regularized function r(x) ⊤ λν 2 ∥λ∥ 2 . Since the function is strongly-concave w.r.t. λ, the maximizing λ is unique. Specifically we denoteEQUATION)Now we are ready to show an important lemma regarding to λ ⋆ (x). Lemma C.8 (Continuity of the max. of reg. functions). For any adversarial Markov game Γ, λ ⋆ (x) defined in ( 10) is (1/2, L ⋆ )-Hölder continuous, specifically∥λ * (x 1 ) -λ * (x 2 )∥ ≤ L ⋆ ∥x 1 -x 2 ∥ 1/2 ,whereL ⋆ := 2(n) 1/4 ν(1-γ) 3/2 |S| 1/2 ( n k=1 |A k | + |B|) 3 4 .Proof. Consider team policies, x 1 , x 2 . It holds true for the unique maximizers λ ⋆ (x 1 ), λ ⋆ (x 2 ) of the adversary's regularized value function that,r(x 1 ) -νλ ⋆ (x 1 ) ⊤ (λ 1 -λ ⋆ (x 1 )) ≤ 0, ∀λ 1 ∈ Λ(x 1 ); (11) r(x 2 ) -νλ ⋆ (x 2 ) ⊤ (λ 2 -λ ⋆ (x 2 )) ≤ 0, ∀λ 2 ∈ Λ(x 2 ),where Λ(x) is the set of feasible state-action visitation measures of the adversary given team's policy x. To bound the distance between the two vectors λ ⋆ (x 1 ), λ ⋆ (x 2 ), we observe that for any measure λ ∈ Λ(x 1 ) ∪ Λ(x 2 ), there exist a measure λ 1 ∈ Λ(x 1 ) that shares the same adversary's policy y as in λ. It then follows from Lemma C.2 that λ 1 -λ ≤ L λ ∥x 1 -x 2 ∥. Therefore we have for all λ ∈ Λ(x 1 ),EQUATION)Where the last inequality follows from (11) and the fact that ∥r(x) -νλ ⋆ (x)∥ ≤ |S||B| 1 + ν 1-γ for any x ∈ X . Similarly, it also holds that for all λ ∈ Λ(x 1 ),EQUATION)Plugging in λ ← λ ⋆ (x 2 ) and λ ← λ ⋆ (x 1 ) into ( 12) and ( 13) respectivelyr(x 1 ) -νλ ⋆ (x 1 ) ⊤ (λ ⋆ (x 2 ) -λ ⋆ (x 1 )) ≤ L λ |S||B| 1 + ν 1 -γ ∥x 1 -x 2 ∥, r(x 2 ) -νλ ⋆ (x 2 ) ⊤ (λ ⋆ (x 1 ) -λ ⋆ (x 2 )) ≤ L λ |S||B| 1 + ν 1 -γ ∥x 1 -x 2 ∥.Adding the two inequalities results inEQUATIONOn the other hand, since r(x) ⊤ λν 2 ∥λ∥ 2 is ν-strongly concave in λ, we have for allλ 1 ∈ Λ(x 1 ). (λ 1 -λ ⋆ (x 1 )) ⊤ (r(x 1 ) -νλ 1 ) -(r(x 1 ) -νλ ⋆ (x 1 )) + ν∥λ 1 -λ ⋆ (x 1 )∥ 2 ≤ 0.We again use the fact that for every λ ∈ Λ, it holds that there exists λ 1 ∈ Λ(x 1 ) s.t. ∥λ -λ 1 ∥ ≤ L λ ∥x 1 -x 2 ∥. Therefore it holds that for any λ ∈ Λ,0 ≥ λ 1 + (λ -λ) -λ ⋆ (x 1 ) ⊤ r(x 1 ) -νλ 1 + (λ -λ) -(r(x 1 ) -νλ ⋆ (x 1 )) + ν∥λ 1 + (λ -λ) -λ ⋆ (x 1 )∥ 2 = (λ -λ ⋆ (x 1 )) + (λ 1 -λ) ⊤ r(x 1 ) -νλ 1 + (λ -λ) -(r(x 1 ) -νλ ⋆ (x 1 )) + ν∥λ 1 -λ∥ 2 + ν∥λ -λ ⋆ (x 1 )∥ 2 + 2ν λ 1 -λ, λ -λ ⋆ (x 1 ) = λ -λ ⋆ (x 1 ) ⊤ r(x 1 ) -νλ 1 + (λ -λ) -(r(x 1 ) -νλ ⋆ (x 1 )) + ν∥λ 1 -λ∥ 2 + ν∥λ -λ ⋆ (x 1 )∥ 2 + 2ν λ 1 -λ, λ -λ ⋆ (x 1 ) + λ 1 -λ ⊤ r(x 1 ) -νλ 1 + (λ -λ) -(r(x 1 ) -νλ ⋆ (x 1 )) .Rearranging, we haveλ -λ ⋆ (x 1 ) ⊤ r(x 1 ) -νλ -(r(x 1 ) -νλ ⋆ (x 1 )) + ν∥λ -λ ⋆ (x 1 )∥ 2 ≤ -ν λ -λ ⋆ (x 1 ) ⊤ λ -λ 1 Ω1 -ν∥λ 1 -λ∥ 2 -2ν λ 1 -λ, λ -λ ⋆ (x 1 ) Ω2 -(λ 1 -λ) ⊤ r(x 1 ) -νλ 1 + ν(λ -λ) -(r(x 1 ) -νλ ⋆ (x 1 )) Ω3 .We bound Ω 1 , Ω 2 , and Ω 3 separately.• For Ω 1 , since ∥λ -λ 1 ∥ ≤ L λ ∥x 1 -x 2 ∥, we haveΩ 1 ≤ ν λ -λ ⋆ (x 1 ) ⊤ λ -λ 1 ≤ ν λ -λ ⋆ (x 1 ) λ -λ 1 ≤ 2ν 1 -γ |S||B| • L λ ∥x 1 -x 2 ∥.Where we use the fact that λλ ⋆ (x 1 ) ≤ λ + ∥λ ⋆ (x 1 )∥ and ∥λ∥ ≤ ∥λ∥ 1 = 1 1-γ . • For Ω 2 , only the second term is possibly non-negative, it holds thatλ 1 -λ, λ -λ ⋆ (x 1 ) ≤ L λ ∥x 1 -x 2 ∥ 2 1 -γ |S||B|.Resulting inΩ 2 ≤ 4ν 1 -γ |S||B|L λ ∥x 1 -x 2 ∥.• For Ω 3 :Ω 3 ≤ (λ 1 -λ) ⊤ -νλ 1 + νλ ⋆ (x 1 ) ≤ 2ν 1 -γ |S||B|L λ ∥x 1 -x 2 ∥.Finally, by putting the bounds of Ω 1 , Ω 2 , Ω 3 and settingEQUATIONConcluding, we plug λ ← λ ⋆ (x 2 ) in ( 15), resultingEQUATION)Adding ( 14) and ( 16), we have2L λ |S||B| 1 + ν 1 -γ ∥x 1 -x 2 ∥ + L ′ ∥x 1 -x 2 ∥ ≥ (λ ⋆ (x 2 ) -λ ⋆ (x 1 )) ⊤ ((r(x 1 ) -νλ ⋆ (x 1 )) -(r(x 2 ) -νλ ⋆ (x 2 ))) + (λ ⋆ (x 2 ) -λ ⋆ (x 1 )) ⊤ r(x 1 ) -νλ ⋆ (x 2 ) -r(x 1 ) -νλ ⋆ (x 1 ) + ν∥λ ⋆ (x 2 ) -λ ⋆ (x 1 )∥ 2 = (λ ⋆ (x 2 ) -λ ⋆ (x 1 )) ⊤ (r(x 1 ) -νλ ⋆ (x 2 )) -(r(x 2 ) -νλ ⋆ (x 2 )) + ν∥λ ⋆ (x 2 ) -λ ⋆ (x 1 )∥ 2 .Rearranging we getν∥λ ⋆ (x 2 ) -λ ⋆ (x 1 )∥ 2 ≤ (λ ⋆ (x 2 ) -λ ⋆ (x 1 )) ⊤ (r(x 2 ) -νλ ⋆ (x 2 )) -(r(x 1 ) -νλ ⋆ (x 2 )) + L ′′ ∥x 1 -x 2 ∥ ≤ L r ∥λ ⋆ (x 2 ) -λ ⋆ (x 1 )∥∥x 1 -x 2 ∥ + L ′′ ∥x 1 -x 2 ∥,whereL ′′ := 2 1 + ν 1-γ |S||B|L λ + L ′ = 2 + 10ν 1-γ |S||B|L λ .By setting λ = ∥λ ⋆ (x 2 ) -λ ⋆ (x 1 )∥ and χ = ∥x 1 -x 2 ∥, we consider the inequality νλ 2 ≤ L r λχ + L ′′ χ with coefficients ν, L r , L ′′ ≥ 0 and variables λ and χ. Choosing α ← ν, β ← L r , and γ ← L ′′ , then Proposition C.2 implies that λ ⋆ (x) is not Lipschitz-continuous w.r.t the team policyx. Hence, we consider a solution of the form0 ≤ λ ≤ βχ+ √ χ(4αγ+β 2 χ) 2α≤ cχ p , where 1 2 -p ≥ 0. We choose p = 1 2 since it yields the best convergence rate from Theorem B.1. Solving the above inequality with p = 1 2 gives that• if χ = 0, the inequality holds trivially;• if χ > 0, we havec ≥ βχ + χ(4αγ + β 2 χ) 2α √ χ = β √ χ 2α + 4αγ + β 2 χ 2α . Since χ = ∥x 1 -x 2 ∥ ≤ n|S|Diam Xi = 2n|S|, by plugging in the coefficients, we havec = 1 ν 2L 2 r X + 4νL ′′ ≤ 2(n) 1/4 ν(1 -γ) 3/2 |S| 1/2 n k=1 |A k | + |B| 3 4.By setting L ⋆ = c, we conclude that∥λ * (x 1 ) -λ * (x 2 )∥ ≤ L ⋆ ∥x 1 -x 2 ∥ 1/2 .We are now ready to show that Φ ν (x) 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) := max y∈Y V ν ρ (x, y). It is the case that,EQUATION.Proof. Since Φ ν (x) has a unique maximizer λ ∈ Λ(x), by applying Danskin's Theorem [8] and the "1-1" correspondence between λ and y (Theorem C.1), we have∥∇ x Φ ν (x) -∇ x Φ ν (x ′ )∥ = ∇ x V ν ρ (x, y(λ ⋆ (x))) -∇ x V ν ρ (x ′ , y(λ (x ′ ))) ≤ ℓ ν (∥x -x ′ ∥ + ∥y(λ ⋆ (x)) -y(λ ⋆ (x ′ ))∥) ≤ ℓ ν (∥x -x ′ ∥ + L λinv ∥λ ⋆ (x) -λ ⋆ (x ′ )∥) ≤ ℓ ν (2n|S|) 1 4 + L λinv L ⋆ • ∥x -x ′ ∥ 1 2 .Where in the last inequality we used Lemma C.8 and the fact that ∥x -x ′ ∥ ≤ 2n|S|. Plugging in the coefficients in Lemma C.8, Lemma C.3, and Lemma C.4, it yields that∥∇ x Φ ν (x) -∇ x Φ ν (x ′ )∥ ≤ 30n 1 4 |S| 5 4 ( i |A i | + |B|) 2 ν min s ρ(s)(1 -γ) 13 2 • ∥x -x ′ ∥ 1 2 .In this part we show that Algorithm 1 converges to an ϵ-NE. Essentially, Algorithm 1 implements projected gradient descent on the regularized maximum function Φ ν : X → R with a stochastic ϑ-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 an ϵ-FOSP.The inexactness of the gradient oracle, ϑ, is the sum of two error sources:1. the fact that the adversary can only approximately maximize the regularized value function V ν ρ (x, y) -the iteration and sample complexity of maximizing V ν ρ (x, •) is provided in Theorem C.4; 2. the exact estimation of ∇Φ ν requires estimation of the adversary's policy y -as we assume that the agents do not observe each other's actions this is impossible. Nevertheless, in Lemma C.9 it is proven that the inexactness error is bounded and controlled through the regularizer's coefficient ν.After quantifying ϑ as the function of the latter two terms, the optimality gap of Algorithm 2 and a term that scales with O(ν), we can tune the rest of the parameters accordingly.The resulting ϵ-FOSP, thanks to the gradient domination property (Lemma C.7), corresponds to an ϵ-NE.Bounding the error of the inexact gradient. Following, we prove that the inexactness error of the gradient oracle is bounded by a function of the controllable parameter ν. Lemma C.9 (Inexact gradient). Let V ν ρ (x, y) := V ρ (x, y) -ν 2 s ∥d x,y (s)y(s)∥ 2 , y ν (x) := argmax y {V ν ρ (x, y)}, and g(x) := ∇ x V (x, y ν (x)). Then, it holds that 3 .∥g(x) -∇ x V ν ρ (x, y)∥ 2 ≤ ν|S| 1 2 ( n i=1 |A i | + |B|) (1 -γ)Proof. We observe that∥g(x) -∇ x V ν ρ (x, y)∥ = ∇ x - ν 2 ∥λ(y; x)∥ 2 = ν ∥λ(y; x)∥ ∥∇ x λ(y; x)∥ ≤ ν 1 -γ L λ .Where in the last inequality we use the fact that ∥λ∥ ≤ 1 1-γ and ∇ x λ(y; x) ≤ L λ .Learning an ϵ-NE. We can now compile the intermediate statements to guarantee that ISPNG computes an ϵ-NE for any desired accuracy ϵ > 0 within a finite number of iterations and samples. Theorem C.3. Consider an adversarial team Markov game Γ and Algorithm 1, ISPNG, with an outer-loop parameter tuning of:EQUATION(1-γ) 24 (mins ρ(s)) 2 ϵ 5;EQUATION;EQUATION(1-γ) 10 (mins ρ(s)) 4 ϵ 3 max (1-γ) 4 (mins ρ(s)) 4 ( n i=1 |Ai|+|B|) |S| , 9 2 .Also, let the tuning of the inner-loop subroutine Algorithm 2 (VIS-REG-PG) be:EQUATION(1-γ) 36 (mins ρ(s)) 4 ϵ 6;• H = 2 1-γ log 2293235712D 4 m |S| 4 ( n i=1 |Ai|+|B|) 6 (1-γ) 22 (mins ρ(s)) 2 ϵ 4 .It is the case that the output of the algorithm, (x * , y * ), will be an ϵ-NE in expectation. Specifically, we haveE V ρ (x * , y * ) -min x ′ i ∈Xi V ρ (x ′ i , x * -i , y * ) ≤ ϵ, ∀i ∈ [n]andE max y ′ ∈Y V ρ (x * , y ′ ) -V ρ (x * , y * ) ≤ ϵ.Proof. Let x * , y * be the final output of the algorithm, from Lemma C.7, we haveEQUATIONWhere (17) follows from Lemma C.9. As for the first term of ( 17), let us define y ⋆ (x) = argmax y∈Y V ν ρ (x, y) and x + = Proj X x t * -1 -η x ∇V ρ (x t * -1 , y ⋆ (x t * -1 )) . Then it holds that, E maxx ′ i -∇V ν ρ (x * , y * ) ⊤ (x ′ i -x * i ) = E max x ′ i -∇V ν ρ (x + i , x * -i , y ⋆ (x + )) ⊤ (x ′ i -x * i ) + ∇V ν ρ (x + i , x * -i y ⋆ (x + )) -∇V ν ρ (x * , y * ) ⊤ (x ′ i -x * i ) ≤ E max x ′ i -∇V ν ρ (x + i x * -i , y ⋆ (x + )) ⊤ (x ′ i -x + i ) + L ν E x + i -x * i + E ∇V ν ρ (x + i , x * -i , y ⋆ (x + )) -∇V ν ρ (x * , y * ) • Diam Xi (18) ≤ E max x ′ i -∇V ν ρ (x + i , x * -i , y ⋆ (x + )) ⊤ (x ′ i -x + i ) + L ν E x + i -x * i + ℓ ν E x + -x * + E y ⋆ (x + ) -y * • Diam Xi (19) ≤ E max x ′ i -∇V ν ρ (x + i , x * -i , y ⋆ (x + )) ⊤ (x ′ i -x + i ) + L ν E x + i -x * i + ℓ ν E x + -x * + E y ⋆ (x + ) -y ⋆ (x * ) + E [∥y ⋆ (x * ) -y * ∥] • Diam Xi . Where • Equation (18) is due to ∇V ν ρ (x, y) ≤ L ν ; • Equation (19) follows from the fact that V ν ρ (x, y) is ℓ ν -smooth.By choosing parameters specified above and combining Corollaries B.1 and B.2, Theorem C.4, Lemma C.12, and Claim B.1, we have the desired result. On the other hand, sinceE max y ′ ∈Y V ρ (x * , y ′ ) -V ρ (x * , y * ) ≤ E max y ′ ∈Y V ν ρ (x * , y ′ ) -V ν ρ (x * , y * ) + ν (1 -γ) 2 = E V ν ρ (x * , y ⋆ (x * )) -V ν ρ (x * , y * ) + ν (1 -γ) 2 (20) ≤ L ν E [∥y ⋆ (x * ) -y * ∥] + ν (1 -γ) 2 .Where in (20) we use the fact that ∥λ∥ 2 ≤ 1 (1-γ) 2 . Combining Theorem C.4, Lemma C.12, and choosing parameters specified above gives the desired result.In this section, we consider the direct parameterization for the policy of the adversary. For any policy y ∈ Y, for any state s ∈ S and any action b ∈ B, we have y(b|s) = y s,b .Where y s,b denotes (s, b) th entry of the policy vector y. In this section, we mainly focus on solving the following policy optimization problem:EQUATION)Where λ(y; x) is the state-action visitation measure under policy y as 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 ν is the regularization coefficient. Then by policy gradient theorem [113] , denoteF ν (λ(y; x)) = V ν ρ (x, y) we have ∇ y F ν (λ(y; x)) = [∇ y λ(y; x)] ⊤ (r(x) -νλ(y; x)) = E ρ,y ∞ h=0 γ h • (r(x) -νλ(y; x)) s h ,b h • h h ′ =0 ∇ y log y(b ′ h |s h ′ ) .Given the direct parameterization, we can show the following lemmas: Proof. By direct parameterization y(b|s) = y s,b , we haveEQUATIONWhere e s,b denotes the standard basis for the (s, b) th entry. Similarly, we haveEQUATION)Where diag(•) denotes the standard diagonal matrix. For the policy gradient, we show thatEQUATION≤ 1 (1 -γ) 2 ζ + ν (1 -γ) 3 ζ .Where ( 24) is due to (22) .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 ∈ Y ζ , we use F ν 1/β (λ(y; x))to denote the Moreau envelope of function F ν (λ(y; x)) such thatF ν 1/β (λ(y; x)) := max z∈Y ζ F ν (λ(z; x)) - β 2 ∥λ(z; x) -λ(y; x)∥ 2 .Moreover, we define the proximal point ŷ1/β of Moreau envelope as following:ŷ := argmax z∈Y ζ F ν (λ(y; x)) - β 2 ∥λ(z; x) -λ(y; x)∥ 2 .Now we proceed to show the following lemma: Lemma C.11. When running Algorithm 2, for any t ≥ 0, we haveE y (t+1) -ŷ(t) 2 y (t) ≤(1 -η y β) y (t) -ŷ(t) 2 + 2(1 -η y β)η y (1 + η y ℓ ν ) • C 3 γ H + η 2 y E ∇ y F ν (λ(y (t) ; x)) -ĝ(t) y ) 2 y (t) .WhereC 3 = |S||B| 6H (1-γ) 3 ζ .Proof.EQUATION≤E ∥y (t) +ηy ĝ(t)y -((1-ηyβ) ŷ(t) +ηyβy (t) +ηy∇yF ν (λ( ŷ(t) ;x)))∥ 2 |y (t) =E ∥(1-ηyβ)(y (t) -ŷ(t) )+ηy(∇yF ν (λ( ŷ(t) ;x))-ĝ (t) y )∥ 2 |y (t)=E ∥(1-ηyβ)(y (t) -ŷ(t) )+ηy(∇yF ν (λ( ŷ(t) ;x))-∇yF ν (λ(y (t) ;x)))+ηy(∇yF ν (λ(y (t) ;x))-ĝ (t) y )∥ 2 |y (t)=∥(1-ηyβ)(y (t) -ŷ(t) )+ηy(∇yF ν (λ( ŷ(t) ;x))-∇yF ν (λ(y (t) ;x)))∥ 2+2(1-ηyβ)ηyE[⟨(y (t) -ŷ(t) )-ηy(∇yF ν (λ( ŷ(t) ;x))-∇yF ν (λ(y (t) ;x))),∇yF ν (λ(y (t) ;x))-ĝ (t)EQUATIONWhere (25) follows from Lemma 3.2 in [34] . For the first part of (26), we haveEQUATION=(1 -η y β) 1 -η y β + 2η y ℓ ν + η 2 y ℓ 2 ν 1 -η y β y (t) -ŷ(t) 2 .Where (27) follows from Lemma C.4. By setting η y , β such that 2η y ℓ ν ≤ ηyβ 2 , andEQUATION)For the third part in (26), we have 2(1-ηyβ)ηyE[⟨(y (t) -ŷ(t) )-ηy(∇yF ν (λ( ŷ(t) ;x))-∇yF ν (λ(y (t) ;x))),∇yF ν (λ(y (t) ;x))-ĝ (t) y )⟩|y (t) ] ≤2(1-ηyβ)ηy∥(y (t) -ŷ(t) )-ηy(∇yF ν (λ( ŷ(t) ;x))-∇yF ν (λ(y (t) ;x)))∥•E[∥∇yF ν (λ(y (t) ;x))-ĝ (t) y )∥|y (t) ] ≤2(1-ηyβ)ηy(1+ηyℓν)•∥y (t) -ŷ(t) ∥•E[∥∇yF ν (λ(y (t) ;x))-ĝ (t)EQUATION)Where Combine ( 26), (28) , and (30), we have• C 3 = |S||B| 6H (1-γ)E y t+1 -ŷ(t) 2 y (t) ≤(1 -η y β) y (t) -ŷ(t) 2 + 2(1 -η y β)η y (1 + η y ℓ ν ) • C 3 γ H + η 2 y E ∇ y F ν (λ(y (t) ; x)) -ĝ(t) y ) 2 y (t) .We then show the result for convergence to optimality for (21) . T = O ℓν L 2 λ inv ν log 1 ϵ + ℓν σ 2 L 4 λ inv ν 2 ϵ log 1 ϵ iterations, we have E F ν (λ(y ⋆ ζ ; x)) -F ν (λ(y (T ) ; x)) ≤ ϵ.Where y ⋆ ζ is the unique maximizer for the optimization problem (21) .Proof. From Theorem 1 in [43] , by setting β = 4ℓ ν , α ≤ 2η y ℓ ν , and η y ≤ 2 9ℓν . Then for any z ∈ Y ζ , we haveEQUATIONWhere (31) E F ν 1/β (λ(y (t+1) ; x)) ≥(1 -α)E F ν 1/β (λ(y (t) ; x)) + αF ν (λ(y ⋆ ζ ; x)) -βη 2 y E ∇ y F ν (λ(y (t) ; x)) -ĝ(t) y ) 2 y (t) - 3L 2 λinv α 2 2η y - (1 -α)αν 2 E λ( ŷ(t) ; x) -λ(y ⋆ ζ ; x) 2 -2η y (1 -α)(1 + η y ℓ ν ) • C 3 γ H . Define Λ t := E F ν (λ(y ⋆ ζ ; x)) -F ν 1/β (λ(y (t) ; x)) , by setting 3L 2 λ inv α 2 2ηy -(1-α)αν 2 ≤ 0, we have Λ t+1 ≤ (1 -α)Λ t + βη 2 y E ∇ y F ν (λ(y (t) ; x)) -ĝ(t) y ) 2 y (t) + 2η y (1 -α)(1 + η y ℓ ν ) • C 3 γ H .Summing over T iterations, and denote E ∇ y F ν (λ(y (t) ; x)) -ĝ(t) y )2 y (t) = σ 2 , we getΛ T ≤ (1 -α) T Λ 0 + 4ℓ ν η 2 y α σ 2 + 2η y (1 -α)(1 + η y ℓ ν ) α • C 3 γ H .By settingH = 2 log(1/νϵ) 1-γ , α ≤ min 2η y ℓ ν , νηy 2L 2 λ inv , and η y = 2 9ℓν , νϵ 10ℓν σ 2 L 2 λ inv , after T = O ℓ ν L 2 λinv ν log 1 ϵ + ℓ ν σ 2 L 4 λinv ν 2 ϵ log 1 ϵ .iterations, we get Λ T ≤ ϵ. Whereσ 2 = C1 K + C 2 • γ 2H , C 1 = 57 (1-γ) 6 ζ 2 , C 2 = 126H 2 (1-γ) 6 ζ 2 , C 3 = |S||B| 6H(1-γ) 3 ζ . Since F ν (λ(y; x)) is smooth with respect to the state-action visitation measure λ(y; x). We haveΛ T = E F ν (λ(y ⋆ ζ ; x)) -F ν 1/β (λ(y (T ) ; x)) = E F ν (λ(y ⋆ ζ ; x)) -max z∈Y F ν (λ(z; x)) - β 2 λ(z; x) -λ(y (T ) ; x) 2 ≥ E F ν (λ(y ⋆ ζ ; x)) -F ν (λ(y (T ) ; x)) + β 2 λ(y (T ) ; x) -λ(y (T ) ; x) 2 = E F ν (λ(y ⋆ ζ ; x)) -F ν (λ(y (T ) ; x)) . Therefore E F ν (λ(y ⋆ ζ ; x)) -F ν (λ(y (T ) ; x)) ≤ Λ T ≤ ϵ.Define y ⋆ ∈ Y such that y ⋆ = argmax y∈Y r(x) ⊤ λ(y; x) -ν 2 ∥λ(y; x)∥ 2 . We bound the distance between the the optimal y ⋆ and y (T ) from Algorithm 2.Lemma C.12. For anyy ∈ Y ζ , if E F ν (λ(y ⋆ ζ ; x)) -F ν (λ(y; x)) ≤ ϵ, then we have E [∥y ⋆ -y∥] ≤ L λinv 8L λ |B|ζ (1 -γ)ν + 2ϵ ν .Proof. Since F ν (λ(y; x)) is ν-strongly concave with respect to λ(y; x), we haveF ν (λ(y ⋆ ζ ; x)) ≥ F ν (λ(y; x)) + ∇ λ F ν (λ(y ⋆ ζ ; x)), λ(y ⋆ ζ ; x) -λ(y; x) + ν 2 λ(y ⋆ ζ ; x) -λ(y; x) 2 (32) = F ν (λ(y; x)) + ν 2 λ(y ⋆ ζ ; x) -λ(y; x) 2 .Where (32) holds because λ(y ⋆ ζ ; x) is the optimal solution for F ν (λ(y; x)) for any y ∈ Y. ThereforeE λ(y ⋆ ζ ; x) -λ(y; x) ≤ 2 ν • E F ν (λ(y ⋆ ζ ; x)) -F ν (λ(y; x)) ≤ 2ϵ ν .From the definition of λ(y EQUATIONEQUATION)Where• in (33) y ζ ∈ Y ζ is chosen such that ∥y ⋆ -y ζ ∥ ≤ 2ζ|B| according to C.6; • (34) holds because ∥∇ λ F ν (λ)∥ ≤ 2 1-γ and λ(y; x) is L λ -continuous. Since F ν (λ) is ν-strongly concave w.r.t λ, we have ν 2 λ(y ⋆ ζ ; x) -λ(y ⋆ ; x) 2 ≤F ν (λ(y ⋆ ζ ; x)) -F ν (λ(y ⋆ ; x) + ∇ λ F ν ((λ(y ⋆ ζ ; x)), λ(y ⋆ ; x) -λ(y ⋆ ζ ; x) ≤ 4L λ |B|ζ 1 -γ .Thus we conclude thatE [∥y ⋆ -y∥] ≤ L λinv E [∥λ(y ⋆ ; x) -λ(y; x)∥] ≤ L λinv λ(y ⋆ ; x) -λ(y ⋆ ζ ; x) + E λ(y ⋆ ζ ; x) -λ(y; x) ≤ L λinv 8L λ |B|ζ (1 -γ)ν + 2ϵ ν .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 a geometric distribution for the team, and • while, the state-action visitation estimators that the adversary uses come from sampled trajectories of a fixed horizon length H.In the former case, the estimator is unbiased while in the second case the bias decays exponentially in H.In the present work, the team agents only need to implement a batch version of REINFORCE [104] .That is, they get estimatesĝ(t) k = 1 M M j=1 g(t)k , where:g(t) i,j = Hj hj =1 r (hj ) i Hj h=1 ∇ log x i a (hj ) |s (hj ) , (REINFORCE)with each H j is a random variable following a geometric distribution with parameter (1 -γ).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 2] ). When Equation (REINFORCE) is implemented with H following a geometric distribution with a parameter 1 -γ, and agent k selects policies from the ζ-truncated simplex on each state, it is the case that the gradient estimates satisfy:E ĝ(t) k -∇ x k V ρ (x t , y t ) = 0; E ĝ(t) k -∇ x k V ρ (x t , y t ) 2 ≤ 24 |A 2 k | ζ(1 -γ) .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 of the a gradient estimator with a deterministic choice of H was significantly less demanding than doing so with a randomized choice. This comes at the cost with a non-zero bias that nevertheless decays exponentially in H. For any policy of the adversary y ∈ Y, we introduce the H-horizon truncated state-action visitation measureEQUATION)Where λ H,s,b (y; x) denotes the (s, b) th entry of λ H (y; x). For any reward vector r, we have[∇ y λ H (y; x)] ⊤ r = E H-1 h=0 γ h • r(s h , b h ) • h h ′ =0 ∇ y log y(b h ′ |s h ′ ) y, s 0 ∼ ρ .In this subsection we will present a detailed analysis regarding estimators defined in Definition 2. t) . Moreover, we have:EQUATION• E λ(t) -λ(y (t) ; x) ≤ γ H 1-γ , and • E ĝ(t) y -∇ y F ν (λ(y (t) ; x)) ≤ H+1 (1-γ)ζ + νH+ν+1 (1-γ) 2 ζ + ν (1-γ) 3 ζ • γ H .Proof. From the definition, we haveE τ ∼y λ(τ |y) = λ H (y; x), E τ ∼y [g(τ |y; r)] = [∇ y λ H (y; x)] ⊤ r.Therefore, t) .EQUATIONThen it holds that E λ(t) -λ(y (t) ; x) = λ H (y (t) ; x) -λ(y (t) ; x)= ∞ h=H γ h • P(s h = s, b h = b|y (t) , s 0 ∼ ρ) • e s h ,b h ≤ γ H • ∞ h=0 (γ h • 1) = γ H 1 -γ .Similarly, we haveEQUATIONFor the first part in the above inequality, we haveEQUATION)For the second part in (36), we haveEQUATIONCombining ( 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 τ = {s 0 , b 0 , s 1 , b 1 , • • • , s H-1 , b H-1 })∥ ≤ 1 (1 -γ) 2 ζ • ∥r 1 -r 2 ∥ ∞ .• For any policies y 1 and y 2 , for any reward vectors r, EQUATION≤ (1 + ν 1-γ ) (1 -γ) 2 ζ 2 • ∥y 1 -y 2 ∥ = 1 (1 -γ) 2 ζ 2 + ν (1 -γ) 3 ζ 2 • ∥y 1 -y 2 ∥.E ∥ λ(t) -λ H (y (t) ; x)∥ 2 ≤ 1 K(1 -γ) 2 .Where λ H (y (t) ; x) is the truncated state-action visitation measure for λ(y (t) ; x) defined in (35) Proof. It holds thatEQUATIONEQUATION)Where:• ( 42) is due to E λ(t) = λ H (y (t) ; x) and the fact that trajectories τ ∈ K (t) are independently sampled;• (43) is because the variance is bounded by the second moment;• (44) is because ∥ λ(τ |y (t )∥ ≤ 1 1-γ .Now we analyze the variance of gradient estimator ĝ(t) y by providing the following lemma: Lemma C.17 (Bounded Var. of Grad. Estimator). For ĝ(t) y in Algorithm 2, we haveEQUATIONWhere ( 45) is due to Cauchy-Schwarz inequality. For the first part in (45), we haveEQUATIONEQUATION)Where:• ( 46) is due to Cauchy-Schwarz inequality;• (47) follows from Lemma C.15;• (48) follows the same proof as in (37);• ( 49) is because of Lemma C.16.For the second part in (45) , it holds that,EQUATIONEQUATION)Where • ( 50) is due to Lemma C.14 and the fact that trajectories τ are independently sampled;• ( 51) is because variance is bounded by second moment;• (52) follows from (22) .Finally for the last part in (45), we haveEQUATIONEQUATION)Where • ( 54) is due to ( 22) and (37);• (55) is because of Lemma C. 16 .Combine ( 45), ( 49), ( 53) and ( 56), we getE ĝ(t) y -∇ y λ H (y (t) ; x) ⊤ r (t) 2 ≤ 3ν 2 K(1 -γ) 6 ζ 2 + 3 1 K(1 -γ) 4 ζ 2 + 2ν K(1 -γ) 5 ζ 2 + ν 2 K(1 -γ) 6 ζ 2 + 3ν 2 K(1 -γ) 6 ζ 2 = 3 K(1 -γ) 4 ζ 2 + 6ν K(1 -γ) 5 ζ 2 + 9ν 2 K(1 -γ) 6 ζ 2 .After bounding the variance of ĝ(t) y in Algorithm 2, we can prove the following lemma Lemma C.18 (Bounded Dist. with Actual Grad.). Consider y (t) and ĝ(t) y in Algorithm 2, it holds thatE ĝ(t) y -∇ y F ν (λ(y (t) ; x)) 2 ≤ C 1 K + C 2 • γ 2H .WhereEQUATION)Notice that the first part in ( 57) is bounded in Lemma C.17 and the second part is bounded in (56) .For the last part, observe that ∇ y λ H (y (t) ; x) ⊤ r ⋆ -∇ y F ν (λ(y (t) ; x)) EQUATIONWhere ( 59) is because of (37) . Since λ H (y (t) ; x) -λ(y (t) ; x)   2 = γ H ∞ h=0 γ h • 1 2 ≤ γ 2H (1 -γ) 2 .We have ∇ y λ H (y (t) ; x) ⊤ ∇ λ F ν (λ H (y (t) ; x)) -∇ λ F ν (λ(y (t) ; x))2 ≤ ν 2 (1 -γ) 6 ζ 2 • γ 2H . (60)For the second part in (58) , it holds that ∇ y λ H (y (t) ; x) ⊤ -∇ y λ(y (t) ; x)⊤ ∇ λ F ν (λ(y (t) ; x)) 2 = E ∞ h=H γ h • ∇ λ F ν (λ(y (t) ; x)) s h ,b h • h h ′ =0 ∇ y log y (t) (b h ′ |s h ′ ) 2 ≤ ∞ h=H γ h • 1 + ν 1 -γ • (h + 1) • 1 ζ 2 ≤ 1 + ν 1 -γ 2 • 1 ζ 2 • (H + 1) 2 (1 -γ) 2 + 1 (1 -γ) 4 • γ 2H = (H + 1) 2 (1 -γ) 2 ζ 2 + 2ν(H + 1) 2 (1 -γ) 3 ζ 2 + ν 2 (H + 1) 2 + 1 (1 -γ) 4 ζ 2 + 2ν (1 -γ) 5 ζ 2 + ν 2 (1 -γ) 6 • γ 2H . (61)We rearrange the latter display into (u -u ⋆ (x 1 ))⊤ ∇H(x 1 , u) -∇H(x 1 , u ⋆ (x 1 )) + ν∥u -u ⋆ (x 1 )∥ 2≤ -(u -u ⋆ (x 1 )) ⊤ ∇H(x 1 , u 1 ) -∇H(x 1 , u)-(u 1 -u) ⊤ ∇H(x 1 , u 1 ) -∇H(x 1 , u ⋆ (x 1 ))-ν ∥u 1 -u∥ 2 -2ν ⟨u 1 -u, uu ⋆ (x 1 )⟩.We bound Ω 1 , Ω 2 , and Ω 3 separately.• For Ω 1 , we have-(u -u ⋆ (x 1 )) ⊤ ∇H(x 1 , u 1 ) -∇H(x 1 , u) ≤ Diam U • ℓ H ∥u 1 -u∥ ≤ Diam U ℓ H L c ∥x 1 -x 2 ∥ .• For Ω 2 , it holds that -(u 1 -u) ⊤ (∇H(x 1 , u 1 ) -∇H(x 1 , u ⋆ (x 1 ))) ≤ L c ∥x 1 -x 2 ∥ • ℓ H Diam U .• For Ω 3 , since the first term is always non-positive, we only need to bound the second term:-⟨u 1 -u, uu ⋆ (x 1 )⟩ ≤ ∥u 1 -u∥ ∥u -u ⋆ (x 1 )∥ ≤ L c ∥x 1 -x 2 ∥ • Diam U .Combining Ω 1 , Ω 2 , and Ω 3 , we conclude that (u -u ⋆ (x 1 )) ⊤ ∇H(x 1 , u) -∇H(x 1 , u ⋆ (x 1 )) + ν∥u -u ⋆ (x 1 )∥ 2EQUATION)Plugging in u ← u ⋆ (x 2 ) in ( 64) and combine it with (63), we get ν∥u ⋆ (x 2 ) -u ⋆ (x 1 )∥ 2 ≤ (u ⋆ (x 2 ) -u ⋆ (x 1 )) ⊤ ∇H (x 2 , u ⋆ (x 2 )) -∇H (x 1 , u ⋆ (x 2 ))+ L ′′ ∥x 1 -x 2 ∥ ≤ ℓ H ∥u ⋆ (x 2 ) -u ⋆ (x 1 )∥∥x 1 -x 2 ∥ + L ′′ ∥x 1 -x 2 ∥.WhereL ′′ = (1 + 2ℓ H )L c Diam U + 2L c L H .Similarly to Lemma C.8, we can set λ = ∥u ⋆ (x 2 ) -u ⋆ (x 1 )∥ and χ = ∥x 1 -x 2 ∥ and consider the inequality νλ 2 ≤ ℓ H λχ+L ′′ χ. We aim to find the solution of the formℓ H χ+ √ χ(4νL ′′ +ℓ 2 H χ) 2ν ≤ c √ χ.By setting L ⋆ = c and solve for c givesL ⋆ = 1 2ν 2ℓ H Diam X + 2 ν(1 + 2ℓ H )L c Diam U + 2νL c L H .Finally, we show that Φ is differentiable and Hölder-continuous. Theorem D.2. Let function Φ be Φ(x) := max u∈U (x) {H(x, u)}. Its gradient ∇Φ is (1/2, ℓ 1/2 )-Hölder continuous,∥∇Φ(x) -∇Φ(x ′ )∥ ≤ ℓ 1/2 ∥x -x ′ ∥ 1 2 ,where ℓ 1/2 := (1 + L c -1 ) √ Diam X + L c -1 L ⋆ ℓ.Proof.∥∇Φ(x) -∇Φ(x ′ )∥ = ∇f x, c -1 (u ⋆ (x); x) -∇f x ′ , c -1 (u ⋆ (x ′ ); x ′ ) ≤ ℓ ∥x -x ′ ∥ + ℓ c -1 (u ⋆ (x); x) -c -1 (u ⋆ (x ′ ); x ′ ) ≤ ℓ ∥x -x ′ ∥ + ℓL c -1 (∥u ⋆ (x) -u ⋆ (x ′ )∥ + ∥x -x ′ ∥) (65)EQUATION≤ (1 + L c -1 ) Diam X + L c -1 L ⋆ ℓ ∥x -x ′ ∥ 1 2 .• in (65) we invoke the Lipschitz continuity of function c -1 (•);• (66) follows from Theorem D.1.Following, SGDMAX is presented where we assume a stochastic gradient oracle G = (G x , Gy) : 1) , y (t) , ξX × Y × Ξ → R d thatĝ(t) ← 1 M M j=1 G x x (t-x (t) Proj X x (t-1) i -η x ĝ(t) guarantees that there exists a t * ∈ [T ], such that, -∇ x f x (t ⋆ ) , y (t ⋆ +1) ⊤ x ′ -x (t ⋆ ) ≤ ϵ, ∀x ′ ∈ X ;∇ y f x (t ⋆ ) , y (t ⋆ +1) ⊤ y ′ -y (t ⋆ ) ≤ ϵ, ∀y ′ ∈ Y. Proof. The proof follows easily from the proof of projected gradient ascent in hidden-stronglyconcave function found [43, Theorem 6] and Theorems B.1 and D.2.Remark 2. It has been shown that when a function f enjoys a hidden-strongly-concave reformulation, it satisfies global the Proximal-PŁ condition (or equivalently, global KŁ condition) [43, 67] . While the equivalence between global KŁ condition and quadratic growth condition has been proven [10, 38] when f 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.• Researchers should communicate the details of the dataset/code/model 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 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? 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. • Including this information in the supplemental material is 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 of Ethics, workers involved in 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 Subjects 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 an 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 be required for any human subjects research. If 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 NeurIPS 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.[18] Y.Cai, A. Oikonomou, and W. Zheng. Finite-time last-iterate convergence for learning in multi-player games. In S. 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, NeurIPS 2022, New Orleans, LA, USA, November 28 -December 9, 2022, 2022. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: (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).

(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?

(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).

(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).
questions: questions: See "weaknesses" above.
limitations: 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).
paper_summary: paper_summary: This paper investigates the identification of NE in ATMGs. The authors explore the underlying landscape, leveraging optimization theory to effectively solve this problem.
strength_weakness: strength_weakness: 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.

I 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.
questions: questions: check weaknesses
limitations: limitations: check weaknesses
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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].
- 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.
- 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.
questions: 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? 
- 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? 
- 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$.
- 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: 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].
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

But after the following point:

- 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)

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.

To 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. 

- Maybe one way is to show hardness results on some finite state-action ATMGs?
- 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?

Future work statement from line 329:

> variance-reduction techniques to achieve a better sample complexity

Is there any conjecture as to how much VR methods save in terms of sample complexity?

As I am in a dilemma, my current score reflects that. I'll update it after the authors-reviewers discussion period. Thanks!
questions: questions: na
limitations: limitations: na
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

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

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

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

- The proposed policy gradient method assumes policy coordination between team and adversary, which often is not the case in practice. 

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

- The polynomial iteration/sample complexities of the proposed policy gradient method are highly sub-optimal in terms of rates and problem dependence.

- The proposed policy gradient method is limited to problems with small state/action spaces, leading dimension scalability issue. 

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

- There are no experimental justifications of the proposed policy gradient method.
questions: questions: Here are other questions for improvement.

- What rewards do team take? It is not clear from Section 2.2.

- What is reformulation in line 207? a confusing inter product notation. 

- unclear notation: $\Delta(\mathcal{A})$, $\boldsymbol{r}(\boldsymbol{x})$, $\hat{\boldsymbol{g}}_i$, $\mathcal{K}^{(t)}$, $\boldsymbol{x}^{(T)}$, etc.

- Why do you need $\zeta$-greedy policy? How does policy gradient projection work in Algorithms 1-2? 

- wrong index: $k\in[n]$ lines 3-4 of Algorithm 1.
limitations: limitations: No

Comments: title: Acknowledgement of reviewing the rebuttal
I re-increased my score
Apologies and Clarification
I will decrease the score
What was not satisfactory in our response?
Thank you
Variance reduction and potential improvements on sample complexity
Value reformulation and References
comment: Dear Reviewer,

We thank you for your response. **We would appreciate it if you could specify how we have not fully addressed your concerns.** Understanding your perspective is important to us. We feel confident that our responses were thorough, and it is disappointing to receive limited feedback given the effort we put into our rebuttal.

Please remember that *this is a theoretical paper*, and we believe it should be judged according to the relevant standards. It is vital for the benefit of the broader community that your counterarguments are shared with the authors.

In our view, the discussion phase is vital for fostering scientific dialogue between authors and reviewers, which is crucial for maintaining the conference's quality. This interaction enhances the overall quality of research and papers, whether or not they are eventually published at this venue.

Sincerely,

The Authors
Dear reviewer,

Thank you for your reply. **We would kindly ask the reviewer to let us know in what ways we did not adequately address their concerns.** We would like to know what is the reviewer's thoughts. We are pretty confident that we answered your concerns sufficiently and the feedback you are giving us is particularly restricted, especially when we put a significant amount of effort in replying. Please again take into consideration that this is a theoretical paper and we strongly believe it should be judged by corresponding standards.

We do not believe that it is fair to the broader community to not share your counterarguments with the authors of the paper.

To our experience and understanding, the discussion phase is specifically meant to allow scientific dialogue between authors and reviewers to flourish. This is crucial to the conference's quality. This peer-reviewing process helps the community improve the overall quality of papers and research; regardless if a paper gets published to that particular venue or not.

Sincerely,

The authors
Thank you for reflecting on the reviews. I have updated my score from 4 to 5. Good luck.
I have reviewed the rebuttal. However, my questions have not been addressed satisfactorily. I will keep my score unchanged.
Thank you for your response. I would like to keep my initial evaluation.
I see. Thank you so much! I appreciate it, and got author's point.
We kindly apologize if we offended you. This goes well beyond our intentions! We are asking in order to be able to further improve our work -- this was our sole intention. We do not take your time for granted and we are grateful for the effort you put into the review and indeed you made yourself clear in not wanting to discourage us. We also do not take for granted that the rebuttal should increase the score. 


Having said that, we think that there is some misunderstanding:
> I know that it is not easy to prove Lemma C.1 and C.2 (i.e., not taken for granted), but many papers have already used that fact. The Lipschitzness of the value function and the gradient of the value function are now almost taken for granted, as far as I know. I also do RL theory and game theory.

**We never claimed lemma c.1 and c.2 are novel**. We claim that Theorem 3.2 (Holder continuity of the gradient of the regularized max function, $\Phi^\nu$--this is weaker than being Lipschitz continuous) is novel, which can be used along the novel Theorem 3.1 (convergence of gradient descent when the gradient is not Lipschitz in constrained nonconvex objectives) to finally end up with our main game-theoretic result (Theorem 3.3). The team agents are running policy gradient on a function that **does not** have Lipschitz gradients (as is the case for virtually all RL applicaiton) and the method still provably converges. We hope this clarifies our claims.

>Now I will oppose this paper being accepted to NeurIPS. I do not think that a similar paper being accepted to NeurIPS should be the reason for this paper to be accepted. For example, should a traditional VAE related paper be accepted just because it was the best paper before? I do not think so.

Our claim is not that our paper should be published; as this is for the conference contributors to decide. We would never claim it should be published based on similarity. We do claim that we solve an open problem of a previous paper that was distinguished in ICLR '23; all the while introducing new optimization results of independent interest.
I feel really bad about your comment. I already mentioned to the AC that I do not want to review as I do not wish to discourage the people who work on pure theory. My score is not affected by the suitability to this conference, and I also mentioned I do not want to discourage the authors. However, I do not understand why the authors think that rebuttal should increase the score.

Now I will oppose this paper being accepted to NeurIPS. I do not think that a similar paper being accepted to NeurIPS should be the reason for this paper to be accepted. For example, should a traditional VAE related paper be accepted just because it was the best paper before? I do not think so.

This was what I deleted (not to discourage the authors) in my previous private comment:
>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. 

>Despite my reservations about its fit for NeurIPS, I do not wish to officially discourage the authors. My thoughts might be only for me and not reflective of the broader community focused on optimization theory. Therefore, I am inclined not to submit my review.

>Theorem 3.1 stands out with significant contributions, while the other theorems, in my view, merely adapt the MARL problem to a specific instance of an optimization problem. 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.

> I hope this comment helps in your decision-making process. Feel free to share it with other reviewers, but I would prefer it not be shared with the authors since my primary concern is about the paper's venue suitability. If AC thinks that paper is not in the borderline (either accept or reject), AC does not need to consider my comments.

I know that it is not easy to prove Lemma C.1 and C.2 (i.e., not taken for granted), but many papers have already used that fact. The Lipschitzness of the value function and the gradient of the value function are now almost taken for granted, as far as I know. I also do RL theory and game theory.
Thank you for your response.

Given that our paper is primarily theoretical, it should be assessed on its theoretical contributions. For context, please refer to our response to Reviewer hEh5, where we list similar papers published in conferences such as NeurIPS, ICML, ICLR, and COLT. These conferences consistently feature numerous theoretical papers each year. We have meticulously addressed all the concerns raised by the reviewers and made substantial efforts in designing and executing experiments to bolster our findings.

Could you please clarify the reasoning behind maintaining the same score? Were our revisions insufficient in addressing your comments?
Thank you for your comment. I will maintain my score.
> *"Is there any conjecture as to how much VR methods save in terms of sample complexity?"*

We believe that it might be possible through a careful design of the estimators (possibly along with a different parameterization of the policy) and bypass the $\zeta$-greedy technique to bound the variance. In this case the sample complexity can be improved by a factor of $O((1 - \gamma)^{15} \epsilon^3)$.
__Reformulation__

Let us restate some definitions to make this reformulation clearer. We start from the value function, which is a scalar:
$\begin{align}
 V_{\rho}(x,y) = E  {[ \sum_{h=1}^{\infty} \gamma^{h-1} r( s^{(h)}, x,b) | s^{(0)} \sim \rho ]}
\end{align}$.

Then, we define the adversary's state-action visitation measure, which can be thought of as a vector in ${R}^{|S||B|}$:
$$ \lambda_{s,b}( y; x) =  E [ \sum_{h=1}^{\infty} \gamma^{h-1} \mathbb{I} (s^{(h)} = s, b^{(h)} = b) | s^{(0)} \sim \rho ]   $$

Finally, $(s,b)$-th entry of the vector $\boldsymbol{r}(\boldsymbol{x}) \in \mathbb{R}^{|S| |B|}$.
$$ {r}_{s,b}(\boldsymbol{x}) =   E [r(s,a, b)] $$ with the expectations taken over $\boldsymbol{a}\sim \boldsymbol{x}$.

Hence, the inner product $\boldsymbol{r}(\boldsymbol{x}) ^\top \boldsymbol{\lambda}(\boldsymbol{y}; \boldsymbol{x})$ will be equal to the summation:
$$ \sum_{(s,b) } \Big(  {\mathbb{E}} [r(s,\boldsymbol{a}, b)] \cdot {\mathbb{E}} [ \sum_{h=1}^{\infty} \gamma^{h-1} \mathbb{I} (s^{(h)} = s, b^{(h)} = b) | s^{(0)} \sim \rho ] \Big)  .$$

From the last, display we can see that the inner product is equal to the value function.

We would thank the reviewer again for spending their valuable time to provide feedbacks. We would really appreciate if the author would consider raising their score.

Best regards,

The authors

---

__References__

[1] Zhang, J., Koppel, A., Bedi, A.S., Szepesvari, C. and Wang, M., 2020. Variational policy gradient method for reinforcement learning with general utilities. NeurIPS

[2] 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

[3] Cui, Q., Zhang, K. and Du, S., 2023, July. Breaking the curse of multiagents in a large state space: Rl in markov games with independent linear function approximation. COLT

[4] Agarwal, A., Kakade, S.M., Lee, J.D. and Mahajan, G., 2021. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. JMLR

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

[6] Zhang, R., Mei, J., Dai, B., Schuurmans, D. and Li, N., 2022. On the global convergence rates of decentralized softmax gradient play in markov potential games. NeurIPS

[7] Wei, C.Y., Lee, C.W., Zhang, M. and Luo, H., 2021, July. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. COLT

[8] 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

[9] Leonardos, S., Overman, W., Panageas, I. and Piliouras, G., Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games. ICLR

[10] Erez, L., Lancewicki, T., Sherman, U., Koren, T. and Mansour, Y., 2023, July. Regret minimization and convergence to equilibria in general-sum markov games. ICML

[11] Giannou, A., Lotidis, K., Mertikopoulos, P. and Vlatakis-Gkaragkounis, E.V., 2022. On the convergence of policy gradient methods to Nash equilibria in general stochastic games. NeurIPS

[12] Park, C., Zhang, K. and Ozdaglar, A., 2024. Multi-player zero-sum Markov games with networked separable interactions. NeurIPS

[13] Cen, S., Chi, Y., Du, S. and Xiao, L., 2023, January. Faster last-iterate convergence of policy optimization in zero-sum Markov games. ICLR

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