Solving Zero-Sum Convex Markov Games
Authors: Fivos Kalogiannis
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Ian Gemp
Georgios Piliouras
Venue: ICML 2025 poster (2025)
Keywords: Markov games
convex RL
regularization
Polyak Lojasiewicz condition
proximal Polyak Lojasiewicz
nonconvex min-max optimization
zero-sum games
gradient domination
hidden convxity
composite optimization
min-max optimization
policy gradient methods
alternating gradient descent-ascent
gradient descent ascent
two-timescale gradient descent-ascent
nested gradient iterations
policy gradient methods
Primary area: theory->game_theory
TL;DR: Efficient Policy Gradient Methods to compute Nash Equilibria in Zero-sum Convex Markov Games

Abstract: We contribute the first provable guarantees of global convergence to Nash equilibria (NE) in two-player zero-sum convex Markov games (cMGs) by using independent policy gradient methods. Convex Markov games, recently defined by Gemp et al.(2024), extend Markov decision processes to multi-agent settings with preferences that are convex over occupancy measures, offering a broad framework for modeling generic strategic interactions. However, even the fundamental min-max case of cMGs presents significant challenges, including inherent nonconvexity, the absence of Bellman consistency, and the complexity of the infinite horizon.

Our results follow a two-step approach. First, leveraging properties of hidden-convex–hidden-concave functions, we show that a simple nonconvex regularization transforms the min-max optimization problem into a nonconvex–proximal Polyak-Łojasiewicz (NC-pPL) objective. 
Crucially, this regularization can stabilize the iterates of independent policy gradient methods and ultimately lead them to converge to equilibria. Second, building on this reduction, we address the general constrained min-max problems under NC-pPL and two-sided pPL conditions, providing the first global convergence guarantees for stochastic nested and alternating gradient descent-ascent methods, which we believe may be of independent interest.

Solving Zero-Sum Convex Markov Games
Fivos Kalogiannis Emmanouil- Cinmanoul-Vaasiliios
Vlatakis-Caaragkounis
Ian Gemp? Georgios Piliouras
Abstract
studi-s how multiple agents interact within shared, dynamic environment to optimize their individual cumu- lative rewards (Silver et al., 2017; Lanctot et al., 2019). However, many real-world applications require a more ex- pressive formulation of agent preferences that do not simply decompose additively over time (Puterman, 2014; Zahavy et al., 2021). To address this limitation, the emerging frame- work of convex Markov games (cMGs) (Gemp al., 2024) has been proposed as principled yet flexible model for capturing complex multi-agent interactions in dynamic envi- ronments. Unlike traditional MGs, cMGs allow for convex utility functions over the state-action occupancy measure, enabling a richer set of players' preferences that better re- flect practical applications. In this context, the occupancy measure of each player reflects the frequency of visiting any particular state of their corresponding Markov decision processes (MDPs), over potentially infinite time horizon.
We contribute the first provable guarantees of global convergence to Nash equilibria (NE) in two-player zero-sum convex Markov games (cMGs) by using independent policy gradient methods. Convex Markov games, recently de- fined by Gemp et al. (2024), extend Markov deci- sion processes to multi-agent settings with prefer- ences that are convex over occupancy measures, offering broad framework for modeling generic strategic interactions. However, even the funda- mental min-max case of cMGs presents signifi- cant challenges, including inherent nonconvexity, the absence of Bellman consistency, and the com- plexity of the infinite horizon. Our results follow two-step approach. First, leveraging proper- functions,
ties of we show that simple nonconvex regularization transforms the min-max optimization problem into a nonconvex proxximal (NC-pPI.) objective. Crucially, this regulariza- tion can stabilize the iterates of independent pol- icy gradient methods and ultimately lead them to converge to equilibria. Second, building on this reduction, we address the general constrained min- max problems under NC-pPL and two-sided pPL conditions, providing the first global convergence guarantees for stochastic nested and alternating gradient descent-ascent methods, which we be- lieve may be of independent interest.
In practice, cMGs are useful for modeling a variety of challenging multi-agent settings, including:
(i) Fostering creativity in machine gameplay, such as dis- covering novel strategies in chess (Zahavy al., 2022; 2023; Bakhtin et al., 2022), (ii) multi-step language model align- ment (Wu et al., 2025), (iii) enhancing multi-agent explo- ration in robotic systems (Burgard et al., 2000; Rogers et al., 2013; Tan et al., 2022), (iv) ensuring safety in autonomous driving (Shalev-Shwartz et al., 2016), (v) enabling imitation learning from expert demonstrations, and (vi) promoting robustness and fairness, in multi-agent decision-making (Hughes et al., 2018). While the former (i-iii) are direct instantiations of cMGs, the latter (iv-vi) will profit when from cMG formulation.
1. Introduction
In general, the authoritative desirable outcome of a multi- agent scenario is some sort of game theoretic equilibrium. Given the plethora of cMG applications, a natural question arises: are there algorithmic solutions for provable equi- librium computation in these games already? Surprisingly, this is not the case! Notwithstanding the model's appeal, an array of technical challenges arise that impede straight- forward algorithmic solution. Yet. empirical results suggest that variants of policy gradient methods (Williams, 1992) can actually lead to favorable outcomes.
The field of multi-agent reinforcement learning (MARL)-often framed as Markov games (MGs) (Littman,
'Department of Computer Science & Engineering, University of California, San Diego, La Jolla, CA. USA 'Deaarmeent of Com- Madison, WI,
puter Sciences. University of Wisconsin-Madison USA and Archimedes, Athena Reaserch Center, Greece Google DeepMind, London, UK. Correspondence to: Fivos Kalogiannis <fkalogianii@@ness @dc...cdu>.
Proceedings of the 4rnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
Following this thread, we consider the simplest reason- able setting, competition between two agents, and pose

---

Solving Zero-Sum Convex Markov Games
central question:
understanding of the optimization landscape of cMDPs and cMGs. For instance, in the min-max case, the computa- tional complexity of the general problem of computing a saddle-point of a remains far from being settled (Daskalakis et al., 2021), while no algorithm is yet guaranteed to efficiently compute them without additional structural assumptions.
Do policy grudient methods converge in zero-sum convex Markov games?
smooth function
We answer this question in the affirmative. More explicitly, we provide an algorithmic framework that is efficient, ad- heres to the independent learning desideratum (Daskalakis et al., 2020), and is simultaneously easy-to-imp templemmmmmemmnnt. This effectiveness is powered by novel technical insights to ad- dress numerous technical challenges native to cMGs.
Searching for structure, we observe that the utilities in cMGs exhibit property known as hidden convexity (Ben- Tal & Teboulle, 1996; Li et al., 2005; Wu et al., 2007; Xia, 2020; Vatakis-Gkaragkounii et al., 2021; Fatkhullin et al., 2023). However, the existing results on hidden convexity either focus on single-objective minimization or, in the con- text of continuous games, make assumptions that do not hold in cMGs (separability of the hidden mapping and un- constrained variables). Having identified the key difficulties of zero-sum eMGs, in the following section we offer de- tailed account of how we tackle them. Briefly, we manage to overcome the aforementioned challenges using some dis- tinct combination of the following algorithmic techniques: (i) conceptually simple but nonconvex regularization of the utility function; (ii) alternating gradient iterations (Tam- melin et al., 2015; Chavdarova et al., 2021; 2019; Zhang & Yu, 2019; Chambolle & Pock, 2011); (iii) careful timescale separation of the individual step-size, and lastly (iv) nested- gradient iterations.
Getting into the weeds, we enumerate the technical chal- lenges that cMGs pose. As cMGs are strict generalization of cMDPs, the Bellman consistency of the agents' utility functions fails to hold (Zhang et al., 2020}-in short, we cannot define individual value and action-value functions. Remarkably, this is a family of long-horizon strategic inter- actions where agents cannot use dynamic programming as opposed conventional MGs. We note that, even though most policy optimization methods rely gradient- based approach, their majority implicitly performs an approximate dynamic programming subroutine such as value-iteration (Jin et al., 2021; Wei et al., 2021; Ding et al., 2022; Erez et al., 2023).
Consequently, the absence of state-wise funetioun translates into a failure of the elementary arguments that were used to prove the existence of Nash equilibria (Fink, 1964), even in two-player zero-sum Markov games (Shapley, 1953). In light of the latter, Gemp et al. (2024) prove the existence of Nash equilibria in cMGs by going beyond the fundamental toolbox of the Brouwer and the Kakutani fixed point theorems. What renders these conventional theorems obsolete is the inherent nonconvexity of the individual best- tiliiies-werre
1.1. Technical Overview
The proof of the proposed theoretical guarantees comes after a combination of several key observations-ole and new. We believe that exposing them in the following item- ized manner will serve in conveying the technical level of our work and an intuitive overview of why our techniques work.
response mappings in terms of players' each best-response mapping yields the set of the agent's 's set of utility maximizing strategy deviations.
Hidden convex functions are nonconvex functions that can be expressed as convex function of a reparametriza- tion of their original arguments, termed the "hidden (la- tent) mapping," " while the original arguments are called "control variables". Yet, in some settings, like reinforce- ment learning (RL), this mapping is not at all hidden but directly computable or observable.
The careful reader might already grasp that the failure of Bellman consistency rules out the seamless application of the majority of MARL algorithms; most of them rely on computing value and action-value functions. We direct our hopes to policy gradient methods which theory of cMDPs and practice of MARL suggest can work. Directly optimiz- ing a policy means facing an optimization landscape that is nonconvex. However, since all local optima are also global in cMGs should bring some hope. Nonetheless, why should policy gradient methods work in cMGs when vanilla gra- dient following methods cycle (Bailey & Piliouras, 2018) and exhibit non-convergent chaotic trajectories even in zero- sum two-player normal-form games? Observe that the latter are nothing but cMGs on a single state with individually linear utilities. Further, even if we stabilize gradient dynam- ics towards Nash equilibria, attaining strong convergence guarantees of an algorithm requires the deepening of our
More specifically, in eMGs, players' utilities are hid- denly concave through the state-action occupancy mea- sure, which is similarly computable (in planning) ob- servable (in RL).
Although analyzing these games via occupancy measures yields a quasi variatiariati inequality problem (Kinder- lehrer & Stampacchia, zunee-luneyyssaailyyyy increasing the technical challenges (Bernasconi et al., 2024)-yct, two crucial facts remain: (i) the utility is concave with re- spect to the hidden mapping, and (ii) the hidden mapping is accessible. These properties ensure that after regular-
2

---

Solving Zero-Sum Convex Markov Games
ization, the hidden function becomes strongly concave. In turn, the resulting function satisfies the proximal Polyak- Lojasiewicz (pPL) condition, with respect to the control variables (i.e., the policies).
Key ingredients. To establish our results, we leverage set of incorporating the distinct combination of the fol- lowing non-trivial components: (i) intuitive stability- inducing specialized regularization of the utility function and (ii) alternating or (iii) mested-gradienn iterations.
Consequently, each player's utility remains pPL while the feasibility sets for their control variables remain in- dependent. This observation wraps up the discussion on hidden concavity and naturally shifts our focus on the constrained optimization of min-max nonconvex-pls ob- jectives. In other words, we reduce solving two-player zero-sum convex Markov games to the problem of com- puting saddle-points of functions that are nonconvex-pPl. over constrained domains.
A noteworthy element of our approach that it ensures convergence even with inexact gradients on top of being stochastic. The algorithm''s robustness to gradient inexact- preserves each player's autonomy, allowing them to op- timize independently without exchanging private policy in- formation. I.e., unlike the single-agent setting, where exact gradients can be stochastically estimated, our framework's ss regularizer depends on both players' policies, making exact estimation infeasible without policy sharing. Consequently, each player must rely solely on an inexact estimation of their own gradient.
Leveraging this reduction, our final steps center on devel- oping policy gradient methods that can provably converge to saddle-points of nonconvex-pPl. functions over con- strained domains, technical development in optimiza- tion theory of independent interest as well.
Finally, a noteworthy product of our approach is the Lips- chitz continuity of the best-response mapping (which returns the optimal strategy given the opponent's 's choices) in the hidden-convex case-and more generally nonconvex-pPL- despite the opponent's utility being nonconvex cetevvee-ooottattinn with the typical 5- 5-Hölder continuity of maximizers in con- strained optimization (Li & Li, 2014). Indeed, while (Kalo- giannis et al., 2024) employ similar technique of regu- larizing the value function through the occupancy measure perspective, their result only establishes a weaker notion of continuity due to the coupledness of individual play- ers' state- action occupancy measure. This claim has been independently supported by (Papadimitriou et al., 2023, Ro- bust Berge Theorem), which considers general nonconvex- strongly concave functions where the feasibility sets of two different strategies depend on each other in Hausdorff con- tinuous manner. To significantly strengthen the continuity of the best-response mapping, we leverage the pPL condition in the individual policy spaces of agents that remain uncoupled. This result was only known for the significantly simpler case of unconstrained two-sided PL functions (Nouiehed et al., 2019).
The proofs are deferred to the Appendix for clarity.
1.2. Our Contributions
Before proceeding to enumerate all parts of our contri- butions, we remark that we deliver a definitive answer to question (*))
There exist decentralized policy gradient meth- ods (Algorithms! and 2) that compute an e-approximate Nash equilibrium for any e >> 0 in any two-player zero-sum convex Markov game using iterations and samples that are:
Theorem.
poly (111 1B],
1
with S denoting the cMG's state-space, A, B the two play- ers' action-spaces, and y > 0 the discount factor.
Our contributions span two key areas: constrained non- convex min-max optimization and equilibrium computation in convex Markov games.
2. Preliminaries
In Theorem 4.1 we demonstrate that the best-response mapping for an objective f(z, y), + y² (z) == arg max (x,, is Lipschitz continuous in x: for reg- ularized hidden-comvex-andd more generally, NC-pPL games. The significance of this result lies in guaranteeing the stability of the iterates of policy gradient methods and serves as a suggestion to practitioners looking for regularization technique that is intuitive, simple, and casily implementable.
Notation. In general, x, n, w and A1 A will denote vectors. Scalars will be denoted using a, 3, 6, e, C, K,,,K,,,, and a, b, d. Matrices will be de- noted with bold uppercase letters. The probability simplex supported on finite set M will be denote with A (MM). For compact convex set Z C Rd, we will denote its Euclidean diameter as Dz, i.e., Dz = maxx,e ||X 3/l2- Lastly, the global optimum of a function ff will be denoted as ft.
In Section 4, we provide the first provable guarantees of convergence to a Nash equilibirum for two policy gradient algorithms Nest-PG and Alt-PGDA (Theorem 4.3).
3

---

Solving Zero-Sum Convex Markov Games
2.1. Convex Markov Games
overloading notation, (2, y) and A2 y) are the unique occupancy measures for policy pair æ; y- Finally, we will at times suppress the notation Fi (Ai (I, y); y) in place of Fi (A1 (z, A2 y)) and similarly for Fg.
In this subsection, we define two-player zero-sum convex Markov games (Gemp et al., 2024) and introduce necessary notation. We then present the occupancy measure and re- mark its continuity properties. Subsequently, we review the policy gradient theorem for convex MDPs and describe a stochastic policy gradient estimator. Finally, we define the perturbed utility function U" obtained by adding a regular- ization term to the original utility function U.
Crucially, both the occupancy measure and its inverse operators satisfy the following continuity properties:
Lemma 2.1 (Continuity of the occupancy measure). Let À E ASS x A B) be the occupancy measure in a (convex) Markov game and let X A(S x A) + X and X (S B) + be the occupancy-to-policy mapping such x; x²² (22 v)) y. Then,
Definition (Two-player zero-sum cMG). An infinite- horizon zero-sum convex Markov game is a tuple r (8, A, P,, 0)
that: XT (>1
À is Lx-Lipschitz continuous and has an Ex-Lipschitz continuous gradient with respect to the policy pair (2, v) in X x y. Specificalll, for all (xr, y) and (x',y'),
a maximizing and minimizing player, finite state space S, and an initial state distribution
Q E (SS),
[M v) - A(x', ./)1 & LA (1 v) (x',8')1 | () - VA(=', s/)ll - Ex [(x,)) (z', 1/)),
finite action spaces A, B, state transition function TP: S x x B A(S).
discount factor y E [0, 1), and
where LA == 18| ((AI+188 and lx == 2 (1A++111 (1-7)²
two continuous utilities F,, F2 functions correspond- ing to each player's occupancy measure, i.e., there exist concave F1, F2
(1-7)²
For any fixed y (respectively, x), X- is LA i-Lipschitz continuous with respect to X1 (respectively, d2), ie. for all >1 y), A1 (1 ()) respectivvl,, >2(2, v), (2(2,
F : ASS X A) X A(S x B) + R;
F2 ASS x A) X ASS x B) + R
|| x' - - || (21(2, - (():v)))]; |I 3/ || - レدー || (A2(22, >2(2,
with- -F ==== F2 F.
With all this in hand, we adopt the following standard assumptions, which are widely used in prior work (Zhang et al., 2020):
with 1x-1 min, 0(3)
Next, our solution concept corresponds to the following min-max Nash equilibrium of the following function U ((4) $I x ( $ + R be such that:
Assumption 1. For the initial state distribution, it holds that o(s) > 0, Vs.
U(x, v) F (A1 (2) )2(x.
Additionally, we assume direct policy parametrization and define the Markovian and stationary policy of the mini- mizing and the maximizing player be x E A(A))S) =: X and y E (BB) =: y respectively. Throughout, we only consider Markovian stationary policies. After the agents fix their policies, x, y. the transition matrix P(z; v) E IR 5|x dictates how they traverse the state space. The occupancy measures are defined as:
Definition 2 (E-NE). A policy profile (x", (x",2") X x 3 is said to be an e-approximate Nash equilibrium (c-NE). if for any x E X and any e V, it holds that:
U(x" - c U( .1' +xx,0)+ (cNNE
Finally, we will denote U to be: U'(I v) = U (A(z, v)) - (2, v) 112. The following Lemma is a direct consequence of hidden-strong- convongc.
xiaa = (1 - Ex. EN (1( = =, (,) = a} [0]
A1 b = (1 Bz,
Σn " (1(((h) s, ((h)) b)1e]
Lemma 2.2. When p > 0, U'(2,) -) has unique maximizer y" for, all x.
Further notation. Further, we denote À to be the state- joint-action occupancy measure, À E A(S x A x B). Over- loading notation, A(x, u) stands for the unique occupancy measure that corresponds to the policy pair 2, y. Addi- tionally, ' E A(S x A), X2 E A(S x B) will signify the marginal occupancy measures with respect to the min- imizing and the maximizing player respectively. Again,
2.2. Policy Gradient Estimators
As discussed, the inexistence of value or action-value functions for general utility MDPs, leads us to focus on policy gradient methods; the direct application of vanilla Q-learning methods is out of the question. To compute

---

Solving Zero-Sum Convex Markov Games
the policy gradient of a utility that is nonlinear in A1, we make use of the (Williams, 1992) along the chain rule of differentiation to write:
Claim 2.3. The function U is hidden-convex (resp., hidden- concave) for the min. player (resp.. max. player), given fixed action of the opponent. Similarly, the perturbed williyy function UH is (p., (xx-))-hidde strongly concave for the max player due to the structure of the regularizer.
VzU(z. EE
EE OF
5:a (z. v). V2
V.
RES O (x,
Proof. Follows from Definitions and 4 & Lemma 2.1.
By sampling trajectories, each agent can stochastically esti- mate the policy gradient using the following estimator.
Proposition 2.4 (HC implics gradient domination; (Fatkhullin et al., 2023)), Let f X - IR. be an t-smooth convexfunctionn tor function of the set X. Further, let F(-) ==))=//) 5() + (x(()) Also, assume that the map d() is continuously differentiable on X.
Definition 3 (Gradient Estimator). Given trajectory = (s!0), a (0))) , s(H-1), ((H-1)) of length H sam- pled under policy profile x, y and initial distribution o. the gradient estimator, 92 (E)2z, 2), is defined as:
and (Jes PH -hidden convex function and Ix be the indica-
Oz. (6)z2,2)
(i) If the set X' = =((2) is bounded with diameter Du, then
H-1
h log (att ((03)1(0)))
Σ 0=
7=2
all))
Σ
V
inf
||s2|| 2
Me
- (F) Ye E X.
8, 6, (u)
Du
with (i)
(i) If is (He, PH) (acc -hidden strongly convex, then inf || 2 2n (F(x)- Ft), Vz E X.
Sufficient exploration In order to ensure that the agents sufficiently explore the environment and ultimately control the variance of the estimators, we assume that both agents are following e-greedy direct policy parametrization, i.e. for a given parameter value x E A ( (AA), , the agent plays according to म (1 - =)xx + =1 vector of appropriate dimension.
82 (BF())
Definition 5 (pPL). Let an f-smooth function f X + R defined over the convex and compact set X S Rdd Let Dx(, () be defined
[A] where 1 is an all-ones
Dx(2, == 22 min (Vf(x). - 2) + 2 12 vll wEX
2.3. Optimization Theory
Then, f is said to satisfy the proximal condtion with modulus μ if for all x E X, it holds true that:
Next, we introduce several key concepts from nonconvex and min-max optimization, focusing on hidden convex- ity and gradient domination conditions. We demonstrate how strong hidden convexity implies the proximal Polyak- tojasiewicz condition (pPL.) and the quadratic growth con- dition (QG). We then show that when a min-max objective satisfies a two-sided gradient domination condition, it enjoys a zero duality gap.
2f f*).
Our following lemma establishes a variant of the "gra- dient dominance" for the case of convex Markov games. Namely show that an approximate constrained first-order stationary point ensures approximately optimal policies in our game.
Definition& 4 (Hidden Convex Function). Consider a func- tion f X + IR where X is a compact convex set such that fx) == (c(z)), Vx X' for some mapping e and function H. If the following conditions are satisfied:
Lemma 2.5 (Gradient Dominance). For a zero-sum convex Markov game, it holds that:
max (V (VU((z x²) 2 pz (U v) U(=",") ,y)): x' x'EX
the mapping e is invertible and its inverse - is 1/pe Lipschitz continuous.
max (V ((,,))) - v) 2011 (U(x, ((1 U(x y'Ey
the set == <(X') is convex and the function H : - R is st--snongly convex.
for Pas By (1-7) min, p(s)
2/2
The function is said to be (Per μn) -hidden strongly convex (HSC), while for s* 0, it is referred merely as hidden convex (HC).
Proof. Fix an arbitrary y E Y. By the hidden convexity of U(, y) and Proposition 2.4, we have:
(1 7) min, e(s)
((x,y)
min U(a", ,y)
Notably, the convergence analysis of our proposed meth- ods begins with the following claim, which connects cMG utilities to hidden convexity.
2/2
FEE
<
min
||32||.
8,E0_U (.E00U(e))+000x(()
5

---

Solving Zero-Sum Convex Markov Games
Where, 2 is the diameter of the state-action occupancy measure. Applying (Rockafellar & Wets, 2009, Proposition 8.32), we obtain:
translated the pPL. condition going through an argument which degrades the modulus of HSC fa to pPI. modulus of MPL Ouu²). ) Hence, directly guaranteeing QG from HSC improves convergence rates of the next sections by at least an order of ((23/2)
min t0.
||al|= = max (VU(,,)), -x) x²)
x' Ex.
||=~21|s1
$ max (V, x- x'EX
x')- --x-
3. New Insights in Structured Nonconvex Min-Max Optimization
Thus, we set Me= := (I-*) min, o(*) and by symmetry, the same holds for My.
As a preliminary step of independent interest, we present our results on optimization schemes for constrained min- max problems under nonconvex-pPL. and pPL-pPL condi- tions. To maintain completeness, we restate our solution concept under constrained min-max optimization perspec- tive:
2/2
Finally, in the Appendix we show that both HSC and pPL imply QG, which states that the optimality gap at any point x is lower-bounded by a quadratic term in its distance from the minimizer. This ensures that progress toward optimality can bound the proximity to the solution.
Definition 6 (e-SP). Assume a smooth function f X x y RR where X, Y are two compact and convex sets. Then, (x", E X' x y is an c-saddle-poin (c-SP) of f if,
Proposition 2.6 (QG from HSC and pPL). Let f: x X IR be E-smooth and satisfy either: (i) (Jes ('H) ) Jhidden strong convexity (HSC), or (ii) proximal Polyak- Lojasiewicz (pPL) with modulus μ. Then, satisfies the quadratic growth (QG) condition:
max (Vaf(=", ,),"= 2) Sc maxyey (VyJ(** , ).y yr) Se
(c-SP)
We adopt context-agnostic approach, assuming each player receives a "black-box" representation of their gradi- ent vector. These hypotheses remain intentionally abstract, as we impose no specific modeling assumptions on how players' payoff' signals are generated. In this sense, they serve as an "inexact gradient oracle" (Devolder et al., 2014) that captures wide range of settings. Reflecting MARL scenario, this framework allows each player to inde- pendently select and apply their preferred gradient estimator, as in (Zhang et al., 2020; 2021; Barakat et al., 2023).
f(z) - f(=0) PQQ || 2 Vo E
where 1p is the closest minimizer in x arg min f(x), and
HQQ -22HH (HSC), MQQ = μ (pPL).
Piecing the Framework Together. At high level, the standard tool in proving convergence to Nash equilibria for gradient-based methods is the construction of potential or Lyapunov- funtttioonnnniionnnnno (See (Bof et al., 2018)). A Lyapunov function needs to be lower-bounded and decreasing for con- secutive iterates of the algorithm. However, proving the latter beyond the convex-concave setting, requires a careful examination of HSC and pPL. As such, in order to shed light on the structured nonconvex landscape, we note:
Model (Stochastic Inexact First- Oracle). For any t, the gradient estimators 9z (Ze. ys) and 9,, (22, Vt) satisfy:
Bli= (It, v:)] gz (2z, vr.), 9e (2e. S o².
El wO] = yy (It,, ye); Bl ( ve || S og..
Additionally, scalars 8z, 8y > 0 bound the inexactness error:
Starting from the taxonomy of structured nonconvex func- tions, we show in the appendix that HSC and pPL are equivalent given a proper transformation of their moduli.
(1g. vi) - Vaf( sc)l Sx. ( vc) - V f vill < Ky.
Hence, the stationarity surrogate (x(xx, E) also serves as a surrogate for optimality fx) - ming'ex f(a). More importantly, by Claim 2.3, the min-max setting, for fixed opponent strategy, a sufficiently small Dx (zz L) indicates that the player has found an approximate best response.
Hence, dR and 9y provide unbiased estimates of IN and 9y- respectively, which in turn serve as inexact approximations of ( We) and V Vy Vt). As a result, we encounter two types of errors: (i) systematic bias (non-zero mean), bounded by 8z, 8y. and (ii) random noise (zero mean), with variance bounded by 0² oz
Furthermore, we highlight an additional crucial detail. Since, the pPL condition already guarantees quadratic growth (with an equal modulus), the contribution of HSC in this regard may appear redundant. Nonetheless, HSC is
3.1. Alternating Methods
A widely used stabilization technique in nonconvex min- max optimization, including adversarial training and GANs,
6

---

Solving Zero-Sum Convex Markov Games
is alternating updates between players (Lu et al,, 2019;
without resorting to multi-loop procedures? To this end,
Nouiehed et al., 2019; Gidel et al., 2019; Bailey al., 2020;
Alt-GDA leverages the sequential computation of 3++1 and
Wibisono al., 2022; Cevher et al., 2023; Lee et al., 2024).
1+++1 ensuring that each update benefits from fresher gradi- ent information.
Building on this approach, we analyze nested and alternating gradient iteration schemes.
Ft +- IIx (It-1 - T=02((1111 (1:1-1::1 11-1))
(Alt-GDA)
3.1.1. NESTED GRADIENT ITERATIONS
y/ -- Hly (Vt-1 TyDy( Br. 1t-1))
As a warm-up, we focus on solving the minimax problem (e-SP) under the assumption that we have access an oracle for approximate inner maximization, similar to (Jin et al., 2020, Section 4). Specifically, for any given æ, the oracle provides a yf such that: f(x, v/) 2 maxy far, 9)
Theorem 3.3 (NC-pPL: Informal version of Theorem D.7). Let f X x y be an L-Lipschitz and t-smooth function and y be compact convex sets with diameters Dx, Dy respectively. Also, assume that f(x.-) satisfies the pPL condition with modulus μ > O for all x E X. Then, the iteration scheme (Alt-GDA) run with tuning of
Me+1 - ARGMAX ( Cy):
(GDmax)
T++1 < xxx (x= V I Uc+1))
step-sizes:Ta =
and Tu =+
Theorem 3.1 (NC-pPL; Informal version of Theorem D.5). Let J x y be an I--lipschitz and f-smooth function and X, be compact convex sets with diameters Dx, Dy respectively. Also, assume that f(x,-) satisfies the pPL condition with modulus μ > 0. Then, the iteration scheme (GDmax) run with a tuning of
C CKka" c
batch-sizes M2 = +
and My = Q
outputs an (E + saddle-ppoin of f after a number of iterations, T, that at most
T=0 DEL(Dx +Dy)
step-sizes: Ts. = (1+) and Ty = θ (+))
2
batch-sizes Mg- θ and My θ RT
Theorem 3.4 (pPL-pPL- Informal version of Theorem D.8). Let f X x y be an L-Lipschitz and E-smooth function and x,Y be compact convex sets with diameters Dx Dy respectively, Also, assume that f satisfies the pPL condition in x and y with moduli pas By > respectively, Then, the iteration scheme (Alt-GDA)
where x E, outputs an (E+ 8z + &8y) saddle-pooin of f H.
after a total number of outer-loop and inner-loop iterations, T, that is most
T T= (Dx (=0(""LDxtD) log (t))
with tuning of
2
step-sizes:Ta = ( (Hy) and Ty =
- (2)
Theorem 3.2 (pPL-pPL; Informal version of Theorem D.6). Let f x y be an L-Lipschitz and E-smooth function and x,Y be compact convex sets with diameters Dx Dy respectively. Further, assume that f satisfies the two-sided pPL condition with moduli paz pa. Then, the iteration scheme (GDmax) run with tuning of
batch-sizes M,
and My Ma
5
u=z
oulputs an e-saddle-point of f after number of iterations, T. that is at most
L(Dx + +Dy)
step-sizes:T= = = (1%) and = (?)
T=
log
batch-sizes M, = θ K=oz and My = θ [EKyO'
4. Main Results Convex Markov Games
outputs an (e+ V H (6w + by) -saddle point of f after number of iterations, T, that is at most
In this section we present our main results regarding the convex Markov games (cMGs). We demonstrate that utility function that is hidden concave the occupancy measure satisfies the proximal-PL condition with respect to the player's policy. Then, we show that the maximiz- ers of Ui(x,)) .) are Lipschitz continuous in the minimizing player's policy x. Finally, we describe two policy gradi- ent algorithms that enjoy convergence to an approximate Nash equilibrium using a finite number of samples and iter- ations. Namely, (i) nested policy gradient (Nest-PG), and (ii) alternating policy gradient descent-ascent (AIt-PGDA).
T=0
1 L. (T.iiDy)
log
log
Hatty
e
where Kg = L and Kay = L. By
3.1.2. ALTERNATING GRADIENT DESCENT ASCENT
Given the simplicity and practical superiority of single- loop methods over two-loop alternatives, a natural ques- tion arises: can we achieve comparable convergence rates

---

Solving Zero-Sum Convex Markov Games
Throughout, 62 is implicitly tuned through the coefficient of the regularizer, J.. Also, 6y 0 since the maximizing player has access to unbiased stochastic estimates of the gradients. To see why j controls 5z, we note that by the -prg---ipsehitz continuity of the regularizer, the norm of its gradient is bounded. As such, o- = O(p and since we also pick μ - -e),, the bound on 8- follows suit.
that is at most:
O (log :) poly (1) (2,1, 1
7/8 F |S|. |A| + (88)
Px Hy min, Ø(e)
4.2. Alternating Policy Gradient Descent Ascent
Theorem 4.1 (Continuity of maximizers). Consider the mapping z + (x) := arg yax f(x, y). Then, for
Algorithm 2 Alt-PGDA: Alternating Policy GDA
input (wo.y0), step-sizes Tax Ty: T O, regul. coeff. μ
any two points 31, 42 it holds true that:
0
for t 11-11 to T do
(m1) (x1)
(x2)) S L, ||21 22l1,
s- Ixx It-1 Tx 7TU"((z (x1-1. V6-1)
where L, = Vppag
y/ s Ny U/-- + Ty V U Vt-11)
Corollary 4.2. Define the function Th :X R Th =
end for Pick t" E (I,...,T) of the best iterate.
max, {U(x,)) y) & (1) ")1²) Then, for any x, x' E
output (2r,
X, the following inequality holds:
VV V. (x')l s 1 || 2l1.
Theorem 4.5 (Informal Version of Theorem E.1 Con- sider a two-player zero-sum cMG, I, and let be desired accuracy > 0. Then, Algorithm run with appropriately step-sizes Tzs Ty 0, exploration parameters Ez O batch-sizes Mg. My > 0, and a regularization coefficient I = O(e), outputs an e-approximate Nash equilibrium after a number of iterations that is at most:
with f = {(1 + T.
4.1. Nested Policy Gradient
Algorithm Nest-PG: Nested Policy Gradient
input (zo. jo). step-sizes Tz, Ty. regul. coeff. μ 2 0
0 (2²) poly min, e(s) Y,
1 1- S),1A|| + IB])
for t = to Tout do Fr.0 + yt-1
Theorem 4.6 (Informal Version of Theorem E.13). Con-
for to Tin do
sider a two-player zero-sum cMG, I, with utility functions that are hidden strongly concave with moduli pas My > 0 respectively. Additionally, let e be a desired accuracy é > O. Then, Algorithm 2 run with step-sizes Tz: Ty > 0, and batch- sizes Ma, My > O outputs an e-approximate Nash equilib- rium after number of iterations that is at most:
It.s - Fly U--1 + UUH (5e-1, (11-1,
Y/1 + Yr,Ten
end for
2t + +Ix (21-1-12 Tu AzU (IC-1.
end for Pick t" E T) of the best iterate. output (1++))
O (log 2) poly
[ M4 mim, 2(3) 7, 1 [8], [-|| + 1B1)
Theorem 4.3. Consider two-player zero-sum cMG, I, and let be desired accuracy >> 0. Then, Algorithm I run with appropriately tuned step-sizes Tæ, Ty > O, Ez, Ey >> O batch-sizes MG My > O outputs an 6-approximate Nash equilibrium after a number of iterations that is at most:
We deem noteworthy the fact that Theorem 4.6 guarantees (expected) last-iterate convergence for a class of nonconvex games that take place over constrained domain.
5. Numerical Results
o (+) poly (
mine e(s) 7, 11.118881111 1B1).
We demonstrate Algorithms and 2 on an iterated version of rock paper- bers the actions selected in the previous round. Hence, the previous joint action constitutes the state in the Markov game. The dummy action is dominated by all other actions such that the Nash equilibrium of the stage game is uniform across rock, paper, and scissors with zero mass on dunmy. We set the step-sizes Tn = Ty = 0.1 and vary the regu- larization coefficient μ to demonstrate its effect in biasing convergence.
where each player remem-
Theorem 4.4. Consider a two-player zero-sum cMG, I, with with utility functions that are hidden strongly concave with moduli PayPy > O respectively. Additionally, let be a desired accuracy E > O. Then, Algorithm 1 run with approprite step-sizes Ta, Ty > O, exploration parameters Ex, Ex,Ey Ey > O, and batch-sizes M2, My > 0 outputs an e- approximate Nash equilibrium after a number of iterations
8

---

Solving Zero-Sum Convex Markov Games
Alt-PGDA on Iterated RPSD
Nest-PG (10) on Iterated RPSD
Nest-PG (100) on Iterated RPSD
Length-1 Joint Action Memory
Length-1 Joint Action Memory
Length-1 Joint Action Memory
Exploitabiiity (e)
Exploitability (E)
Exploitabllity (E)
P= 10.0
10
10
10
7-7.
==
10-2
10
10-2
pm 1.0
10-3
10-3
10-3
02
p-0.1
10
30
40
50
20
30
40
20
30
Iterations (Thousands)
Iterations (Thousands)
Iterations (Thousands)
Figure I. Exploitability decays towards small, hut positive value corresponding to the bias introduced by the regularization coefficient Results averaged over 100 trials, each running the algorithm with different randomly initialized policy profile. The leftmost plot reports results for Algorithm 2; the right two report results for Algorithm with Ti 10 and 100 respectively.
Our experiments suggest clearly that (i) there is pro- nounced trade-off between speed of convergence and the ex- ploitability of the solution of the perturbed problem (ii) more inner-loop iterations account for more stable exploitability decrease across consecutive iterates.
From theoretical standpoint, we anticipate fascinating explorations of multi-player cMG interactions and deep investigation of an array of game-theoretic solution con- cepts. We hope to see the experience the rich multi-agent cMG applications inform theory and give rise to meaningful and challenging problems like equilibrium learning, equi- librium selection, and notions of equilibrium performance.
6. Conclusion and Future Work
We reiterate the fact that cMGs render the value-iteration subroutine useless. The latter lies at the heart of the corre- sponding algorithmic solutions for equilibrium learning or computation in conventional MGs; its inefficacy in cMGs, more than just posing an additional challenge, can stimulate the search for new algorithmic tools.
Convex Markov games (cMGs) unify the domains of convex MDPs and Markov games. Even the rudimentary form of a cMG, a two-player pure competition, fosters a rich mosaic of applications spanning language model alignment, self-driving cars, and creative chess playing, to name a few.
In this work, present the first algorithmic solution for computing Nash equilibria. To achieve this, we develop the first guarantees of convergence of alternating descent- ascent to a saddle-point for nonconvex functions that satisfy a one-sided or two-sided proximal Solyyk-LLoassewiie con- dition over constrained domains, We utilized these results to design number of independent policy gradient algo- rithms for convex Markov games that provably converge an approximate Nash equilibrium. In nutshell, develop simple-to- -t-sue learning dynamics that converge to the op- timal game solutions even under realistic and challenging conditions where batch learning only allows noisy gradient estimation.
A Acknowledgements
FK gratefully acknowledges Panayotis Mertikopoulos for his mentoring and insightful discussions during the former's 2024 summer research fellowship at Archimedes, Athena Research Center.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here.
In terms of message to practitioners, our work highlights that the regularized (Alt-GDA) algorithm is exceptionally effective and easy to deploy to tackle min-max problems. Its efficacy is achieved by mere (i) regularization, (ii) al- ternating updates, and (iii) step-size magnitude separation Moreover, the generality of Theorems 3.3 and 3.4, cou- pled with the prevalence of the PL condition modern machine learning objectives, makes a strong case in favor of (Alt-GDA) as the default algorithm for min-max opti- mization. Furthermore, believe that can seamlessly accommodate more elaborate update schemes top of (i- iii), like adaptive learning rates, preconditioning, and, if necessary, higher-order information.
References
Abel, D., Dabney, W., Harutyunyan, A., Ho, M. K., Littman, M., Precup, D., and Singh. S. On the expressivity of markov reward. In Advances in Neural Information Pro- cessing Systems (NeurIPS), 2021.
Afriat, S. Theory of maxima and the method of lagrange. SIAM Journal on Applied Mathematics, 20(3):343-35) 1971.
Azizian, W., Iutzeler, F., Malick, J., and Mertikopoulos, P. The rate of convergence of bregman proximal methods:

---

Solving Zero-Sum Convex Markov Games
Local geometry versus regularity versus sharpness. SIAM Journal on Optimization, 34(3):24002471,, 2024. doi:
Bolte, J., Daniilidis, A., Ley, O., and Mazet, L. Charac- terizations of lojasiewicz inequalities: subgradient flows, talweg, convexity. Transactions of the American Mathe- matical Society, 362(6):3319-338)) 2010.
10.11377/23M58802188 URL https: pitttss:/doli 2L37/23M1580211
Bai, Y. and Jin, C. Provable self-play algorithms for compet- itive reinforcement learning. International conference on machine learning, pp. 551-560. PMLR, 2020.
Burgard, W., Moors, M., Fox, D., Simmons, R., and Thrun, S. Collaborative multi-robot exploration. In Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Pro- ceedings (Cat. No. 00CH37065), volume I, pp. 476-481. IEEE, 2000.
Bailey, J. P. and Piliouras, G. Multiplicatiie weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 321- 338, 2018.
Cai, Y., Luo, H., Wei, C.-Y., and Zheng, W. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. Advances in Neural Infor- mation Processing Systems, 36:36364 36446,, 2023.
Bailey, J. P., Gidel, G., and Piliouras, G. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Conference on Learning Theory, pp- 391-407. PMLR, 2020.
Cai, Y., Luo, H., Wei, C.-Y., and Zheng, W. Near-optimal policy optimization for correlated equilibrium in general- sum markov games. In International Conference Arti- ficial Intelligence and Statistics, pp. 3889-3897, PMLR, 2024.
Bakhtin, A.. Wu, D. J., Lerer, A., Gray, J., Jacob, A. P., Farina, G., Miller, A. H., and Brown, N. Mastering the game of no-press diplomacy via human-regularized reinforcement learning and planning. arXiv preprint arXiv:2210.05449. 2022.
Cen, S., Chi, Y., Du, S. S., and Xiao, L. Faster last-iterate convergence of policy optimization in zero-sum markov games. arXiv preprint arXiv:2210.010500 2022.
Barakat, A., Fatkhullin, I., and He, N. Reinforcement learn- ing with general utilities: Simpler variance reduction and large state-action space. In International Conference on Machine Learning, pp. 1753-1880 1800. PMLR, 2023.
Cevher, V., Cutkosky, A., Kavis, A., Piliouras, G., Skoulakis, S., and Viano, L. Alternation makes the adversary weaker in two-player games. Advances in Neural Information Processing Systems, 36: 36:18263-11 18263-18290, 2023.
Bauschke, H. H. and Combettes, P. L. Convex analysis and monotone operator theory Hilbert spaces. Springer Science & Business Media, 2011.
Chambolle, A. and Pock, A first-order primal-dual algorithm for convex problems with applications imaging. Journal of Mathematical Imaging and Vision, 40:120-145, 2011. URL https:
Bellman, R. Dynamic programming and stochas- tic control processes. Information and Control, 1(3):228-233) 1958.
ISSN 0019-9958. doi:
261281173.
URL sai https::/www.sccennedieccee com/
Chatterji, N., Pacchiano, A., Bartlett, P., and Jordan, M. On the theory of reinforcement learning with once-per- episode feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Ben-Tal, A. and Tehoulle, M. Hidden convexity in some nonconvex quadratically constrained quadratic program- ming. Mathematical Programming, 72(1):51-63. 1996.
Chavdarova, T., Gidel, G., Fleuret, F., and Lacoste-Julien, S. Reducing noise in gan training with variance reduced extragradient. H., Beygelzimer, A., d'Alché-Bue, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.,
Bernasconi, M., Castiglioni, M., Celli, A., and Farina, G. On the role constraints in the complexity of min-max optimization. arXiv preprint arXiv:2411.03245 2024.
Wallach, H., Larochelle,
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., Hesse, C., et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint arXiv: 1912.06680 2019.
2019. URL https::/proceed neurip cc / paper cc//aappe__iilee//pee////////// Saa21cGeasff033f555122222288888. pdf.
Bof, N., Carli, R., and Schenato, L.. Lyapunov theory for discrete time systems. arXiv preprint arXiv:1809.05280 2018.
Chavdarova, T., Pagliardini, M., Stich, S. U., Fleuret, F., and Jaggi, M. Taming gans with lookahead 2021. URL hww.tttts////ett /eetps://arxv..... http://s//.rriv.oor/////////... 14567.
10

---

Solving Zero-Sum Convex Markov Games
Chen, X., He, N., Hu, Y., and Ye, Z. Efficient algorithms for class of stochastic hidden convex optimization and its applications in network revenue management. Operations Research, 2024.
Drusvyatskiy, D. and Lewis, A. S. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 43(3);919-948, 2018.
Cheung, W. C. Exploration-exploiatiie trade-off in re- inforcement learning on online markov decision pro- cesses with global concave rewards. arXiv preprint arXiv:1905.064466. 2019a.
Drusvyatskiy, D. and Paquette, C. Efficiency of minimiz- ing compositions of convex functions and smooth maps. Mathmattcal Progrumming, 178(1):03-5558 2019.
Efroni, Y., Merlis, N., and Mannor, Reinforcement learn ing with trajectory feedback. In AAAI Conference on Artificial Intelligence, 2021.
Cheung, W. C. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. In Advances in Neural Information Processing Systems (NeurIPS), 2019b.
Erez, L.,, Lancewicki, T., Sherman, U., Koren, T., and Man- sour, Y. Regret minimization and convergence to equilib- ria in general-sum markov games. In International Con- ference on Machine Learning, pp. 9343-93733 PMLR, 2023.
Cui, Q. and Du, S. When are offline two-player zero-sum markov games solvable? Advances in Neural Information Processing Systems, 15:25779-257999 2022.
Cui, Q. Zhang, K., and Du, S. Breaking the curse of multiagents in a large state space: RI in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2651-2652. PMLR, 2023.
Facchinei, F. and Pang, J.-S. Finite-dimensionl variational inequalities and complementarity problems. Springer, 2003.
Facchinei, F. and Pang, J.-S. Finite-dimensional variational inequalities and complementurity problems. Springer Science & Business Media, 2007.
Daskalakis, C., Foster, D. J., and Golowich, N. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540, 2020.
Fatkhullin, I., He, N., and Hu, Y. Stochastic optimization un- der hidden convexity. arXiv preprint arXiv:2401.00108, 2023.
Daskalakis, C., Skoulakis, S., and Zampetakis, M. The complexity of constrained min-max optimization. In Pro- ceedings of the 53rd Annual ACM SIGACT Symposium on Theorr of Computing, pp. 1466-1478, 2021.
Feng, Q. and Shanthikumar, G. Supply and demand functions in inventory models. Operations Research, 66 (1):77-91, 2018.
Fink, A. M. Equilibrium in stochastic n-person game. Journal of science of the hiroshima university, series ai (mathematics). 28(1):89-93, 1964.
Daskalakis, C., Golowich, N., and Zhang, K. The complex- ity of markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4180-4234. PMLR, 2023.
Geist, M., Pérolat, J., Laurière, M., Elic, R., Perrin, S., Bachem, O., Munos, R., and Pietquin, O. Concave utility reinforcement learning: The mean-field game viewpoint. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022.
Deng, X., Li, N., Mguni, D., Wang, J., and Yang. Y. On the complexity of computing markov perfect equilibrium in general-sum stochastic games. National Science Review, 10(1):nwac256, 2023.
Gemp, I., Haupt, A., Marris, L., Liu, S., and Piliouras, G. Convex markov games: A framework for fairness, imitation, and creativity in multi-agent learning. arXiv preprint arXiv:2410.16600 2024.
Devolder, O., Glineur, F., and Nesterov, Y. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2014.
Diakonikolas, J., Daskalakis, C., and Jordan, M. I. Efficient min-max
Ghadimi, S., Lan, G., and Zhang, H. Mini-batch stochastic approximation methods for nonconvex stochastic com- posite optimization. Mathematical Programming, 155(1): 267-305, 2016.
methods for structured optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2746-2754 PMLR, 2021.
Ding, D., Wei, C.-Y., Zhang, K., and Jovanovic, M. Inde- pendent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game- agnostic convergence. In International Conference on Machine Learning, pp. 5166-5265500 5220. PMLR, 2022.
Gidel, G., Hemmat, R. A., Pezeshki, M., Le Priol, R., Huang, G., Lacoste-Julien. S., and Mitliagkas, I. Negative mo- mentum for improved game dynamics. In The 22nd Inter- national Conference on Artificial Intelligence and Statis- tics, pp. 1802-1811. PMLR, 2019.

---

Solving Zero-Sum Convex Markov Games
Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial nets. Advances in neural informa- tion processing systems, 27, 2014.
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence of gradient and proximal-gradient methods under the polyak-tojasiewicz condition. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECMI. PKDI) 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part 16, pp. 795- 811. Springer, 2016.
Gronauer, S. and Diepold, K. Multi-agent deep reinforce- ment learning: a survey. Artificial Intelligence Review, 55(2):895-943, 2022.
Kinderlchrer, D. and Stampacchia, G. An introduction to variational inequalities and their applications. SIAM, 2000.
Hazan, E., Kakade, S., Singh, K., and Soest, A. V. Provably efficient maximum entropy exploration. In International Conference on Machine Learning (ICML), 2019.
Kobyzev, I., Prince, S. J., and Brubaker, M. A. Normalizing flows: An introduction and review of current methods. IEEE Transactions on Pattern Analysis and Machine In- telligence, 43(1 (3(11):33644397) 2020.
Hughes, E., Leibo, J. Z., Phillips, M., Tuyls, K., Dueñez- Guzman, E., Garefa Castañeda, A., Dunning, I., Zhu, T., McKee, K., Koster, R., Roff, H., and Graepel. T. Inequity aversion improves cooperation in intertemporal social dilemmas. Advances in neural information processing systems, 31, 2018.
Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Ekonomika Matem- aticheskie Metody, 12:747-756, 1976.
J Reddi, S., Sra, S., Poczos, B., and Smola, A. J. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29, 2016.
Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F. Tuyls, K., Omidshafici, S., et al. Openspiel: A frame- work for reinforcement learning in games. arXiv preprint arXiv: 100,00990,, 2019.
Jin, C., Netrapalli, P., and Jordan, M. What is local optimal- minimax optimization? In
Lee, J., Cho, H., and Yun, C. Fundamental benefit of alter- nating updates in minimax optimization. arXiv preprint arXiv:2402. 10475, 2024.
ity in International conference on machine learning. pp. 4880- 4889. PMLR, 2020.
Leonardos, S., Overman, W., Panageas, I. and Pil- iouras, G. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2 100.019999 2021.
Jin, C., Liu, Q.. Wang, Y., and Yu, T. V-learning simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint wwXiv:2110.145550 2021.
Ji,, Y. Muthukumar, V., and Sidford, A. The complexity of infinite-horizon general-sum stochastic games. arXiv preprint arXiv:2204.04 2022.
Li, D., Wu, Z.-Y., Joseph Lee, H.-W., Yang, X.-M., and Zhang, L.-S. Hidden convex minimization. Journal of Global Optimization, 31:211-233, 2005.
Kalogiannis, F. and Panageas, I. Zero-sum polymatrix markov games: Equilibrium collapse and efficient com- putation of nash equilibria. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Sys- tems, volume 36, pp. 59996-60020. Curran Associates, Inc., 2023.
Li, G. and Pong, T. K. Calculus of the exponent of kurdyka- lojasiewicz inequality and its applications to linear con- vergence of first-order methods. Foundations of computa- tional mathematics, 18(5):1199) 1232, 2018
Li, X.-B. and Li, S. Hölder continuity of perturbed solution set for convex optimization problems. Applied Mathemat- ics and Computation, 232:908 918, 2014.
Kalogiannis, F., Anagnostides, I., Panageas, I., Vlatakis- Gkaragkounis, E.-V., Chatziafratis, V., and Stavroulakis, S. Efficiently computing nash equilibria in adversarial team markov games. arXiv preprint arXiv:2208.022 022044 2022.
Liao, F.-Y., Ding, L., and Zheng, Y. Error bounds, pl condi- tion, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. In 6th Annual Learning for Dynamics & Control Conference, pp. 993-1005. PMLR, 2024.
Kalogiannis, F., Yan, J., and Panageas, I. Learning equilibria in adversarial team markov games: A -iidden---- concave min-mat max optimization problem. arXiv preprint 1rXiv:2410.05077 2024.
Lin, T., Jin, C., and Jordan, M. On gradient descent ascent for nonconvex concavee minimax problems. In Interna- tional conference on machine learning, pp. PMLR, 2020.
12

---

Solving Zero-Sum Convex Markov Games
Littman, M. L. Markov games as a framework for multi- agent reinforcement learning. In Machine learning pro- ceedings 1994, pp. 157-163. Elsevier, 1994.
Nouiched, M., Sanjabi, M., Huang, T., Lee, J. D., and Raza- viyayn, M. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Liu, M., Rafique, H., Lin, Q., and Yang, T. First-order convergence theory for weeely--oovex-wwkky--oooo min-max problems. Journal of Machine Learning Re- search, 22(169):1 2021.
Oikonomidis, K., Laude, E., and Patrinos, P. Forward- backward splitting under the light of generalized convex- ity. arXiv preprint 2r0i: 18098, 2025.
Lu, S., Singh, R., Chen, X., Chen, Y., and Hong, M. Alter- nating gradient descent ascent for nonconvex min-max problems in robust learning and gans. In 2019 53rd Asilo- mar Conference on Signals, Systems, and Computers, pp- 680-684. IEEE, 2019.
Papadimitriou, C., Vlatakis- Saaaiiiss-aaaaauuuii.... E.-V., and Zam- petakis, M. The computational complexity of multi- player concave games and kakutani fixed points. In Pro- ceedings of the 24th ACM Conference on Economics and Computation, 2023.
Luo, Z.-Q. and Tseng, Error bounds and convergence analysis of feasible descent methods: general approach. Annals of Operations Research, 46(1):157-178, 1993.
Park, C.,, Zhang, K., and Ozdaglar, A. Multi-player zero- sum markov games with networked separable interactions. Advances in Neural Information Processing Systems, 36: 37354-37365 2023.
Madry, A., Makelov, A., Schmidt, L.,, Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. arXiv preprint vrxiv:/706.0688. 2017.
Polyak, B. T. and Juditsky, A. B. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4)883-885, 1992.
Martinet, B. Régularisation d' d'inéquations variationnelles par approximations successives. ESAIM: Mathemati- cal Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, 1970.
Puterman, M. L. Markov decision processes: discrete
stochastic dynamic programming. John Wiley &Sons, 2014.
Rebjock, Q. and Boumal, N. Fast convergence non- isolated minima: four equivalent conditions for func- tions. Mathematical Programming, pp. 1-49, 2024.
Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chan- drasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv: wwx.v::807002629 2018
Rockafellar, R. T. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimiza- tion, 14(5):877-898, 1976.
Mladenovic, A., Sakos, I., Gidel, G., and Piliouras, G. Gen- eralized natural gradient flows in hidden convex-coneave games and gans. In International Conference on Learning Representations, 2021.
Rockafellar, R. T. and Wets, R. J.-B. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonogiou, I., Wierstra, D., and Riedmiller, M. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 13/.55602 2013.
Rogers, G., Nieto-Granda, C., and Christensen, H. I. Coordination strategies for multi-robot exploration and mapping. In Experimental Robotics: The 13th Interna- tional Symposium Experimental Robotics, pp. 231- 243. Springer, 2013.
Mulvaney-Kemn J., Park, S., Jin, M., and Lavaei, J. Dy- namic regret bounds for constrained online nonconvex optimization based on bolaak-lojsseewizz regions. IEEE Transactions Control of Network Systems, 10(2):599- 611.
Ruppert, D. Efficient estimations from slowly conver- gent robbins-monro process. Technical Report, Corell University, 1988.
Sakos, I., Vlatakis- Vlatakis-Gkaragkee Gkaragkounis, E.-V., Mertikopoulos, P., and Piliouras, G. Exploiting hidden structures in non- convex games for convergence to nash equilibrium. Ad- vances in Neural Information Processing Systems, 36, 2024.
Nemirovski, A. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continu- ous monotone operators. SIAM Journal on Optimization, 15(1):229-251, 2004.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Ro- bust stochastic approximation approach to stochastic pro- gramming. SIAM Journal on Optimization, 1974) 1609, 2009.
Sayin, M., Zhang, K., Leslie, D., Basar, T., and Ozdaglar, A. Decentralized q-learning in zero-sum markov games. Advances in Neural Information Processing Systems, 34: 18334, 2021.
13

---

Solving Zero-Sum Convex Markov Games
Schneider, S. and Wagner, D. H. Error detection in re- dundant systems. In Papers Presented at the Febru- ary 26-28, 1957, Western Joint Computer Conference: Techniques for Reliability, IRE-AIEE-ACM, '57 (West- ern), pp. 115-121, New York, NY, USA, 1957. Associa- tion for Computing Machinery. ISBN 978 9781450378611. doi: 10. I 044114/4445666.445555555 org/10 1ee.11111//155//1 14555877.
Wang, Y., Lacotte, J., and Pilanci, M. The hidden convex optimization landscape of regularized two-layer relu net- works: an exact characterization of optimal solutions. In International Conference on Learning Representations, 2021.
Wang, Y., Liu, Q., Bai, Y., and Jin, C. Breaking the curse of multiagency: Provably efficient decentralized multi- agent rl with function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2793-2848. PMLR, 2023.
URL https: //dotp.. /doi.
Shalev-Shwartz, S., Shammah, S., and Shashua, Safe, multi-agent, reinforcement learning for autonomous driv- ing. arXiv preprint (6K..:326000 2016.
Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Last- iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Conference on learning theory, pp. 4259-4299. PMLR, 2021.
Shapley, S. Stochastic games. Proceedings of the national academy of sciences, 39(1001095-11100 1953.
Silver, D., Schritwwessr, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, I.,, Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. nature, 550(7676)3354-399 2017.
Wibisono, A., Tao, M., and Piliouras, G. Alternating mir- ror descent for constrained min-max games. Advances in Neurul Information Processing Systems, 35:35201- 35212, 2022.
Singh, B., Kumar, R., and Singh, V. P. Reinforcement learning in robotic applications: a comprehensive survey. Artificial Intelligence Review, 55(2):945-990 2022.
Williams, R. J. Simple statistical gradient-following algo- rithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Song, Z., Mei, S., and Bai, Y. When can we learn general- sum markov games with large number of players sample-efficiently? arXiv preprint 18.04441 2021.
Wu, Y., Viano, L., Chen, Y., Zhu, Z., Antonakopoulos, K., Gu, Q., and Cevher, V. Multi-step alignment as markov games: An optimistic online gradient descent approach with convergence guarantees. arXiv preprint arXiv:2502. 2025.
Stella, I.., Themelis, A., and Patrinos, P. Forward-backward quasi-newton methods for nonsmooth optimization prob- lems. Computational Oplimizution and Applications, 67 (3):443-487, 2017.
Wu, Z.- Li, D., Zhang. L.-S., and Yang, X. Peeling off nonconvex cover of an actual convex problem: hidden convexity. SIAM Journal on Optimization, 18(2):507- 536, 2007.
Tammelin, O., Burch, N., Johanson, M., and Bowling, M. Solving heads-up up limit texas hold'en em. em. In Proceedings of the 24th International Conference on Artificial Intelli- gence, IJCAI 15, pp. 645-652. AAAI Press, 2015. ISBN 9781577357384.
Xia, Y. A survey of hidden convex optimization. Journal of the Operations Research Society of China, 8(1):1-28, 2020.
Yang. J., Kiyavash, N., and He. N. Global convergence and variance reduction for a class of minimax problems. Advances in Neural Information Processing Systems, 33:1153-1165, 2020.
Tan, A. H., Bejarano, F. P., Zhu, Y., Ren, R., and Nejat, G. Deep reinforcement learning for decentralized multi- robot exploration with macro actions. IEEE Robotics and Automation Letters, 8(1):272-279, 2022.
Yang. J., Orvieto, A., Lucchi, A., and He, N. Faster single- loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intel- ligence and Statistics, pp. 5485-5511 PMLR, 2022.
v. Neumann, J. Zur theorie der gesellschaftsspiele. Mathe- matische annalen, 100(1): 112259332,, 1928.
Vlarakiss E.-V., Flokas, L., and Piliouras, G. Solving min-max optimization with hidden structure via gradient descent ascent. Advances in Neural Information Processing Systems, 34:2373-2333 2386, 2021.
Yang, Y. and Ma, C. O(t-1) convergence of optimistic- bollow-therrggulaiieee--ee in two-player zero-sum markov games. arXiv preprint arXiv: 2022.
Von Stengel, B. and Koller, D. moam-maxmin equilibria. Games and Economic Behavior, 21(1-2):3093211 1997.
Ying, D.,, Guo, M. A., Ding, Y., Lavaei, J., and Shen, Z.-J. Policy-basse primal-dual methods for convex constrained
14

---

Solving Zero-Sum Convex Markov Games
markov decision processes. Proceedings the AAAI Conference on Artificial Intelligence, 37:10963-10971, 2023.
Zahavy, T., O'Donoghue, B., Desjardins, G., and Singh, S. Reward is enough for convex mdps. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Zahavy, T., Schroecker, Y., Behbahani, F., Baumli, K., Flen- nerhag, S., Hou, S., and Singh, Discovering policies with domino: Diversity optimization maintaining near optimality, arXiv preprini arXiv:2205.1355), 2022.
Zahavy, T., Veeriah, V., Hou, S., Waugh, K., Lai, M., Leurent, E., Tomasev, N., Schut, L.., Hassabis, D., and Singh, S. Diversifying ai: Towards creative chess with alphazero. arXiv preprint arXiv:2308.00 09175, 2023.
Zeng. S., Doan, T., and Romberg, J. Regularized gradient descent ascent for two-player zero-sum markov games. Advances in Neural Information Processing Systems, 35: 34546-34558, 2022.
Zhang. G. and Yu, methods on bilinear zero-sum games. Inter- national Conference on Learning Representations, 2019. URL http::::/ap..smmttitssstttt semantccscholar. Tttp/CorpusDD:211055
Convergence of gradient
Zhang, J., Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M. Variational policy gradient method for rein- forcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572-4588, 2020.
Zhang, J., Ni, C., Yu, Z., Szepesvari, C., and Wang, M. On the convergence and sample efficiency of variance- reduced policy gradient method. Advances in Neural Information Processing Systems, 14:2228-22444 2021.
Zhang, R., Liu, Q., Wang, H., Xiong, C., Li, N., and Bai, Y. Policy optimization for markov games: Unified frame- work and faster convergence. Advances in Neural Infor- mation Processing Systems,
2022a.
Zhang, R., Mei, J., Dai, B., Schuurmans, D., and Li, N. On the global convergence rates of decentralized softmax gradient play in markov potential games. Advances in Neural Information Processing Systems, 35:1923-1935, 2022b.
Zheng, T., Zhu, L.. So, A. M.-C., Blanchet, J., and Li, Universal gradient descent ascent method for nonconvex- nonconcave minimax optimization. Advances in Neural Information Processing Systems, 36:54075-54110, 2023.
15

---

Solving Zero-Sum Convex Markov Games
Appendix
Table of Contents
Further Related Work
A.1 Hidden Convex Optimization
17
A.2 Min-Max Optimization
17
A.3 Convex Markov Decision Processes
A.4 Markov Games and Multi-Agent Reinforcement Learning
18
B Optimization Preliminaries
B.I Optimization Definitions & Lemmata
19
B.2 Min-Max Optimization Lemmata
23
Hidden Convexity, PL, KL, and EB
C.I Equivalence between the three conditions
................................
27
C.2 PPL from HSC
30
QG directly from HSC, KL. pPL
C.4 Warm-up: Stochastic Projected Gradient Descent a proximal-PL. Function
31
D Constrained Min-Max Optimization Under the pPL Condition
33
D.I Key Lemmata
33
D.2 Stationarity Proxies and the Gradient Oracle
35
D.3 Convergence of Nested Gradient Iterations
36
D.4 Convergence of Stochastic Alternating Gradient Descent-Ascent
37
E Convex Markov Games
47
E.1 Properties of eMG Utility Fucntions
................................
48
E.2 Stochastic Estimators
................................
49
E,3 Additional Supporting Claims
52
Nested Policy Gradient
E.5 Alternating Policy Gradient Descent-Ascen
58
Roadmap of the Appendix
Helping the reader navigate, we list a short summary of the topics that are covered in each section.
Appendix A, we attempt to present an overview of key research directions, theoretical landmarks, and applications. Interested readers can find further details in the cited literature therein although an exhaustive survey is infeasible.
In Appendix B, establish series of lemmata concerning gradient descent for smooth functions: (i) Lem- mata B.2 to B.4 are standard results regarding the iterates of projected gradient descent (with an exact inexact and stochastic first-order oracle). (ii) We introduce Dx as the primary proxy of stationarity and derive descent inequality for inexact gradient estimates based on this proxy (Lemmata B.7 to B.9). (iii) The section concludes with an analysis of the Lipschitz continuity of this proxy in min max optimization. We also examine how one player's s deviation affects the proxy of the other player.
16

---

Solving Zero-Sum Convex Markov Games
Appendix C, we study relationship of Hidden Strong Convexity (HSC) and the equivalent conditions of the proximal Polyak=-.ojssiewiiz (pPI.) and the Kurdyka-t.ojasiewiizz (KI.).
In Appendix D, we present key results, including: (i) The Lipschitz.cnntinuity of maximizers, (ii) Convergence
rates for nested and alternating schemes under the general framework of hidden-convex hidden-concave min-max optimization.
Finally, in Appendix E, extend our analysis to convex multi- aggett reinforcement learning, combining the results from Appendix D with policy gradient estimators to compute parameter updates.
A. Further Related Work
A.1. Hidden Convex Optimization
Hidden convexity has emerged as an important structural property in nonconvex optimization, enabling global convergence results in settings where traditional convex analysis fails-a survey can be found here (Xia, 2020). Fatkhullin et al. (2023) have decisively proven the convergence of first-order methods even for the nonsmooth and stochastic settings. Moreover, hidden convexity has been extensively studied across diverse applications, including policy optimization in reinforcement learning (RL) and optimal control (Hazan et al., 2019; Zhang et al., 2020; Ying et al., 2023), generative models (Kobyzev et al., 2020), supply chain and revenue management (Feng & Shanthikumar, 2018; Chen et al., 2024), and neural network training (Wang et al., 2021). Even earlier, instances of an implicit convex structure have appeared in a number of works in the past (Ben-Tal & Teboulle, 1996; Li et al., 2005; Wu et al., 2007). In a certain sense, hidden convexity falls into the general category of metric regularity conditions (Karimi al., 2016; Li & Pong, 2018; Drusvyatskiy & Paquette, 2019; Drusvyatskiy& & Lewis, 2018; Liao al., 2024; Rebjock & Boumal, 2024; Luo & Tseng, 1993; Oikonomidis al., 2025) that have been used to prove convergence of iterative gradient- based methods.
Particularly, hidden convexity ensures convergence in nonconvex-nonee nonconcave games. Namely, Vlatakis- Saaukks-Garragkoumiii et al. (2021) introduced the notion of hidden-convex hidden-concave games and proved global convergence to a NE. Further extending these ideas, (Sakos et al., 2024) investigates the impact of hidden structure and show that such properties can be leveraged to enhance the stability of first-order methods. The generalized notion of hidden monotonicity (Mladenovic et al., 2021) guarantees global convergence for multi- multi-player nonconvex games.
A.2. Min-Max Optimization
The literature of min-max optimization is long-standing and intimately connected to game theory (v. Neumann, 1928). In recent years, the exploration of nonconvex-nonconeeae min-max problems gained prominence in machine learning, particularly due to developments like generative adversarial networks (GANs) (Goodfellow al., 2014) and adversarial learning (Madry et al., 2017). Research has focused on defining appropriate solution concepts and developing methods to mitigate oscillatory behaviors in optimization algorithms. A min-max optimization problem is often formulated as a variational inequality problem (VIP) (Facchinei & Pang. 2003) and the literature has managed to guarantee provable convergence to solutions of the corresponding VIP only under certain assumptions. Namely, convergence to an approximate solution of the VIP point is guaranteed under (i) monotonicity, (or, a convex-concave objective) (ii) a gradient domination, and (iii) other regularity conditions.
In particular, under monotonicity, the proximal point methods (Martinet, 1970; Rockafellar, 1976) for VIP guarantee convergence. When the objective function is Lipschitz and strictly convex-concave, simple hewaadd-bacwwan schemes are known to converge. Moreover, when coupled with Nemirovski et al., 2009), these methods achieve an O ( complexity without requiring strict convex-concavin (Bauschke & Combettes, 2011] I). If additionally the objective function has Lipschitz continuous gradients, the extragradient algorithm (Korpelevich, 1976) ensures trajectory convergence without strict monotonicity assumptions, while the time-averaged iterates converge at a rate of O(1/e) (Nemirovski, 2004). Furthermore, in strongly convex-concave settings, forward- forward-backward backward methods compute an c-saddle point in O(1/c) steps. If the operator is also Lipschitz continuous, classical results in operator theory establish that simple forward- -bakkdd methods are sufficient to achieve linear convergence (Facchinei & Pang. 2007; Bauschke & Combettes, 201 1).
averaging (Ruppert, 1988; Polyak & Juditsky, 1992;
Under a single-sided gradient domination condition, convergence to a stationary point of the min-max objective has been proven in (Lin et al., 2020; Nouiched et al., 2019; Yang et al., 2022). Under a tio-sided gradient domination condition, (Daskalakis et al., 2020; Yang et al., 2020; Zheng et al., 2023) have proven the convergence to a solution of the corresponding
17

---

Solving Zero-Sum Convex Markov Games
VIP (and equivalently to a min-max point). Further, under the Minty condition, (Mertikopoulos et al., 2018; Liu et al., 2021; Diakonikolas et al., 2021) show convergence solution of the VIP even under nonconvexity. Evenmore, (Azizian et al., 2024) shows convergence of gradient descent under various conditions of regularity and local optimization geometry.
A.3. Convex Markov Decision Processes
The study of convex reinforcement learning emerged as a natural extension of standard RL to handle more expressive, non-linear utility functions. Hazan et al. (2019) introduced the problem of reward-free ffree exploration of an MDP through state-occupancy entropy maximization. To tackle policy optimization, they proposed a provably efficient algorithm based on the Trolk method. Further advances were made by Zhang et al. (2020; 2021), who studied convex RL under the framework of RL with general utilities. Their key contribution was a policy gradient estimator for general utilities and the identification of a hidden convexity property within the convex RL objective, enabling statistically efficient policy optimization in the infinite-triall setting. More recently, in (Zahavy et al., 2021; Geist et al., 2022) convex RL reinterpreted through game-theoretic perspective. The former work views convex RI. min-max game between a policy player and cost player, while the latter positioned convex RL subelass of mean-field games.
A related strand of research focuses on the expressivity of scalar (Markovian) rewards. Abel et al. (2021) demonstrated that scalar rewards cannot naturally encode all tasks, such as policy ordering or trajectory ranking. While convex RI. extends the expressivity of scalar RL in these aspects, it still has inherent limitations. Specifically, infinite-trial convex RL excels at defining policy orderings but lacks full trajectory ordering capabilities, as only considers the stationary state distribution. In contrast, the finite-trial convex RL formulation presented in this paper naturally captures trajectory orderings at the cost of reduced expressivity in policy ordering.
Another relevant direction concerns RL with trajectory feedback, where learning occurs through entire sequences rather than scalar rewards. Most prior works in this area assume an underlying scalar reward model, which merely delays feedback until the episode's end (Efroni et al., 2021). A notable exception is the once- per--pee-e feedback model studied by Chatterji et al. (2021). Lastly, related research in multi-objective RL has explored the use of vectorial rewards to encode convex objectives. The works of Cheung (2019a;b) demonstrated that stationary policies are often suboptimal in such settings, necessitating non-stationary strategies. They provided principled procedures to optimize policies with sub-linear regret, complementing our analysis in aefinite-horizon convex RL, where distinctions between finite and infinite trials diminish.
A.4. Markov Games and Multi-Agent Reinforcement Learning
Markov, or stochastic, games, were introduced by Lloyd S. Shapley (Shapley, 1953). Interestingly enough, their introduction coincides with that of single-agent of Markov decision processes (Schneider & Wagner, 1957; Bellman, 1958). In an MG, agents interact with both the environment and each other. Each agent must balance immediate rewards against the potential future benefits of guiding the system to more advantageous states. Since their inception, MGs have served as the canonical model of MARL (Littman, 1994) which in turn encompasses numerous applications like autonomous vehicles et al., 2016), multi-agent robotics (Singh et al., 2022; Gronauer & Diepold, 2022), and general recreational game-playing (Mnih et al., 2013; Silver et al., 2017; Berner et al., 2019).
In recent years, theoretical MG research has focused on developing computationally and statistically efficient algorithms. The literature has experienced rapid development making an exhaustive review infeasible in the context of this small note. We outline results regarding (i) the computational complexity of equilibrium computation in MGs, (ii) "no-regret" learning approaches with convergence to the corresponding equilibrium notion, (iii) convergence to a NE when the game's structure permits it, and (iv) offline equilibrium learning from data.
A number of works (Deng et al., 2023; Jin et al., 2022; Daskalakis et al., 2023) concurrently proved that (coarse) correlated equilibria are intractable in anfinite-horizon MG when the policies are required to be stationary and Markovian; computing them is PPAD-complete. This is a pronounced contrast to normal-form games where they are computable in strongly polynomial time. In terms of "no-regret" approaches, the literature has been quite fruitful, as it considers inite-horizon games and policies that are stationary and both Markovian and non Mar-Markovian. The solutions (Jin et al., 2021; Yang & Ma, 2022; Zhang et al., 2022a; Erez et al., 2023; Cai et al., 2024) are diverse and build upon the hellow-the-rggalariee--dee and online-mirror-dessenn framework. Nash equilibrium convergence has mainly considered fully competitive two-player zero-sum MGs of infinite horizon, the Markovian counterpart of potential games, or their unification (adversarial team Markov games) and games with certain structural properties on the rewards and the dynamics. In two-player zero-sum games there have been results with a mostly stochastic-optimizztion approach (Daskalakis et al., 2020; Wei et al., 2021;
18

---

Solving Zero-Sum Convex Markov Games
Sayin et al., 2021; Cen et al., 2022; Zeng al., 2022). In addition, notable work guarantees convergence to a NE in infinite-horizon games using only bandit feedback (Cai al., 2023). Then, for Markov potential games, global convergence of policy gradient methods has been presented in (Zhang al., 2022b; Leonardos et al., 2021; Ding et al., 2022). Moreover, (Kalogiannis et al., 2022; 2024) consider an MG of a "team" versus an "adversary" similar to (Von Stengel & Koller, 1997) and guarantee provable convergence to NE. Lastly, (Kalogiannis & Panageas, 2023; Park et al., 2023) generalize zero-sum polymatrix game to their Markovian counterpart with extra assumptions on the dynamics, and prove the tractability NEs. In terms of learning equilibria from samples, (Bai Jin, 2020; Cui Du, 2022) guaranteed sample-efficient learning of NE in zero-sum games and (Song al., 2021) went further to consider general-sun games. Finally, (Wang al., 2023; Cui al., 2023) consider the sample complexity of learning equilibrium beyond the tabular setting.
B. Optimization Preliminaries
In this section we go over some rudimentary optimization lemmata as well as some novel exploration of the min-max optimization landscape for pPL. functions. Namely, Appendix compliments the study of (Nouiehed et al., 2019) for the constrained domain. To our knowledge, we offer the first such investigation of the constrained pPL. landscape.
B.1. Optimization Definitions & Lemmata
Lemma B.1 (Smoothness inequality). Assume that f + I& is an E-smooth function. Then, for J.y X it holds that:
L f(v) + (Vf()). 11v- x1 -) S f(x) fv) + (Vf(v).v z)
L 11 x1
Definition 7. A function f is said to be l-weakly convex if f(x) + & ||~ is convex.
B.I.I. CONCERNING THE GRADIENT MAPPING
Lemma B.2. Let X C. Idd be a non-empty. closed, and convex set. Denote by 1x Rd + X the Euclidean projection operator onto X. The following inequalities hold,
for projected gradient descent:
(u, 11x (x - -mu)) 2 - ||2 IIx (x - -m))l?
77
for projected gradient ascent:
(v, xx (x + tw) - xx) 2 =100 1xx (x + no)l
Proof. After writing the Euclidean projection of gradient descent with feedback o as an optimization problem:
min 1 ||'' (x (101))
xx E'EX 2
we get the first-order optimality conditions, (ne Ix (x - (w) x, 2 TIx (x mp)) 2 0, V2 X.
Setting z = x and re-arranging.
(v - (x mll) 2 [x (x m70) - =xl??
Similarly for gradient ascent with feedback we write,
min || - (x + ( a' VEX 2
19

---

Solving Zero-Sum Convex Markov Games
The first-order optimality condition for the Euclidean projection, reads,
(x' --. x²) 2 0, A2 X.
Plugging-in x' = 1Ix (xz + nT)).
axx (xr + +1)) n, 1xx (x + m7r1)) 2 0.
Re-arranging we conclude,
(u, 11x (x np) - x) 2 "
|1lx (x + m78) - -x|]?.
Lemma B.3 ((Ghadimi et al., 2016, Lemma 2)). Let U1, U2 be vectors in I2 and X C Rd be compact conver set and scalar 17 > O. Also, let points ut, ,x E X such that:
x = 1x (I - 1701);
z = 1Ix (x 1702))
Then, it holds true that:
| 2 #1 1 - -2ll
Lemma B.4 (Stoch. vs. Det. Grad. Mapping). Assume stochastic gradient oracle 9s for differentiable function For the stochastic gradient oracle, it holds that [x]] (1)), Elllă=11 oZ. and (1)(x)) Vf(x)] < 6g for all X. Also, let x, xt, at be points in X such that:
x : Ix (xr v))))
a+ = 11 (I (z)).
Then, the following inequalities hold:
x a+ 1+1|² 2 x x+ 2+| 4nj0 + 4
| + 1 < 2 x 1| 4n + 4
Proof. We will prove the first inequality; the second follows from the same arguments.
E
+11
2E
x - ---x11p 1
2B a+ 21
< 2R
[x x + + (x) (x)(1))
2E
1z x 1= + (1. - -x
+ 4n (1g vxf(=))?
[ - x 1| + 44 + 41
< 2E
The first and second inequalities hold from the fact la + b/2 < 2/a + 2/b/2. The last incquality comes from the properties of the stochastic gradient oracle.
20

---

Solving Zero-Sum Convex Markov Games
B.1.2. Dx: AN ALTERNATIVE PROXY OF STATIONARITY
In unconstrained optimization of differentiable functions, the conventional bounds of optimization algorithms directly guarantee the minimization of V (z)]l. Le., the norm of the gradient of f at point z. In constrained optimization of differentiable functions, guarantees for algorithms like projected gradient descent ensure the minimization of the norm of the gradient mapping, i.e., y stationarity. For our work, we will consider the quantity Dx to be defined shortly. This quantity is greater than the squared norm of the gradient mapping and turns out to be particularly favorable when handling the constrained optimization of proximal-PL functions, In what follows, we will define xx and discuss some its useful properties.
I | - X (a V fz))l] It can be shown that the gradient mapping is indeed good proxy of
Definition 8. Let X' C TRd be a compact convex set and f X -> be an f-smooth function. We define (x(xx, E) to be:
ax(a, 22 min { yERd (VI(x)), x²) + b |lv x1|² + Ix(1) - Ix(x))
Where Lx the indicator function of the set X with [x)) = 0 o E X and [x(x) = +oo otherwise.
Remarkably, this expression can take closed-form. As we will show, the minimizer of the display inside the brackets exactly the point returned by step of projected gradient descent the argument with stepsize equal to Claim B.5 (Closed form of Dx). Let be t-smooth function defined a compact corvex set X' C R. point X, and scalar 2 l. Then the following equation holds for Dx(x, a)):
1 Dx(x,a) = 2a Vf(x),.= - 1Ix (2---Vi) -
)) -2
V
IIx
Proof. By first-order optimality optimaaly conditions, we see that the objective is equivalent to the objective of the Euclidean projection of the point (x 1 Vf()) E Rd to X. Then, we just plug the minimizer into the display.
Next, we see that D(, a)) is non-decreasing in the scalar a. Lemma B.6 (Karimi et al., 2016, Lemma 1)). Let a differentiable functiooo f X - IR and positive scalars 0 < a1 $ a2. Then, the following inequality holds true:
Dx(2,a)) s Dx(x,02).
The following Lemma demonstrates the relationship between Dx and the norm of the gradient mapping.
Lemma B.7 (Dx vs. Gradient Mapping Norm). Let X C Red be a non-empty, closed, and convex set. Consider differentiable function X + R. that has an E-Lipschitz continuous gradient. Define the gradient mapping point x X with step size 1/f as,
(x
xt) x())
where,
x = Ix I e (V(())
Then, the following inequality holds:
Dx(x, 2 B1lat x=12
Proof. By observing the definition of Dxx we observe that first-order optimality for its inner minimization problem read,
(vf(z) (y =)) - 2 0, e X.
On closer inspection, we recognize the first-order optimality of the Euclidean projection of one gradient descent step, i.e.,
L xx
xt = arg min
(V[(z).)
x) + 1
yEy
21

---

Solving Zero-Sum Convex Markov Games
Plugging-in xt:
Dx(2,() -2 (Vf(z), x - - 1111 z||² (V
28 (Vf(z), x- 1 1111 x
2 e 1| x
where the inequality follows from Lemma B.2.
Lemma B.8 (( Reddi al., 2016, Lemma 6)). Let f X - R be an E-smooth function and point & Rd. Also, define the vector E Rd and y E X to be
: IIx (x m7))
Then, the following inequality is true:
f(v) - f(2) + (Vf(x)) vs 2)
(5 2
(5+
l 1)
+ 2m
11 - x1|'
||
x²|²
1 =||²
2n/
1.1.3. A DESCENT LEMMA INVOLVING Dx
Lemma B.9. Let X C & be closed convex set, and let f : X + R be E-smooth function for some E >> 0. Suppose > O with 1) S 1. For any E X and any vector E IRd, define x+ = Ix (x qp) Then the following inequality holds: st-
f(xt) S f(x) 6
(x, 1/n) + [V ull
Proof. First, we define b+ := 11x (I Vz())).
Invoking f-smoothness of f for x, __ and assuming a > with a 24
f(z+) f(x) + (Vf(c) (Vf() s f((x) + (Vf()), 2 | 21
||, - x/
f(z) (V.f())
2 | x0|
f(x) 2a Dx(x,o).
(I)
Invoking Lemma B.8 with x, y= =
x, fxx
f(ā+) f(x) + ( 1 ))
|| =
(2)
a
Again, invoking Lemma B.8 but with 2, y = F4, E+,
f(x+) < f(z+) + (Vf(x) u, - I++)
+
+(1 l 1
{
||= - x11 + (2
(e
+ 1
1
1 x1?
1
||+4 I+112
(3)
2m
2m
2n
Adding 1/3x(1) and (23x(2) and letting 1/a=
1
2
f(o+) S f(x)
(x 1/n)
| x|
6n
3n
22

---

Solving Zero-Sum Convex Markov Games
Adding (3),
f(x+) 5f f(x) " Dx (x (0,,1/)) +
(
2
1|
x²|
3
3n/
+ (V)(z)
U - -x+)
(
1
+ +(2 27)
|| - x
+
+
| - x=1
2 - =+1"
2
27/
27j
$ f((x) - " Dx (x(21111)) 1/1) +
56
1
|
=1|
6
61
P [V(()) - -11 +
1
|
I+1l
2
2p
1 1
1
+
1|++ - x=
1|
- x12
(4)
27/
21
58
1
f(x) Dx (x,21111) +
| x=1?
6
6
6n
VV(xx) - ull
2
L 1
+ 2 27/
||++ - ==
$ f(x)
2 Dx 1/n) + 2 [[]x)) u|
u||²
(5)
(4) follows from the application of Young's inequality;
(5) follows by dropping the non-positive terms; non-positivity follows from the choice of the step-size,
52-
B.2. Min-Max Optimization Lemmata
The following claims novel to our knowledge. They justify the intuition that the constrained min-max pPL land- scape should resemble its unconstrained PL. counterpart. For example, the trivial bound [[V=[(z,)) (x,(,,)))' s
e2 lyy - y'll of the unconstrained setting takes the form Lemma B.
Claim B.10. Let X and y be convex and compact sets. Suppose that the function f X x y - RR is E-smooth. For given points y1: 322 E V, define in and ot as follows:
Ii arg mingex fx, M1), and
x = xx (x1 v/ Y2)).
Then, then holds true thut:
1
| - =1 < y2ll.
Symmetrically, for given points 21, X, if
arg magmax f(11, v1). of Hy (n V
! |lll vill < {| x2ll
Proof. By optimality of æ1, ot for their corresponding optimization problems:
(Vf(m,))), - æ1) 2 0
(6)
1
((( > 1
x1 - xt
77)
23

---

Solving Zero-Sum Convex Markov Games
Addinniand-suubractinng V (2) Equation (6),
S ( - -x1)
(V/(21,)) (1) V 8/) + 32), - xx1)
(V[(n,)))) (5(x1,82)) - x1) (VI(xi, (x), 12))
- x1).
(8)
Hence, combining Equation (8) with Equation (7),
(vf(z1.21) (211 - x1) 2 (2(12112)
- -
By Cauchy-Schwarz,
[Vf(z,))) V (f(11.
|
xi ž -
| -==1l 1112
Finally by Lispchitz continuity fxr |lyI
3/2
21
This completes the proof for step of projected gradient descent. The arguments for the projected gradient ascent claim identical.
Lemma B.11. Assume f X x y an E-smooth function, and scalar
0. two points y. vf E y and
argmin [(z, v) It is true that:
2² by v'11²= Dx((,
Proof. Let xt = arg T (V - ==1} II (x (x-2 Vf(,,)))
1
Dx (x (r, 1/ a)) = (VS(x, 1/) ) xt) マ/2 | =+1²
20
(Vf(z,))) v ffr xt) 2 - x 11 1 (Vf(z, 1), xx)
(9)
We have assumed that = arg min f y). therefore,
(Vf(z,)), x)20 20 E
As such, when x
[[(,,)),x-- 50.
Hence, since =1 11 -0---11- (Vf(x,)), xI x + $ plugging in (9),
a || -
1 Dx(
(v)(z))) Vf - 2a
Using Sauchy-Schwarz and é-Lipschitz continuity of the gradient,
e fly 5'll || x
- -x(x,
1
2a
Finally, using Claim 10 with 7 =
@² ll v'12 a
1
Dx (z, ae
2a
24

---

Solving Zero-Sum Convex Markov Games
Lemma B.12. Let f X x y be E-smooth functionn, O, two points y: y Y, and a point X. Then, the following
inequality holds:
-x(()))))()))) 36 ly w/1
Proof. We define 2, E' E X be:
T = 1I
V f v)
1 V fz
J': 11x
By the definition of (x))) we write:
1 (x) - (V/(2, y), x-
x|
2a
1
- Dx (z, 0;y/ (Vf(z, -
20
2
Considering the difference Dx(x, 0, Dx(2, v' we see that:
1
(Dx(z, Dx(z, a: 0/1l = (V fx. vaf(z, 1) -
[ [ F|
| z²1²))
2a
2
S (Vas(<,, (2 V.f(z, ) 2)
(1Ix- F|
|| 1' =11²))
$ (VaI(z, VaS(2, (2,1))), 2)
|
$ [VV.f(z, 9) vzf(2, v= -
| - -
s 1 V V=f(,,8')11 +
1
|Vzf(z,)) vaf(r,z/11
a
2a
362
$ 2a ly v112.
We note that:
The first inequality follows from the triangle inequality.
In the second, we apply the reverse triangle inequality.
The third inequality uses the Cauchy-Schwarr inequality.
The penultimate uses Lemma B.3 and the final É-Lipschitz continuity of the gradient.
Claim B.13. Assume a function f X x y satisfying the pPL condition with modulus μ over f(x, for any x E X. Also, assume that (xx) == max,ey (x, y). Additionally, define: D (x. a) = -2a min.ex (V x) + ||= - x0| Then, it holds true that,
D - Dx(x, < 3En:DDy( (2;222 x2;
where K P.
Proof. We define 3. x' as,
1I
x
a1
11x
v Vf(z,8) v)
a1
25

---

Solving Zero-Sum Convex Markov Games
Then, see that:
1 201
(2,
Dx az: a2: v) - (VV a1 2
|| - =1*) ( (V y), -x)
01
||
2
< <((V((>) v/(r,, x' -
11
|| m
|| - x'1?
(
Vf(z, 2)1l || - -
01
> - 1'' ?
2
3 [ v {(b,,)]|
201
36
1y -=)(11
201
3lx²
() 02;
201
Where, the first inequality is due to the definition. The second and the third, follow from the triangle inequality and the reverse triangle inequality respectively. The fourth follows from the fact that the projection operator is contractive (1 (I-Lipschitz). The last one is due to the quadratic growth condition and the pPL inequality.
C. Hidden Convexity, PL, KI, and EB
In this section, we offer brief exposition to the notions of hidden convexity and other regularity conditions it is related to. We refert the interested reader to (Karimi et al., 2016; Li & Pong, 2018; Drusvyatskiy & Paquette, 2019; Drusvyatskiy & Lewis, 2018; Liao et al., 2024; Rebjock & Boumal, 2024) and references therein. We commence by defining hidden convexity in the manner that (Fatkhullin et al., 2023) do it.
Definition (Hidden Convex Problem). Consider the optimization problem
min f(x) = (c(x)). #EX
This problem called hidden convex with moduli Lo-1 > 0 and μa 2 0 (or the function f is hidden convex on X)) if the following conditions are satisfied:
(HC.1) Convexity of H and Domain:
The domain V c(xt) is convex.
The function H L1 - R satisfies for all u, v E U and 0 S a $ 1,
H(11 atu + ov) -1 (u) aH((v) (1 a)auH
| -o|2
The problem admits a solution u* E U.
(HC.2) Invertibility and Lipschitz Continuity of 11:
The mapping c X > is invertible.
There exists Me 0 such that for all z. X.
|| - vll S Me [|((z)) - c(y)ll.
Furthermore, if μn 0, the problem is referred to as (Pe, mH) (H) -hidden strongly convex.
Assumption 2 (Lipschitzness and smoothnes of c). Let xx - L4 be mapping such that for all (x, v), (x', ,5) E Xxy and all u, w/ E U4 the following conditions hold:
||o(2, v) c(x', // S Lell(z.)) v) (zl,3))ll:
[lc=((u) - c (u')l S L. =1lu w'll:
and also,
Vo(r.y) 9) ve(x', S Cell(s,))) v) - (2x, v'',v') v/)ll
VV- (w) Vc- (u')) < ea 1| n'll-
26

---

Solving Zero-Sum Convex Markov Games
Fact C.1. A hidden fonnrue--ccoexefnitioon has unique maximizer.
C.1. Equivalence between the three conditions
Throught this subsection, we will denote X' to be X arg min f(x), an w.r.t to point x E X' is defined as some element of arg minz | x'I1. Moreover, define F()) := f(x) + Ix(x) with Lx(x) 0, if E X, and
Ix(x) +oo, clse.
Definition 10 (pPL. KL, PEB). Let f X + R be an L-Lipschitz continuous function with é-Lipschitz continuous gradient. Then,
Proximal Error-Bound (pEB); J' is said to satisfy the proximal Error-Bound if Be 0 s.t.
Txx (x 2 (
|| x S
( Vo E
Proximal Polyak-tojasiewiccz (pPL): f is said satisfy the proximal Polyak--.ojasiewier condition if Ey. s.t.
_タ2 Dx(x, 2 (f(x)) f(x)))
Kurdyykka-Ljjasievicc(B.I fs said to satisfy if 37 s.t.
min a, (x)))
| (p(x)x) -(())) E
Lemma C.1 ((Karimi et al., 2016, Appendix G)).
(pPL) = (pEB) = (KL).
Remark As will see, (KL) with a modulus z implies (pEB) with modulus 2 turn, (pEB) with modulus c, implies (pPL) with modulus 1#427
Following, we repeat the calculations of (Karimi et al., 2016) by explicitly tracking the dependence between the constants. We will denote X == arg min f()) and (x) be the normal cone of X at x.
KL >pE First, let be F(x) == f(x) [x(x). By the ê-smoothness of f and the convexity of Ix, we observe that F is weakly-convex. By (Bolte et al., 2010, Theorem 13), for any domP there exists subgradient curve Xa [0, 00) - dom/" that satisfies the following:
xa(1) E (F)(x())),
Xa (0) I,
d (()((t)) (t)x
dt
where (t)( is non-increasing and Lipschitz continuous function for t In, oo] for any 17 > 0. Further, we define the function r(1) = vF(x((() - F*. By differentiating r()), we observe that:
dr(1)
F(x((1)
dt
2 F() F
(t)12
2 F(x((x(t)) F F*
S X
In the second line, we plug in the definition of the subgradient curve.
In the third line, we use the KI. inequality and the fact that (t) E -FF((x(11)
27

---

Solving Zero-Sum Convex Markov Games
Taking the integral, we write:
r(7) r()) = '"
T dr(t) dt
dt
S V /-" lIxx(t)lldt
(10)
- v / (1/2dis((xx())xxx(())
(11)
where:
(10) uses the bound on r(t)
(11) the fact that any curve connecting two points has length greater than their Euclidean distance.
Now, we will show that +im r(T) 0. By (11), we get
r(T) r()) = S'" dr(t)
di di
11xx(1)112 dt
2 ((F(x(()) - F.
2 l. (" VF(xa(t)) F+dt
P
--TI((T)
$ 2
where the first inequality follows from the KL condition, and second inequality uses the fact that F(Xx (t)) is non non-increasing in f. Hence, we get bound on r(T),
0 05r(T) 2r(0) 2 TT'
By taking the limit of T + co, we get limy r(T) + 0. Now we can focus on the term r(0) VF(x) F*, Proceeding, by (1I) we write.
F(x) F. 2 dist X*),
(12)
From (12) and the KL condition, we see that:
dist dist(O, (ddis(xx,x*))
(13)
Now, let define + prox to (x - [x()). By the optimality of xt, we have - -Vf(xt) - e(xx -x) Nx(x*)). As such,
Vf(**) - Vf(x) - f(x - x)) (1x(x*))
Letting the particular subgradient of [x(x+) that achieves this be &. we write.
dist (O, (F(+*)) = |10 Ell
= [|V - Vf(x) - e(x+ ((x==(())))) -x)
< 0l|xt = [V - -f(()]]
< 20|lx - =11
(14)
28

---

Solving Zero-Sum Convex Markov Games
where used the triangle inequality and the E-Lispchitz e--ispchitzcontiiuitty
continuity of V.. Finally, we derive the proximal-EB condition
by
(ist(r, )²) < || xx1l
dist(a* "atttx",1"'" ,
1
S || x+1|
dist (0, ax(²)))
/
2
s || x+1| ||
+
|| + x
28 |+
|| x x=1
We note that:
the first inequality follows by the triangle inequality;
the second inequality uses the (13);
the third inequality uses (14).
Re-iterating:
28 x+
min
||x1|| 2 2p (f(x) f())),, v dist(r, x*) 1 1
||0
e =0(
DEB-XpP
Before proceeding, we define the forward-backware envelope, F., of F (Stella et al., 2017, Definition 2.1),
as:
p=:=min min [ - x) + L 1ly x212 + (x(x) - Lx((0) yERd
2
Additionally, we observe that: Dx(x, 28 (F(x) - Fi (a))
Movving forward we note that by assumption, it holds that:
x (x- - (V)(
dist(r, $ c x 1Ix
From the latter we write,
F(x) F" F(x) - (x(x) + F; (x) F
< F(x) F1(x) + 28 1/ z1|
$ F(x) F1(x) + 200 x - 11x ( (-2(((0)))
|
$ S1+4c) (F(z) - F2((x))
1 (1+ 28 Dx( E).
Where the second inequality follows from the pEB condition and the two last steps follow from (Stella al., 2017, Proposition 2.2(i)): & 2 || Ix (x - - \ < F(x) - Fg (x) and F(x) - Fy (a) = 22 Dx(x, E). In short,
1 4 (F(x) F*) < 2 Dx(s,
Concluding, we see that KL with modulus translates to pEB with constant c = (1 23 In turn, pEB with constant c translates to pPL with modulus 144
This means that KL. with j equivalent to pPL with modulus μ.
l
IT
9T + 3202
1 1 4 1 +
2
29

---

Solving Zero-Sum Convex Markov Games
C.2. pPL. from HSC
Proposition C.2. Let X IR be E-smooth function that is (Pes PH p -hidden strongly conver with pa 0. Then, satisfies the proximal Lojjss--ojssiewiiz condition with modulus p,
1 (441111
24
2pE
Proof. By (Fatkhullin et al., 2023, Proposition 2(1)), (4) ) -hidden strong convexity implies,
min [+(+))))
| 2 2 2 (f(x) - f(=)).
8,
While, (Karimi et al., 2016, Appendix G) and our precise quantification of the constants,
11
1 + 4 (1+
2 2P2PH
C.3. QG directly from HSC, KL, pPL
Proposition C.3 (QG from HSC). Let f X - TR. be E-smooth function that is (iidddee strongly convex. Then, for all x E X,
f(z) - f(x))((x") 2
μQQ
x x²1
2
with PQG He where x² the unique minimizer of over
Proof. We start by leveraging the strong convexity property of the function H. By the definition of strong convexity with modulus pn, for any u, E U:
-
u²))
P8
11
(15)
When is minimizer of H, the gradient at u² satisfies:
VVH((u)u--))) 20
Leveraging the latter, (15) simplifies into:
((u) H("))(u 2 μH ||u 11
(16)
Because -1 is Lipschitz continuous with modulus 1/ obtain:
1
|| - x01 = ||c (w) c (u*)|l (ut)l
||u u²ll
tec
Substituting this bound into equation (16), we obtain:
H(u) H(u))² >
PH
||u u² u²112
2
H || x=
Recognizing that (u) f(x) and H(u)) = f(x*), we can rewrite the above inequality as:
1.
f(x) f(x)) >
|/ x=
2
This concludes the proof.
30

---

Solving Zero-Sum Convex Markov Games
Proposition C.4 (QG from KL). Let an E-smooth function f X R satisfy the Kurdyka-ttjaasiewicz (KL) condition with modulus Js > Le.:
(((())
inf (a)(()
||>=ll? Vo X.
Then, it satisfies the quadratic growth (QG) condition with modulus E/2 i.e.
1| - =; 1 - Vx E
4
where 27 arg g || - 1=1 and in turn X == arg min (x))
Proof. Before proceeding, we note that the condition in (Liao et al., 2024) is what we call the KL condition in this manuscript. Let define F(-) = f(-) + [x(:) where Ix is the indicator function of the compact convex set X. We note that, Lx is convex and ff is ê-smooth and as such e-weakly convex. Hence, F(-) f(-) Lx(+) is also é-weakly convex. By (Liao et al., 2024, Proof of Theorem 3.1 (PL-+EB)
|
inf p #EAF(a)
||sI||,
where x arg min Ex. || - 11² and turn x arg min ZEN (1x). Then, by (Liao et al., 2024, Proof of Theorem 3.1 (EB-+GG)) we know that,
4/p xx- rill {1x) =()))
Proposition C.5 (QG from PPL; (Mulvaney-Kent et al., 2022. Theorem 2)), Let an E-smooth function f X + R satisfy the proximal Dolyak-t.ojsiiviin (PL. condition with modulus >> 0. Then, it satisfies the quadratic growth (QG) condition with the same modulus μs,
1 [| 1|=-1 f(x)- ft Vz e
4
where J arg ming ex+ || - 11² and in turn x == arg min f(x).
C.4. Warm-up: Stochastic Projected Gradient Descent on a proximal-PL. Function
Now consider stochastic projected gradient on a nonconvex pPL f-smooth function f. The analysis closely follows Reddi et al., 2016).
Assume (g)( g- (x), (x) ga gx((1)) 5 and l1 (x) < o², Further, define points 2441, Tr-1 be:
F(+1 IIx (It (x:)))
F++1 IIx V
Theorem C.6. Assume an t-smooth function f X + R with an inexact stochastic gradient oracle 9n such that Eg. (z) = (z),,, (10x(x) - gxll & and || S 0². Then,
running stochastic gradient descent with 6, -n-inexact gradient for T > O iterations, yields the following inequality:
(Rf((zo) Dx( 38 f(x*)) +352 30
Σ
T
Further, if is pPL with modulus the followinng inequality holds true:
Ef(rr+1) - f(x') < exp (- (T) (f(2o) f³)
3182
3la
31

---

Solving Zero-Sum Convex Markov Games
Proof.
We let F141 2441 = Hx (x): (fx)). Invoking Esmoothness of for Ft, F++1 and requiring that 1) S 8
((x)
[
zzll
27
1
f(x)) (Vf(z)), E(+1)
-
| xxll?
2n
= [(x)
" Dx 1/1)
(17)
2
Invoking Lemma B.8 with Ft, y = 1, 2 = Iz, (f((xt)
( -
((x+-1) S f(xx)) +
[ 1)
|| - xeel
(18)
Again, invoking Lemma B.8 but with x = Tt, y = Ft+1, 2 = I+ v = g(zr))
f(1(11) S f(1+1) + (Vf(x,) , I++1 - II++1)
l 1
||++11 - xell2 xzel? + (
{ + 21/
1
1
| x=l12-
|
Ie+1ll?
(19)
2
2n)
2n
Adding 1/3x(17) and (18)
f(T S f(z))
7 Dx 1/n))
2
|J xell?
6
3n
Adding (19),
f(a++1) S f(x)) !
Dx 1/1) + ( 2
|J+41 xell?
3n/
(V)(x)) (x1)) 2441 - I(+1)
8 1
||01+1 - -xxl12= + (
1
+
+ 2n
|| - =2e112
|| Ie+1|l
21/
2
2n
$ fxx))
" (Dx(xt,111)) +
5l 1
| =x+12
6
6
6n
+ 1
Vf((z)) (xx)))
(20)
+ +(2
||00+ - 2il1
$ f(x))
"
"Dx(xe,111) 1/n) + 7 [Vf(xt) (x:))1
(21)
6
< ((x)
Dx(et, 1/1) + (V - (x:))))
(x)) - Gn (x:))l
(22)
We note that we have picked 1) S 58-
(20) follows from the application of Young's inequality (a, b) < 2 1|a| + 1 |ba with p
(21) follows by dropping the non-positive terms; non-positivity follows from the inequalities:
1. 02 58-
5 0 2. \ < 5l < then - 77
32

---

Solving Zero-Sum Convex Markov Games
(22) follows from ||a + bl2 2| +
Taking expectations:
= Dx 1/m) + 17 + t1zz
?
(23)
6
where the last inequality follows from the choice of the step-size. Rearranging (23) and summing over T,, we get:
T Σ Dx(at, 1/1) S
- ( + +52 + +30 3 (Bf(ro) - f(x)))
nT Σ
+ +38 + +30
T/
When the pPI. condition holds and 17 52. we get from (23),
1
Bf(x++)) - (1
/
(Bf(r)) -
00
3B
and as such,
T
Ef(xT) - 5
11
(f(zo) - f*) (6
Σ
3
3
1=1
(1
# T
(f(xo) - -p) + (6e 22)
1
(1
3F
T+1
30
(1
37
T (f(x)) -f*) + 3662 3l0
$ 32)
1
(-) (f(20) - - 3252
3lo
S exp
1 /
D. Constrained Min-Max Optimization Under the pPL Condition
D.1. Key Lemmata
Theorem D.1 (NC-pPL and cont. of maximizers). Let function f X x 3 - IR with faz satisfying the proximal-PL
condition with parameter μ for all a E X. Then, consider points 21, D2 E X and y" (x1). (12)) E y with y (x11) == arg yey [at, .y) and y² (I2) = arg max [122, 4), it holds true that:
llo - y (x2) < T.+ 11 - x2ll
where L. ;= p.
Remark 2. One might compare the last statement to the Robust Berge Maximum Theorem (Papadimitriou et al., 2023, Th. 3.20) which concerns (non)convex-stroo) -tonogly-ccoccav functions with coupled feasibility sets. Essentially, the former statement illustrates that hidden- sirden--trong-ee strong-concavity the feasibility sets are only "hiddenly" coupled. This allows us to decouple the constraint sets and view the problem as constrained nonconvex-pPl problem. Then, it is quite intuitive that Lispchitz continuity of the maximizers holds in light of the analogous result (Nouiehed et al., 2019, Lemma A.3) which concerns unconstrained min-max optimization over nonconvex- PL functions. Ultimately, this decoupling principle is also the reason why Kalogiannis et al. (2024) can compute the gradient of the maximum function by only invoking Danskin's 's Theorem and not the more elaborate Envelope Theorem (Afriat, 1971).
is in some aspect stronger assumption than strong-concavitg in hidden-
Proof. Since we have defined the pPL and QG growth conditions for minimization problem, let us assume g(2, y) -J(x, y). Consequentially, arg min g(x, y) = arg max,ey (xx,v) e y (x)) Finally, we define:
D (y(),;;))) == -2a min ze)
{
(V (Vyg(z,8)22 v) 2 || y/1
33

---

Solving Zero-Sum Convex Markov Games
By the proximal-PPL condition, it holds that,
2 Dy (u' (x1), (/)) 2 (x1)) - g (x2,1"(22)) (x2)))
By the QG condition:
9 (x2, (02.v((1)) (xi)) (z2, (22. (x2)) HQQ (1)) (x)) yo (x²2) 2
2
Where, (7(22) = arg min min (x1) - 3/|l and (x) = arg min Bey ( y). Finally, by Lemma B.
1/1 - - =211
Putting these pieces together,
PQG 2
|| (x1) - (12))
|| x2
2μ
Further, we know that pPL with modulus implies QG with the same modulus (Proposition C.5). This concludes the proof.
Corollary D.2. Let function f X' x y - TR with f(x,) .) satisfying the proximal-PL. condition with modulus for all x E X. Then, (xx) = max f(, y). For any two points I1, I2 X it holds true that:
[v (=2(2)) la ||l xzll.
where la = + L.) = c+ e
Proof. We write,
[. - V.
= V.f y² (x1)) Vz v < é [1 y (#1)) - (12,,"(<>)) (z2))
- f [| z21 + fL, ||=1 1 xzll
The first equation holds due to Danskin's lemma, and the first inequality due to é-Lipschitz continuity of the gradient. The second inequality is due the triangle inequality and the Li-Lipschitz continuity of the maximizers.
Lemma D.3. Let X x y + R be an L-Lipschitz continuous and f-smooth function that satisfies the two-sided pPL condition for both ((,y) and fxx -), then:
min max f(x, v) = max min f(I, v) =: x
xEx yEy
yEy xEX
Proof. We can invoke (Yang et al., 2020, Lemma 2.1) which holds for two-sided pPL functions with minor modifications.
Lemma D.4. Let the function X y TR satisfy the pPL. condition with moduli μ1, P2 > O respectively for f(.,)) Vy E y and (x, :), Vx E X. Then, the function & X R with ((x) maxy'ey (xx satisfies the pPL condition with modulus μ1.
Proof. For the purposes of this proof, we will enhance the notation of Dx as follows:
D& 0; -2 min
(Vf(x,
x) + || x=|
=
(2, a) = min
(V
a ||2 2: 1|?
2
34

---

Solving Zero-Sum Convex Markov Games
(x (a) = D' (x, ka: (x))
2 2 (((,)0
min f(z (r)(())))))
z'ex
Further,
f(z', -
max f(z' NEy
and minimizing on both sides yields,
min FEE
[1', (x)) s min max [(+ v) $²
z'Ed yEy
Hence,
(x) 2/11 (D(x) D²).
D.2. Stationarity Proxies and the Gradient Oracle
Definition 11.
We define Dy and D to be the following quantities:
(-V - y) + a || y112) *EY {
Dy 0; = -2x min
2
and correspondigly.
(x, = 22 SE
(VV()), - 2) xx) x
a x=12)
Definition 12. We define the deterministic and stochastic gradient mapping at point I, and y to be:
G2,r, (x)== == 1 (x xxx (a T) and G2 = -a (It);
G (2+)) 1 (x Txx (x T= vc))) and G%,T= G (1te:
Tz
and respectively:
()) = (Ily (y + Typ 3) and Gr = G (y); S (V) = Ty mTy (y + i) y) and G = G M.r, (y)- Assumption 3 (Unbiased Inexact Gradient Estimators and Bounded Second Moments). For all iterations t, the gradient estimators Oz ( ve) and 0n (zz, ve) satisfy
E @e (2,, ve31 g( vt),
E 10 ve'1 = g((0,,)))
and
E
(1r,, vi]1[]] (1)lt,..))??
o² oz.
E
[10
ww]l (.0(
In turn, 11g vr) - (x) & 6g. I1o,, (Ze, ue) - V ve)ll S 8y-
Remark (Bound on Second Moment instead of Variance). At first, it might appear slightly stronger assumption to place a bound on the second moment of the gradient estimator. Yet, in most relevant works the variance of the relevant estimators bounded only after bounding the second moment (Daskalakis et al., 2020; Zhang et al., 2020; 2021). As such, this assumption reasonable and rather standard to satisfy for the aforementioned applications.
35

---

Solving Zero-Sum Convex Markov Games
D.3. Convergence of Nested Gradient Iterations
We can formulate the nested gradient iterations algorithm using the following template,
M++1 + (f (), 6y);
(24)
Ze+11 f- Ix (2+ - n/ AVV [2 vt++))
where, AR, E) returns an e-approximate maximize of function h. As function, it can be implemented efficiently by projected gradient ascent.
Finally, the outer loop of the process implements projected gradient descent with stochastic and inexact gradient feedback on (()).
Theorem D.5 (NC-pPL). Let f -),,)). Then, after T iterations of (24) it holds true that:
x y - be an E-smooth function satisfying the PPL condition with modulus μs for
6LDx T&T
ghit 2,TT
+ 65 + 60
Proof. By Theorem C.6 and tuning of step-size Tx S 5Ł. we get that,
1
(o41)) 38 (BD(20) ((x)))
T
Σ
+ +362 30
TxT
In this context, the inexactness of the gradient oracle 6, is:
8
max
E ((x())
Vf(z,,
max 05
E 113e v'(x))l,
while by the quadratic growth condition of f(x,,) we know that,
By 11ye y" (xx)) S (B(())) - (x,,,
where cy is the accuracy the inner loop which we will defer tuning. We, invoke Lemma B.7 to see that the sum of (x,,,, 1/Tz) upper bounds the sum of G
T
6 (E +(x*)) + 652 + Go
G 2.Tx
T,7 T
Now, we see that (2x)) ((x") is bounded by LDx due the L-Lipschitz continuity of d and the bounded diameter of X. Finally, tune Tu and Ey-
To 56
T 18LDx x
M2 18c7
Ey V18'
Theorem D.6 (pPL-pPL). Let f. X > - be an L-Lipschitz. E-smooth function and X, y be two compact convex sets with Euclidean diameters Dx, Dy respectively. Further, assume that f(, y) satisfies the pPL condition with modulus pa for all y E y while fxx, satisfies the PPL. condition with a modulus Py for any x E X. Additionally, let 9x be an
36

---

Solving Zero-Sum Convex Markov Games
inexact stochastic gradient oracle such that Eg (2) (x)), iterations of (24) with tuning of step-sizes Tx 5t."
E (l)
Ir (x()l) of and [1 S òz.
Then, after T
(- (T) LDx + 3l002
3640
[+( xxxx)=)+)+))))))) s exp
36.
Mr
Mr
Proof. By Theorem C.6 with Ty 525
(- 1l T (1(20) -b) 3l402
34402
EQ(TT+1) (xx²) S exp
36x
Me
Pz
First, repeat the fact that LDx 2 $(x0)
कx due Lipschitz continuity. Then, note that 82 has be tuned
ehs and the batch-size needs to be M₂
where >> 0 is the desired accuracy. Finally, T 36e log (LLDx
V B8o
cpz
D.4. Convergence of Stochastic Alternating Gradient Descent-Ascent
In what follows, we will analyze the convergence of projected alternating gradient descent-ascent for nonconvex-pPL and two-sided pPL functions. The convergence proofs closely follow those of (Yang et al., 2022) and (Yang et al., 2020) respectively after carefully modifying the arguments to make them work for the constrained setting. Convergence is proven by showing that an appropriate Lyapunov function diminshes along the trajectories of the algorithm's 's iterates (Bof et al., 2018).
In both scenarios face, proving that the corresponding Lyapunov function diminishes is proven by first:
lower bounding the descent on the maximum function (--) for every update on
lower bounding the ascent on f(x,)) :) for every update on y;;
upper bounding the descent on f(;;y) for every update on æ.
As reminder, the iteration scheme of alternating gradient descent-ascent is the following,
It+1 xxx (x+ TT ( vc))
V++1 Ty (ye + ( yr))
D. NC-PPL
Theorem D.7. Let X X y R be an L-Lipschitz, t-smooth function and X.Y be two compact convex sets with Euclidean diameters Dx, Dy respectively. Further, assume that f(x.-) satisfies the pPL condition with modulus p. Additionally, let (gx, 9y) be inexact stochastic gradient oracle satisfying assumption 3. Then, after T iterations of (Alt-GDA) with tuning of step-sizes Ta 500ER? and Ty 52. it holds true that
Σ
T-1
IE
21
x ED (vn,
Ee + Dy)
0202 + c2202 +
CzK203 + 2
T
T
M2
Mn
where, C1, C22 C3 E O(I)
Proof.
Descent bound on +.
G.. =
(xt
II, (x+ T2 (
Tx
Due to E-smoothness and the fact that
> 5le can Equation (23) to get:
E$ (x(+1)) < (3))))
Tx "ED 1/Tx) + E
V Vaf vell V. (x.. v:ll
6
37

---

Solving Zero-Sum Convex Markov Games
(2,)
Tm
B
+
T
V ((x))) vzf(xx, yo)l T af yr) - 9 (I yt)1
6
(x:)
To
E V ((4)
V=](xt, +2==0² + 2T
6
Ascent bound on -(x),)) For choice of Ty s क2 S
(f(2241.3411 Ef(2441 M1) Tu ED 1/Ty1 -T o
Upper Bound on the descent: (()) - (aao))((aae [18411, Wr).
f vo) 2 f(ztf M1) + V v1). Det1 x1)) | =xell
=f(xc. v1)
To (Te( Vr), g2 P2.To) -Tx To (f Me0 ( Mr). 92.m
2
= =f(x Vi)
To ( (g Mt), Mr), (r.T.) To (Ir( (0 ve). (t). Parre
V (xte - Iu (1)),1)), S2.To)
Tx
12
f(11, Vi) To ( (Tr (1)),,))))..).))))))) Pa.T.)
(0x( 1/)) dz (2t, M1), I2.
Ta (ga vi) Ôz (fe. vt), De.r. -Ferr
Tx
( Me) - gz (xr, ve).
To
ET?
2
2 f(re, vi)
To
11 [0) 91)
Tx
@r
2
(25)
2
2
To (gx( vt.) (21, V - (o). Oz (Fce (1). )2,To)
To
Vzf( ve) (x
Tx 2
gt
2
1T2
2
2
f Vi)
{T= Txx
02.r
||=
I1 (2r, 21
Tx (gx vz)
(2 Me), Derra) To (on(Fe vi) Ir (a (xr, Da.r. (e.re)
Ta02
(26)
2
6
| 2,Tzz
2 |
Ts ( y=ll
2 [1t, y1) - Tx +
2
2
-z (0x(2t,) V1) - (z,, G - (2,, ve) - (x,, ve w1l1
(27)
2
the initial equations are mere additions-subtractinnn of terms and plugging-in of definitions:
38

---

Solving Zero-Sum Convex Markov Games
(25) follows from Young's inequality;
(26) follows from gathering terms and using the bound on the gradient inexactness error;
(27) follows from the Cauchy-Schware inequality and the non-expansiveness of the projection.
Taking expectations again:
2
Tx
Ef(re+1,80) 2 Ef(rc,
Tz +
E
g1
2
Tz62
Tr (1) - Io (x (1), (2
Tx
2
ET
3r
2
Tx
= -E((ze
+
E
11,T
2
2
3 E
3 x
T2
2 Vf(
4
2
2
3Tx
2
7T
2 (f)
B
1 22
x
0x
2
(28)
2
2
2
Where, we used that Tz
< 2 which means that 1 (Tx + (T2) + v
3ru
1
Bounding AGDA iterate difference E B(+1) - ( ((,,,)1)) V:)-
3r
Or
7Tz
Ef(1441: - Ef M1) 2
E ||
62
2.T
2
2
2
+ 6
Ty
EDy(U, //T1)
TTy T
We will define the Lyapunov function, The Lyapunov function.
Vi wh) = ((x,) + a (xxz) - [(x,, ve) = + a1+ as(E., vt),
with a > 0 to be tuned at the end. Also, we will denote Vú = V (it,, Bt).
EV, - EV--V411 = (1 + a) (Z)();)) (4(4+11) + a (Bf(To-L. -f
EV- - EV-1 2 (1+a) a)
Ts
2
T
Vaf vi)l 2T 25
+
3
E
gt
||
9Ta02
7Ta
82
2
2
2
+
E
Tv
1/
8 Ty
(1 + a)T
E
|
1| (1
a)
T.
V (xxz) V fxf(
6
3
2
+
aTy
ED (vt, //Ty:
2
6
9Tz
2Ta + +a)
2
(-ar, oz
0
2
7Tz 0
+
-TT +a)
82 + (-aT,)
00
2
39

---

Solving Zero-Sum Convex Markov Games
(1 + TT To
11 - (1 + a) T (xx)
Vaf(xc.
6
3
E
| 1
1|
+
aT
EDy (yr, 1/Ty:
3ar,l²
E 1 xe+111
2
6
6
9Tz
-1 +a)
2 a
0
2
(-aTy) ) og
TTa
+
(1, +a)
6 + (-aTy) 6g
(29)
2
(1 + aaTe
E
|| 1|2 (1 T) (xz()))- 2e)
6
3
| +
aTy EDy ED,
E
2
6
aT
E
1|2
2a Ty l 0/+-
2
2
9T,
+
-2Ta + +a)
a
02 (-aTy) og
2
7 a
+
2T (1 +a)
0g + (-aTg) bg
(30)
(1 + a)TT E || 1|?
(1 + OOT | (xx)) Vzf( v1)1
6
+
3
TTTTTE e
E B
11 2
+
aTy ED " ED kx)
2
6
9T,
21 +a)
a 2aT
12
0 + (-aTy) og
2
7
+
12 +0)
0
20 Typ 12
82 + (-arT, 69
2
(1 + a1+a) a
20 2
/2 x:
E
2 (1 + [1+
Vef v1ll
aTy
3Tzann2 2 -2aT of
EDDy (x
6
9T, a - 2aT Typ 12
21, + +a)
02 + (-aT,) og
2
7Tx
+
21 + a)
a - 20T 12
82 + (-arr, 8
2
(1 + TT
3T - 2aT Ty
E
g 2 - (1 + Dy l:x.)
6
+
aTy
3T - -2aT 1² x2x²2)
EDDyuus (3
6
9T, a - 22T
+
21 +a)
22 + (-aTy) oy
2
7Tz a - 2aT e2
+
21 (1+a)
82 + (-arg, 88
(31)
2
Q)T (1+0)T=
(1
+
3T - 20 2
n {²
E
g 1
6
QTyy
3rzan= - -2073 12 x22 - (1 + x) (u
6
9Tz
+
(1 + a)
2 TT 12 oz + (-a7,) 0z
2
40

---

Solving Zero-Sum Convex Markov Games
+ (
Trz a a- -y-aaa 82 + (-arr,) 8 2T+(((+))) (1+))
2
(29) uses Lemma B.12 and the fact that |a- - bl < c implies a > c, iee.
(1 2 Dy 03 - 36 11 02t1ll?
(30) uses the definition of T I2.T, and Lemma B.4 replace the term: | - retall Lee:
|| 21+1ll
s 2|
T(+1|
112 + [x+1 Es+1ll
- 2T
g2,T,
2 + 2T 11 (22, ve) V f2),
$ 2T 92
2 + 4T + 4
By the fact that ||c - d|I = ||c||2 + |d]2 2 (c and Young's inequality, we can write ||a|2 = |[(a b) + b12 s
(1+ 1/p)llall + +11 + p)][6 Then we plug in a + G2 b
-2
| || (1 (1 + +)) - 1
x (or Ta (((r.v)) Hx (x - To v=Vo))))))
1+
Tv
(1+ + p) 11
1+ P
[V Me) - [x(2,)
S + p) 11 1|
1+
8 ((r) -v
e (0(1z) - -f(2, v1))
<1 + p) 11 1|²
+
1 p)
MQG
- (1 + 11
1|²
+
1
Dy (;
Where the third last inequality follows from Danskin's lemma, the penultimate is due the quadratic growth property, and the last is due to the proximal-PL property. We have set
(31) follows from the pPL property.
1|
gb 1| +2 G0. 11?
2.7,
22 _|- 2 - v
< 24 _|2
2f y (xx))
s 2 2 1| 2exx Dy (zxe))
Re-iterating,
(1 + a)
3r -0-7-27-- T (2) E g ||?
EV- - EV+1 2
6
QTy
3T,an
-20 E 162 - (1 + a) EDy(u,, 4x))
9Tx
+
2 (1 + +a)
20T,
o% + (-arī dz
2
7īz
+
2r (1)
22
&2 + (-aTT, 6y
2
What is left to do is to ensure that the coefficients of | | Dy(ve, E; xx) in the last display are positive. We will show that this indeed the case for a correct tuning of Ta Ty and a.

---

Solving Zero-Sum Convex Markov Games
Coefficient of |
2 We assume a priori that, Tax Ty Z. Hence we can write:
+ T.
a - 2aT Tyl
1 1+ a 18a 12a
Tx 2
1
29a
Tg
2
Tx
6
180
Where we require that a S 1/30 < 1/29.
Coefficient of Dy. We require that T. 2 Iy for some >
on
3r -ar - (1 aatzh QTy
a
18a/c 12a/c2 6(1 a)/e
2
6
6
(c2 24c 12)a - 6c
6c
Tg
Tv
10
Where in the inequality we assume = 100, 1/30.
Coefficients of o oz day 8y.
For of 62
2T. (1 + +a) + TT a + 2 < (1++) +
9Tz
a + 2arT T l
2
2
60 20+ 135
200
Ts 30
Ta 100
30
60 + + 135
200728
Ta 500
30 500
60 + 2 + 135
200Tz
S T2
< 8Tg
(T. S 1/6
= s 1/Tx).
30
500
For og 52.
100k2
aTy 1 30
T2 S 4x Tz
| 1|
2 G
| 1|2 + 2x Dy
Summarizing:
Ta 360
| | 11 9,33,, EDy (vr, (,xx)
Tx 360
| a..r ||
Ty
2x
ED EDy(Ut (;
10
360
< EVV- EV44 + 0 2 + 8T28²
+ 4r 2 T + 4n. T8.
Summing over i and dividing by T:
(IC2.... + * (v),
<
720 + Dy)
2880 - + 1440x² (0z + +6))
TxT T
42

---

Solving Zero-Sum Convex Markov Games
D.4.2. TWO-SIDED PPL MIN-MAX OPTIMIZATION
Theorem D.S. Let X R be an L-Lipschitz, t-smooth function and X be compact convex sets with Euclidean diameters Dx, Dy respectively. Further, assume that f(r.9) v) satisfies the pPL condition with modulus pa for all y & y while (x, satisfies the pPL condition with modulus My for any z E X. Additionally, let (gx. 9y) be an inexact stochastic gradient oracle satisfying assumption 3. Then, after T iterations of (Alt-GDA) with tuning of step-sizes
= To 160g
and 58' it holds true that:
(- Mufty T [160E3 L(Dx +D)) + G Pr
c cgl
c2l Pxlly
(*(TT) 4-
E (f(T, VT)) S exp
yr
where, C2 E (1).
Proof. Our goal is to ultimately demonstrate that there exists Lyapunov function, V,, whose value decreases along any trajectory of the algorithm's 's iterates. Not only so, but its value contracts, i.e., there exists 0 < w < such that V++1 I Vv, Vt. To demonstrate this, we first need to lower bound the descent on ((), lower bound the ascent on f(z,,) ) and finally upper bound the descent on (()
Descent Bound on (.). By Lemma B.9 and Lemma D.4 we write,
EC (141) & (D(x)) Tr ED +, Vaf(as,
+ 2 + 2T
Taka (T(x:) Φh) + F. (x),
< (0(a)))
3
2T 2
Hence,
E0(0++1 4² < (1 TzM2 (D(ar)) - x²) T 11y 1211?
+ 2T + 2T
TzMs
3 (T()))) Φh) ) + Tz nee//g//2 ( - f(2,,
+ 2 2 + 27,
(32)
or, also write,
E4(2.41) - -E(())) < Tzfla (1(I)) -²) + T, (4 - f(r,, v:))
3
2T, 33 2T
(33)
Ascent Bound on (() simple application Lemma B.9 yields,
Ef(z41 M++1) 2 (f(2 vo) + Ty Tu 1/Ty: TY57 o.
From which, we can also write,
(4(x441) - Bc+1)
< E4(()41) Ef(x(41,11)
Ty EDDy(uu (14)))1))))))))))))))))))))))))0 + T + o 6
43

---

Solving Zero-Sum Convex Markov Games
- <(1- MyTy (E+()++)) - Ef( (c)) + Ty + To
Ty
(E+((a)) - Ef vi) (f - Ef Ur) + (+((+))) - EΦ((),)
(34)
Upper bound the descent (() From (28) write,
Ef v0) 2 (1)
3Ta
11 |
9T.
0x
7Tx 5²
2
2
3 Dx((xee 1/Tx: V1)
9T.
7Ta 8
2 Bf(r))))))
0
(35)
2
2
The second inequality follows Lemma B.7. Now, (34) by plugging-in (33) and (35) reads,
Bd E [1++1, 2641) _
(Bo(z)) (z 91))
6
1 Py
(Bf( We) (x(+111,1,,)) W:))
(1 Ty
[E (ae+1) (x:))
+ 0 v + T
1 Ty
(xx) - Ef(xe,
Ty
3r. Dx( 1/Tx:
9T.
0²
7Tx
52
2
2
(1
Myyo Ty
Ta ED (zt, 1/7x)
T.
V (2xe)
+ 27 + 27m0²²
6
Ty y
+ T y
My Tv
(x,) - E.( Vc))
6
Ty
3Tz
Dx (It, 1/Tx:: Vc)
(1
Nyyo
Ts ED (xi, 1/Tx) + T. [V Vef( w0)l
6
Ty
To +7 7 (1- HyTy 02 + T T
+
7
(36)
6
The Lyapunov Function. proof:
We will consider the following Lyapunov function where or >> O is to be defined later along the
V(Ia, y1) == (x.) - )²) + a (T(xe) f(1,,
For convenience, with U, We we will denote the quantities:
U. = 4(xx) x*
W, = f(x,) fxr.
and we can then write V, = U, + aW, Piecing together (32), and (36)
U41 + aW+11 U, To ""ED" ED + E. - (xf(x,, U112
2T,02 2T,
44

---

Solving Zero-Sum Convex Markov Games
Ty
W₂
6
Py
3Tz
+
Dx( 1/Taitt)
6
2
+0
PyyTy
L2
ED (Tt, 1 1/Tx) + T2 V - Val(or.Bi)))
6
6
+a
(7(1-
MyTy
Tx 2 + 7 (1 1yyT
T + Ty + T
6
6
U0+ +
(1
My y
+ (1
MoTy
3rg
ED (ze, 1/Th)
6
6
2
To
+
[
MyTTy
E V (x,)
V Bx)
6
MyT
6
+a
Py
3
Dx [tt 1/ /a))))) - D 1/Tx]]
2
2 + 7a
1
My
Tz + (2+ + 7a (1- MuTY
T= + any + o
(37)
6
U.+ +
Ts
aTx
(1
My
+ a (1 MyyTy
3r.
( (zt, 1/Ta)
6
6
6
6
2
aTxx (1
HoTy)
26
+
T2
+
(ED(xx)
(x
6
PQG
(1
MyTy
+
W
6
+ +a
(1-
PV V
l
(B4(x;)) - Exx(, 2c))
MQG
+
2 + Ta
1
MyyTy
T + (2 + 7a (1 -_=TTe
)) T=o² + o + a
(38)
6
6
U2
1x
aT2
(1
NyTy
7y
3rz
) Up
1
2
6
6
2
(1
Myyy) ))
2 W₂
+
To
arx
6
PQG
MyTo
+a
W₂
6
9T 12
+ a
We
MQG
+ (2 + Ta (1
MyyTy
) T2O + (2 7a (1 -- )) T=oz + + +
(39)
6
In (37) we use the fact a < la bl + b with Dx([I, 1/22: v.), D& (22, 1/Tx) in order to remove the term Dx((,, 1/Txi vs) and introduce the terms Dx 1/Tx;01) - D (ax, 1/Tx) and D (1², 1/Ta);
In (38), we use the following facts:
1. (Dx v/) Dt (2,, 1/Ta]] S 362 1Ive y" (x=))) Lemma B.12;
2. [V. - Vef(z,, v2) < 6 fly1 y (2:)
3. MOG 1ive y" (z.))l < (xx)) - f(x,, quadratic growth condition of pPL functions Proposition C.5.
In (39) we use the fact that D (z, 1/Tx)) 2 UuU; (Lemma D.4) and the negativity of the coefficient of ED 1/T,), i.e. the display (- at.
6 (1 MyTy) + + (1 - ByTT)) (r=) To ensure negativity, we require that a < 1 and utilize the fact that par & and hence T2/2o S 1 by the choice of step-size.
45

---

Solving Zero-Sum Convex Markov Games
Summarizing:
(1 Tx
Tf
(1
My
U2+1 + aW241
Ur
3
m
11
11 PTTT
26
My +
1 1
W.
HQG
6PQ6
apQG
W2
+ 2 Ta (1- MyTT
T + (2 7a (1- MyyTy
Txo + atyoy + aT
6
6
Tuning the parameters: We need to ensure that 0 < w1, 12 < and then, we can show that the value of the Lyapunov function is contracting, iee. UL+1 + aW I max 11 32 (Ur + aW,) + &. We wiil now upper-bound W1, 022 For w we see that:
Tx
Tf (1
Taflz
T2 1
29
<
T2
6
3
30
For 2
2T 82
+ Tz (1
MyTT
26
(1
Py
9r l
6
OUQQ
6
PQG
PQQ
1
Tx
244
1
Py y
11
By
T
1 y
2
<
1
11
Byy
?2
TTa
M T2
<
1
31
My
TT
< 1
Pby
where we have used the fact that PQG is equal to By by Proposition C.5 and we require that 7 32. As such, we
To 328 and Ty 58- Further, We observe that P max
MTTo } since 2 pz: My. Combining
the pieces:
EV+1 & (1 MTTx) 3r, + 3r + T T
Applying the inequality recursively and using the formula for the sum of the geometric sequence, get,
30"
38
326
32
EV. S (1-11-100 (1-14TT
Vi
+
+
Px
30
352
320
32 82
S <exp Vo
Mapt
Pz
Further, we note that since f, & are L-Lipschitz continuous and their domains have bounded diameters, we can bound Vi as Vo < L (Dx + Dy). Finally, we see that by the choice of step-sizes Pa
#=
16027
46

---

Solving Zero-Sum Convex Markov Games
E. Convex Markov Games
Lemma E.1 (Continuity the occupancy measure). Let E A(S A B) be the occupancy measure a Markov game. Then is Lxpisschittz continuous and εx- -mssohhh with respect to the policy pair (z. y) E X V. Specifically, for all (z. y) and (x', ))
[A v) X(2' _ La (1 (2'.1/11: [V - VA(x' .0' lx (I,,,) - -1',
where Lx= (1A++8)) and la 2-/81 27/8/ 2111)-18111 (I-7)²
(1-7)
Moreover, consider the functions x7= A(S x A) + X and X2 A(S x B) + Y, such that:
\7 (A1 v))
X2 (N2(2, v)) = y.
For any fixed y (respectively, 2), X-1 Lx-r-Lipschitz continuous with respect to A1 (respectively, X2), i.e, for all X1 (x, u), d (z', respecciiillllyy 22(2, y), (2(r))'),
| 1'11 S 4x |AT (A1(z.)) (((c,y))-1( (A((E.)))A1(E'))))) (1 l - s s يا
| (12(1.)) A2(2. /)]l
with LX-1:= mint e(=)(1-7)
2
Proof. (Kalogiannis al., 2024, Lemmata C.2 & C.3).
Throughout, we will assume e-greedy parametrization of the policies, iee. the players play according policies:
s1
e1
nx = (1 - c)
and Ty (1 <)y +
[A
where 1 is the all-ones vector of appropriate dimension.
47

---

Solving Zero-Sum Convex Markov Games
E. Properties of the eMG Utility Fucntions
We reinstate that the utility function Lu- Le-Lisschitz continuous and Em-smooth with,
LF S (1A BB)
(1 7)2 to 2 S (IA] + [B]
LU
(1-7)3
E.I. PROPERTIES OF CMGS WITH CONVEX UTILITIES
For the two-player zero-sum cMG with merely concave utilites, we consider the regularized utility function ("( y) == U(r,y) + [22(1, w)ll". We note that that an upper bound to the Lipschitz smoothness moduli of UH, VUA is given by L.
SF|S (IA)+ + (11)
Ey 41 (IAI + |B1)*
- 2
(1-
(1-7)8
Let us now compute the moduli of the quadratic growth and pPL condition,
(min, ((s)) - 2
(min, e(x)) -1))
PQG
4
PPL
2 (IA) + |B8)*
Since the quantity HoGHPr, will frequently appear in our calculations, we write:
(min,
- (1-)))(1-7)14 / (IA1 + [B])
HQGHPL
The condition number is defined as
VPQCHEL and is equal to:
1687>~1818 (1A)) (
(min, e(s)) 15
Finally, we define function o" == max Ui" v) and observe for its Lipschitz modulus, Li. and its gradient's Lipschitz modulus, t/.
Lp|S| (]A] + +18)) T 1 (1 76
5126 S 28 (1A1 + B
26
(1 - 23) o(s))
E. PROPERTIES OF CMGS WITH STRONGLY CONCAVE UTILITIES
We carry over the same calculations for the eMG with strongly concave utilities. Since we do not perturb the utilities, the relevant Lipschitz moduli remain the same. This is not the case for PQG, MPL. We write:
(min, e(s)) 7)2ku
(min, (())) - T2
PQG
/PL.
4
46pr|S11 (IA)) + 1B))
Further, = Ey which is equal to:
4 20 |8 (IA) + +B1)
(min, (1 - 7) 2
Finally, the Lipschitz modulus of Φ and its gradient will be:
Lg = Lu - LF(8|} (1A4) [B])
Ey 16 (1 1B)
21
(min, (1)))3(1--) =
48

---

Solving Zero-Sum Convex Markov Games
E.2. Stochastic Estimators
Using trajectory : , of A2.
(0) ,00),,, (1)) ,...) and { (s0)),(()) ((0)
b(0) 600 b,,,.., ,...) respectively, we define the estimates
Hg
A4 =
A "( =s,a! =a
k=1
2
(1(0( = =s,b(h) = -b..
Additionally, for pseudo-reward vector z E R S|x and g = (s(0), al s(2), ,a(2) ,...) )...) E R[ correspond-
ingly and & == (s(0), ((0), s(1) ((1)
we define gradient estimates 1x V u.gi
9o (E yc. 2)
h (h) ,a!i)).
v log x (a (s(0())))))
h=0
0u(E|0t, Ve,
M2 (b))),))))
V. y log y (B00))000)
4'=0
At every iteration t, each agent constructs Pzze Vx, F(r,t) describe how to construct Pr, Fy batch versions of the latter estimators will be,
Mr In (Silae ye, Pa.e) Σ
and 4 >
(e Me, Py.e).
(40)
Now, for each one of the two cases we let 2 +- V,, F (1 and + V F (21.: Us correspondingly.
Remark 4. This stochastic gradient estimator assumes access to gradient oracle for Vx, F. Access to oracle for F or F is an assumption made in virtually all the references that we have encountered concerning policy gradient methods for MDPs with general utilities (Zhang et al., 2020; 2021; Barakat et al., 2023). Designing a gradient estimator that entirely relies on samples lies well-beyond the scope of our paper. Nevertheless, this assumption is not strong one as even with a complete knowledge of F, agents cannot control the function's arguments except for affecting them implicitly.
The occupancy measure estimator
Let trajectory sample & of length Hg, we define the occupancy estimator for player
1 to be,
He (9) = Σ
> A1(0(1) =, = =a}
A=1
Ms
(5) Σ
*hh A1{s(1) s,6(1) b}
Assume policies Fe, y/ and corresponding sampled trajectories {Er. 1 and (8 for player and 2 correspondingly. The occupancy batch estimators dι,t 'i,t
Mr
dex 1 M, (z(S).
d1, = M₁
(Ea)))
M
H
h 1 ((s =s a at IP (1( B(h) s((h)) (0.0)
1.8 (I. v) = -Ez.y
hm
49

---

Solving Zero-Sum Convex Markov Games
2 (x, v) = Be
A 11s((h) - =s = P (stht1) (h)) (a()) b(h) s(ui) (s10)
Lemma E.2. Let empirical estimate d1 of the truncated-horizet occupancy measure X, Then, the variance of the estimate can be bounded as:
|| - A1,
1 Ma(1 - 7)
The policy gradient estimator Assuming e-greedy parametrization to control the variance of our estimators, we can go forward and state our main lemmata regarding the gradient policy gradient estimator's variances.
Lemma E.3. Let Vt be defined as in (40). The estimators variance can be bounded as:
|
27L7
E
V. V S M1 =2
Proof. We essentially carry the computation as Step 2 in the proof of (Zhang et al., 2021))Lemma F.2] using our notation and assumptions. To simplify the excessively busy notation and improve readability, let us introduce some shortcuts,
A = (11,
\ d1.
r = Vx,F (2., = VA, F (Ari
= VI Me) = V211.
f: = Vx, F V).:
= v.F F (AI, ve) = F (A1:
9. å= (5. (1,, f),
9G.- = (c Vc: r-).
We finally write:
M,
M
E 1
JT
J
=
g1, Ma _
g1x g + g J
M
M
M
3E
0. g1.z
+ 3E
9 J T f0
+ 3E
G1.-
M
Mr
For the first term we write,
M
27
1
M
2
E
Σ
Di.0)
|
-i.-
M
M
4
E
||2
112
(1 7
4L3
| X
E
(41)
(1 7)462
AT.3.
M2 (1 6E2
50

---

Solving Zero-Sum Convex Markov Games
Where (41) follows from the following fact:
6 -r2(s)))))))) (E2
V log (a(((lb)))
(0(E) r()lx,
(t + 1)]l - r2lloo
E
2 2||r r2l
(1 - -1-7)3
The second and third terms can be similarly bounded as:
1
E
J
P:
<
M₂ 7)11
and
M2
4L2
Dr..
<
M
Mz - 768
Lemma E.4. For any H> 1 of the policy gradient estimator defined in Equation (40):
Tn(i-ar and a greedy exploration parameter e, the following inequality holds true for the bias
256LF I (2F((N(E,)):)) N V2 (1 7002
exp
Proof. By (Zhang et al., 2021, Lemma E.3), we have that,
( 8L7 L2
( +11
(1 (1-1))) 7mm
1
)
(V Va (E
( -11-90 6) 7622
+
g²
((1
Further, we can bound the RHS as:
SL (1 - 62
L ?²
(H (H+ + 1)2
(1 - 1- 1) 72
1
)
256 +12
16
211
(1 7)2
(1 - 7)
Now, in order to simplify the display, compute an H >> 0 such that:
(H + 1)2
(1/>) $
equivalently,
2 2og
(H + +1) S H +1
changing the base of the logarithm, we get,
ln11 In H 1) S H +1,
but the latter is true for any H + hmlmm//////////// V7). Hence, since < and noting that 7 1 - (1 (1- -1-)),
256L (H + 1
28 <
256LF (1 0g2
7 #11 <
256LF
exp (-11-2)(H-1)) -1) -1))
2)22
(1 eg2
51

---

Solving Zero-Sum Convex Markov Games
E.3. Additional Supporting Claims
In this subsection we bound the errors incurred due the e-greedy parametrization, and the regularization.
Error due to e-greedy parametrization.
Claim E.5. Assume I--Lipschitz continuous function : -> IR. Further, let X be concatenation of n m-dimensional probability simplices. Further let w be the mapping w(x) == (1 =) + for some 0 < < <<<L 1.
1f(z) - (f 2 VnLe
Further, for some and X,
-f Sc.
then
(fow)(w) 1 s VūLe
m
The second follows directly.
Proof. The claim follows from the Lipschitz continuity of f. It the case that w)) = f((1 - -) + t/m),
1f(x) f((1 =)x + =/m)) s L ||
((1 E)x + e/m)]
VnLE
<
Claim E.6. Let L-Lipschitz continuous function : X x ) - R. Let X, be concatenations of and ny mz- and my-dingg dimensinnaa probability simplices respectively. Further let w be the mupping w(a;e, ;= (1 (1=s)æ e/m for some 0 < e <. 1. Further, for some Ex, > 0 define fw(x,y) == (w(r; Ez, ma), wry, my)), (.r == maxyey (w v), and 4 = min (T). Then, the following inequalities hold true,
(x:) (xx) S Lez Ley
vie
my
10- 1+1 <
+
LTy
m.
my
Proof. The proof of the first item directly follows from an application of Claim E.5 and the I--Lppshitz continuity of given that f L-Lipschitz continuous.
For the second item, the incquality just attained and write,
La
VnyLEy
$ (x) (xx)
mg
my
Minimizing over & for the sides yields,
v TTyLey
+ n (xx)) S (xx")
my
my
Where, x" are such that x" E arg min xx (xx) and oi E arg min ne (x). Applying the same trick to the other side of the other direction of the inequality:
+ VTyLEy
((x*)= < (x
ma
my
As such,
+ Thy
(x=*))
mg
my
52

---

Solving Zero-Sum Convex Markov Games
Claim E.7. Assume an L-Lipschitz continuous and E-smooth function J X - R that is p-pPl. Further, let X be concatenation of m-dimenssinnal probability simplices. Further let w be the mapping w(x) = (1 e)ar + e/m m for some O<E<L Define D (x, a). x (x. (x) for some a > to be:
(x) a)) -2a min VE { (V x) || u1l²}
Dx fm (Ta, - 2x min
(V]om(()). x) + a | u1(
VE
2
Then, it is the case that:
D few (x, 2()())) -VneLaDxE.
2
Proof. We essentially need to prove that fact:
D ()) (2, S 116/itlaDxs.
We write (x, a) equivalently as:
(2, max yEA
22x (Vf(x), a² 1| y1²)
We define G(::)) after we isolate the display inside the max-operator and in place of the gradient put any vector of the same dimension:
G(u: v) == 2a (v,z v) a² || -yll
We see that V V.G((; = 2a(x 1 y) and || - yl S Dx. As such, G is 2ad x-ipschit continuous in v. This consequently means that (v) = max G(u:y) v) is also 2xDxx-.ipschitz in v. Now, all that is left to do is to bound the distance between (f o (x) and V.f(x). By the chain rule:
(1-c)) ==m(aa)
Further, ve w(x) and observe that
[[V=f(x) v=+((=))l - f xell
= E {|æ (1 - E)x e/mll
|lex - =//mll
I le(Vī + 1/m).
Where in the last inequality we use the fact that for a probability vector y. ||v|| $ 1 and the triangle inequality. Assuming that n. m 1, can further simplify into:
[+f(()) vef(=z)) S ///
(42)
Now, by the fact that & (VVx(x)) = uf D.oo (x, a). and the Lipschitz continuity of v, we write:
| a) - -
(z, a))
s 20Dx (f - v=)(2))
s 2nDx [=]((> V=s(xt))l 2nDx (x.))
< AVilaxx + 2aDxeL
s 16vzeLaDxe.
The claim follows.
53

---

Solving Zero-Sum Convex Markov Games
Claim E.8. Assume an L-Lipschitz continuous and E-smooth funcctionn f X IR such that:
max x' d'Ex.]Iz-<'1s (Vaf()),x-1") (f(x) f*).
Further, let X be a concatenation of n m-dimmensional probability simplices. Further let w be the mapping w(x) == E) e/m for some 0 < E 1. It is the true that:
(Vol w)(x), x- - -x)) ()((() -f) - -VTELLDEE.
max s' s'EN 22-1-11
Proof. Similar to the previous case, we need to show that G(e,x') == (v,x- - x²) is Lipschitz continuous in v. Indeed, V,G(u; := x x' and as such [V, x')l & Dx. Consequently, (()) == max,'ex' G(u; x') is also Dx-Lipschit continuous. Further, as previously shown (42),
[Vz((>) - vas(+e)l & 2/nle
We can finally write,
max 2'EX x [s1 [V(Jow),, x²) 2 x'Ex.||a->
(VaJ x²) -VrlLDxe
max
Error due to the regularizer.
Claim E.9. Let two-player zero-sum eMG with utility U X y R. Assume that the maximizing player employs regularization to their utility of the form:
U.ro (I,y) = (xx,))
Mrng.
[2)(2,))1?
2
where Preg. > O. Then, the following inequality is true:
V V.U"(E,))l S Mrog. ||xl
Proof.
[| v) V2U"(2, v)1l Mseg. V2d2(1 y)ll
prog. D ll V/ (2
Uzeg LA.
E.4. Nested Policy Gradient
E.4.1. CMG WITH CONCAVE UTILITIES
Theorem E.10. Assume awo-player zero-sum eMG and desried accuracy 0. Running Algorithm tuning of Algorithm I with, preg.
= (1-7)(min, o(o))s L.
and,
step-sizes, T = (min, # (1))) e 8
(1 (1-g)²
and Ty =
41 (1A|+(8))
S12 ( and E, = <(min, o(e)) 2 (1-)) 2
<(min, u²
exploration parameters Eg
à 2 (1A1_115))
54

---

Solving Zero-Sum Convex Markov Games
(L batch-sizes Ms θ
c (11 (min, (10)))011-7))
(miin, e(s))*11~3)z and My = θ
outer-loop number of iterations at least T. = + Lyt 2 t (IAI+ BI) +
and inner loop iterations that are at least
(1-3) (min, 2(s)) 4,7
Ty = ( (f (1L In (LLL4))5((A)4111 (min, e(*){[1-)}
[min, ((5))(1->))
will output an iterate Zr y such that:
E
U ( min U('', -1++1) x'EX
S
E
max U (2,,, EU (I,,, yrr) vEy
c.
Proof. In order simplify our arguments, formalize e-greedy parametrization composition of the utility function Uzz y) with mappings w(2; E, m) where w(x) -))x s1/m. In particular, our convergence guarantees are w.r.t. the function ()) = Uh (wi(r; [l), w(y; Evz (B)) and ((x) maxyey UK (2,
We will tune T2, T2, Hz, Szy Ma. by, Theorem D.5.
T
a || x
5lggDDx + 65 + M, (1 7
1 4L2
First, we see that in order to achieve an e-approximate best-response w.r.t. to æ, then, needs to be an (1 (1)7)min, @())e- approximate stationary point. general, then, we need to ensure that,
- (1 ()) (min
(min e(s))
Hence, by Claim E.9, we can pick the regulizer's coefficient to be:
( (1 (1->)(mm) (min, e(s))e
Preg. = +
LF
Lemma E.4 dictates the tuning of Ha, Hy,
0 In
(EpLF)/8((AA) + [B])
<(1 - 7)min, e($) ))
Hg Hy = O 1-
Further,
c 0 (1- (1--7) (min, e(s))e =
emin, e(s) (1 - -7))12
p1ppp
2LpFF 3 + |B))
(1-7)²
=
EptELA =
1
11m> (1 |B1
0. S (1AI+ 1B))
(min e(s)) - 30
M, 0 11P71117 (1A) + 1B)
(ming (1s)) 7)32
55

---

Solving Zero-Sum Convex Markov Games
As for the inner-loop, we need to set
[ - (min, e(s)) =
min, ((s) (1- 2
Cy = 0
20%
17 + B1)3
and hence,
Ey= = (nQo(1-2)26 (min e(s))
min, e(s) -0)
=
Lu S
[S) ((AA) + [B1)
Now, we are ready to tune the number of inner-loop iterations, Ty,
ty L (LAI 181)* -
(erLryls) (|A]](AA))))) + [ (min, e(8)) -7)
(min, -(8))9(1-7)44
and the batch-size, My. to be:
A 1 10 (1A) 1B)
M, 0
(min, 0(5)) 52
Finally,
T. Lp Lp 20 (IA + BB] +
7)
26 (min, e(s)) 4
E.4.2. CMG WITH STRONGLY-CONCANN UTILITIES
Theorem E.11. Assume a two-player zero-sum cMG with utilities that are strongly concave with modulie μr: p2 0. Let 0 be given. Then, a tuning of Algorithm with,
step-sizes, Tu = (min, e(s)) pi
(111111 and Ty = 26r7|812 (1-()())((A(++111)
(1-7)²
exploration parameters Ex = <(min, =(=)) and Ey = <(mmn, ((=))) (1-7) 7
(1A1-18))))
14 ( D3. 47 (1 4
batch-sizes M,, O an outer-loop number of iterations at least Ts O
and M, = 0
Amin, e(x)) (1-7) 47
?(min, e(x)) "3,00)")"
[10/2/5) 7 and inner loop iterations that are at
min, e(s)" m2 (1 (1-7)
least T. = 2 [min, (1))) D
will output an iterate It, Ye., such that:
E
U Ule 31441)
min U(I',yer4) x'eX
(e-+1) Sc:
E
max U(r,,y)) (U( Se.
vEy
Proof. An optimality gap (2 - < for the utility function that is composed with the greedy exploration mapping, translates to an optimality error of the original utility function:
|S]
Locr
| + & Dxex.
(x(411) Tb' sct
+
A
B
56

---

Solving Zero-Sum Convex Markov Games
First, we can set the number of iterations to be at least,
[plln|8) ((A) (B)) (min, (( - 7)
16V2|S| (IA1) + (B)) 3
T3 0
min, o(s) uui (1 - -))
As such, we tune the exploration parameter En to be:
c | s|D)
AAke
min
So we can set, Ex | Lx
Substituting yields:
[((min, e( (1 (1-7) 1 (A + [B) "
[_(min, 0(5)) (1 77)
Eg
6 55 (IA) + |B))
27 | [ 7 27 [|A|+1B1) 39
M2 0
emiin 19 (1 11-7) 4
In order to tune 8g, we see that it is sum of two terms, the bias of the gradient estimator and the expected distance of z/ from (x+) at each iterate t. We see that we need to set,
Further, we require that Eg < min
18|c
[s] Lo
E3 Dy
8, S Vagaa
Vta
for some constant sufficiently small. As such, will control the horizon of the stochastic gradient estimator, Hz, to be,
H₂ 0 (1-
c(1 (
(1pLF>|8) ( 181) ) 7)mn (mm-->)min e(s) ))
For the inner loop, we need to ensure that E [1y y² (ax)) < the optimality gap of the inner loop, ey. needs be bounded as:
L/pplat vix
Hence, by the quadratic growth condition w.r.t. y.
(((min, (1-)))41222 { ( (IAI + [B8)
Ey = θ (SHpl.rtaaa.
To achieve such an optimality gap at the inner-loop every outer-loop iteration f, by Claim E.5, need to set Ey Ppplee
(<(min, e pu (1 -7) #
Ey -
1 (IAA) + (
the latter leads to the bound on oy
3 (|A1 + 1B1)
0f
2 e(s)) 18 |6 (1 2)
while, the previous bound calls for batch-size,
1 (|A) + |B)) 4
My -
2minn, e(s)) 22 3 (1 - 7)
57

---

Solving Zero-Sum Convex Markov Games
Finally, the horizon of the inner-loop gradient estimator will be to be:
H = (1 1-
c(1 - min, g(s) p(s)HPLHHy) )
Ep EpTr (IA1) (B1)
In
while the step-size needs
1
117)3 2 (IA) + (B)
Ty =
and the total number of iterations needs be at least,
tu In
(2Lpep|S (3)
Ty -
Hpl.y
min, ((s) 7)
2 (IAI+ )
-
(ming -1))
E.5. Alternating Policy Gradient Descent-Ascent
E.5.1. CMG WITH CONCAVE UTILITIES
((A)))1)) (1- (1-7)""((mnn)) e()))
Theorem E.12. Let a desired uccuracy. After at most =
iterations of Algorithm 2,
with step-sizes, Ta = - (unin, (1)))) and Ty =
(1-7)"
48py?1S) (1A)+181)
exploration parameters & θ
min, p(s) (1 (1 and Ey =
min, p(s)(1=1))
2hrer
16L |S| (1
batch-sizes, Ma. = O 1S ((A(+1))))) and M,, -
[S1 (1A++181)
[min, (1-))=
[min, (1-))"
sampling horizons Ha, as Hy 0 ( In (1-7)(min, e(+))c
there exists an iterate t*, such that
IEU (xt+ 1/-)) 4- S EΦ((.)) - EU((, y1r) S c.
Proof. We invoke Theorem D.7 and tune the parameters appropriately using Lemma E.4 and claims E.5 and E.6. We tune the coefficient of the regularizer first. Needing to achieve an (1 - (min, e-s))t-first order stationary point, we tune the regularizer as:
( e(s))c
Preg. +
L.
We compute the pPL modulus given the regularizer tuning.
MPL = (min, (1 262
( (IA4) + 1B])*
Further, by claims E.6 to E.8, we see that Ez, Ey need to be tuned as,
Eg = @ (1 (min, e(s))e) =
emin, e(s) (1 72 2L (|A5 +1
58

---

Solving Zero-Sum Convex Markov Games
and
min, e(s) 2
Ey =
16LF |8 4 1 + |B))
The resulting bounds the variance are:
0 1 (IA1) + [88) "1
(min,, e(s)) 7)
and
o = 1614 |S| Mg) 8 2B))
min; g(s) 52222
The latter dictates the batch-sizes,
M2 = + S (14) + [B]) 11
<(min, ((s)) - 3/22
and
(1 =
14 22 (1.11 + (B)) (min, e(s)) 7)85
My 0 =0
(min, (
The step-size tuned straightforwardly as,
(mingg e(s)) - () 23
Ta O
17-55113 (1.4) [B]) 1
By Lemma E.4 we easily that H,, Hy need to be.
H Hy - (1 In 1tpLr|8|(14) + [B) (1-7)(min) e(s))e
After we have tuned the regularizer, we can compute the upper bound on the number of iterations:
T= 1 (IA 1B)
(1 40 115)
Now, tuning By is also straightforward,
1r (Fee (1-2/))==0 =0
(1 (1-788
Ty
0
S5 (1AA) 18))
E.5.2. cMG WITH STRONGLY-CONCAVF UTILITIES
Theorem E.13. Assume > O and a two-player zero-sum cMG with utilities that are strongly concave with moduli μ4: P2- Then if the two players are following Algorithm 2 with
[(mmin, (1=))) min (x2.n2) mmin 4Lr(111833+P((A1118))
exploration parameters Ex, Ey
step-sizes, Tz = (min, (1-)))(1-7)30)
321|1|1|[[|+ Ty. = 26 8 [1AI+151)
(1 (1-7)²
and
59

---

Solving Zero-Sum Convex Markov Games
16L 7
16L 2 (1))
batch-sizes, Ma = then, is the case that:
My - (mmi,, o(=))=*(1-)) ( m
(min, (1-))) (
EU (xT, (r) 4- Ss
Ed (Φ(2r) EU (TT, yr)
after most iterations, with T = =
48 is (1A)+ log min, e(s) (1 (1-7)"
[111)1)(((4)))11 (min, (13)(11)))
Assume the function (zz v) U (w(x; Ex, [l), w(y: Eg. [B)) where w(2 E, m) (1 - E)2 + claims E.6 and E.7 make sure that we can bound the optimality gap on the initial function U by running Algorithm 2 on U. Hence, combining the aforementioned claims with Theorem D.8 and Lemma E.3, we see that we need to set:
<(mmin, e())) (1 - 7) min (m2 :1))
Ex. Ey =
|1.1 (I.A) + (B1) (Dxx + Dy)
The resulting variances will be:
16L (1.4) + |B])* (Dx + Dy)² (min, ((s)) (1 - 70 min f p&)
02 =
We will control the resulting variances using batches the following size, which will also counter the μ
1 ((4) + (B])
Ma =
(miin e(s)) 7) 42 min (00.10)
167./// 10 - (IA)) + 1B))
My θ
2² (min, ((s)) 28 (1 7) 50
min { {M21 m0
We can easily see that the sampling horizons need to be:
H₂, Hy = (1 1-7
In EpLry111 (1A1) + 181)
E(1 - m)mn, (
The step-sizes are tuned to be:
1²,1 (ming e(s))5(1 77)00
(1 - 71)
To
21 (I.A) + [B]
; Ty 20 (IA4) + (B))
Finally, the iteration complexity is at least:
46p 6 (IA) + [8]
L (IA)+ [B])
T T=
log (min, 0(s))(1 - 7)H1, P2.8
min, e(s)22 7) 2 11.2
60


Reviews:
[{"review_id": "PK8s9UlXvg", "reviewer": "Reviewer_9QVE", "summary": "The paper studies convergence of policy gradient methods in zero-sum convex Markov games, giving the first convergence result to $\\epsilon$-Nash equilibria for such games. The approach uses the inherent hidden convex-concave structure present with respect to the occupancy measures. This structure is formalized the proximal PL condition, and is connected with other known assumptions such as quadratic growth. With the hidden structure and added regularization, two general policy gradient methods are studied, double loop nested PG method and alternating gradient descent-ascent method.\nComplexity analysis is thoroughly given in the general context, min-max with hidden structure, and then linked back to the problem of convex zero-sum Markov games.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive reception of our work and recognizing the technicality and contributions of our paper. Allow us to address your concerns.\n\n\n## Policy gradient terminology\n\n* Given that literature labels as \"policy gradient methods\" most algorithms that use a gradient wrt the policy in order to maximize, we believe that we are not abusing the term. \n\n* Indeed, as we point out in lines 76-100 left col., simply running a directly paramatrized policy gradient descent ascent, would not work. For this purpose we use alteration in gradient updates and regularization that is ubiquituous in optimization.\n\n## The the tuning of the bias $\\delta_x, \\delta_y$:\n\nWe are glad you bring up this detail we overlooked clarifying. Checking the formal statements of our theorems, it should be apparent how convergence depends on these quantities. Namely, the $\\delta$'s dictate the accuracy that is possible to get in terms of stationarity and duality gap (for convex and strongly convex utilities respectively).\n\nFor the particular case of Alt-PGA and Nest-PG:\n\n* $\\delta_y$ is merely the sampling bias of estimating the gradients by picking trajectory samples of fixed deterministic horizon, $H$. Yet, $\\delta_y$ decays exponentially with $H$.\n\n* $\\delta_x$ suffers from the same sampling bias **plus** the fact that player $1$ does not have access to the precise gradient of the regularized function. I.e., player $1$ can only estimate the gradient of the un-regularized function and suffer an error that is *bounded by the regularization coefficient's size times the upper bound of the regularizer's gradient norm*, in which case is the regularizer's Lipschitz modulus,  i.e.,\n\n$$\\delta_x \\leq O(\\exp(-H)) + \\mu_{\\mathrm{reg}} L_{\\mathrm{reg}}.$$\n\nFor this reason we tune the regualrizers coefficient as $O\\left(\\frac{\\epsilon}{L_{\\mathrm{reg.}}}\\right)$.\n\n\n## Further Notes\n\n* What we meant to say is that the BR-mapping maps to a set of policies that is convex.\n\n* Lipschitz modulus in Lemma 2.5:\n\n  (i) $\\mathcal{D}_{\\mathcal{U}}$ is the Euclidean diameter of the state-action occupancy measure. Since it is a simplex, the diameter is $\\sqrt{2}$.\n\n  (ii) Then, $\\mu_c$ is the inverse of the Lipschitz modulus of the transform from occupancy measures to policies and it is bounded by $\\frac{2}{(1-\\gamma \\min_{s})\\rho(s) }$. [1; Lemma C.3]\n\n---\n\nThank you,\n\nPlease let us know in case you have further concerns.\n\n---\n\n[1] Kalogiannis, F., Yan, J. and Panageas, I., 2024. Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem. NeurIPS 2024.", "claims_and_evidence": "Claims are mostly theoretical, see the appropriate section below.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "The theoretical claims seem reasonable. I was not able to check all the claims in the paper. I do have some questions on some of the results that are not clear.\n\n## Lemma 2.5\nIn Lemma 2.5 it is unclear how the constants $\\mu_c, D_{\\mathcal{U}}$ in Proposition 2.4 correspond to the constants in Lemma 2.5 where the proposition is applied. Is there an assumption missing? maybe one needs to apply claim 2.3? More precisely, where does constant $\\frac{(1-\\gamma)\\min_s{\\rho(s)}}{2\\sqrt{2}}$ come from in Lemma 2.5?\n\n## The the tuning of the bias $\\delta_x, \\delta_y$\n\nThe first order stochastic oracle model from line 325 specified potential systematic error (bias) in the gradients, however it is unclear how this irreducible bias is present in the results within the main paper. For example Theorems 3.1-3.4 specify tuning for stepsizes and batchsizes without mentioning how the bias error affects the convergence. Looking at the appendix it is mentioned that this bias needs to be tuned (e.g. line 1908). As expected there should be an neighbourhood of convergence that depends on this $\\delta$ if it is not tuned. If tuned this should be stated in the main body of the paper, i.e. what upper bound is needed on the bias to attain the complexity guarantees presented in the paper similar to how the stepsizes and batchsizes are picked.", "experimental_designs_or_analyses": "The experiment  used to test the theory is limited to a toy repeated RPS example. However, due to the theoretical focus of the paper this is a minor point.", "relation_to_broader_scientific_literature": "The paper seems to be well placed within the broader scientific literature. It is much appreciated the effort that the authors have done through to connect results to the general optimization literature. There can be some more references included to better complete background and make the paper more approachable. For example, references for the proximal PL condition and Quadratic growth would be helpful. I believe the proximal PL condition is defined in:\nKarimi, H., Nutini, J., & Schmidt, M. (2016, September). Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition. In Joint European conference on machine learning and knowledge discovery in databases (pp. 795-811). Cham: Springer International Publishing.\n\nThe approach also seems related to the idea of Nesterov smoothing, especially for the nested GD method, where a min-max problem can be turned into a smooth convex problem if you smooth out the best response of the max player. Some discussion in connection to this technique could be helpful/insightful.", "essential_references_not_discussed": "Due to the relatively new setting of convex Markov games, I am not aware of essential references that should be included.", "other_strengths_and_weaknesses": "Strengths\nThe paper makes some fundamental observations regarding the structure of convex Markov games in connections to well-known non-convex optimization concepts, and uses these general assumptions to provide new guarantees in a new class of hidden convex-concave games. These two main contributions seem both important in their own right, i.e. for understand convex Markov games, and understanding what is useful structure in hidden convex-concave problems.\n\nWeaknesses\nThe requirement of regularization seems to be a weakness albeit a minor one. It is well-known that regularization in games can utilized to establish convergence of gradient descent-ascent methods (i.e Nesterov smoothing, or entropy regularization in quantal response equilibria), however, I would not interpret those results giving an affirmative answer to whether policy gradient methods converge in min-max problems. I think most would agree that policy gradient methods can diverge or cycle in convex-concave games as it is assumed there is no additional curvature structure (i.e. regularization). Therefore I find the claim a bit strong to that the methods proposed in the paper show that policy gradient methods can converge in zero-sum convex Markov games.", "other_comments_or_suggestions": "- what does it mean for the BR mapping to be convex? isn't this a set valued mapping?\n- Def 1 seems a bit off, the way it is written suggests that we are asking $F$ to be concave over the cross-product of occupancy measures? I think what is meant is that it is convex-concave? for example this would not hold in a matrix game e.g. x*y is convex/concave but not concave in $(x,y)$.\n- is Nest-PG the same as GDmax? Nest PG is only defined much later in section 4.1 after it is first referred to in earlier Theorems.\n- what is a $\\mu$-modulus transformation?(280)", "questions_for_authors": "1. In Lemma 2.5 it is unclear how the constants $\\mu_c, D_{\\mathcal{U}}$ in Proposition 2.4 correspond to the constants in Lemma 2.5 where the proposition is applied. Is there an assumption missing? maybe one needs to apply claim 2.3? More precisely, where does constant $\\frac{(1-\\gamma)\\min_s{\\rho(s)}}{2\\sqrt{2}}$ come from in Lemma 2.5?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ilPXQBnTC6", "reviewer": "Reviewer_4bBk", "summary": "This paper addresses global convergence to Nash equilibria in two-player zero-sum convex Markov games (cMGs)—a recently introduced framework generalizing Markov decision processes by allowing convex utilities over occupancy measures. The main contribution is proving that independent policy gradient algorithms, with a specialized regularization for stability, converge to ϵ-Nash equilibria in polynomial time. The authors present two methods—Nested Policy Gradient (Nest-PG) and Alternating Policy Gradient Descent-Ascent (Alt-PGDA)—and provide both theoretical guarantees and a simple empirical demonstration on an iterated Rock-Paper-Scissors gam", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive reception of the paper. We are glad that you recognize our technical contributions that we deem important in broadening our understanding of multi-agent RL and nonconvex optimization. \n\nRegarding your question **''Do you anticipate straightforward extensions to general-sum cMGs or more than two players?''**,\nthe initial paper [1] defining the setting, in fact defines cMGs for any number of agents and general utilities. So yes, there is a straightforward extension. A very interesting avenue of future work is finding nontrivial families of games where equilibrium computation is computationally feasible.\n\nAgain, thank you and let us know if you have further concerns that we could address.\n\n[1] Gemp I, Haupt A, Marris L, Liu S, Piliouras G. Convex Markov Games: A Framework for Creativity, Imitation, Fairness, and Safety in Multiagent Learning.", "claims_and_evidence": "Key claims: (1) These are the first algorithms with global convergence guarantees for zero-sum cMGs, and (2) the proposed regularization induces a structure (proximal PL) that stabilizes independent learning. The paper offers solid theoretical proofs (theorem 4.3-4.5 and 4.1 respectively) and an experiment showing that exploitability decreases as expected.", "methods_and_evaluation_criteria": "The authors use policy gradient with a custom occupancy-based regularization to ensure smooth best responses. The design is coherent with the cMG problem structure and empirical success of PG based methods. The evaluation focuses on reaching \nϵ-Nash equilibrium and analyzing the iteration/sample complexity, which matches common MARL metrics.", "theoretical_claims": "The authors prove that, under regularization, best responses become Lipschitz in opponent policies. They then establish convergence to ϵ-Nash equilibria via proximal PL arguments. The proofs look consistent and are comparable to known gradient-based results under nonconvex–nonconcave settings.", "experimental_designs_or_analyses": "The single experiment on iterated RPS is limited but indicative. It confirms the predicted behavior: with regularization, exploitability drops and remains near a small positive threshold determined by the regularization parameter.", "relation_to_broader_scientific_literature": "The paper's main contribution theoretically supports the empirical success of PG based methods in MARL literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The presentation is clear and easy to follow. Though I am not very familiar with this topic, the structure, starting with basics to their contribution guided me smoothly to the main point of this paper.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Do you anticipate straightforward extensions to general-sum cMGs or more than two players?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VzsjRf7xjt", "reviewer": "Reviewer_Jsh5", "summary": "The paper studies two-player zero-sum convex Markov games and considers a regularization-based policy gradient approach for finding the Nash equilibrium. Two algorithms are proposed, and their complexity are provided.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your time and effort in reviewing the paper and pointing out this mistake in our bibliography. We apologize for our negligent mistake, thankfully, the wrong LLM-generated bib items are limited to the related work sec of Appendix B. As we clarified to the AC, all hallucinated references correspond to real citations. We were able to communicate a list of them to the AC but due to space constraints we cannot include them here.\n\nBefore proceeding to address your concerns, we want to point out that our contributions are the following:\n* Designing finite-time finite-sample algorithms that converge to saddle-points in constrained nonconvex-pPL, pPL-pPL objectives (Sec 3).\n* Using the latter to design policy gradient algorithms that converge to Nash equilibria (NE) in cMGs (Sec. 4).\n* Our work is theoretical but our numerical experiments strengthen our claims. Although RPS is initially \"linear\", after regularization it is no different than a generic cMG.\n\n*We do not claim* to be (i) coining the proximal-PL condition, neither that (ii) formulating the NE as a min-max optimization problem is our contribution.\n\nLet us elaborate on two points that we think are critical in demonstrating the technical hurdles we needed to overcome.\n\n## Bellman equations invalid\n\nAs pointed out in convex MDP literature, the Bellman equations, ($V(s) = \\max_{a}\\[ r(s,a) + \\gamma \\mathbb{E}_{s'} P(s'|s,a)V \\] $) , fail to hold. This is due to the non-additivity of rewards. The total utility is a convex function wrt the occupancy measure and value is not generally defined state-wise (e.g. the entropy of the state occupancy measure). See, e.g., introduction of [Zhang et. al, 2020, Intro - 3rd paragraph ]. The original contraction argument of (Shapley 53) which subsumes additivity cannot work. All these rule out the possibility that some value-iteration scheme can work.\n\n## From unconstrained to constrained AGDA\n\nWe needed substantial work to extend to the constrained case. It is not always true that incorporating a projection step does not require significant modification of the proof. One might get that idea when comparing the proof of convergence of gradient descent (GD) vs. projected-GD in nonconvex smooth optimization. Two facts make the latter straightforward for nonconvex smooth minimization case: (1) the Lyapunov function used to prove convergence is merely the objective function itself and the (2) the projection operator is 1-Lipschitz continuous.\n\nNonetheless, in proving convergence of alternating gradient descent ascent for the challenging min-max objective, the Lyapunov function is a weighted sum of the two individual optimality gaps.\n\nFor the unconstrained case [1,2], proving that the Lyapunov function progressively decreases revolves around manipulating the quantities $\\nabla_x f(x,y), \\nabla_x \\Phi(x),$ and $\\nabla_x f(x,y)$. These quantities are very easy to work with due to their Lipschitz continuity which follows from the assumptions.\n\nIn the constrained case, proving progressive decrease in the Lyapunov function requires working with the gradient mapping $\\| x - \\Pi(x - \\eta \\nabla_x f(x,y)\\|$ and the quantities $D_{X}^f, {D}_{X}^{\\Phi}, D_Y$. The same assumptions that we make in the unconstrained case, do not make it easy to appropriately manipulate these quantities in order to show convergence.\n\nWithout diving deeper, it is not obvious for example why $D_{\\mathcal{X}}(x,a;y)$ should satisfy the following inequality,\n$$|D_{\\mathcal{X}}(x, a; y) − D_{\\mathcal{X}}(x, a; y)| ≤ 3\\ell^2 \\| y − y′\\|^2 ;$$\nespecially when it is defined as an optimization problem in itself: $$D_{\\mathcal{X}}(y,a;x) := -2a \\min_{y'} \\{ \\langle -\\nabla_y f(x,y) , y' - y \\rangle  + \\frac{a}{2}\\|y-y'\\|^2 \\}.$$\n\nPlease, notice that $D_{\\mathcal{X}}$ appears with an exponent of $1$ while $ \\| y − y′\\|$ with an exponent of $2$. Instead, en route for our convergence proof, we had to prove Claims C.10 through C.13. We have not encountered these claims in previous min-max optimization literature before.\n\n\n## Further concerns\n\n>  when the problem itself is not hidden strongly concave, a regularization [...] needs to be added to make\n\nYou are correct and we should provide the regularization's order. For the time being, please see Thm. F.10 (formal version of Thm. 4.3) for a precise tuning. $\\mu$ is tuned at line 2945.\n\n> Proof of Theorem 4.1\n\nPlease refer to its formal version Theorem E.1.\n\n\n\n\n[1] Yang, J., Kiyavash, N., and He, N. Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems. NeurIPS 2020.\n\n[2] Yang, J., Orvieto, A., Lucchi, A., and He, N. Faster single-loop algorithms for minimax optimization without strong\nconcavity. AISTATS 2022.", "claims_and_evidence": "I did not carefully review the paper due to a serious ethical concern. If the authors can address my concern (below), I am happy to provide a careful evaluation in the rebuttal period.\n\n## Updated March 30\n\nThe main claims on how the two-player zero-sum cMG is abstracted by a nonconvex-nonconcave minimax optimization and the convergence guarantees of the proposed nested-loop and single-loop algorithms are sound and credible.", "methods_and_evaluation_criteria": "## Updated March 30\n\nThe convergence metric ($\\epsilon$-NE introduced in Definition 2) is a standard choice in the literature and makes sense.", "theoretical_claims": "## Updated March 30\n\nI checked the mathematical claims in the main paper and part of the appendix. I do not see any major errors and find the claims solid and credible.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "The pPL condition may come up in other problems beyond zero-sum cMGs, in which the analysis of gradient-descent-ascent-based algorithms presented in this paper can provide insight.", "essential_references_not_discussed": "## Updated March 30\nThere are two important works which are currently referenced and discussed in the paper in a superficial way, Karimi et al. [2016] and Yang et al. [2020]. More discussion on the technical novelty of this work over the two papers should be made more clear.\n\nKarimi et al. [2016] studies nonconvex (possibly non-smooth) optimization under the PL condition and draws the connections between a range of related conditions such as PL, quadratic growth, restricted secant, etc., and studies the convergence of (proximal) gradient descent. I do not find most results on page 5 unexpected as similar versions of them appeared in Karimi et al. [2016].\n\nYang et al. [2020] studies nonconvex-nonconcave minimax optimization under the PL condition and shows the convergence of alternating gradient descent ascent under deterministic and stochastic gradient oracles.", "other_strengths_and_weaknesses": "There are a large number of non-existent references, including but not limited to \n\n\"Learning in markov games: Algorithms and guarantees\",\n\n\"Decentralized learning in stochastic games: Convergence to coarse correlated equilibria\",\n\n\"Convergence to cce in multi-agent markov games\",\n\n\"An empirical study on offline multi-agent reinforcement learning\",\n\n\"Fast convergence of equilibria in stochastic games\".\n\nThis raises a concern for potential misbehavior.\n\n## Updated March 30\n\nOn the positive side, the paper is very clearly written in the methodology. The development of technical results is easy to follow and provides a tutorial value in that aspect. The technical claims are sound and credible.\n\nMy main concern is that the paper seems to lack important technical contributions over the prior works I mentioned above (especially Yang et al. [2020]). The difference between this paper and Yang et al. [2020] that I can see is 1) Yang et al. [2020] studies the unconstrained case, while this paper studies the constrained problem and the algorithm makes projections to the constrained set. However, making this extension should be straightforward; 2) this paper models the zero-sum cMG problem in the minimax optimization framework, which also seems technically insignificant. I encourage the authors to correct me if my understanding is incorrect. In any case, more discussion on the exact technical contributions over the prior work should be made in the introduction section.", "other_comments_or_suggestions": "In the theorem statements in Section 4, the authors should consider specifying order-wise how to choose $\\varepsilon_x,\\varepsilon_y,\\tau_x,\\tau_y$ as functions of the desired precision $\\epsilon$.\n\nRegarding the simulations, \n1) It would be nice to see the single-loop algorithm compared against the nested-loop one.\n2) Is the rock-paper-scissors-dummy problem a convex, nonlinear MG or is it actually linear?\n\nMore discussion of Theorem 4.3-4.6 is needed. Can the authors clarify if my understanding is correct: when the problem itself is not hidden strongly concave, a regularization on the order of the desired precision needs to be added to make it so. If this is true, why does the statement of Theorem 4.3 not involve $\\mu$?\n\nI find it hard to locate the proof of Theorem 4.1. Can the authors point out where it is in the appendix?\n\nI do not understand the discussion of the technical challenge in line 055-062 (first column on page 2). At least in the linear utility setting, it is clear that we can define the aggregate value functions, which satisfies a fixed point equation involving a contractive operator. See Perolat et al. [2015]. Value-iteration-type methods can be used to find the fixed point. I suppose something similar should exist in the general convex setting as well.\n\nReferences\n\nPerolat, J., Scherrer, B., Piot, B. and Pietquin, O., 2015, June. Approximate dynamic programming for two-player zero-sum Markov games. In International Conference on Machine Learning (pp. 1321-1329). PMLR.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Research Integrity Issues (e.g., plagiarism)"], "ethical_review_concerns": "The paper contains a large number of non-existent references. This raises a potential concern for LLM-generated content which has not been carefully reviewed by the authors."}}, {"review_id": "L8ie9lM6Pe", "reviewer": "Reviewer_s9rc", "summary": "In this paper, the authors provide two (policy gradients-like) algorithms which learns $\\epsilon$-Nash equilibria in convex Markov games. The authors provide bounds to the number of iterations required to compute the approximate ($\\epsilon$) Nash. In order to do so, the authors leverage properties of hidden convex functions and Polyak-Lojasiewicz ones (namely, functions which satisfy the proximal Polyak-Lojasiewicz condition).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Dependence on $\\min_s 1/\\rho(s)$.\n\nThis quantity is merely a variant of the dependence on the *mismatch coefficient* [1, page 6 in the arxiv version][2]. The quantity $\\min_s 1/\\rho(s)$ upper bounds the mismatch coefficient when $\\rho(s)>0\\forall s$. The single-agent policy gradient convex MDP works also suffer this dependence on the mismatch coefficient [3,4].\n\nThe main policy gradient algorithm that manages to circumvent dependence on this parameter is the natural policy gradient [1] (NPG). Yet, provable convergence for this approach is known only for single-agent conventional MDPs and not even convex ones. Further, to our knowledge, there is no natural policy gradient approach for two-player zero-sum Markov games.\n\nConcluding, dropping this dependence seems distant for two particular reasons:\n\t(a) No provable guarantees for the natural policy gradient method insingle-agent convex RL exist.\n\t(b) No provable guarantees for NPG in two-player zero-sum Markov games exist.\n\nAs such, it should not be surprising that this dependence is present in our work as well\n\n\n## Dependence on $1/(1-\\gamma)$.\n\nLarge dependence on the quantity $1/(1-\\gamma)$ in sample complexity is to be expected as is the case in similar works, e.g., [2], where the exponent of $1/(1-\\gamma)$ is $48.5$ and [5] $10 \\times 4 = 40$.\n\n## Dependence on $\\delta_x,\\delta_y$ and their tuning.\n\nThank you for bringing this matter up. We ought to have been more clear on this. Checking the formal statements of our theorems, it should be apparent how convergence depends on these quantities. Namely, the $\\delta$'s dictate the accuracy that is possible to get in terms of stationarity and duality gap (for convex and strongly convex utilities respectively).\n\nFor the particular case of Alt-PGA and Nest-PG:\n\n* $\\delta_y$ is merely the sampling bias of estimating the gradients by picking trajectory samples of fixed deterministic horizon, $H$. Yet, $\\delta_y$ decays exponentially with $H$.\n\n* $\\delta_x$ suffers from the same sampling bias **plus** the fact that player $1$ does not have access to the precise gradient of the regularized function. I.e., player $1$ can only estimate the gradient of the un-regularized function and suffer an error that is *bounded by the regularization coefficient's size times the upper bound of the regularizer's gradient norm*, in which case is the regularizer's Lipschitz modulus,  i.e.,\n\n$$\\delta_x \\leq O(\\exp(-H)) + \\mu_{\\mathrm{reg}} L_{\\mathrm{reg}}.$$\n\nFor this reason we tune the regualrizers coefficient as $\\mu_{\\mathrm{reg}}\\gets O\\left(\\frac{\\epsilon}{L_{\\mathrm{reg.}}}\\right)$.\n\n## Further Notes\n\n* (3.) Absolutely correct, it should be GDmax\n4-5. We will fix these errors shortly. We agree that we should be using $O(\\cdot)$ notation.\n\n* (6.), this is an interesting question. To the best of our-knowledege there are no lower bounds. We think that base on [6], the lower bound should not be more that $O(1/\\epsilon^{3})$.\n\n* We agree that a comparison with [Goktas et al 23] should be discussed along with improvement of our related work section. Thank you for bringing up this work. \n\n-----\n\n[1] 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\n\n[2] Daskalakis C, Foster DJ, Golowich N. Independent policy gradient methods for competitive reinforcement learning. NeurIPS 2020\n\n\n[3] Zhang, J., Koppel, A., Bedi, A.S., Szepesvari, C. and Wang, M., 2020. Variational policy gradient method for reinforcement learning with general utilities. NeurIPS 2020\n\n[4] Zhang, J., Ni, C., Szepesvari, C. and Wang, M., 2021. On the convergence and sample efficiency of variance-reduced policy gradient method. NeurIPS 2021\n\n[5] 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 2021\n\n[6] Vavasis SA. Black-box complexity of local minimization. SIAM Journal on Optimization. 1993", "claims_and_evidence": "The claims seem convincing.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense and are intuitive.", "theoretical_claims": "I did not check any proofs in details, nevertheless, the results seem convincing.", "experimental_designs_or_analyses": "I checked the soundness of the experimental design in the main paper.", "relation_to_broader_scientific_literature": "I think that both the techniques and the result presented in this paper would be of interest for the Game Theory community.", "essential_references_not_discussed": "I believe that the paper is missing the following reference. I think that a comparison with [1] should be inserted in the paper.\n\n[1] \"Convex-Concave Zero-Sum Markov Stackelberg Games\", Goktas et al. 2023", "other_strengths_and_weaknesses": "Overall, I believe this is a good paper. The theoretical analysis seems solid and the results are convincing. The paper is presented in an intuitive way, so that the reader can grasp the main idea behind the techniques.\n\nPossible weakness of the work is the dependence of some parameters in the number of iterations necessary to approximate the Nash. For examples:\n1. Is the dependency on $\\min_s 1/\\rho(s)$ necessary?\n2. The $Poly$ notation hides some really bad coefficients with respect to many of the parameters in the bound (e.g. w.r.t. $1/(1-\\gamma)$)\n\nNonetheless, I do not believe these reasons are sufficient for rejections. Thus, for now, I lean towards the acceptance of the work.", "other_comments_or_suggestions": "3. Shouldn't be (GDmax) the algorithm employed in Theorem 3.1 and 3.3. ?\n4. Theorem 4.6. two \"with\"'s in the statement.", "questions_for_authors": "See Weaknesses. \n\nAdditionally,\n\n5. Why many of the results are proved with the $\\Theta$ notation, while others (see Theorem 4.5, 4.6) with the $O$ one? Moreover, are you sure the employing the $\\Theta$ notation is correct of a \"sample complexity\" kind of bound as the ones presented in the work? \n6. Are there lower-bounds for the number of iterations required to compute the $\\epsilon$-Nash?\n7. I do not fully understand why (GDmax) and (Alt-GDA) have no dependency on $\\delta_x,\\delta_y$ in the bounds (or in the batch-sizes).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the convergence of policy gradient methods in zero-sum convex Markov games to an approximate Nash equilibrium. The key technique is to leverage the hidden convexity of the objective in terms of the occupancy measure, together with the use of regularization. The theoretical results are solid and reasonable, albeit many techniques are adopted from the literature of minimax optimization and recent development of regularized policy optimization in RL, weakening the technical novelty of the results. There were also some comments on the presentation and clarity of the paper. Overall, the new model and results are still of merit to the multi-agent RL literature. I recommend that the authors incorporate the feedback from the reviewers in preparing the camera-ready version of the paper.
Decision: Accept (poster)