Policy Gradient Methods Converge Globally in Imperfect-Information Extensive-Form Games
Authors: Fivos Kalogiannis
Gabriele Farina
Venue: NeurIPS 2025 poster ()
Keywords: policy gradient methods
policy optimization
MARL
extensive-form games
zero-sum extensive-form games
imperfect-information
PL
Polyak- Łojasiewicz
natural policy gradient
softmax parametrization
REINFORCE
hidden convexity
hidden concave
hidden convex
Primary area: theory
TL;DR: We contribute provable guarantees that regularized policy gradient methods converge in approximate Nash equilibria in imperfect-information extensive-form zero-sum games.

Abstract: Multi-agent reinforcement learning (MARL) has long been seen as inseparable from Markov games (Littman 1994). Yet, the most remarkable achievements of practical MARL have arguably been in extensive-form games (EFGs)---spanning games like Poker, Stratego, and Hanabi. At the same time, little is known about provable equilibrium convergence for MARL algorithms applied to EFGs as they stumble upon the inherent nonconvexity of the optimization landscape and the failure of the value-iteration subroutine in EFGs. To this goal, we utilize contemporary advances in nonconvex optimization theory to prove that regularized alternating policy gradient with (i) *direct policy parametrization*, (ii) *softmax policy parametrization*, and (iii) *softmax policy parametrization with natural policy gradient* updates converge to an approximate Nash equilibrium (NE) in the *last-iterate* in imperfect-information perfect-recall zero-sum EFGs. Namely, we observe that since the individual utilities are concave with respect to the sequence-form strategy, they satisfy gradient dominance w.r.t. the behavioral strategy---or, \textit{policy}, in reinforcement learning terms. We exploit this structure to further prove that the regularized utility satisfies the much stronger proximal Polyak- Łojasiewicz condition. In turn, we show that the different flavors of alternating policy gradient methods converge to an $\epsilon$-approximate NE with a number of iterations and trajectory samples that are  polynomial in $1/\epsilon$ and the natural parameters of the game. Our work is a preliminary---yet principled---attempt in bridging the conceptual gap between the theory of Markov and imperfect-information EFGs while it aspires to stimulate a deeper dialogue between them.

Policy Gradient Methods Converge Globally in Imperfect-Information Extensive-Form Games
Fivos Kalogiannis UCSD CSE La Jolla, CA 92093 f stalogiannis@uceee edu
Gabriele Farina MIT EECS Cambridge, MA 02139 gfarina@mit. edu
Abstract
Multi-agent reinforcement learning (MARL) has long been seen inseparable from Markov games (Littman, 1994). Yet, the most remarkable achievements of practical MARL have arguably been in extensive- like Poker, Stratego, and Hanabi. At the same time, little known about provable equilibrium convergence for MARL algorithms applied EFGs as they stumble upon the inherent nonconvexity of the optimization landscape and the failure of the value-iteration subroutine in EFGs. To this goal, utilize contemporary advances in nonconvex optimization theory to prove that regularized alternating policy gradient with (i) direct policy parametrization, (ii) softmax policy parametrization, and (iii) softmax policy parametrization with natural policy gradient updates converge an approximate Nash equilibrium (NE) in the last-iterate in imperfect- information perfect-recall zero-sum EFGs. Namely, we observe that since the individual utilities are concave with respect to the sequence- form strategy, they satisfy gradient dominance with respect to the behavioral strategy or, policy, reinforcement learning terms. We exploit this structure to further prove that the regularized utility satisfies the much stronger proximal condition. In turn, we show that the different flavors of alternating policy gradient methods converge an 6-approximate NE with number of iterations and trajectory samples that are polynomial in 1/c and the natural parameters of the game. Our work is preliminary- yet principled principled-attemppt in bridging the conceptual gap between the theory Markov and imperfectt-informatinn EFGs while it aspires stimulate deeper dialogue between them.
games (EFGs) spanning games
Introduction
Reinforcement learning (RI. dominates contemporary applied and theoretical research. The flagship of RL, policy optimization methods, appears to lend reasoning capabilities to language models (Shao et al., 2024), defeats human Go world champions (Silver et al., 2016), and navigates real-world roads safely (Lu et al., 2023; Holuano-TTwwee et al., 2025). As is evident from even more ex- amples (Vinyals et al., 2019; Schritwieser et al., 2020), machine gameplay has transformed by incorporating RL techniques into its algorithmic arsenal. Although theoretical literature (Littman, 1994) posits that the canonical model of MARL are Markov games (MGs), MARL has handled informaatffoonn extensive-fome games (EFGs) with commendable success (Brown and Sand- holm, 2019b; Bard al., 2020; Perolat al., 2022).
At first, the theory and practice of imperfect-informaeee search in the properties of EFGs has exposed its convex structure using sequencc--orm strategies (Ro- manovskii, 1962; Koller al., 1996; Von Stengel, 1996) and yielded the different rounterfictuual-rgrett minimization algorithms (CFR) (Zinkevich et al., 2007; Tammelin, 2014; Brown and Sandholm,
EFGs can seem saturated. Exhaustive re-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

2019a). These algorithms can solve games using tabular policies with unmatched computational efficiency. Notwithstanding, these techniques seem to hit wall when faced with large-scale games whose size makes the use of tabular policies infeasible and calls for neural network parametrized policy (or, more generally, policy function approximation). The picture even more grave when CFR needs to be combined with model-free counterfactual value estimation. Its call for importance sampling yields a feedback of prohibitively high variance. Further, CFR's average-iterate conver- gence makes the task of extracting single policy network highly nontrivial. Since practitioners have extensively studied policy optimization for imperfect-information games (Lanctot et al., 2017; Srinivasan et al., 2018; Lockhart et al., 2019; Hennes al., 2020; Rudolph et al., 2025) without offering guarantees of polynomial time convergence, we are naturally lead to the question:
Do policy gradient methods provably converge to equilibrium in imperfect-informatiee EFGs using a polynomial number of iterations and samples?
To answer, we need to face the two obstacles that inperfect-informatioo games raise against optimiza- tion, the failure of value iteration-whicl we sidestep by solely using policy gradient updates-ant and a highly nonconvex policy optimization landscape-wiie whiic we prove to be benign.
Failure of value iteration In MARL for MGs, the overwhelming majority (Shapley, 1953; Wei et al., 2021; Zhao et al., 2022: Alacaoglu et al., 2022b; Zhang et al., 2019) of existing algorithmic solutions for equilibrium learning or computation makes use of value iteration subroutine or a value critic-which is in essence a backwards induction of the estimated value of the game. Instead, solving imperfect-information games requires leveraging the opponent's 's uncertainty about the underlying state. In other words, one needs to trade off exploiting private information and the benefit of keeping it secret. This precludes solving bebtree-b--subreee conditioned on private information and leads to the emergence of behaviors such as bluffing at optimality.
Gradient Domination in Nonconvex Problems. Contemporary machine learning is arguably propelled by large-scale optimization of systems of astounding size to perform increasingly elaborate tasks. The corresponding objective functions are by no means convex in terms of parameters, which precludes theoretical guarantees of even reaching a local optimum in a reasonable number of iterations (Murty and Kabadi, 1985). Yet, practice indicates a different reality and theory is gradually catching up. It has painstakingly been demonstrated that the nonconvexity of various ML. optimization problems is seriously canign-Significant
often, stationarity implies global optimality. Cases in point, gradient domination exhibited for the loss functions of overparamelrized neural networks (Liu al., 2022a; Scaman et al., 2022), the linear quadratic regulator (Fazel et al., 2018), value functions of Markov decision processes (MDPs) (Agarwal et al., 2021; Bhandari and Russo, 2024), matrix completion (Ge et al., 2016), dictionary learning (Sun et al., 2015), and more. For a thorough discussion of gradient domination and other regularity conditions we refer the reader to (Karimi et al., 2016; Li and Pong, 2018; Drusvyatskiy and Paquette, 2019; Drusvyatskiy and Lewis, 2018; Liao et al., 2024; Rebjock and Boumal, 2024; Oikonomidis et al., 2025) and references therein. With the latter in mind, one could make the case that when game theory researchers seek equilibrium computation in general nonconvex games (Cai et al., 2024a; Angelopoulos et al., 2025) they set the bar too high. Still, the study of benign nonconvexity seems of great importance and rather underexplored (Yang et al., 2020; Mulvaney-Ken et al., 2023; Manakks-Gkaragkoouaa et al., 2021; Sakos et al., 2023).
1.1 Contributions
We answer in the affirmative by developing three policy gradient methods (Theorems 3.1 to 3.3). All three algorithmic approaches lead to last-iterate convergence to a regularized NE of the EFG. We contribute,
a novel decentralized exploration scheme that yields sufficient visitation of all information sets; a proof that the nonconvex utilities of the (un-)regularizee game satisfy gradient domination; guarantee of last-iterate convergence of three different alternating policy gradient (PG) methods: (1) PG with direct purametrization and fn-n regularization (2) PG sofimux parametrization and entropy regularization (3) natural policy gradient (NPG) with sofimax parametrization and entropy regularization.
2

---

condition for On a sidenote, we offer sharper dependence of the PL modulus to the hidden convexity modulus than the one suggested by (Karimi al., 2016, Appendix G) for constrained optimization.
1.2 Overview of Techniques
The theoretical guarantees for our three algorithmic solutions are pinpointed by a simple unifying conceptual principle. That is, the nonconvex optimization problem of computing an equilibrium by directly optimizing the behavioral strategies (or, policies) is a constrained two-sided PL optimization problem where alternating gradient descent ascent is known to converge. Namely, we show that the optimization landscape viewed in terms of policies is nonconvex in a rather benign way; the utility is hidden concave. In particular, after appropriate regularization, each utility function satisfies strong gradient domination property, i.e., the proximal Dolyykk-ojjssiewcce condition.
Hidden concavity. Going into more detail, utilities in EFGs are concave in terms of sequence- form strategies. We select an appropriate regularizer that enhances concavity to strong concavity, Moreover, enforcing positive lower bound the probability of reaching every information set yields a uniform Lipschitz constant for the bijection that maps sequence-fome strategies to behavioral policies. Taken together, these two observations imply strong each player's policy.
PL condition. For the sake of offering intuitive exposition, forego the nuances of constrained optimization to explain how the PL condition is proven to hold. We say that an optimization problem min, fz) exhibits hidden strong convexity when there exists invertible mapping
c(z) and function (n) that is j-strongly convex in u and f(x) = Hc(xr)). Strong convexity implies that
f(x) f" = H(()) H < 2p VV H.HH())l' (=)ll Now, a bounded Lipshcitz modulus Le >> O of the
1
12
inverse transform, (u) = x, leads to the Pt. inequality f(x) - l <
[[< by merely 2p
applying the chain rule of diffcrentiation. Similar arguments work for the proximal-PP condition.
Convergence. Then, alternating gradient descent ascent mingex maxyey S (x. y):
Tz+1 < Proj [xg - -1 V [e]l; M++1 + Proj y [v + v
proven converge a saddle-point point using typical Lyapunov function argument. We tune the stepsizes 722 Bly in such a way that one player learns faster than the other. Since the function is PL, this means that after each update the optimizer is significantly approximated. Intuitively, after enough iterations, the update scheme can be viewed as optimizing for ((x) == max,ey f(z y) as Tt-1 R Projx (z+, Th V, (xx)). Crucially, our convergence analysis sets aside the usual regret minimization arguments that are used to either prove average-iterate or best iterate convergence (e.g..
Anagnostides et al. (2022); Liu al. (2024)).
1.3 Comparison to Related Work
We point out two particular results (Sokota et al., 2022; Liu et al., 2024) directly related to our endeavor of policy gradient/optimizztion methods for inperfect-information EFGs. Although the magnetic mirror descent method proposed in (Sokota et al., 2022) does not come with guarantees in EFGs, it exhibits impressive empirical performance. (Liu et al., 2024) lays the foundation of our approach as it introduces the bidilated regularizer although it does not offer a convergence guarantee that is polynomial in the parameters of the game and 1/c.
Our work follows arguments utilized in the context of policy gradient methods for Markov decision processes (MDPs) and MGs. Namely, we use techniques from (Kalogiannis et al., 2025) that analyzed alternating gradient descent in the constrained parameter case and arguments from (Mei et al., 2020; Cen et al., 2022a) as the entropic bidilated regularizer is almost identical to discounted entropy. Further, we use arguments from (Zhang et al., 2021) to show that the mapping from sequence-form strategies to policies is Lipschitz continuous.
3

---

Altern//Simult Updates
Provable Convergence
Regularization
Feedback
(Liu et al., 2024)
simultancous
yes, best-iterate"
bidilated policy entropy
CFR, Q. Q
(Sokota et al., 2022)
simultancous
no
last-iterate,
Ours
alternating
bidilated
VVV, Q
polynomial time
Table Comparison policy gradient/optimization methods.
CFR, Q, Q, VoV stand for counterfactual value, action-value, traject. action-value, and policy gradient. Guarantees pscudo-polynomial in the game-size.
Preliminaries
In this section we introduce the key ingredients required for our analysis. For IIFGGs, we high- light how the utility is expressed as a concave function the sequence-forn strategies. We also review the-Euclidean entropic-bbdilated regularizer whose strong convexity underpins our gradient-domination arguments. With regards to RL theory, we recall the definition of the value and and action-van value functions and show that trajectory samples, roll-outs, give unbiased Monte-Carlo estimates both the utility and the bidilated regularizer via the (REINFORCE) estimator ( (Williams, 1992; Sutton al., 1999). Finally, review the optimization notions of hidden concavity and gradient dominance, used to prove convergence of our algorithmic solutions.
2.1
Imperfect-Informaaioon Extensive-Form Games
We briefly go over the definition of an IIEFG and move on to the sequence-form strategies and the corresponding regularizers.
Definition (IIEFG). A player zero-sum extensive-form game, r, is defined by the tuple S, A special chance player, c, models uncontrollable randomness while,
T is rooted game tree of height D(T),
: Hi U H2 U He is the set T'''s nodes, referred to as histories. Each history, h, belongs to exactly one of the sets Hi H2, He depending on the player responsible for taking action at
= U2 a finite set of information sets (infosets). The infosets partition histories, His of the acting player into sets of nodes that are indistinguishable. We will note S := max{ {,,,
A = {A.)ess,, B =
{B.).ss, are the action sets of player 1 and 2, respectively. Each infoset s S has a corresponding set of actions Ag, and respectively By, Further, will denote A, = AAa, A == max, A, and B, == |Ba), Buax == max, B,.
r: H + [0, 1] is a payoff function mapping leaves T to payoff for player 1; player 2 gets the opposite payoff.
perfect recall assumption is made, ensuring that players remember their past observations and actions. This implies that nodes in the same infoset have the same past observation sequence. We E S and (s',b),= E S₂ history h. ai (2(-) are either unique for non-root nodes or the null set for the root. We will overload notation a (h) to mean a (s) for the infoset s where h belongs (resp. for (h)).
will use 01 (s),, (2(s) s) to denote the last parent infoset-action pair (s',a'), a²),
encountered when descending from the game tree's
Sequence-Fore Form Strategies A player's behavioral strategy is probability distribution over actions each of their infosets. With Σ, we denote player I's subsequences of play starting at the root. In sequence-form, the strategy of player 1, 11 E R Eal, with EΣ1 1 Σ. A, is defined as:
1 (s, a) := 1
Vs E S, E As; 14 (
The sequence-form strategy and En of player 2 is defined in symmetric fashion. Introduced in (Ro- manovskii, 1962; Von Stengel, 1996; Koller al., 1996), sequence-fore strategies are generalizations of simplices and express the sequential structure of an IIEFG. The set of sequence-form strategies,

---

M2 are convex polytopes as they are is defined only by linear equalities and non-negene negaaiivtvv constraints. The chance player's contribution the probability of reaching history h is given by Ha(h) and it is assumed to be strictly positive for reachable nodes. For player 1, the expected utility given by the bilinear form:
V = (4i R
where R is the matrix representation of payoff function r. Forward, we will refer to behavioral strategies as policies which will be denoted as MI, n2. The solution concept we are after is an e-approximate Nash equilibrium.
Definition (c-NE), A policy profile Ti. x an e-approximate Nash equilibrium of an IIEFG r, if. for any policies nı and T2 it holds true that,
V S V & V +
The bidilated regularizer. Introduced in (Liu et al., 2024), the unweighted bidilated regularizer is defined using strongly-convex regularizer v-(-) multiplied by the total probability of reaching the corresponding infoset. Since it depends on both players' policies we write R( T2), R( T2). s.t.:
R1 (TI1 == BN
Σ ( (11)))
and R2(TI, = ENTT
Σ h
(TT(-116))
2.2 RL Fundamentals
Moving on, we define the value, action-value, and advantage functions in the context of IEFGGs Inspired by the occupancy measure of MGs, we define the history occupancy measure d' for a given policy profile x := (TT, .T2) which simply is the reach probability of each history and comes in handy shorthand notation in the description of the algorithms and their analysis. Moreover, we recall the definitions of direct and softmax policy parametrization. Last but not least, we demonstrate how the (REINFORCE) gradient estimator computes policy gradients for IIEFGs for both the unregularized and regularized utility.
Value, action-value, and advantage functions. Without loss of generality, we assume that players get a payoff only on a terminal history h. This way we can define the value function of infoset s, as the expected utility if the game were to start at a history ho belonging to s,
= B [r(h)]ko Es]
In similar vein, we define the action-value function, or Q, as the expected utility if the game started at at history ho belonging in and after the player had taken action ag. (or, resp. by).
Q a) = BT (-r ho E s, ap = a] and Q b) = n [r (r( E E ss = b]
Finally, the advantage function is defined for each player as the difference between an action-value and the infoset's 'ss  value A5(s. a) ;= (s)(s) QF a) and Ag (s, V*(() ( b). Similar to the state occupancy measure of an MG, we can define the history occupancy measure d= 7 + (0. 1]
which is defined as, dm (h) Exor [1 h]]. Overloading notation, for infoset S
dl (s) == Σne, (h).
Policies. Policies are precisely parametrized behavioral strategies. We will consider two parametrizations of policies, (i) direct parametrization, and (ii) softmax parametrization. For di- rectly parametrized policies, we denote the parameters as x, y which are x E *X.es, A(As), XsES, A A(B.). The parameters of softmax policies will be denoted x, 0 with E RAAAA A= E. A,
and 0 E B E.
Gradient estimation with REINFORCE. The ability to estimate gradient of the value function using trajectory samples, or roll-outs, has endowed the theory and practice of RL with the rich toolbox of gradient-based based optimization. In fact, the (REINFORCE) gradient estimator (Williams, 1992; Sutton et al., 1999) also an unbiased estimator of the policy gradient in the IEFG setting, and thus provides sound foundation for our analysis.
5

---

Definition 3 (REINFORCE), Let denote trajectory of infoset and actions sampled by implementing
policies T1, R2, { = ((k)).))))....)) We define REINFORCE,
Vy). (Vasvy) to the stochastic
gradient estimators:
Kg
K₁ v log Tx (a())))())) and V, Tg
V x log Ty T (b(4))88))) (REINFORCE)
km
The addition of regularization, leads to the definition a regularized value function, V7, (s) == E >x r(h(a) + + En (+((1(--)(x))) + (=T2(-1M(s))) [ E E
The regularized Q-value and advantage functions, Q7, are defined accordingly (see Ap- pendix B.2). Furthermore, (REINFORCE) can be minimally modified to estimate the policy gradient of the regularized value function without importance sampling (discussed detail in Appendix F.I).
Assumption 1. For Ti (als) 2 e, E E1, Va E A. T2(b|8) 2 e, Vs E S2, vb E B,.
0, both players' policies, for every infoset and action, satisfy
(s-trunc.)
Guaranteeing that (e-trunc.) holds is straightforward for directly parametrized policies. The players need pick policies I, y, from the cartesian product of appropriately trun- cated simplices, to be denoted 2e X², y respectively. As for softmax parametrized poli- cies, (e-trunc.) is achieved when both players' parameters are restricted to the poly- topes XR, OR. To demonstrate, XR is defined in the following manner, XR {x E IRA,A= A Σ. A, X. 1 0, Vs E Si, of OR follows suit. We highlight that the images of X RR V under the softmax map are convex sets (Lemma D.5) and we will denote the resulting truncated policy sets as II IIf.
Xa.l S 2R, Vi, [A.]] and the definition
2.3 Hidden Concavity and Gradient Domination
In this subsection, we define the two key backbone concepts of hidden concavity and gradient domination. Gradient domination of a weak or strong form has been extensively investigated in the theory of RL and MARL (Bhandari and Russo, 2024; Agarwal et al., 2021; I; Mei et al., 2020; Zhang et al., 2019; Daskalakis et al., 2020). Simply put, the nonconvex value function satisfies dominattoo property and any stationary point is globally optimal. Thus, any guarantee of convergence stationary point is elevated to guarantee of convergence global optimality.
Definition (Hidden convexity). noncorvex function f : X + R defined over the set X is said to be hidden (strongly) convex if there exists (i) bijective mapping X - for some convex set U; (ii) a function l - R that is strongly convex with modulus ay 2 0; such that [(x) (c(x)), Vx E X.
When the Lipschitz continuity modulus of the inverse transform, c- uniformly bounded implies the gradient domination condition shown in (Fatkhullin et al., 2023, Prop. 2) coupled with (Karimi et al., 2016, App. G).
Definition 5 (pPE. condition (Karimi et al., 2016)). Assume F RRd + IR defined as F(x) = f(x) + (x)) Let f: Rdd + RR be an E-smooth function and g Rd - R be convex. Define
Dz(x, - 26 min (V]()),= r) +)+ B(>l(=) +(=) - 5(x)
for choice of Bregman divergence B(-ll-). We say that F satisfies the pPL. condition with modulus a > if. for every x,
1 ! (2( -
where F+ ming F(x). When is the indicator function of a set X we write Dx(x, E).
3
Main Results
With the latter in hand, we are ready to state our main contributions, (i) the independent exploration strategy, (ii) the gradient domination condition for utilities of EFGs (iii) and the global convergence of three variants of policy gradient methods to approximate Nash equilibrium.

---

3.1 Efficient Exploration Scheme
We propose novel approach to exploration. Each player is expected reach every subsequence with probability at least " The rule is simple:
[H]
Assumption (Efficient Exploration). Both players follow the following exploration strategy:
At the start of each game, the player flips biased coin that shows "heads" with probability 7/- If the coin shows "heads", ;, the player selects sequence uniformly random and then executes After this sequence, or if the coin shows "tails", the player resumees play according to their policy.
noteworthy that using this exploration strategy, one can exercise direct control over the modulus of gradient domination. Whereas, policy gradient literature (Agarwal et al., 2021; Daskalakis et al., 2020; Mei et al., 2020; Zeng et al,, 2022) needs to make an assumption on the boundedness of the distribution mismatch coefficient.
Remark 1.
3.2 Gradient Domination Property of the Utilities
In this subsection, we establish that the utility of inperfect-informaann EFG under different policy parametrizations is pPł. with regards to the policy. This observation is central in proving convergence of policy gradient methods property for the unregularized utilities of the game.
Nash equilibrium. First, we state the weak gradient domination
Lemma 3.1 (Utility Weak Gradient Domination). Let be an imperfect- EFG, following Assumption 2, then holds true that
1
V
min 1 < max (V
52 T1 - mT)
2a
1
max T2
V V81
max 11. T22 - m2)
2a
for an a > 0 with a a' poly (2. |H,,
Now, by picking an appropriate regularization term to each player's utility we can enhance the weak gradient domination property to the much stronger pPE condition which ultimately guarantees last-iterate convergence to an equilibrium of the regularized game.
Lemma 3.2 (Utility PPL: restated from Lemmata E.1 E.3). Let an imperfecttinfformation EFG, I, perturbed by a pair of weighted bidilated regularizers (R1, R2) with coefficient T > O. Also, assume that each player follows Assumption and Assumption 2. Then, each player's 's utility satisfies
the pPL condition with modulus a x poly 4 minn) |H|, A, B,
key observation in both conditions is that the modulus a polynomial of the exploration parameter 1/7. This stresses the importance of efficient exploration and corresponding contribution of the scheme in Assumption 2. Also,
3.3 Convergence of Alternating Regularized Policy Gradient
Having established the required background and notation, we are ready to present our main results. In Theorem 3.1 we show the convergence of simple alternating regularized policy gradient to an approximate NE in the last iterate. Moving to Theorem 3.2, prove similar result for softmax- parametrized policies. Finally, we analyze alternating regularized natural policy gradient through a mirror-descent lens, demonstrate its relationship multiplicative weight updates of the policies, and prove its convergence to an approximate NE the last iterate (Theorem 3.3).
Throughout, Ja. f/y denote the stepsizes and V denotes the (REINFORCE) gradient estimate the utility w.r.t. player's parameters accounting only for their own regularization term.
3.3.1 Direct Policy Parametrization
The first result we present is the a simple policy gradient scheme with alternating updates and Euclidean regularizer. The parameter updates of alternating regularized policy gradient takes the
7

---

following form,
F1+1
Proj
1/e V (Iee, 2/-) Tr
x
(Alt-RegPG)
Vo+11 Proj y
Vr + my (z
where Projxe, Projy- denote the Euclidean projection of the parameters to the truncated simplices dictated by (e-trunc.). We state our first convergence theorem which settles question and defer its formal statement to the Appendix H.1.
Theorem 3.1 (Informal; restated from Thm. H.1). With direct policy parumetrization and the Euclidean bidilated regularizer, alternating policy-gradient algorithm atlains last-iterate e-Nash equilibrium in
T= =olo ( 1. [H], B,,277)) iterations, 2121
using batches of poly
2 [H], |1 (2), A, B,2D(T) trajectory samples each step.
Remark We note that the exponential dependence on D(T) is still polynomial in the game size as the height has üself logarithmic dependence in size of the game.
3.3.2 Softmax Policy Parametrization
We move on to convergence under softmax parametrization and entropic regularization. This choice of parametrization is an important step towards getting provable guarantees for policy gradient methods imperfect-informatiin EFGs using function approximation (e.g. neural networks). The projection to X O guarantees that (e-trunc.) is satisfied,
X++1 Proj Xn
Xt Th V 01)
(Alt-EntRegPG)
0+11 Proj 0, + ny (7(1..1.00) 0.)
Theorem 3.2 (Informal; restated from Thm. H.2), Alternating graddent algorithu with softmax policy parametrization and the entropic bidilated regularizer, converges in expectation in the last- iterate to an e-Nash equilibrium after a number of iterations T, that is
T = poly ( [H], A,,
iterations,
using batches of poly
L 1 [H) S1l. S2), A. trajectory samples at each step.
3.3.3 Natural Policy Gradient
Finally, we consider the natural policy gradient algorithm (Kakade, 2001) which is an adaptation of natural gradient (Amari, 1998). This algorithm is of particular interest due its intimate connection to the TRPO, PPO (Schulman et al., 2015, 2017) policy optimization algorithms. Natural policy gradient uses Fisher information matrix induced by the policy as preconditioner for policy gradient updates:
(xx,0)===av
dxx0(s)
E Tx (alss (als) (V log n. (als))
We cast natural policy gradient steps as mirror descent steps with Mahalanobis norm induced by the Fisher information matrix (for more nuanced discussion on this connection see (Raskutti and Mukherjee, 2015)) 5)).T)eTeeeee The update scheme can be equivalently written as:
x|(
X++1 arg min
Xx nu.
(x
0,)
x
Fx(x)()))
(Alt-RegNPG)
F (x+1, - 01
0.t1 arg min
00,
RE0R
Fo (x.+1.88))

---

More importantly, we note that in policy space, the update scheme of natural policy gradient takes very simple form which, as expected, reads, for player 1 (0 is element-win wise multiplication):
T1.41 (-1s) & TT - + exp (12 (1= Q= (s,-));
(-1))))))
F1.+1(1195 x arg min KL ( =en?
To see why the second approximate equality holds, we note that the Mahalanobis distance over the parameters induced by the Fisher information matrix of the softmax policy, is second-order approximation of policy KL divergence. The derivation and an extensive discussion are deferred to Appendices H.3 and I.
Theorem 3.3 (Informal; restated from Thm. H.3), For an appropriate tuning of Ma. fl O, the last-iterate of alternating regularized natural policy gradient (Alt-RegNPG) converges in expectation an e-approximate Nash equilibrium in number of iterations T that is:
T = poly ( (S1, A,
Empirical Validation
To corroborate our theoretical results, we tested Alt-RegNPG on four different imperfect information EFGs (Kuhn Poker, Ledue Poker, 2 x 2 Abrupt Dark Hex and Liar's Dice). Inspired by MMD (Sokota al., 2022), we implement two variants of Alt-RegNPG where the (i) the regularization strength diminishes across time along the stepsizes and (ii) the regularizer is the discounted KL divergence from a moving reference policy. We observe that the exploitability (i.e. max;; VTi
ming; mT diminishes across time for our method, and compares well with CFR and MMD,
Kuln Poker
Ledue Poker
Dark Hex
Liar's Dice
Exploitabiity
100
10-3
10-1
10
10
10-1
2
3
500 Ineration
1000
500
1000
500
1000
500
1000
Itcration
Reg, NPG
Reg, mav.
XMD temp.
Alt. Reg, NPG anneel.
CFR
Figure 1: Three variants of Alt-RegNPG compared against CFR and MMD.
5
Discussion
We conclude our main text with further comparison between MGs and imperfect information IIEFGs to further promote the connection between the two areas. Finally, state our conclusions and suggestions for future work.
5.1 Further comparison of Markov and Imperfect Information Extensive-Form Games
innrrrecttinfoormationn IIFGGs and MGs both model multi-stage strategic interaction. They differ sharply in what each player can observe while they maintain marked similarities in the way strategies are represented (behavioral strategies and policies), the hidden concave representation of utilities (concavity w.r.t. sequence-form strategies and occupancy measures), and regularization choices for optimization. The table and discussion below summarize this comparison along the axes of observability, strategy space, utility convex reformulation, regularization and optimization landscape. Clearly, infoset (information set) in an a state is to a policy an MG. However, imperfect information (or partial observability) leads to discrepancy between the expected return of an infosct in EFG and the expected return state
EFG is to a behavioral strategy what

---

Game State
Observable State
Control Variables
Utility Concave In
Behavioral Strategy T(-(s)
Sequence-forg
History h T
Infoset E S
HEFG
Strategy μ
each a node of game tree graph T
each a disjoint set of multiple histories l
distribution over actions at infoset
independent of
opponents' strategies
State-action
Markovian Policy x(-[s)
State
Occupancy measure X"
MG
fully observable by all players
distribution over actions state 8
depends on opponents' policies
potentially recurring in the finite or infinite horizon of the game
Table 2: Imperfeettinfformatior extensive-form games (IIEFG) vs. Markov games (MG).
in an MG as highlighted in (Nayyar et al., 2013; Sokota et al., 2023). Interestingly, the concave reparametrization of EFG utilities exhibits a structure more favorable than the corresponding one in MGs. In particular, the utility is concave in sequence-form strategies of IIFGGs and the latter depend solely on a player's own behavioral strategy. This comes in stark contrast to the state-action occupancy measure of MGs which are conditioned on opponents' strategies.
Finally, similarities of the regularization techniques in IIFGSs and MGs are cornerstone The EFG entropic bidilated regularizer (Liu et al., 2024), R. and the very commonly used MDP discounted entropy (Williams and Peng, 1991; Haarnoja et al., 2018; Mei et al., 2020; Cen al., 2022a,b), E, are virtually identical. We note that, in IIEFGs regularizer is mostly used in context of directly optimizing the sequence-form space. They induce a distance generating function of mirror descent instantiations. Some more recent works have used it to make the game strongly-monotone and guarantee convergence of gradient descent methods (Liu al., 2022b). Liu et al. (2024), in the context of policy optimization, define the bidilated regularizer whose policy gradients can be estimated without importance sampling. Illustratively, the two regualaizers read side-by-side (7 is discount factor of MDPs):
work.
R(T) = EgNT EEvneEs (T((+13)))
{(T) = Eg Σ# (0-1(((((())))
5.2 Conclusion
We studied three different policy gradient methods for imperfect-information perfect-recall zero- sum IIFGGs under unifying optimization principle. We managed to provide the first global last-iterate convergence guarantees of policy gradient methods to an 6-approximate Nash equilibrium. Furthermore, our analysis requires a number of iterations and samples that is polynomial 1/e and the parameters of the game. To do so, demonstrated that utilities as functions of behavioral strategies (policies) exhibit gradient domination properties even though they are nonconvex; and provided practical decentralized exploration scheme that implicitly controls the moduli of gradient domination. We departed from the usual route regret analysis in IIEGGs and opted for more conventional convergence analysis arguments using a Lyapunov function. We hope to motivate further exchange between theoretical MARL research and the theory of IIEFGs as we strongly believe in the potential this communication fosters.
Future directions. Our main objective was proving polynomial time convergence of policy gra- dient in IEFGGs our analysis at places loose. We firmly believe that the convergence rates and constant dependencies can be improved, e.g., by using the machinery of treeplex norms (Fan et al., 2024), relatively- smooth optimization (Lu et al., 2018; Fatkhullin and He, 2024), and other policy optimization arguments (Zhan et al., 2023; Cen et al., 2022b). To be particular, we would like to see guarantees that do not call for mini- mini-batching and possibly use variance reduction techniques. Moreover, fundamental questions about the limit points of policy gradient methods in IIEFGs (similar to those of (Giannou et al., 2022) for MGs) are open. More broadly, do forms of benign nonconvexity (like hidden convexity) refine the results of (Cai et al., 2024b; Angelopoulos al., 2025)?
10

---

Acknowledgments
This work was supported in part by the NSF AI Institute for Learning- Optimization at Scale (TILOS, (CCF22122655) NSF Award CCF-244306, and the Office of Naval Research (ONR grants N00014241266 and N00014-25-1-2296) GF is supported in part by an AI2050 Early Career Fellowship.
References
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-766 1-6, 2021.
Ahmet Alacaoglu, Luca Viano, Niao He, and Volkan Cevher. A natural actor-critic framework for zero-sum markov games. International Conference on Machine Learning, pages 307-366. PMLR, 2022a.
Ahmet Alacaoglu, Luca Viano, Niao He, and Volkan Cevher. A natural actor-critic framework for zero-sum Markov games. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 307-366. PMLR, 17-23 Jul 2022b. URL https: / ppoppeeecceeensse// mlr www.ppres/vveie wwwpppewsseeeeeeeepeepep wtllv////aaaalllllaaa ala.aoglu22a........ html.
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2)251-276. 1998.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. International Conference on Machine Learning, pages 536-581. PMLR, 2022.
Anastasios N Angelopoulos, Michael I Jordan, and Ryan J Tibshirani. Gradient equilibrium in online learning: Theory and applications. arXiv preprint arXiv:2501 20030:030000033300, 2025.
Nolan Bard, Jakob Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, et al. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 280: 103216, 2020.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. Opera- fions Research, 72(5): 2X5):1906-1922 2024.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 310t):2 2002.
Noam Brown and Tuomas Sandholm. Solving cuperfect-informaatee games via discounted regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1829-1836, 2019a.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019b.
Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen Yu Wei, and Weiqiang Zheng. On tractable phi-equilibria in non-concave games. arXiv preprint arXiv:2403.08/71, 2024a.
Yang Cai, Gabriele Farina, Julien Grand-Clénen Christian Kroer, Chung-War Wei Lee, Haipeng Luo, and Weiqiang Zheng. Fast last-iterate convergence of learning in games requires forgetful algorithms. 200.244066.033, 2024b.
arXiv preprint
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4): 1563-2578,, 2022a.
Shicong Cen, Yuejie Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence of policy optimization in zero-sum markov games. arXiv preprint arXiv:2210.010550 2022b.
11

---

Marco Honumano-Towneee David Hafner, Alex Hertzberg, Brody Huval, Aleksei Petrenko, Eugene Vinitsky, Erik Wijmans, Taylor Killian, Stuart Bowers, Ozan Sener, al. Robust autonomy emerges from self-play. arXiv preprint arXiv:2502.03344, 2025.
Constantinos
Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33: 5527-5540, 2020.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate (k-1/4) on weakly convex functions. arXiv preprint 1rXiv:1802.02988. 2018.
Dmitriy Drusvyatskyy and Adrian S Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 43(3):919-948, 2018.
Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming. 178:503-5553 553600555,,11 2019.
Zhiyuan Fan, Christian Kroer, and Gabricle Farina. On the optimality of dilated entropy and lower bounds for online learning in extensive-form games. arXiv preprint arXiv:2410.23398, 2024.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive- form games via dilated distance-generalie functions. Advances in neural information processing systems, 32, 2019.
Ilyas Fatkhullin and Niao He. Taming nonconvex stochastic mirror descent with general bregman divergence. In International Conference on Arlificial Intelligence and Statistics, pages 3493-3501. PMLR, 2024.
Ilyas Fatkhullin, Niao He, and Yifan Hu. Stochastic optimization under hidden convexity. arXiv preprint 1xXiv:2401.00100 2023.
Maryam Fazel, Rong Ge. Sham M. Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, 2018. URL https: / //api. semanti cscholar.. Perg/CorpusID:.. :11rpusII::5181644 51881649.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory
and reinforcement learning. arXiv preprint 1rXiv:1704.0088 2017.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in neural information processing systems, 29, 2016.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International conference on machine learning, pages 2160-2169. PMLR, 2019.
Angeliki Giannou, Kyriakos Lotidis, Panayotis Mertikopoulos, and Emmanouil- Vassiliios Vlatakis- Gkaragkounis. On the convergence of policy gradient methods to nash equilibria in general stochastic games. Advances in Neural Information Processing Systems, 35:7128-7144
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference machine learning, pages 1861-1870. Pmlr, 2018.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):157-325 2016.
Daniel Hennes, Dustin Morrill, Shayegan Omidshafiei, Rémi Munos, Julien Perolat, Mare Lanctot, Audrunas Gruslys, Lean-Baptiste Lespiau, Paavo Parmas, Edgar Duéñez Guzmán, and Karl Tuyls. Neural replicator dynamies: Multiagent learning via hedging policy gradients. In Proceedings of the 19th International Conference on Autonomous Agents and MulriAgent Systems, AAMAS '20, page 492-501, Richland, SC, 2020, International Foundation for Autonomous Agents and Multiagent Systems. ISBN 1781450375184.
Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2): 494-512, 2010.
12

---

Sashank Reddi, Suvrit Sra, Barnabas Poczos, and Alexander Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29, 2016.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Fivos Kalogiannis, Vaniloui--Vasileioos Vlatakis- Katakis-Ckaragkounii. Ian Gemp, and Georgios Piliouras. Solving zero-sum convex markov games. In Forty-second International Conference on Machine Learning, 2025.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewiez condition. In Join! European conference on machine learning and knowledge discovery databases, pages 795-811. Springer, 2016.
Daphne Koller, Nimrod Megiddo, and Bernhard Von Stengel. Efficient computation of equilibria for extensive two-person games. Games and economic behavior, 14(2):247-259, 1996.
Christian Kroer, Kevin Waugh, Fatma Kılinc- Karzan, and Tuomas Sandholm. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming, 179 (1):385-411) 2020.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Gracpel. A unified game-theoretic approach to multiagent reinforcement learning. Advances neural information processing systems, 30, 2017.
Tor Lattimore and Csaba Szepesvári. Bandil algorithms. Cambridge University Press, 2020.
Guoyin Li and Ting Kei Pong- Calculus of the exponent of aurdyka-lojasievin inequality and its applications to linear convergence of first-order methods. Foundations of computational mathematics, 18(5): 1992, 2018.
Feng-Y- Yi Liao, Lijun Ding, and Yang Zheng. Error bounds, pl condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. In 6th Annual Learning for Dynamics Control Conference, pages 993-1005. PMLR, 2024.
Michael L Littman. Markov games as framework for agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022a.
Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regularization in solving extensive-form games. arXiv preprint arXiv:2206.09490 2022b.
Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar. A goadietgradient approach to solving imperfect-information games with iterate convergence. arXiv preprint arXiv:2408.000 00751,, 2024.
Weiming Liu, Huacong Jiang, Bin Li, and Houqiang Li. Equivalence analysis between counterfactual regret minimization and online mirror descent. In International Conference on Machine Learning, pages 13745- PMLR, 2022c.
Edward Lockhart, Mare Lanctot, Julien Pérolat, Jean-Bapiin nan-BBptitte Lespiau, Dustin Morrill, Finbarr Timbers, and Karl Tuyls. Computing approximate equilibria in sequential adversarial games by exploitability descent. arXiv preprint arXiv: 05614, 2019.
Haihao Lu, Robert Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal Optimization, 28 28(1):33--354 2018.
Yiren Lu, Justin Fu, George Tucker, Xinlei Pan, Eli Bronstein, Rebecca Roelofs, Benjamin Sapp. Brandyn White, Aleksandra Faust, Shimon Whiteson, et Imitation is not enough: Robustifying imitation with reinforcement learning for challenging driving scenarios. In 2023 IEEF/RS/ International Conference on Intelligent Robots and Systems (IROS), pages 7553-7560, IEEE, 2023.
13

---

Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International conference on machine learning, pages 6820-6829. PMLR, 2020.
Julie Mulvaney-Kemne Sang Woo Park, Ming Jin, and Javad Lavaei. Dynamic regret bounds for con- strained online nonconvex optimization based on polyak-lojasiewiez regions. IEEE Transactions on Control of Network Systems, 10(2):599-611, 2023. doi: 10.1 10.110002
Remi Munos, Julien Perolat, Jean-Baptiste Lespiau, Mark Rowland, Bart De Vylder, Mare Lanctot, Finbarr Timbers, Daniel Hennes, Shayegan Omidshafici, Audrumas Gruslys, et al. Fast computation of nash equilibria in imperfect information games. In International Conference on Machine Learning, pages 7119-7129, PMLR, 2020.
Katta G Murty and Santosh Kabadi. Some np-complete problems in quadratic and nonlinear programming. Technical report, 1985.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances in neural information processing systems, 30, 2017.
Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. Decentralized stochastic control with partial history sharing: A common information approach. IEEE Transactions Aulomatic Control, 1845)11644-1658 2013.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy-regularized markov decision processes. arXiv preprint arXiv:1705.07798, 2017.
Konstantinos Oikonomidis, Emanuel Laude, and Panagiotis Patrinos.
splitting
under the light of generalized convexity. arXiv preprint arXiv:2503.1880 2025.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two- wwo-player zero-sum markov games. In International Conference on Machine Learning, pages 1321-1329. PMLR, 2015.
Julien Perolat, Remi Munos, Jean-Baptis Lespiau, Shayegan Omidshafici. Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference on Machine Learning, pages
PMLR, 2021.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, (78(663)):99--999 2022.
Garvesh Raskutti and Sayan Mukherjee. The information geometry of mirror descent. IEEE Transactions on Information Theory, 61(3):1451-1557 2015.
Quentin Rebjock and Nicolas Boumal. Fast convergence to non-isolated minima: four equivalent conditions for с functions. Mathematical Programming, pages 1-49, 2024.
Roomanoskki. Reduction of game with complete memory to a matrix game. Soviet Mathematics, 3:678-681, 1962.
Max Rudolph, Nathan Lichtle. Sobhan Mohammadpour, Alexandre Bayen, J Zico Kolter, Amy Zhang, Gabriele Farina, Eugene Vinitsky, and Samuel Sokota. Reevaluating policy gradient methods for imperfecttinfoomaation games. arXiv preprint arXiv:2502.08933 2025.
Iosif Sakos, Emmanouil-
Caamanoui--Vasileios Vasileios Vlatakis Gattakis-Gkkragkkuumag Panayotis Mertikopoulos, and Georgios Piliouras. Exploiting hidden structures in non-convex games for convergence nash equilibrium. Advances in Neural Information Processing Systems, 36:66979-67006, 2023.
Kevin Scaman, Cedric Malherbe, and Ludovic Dos Santos. Convergence rates of non-convex stochastic gradient descent under generic lojasiewiez condition and local smoothness. In International conference machine learning, pages 19310-19327. PMLR, 2022.
14

---

Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-66) 2020.
John Schulman, Sergey Levine, P. Abbeel, Michael I. Jordan, and Philipp Moritz. Trust region policy optimization. ArXiv, abs/1502.004777, 2015. URL htt.:t/...pp...saaiiiccc.. semanticscholar
org/Corpus 16046818.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/1707.06347, 2017. URL https://api set.ppiissnataiicchhllarrrr
org/CorpusID 28695052.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. Deepseckmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint Stt1:2402.033000 2024.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):
1095-1100, 1953.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484-455 2016.
Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Mare Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games, arXiv preprint arXiv:2206.0553 2022.
Samuel Sokota, Ryan D'Orazio, Chun Kai Ling, David Wu, Zico Kolter, and Noam Brown. Abstracting imperfect information away from two-player zero-sum games. In International Conference on Machine Learning, pages 22169-321999 PMLR, 2023.
Sriram Srinivasan, Mare Lanctot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling. Actor-critic policy optimization in partially observable multiagent environments. Advances in neural information processing systems, 31, 2018
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere. In 2015 International Conference on Sampling Theory and Applications (SampTA), pages 407-410. IEEE, 2015.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Oskari Tammelin. Solving large imperfect information games using cfr+. arXiv preprint 1rXiv:1407.5042, 2014.
Oriol Vinyals, Igor Babuschkin, Junyoung Chung, Michael Mathieu, Max Jaderberg, Wojeiech M Czarnecki, Andrew Dudzik, Aja Huang, Petko Georgiev, Richard Powell, et al. Alphastar: Mastering the real-time strategy game starcraft ii. DeepMind blog, 2:20, 2019.
Emmanouil-Vasilee Vlatakis- Kaaakis-Gaaaggounii. Lampros Flokas, and Georgios Piliouras. Solving min-max optimization with hidden structure via gradient descent ascent. Advances in Neural Information Processing Systems, 34:2373-2386 2021.
Bernhard Von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-246 1996.
Chen-Yu Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infiite-horizon competitive markov games. In Conference learning theory, pages
PMLR, 2021.
Ronald J Williams. Simple statistical gradient- following algorithms for connectionist reinforcement learning. Machine learning, +:229-256, 1992.
15

---

Ronald J Williams and Jing Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):411-268. 1991.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconnvex-monconcav minimax problems. Advances in Neural Information Processing Systems, 33:1153-1165, 2020.
Sihan Zeng, Thinh Doan, and Justin Romberg. Regularized gradient descent ascent for two-player zero-sum markov games. Advances in Neural Information Processing Systems, 35:34546-34588, 2022.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lec, and Yuejie Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. 2023.
SIAM Journal on Optimization, 33(2):
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572-4588, 2020.
Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari. Mengdi Wang, et al. On the convergence and sample efficiency of variance-reducee policy gradient method. Advances in Neural Information Processing Systems, 34:2228 22400, 2021.
Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Policy optimization provably converges nash equilibria in zero-sum linear quadratic games. Advances in Neural Information Processing Systems, 32, 2019.
Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong. Na Li, and Yu Bai. Policy optimization for markov games: Unified framework and faster convergence. Advances in Neural Information Processing Systems, 35:21886-21888 2022.
Yulai Zhao, Yuandong Tian, Jason Lee, and Simon Du. Provably efficient policy optimization for two-player zero-sum markov games. In International Conference Artificial Intelligence and Statistics, pages
PMLR, 2022.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances neural information processing systems, 20, 2007.
16

---

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

---

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

---

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

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: description of laptop
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htttps://eeurips http:///ww......eeeiiiet//////// cerpriiiccceeeeeeeec ines?
Answer: [Yes]
Justification: we follow the NeurlPS code of ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: work is theoretical. probably unlikely that will have direct societal impacts
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
20

---

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

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: no crowdsourcing
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: theoretical research
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines: only editing grammar
22

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non-standard components.
Please refer to our LLM policy (https : //tprr/ee.ppp//eee cc/Conferences// /LLM) for what should or should not be described.
23

---

Appendix
A
Further Related Work
25
Further Preliminaries on IEEGSs
26
B.1 The Behavioral and Sequence-Form Strategies
26
B.2 Value, Action-Value, and Advantage Functions
28
B.3 Continuity the Utility..
29
B.4 Properties of the Bidilated Regularizer
30
Efficient Exploration
34
D Regarding the Policy Parametrization
35
D.I Definitions..
35
D.2 Properties under Parameter Constraints
35
E Gradient Domination
38
E.1 Direct Policy Parametrization pPt.
38
E.2
Softmax Policy Parametrization pPL.
E.3 Mahalanobis -PE
39
E,4
Weak Gradient Domination
40
Gradient Estimators
40
F.1
A Policy Gradient Theorem
40
Optimization Lemmata
45
G.I A Variation of the Descent Lemma
47
G.2 Min-Max Optimization
48
G.3 Regarding the Mahalanobis Distance
50
G.4 Alternating Mirror Descent using a Changing Mahalanobis DGF
H Convergence Analysis
55
H.1 Direct Policy Parametrization
H.2 Softmax Policy Parametrization
57
H.3 Natural Policy Gradient
59
Proximity of Projections
24

---

A Further Related Work
In this section we attempt discussing related work. Arguably, since our work lies in the intersection of several already broad themes, we encourage the reader to follow references in the cited works.
Relevant MARL for MG works In MDP and MG literature, policy optimization seems to come in two flavors- an online learning (Hazan et al., 2016; Lattimore and Szepesvári, 2020) approach and a stochastic optimization one. In the current work, we opt for the second approach.
The approach of (Zeng et al., 2022) which considers zero-sum Markov games is particularly similar to ours. Yet, highlight that they make rather strong assumption; they assume that the probability of playing each action in the support of the regularized Nash equilibrium is lower-bounded by constant independent of the regularization coefficient т. In turn, we contribute the two-sided pPt. condition for IIEFGs and, importantly, circumvent such an assumption by exercising direct control over the minimum probability of playing any action by projecting the parameters of the softmax parameters onto convex polytope.
Theory of Policy Gradient Methods The policy gradient method was introduced for Markov decision processes in (Williams, 1992; Sutton et al., 1999). Ever since provable guarantees have been yielded by number of works for different variations of the algorithm:
(Agarwal et al., 2021) prove the convergence of directly parametrized policy gradient. They use the convergence result of gradient descent for smooth nonconvex function along a gradient domination lemma to demonstrate a O(1/²)) convergence rate to optimality. Later, (Zhang et al., 2020, 2021) use the hidden concave structure of the problem to improve the convergence rate to O(1/e).
(Mei et al., 2020) provide the first asymptoti convergence rate result for the policy gradient method using discounted entropy regularization (the analogue of bidilated entropy regularization). The proof of convergence uses a novel nonuniform PL condition.
(Cen et al., 2022a) analyze natural policy gradient (NPG) with discounted entropy regular- ization. Natural policy gradient can be seen as form of preconditioned gradient descent. Natural policy gradient effectively boils down to policy multiplicative weight updates using the Q-functions feedback. The analysis of convergence uses linear dynamical system.
Regularized Markov Decision Processes Regularization in RL seems to have a very broad development. was theoretically analyzed by (Haarnoja al., 2018; Nachum et al., 2017; Geist et al., 2019). Regularization helps with both the optimization landscape (Mei et al., 2020) as well as learning policies from offline data (Neu al., 2017).
RL & Regularization in HEFGS and action-value functions not new endeavor. It has been extensively studied from both theoretical and practical viewpoints (Munos et al., 2020; Sokota et al., 2022; Rudolph et al., 2025). Yet, provable convergence guarantee for policy gradient methods like ours was missing. Furthermore. using regularization has also been investigated in (Perolat et al., 2021; Liu et al., 2022b, 2024) to get favorable convergence guarantees to equilibria, to guarantee uniqueness of equilibria and continuity of best-response maps Sokota et al. (2023).
Applying RL in HEFGG, in the sense of using policy gradients
Markov Games
MGs have been extensively studied through the lens of policy gradient and policy optimization methods. For the zero-sum setting there have been numerous algorithmic approaches using multiple techniques (Brafman and Tennenholtz, 2002; Perolat et al., 2015; Alacaoglu et al., 2022a; Wei et al., 2021; Zhang et al., 2022).
25

---

B Further Preliminaries on IEFGSs
B.1 The Behavioral and Sequence-Form Strategies
In this subsection, we investigate the continuity of the sequence-form map and that of its inverse.
Lemma B.1. Under Assumption 2, the transforms ci M1 - c2 M2 - V'y are Lipschitz continuous. Le., for any Hi, p4. it holds true that,
2/H/VA A
|l (W1) - (xiill -
11 1لl1
7
and any p2, Plz
2/H|VB
(T2) - (16)]
11
1221l
y
Proof. We will first observe the difference in e in the (s, a) entry of the the vector-valued mapping:
())
p)(s,a) (s)
(i((,,))
()
(1(s,a)
pi(s,a)
[s)
(1(s)
mi(s)
mI(()
mi(s)
(1(8,a)
(s)
1
pl(s) ph((s,))
Mi(s)
(1(s)
M1(s)
mi(sa))
a)(s,a)
(1(s) - (s())
(s) ps(saa)
(i(s)
(1(s)
As reminder, for all s E S₁ it holds that (1(s) 2 [ desired inequality,
by Assumption 2. Proceeding towards the
(xii)
(
(1)(8, 14(()
14(s,a))
+ 14(()) - mm((s)
(s,, 12
Σ Σ
Ms(s)
(1(s))(((s)
SE81 AEA.
2 (1(s,a)
a)
(G(s) 11(3) (1(s))
+ Σ Σ
14 (s,a)
(1(())
M1(s)
(s)
SESI aeA.
SESIREA
(1(s,a)
al(s,a)
2
(1((s) [4(()) 11()) (1()))
2
+
Σ Σ
(s)(s)
(1(s)
m1(s)
(1(5)p((s)
SES1 a.A,
SES1 REA,
2/H 2
2/7112
Σ
(#1(8, - (s)
+
(11()) - (s))
22
x2
#ES; a
SES, aEA.
2/H
2
|| --11 +
Σ (((s))((ss)²
72
72
sES,
2 mn(s,))
2/7112 72
1|
2
Σ
-
(1)
72
sES,
NoEA.
We need to upper bound the second term by some quantity proportional to || w/ll. We first note that by the triangular inequality.
Σ A.
(1lss) (i((ss
Σ (a((s) (n(ass)
a.A,
VA AAll - -1(-1s)]
26

---

where the last inequality is due to the fact that || - /d Ve E R As such, we can note that,
Σ
Σ
(a(())))
(1(()))
Σ
- (i(1))))
aES; NaEd,
sES;
A
(1((8, (((s,))
#ES aEA.
A |l M1ll"
Plugging this inequality into (1) yields the desired bound.
Lemma B.2. The sequence-fom strategy μ1 (1( is a (DT)) -mmothh function of the behavioral strategy TT. That is,
Lipschitz and
(1c)(T1) - ( & v ((() 1 mill2
|| (T - (Ti)llop VE, I| - -Till2
for any T1, Th, where Je, (.) denotes the Jacobian of the sequence-fon map.
Proof. For the continuity of [41 we observe that each entry of the Jacobian, Je, (m1), is in [0. as product of variables [0. 1]. Further, the number of non-zero elements of each row of Jo, is bounded by the height of the tree, D(T). We can then write,
max ([, (Tp S max |J (T) S (EII((T)
mi
Now, for the continuity of the Jacobian, Jc, (-), we make some observations on the Hessian tensor. In particular, for the matrix corresponding
single entry of μr. with index i, it is the case that all entries are in [0, 1] and are at most D 2 in number. Then, we consider [[V lop
1| E E, (V )) where j, k index entries of TT. this case, by bounding each [E V by upper bound on its Frobenius norm, conclude that,
(V S D(T)?
Lemma B.3. The sequence-form strategy in =x((xx) (v ( Liischitt and (VIE, smmothh function of the parameters of softmax policy Txo X. That is,
||e| (Tx) ci (TTx - $ [V/ Ilx 2
[J (Tx) - Joi (Tx) < 15 - 22
for any X.X'.
Proof. We know that the softmax map is L-Lisschitz continuous and it has 8-Lipschitz Jacobian Lemma D.2. Treating ei (Txx) as a composition of the sequence-form map and the softmax map, we can conclude that,
[xx(Tx) - (((x))l V D(T
1-x111
and
[J,, (xx) Ja, (1x < (VVEE, (2)² + (VI) 8) 11x -x112
166//E -
27

---

B.2 Value, Action-Value, and Advantage Functions
On notation. In this subsection, we will use the following shorthand notations,
01 (h), o2 (h) returns the last history before h where player (player 2. resp.) took an action,
h E signifies that history à belongs in the infoset 8,
h' ET h, žT (h, a) signifies that h' is successor/child node of h. (h, a);
h E & (h, a) E signifies that h, h, a belongs the game trajectory from root to terminal node.
Occupancy measure For policy pair == (T., T2), we define dt S - 10, 1] to be a finite measure over the crfosets-suumet over all infosets & E S yields the depth the game tree for any infoset e S.
d' (s) (oll
BES
The value function of each infoset is defined as,
(x) :=) :BEEa
Σ In(())a(H2 =T (e ThES:hES
NEE
Σ
ENES "o(h) (a (o2)
Also, the action-valus function reads:
(8, :Rew
Σ
rhh) (1,)))
('EE
pa (3) E3
Σ r(h))
Ee Pa (3) (h,
NEEE. L (
We define the advantage function to be:
(T = Q7 (s).
Finally, let policy pair mı n2 and (II, R2). Let क be parametrized by some vector 0. We compute the policy gradient for 0,
av
PT)
00..
00 3.a
8
Olog (E)
Σ (T())
08.,
log क (a'ls)
(T) (5)
1(3h e (h, E
00
113h s: (h, E
m (a' 2 log क. (a'ls)
ΣΣ
(i(E) (S)
(a'ss)
00,a
{
113h E (h, E
@log ग. (d'ls)
ΣΣ
Σ r(h)+ + Σ r(h')
(T(())
(i(als))
(a'ls)
08 s.a
N'Eg LA (h.o)
WEE. N (kr()))
28

---

113h E ah, E (a (s)
ti (a'lss) ① log π (d)l))
ΣΣ
r(h()
(PTT()
00,.a
N'EE
M MMT (h
log (1('ls)) (s,a')
+ (s)
(d'ls)
00
log क (a
= (s)
Ti
(a'ls)
(s,d')
(2)
00 a0.a
Where have used the following fact,
1 113h E:: (h, dh, E Ti (i(s(s))
Ölog क (a'ls)
ΣΣ
Σ r(h')
(a'lsss
00,,a
MEE. Li (h,a)
1 1 Es: 8: (h, d') EE} T1 1i(a' (s)
(1(a11 2 log ग (a'ls)
ΣΣ
Σ r(h))
00 s.a
a²
NEE.
LA (h.aa)
=.O(s)
Σ (as)m (a'ls)
00,,a
Olog (a'ls)
Ti (a'ss) C(s) Σ
00...
a'
C(s) 00..a
Σ (a'ls)
C(s) 00..a
1= 0.
Further, for direct policy parametrization, we get,
ov
3i, (8, (s()))"
For the softmax policy parametrization, (2) yields,
OvT
d= Σ (a'ls) 2 log ग (a'ls)
Q (s,a')
00,a
20.a
dd Σ (i(''ss) [1[a' = - (
= (ss)) v=((s)
B.3 Continuity of the Utility
We briefly consider the Lipschitz continuity of the utility w.r.t. direct and softmax policy parametriza- tions.
Lemma B.4. The utility of an IIFG function as a function of direct-parametrized policies is (ma (1,2) v (E.]D(T))
Proof. Let u:= RpT² It is a vector in R E with entries in [-1, 1], As such,
VT = (17',u)
29

---

from which we write,
V V=L
7
Viima
= V (4f) u) - V (14 u
||||| |x ((T) || aill
En (TT m -/ll-
Where, we used Lemma B.2 in the first inequality.
Lemma B.5. The utility function as a function of softnax-parammtrized policies is 16(max1e11.2 V(TTD(T))
Proof. We treat the utility function composition of the utility function of the policy and the softmax map (i.e, Lemma B.4 along with Lemma D.2).
B.4 Properties of the Bidilated Regularizer
Introduced in (Liu et al., 2024), the bidilated regularizer offers an alternative to the commonly used dilated regularizer (Hoda et al., 2010). It can be seamlessly used along Q feedback by dropping the need of importance sampling which would be necessary for the dilated regularizer when the gradient estimated through trajectory roll-outs. The purpose of this refined regularizer was introducing distance generating function in the sequence-form space that would not necessitate importance sampling.
B.4.1 Strong Convexity Modulus
Lemma B.6. For choice of strongly convex function sb and weighting scheme f (w2,)ees2 and let Oail > 0 be the modulus of the weighted dilated regularizer. Then, the corre- sponding bidiliated regularizer is strongly convex,
Oibi = H
min (e))
Proof. These caleulations were used in the proof of (Liu et al., 2024, Lemma D.1); we repeat them for completeness. For an appropriate choice of weights (wi,))>ess {w2,, >ess, the weighted bidilated regularizer is defined as,
( -1+²)= EnT (o
AhEe
( T1 2z = Σ
T2 u2 (o2(s))
Σ (oo(t))3((1((1))) (2
hES
We can slightly refine (Liu et al., 2024, Lemma C.I) order to compute an explicit lower bound on the convexity modulus of different weighted bidilated regularizer depending on the choice of th. From the fact that R₂ (uT', (1")) linear in nz² and the definition of the Bregman divergence, we conclude that,
(V(1 + (1) 212 - ((Ri + R2) 112) (1TT,, ,152) (1i, ,112 .112))
BRi (MT² [ + BRi (1T m6²²) + BRS (1 ; + BRG (1t (18
By (Liu et al., 2022c, Lemma D.2) we know that,
BR [1] x 11 1
min pe (h) Beil (u (1r 7 min (h) Gai-
HH
As such, for the strong convexity modulus of the weighted R relative to the choice of norm appropriate for sh, we write.
Obi
[70
30

---

By (Farina et al., 2019, Corollary 1), we know that there exists weighting scheme, such that the Euclidean dilated regularizer is 1-strongly convex w.r.t. the no-no.. The procedure assigns weights to nodes in a bottom-up fashion.
At each leaf node the weights are
W1,+ 1.
For an internal node let Sa S...... denote its child nodes under actions d'...... For each action a, compute
W1.s.
Σ W1,5'
(sEa(s,))
The node's weights are then set to
W1,s
2 max W1.s..
Corollary B.1 (Euclidean Regularizer). There exists a choice of weights, with max; Wis. max, W2,s = ((2D())), and under the assumption that min, p2( 2 % the bidilated Euclidean regularizer has strong convexity modulus w.r.t the E--norm, Obi.
euel Ob
Y min (c(h).
H
(Kroer et al., 2020, Theorem 2) states that a recursion defines weights with max, W1.s, max, W2,a ((2P(T)) such that the entropic dilated regularizer is strongly convex w.r.t the fn-nomm. Corollary B.2 (Entropic Regularizer). There exists a choice of weights, and under the assumption that ming (s) 2 % the bidilated entropic regularizer has strong convexity modulus w.r.t. the to-n Obi-
Oi
min (h).
H
B.4.2 Lipschitz Moduli
Here, we establish the Lipschitz continuity of the regularizers and that of their gradients.
Euclidean regularizer
Lemma B.7. The weighted Euclidean bidilated regularizer is E-smooth with
:= θ 2 D(T)
E. (()))))
max (E(1.)
Proof. We write the bidilated regularizer as
R (TI, T2) ==
For fixed n2, we have
v Rouel (Ti m2) ( (2) g((=)) + (T)) f(T,
where, f(11, (()
E RIम with f(T1, T2) Enee (o2)) and
(m))) = w1,- || (1
We write:
V Roucl ( π2) V,, Riue m2)||
< ( -(()]
+ [|
I ( s(=i))
e max [|g( +2
max
|| -
zi
< lyvs + 2L + lo (VVS)
||
31

---

For we see that Lg := VS max, W1.s and Eg := 2/S max, w1,s by the properties of the weighted norm and the fact that n (-Is) lies in the simplex, i.e., (-|s)) S Also, the weight wi,s only scales the local quadratic term.
For f. similar to Lemma B.2 and Lemma B.4, Ly S maxie D(T) and & - (1 (E) Also, it holds that max my [1 S S.
Concluding,
V R1 Riuc T2) - Vn R1 Ru (Tí, m2)l| S 64 max wi,s max
[ =
(E(1))
Symmetrically,
V x2 R2 Ruul
(T1 m2) S 64 max w2,s max (TL, T2) n2 Reuel
(E(1.2
Now, we need to bound the Lipschitz modulus V R2 (TL T2). Similarly, we write,
R2 T2) = (f n2), ((2))
We that the the vector [(m T2) (occupancy measure of player 2) has entries that products of entries of f1 M22 Me. Hence, L (1 |> (D))) and é max,2 [C))SS) (TI,
|| v,, R2 (T,, T2) - V R2 cuc (2), S || (mI, T2) - ( -2 (1 [|9()2)]|
s max [E. | - m|| [1)(m))
xE(1.2)
max 22,3 max
Σ D(T) ||| -1
(1,2)
Entropic regularizer Lemma B.8. The weighted entropic bidilated regularizer is E-smooth with
E := θ
2(T))
max [EI (e(1.2
Proof. We write R2 as the inner product of [T(xx := x and = [No log no (b)))] For
notational convenience, we suppress dependence f.g on ne.
Rx(xx)= (f(xx: ne), ((TO)))
We now bound the Lipschitz modulus of the gradient using the chain rule:
V R2 To) V R2 < (x) ( - Jx(x') (xx))) [[((=))]
(x) (Tx) - J= (x(x) J, [x) J (xx) - Jx(x') Jy( [(o(=)))
< (()+( ( J)(Tx)) [ (x+(x) (x)x [19(TT))
< (2) max E. D(TVV + 8 max sE(1.2
E D(T)S
S max W2, l|x - x111-
(E(1.)
For the Lipschitz modulus of V R, (Txx To), we re-purpose the lengthy calculations found in the proof of (Mei et al., 2020, Lemma 14), we consider = + ar for some E IRA a E R,
dg(x + au)
max 1 log |ulli;
da
hence, (since ||0||2 < VST |
dg(X + au) da
< max W1, log AVS |1ll2
32

---

or, Lg max, w1,s log Avs. Similarly,
d (x + ax))
max (1, + log A) ||ul|2:
da²
and, as such,
d gx + aa))
< 3 max (1 + log A)V5 [wul2:
d
or, Eg = 3 max, 11 + log V. Hence, V R1 is Essmooth with
8 S max w1, log A
(T)) (2) 8VS
max
E
D(T) +
(E(1
+ max W1,5 (1 + log A)vS 2 max (E(1.2)
| D(T) max 11,s log A AVS
< P(T) max Ni / (E(1.2)
33

---

C Efficient Exploration
Throughout our proofs, we have kept our complexity results parametric w.r.t. 1/y, A naive exploration rule that would dictate that the player merely picks behavioral strategies over the e-truncated simplex will give a 7 = O(eP()). We propose different approach to exploration. In particular, every player is expected to reach every prefix subsequence with probability |ity where Σ := 1 + Eees, [Aa)
denotes the set of all possible "prefix" sequences player The rule is simple.
at the beginning of each game, the player throws a biased coin which lands on "heads" with probability 7 If so happens, the player executes sequence of actions with probability pAl Afterwards, the player continues to play according to their own behavioral strategy.
In the case that the coin lands on "tails", the player simply plays according to their behavioral strategy.
We observe that in sequence-form, this means that (1(((()) 2 [9g1 + I&t EvES, 1fs' žt s} (in words, the amount of pprobability flow" reaching the corresponding sequence (s) for s, is at least as much as [Σ.T plus the flow that passes through (s) to visit its children). other words, the sequence-form strategies truncated by set of linear constraints and long 7 S 1. there set of feasible sequence strategies non-empty. We now observe that the mapping, from μa to the part component of the behavioral policy the agent can in fact control, is
T(als) = 1u(s, a) 1E11 EvES, 1 Ir (8,
((((s)) En EvER, 11s' =T
The "probability flow" passing through the edge (s, breaks down controllable part due to the policy x[a|s) and an uncontrollable one due to the exploration scheme. In particular, the 3 Evex, 1 =T (8,a)) proportional to uncontrollable "prohability flow" is precisely ΣРi
the number of nodes of the subtree rooted at the next node after (s, a) where player 1 acts. As such, the Lipschitz continuity of mapping j + n, is Lipschitz continuous with a modulus,
EglVA
by following the same line of arguments as the ones in Lemma B.1.
In short, we are only adding an additional linear constraint on the feasibility set of 1T (and p.² respectively). Granted that that this new feasibility set is always non-empty, this y-truncated treeplex remains a convex polytope. Finally we note that for any player i, |Eg] S [7]]
Proposition 1. Let I be an n-player imperfect-informatiee that players follow the exploration scheme of Assumption 2. Then, an e-NE on the exploration- induced 7-truncated treeplices, is an (e 2[1 (1 7)" -NE of the original game.
EFG T with perfect recall. Also, assume
Proof. Let :h" be a joint policy profile, V will be the utility of player under no exploration under joint policy n² and V the utility of player under the exploration scheme. When the exploration scheme is followed, there is still probability (1 - -))" that no player follows it for particular episode. Hence, for any n²,
VI
$ (1 (1- (ri (rimiu))
$ <11 - ()),
where, mam Timmin signify the maximum and minimum value of payoff r, for player i. With the
same line of reasoning, maxx v. - max,; Viya vー < 1 (1 > Now, assume {Λī hejs to be e-NE. Fixing player we want to compute the difference in the optimality gap on the y -ttunccte treeplex versus the entire treeplex. Now, by definition the eNE,
max
p/ 73
V 3.
Sc
max
V
< 2 - (1 71-
When = 2, 2 -(1 = e 47 222 = +)).
34

---

D Regarding the Policy Parametrization
D.1 Definitions
Direct policy parametrization. Both players parameterize their policies (or behavioral strategies), Ti :1 A and T2 S2 B, using a concatenation of S and [S&] probability vectors over the (potentially truncated) probability simplex ((A)), (B,) for all in S and S2 respectively. The parameter space of player 1 is denoted by X == ILes, A(A)), while the parameter space of player 2 by y = Il.es, ((B)).
Softmax policy parametrization. Softmax parametrized policies have well-known definition. The parameters of the corresponding policies are denoted X, with x E RA, Σ, Ag and E R == E,
Bg. For each infoset s, the policy is
exp(Xaa) En exp(Xs,r)
exp(Os,0)
x (a(s))
or
To (b(8)) Ev exp(0x,b)
Now, since we want to have control over the minimum eigenvalue the Jacobian softmax( ) we restrict the parameter space to the following convex polytopes.
Xx {x R. A =
Σ Ag x! 0, Vs S1,1xe.s Xayl 2R, vi,j E [Aal]:
On R B BB 0.1 = 0, 8 10.. 0nyl S Vi [B.1
BB
D.2 Properties under Parameter Constraints
Lemma D.1. Let = Joftmaa (0) E Rdxd be the Jacobian of the softmax map. Its matrix form is:
J = diag (softmax(0)) - softmaa
Further, the vector is an eigenvector of with corresponding eigenvalue 0f0. O. The rest of the eigenvalues are
A E
min softmax;(0)) max soft
je|d
ie|d
Proof. For brevity, define softmax(0), and let diag(r) be the d x d diagonal matrix "whose diagonal entries are given by E Rd.
= diag(o) aa
First, we observe that the all-ones vector Rd is an eigenvector of J with corresponding eigenvalue of 0,
J ( 0 )1 = =
By Weyl's inequality for two Hermitian matrices, A, B, we know that their eigenvalues indexed in descending order Å₁ (A) 2 >a(A) satisfy,
A + B) < ((A) + AB( S A B).
(ddiag()) = of while >a(-or T) = - | = [-1, ] Hence,
X (J) 2 mingeld (0) - by taking and j = 1;
o < Amax (J) S max4eld (0) - by taking 2, for the LHS and i 1, for the RHS.
35

---

Lemma D.2 ((Zhang al., 2021, Lemma 5.3)). The softmax map 8-smooth.
Lemma D.3. The softmax map, softmax : IR + R has an 3 2 smooth gradient.
Proof. Again we use == softmax(() for brevity. We compute the second order derivatives:
d² ①
00 0, 002 (oi( - r,)]
(0 (ō.j -)))-o;0(66p ok).
Every term is function of and it is true in general that [f(0) ( h(0) f(6') ((0)) h(0') (f()) f((') lo(0) [n())] + lo(0) 9(0') If(00) (h(0)
As such, can write,
8²
82
(0)
(0') 33 110 0'1l2
00,00
00,00,
Lemma D.4. Assume Rd with 0 E OR = (0 Rd 0T and 10, 10,-051= 5.1 2R, Vi,j E [4].
Then, the following bounds hold true,
minseld softmax;(0) 2 1)
m softmax;(0)
Itd-l1je 2R
Proof.
Minimum probability lower bound.
W.l.gg. minimize the first coordinate. We write,
1
Σ c
1+ Ei>i cb:
By observing that,
01-01 S max maxx"0- 00
)
We can lower bound the value
0
Σ,
1 (d 1) max, (
suffices to maximize the quantity mf , (0; 01 as the RHS quantity non-increasing in max (0; 0,), ). Le., the largest difference between two coordinates of vector in the sphere 2R. The minimum achieved when f2 - 81 = 2R and O, = 6k. Vj.k l 2 2.
Maximum probability lower bound. Similarly, w.l.o.g, it suffices maximize softmax, (0) for
0 E OR.
11
Σ, 9 Φ
Eips e0
2
<
Φ (d 1) 2.,00010 b./dd-1)
36

---

where the inequality follows from the convexity of c². For any 8 E OR the point (0) (01,... ....... is also in 2n due to the convexity of the set (it is linear polytope). We can simply optimize the objective,
max 0,6 1 (d 1)
s.t. |a bl _ 2R.
Due to the objective function's monotonicity a, the program can be simplified even more into,
min b - 0,5
|a bl 2R.
Finally, it is clear that the last objective is minimized for a b = -2R. Letting & S (d - 1)-2
In this vein, if we want to bound the minimum probability of the softmax parametrized policy by 0 for some R max softmax;(0) Z --ete(d-ry
need to set R s 1/2 log ((d-1)) Then, it is also the that
E = - 1)²
Proposition 2. Let p be probability vector d and define ((p) be the set of such that softmax(f) = p. For any two 0, 0' E (p)), there exists E IK such that 0 O' + cl.
Proof. By assumption, softmax(0) softmax p. For every entry
e%
pi
Σ,e 60
Σ
6
Letting Z: Σ/ ,
7' = E. we observe,
e
7'
c
Z
Z'
0: = 8 + log
Vi fl.....d].
z
Hence, any two 0, 0' that map the same probability vector translations of each other in the direction of 1.
Proposition 3. Let p E A probability vector and the set, 0(p) of vectors TRd such that softmax(()) ()) = p. For the vector 8* = arg mingge(p) ||0]| it holds true that,
1 T0 0.
Proof. The set 0(p) takes the form ((p) {0; log p: c) ICe R] (0, cl R} for an appropriate choice of Og. Picking an arbitrary 0g E 0(p) to use as a reference, we can write the problem of minimizing ||0]|, as,
min #EA(P)
||0| 12 = min 10 cll min ||0||] (0o, ||c1|]².
CER
cER
By the first-order optimality conditions, c = - Plugging back this for 0*, we see 6* 0. 1 1). We see that, 1 T 1 T 1 10110
Lemma D.5. Assume a fixed < < oo and define the set OR to be On = {0 E Rdd 0
0 and 10, - 0,1 < 2R, Vi,j E [d]). Then, softmax (R) is convex set.
37

---

Proof. For any Ad-1 for which e
2-2 2R < S cR2 vi,j E [d], there exists 0 E 2g such that P5
softmax(() = p. To see this, we apply the logarithm on the inequalities.
2R E logp: - log Pj I 2R.
(3)
A vector X with entries X := log Ps clearly implements p. By (3) we see that subtracting max; log p ming Pt from all entries yields softmax-equivalent vector X log P. with softmax,10)
- -R X S R. Conversely, for any 0 E OR e e < softmux, S e2n
Now, the set defined by the inequalities p Ad-1, 2n R < Bi S 2R clearly a linear polytope and as such, convex.
E Gradient Domination
In this section we prove the gradient domination properties of the utilities of the game with different policy parametrizations. Further, for clarity, in place of V we will use V, (x; y); and in place of x will use 0).
E.1 Direct Policy Parametrization pPT.
Lemma E.1. The utility of the game regularized with the weighted bidilated Euclidean regular- izer with a weighting scheme defined in Appendix B.4.1, 1, satisfies the pPL. condition for directly parametrized policies,
T minng (o(h))²
1 [V-(r,u) V+(*",
Dx (x(x, (;1);
101/7//3
2
T ming (c)
1 [V, (z 1 D (y,
101
Proof. We write the utility function of the regularized game,
Heuel (p1, (12) = (1,, R422) TR (11, U2)
TRgucl (2),)
For player know that the function Heucl is strongly convex with appropriate weighting scheme ( (correspondingly { for player 2),
H (1h P2) 2 H (m), + (V H. (ui, (n1, - -mi) +
Tah
eucl
||
μ2 l
2
Strong convexity implies the KE condition for μl. In turn, using the bound the Lipschitz continuity modulus of the map 11 + x,
Heuch (ni, u2) - min Hrreeel (m1*, .12) <
2 |100
1
2
encl bi
[d
Now, we know that ai
ming (e( H
(Corollary B.1). The conclusion follows from Lemma G.2.
E.2
Softmax Policy Parametrization pPE
Lemma E.2. The utility of the game with sofimux-parametrized policies satisfies the two-sided PPL condition,
T min, 3
[V> 0) v=(x*,0)] 2 Dxa
101 + (A - 2
T min, (h)
1
201 + (B- - 2R [V 0-) -V() < De (0,
where l is the smoothness constant of the softmax- utility function.
38

---

Proof. The main challenge in proving this lemma is the fact that the softmax mapping is not bijection; this is manifested with a rank-deficient Jacobian of the mapping.
Concretely, from (4), we know that the Kt.-condition holds for the policies. What remains to show is that the Kt.-condition also holds for the parameters X (and 0).
For some 0, let XR = softmax(Xp (R)) be the convex set caltmax-parametriized policies where
XR 0 R A Σ. As x 0, vs St, Xx,i X+Jl S 2R, Vi,j [A.]]. By
overloading notation, let ( No) be the loss function of the minimizing player function of policies xx; va and V(x.0) 0) the utility as a function of parameters X, 0.
Now, we note that the subgradient E Ōzy (V (V To) + Lxx (Txx) that minimizes |||]| is such that s So when picking norm-minimizing 8, it suffices look at the set of subgradients that perpendicular to 1. Further, the chain rule applied on (TTx: TO) + Ix (Tx) yields,
0x (V (Tx: Re) Lx (xx)) S J() (V, (TTx TO) O2 Lx (Tx)). Moreover, we note that by the symmetry of J(x).
(5)
[Jx)s||2 = s J() J(x)s
2 A (J()) (x))T((x))) J(x) ||s||
(A (J())) ||s||
(6)
From inclusion (5) we infer that:
min wrB (V(= + Ix (x)) ||w|| 2
min =EJ(X( (o) 1x (Tx) ||ill
Lemma D.4 provides the bound A min (J(X)) 2 1-(B-Ijaa8 and the conclusion is proven.
E.3
Mahalanobis-pPt.
Lemma E.3. The utility of the game with soffmax-parametrizze policies satisfies the two-sided Mahalanobis pPL condition,
ming p
[V(X. V=(x*,0) 1 Dx (x,:0)
101 Amax MM- ( (A - 1) 22
T minin (o(h)
101 Amax (M 3/7/3111111111111111111111 + (B - 1)e2Ry2 V+(x. Vx s - Dap (0, (:x).
Proof. We invoke (6) and the fact that 2- 2 A (M-1) ||w|| for any (w, v) = 0, Ve e ker (M-1). Also, we use Equation (e-trunc.) and Assumption to bound A (M (M-1). In detail, we know that,
31 (A- 1)=)
min (V (Tx))
- ||mm| 2 -(x,))-((x' V(''
minA po(h)33
72 minn (e(h)
When M : F(x, 0), it true that
Amax (F(x,0)) < 1.
17
The spectrum of the Fisher Information Matrix we can conclude that,
With the same arguments used Lemma D.I,
Amin (F(x: 0)) = 0:
min (F(x, 2 d(s) mina (x(ss));
(x) ming, Tx (als)) < Amax (F(x, 0)s) S dx max, T (x s) + 1.
39

---

Hence,
min (F(x, 0)) m xx (als);
mine u. [HP
S Amax (F(x: 0)) -
Moreover, (s) 2
12 ming (k(h)
by Assumption 2.
E.4
Weak Gradient Domination
We now conclude this section with proof of the weak gradient domination condition.
Lemma E.4 (Utility Weak Gradient Domination). Let be an IIEFG satisfying satisfying Assump- tion 2. Then, it holds true that,
V min V
32 v
max (V V 21 - -m1)
20x
1
max TT
V0 S
V mT/ -T2) max (V
20y
for Oz V2|H|
and Oly VE
Proof. We use (Fatkhullin al., 2023, Prop. 2) by using the fact that the diameter of the treeplex is most A/ and the fact that the Lipschitz of (T -> Th is VA
Then, the fact that
(Vf(z), y) m ||w|]| ?
Gradient Estimators
In this section, we demonstrate that the well-know stochastic gradient estimator, REINFORCE, can be used yield an unbiased estimate bounded variance of the gradients of the non-regularized and regularized imperfect-informatii game.
E1 A Policy Gradient Theorem
We define trajectory
be sequence of consecutive history-action pairs,
(M (i (1(2), ((2))... ((2))....) )....). The length of trajectory is noted as Kg and it is bounded by the game-tree's 's height, D(T). We define K. to be the set of all trajectories and note that it is finite. After policy profile, (I), m2), ). fixed, the probability of each trajectory K. taking place the product of the probability of each consecutive action,
(2)
Ke
T (E)
II TI(R) (a (G00)) (1
where i(k) denotes the player that takes an action at timestep k. Lemma F.I. Under the assumption of (e-trunc.), it holds true that the gradient estimator (REINFORCE) is unbiased,
[ (2V(TT,T)), and Bewny V V V (TI n2);
E m2
and also, its variance is bounded:
D²D
1 VVV(T,, T22
E
B BT)
| V,V(
E E
where A, B denote the maximum available number of action in any infoset for player and respectively.
40

---

Proof. We first show that the gradient estimator is unbiased. Indeed,
(eV( = Vx (E)
(E)
EEK
Σ
rE V. xr IpTI..I (5)
SEN
Σ SEK
Th Pe V. x log I (5)
K₁
Σ SEN
re
P (S)
V log T(()) (a In (11))
k=1
Kt
Vx log (()) ( (8)
(2(k)) nb(t))
re
Kg
v. log πं ((8))
rE
The proof for v y uses an identical argument. We will now proceed to show that the variance of the (REINFORCE) gradient estimator is bounded:
Eg
4 z E
S
E
Ke
Eg
x log कe (a (a( (((0))
K₂
v log Ti (alt))s(3))
< Eg
km
Ke
v log क (a (200)) 12
< REg
Ke
k=1
K2
S E(
Σ
Vz log I (a |s(0)]]
Am1
K2
= D(T)
Σ
1(8 = s(k) a = (44))
क8 (1)) (10)
k=1 5,a
K₂
= D(T)
Σ Σ 1(s = s(b)
(a(s((())
A=1 9,a
Ke ΣΣ 1(8 118= S(0))
A
< D(T)EE
k=1 a.a
Kg
A
D(T) Σ p (E)
Σ 11s {(k))
EEK
1=
5.a
41

---

AT)
8
Lemma F.2. The variance of (REINFORCE) for seflmaxxpurametrizzd policies bounded as Tg ox I 2D())
Proof. We see that Vo log nT(aas) Cs.a (-1s). From then on, Vo log no (a|s)]l S v2 with probability 1. Then, the proof follows arguments similar to the previous one.
L
Policy gradient the bidilated regularizer regularizer, Vz R1, as:
We define the policy gradient estimator of the bidilated
Kg V RRR1 = Σ (TT (s(tt))
K V log Tı (a (o()))((0)) +
Ke
>
v ( (s())))
We will demonstrate that this gradient estimator is, in fact, both unbiased and enjoys variance that bounded. We start with preliminary proposition about an alternative expression of the regularizer. Proposition 4. For a policy profile T1, T2. the bidilated regularizer, R1 can be alternatively defined as:
Ke
Σ v (m (1(11))
R1 R1(11,
Σ SEK
(E)
Proof.
(1(,, Σ
1 (o(s)) Ema(hiy ((T(()))
sES1
hEv
|PT1.T2 (s))((T((5))
sES
Σ E
Σ 1(8 (000 (((((()))
SES,
Eg
Σ
Σ 1(== ((((((()
SES1
K₂
Eg
Σ
Σ
1(8 S(H)
sES
K₂
2 I (1(11))
Eg
Σ ((m (11201)
Kg
p
(E)
SEA
With the latter expression, proving the desired properties is easier.
V Ri (TI, T2)
K₁
V (E)
Σ 2 ( (S(()))
SEK
42

---

K2
Kg
Σ
V mm (E))
Σ
26 (m (m(()))))))
Σ EEK:
pm (E)
V
/ (Ti
(s
EEA
Kg
[Pa), (E) x log (p
Σ (Tz (s(A)))
EEK
20
Kt
+ (E)
( (T)((1))(()))
SEK
For W1, let us denote rgg = Ex 2/ ( (s(K)))
1
rg
pan..2 V
z log pa (g)
EEK
Σ EEA
re Pe V log
Ke
V log (((k) (o/(k) (n(())
rg
SEK
k=1
Eg
TE
(k) log T((k)
(a(()) (k))
Ke
V 2 log (2(4))s(t))
TE
For 22 we write,
Ke
5 (E)
Σ
V ( (11 (s(tt))
202
EEK
Kg
E
Σ
V tb (T (3(A)))
k
We will use similar arguments for the variance in the case of the (REINFORCE) gradient estimator.
6 R, - [E(RRR1111 11
E R 17
<
2
K5
EE 2
Σ 2 (s(1))
V R log क. (10)))
+2
Σ
2b (
(5((1))
02
For 8,, similar Lemma F.I, we see that
A 12 max D(T)²
E 2011
43

---

Whereas, for 02,
Kg
V (((0))1) /2
|[ S E
KE
Kg Σ 2 E
< ( E.
Finally, note that when Assumption 2 is followed, then (REINFORCE) is also unbiased estimator of bounded variance (same bounds as previously) of the perturbed version of the game. The reasoning is the same (when a player exploring the gradient of the probability of an action is zero) and as such we omit it.
44

---

G
Optimization Lemmata
Definition 6 (Stationarity Proxies), Assume a function F f + Ix such that R
E-smooth relative to Il and (x):) is the indicator function of the set X. We define the following stationarity proxies,
gradient of the Mahalanobis proximal mapping (MPM),
(x == /² 0||0 prox pr (1x) (4))
M.
with pro arg min (F(x') + 2 x' lim)
Mahalanobis gradient mapping (MGM),
A (a:) 0² || xt 11 I...
where x+ == arg min ||= - PM (
Mahalanobis
mapping (MFBM),
D)x,p)= -20nin((V x) -1x-= + Ix(x') Ix(x));
Lemma G.1. The following properties hold true for the proximal point and the Mahalanobis Moreau envlope,
VFp(a)= = 2/(x (zx -2) 2)
dist(0, (F()) S [VF(())
F()) & (a) S F(x)
Proof. The first and last items follow easily from the definition and standard arguments (Davis and Drusvyatskiy, 2018). The middle one uses the optimality condition of à == prox,F (z).
0 0 F(t) + M -x)
p
from which we conclude,
M - 2) OF
Finally, we conclude that minggE0F(2) ||02 2 M-- 2 -
Definition 7 (pPt., Kt.). Let S X + RR an L-Lipschitz continuous function with E-Lipschitz continuous gradient. Then,
Proximal Lojyyk--ojasiewicz (pPL): f is said to satisfy the proximal Polyak- Malyak-Lojasiewice condition 3o 0s...
Dx(x, 0) 2 [f((x)) f(x))
Kurdyka-t.ojaseviicz (Kt)): is said to satisfy if 3 s.l.
min
|| 2 26 [f(z) f(**)), Vr E X.
# =0((++))))))))))
The definitions for the Mahalanobis analogues of pPL and KE follow straightforward extension.
Lemma G.2. Let I be an f-smooth function relative to Il-ll defined over the convex set X. If ʃ satisfies the (Mahalanobis) KF. condition with modulus ona, also satisfies the (Mahalanobis) pPt. condition with modulus of appl
45

---

Proof. First, we define F(z) := (xx), with Ix(-) being the indicator function. We highlight that since (x)-) is convex and f is ê-smooth (relative to l1-l)x) then F' is E-weakly convex (relative to || Ml.) This means that the proximal point of the function F/p is well defined for any p > L. Now, assume a point a E X' and ã = proxF/p(00 (x)). By assumption, for any I E X, it holds true that,
|| 1 2 a ( 17
2
where 8, E @f))). The latter implies that for the gradient of the Mahalanobis Moreau envelope of F, it holds that,
2 (F1//())) M- - -r
=a+alf(8) f(x))
( D(z, p)
L
2ai((z) - 22
11 i Ill
(7)
2
where (7) follows from the fact that F is an Ê-weakly convex function, and for every 0F(x). To this, write that due to weak convexity (relative [1-I
F(#) 2 F(x) + (v, 5 - x)
2 | =lli
L t+p
= F(z) + (v, 8 - 2) +
|| 211
2
2 F(x) + min
V [V]()), y - x) + || yll }
e+ P
1 - -1
NEY
2
1 p) t+ | 11
F()) 2p
Collecting the terms,
l l+ p) + (o+
[F)(
((z.)))zaf(a f*1. 2p
2p²
A direct generalization of (Karimi et al., 2016, Lemma 1), implies that for the MFBM and choice of P1,P2 > such thatp1 P2. then P(x,P1) 2 D(x,, As such, we write,
(+p) ( + 2p²
D(z, 2af(2)) ff
2p
We can pick = 46 which then yields.
(1
1 12a
+
( M + - a()()((()) - 1*).
2
e
8e
Observing that in general, we re-write:
25
1 + + [=)
2
Now, from (Fatkhullin and He, 2024, Lemmata 4.1 & 4.2), we know that,
16D (r, 40) 2 /
which we plugin in the former inequality finally conclude that,
D(z, 40) 2 # - 1(x)) -
Remark 3. The latter lemma provides a bound that is significantly tighter than the one implied by the analysis found (Karimi et al., 2016, Appendix G) which connects the moduli of the KFand pPLconditions.
46

---

G.1 A Variation of the Descent Lemma
The following lemma is a consequence of the three-point identity of the Mahalanobis norm and the smoothness of f.
Lemma G.3 (( Reddi et al., 2016, Lemma 1)), Let f f - R be an E-smooth function relative to Illl,x, and point X Rd. Also, define the vector R and E X to be
y = Proj (x - (.n,M--'u X.M.
Then, the following inequality holds true:
f(y) S f(2) (Vf(z)-0; 2)
#/5
1
11y
x1| M. 2 2+
8
|| -x1lm
1 2 1ly =IlM.
2n
2 21)
Lemma G.A. Let X' C Red be closed convex set, and let f X -
TR be an f-smooth function
relative I1,1lm, for some O. Suppose n O with n 5e- For any x X and any vector
v E Rd, define x Proju,, M, (x - mpo). Then the following inequality holds:
f(x)) S f(x)
7 (x 1/n) + 2 [V[(z) - ullM
6
Proof. First, we define x+ == Projx,M, (s- 1.-M, (M,,
Invoking Ê-smoothness relative to |I-IIM. of for x, x4 and assuming p > 0 with p 2 t
f(++) (Vf()) - x) + 2 | x M.M.
5)(x) + (V)(2) x4 x) + l 1 x Mr
-(x) (VV)(x), x 0 |,+ x =l/M)
= f(x) 2p
DM, (I, p).
(8)
Invoking Lemma G.3 with x = v. y Et, 2 = V, U fx()))
l
((x+) < ((z) 2/2
| ==|3,
(9)
Again, invoking Lemma G.3 but with x = x. = x+ , 2 = F+, u,
[(x+) < / (T+4 (V](x) u, x+ I+}
+ 2 1 ||+ - 2l/,, (
l 1
1
+
|| =1122.
1
I+ 1 I..
2m
2n
21
(10)
Combining the previous inequalities 1/3x(8) and 2/3x(9), and letting 1/p 17 1 yields,
f(z))
Dx +
2 2 | -x1/2/
6n
3n
Adding (10),
f(x4) < f(z) - 6 Dx 1/n)+ +
(5
(
| - x112a.
3m
47

---

+ -V,( - 0, - -I+)
+ +(2 2 21/
1
l
1
1
12+ - -x1i; +
+
|
1|
2+
ll
2
2n
2n
f(x) - " (xx,,,111) +
5l
1
|| 2: liM.
6
6
6r)
1
[V)(z) - -ullM
1
- x+ 11/m
2
2p
L 1
1
10+ x1 N.
|
F+ 1l..
(I1)
2 2n
21
f(z)
Dx(x, 1/n) +
(6
56
1
||
l..
6
61/
"
- M,M-
l
1
|2+ x |
2 2n
f(x)
"
+ 2/2 [V ullM,
(12)
(11) follows from the application of Young's 's inequality on
(vf(=) - u - M, -MM,-1/2 f/2) - v, M, 1/2xt - x²)
-x+)
(12) follows by dropping the non-positive terms; non-positivity follows from the choice of the step-size, S 52-
G.2 Min-Max Optimization
Lemma G.S. Let J : x y be an E-smooth function, p > O, two points y: 1/ E Y, and a point
E X. Then, the following inequality holds:
(Dx(x, Dx (x, (xxx)))))) 3X (M, 11y y y
Proof. We define F,F' E X be:
= Proj
M, -V (x.
X.M.
E' = Proj
I
M, "a.i'va(tee (2)(2.)))
X.M,
By the definition of D (I, p: we write:
20 1Px(xxppV) (Vf(x, -
f 1| F M.
Dx(x,P.))) = (VI(z, -F' $ || F M. 2p
Considering the difference Dx Dx that:
(2x(x,pi)) - Dx(x,p:1)1 2p
= <VV(f(x)))) -
V.f(z,))) x²
P [|e x Il.. 1|
x' 2(1
2
48

---

IV (V.f(z.)) vof(e. x) P
(1 [1x- M. 1| z'lin.)
/.,, 5) v.I(I, x) | x z'll,2.
P
V.,((,, v) vas(e,)))ll M |
x
P
|| - Ft' ll..
2
1
(v,(()))) y) v.f(2, v') MM
[v - y''
2p
Ammax (M |V=f(z.)) vaf(z,
Amaz (M.')
vef(z,)) v=f(r.)/11
2p
3Amas (M, 366
11 1'112
2p
We note that:
The first inequality follows from the triangle inequality.
In the second inequality, we applied the reverse triangle inequality.
The third uses the Cauchy-Schwarz inequality.
Finally, the second to last uses Lemma G.9 while, the last one, invokes the é-Lipschitz continuity of the gradient.
Lemma G.6. Let f: : X x y be an E-smooth function such that for any x X, f(x, satisfies the proximal-PE PL condition with modulus 0. Then, the function 4(x) := arg maxyey fa, v) is t.-smooth, with
4 e
Proof. We effectively need show Lipschitz continuity of the maximizers y-)+) := arg max, and the proof will follow from Danskin's 's lemma and f's own Ê-smoothness. So, we write by the quadratic growth condition,
1l (x') (x)) s(,,))) f(x,,((x')) (
(13)
We denote Dy(-, x) == Pt. condition, we write.
y) lly - =21²² and by the proximal-
f(r - _ Dy x)).
(14)
2a
Now, we aim bound (y (2) by (1v((x) vz2'111 We observe that,
4x)) = 0.
Hence,
(z'),,z)) = Dy (z)), (()))(())))))))))) 26 2
(x)
(15)
where the last line follows from slight sharpening of the proof of Lemma G.5 (for the function My, = (sx, and M = I). Finally, piecing inequalities (13), (14), and (15) together,
(o= (2')) < ||ا - ='1l-
(16)
What is left do observe the following, due to Danskin's 's theorem and é-smoothness of f.
V ((x) - v. [V.f(z.v
V v2')'"
49

---

< (x)) (z'))]
l | z'
|| x
The latter inequality follows from (16) and completes the proof.
Lemma G.7 ((Kalogiannis et al., 2025, Lemma D.3)). Let f : X y an l-smooth function. Additionally, assume that f(-,y) is aw & Pe-p for all y y and f(x," is ay- all E X. Then, holds true that:
min max (x, y) max min fa, y). yEY DEA
#EX yEy
Lemma G.8 ((Kalogiannis et al., 2025, Lemma D.4)). Let f : X y an l-smooth function. Additionally, assume that f(-,)) is or PPt all y E y and f(x," is ag -Pt all x E X. Then, the function ((x) == maxxey J f(x, y) aPt.
G.3 Regarding the Mahalanobis Distance
Throughout, we will refer positive-semidefinee matrix M E RRdxd and its Moore-Penrose pseudo- inverse Mt E Raddd_ Although general a PSD matrix cannot define a distance, restricting æ; TR such that (xr - y) ker(M)- then ||x - -yll := (æ y) MMM - y) satisfies all properties of metric. As we shall see, this seemingly arbitrary assumption is satisfied for every pair of consecutive updates of natural policy gradient steps. The matrix deffccefiiennt matrix we are interested in is policy gradient Fisher information matrix, and for softmax policy parametrization, is rank deficient in the direction Rd Further, the gradient fx) as
Proposition 5. Assume that 0g = 0. Also, let un = 0, AI E (1,2,3,... Then, setting 0.+1 02 1/M U; guarantees that,
(0t+1 0,) 11 and 0,1 = 0, Vt.
Proof. Since, Oct1 = 0, r/ ut, we see that 0,411 = (0, - 1/M vt = and (0.+1 - Oz) T
Proposition 6. Let θ S R be convex compact set. Assume that 0o 0. Also, let v/ 1 0, Vt E (1,2,3....) J. Then, the following minimization problem has unique solution.
min s. (P-0.) T 1=0 [1 n/M vz) Oll
Further, it is equivalent to the minimization problem,
min 000.a.1.0-0.)
(ve, 0 - 02) + 2n
10 0, 1
Proof. It is clear that, for 0, 0,0 T the function ||0] M.M.. 10 xI1 is strongly
convex in 0. Hence, both problems attain a unique minimum.
For the first problem, the first-order optimality conditions for the write,
(Ø+ (0 m/M vx) 0-) 2 0, 40 E 0 10
Noting that, (0+ (0: 7/M²,, v.) T and (0 A) 0. (MO- - M0 + 1y4, (1 2 0,
000,011-
But, since the matrix M is PSD and the last inequality is condition on the sign of the inner-product, it can be written equivalently as,
(Mo - M0 + nu,, (0 ++)) 2 0, YB 10
The final inequality, is exactly the first-order optimality condition for the second minimization problem.
D
50

---

G.4
Alternating Mirror Descent using Changing Mahalanobis DGF
G.4.1
Supporting Lemmata
Lemma G.9. Let U1, U2 be vectors in F² and X' C 12 be a compact convex set and a scalar 1) > Also, let points oī 222 E X such that:
xi Proj (a 11M; v
X.M.
2 = Proj (z r/M; '22). X.M.
Then, it holds true that:
| 25 ll Il.. /nluur 0211M,1
Smoothness Relative to the Mahalanobis Distance
Proposition 7. Let f be a function (-smooth relative to the li-distance. Then, it is Amin(M.)) smooth relative to the Mahalanobis distance induced by positive definite matrix M,.
Proof. We will merely demonstrate that if f is E-smooth (relative f2-distance) it is also the that:
If(v) f(z) (V 2) 2)..
||0 y li..
For one direction use vector norm equivalence to write:
f(y) 2 f(x) + (Vf(x), - x 2 | - yll
2 fxx + (Vf()),y x) 22min (M,)
||00 yll
Correspondingly for the opposite direction:
L f(y) - f(z) (Vf(z). - x)) 1 yll
$ f()) (VS(s), x) 2dmia (M,) ||00 yllm
G.4.2 Convergence of Alternating Descent-Ascent
Through, we consider this section, we consider the iteration following scheme,
T++1 = arg min
( Bc), - xz.)
||x
xell xell
277
(Alt-GDA)
Mc+1 = arg min yEy
(- - y0) +
11 ye lell MM.
2ny
We make standard assumption on the gradient estimators and their second moments.
Assumption (Unbiased Gradient Estimators and Bounded Second Moments). For all iterations the gradient estimators 9z (x Vi) and ây (21, Nt) satisfy
E (2e, wc)] = (xr,,,W1)) E (T,, wc]] = (Ne, Wr),
and
E [ 11)1 S 5
Il (2te, )1) < oz
In turn, (2 vc) Vaf(zn, ve)l _ 8n, (Ie, vr) - V (zre vi)ll by-
51

---

Theorem G.1. Let f: : x + R an E-smooth function and bounded in the interval Zj. Further, assume X. y to be two convex sets with Euclidean diameters, ( diam())). Moreover, assume that I satisfies two-sided PPt. condition with moduli ozz for all y E y and ag for any x E X. Additionally, let (gs, By) be an inexact stochastic gradient oracle satisfying Assumption 3.
When M. = I, after T iterations of (Alt-GDA) with a choice of stepsizes nee g60ts and Fl it holds true that:
(D((T)
4- + (B
ara
ciO²
ci oz
colo0
S exp
T
D
+ ag
960
ar
anaz
ag
where, A max f(x min ((x v) and c1, C2 E O(1)
For a general positive definite choice of M. (Mahalanobis metric), after T iterations of (Alt-GDA) with a choice of stepsizes The 960 X
a,
and Bl 5exmax holds true that:
(x(T))
4* +
1 T0
(ET(TT)
- (f(TT,,T))
ar
2 y
CiO
ci +
Amax c2l Xmaxx
82 y
I exp
T
B +
araz where, A := max (xx minmex (I, Amax = max; Amax MaxxxMMM (M.7) and 01, C2 (1)).
960X
az
ax
araz
Proof. To prove convergence we will use the Lyapunov function L(x; y) = U(r v) + cW(x, with (zz y) == E [0x)) Φ*). Wx,,y) [[ f(z y)] and
Intuitively, U
measures I's success in achieving the unique minmax value $*, while W(x, y) measures y's success in achieving be a best-response to its corresponding x. We begin with some preliminary work to ultimately setup recursion on L.
Descent on & In order to guarantee descent, by Lemma G.6, Proposition 7, and Lemma G.4, it suffices to pick 7 I 5tAmax Then, we can write,
(0(4))1) & (x()))) The "ED 1/na) + N. V. Val(
2 2n
Equivalently, subtracting Φ* from both sides yields,
(0(())) - 4h < (B)(()) Φh
Th ED (xt, + (v - (ar
6
+ 20 0
Further, a simple re-arrangement reads.
B4(2+11 - (x;())) <
Te D (x., 1/nw) + + 7. VV 31)(
6
+ 2n + 2n.
Ascent on ((x))) Requiring that f/y 30Amax(MM,.1 (Proposition 7 and Lemma G.4), we write:
"y EDy(y, 1/7g #241) ny - 7700
Ef(z Mo+1) 2 (f Me) +
6
Invoking Lemma G.8, multiplying by 11, and adding (x will yield,
E [1(+))1) - -f( < (1- Gy E (1((1)1) f(2411) + 02 + oo
11
Ty
E (((x)) [(x, we) + [I,, (( + (xx+11) 4 (xx))
6
+ +7,00² + T As a reminder, is a PPL. function relative to the Mahalanobis distance induced by M, by Lemma G.8.
52

---

Upper bound on the descent of f(-,8) v) From the smoothnes of f:
3T E G|1 (1ie) 1
71,
(f(x+11, 2 Es (22, Mr)
2
2
2
31
9m
71, 52
2 Ef(,, y1)
ED (xc, 1/
2
2
Re-arranging to isolate f(r vo) 11
3
Mo 2
7
(s ve) Ef Me) S
EDx ( 1/1x: vc) +
2
2
2
Putting the pieces together for 4 (x++ - f(re; Be), we get:
E
(x(+1)
f( v(+1)]
ay'ly
E
(x+)) - (1t,,
Te EDD (2,, 1/nz) + nh E - V2f 2o
+
E
6
6
Ty
E
31T
EDx EDx (2t, 1/mxiv1)
6
+ O + oy
The (1
ax
( o 11 6
6
Decrease in the Lyapunov function We consider the Lyapunov function L(x, y) == U(x
(z. y) with (zz 3) := E [(x)- - 0²) W := E [ - f(r. y)] and shorthand notation U, 1==U( (2,, yr). W. W (z, Mr). Here U, measures primal suboptimality via the PL condition on
Φ while W. captures the dual gap (xx.) - [ V1).
U + cW4+1
< U,-
12 ED X
(
1/mx) + 7 V - (
6
ayTly
+
EW,
6
+
ayTly
E
n
ED
1/1a) n. V. - V Vn (I Wt)l
6
6
yyy
3 E [Dx 1/ 1/1xit:))
+
6
2
+ City 82 + City
+ CTJ (1
au fy
( 02 + 52) + =2mn002 2 + 21
$ U,
12 ED 1/mx)
E. V (xx)) - Vzf(I,, Ves(sz..()11) 1
ay'ly
+
EW,
6
+
E
ne
EDD (xt, 1
+ R. V V.I(Ir, 91 11)) [i]]]]
6
6
+0
ay
31
E [ (Zt, /// - D$ [x, 1/n=)1 + (x+, 1/1z)] (17)
6
2
+ cnly y
+ Cnyy y + Cn (1
( oz + 4 52) 21 + 27
$ U,
12
& (It, 1/Th)) + [
Vzf( (
6
ayTly
+
EW;
6
+
ayTly
E
Te
ED
(2r, V. VaI(ar, v:)
6
6
+
ayTy>
31
E
3Amax (M 1d
||
(xx)) 2 + D 1/Twm)
(18)
6
2
+
0 + cnyy
o
2
+ cna (1
13
+
2m + 21
53

---

< U.
1
EDD (It, 1/1x) The Amxx (M (1y"( vell
Oy'ly
+
EW;
6
+
aylly
The
D D Tzz 1/nz] + 7/5 Max (x())x))=))))))))))) - yell
6
6
311 E
+
3 MM |1: y/ (x+)) (xx, : 1/ mmmz))
6
2
+ Cnyy + by o + en (1
22 13 o + 4/4 6%) 2m + 2m
(17) uses the fact that < la
bl + for (x // = D (rx, 1/na).
This decomposition isolates the term [Dx D |. which can then be controlled using the Mahalanobis continuity lemma in y.
(18) uses Lemma G.5 and Danskin's theorem: this yields a bound 1xx Dx s 3A (M, - y (x,))..
ED (Tt, 1/Tx) + 2012 Amax (M
U141 + cW S U2
W.
6
Ogip
+
EW:
Max (M, Wr
Qy
Th ED x (Iz. 1/1o) +
+
E
0ggg
+c(1
0y
31le
6Amax (M M2
We
Ogg
+ t + og y + cme (1- ay Tu
( 2 0- +
11 62) + 222 + +1
I w + co
+n + oy + c7 (1 -- -
U1
13 0
2 82) + 2n + 27
We then collect the coefficients front of U, and We in the previous inequality into w and w2 respectively, that the Lyapunov recursion be written compactly Uc+1 cW S wi U, + cw2 W. + noise. l.e.
-1-c(1-
aylly 3): )3):
10 a
3 + +
3
6
2n Amax (2
11 Amax e
Oyy + (1
a'y'ly
W2 ;=1 +
Colo
Oqg
For 11, letting 1/10
(1 1 1
(1
Oiy
1
1
(1
W =1 -0
3
10
3
10
6
Oky
=1 az
ag The
30
3
For W2, distinguish two cases relevant our algorithms, M, and general choice of M,
* For M, = I, it holds that Amax (M.!) 1, and Aqg.
ay. So we write
20m 1
ay (1- _y
11
We =1
Ogy
ay
agT 11 (1
0
-20 + 6.
ag
6
54

---

1x Oy
S
(-20 32 -11)
0 Let
192. Then, choosing Y/y
52 yields 1/2
9602
For general choice of M,, let Amax == max Aax (M ming: Cy.
Amax (My.e) and ag +
w2 = Amaxx l
aylly
0yy0
2mxx
+
Qgy
6
Q2y
1 Amax?i E
0gy By
agy
-20
11
Oty
6dmax 1n2
Similarly, need to set
Oty fl
192.
Amax
This in turn yields fl 5Amax! and
960E
Remark 4. In fact, M, is allowed to be positive semidefinite as long as the gradient throuhgout the iterations is in the kernel of M,
H Convergence Analysis
H.1 Direct Policy Parametrization
Theorem H.1. With direct policy parametrization and the Euclidean bidilated regularizer, alternating policy-gradient algorithm attains a last-iterate e-Nash equilibrium in
T 12 poly A,,, PDT)) ming (h( (S11.18a) iterations,
using butches of poly (t 5, HI, A, B, P(T)
(e(h) [1 (Sa) trajectory samples each step.
Proof. The proof follows as an application of Theorem G.I. In central role lies Lemma E. which provides two-sided pPt. condition for the regularized game under direct policy parametrization, while supportive one the smoothness lemmata of the value function and the Euclidean bidilated regularizer when the policy is directly parametrized.
First, we relate equilibria of the regularized, truncated, ixploration-perturfii game equilibria of the original game. An e-NE of the regularized game is an e'NNE of the unregularized game where
é' d== PTT =S max A, B) +7).
The term contains the optimization error c, the regularization error (controlled by 7), the truncation enror (controlled by through the minimum action probability). and the inpoorattooiinducee error (controlled by 7). To make each contribution Occ) we choose
y (c)).
max (1.3) (8,120(7)
8 +
max:g(1.2) St] maxe A. [
55

---

We now instantiate Theorem G.I. By Lemma E.1 the utility of the regularized game satisfies the two-sided pPL condition with moduli
minne (e(h))
Oxgy Cty
+
H/3
Combining the smoothness of the value function with that of the Euclidean bidilated regularizer (Lemmata B.4 and B.7) yields an overall smoothness constant
6 max
V D(T) +
[2)]] (()) max[[Si], (8a1
max (E(1
(1
= (PM max (E(12)
E
The stochastic gradients used by Alt Alt-RegPG are given by the REINFORCE estimator together with the gradient estimators for the bidilated regularizer; by Lemma F.I and the analysis of Appendix F.1 they are unbiased and have bounded per- per-trajectory variance
V V VI A²D(T)²
B²D(T)²
E
V
If each update averages a mini-batch of M i.i.d. trajectories, V= 1 ((m) then the averaged estimators have variances
Σm= (m) and V,
M
M MM
of Var(V,)
o
Var (ar(v)) S
M
M
with per-trajectory bounds of A2D(T)?/E and of S B²D(T)²/E. Substituting these into Theorem G.I, the stochastic error terms are controlled (up to absolute constants) by (MM)) and È / (Ma,a))) Requiring each to be at most leads to the condition
of Loz
(AD((T) (B2D(T)'}
M 2 max
max
602
a
EE
EE EEa2a7
Using the explicit forms of Otr, Og from Lemma E. and the per-trajectory variance bounds from Lemma F. this can be summarized as choosing
EET EET 1).
l
M θ max
Writing S = max max([Si), and using the tunings 7 O(e), = A(c/(S2P())), and e ((c((SA)) from above, together with
ê = ((D(T) max
max (E(1.2)
Egle e max
(V
(E(1.2}
S minn Mo(li) = e mins po(h)
===0p ag = 0
S2D(T))H43 Ea)
17/3
a direct substitution yields the explicit bounds
(PT)) 2 5 A 17(
M 2 θ
minA (c(h) c
(8D(T) D(T) 5t A B I71 max m (maxxe(1.2) Ex ee max4e(1.2} Eil}
M M20
(mina (h)) c14
For small the second constraint dominates, so it sufficient choose
M = 23D(T) D(T)3 5t a ( max / Ex max;e(1.2 Edl}
(mina (h)) c4
56

---

which spells out the precise dependence of the mini- size on A, B, D(T), [S1], [Sa), [7], and min, (h).
Under these conditions, Theorem G. prescribes the concrete stepsizes
Q z2 mmnn Mc(h))
Fy 56"
and Tee 960 8 960 101 |H|6 8
owing the symmetric pPL moduli a, = ay from Lemma E.1. The resulting duality-gap decay is exp
a. 960r3
)). so driving the deterministic term below requires
T 960 e
960 101 17/ 8 log
A
log
0g
م (minscH (o(h))
where Ay is the payoff range appearing in Theorem G.1. Substituting the smoothness estimate from Corollary B.1 and Lemma B.7,
L <= (DT max
max iE(1,2)
max (E,1,2
yields the following dependencies on the game parameters:
fl +
D(T) maxe / (1.2) EE maxic [Ei1]]
e (minken (h)))
Gre +
22D(T) sa 191 D(T)3 max maxic (1.2) E.l. maxic |2,}}²
(aPeT) sa pu D(TY max max Eille max.e(1.2) {.1} log ب (minsse (c(h)) 22
T = θ
Finally, substituting the choices of y, T,E from above into the expression for T yields
T T= (23D(T) 8 1711 D(T)² max (max Eglee max [E,]]" log A
(minke (c(h)) el
as claimed in the statement of the theorem.
H.2 Softmax Policy Parametrization
Theorem H.2. Alternating srriyeggradint algorithm with softmax policy parametrization and the entropic bidilated regularizer converges in expectation in the cast-iterate to an e-Nash equilibrium after a number of iterations T given by
T 218 poly (176), A, B, PDT)
mins (h) |8t]. 621).
using batches of poly (2. 2. H|, A, B, P(T)
mina (hj [1 (111. trajectory samples at each step.
Proof. The theorem follows as a corollary of Theorem G. .. By Lemma E.2, the regularized game under softmax parametrization satisfies the two-sided pPL condition with moduli
T minneh Ha(h)
T minnee (e) 3
a₂
ag = e
[7/3(1 + (B 2)
up to absolute constants. An c-NE for the regularized game also an c'NE for the unregularized game where
'' <'= max(log A, log B} + =S(max{(, BB)))
Then, need to tune:
57

---

(c))
θ (1.2) (,,22077) max/ Ao B3
E max.e(1..) ([[mmxx(A.B))
We recall the smoothness parameter of the softmax-parametriaal regularized utility function is
Coottmax
8/16 16 max (E(1.2)
V D(T) T
max (1,22
D(T) max(log A, log 13)
= =DDD(T max (E(1
by combining the Lipschitz bounds on the utility and the weighted entropic bidilated regularizer (Lemma B.8). Then, from Theorem G.I we tune,
f2y +
T/ -
T=
log
where we set = Esoftmax. and Oz Gy are the softmax pPt. moduli of the two players. Invoking Lemma E.2 for player yields
T TminkgeHeaa Mc(h) 1 + (B - 1)
By -
and therefore, prior to relating to the truncation level E,
7² (minsgH Mc(hh)) 76 1711 (B (B-1)e2 R)
n2 θ
Finally, using the explicit relationship between R and the minimum action probability (so that (1 (B 1)e2R) can be expressed polynomial 1/2) and simplifying constants leads the following convenient. And, subsequently,
fly = D(T) max m1x E.Ie (1.) |E.1]
23 (miunen (o(h))?
The θ
22D(T) 96 [7/6 D(T)3 max{ / /max.ce (1.2) [E max2c [Σ,1]" [max((lg Aloog B))² (max
Finally, plugging the explicit expressions for On, Ol from above into the generic bound T |H| e² (1+(A-1)6"") (1+(B-1)c2")
θ
log! yields the precise parameter dependence
(munnee (h)))
176 03 (8(11 (1+ 1)e 2)) (1+ - 1) 2)
T 0
log
33 (mingeH Me(h))² 79
Using the relationship between and the minimum action probability upper-bound (1 (A R))2 and (1+ (B-1)e25 by polynomials 1/c and then substituting the tunings 7 e we obtain an explicit dependence on the game parameters. Writing = max[[S]], ||| and using the smoothness estimate Esoftmax together with the truncation relation straightforward calculation
yields
T= 23D(T) 5 H7 ((T)*((maa) (maxief1.2 [21)) max{(A 12
(max{log A, log B3)
S( (mxx ((max(A,B)) AJ)
log
(minae (h))3 c18
As the diramtt-aanmettiiaatoonn case, we now quantify the effect of stochastic gradients. For softmax-paramette policies, Lemma F.2 shows that the REINFORCE estimator (combined with
58

---

the estimator for the entropic bidilated regularizer) is unbiased and has bounded variance per- trajector with xx o I θ (D(T)² + +) O (D(T)²). We will control the stochastic error using mini-batches.
Substituting these into Theorem G.I with the softmax pPL moduli from Lemma E.2,
T mimpee Mc(h)
T mimnnn (c 73
+
Og = θ
[1+ (A (A-1)e22) 1))2n)²
11133 (B 1)e2n) 2
the stochastic error terms are controlled by
o Ma²
D(T)² 1761 (1 (A 1)
θ
M T minDEH (h) 7:3
l to Mazay S
D (1 (1 - 1)
(1 + (B - -))22R)
θ
M r3 (minken Mc(h)) 70
Requiring each to at most gives the condition
D(T)² H (1 (A 1 1)c D(T) (1 (A - 1)e2R)² (1 (B -1)c2R)²
))
M 2 θ max
minneH n
cr3 (minnEN Mc(h)))
The second term dominates for small e, so suffices to enforce
(B-1)e22 D(T)² 1/2 (1 + (A - - 1)) (B+ r3 (minKEH (h() 70
M M
To relate the dependence on R to the truncation level, we use Lemma D.4, which implies that if the minimum action probability under the softmax parametrization is at least e, then 1+ (A - 1)e < 5
and (B 1)e2R < 2
(1+ (A- (1 (B 1))
c6
Combining this with Ê-smoothness from above yields the bound
D
M
θ ET (minnEN H (h))3
Finally, denote S := max | [S2]] and substitute the terms y, T, E, together with the definition of feottmax, a direct calculation shows that is sufficient to choose
(2D(() D [7|0 5 max4e(1.2) [2:] (max((A B}) 12 (max(log A, log B3)*
M- = θ
(mingeH (h)) 21
H.3
Natural Policy Gradient
H.3.1
The Fisher Information Matrix
F(x) Egsax (a [V log, म (als))] log x (a]s)]
The matrix F(x) is a blog diagonal matrix with its (s, block being the matrix: F.(x) dxx (s) (diag(T (s)) (x)
Its pseudo-inverse, Ft, is again a block-diagona matrix, with an (s. 8) block,
FI()) (x) (diag(TTx - (s)TT
Interestingly, the matrix Z FiJ (x) is a biock-diagonal matrix with entries (x. I [AIxXAA)] on diagonal (s, bllock.
59

---

The spectrum of the Fisher Information Matrix we can conclude that,
With the same arguments used in Lemma D.1,
Amin (F(x 0)) = 0: min (Fx(X, 0)) 2 (x) mitl, Tx (als);
minn (h) S maa (x,(x, 0)) S 1.
Hence,
X (F(x, 0)) 2 mins,a (
min. A. Amax (F(x, 1.
While, dx- 2 22 2mmin (ech) by Assumption
[H]
Theorem H.3. Alternating natural policy- graiient algorithm with softmax policy parametrization and the entropic bidilated regularizer converges in expectation in the last-iterate e-Nash equilibrium after a number of iterations T, that is
36 poly (5) [71, A, B, 2P(T), MinKER Mo(h)) [11, (Sal)
T
Proof. This theorem is again application of Theorem G.I, in its Mahalanobis form. For natural policy gradient, the updates are mirror-descent steps with a Mahalanobis metric induced by the Fisher information matrices,
Alt-GDA with M Fx 0e) and My Fx 0t)-
By Lemma E.3, for a general Dositive-semidefine metric matrix M the game satisfies a two-sided Mahalanobis pPt. condition with moduli
minnew (h) 73
â₂ =
Amax (M-1) /7/3(1 (A 1 1)
minnew (3)
0g 0
Amax (M-1) (M| (1+ (B 1)
When we specialize M to the Fisher information matrices, the spectrum bounds in the previous subsection together with Assumption 2 and the truncation assumption imply
X min (F (xxxx0)) 2 72 minpen (b))))
72 minBEH H (c(h)
x min (Fo(x.0) 2
1712
[7/2
and hence, over the image of the Fisher matrices,
H2/22
Amax F (x, 0)). Amax (F (x, = minnew (c(h)
Substituting these bounds for Amax (M-1) into the expressions above yields Mahalanobis pPL moduli
a θ (mingeH
āg = ((minnexx
1H 1)e2n)
|7/5(1 1))2n)²
The Mahalanobis version of Theorem G.I prescribes stepsizes (up to constants)
(
( 12 X log
7/y - 1xmaxx
Th θ
y
T= θ
[3
az
where L is the Euclidean smoothness constant of the objective and Amax == max, Amax (M We the Euclidean smoothness constant é == fsnttmax as the ceftmax-parametriin policy-gradient case; writing Σ = max.2(112) [Egl and S == max[]S S21]
= 0 D(T + ( D(T) max(log A, log =
60

---

where the final inequality uses the tuning of 7 and é < 1. By the Smoothness Relative to the Mahalanobis Distance (as used in the proof Theorem G.I), we have
Amax o
H12
minnen Me(h)
and hence the stepsizes can be expressed as
ex "minneH (o(h)
= D(T) ES max (A, B))2
24 minnke Mc(hh)
= θ 22D(7) 1 D( g (max{A, B}) (max/log A, log B})²
As in the saftmax-parametne policy-gradee gradient case, relate equilibria of the truncated, regularized, exploration-perture game to equilibria of the original game. An c-NE of the perturbed game an c-NE of the unregularized game with
c = max (8,12P(T) max lo B} + max [S,](max {A, (A, B)))) iE(1.2)
=
(e.12
so, as before, we choose
7 (
r maxie(1,a) (8,1207 max A,oog B)
+
Combining these tunings with the expressions for āz ay. the smoothness Esottmax the bound on Amax and the generic iteration bound 7'
O e softmax X2 / log (og)( and using Lemma D.4
to relate R to the truncation level yields
(2D(T) 3 | 19 514 3 (max A, B)) (max A, log B}) log
S(max (A, B))²
33
(minge (h))
I Proximity of Projections
In this section, we consider that the update rules:
- 0, + r/ (oo)
0F + arg min - 0) (0 0); B
(19)
0u arg min DKL (softmax(()) (0]llso))a #E@R
(20)
and demonstrate that (19) and (20) sufficiently close. For brevity consider only the maximizer's updates and drop the minimizer's variables from the notation. Le., our goal is to bound |0 0rl We begin by defining the objective functions that each projection optimizes,
(F) (A 8) F( 8); (i) Ise(ō) Ise(() Vlse (8) (0 8),
T
where lse(0) : log Σ c. Then, we write,
Pp arg min Lp(0);
de@a
0gt arg min Lx (0)-
61

---

Further, for the gradient of Lu we write.
(Lu (0)) 8)
( B).
Now, from stationarity of the optimal, for in the normal cone of @ 0yt.
0 (la)( +
(O 0) +
F(0))(02) - 0) [F(a)) F(0))](Ok) 0) + v
Therefore, we can bound the stationarity of 0ua for the objective of (r(-):
(00) 8) + e|| = (( (( 8)
[Oo)) F(Oka) ||0at 01l
LF 110- 8all Au 0|
2
LF (1|@ 0oll
+ ||0 0kill) ||0 - 01
2
LF
1
n2vSB 1
n2v
SB
-12 SB
Va
V
Lr
0
where we use:
Le is the Lipschitz continuity modulus of the operator norm of F(-).
Proposition 8,
a mingge, R A (F()),, and
the fact that when tuned as dictated in Theorem H.3:
0
S n [()))VVT())]
< 22vV5B
Proposition 8. Consider the update rules (19) and (20). is the case that:
11pp 0kll S
V | a
where a minoge Att. (F(O)) and Rt' = R+ 71 SB.
Proof. We begin by stating a useful fact.
Fact 1. Let lse the function Ise(f) == log E, c.. Then, softmax(0) Vlse(f). Further, (.)(-) strictly convex on + == {0 E Rd 0T1= 0} and its Bregman divergence is:
Bis (0'l(00))) (10) = Ise(O') Ise(0) Vise(0) - 0).
Further, it is the case that:
B (0((0)) = DKL, D)
The arguments for this fact can be found in (Gao and Pavel, 2017). By standard calculations we can see that:
Bio (8' > a 100 - 811 for 0, e O1,
2
62

---

with a = A (F(O)). From Fact 1 we can conclude that,
a Oua 0|²
Bise
0
00)
2
where we let OR for Rt' = -R++1 12+ SB. From -smoothnesss of Lx1(-) we write,
Lx((6) & La) + (C) (6o - 8) + 4 |10. B||
2 | - 0|
Since 0k1 = arg mingeoR (0) follows that
1 |10 - Ø|
at
0u - 1|
2 2
which concludes the claim.
63


Reviews:
[{"review_id": "YVRlsBKknw", "reviewer": "Reviewer_JY7P", "summary": "This paper address the issue of establishing convergence to an approximate Nash equilibrium ($\\varepsilon$-NE) of policy gradient-based methods for solving imperfect-information, two-player, zero-sum extensive-form games (EFGs). The main idea is to (a) consider the EFG in sequence-form, which is known to be solvable via an equivalent bilinear optimization problem over the players' strategies in sequence-form, (b) restrict to simple classes of policy parameterizations (i.e., tabular, softmax) providing a well-behaved mapping from policy parameter space into sequence-form space, (c) suitably regularize each player's utility to ensure that each agent's utility satisfies a one-sided Polyak-Lojasiewicz (PL) condition in the agent's policy parameters, and (d) leverage the PL property to establish convergence of policy gradient descent-ascent algorithms to an $\\varepsilon$-NE under suitable conditions. The primary contributions are the establishment of a certain two-sided PL condition for the regularized payoff and convergence analysis for vanilla policy gradient (REINFORCE) with tabular and softmax parameterizations, as well as natural policy gradient with softmax parameterization.", "questions": "The following questions may help improve clarity of the paper:\n1. What is the main point of the discussion lines 49-56? How does value iteration fail?\n2. What is the main point of the discussion lines 57-74? How is it relevant to the rest of the paper?\n3. How does one go from the single-variable PL condition of lines 101-107 to a saddle point of the two-variable objective $f$ around line 101?\n4. How are the information sets in Definition 1 defined? Which player is maximizing in Definition 1?\n5. How exactly are $\\sigma, \\sigma_1, \\sigma_2, \\pi_1, \\pi_2$ defined?\n6. How exactly is $\\mu_1^{\\pi_1}$ defined in the mention of sequence-form strategies around lines 184-185?\n7. In definition 2, should the LHS be $V^{\\pi_1^*, \\pi_2} - \\epsilon$?\n8. How are \"summed multiplied\" and \"total reach probability\" defined on line 192?\n9. How is \"reach probability of each history\" defined on line 197?\n10. Under what conditions is the REINFORCE estimator \"an unbiased estimator of the policy gradient\", as claimed on line 221?\n11. What is $K_\\tau$ in Definition 3?\n12. In Lemma 2.1, since there is a set of decision variables corresponding to each player in the utility, in what sense does a given player's utility satisfy the PL condition? Clarify the leap to the \"two-sided\" PL condition being made here.\n13. What is the key technical challenge in the proof of Lemma 2.1? What is the significance of the result?\n14. What is the key technical challenge in the proof of Theorem 3.1? What is the significance of the result?\n15. What is the key technical challenge in the proof of Theorem 3.2? What is the significance of the result?\n16. What is the key technical challenge in the proof of Theorem 3.3? What is the significance of the result?\n17. Does the bound in Theorem 3.1 have exponentially growing dependence on the problem horizon? If so, how does this impact the claim of polynomial complexity in the abstract and introduction?\n18. What is the \"size of the game\" in line 286?", "limitations": "See weaknesses and questions above for limitations.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n1. *Relevance to the community:* Convergence analyses for multi-agent reinforcement learning (MARL) methods applied to games is currently an active area, and the particular imperfect-information EFG considered in this work is a game of fundamental importance. For this reason, this work is likely of interest to the theoretical MARL community. In addition, the substantial body of recent work establishing convergence to global optimality of single-agent policy gradient methods using PL and similar conditions has only just started to be leveraged in the MARL for games setting, making the subject of this work quite timely and increasing its interest to the community.\n2. *Well-motivated:* The core idea of establishing \"hidden convexity-concavity\" of the regularized payoff and leveraging this condition to establish convergence to an $\\varepsilon$-NE is both sound and interesting. Leveraging the nicely structured sequence-form of the EFG is a natural idea, and the steps (a)-(d) outlined in the **Summary** make clear sense as a way to achieve this.\n\n**Weaknesses.** Despite the strengths listed above, the paper has significant clarity issues making it difficult to accurately evaluate the technical contribution of the work. Major clarity issues include:\n1. *Technical contribution:* It is unclear from the main body of the paper what the core technical innovations of the analysis are and what key challenges were overcome in order to achieve the analysis. Lemma 2.1 and Section 3, which constitute the main contributions of the paper, offer little to no discussion is provided offering insight into the meaning behind and challenges in obtaining the results. In addition, though the appendix contains much content, there is little to no exposition tying the results together and relating them back to the main body.\n2. *Key concepts poorly defined:* Important concepts, such as the definition of sequence-form (discussed around lines 184-185) and the explicit statement of the two-sided PL condition (not defined in the main body) are not clearly defined in the main body of the paper. Since these are central concepts for the paper, this significantly weakens the ability of the reader to accurately evaluate the work. Without a clear definition of the sequence form it is difficult to see the critical relationship between the policy parameterizations and bilinearity in sequence-form that make hidden convexity-concavity of the regularized objective possible. Without explicit statement and discussion of the PL condition, it is likewise hard to see why this hidden convexity-concavity holds. As with weakness 1, the appendix does provide some additional content (Sec. C and E for sequence-form and PL condition), but there is little to no exposition tying the results together and relating them back to the main body.", "was_revised": true, "final_justification": "While the authors have made a substantial and appreciated effort to address the significant lack of clarity in the submission (see Weaknesses 1 & 2 and the 18 Questions in my initial review), the amount of revisions that will be required to address all these issues goes significantly beyond what can be expected for the camera-ready version. I therefore maintain that the submission is not ready for publication in its current form.", "rebuttal": "Dear Reviewer,\n\nWe thank you for your time and the extensive valuable comments. We will answer them one by one. \n\n---\n\n### Regarding the highlighted weaknesses\nOur **key technical contributions** were providing the first polynomial time policy gradient convergence results for imperfect-information EFGs. We first establish a gradient domination condition for the highly nonconvex utility function of EFGs -- this step is a cornerstone for our analysis. In general, we cannot prove polynomial-time convergence in min-max functions without some gradient domination property. \n\nThen, we analyze alternating mirror descent ascent with changing mirrors for constrained min-max optimization in the presence of inaccurate gradients.\n\n---\n\n### Key concepts: Sequence-form strategies, hidden convexity, and pPL condition\nWe agree that a clearer definition of the sequence-form strategy would improve exposition. We omitted a longer discussion on the sequence form as it is considered quite standard in the literature of EFG. The sequence form is a convex polytope defined from linear constraints. Intuitively, a sequence-form strategy is a nonnegative vector indexed by a player’s sequences, where a “sequence” is the ordered list of that player’s own actions from the root (including the empty sequence). Each entry gives the probability that the player realizes exactly that sequence under their behavioral choices.\n\nWe clarify now that in terms of sequence-form the utility of each player is concave (linear for each player's sequence-form strategy). Since, there is a transform from behavioral strategies to sequence-form, the utility is hidden-concave automatically. Now, hidden concavity can be translated to gradient domination (weak or proximal PL).\n\n\n---\n### Answers to questions\n\n>1. What is the main point of the discussion lines 49–56? How does value iteration fail?\n\nThis discussion demonstrates why our proposed solution, policy gradient methods, is needed and how other RL algorithms (used for Markov games) fail for incomplete-information extensive-form games.\n\nNash value-iteration fails because policies at the root of each sub-tree alters the q-values of their children nodes. We can check this by a simple example. Consider the game of matching pennies transformed into an imperfect-information extensive-form game.\n\n* At the root, picks a side of a coin that is not revealed to their opponent.\n\n* This choice will lead to two different histories $H$ or $T$.\n\n* Since the coin is hidden, player $2$ does not distinguish between the two histories and they lie in the same info-set.\n\nAssume that player $1$ initializes their strategy with the uniform strategy; the q-function cannot be defined otherwise.  \n\nThis means that player $2$ q-function at their info-set is $(0,0)$. Any strategy is a best-response.\n\nNash value iteration would call for a bottom-up solution. I.e., it prescribes that the policy of each player is a Nash equilibrium of the joint q-function.\nSince agent do not act simultaneously and the last decision is taken by player $2$. Player $2$ picks a minimizing strategy which is any strategy ($\\arg \\min_{\\pi_2 \\in \\Delta} \\pi_2^\\top q = \\Delta$ ).\n\nClimbing the tree to the root, player $1$ can alter their strategy by picking an appropriate best-response. This process does not lead to a Nash equilibrium. The same would be true for any initialization of player $1$'s strategy.\n\n> 2. What is the main point of the discussion lines 57–74? How is it relevant to the rest of the paper?\n\nThis paragraph highlights how different gradient domination conditions hold across different fields of ML.\n\nIn our case, the proximal-PL condition fosters the validity of our convergence arguments and also the empirical success of policy gradient algorithms for incomplete information EFGs.\n\n> 3. How does one go from the single-variable PL condition of lines 101–107 to a saddle point of the two-variable objective \\$f\\$ around line 101?\n\nEssentially, a two-sided PL condition for $\\min_x \\max_y f(x,y)$ means that $f(\\cdot, y)$ is PL for any $y$, and $f(x,\\cdot)$ is PL for any $x$.\n\n4. How are the information sets in Definition 1 defined? Which player is maximizing in Definition 1?\n\nInformation sets are defined as sets/groupings of *histories* of the EFG. I.e., they are the underlying states of the game indistinguishable to one another since the players to not have full information. E.g., in poker, a player knows what their opponent has bet, what cards are on the table, and what cards are in their own hands. But, since they do not know what kind of cards the opponent is holding, all possible states of the opponent's hand are in the same infoset.\n\nPlayer $1$ gets *payoff* $r$, and so is considered to be maximizing in this definition.\n\n> 5. How exactly are \\$\\sigma, \\sigma\\_1, \\sigma\\_2, \\pi\\_1, \\pi\\_2\\$ defined?\n\n* $\\sigma(\\cdot)$ takes is a typo. It should be $\\sigma_1$ or $\\sigma_2$ depending on the player considered\n* $\\sigma_1, \\sigma_2$ take as input an info-set and return the last history where player 1 (or player 2 respectively) took an action.\n* $\\pi_1, \\pi_2$ are each a concatenation of simplices, one for each information-set.\n\n> 6. How exactly is \\$\\mu\\_{1,\\pi\\_1}\\$ defined in the mention of sequence-form strategies around lines 184–185?\n\nIt is the sequence-form strategy that corresponds to behavioral strategy (or policy in RL terms) $\\pi_1$.\n\n> 7. In Definition 2, should the LHS be \\$V\\_{\\pi\\_1^\\*,\\pi\\_2} - \\epsilon\\$?\n\nYes, thanks for bringing this up.\n\n\n> 8. How are \"summed multiplied\" and \"total reach probability\" defined on line 192?\n\n\nThe total reach probability is defined as the probability of reaching a particular infoset for a particular policy profile $\\pi_1, \\pi_2$ taking into consideration chance.\n\nAlso, this is a typo. The bidilated regularizer is defined using a strongly convex function multiplied by the latter *total reach probability*.\n\n> 9. How is \"reach probability of each history\" defined on line 197?\n\nThis is $E_{h' \\sim \\pi_1, \\pi_2}[\\mathbf{1}\\{h' = h\\}]$. I.e., the probability of reaching a particular history conditioned on the policy profile $\\pi_1, \\pi_2$.\n\n\n> 10. Under what conditions is the REINFORCE estimator \"an unbiased estimator of the policy gradient,\" as claimed on line 221?\n\nREINFORCE is generally an unbiased estimator of the policy gradient. The variance can be bounded under the assumption of $\\epsilon$-greedy parametrization for direct-param. and generally bounded for softmax policy param.\n\n\n> 11. What is \\$K\\_\\tau\\$ in Definition 3?\n\n$K_\\tau$ is the length of trajectory $\\tau$.\n\n> 12. In Lemma 2.1, since there is a set of decision variables corresponding to each player in the utility, in what sense does a given player's utility satisfy the PL condition? Clarify the leap to the \"two-sided\" PL condition being made here.\n\nFor the utility function $V(\\pi_1, \\pi_2)$, two-sided proximal-PL means that $V(\\cdot, \\pi_2)$ satisfies the proximal-PL for any $\\pi_2$ and so does $V(\\pi_1, \\cdot)$ for any $\\pi_1$.\n\n> 13. What is the key technical challenge in the proof of Lemma 2.1? What is the significance of the result?\n\nLemma 2.1 establishes a gradient domination condition for the utility functions of incomplete-information EFGs. This property is crucial and opens the possibility of provable gradients of policy gradient methods.\n\n> 14. What is the key technical challenge in the proof of Theorem 3.1? What is the significance of the result?\n\nThe significance of this result is a first provable convergence guarantee of policy gradient methods for incomplete-information EFGs.\n\nThe key challenge of this theorem was handling the gradient inaccuracy error $\\delta$ which is controlled using the regularization coefficient $\\tau$.\n\n> 15. What is the key technical challenge in the proof of Theorem 3.2? What is the significance of the result?\n\n\nThe key challenge was coming up with feasible set of parameters $\\chi, \\theta$ that will guarantee every action is played using a controllable lower bound on the probability while still retaining convex (both in the corresponding restricted policy space and the parameter space Lemma D.3 & D.4)\n\nThe significance comes from the fact that we consider the first algorithm that goes beyond direct policy parametrization and make way for future work where the softmax parametrization uses some neural networks.\n\n> 16. What is the key technical challenge in the proof of Theorem 3.3? What is the significance of the result?\n\nThe key technical challenge comes from the fact that we had to interpret natural gradient as mirror descent with changing mirror. We refactor the previous convergence proofs to accommodate for the changing mirrors and control errors introduced by this change.  \n\n> 17. Does the bound in Theorem 3.1 have exponentially growing dependence on the problem horizon? If so, how does this impact the claim of polynomial complexity in the abstract and introduction?\n\nAs we note, the convergence rate depends does depend on some constant exponentiated by the height of the game tree. But, the height of the game tree is in general a logarithm of the game's total size.\n\n> 18. What is the \"size of the game\" in line 286?\n\nThe size of the game is typically the size of the action space and the number of histories of the game.\n\n---\n\n\nWe hope to have addressed your concerns sufficiently and we would love to answer possibly more questions,\n\nThank you again, \n\nThe authors"}, {"review_id": "ZNDyLU08Og", "reviewer": "Reviewer_k6sM", "summary": "This paper proves global last-iterate convergence of three policy gradient variants, namely direct parameterization, softmax parameterization (with Policy Gradient and Natural Policy Gradient),, to an $\\epsilon$-approximate Nash equilibrium in imperfect-information, perfect-recall, zero-sum extensive-form games. The convergence occurs in polynomial time in $1/\\epsilon$ and game parameters. The key idea is that the nonconvex policy landscape becomes gradient dominated due to hidden concavity in sequence-form strategies. This enables analysis via the Polyak-Łojasiewicz (PŁ) condition, bypassing traditional regret-based arguments.", "questions": "See the weaknesses section.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper does a great job reviewing relevant literature and situating the work in the broader context of MARL, EFGs, and nonconvex optimization theory. Additionally, the intuitive explanation of the hidden convexity and gradient domination properties is helpful for readers to grasp the key idea of the paper. While I have not examined every detail of the proof, the overall reasoning is clear and compelling. Overall, the paper is well-written and easy to follow.\n\nWeaknesses:\n\nWhile the results are promising, the presentation of the main theorems is overly brief, and many important details are deferred to the appendix. For instance, the bound is given as $T = \\text{poly}(1/\\varepsilon, \\dots)$, but the actual order of the polynomial is never made explicit, which weakens interpretability. In particular, in MARL literature, natural policy gradient (NPG) methods are generally shown to be more efficient than policy gradient (PG) especially for softmax parameterization. However, the way that the authors show the results make it unclear whether this is still true in the EFG settings.\n\nFurther, the role and selection of the regularization parameter $\\tau$ is not well-explained. How does $\\tau$ affect the convergence rate or approximation error? Is there guidance on choosing $\\tau$ in practice? Also, there seems to be a notation conflict, as $\\tau$ is used both as the regularization coefficient and to denote trajectories (in Definition 3), which may confuse readers.", "was_revised": true, "final_justification": "I would like to sincerely thank the authors for their responses during the discussion phase. I decided to maintain my score. In particular, in the camera-ready version, I would like to suggest the authors to be more careful and clear about certain mathematical claims, such as including a more detailed rate without the big O notation hiding a lot of details on the dependence on different parameters.", "rebuttal": "Dear Reviewer,\n\nThank you for your time and your valuable feedback.\n\n* We are updating our draft to make these rates explicit. Nonetheless, we stress that it was not previously known whether policy gradient methods converge to a Nash equilibrium in a polynomial number of iterations in EFGs.\n\n* The main reason as to why alternating regularized NPG has a slower convergence rate is because (i) we cannot use the arguments of [1] which are tailored to the Markov game structure (ii) we need to explicitly control the minimum node reach probability using a constraint on the parameter space. Consecutively, the minimum action probablity inversely scales the Mahalanobis-smoothness of the utility function and in turn the convergence rate.\n\n* $\\tau$ needs to be tuned as $\\tau \\gets O(\\epsilon)$ where $\\epsilon$ is the accuracy of the desired $\\epsilon$-approximate Nash equilibrium. It trade-offs rate-of-convergence with an exploitability lower bound. I.e., a larger $\\tau$ guarantees faster convergence but it will introduce a larger bias on the exploitability of the policy profile reached at convergence.\n\n* Thank you for bringing this up. We already corrected it in our draft by using $\\xi$ for trajectories.\n\n\nWith this note, we hopefully have addressed your concers,\n\nThank you,\n\nThe authors\n\n---\n\n[1] Shicong Cen, Yuejie Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence of policy369\noptimization in zero-sum markov games."}, {"review_id": "pIcHCzdW5a", "reviewer": "Reviewer_jMiC", "summary": "The paper shows that the utility of an extensive-form game has hidden convexity when min- and max-players' policy are tabular and soft-max policies, sufficient exploration is conducted, and the utility is augmented with bidilated regularizers. Based on this result, the paper provides three self-play policy gradient methods whose last-iterate converges to a Nash equilibrium.", "questions": "Would you provide a detailed proof of Lemma E.2? Since $\\mu_1^\\pi$ and $\\mu_2^\\pi$ do not seem to correspond to policy parameters one-to-one, I do not really understand why the proof of Lemma E.1 can be used for proving Lemma E.2.", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "# Strength\n\nThe paper provides a novel look at algorithms for solving extensive-form games from the perspective of hidden convexity. It also shows that policy gradient methods have the last-iterate convergence property, which I think is new and very important for practical reason.\n\n# Weakness\n\nThe main weakness of this paper is writing. It was difficult to understand core technical contributions of the paper and which results are new. To me, many theoretical results seem to be straightforward applications of existing results except Lemma E.1 - E.3, which I think are the core technical contributions of the paper and show the utility of an extensive-form game has hidden strong convexity under various parameterization.\n\nI would remove explanation of Markov games and comparison of it to extensive-form games and focus more on explaining the importance and novelty of E.1 - E.3. Furthermore, it would be very much appreciated what technical difficulties exist for deriving presented results. Currently, too much pages are devoted to the introduction of background knowledge, some of which do not really need to be required in the main paper (e.g., Markov games and hidden convexity).\n\nAlso, careful revisions are required. Apart from simple typos, it would be very much appreciated if details of proofs are added. For example, in Lemma C.2, I am confused what $\\alpha_{\\mathrm{dil}}$ is. Another example is the proof of Lemma E.1. There, it is written that \"For player 1, we know that the functions is strongly convex with an appropriate weight scheme...\", but it would be nice to explicitly mention which theoretical result you are referring to. (I guess Corollary C.1, right?)\n\nA minor weakness is that obtained convergence rates for proposed algorithms are slower than convergence rates for previous algorithms, as mentioned in Conclusion of the paper.", "was_revised": true, "final_justification": "While proving the global last-iterate convergence of the policy gradient methods under different policy parameterization based on hidden convexity is a nice contribution, the paper fails to clearly present what are new results in the paper. This writing issue seems to be critical, so I keep my score.", "rebuttal": "Dear Reviewer,\n\nWe are glad that you validate the originality and importance of our key technical contribution (last-iterate convergence of policy gradient methods for imperfect-information EFGs). We thank you for the time you took to highlight your concerns. We will do our best to address them.\n\n---\n### Presentation and core contributions\n\nOur goal with this paper is to also bridge the two communities of mutli-agent RL and EFGs. We offered an extensive presentation in order to serve this purpose. Nonetheless, we agree with you that part of the preliminaries can be moved to the appendix and that we should elaborate on our results with commentaries and an exposition of technical challenges. That is, the comparison of the two regularizers can be moved to the appendix, the lengthy exploration note also. Further, the extended comparison of EFGs and MGs can be moved after the main results as part of the concluding remarks.\n\nFurther, hidden convexity is crucial in proving the gradient domination properties. As such, we deem it important that it is part of the main text.\n\n\n---\n### Regarding Lemma E.1-E.3\nThey establish the proximal-PL condition of the value function under different policy parametrizations. Hidden strong convexity is a direct consequence of regularization. I.e., in the sequence-form, the utility is concave since it is linear for each player's sequence-form strategy. Then, adding a strongly concave regularizer makes it strongly concave. What is left to show using Lemmas E.1-E.3 is that this translates to a proximal-PL condition for the parameters of the policies.\n\n---\n### Proof sketch of Lemma E.2\nThe main argument is the following (a full proof is deferred to the new draft). In Lemma E.1, we establish the KL condition satisfied for the policies (the concatenation of simplices, not the parameters). Now, we are interested in translating policy KL condition to a KL condition for the parameters of the softmax policies. In turn, we can get the pPL condition from Lemma B.2.\n\nLet us denote:\n*  $f(\\theta)$ to be the utility as a funciton softmax parameters, and\n*  $v(\\pi)$ the as a function of policies \n\nalso, let $I_\\Theta, I_\\Pi$ be the indicator functions of the convex feasibility sets $\\Theta, \\Pi$ respectively. Last, let $c:\\Theta \\to \\Pi$ denote the transform from parameters to policies.\n\nWe now observe by the chain-rule of subgradients $s_\\theta \\in \\partial (f + I_{\\Theta})(\\theta), ~ s_x \\in \\partial (v + I_{\\Pi})(\\pi):$ \n$$\\nabla_\\theta c(\\theta) s_\\pi = s_\\theta.$$\n\n\nAlthough the transform is not 1-1, we see that its jacobian, $\\nabla_\\theta c(\\theta)$, is rank deficient with a unique zero eigenvalue which corresponds to an eigenvector of all-ones $\\mathbf{1}$. This allow us to transform the KL condition for policies to a KL condition of parameters using the pseudo-inverse of $\\nabla_\\theta c(\\theta)$. \n\n---\n\n### Weighting Scheme\nWe use the scheme in (6) found in [1]. A simple implementation would be the following:\n* start at the leaves and give a weight of $1$,\n* for internal nodes, sum the weights $w_s$ of each action $a$'s children nodes, $W_a$. Pick the maximum $\\max_{a} W_a$, and set that node's weight to be 2 $\\max_{a} W_a$.\n\n---\n\nAgain, we thank you for your time and we hope to have satisfactorily addressed your concerns. \n\n[1] Kroer, C., Waugh, K., Kılınç-Karzan, F. and Sandholm, T., 2020. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming."}, {"review_id": "xqnb8FqRUN", "reviewer": "Reviewer_Re8E", "summary": "The paper establishes the last‐iterate convergence guarantees for alternating policy‐gradient methods in zero‐sum, imperfect-information extensive‐form games. It observes that although the optimization over behavioral policies is nonconvex, each player’s utility is concave in the sequence-form strategy and satisfies a gradient-dominance property. By adding regularization, the authors show the utility further meets the Polyak–Łojasiewicz condition. They analyze three variants—direct parametrization, softmax parametrization, and softmax with natural policy gradients—and prove each converges in polynomial time to an $\\epsilon$-approximate Nash equilibrium. Their results bridge theory between Markov games and extensive-form games, providing a principled foundation for the practical successes of MARL in settings like Poker and Hanabi.", "questions": "(Q1) This work is closely related to Zeng et. al. (2022), where they assume that the probability of choosing all actions are lower bounded by some constant. In this work, according to Assumption 1, the authors assume that all the actions need to be sufficiently explored. What are the main differences between this work and Zeng et. al. (2022), regarding key assumptions, analysis techniques, etc. ? \n\n(Q2) What if the game exists multiple $\\epsilon$-approximated NE? Is the current framework able to identify which NE it converges to? \n\n(Q3) How would the result be to extend it to N-player? How would the polynomial-time algorithm depend on N?\n\nZeng et. al. (2022): Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: The paper is in general well-written, recognizing the research gap and provide comparisons of Markov games and imperfect-information extensive-form games. \n\nWeaknesses: \nMy major concern is the empirical validation of the work. I would appreciate it if the authors could provide further numerical or empirical results demonstrating the effectiveness of their algorithms, e.g. to compare all of the three algorithms proposed. \n\nThere are some additional questions listed in the below.", "was_revised": true, "final_justification": "I appreciate the author's response to my questions and I'll maintain my original evaluation.", "rebuttal": "Dear Reviewer, \n\nWe thank you for your positive evaluation of our work. You raise some important points that we want to address. First, regarding the **numerical validation** of our results:\n\nWe ran experiments comparing our last algorithm (alternating regularized natural policy gradient) to MMD (Sokota et al 2022) and CFR on Kuhn Poker, Leduc Poker, 2x2 Dark-Hex and Liar's Dice. In all of the experiments our algorithm's performance is comparable to the rest while in some cases it can overperform them.\n\nWe pick our last algorithm as it makes for a more fair comparison and it is closer to TRPO and PPO algorithms.\n\n---\n\nNow, answering your questions one by one:\n> * **Q1:** This work is closely related to Zeng et al. (2022), where they assume that the probability of choosing all actions is lower bounded by some constant. In this work, according to Assumption 1, the authors assume that all the actions need to be sufficiently explored. What are the main differences between this work and Zeng et al. (2022), regarding key assumptions, analysis techniques, etc.?\n\nThe assumption in Zeng et al. is an assumption on the problem. It is rather stronger than what you are mentioning. Zeng et al. assume that after regularization, there exists a problem-dependent constant, independent of the coefficient of regularization, that lower bounds the probability of all actions in a Nash equilibrium. They consider an uncosntrained parameter space as they do not need to lower bound the smallest probability of an action.\n\nOur ``assumption'' is not on the side of the game but rather on the algorithm. We also need to control the lower bound of an all actions' probability so we consider **constrained** softmax parametrization.\n\n\n> * **Q2:** What if the game has multiple \\$\\epsilon\\$-approximated Nash equilibria? Is the current framework able to identify which NE it converges to?\n\nThe regularized game always has a unique Nash equilibrium as it is a strongly monotone game [1] (Theorem 2).\n\nNonetheless, our convergence proof does not require uniqueness.\n\n> * **Q3:** How would the result extend to the N-player case? How would the polynomial-time algorithm depend on N?\n\nThis is a very interesting question. In general, computing an approximate Nash equilibrium even for 3-player zero-sum games is $\n\n---\n\nWe hope to have addressed your concerns sufficiently,\n\nSincerely, \n\nThe authors\n\n\n---\n\n[1] Rosen, J.B. \"Existence and Uniqueness of Equilibrium Points for Concave N-Person Games.\" Econometrica"}]

Author rebuttal:

Meta-review: This paper establishes last-iterate convergence guarantees for alternating policy gradient methods in imperfect-information EFGs, leveraging hidden convexity in sequence-form strategies and the Polyak–Łojasiewicz condition.

During the discussion and rebuttal, reviewers raised concerns primarily about clarity and exposition, as well as the need for more explicit details in the main text. The authors responded constructively by elaborating on the technical challenges, clarifying key definitions, and providing preliminary empirical validation on benchmark games. While some reviewers remained unconvinced that all clarity issues could be resolved within a camera-ready revision, others emphasized that the core contributions are significant, well-situated in the literature, and relevant to the MARL/EFG community.

Overall, the theoretical contribution is solid and timely, and the additional validation provided during the rebuttal period further strengthens the submission. Given the novelty, technical depth, and potential impact, this work leans toward acceptance.
Decision: Accept (poster)