- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the convergence of expert-KL-regularized policy gradient methods in two-player zero-sum convex Markov games. The authors show that reference-KL regularization preserves the convex-concave structure in occupancy space and establish a two-sided proximal Polyak–Łojasiewicz (pPŁ) condition under constrained softmax policy parameterization. Building on these properties, they prove local convergence of simultaneous gradient descent-ascent (GDA) and global convergence of alternating regularized policy gradient, with explicit polynomial complexity bounds. The theoretical results are complemented by experiments on three games.
Critical strengths
The paper addresses a meaningful problem concerning the convergence of regularized policy gradient methods in two-player zero-sum Markov games. The theoretical analysis appears generally sound, and establishing convergence guarantees under softmax policy parameterization is potentially valuable.
Critical weaknesses
-
Limited novelty relative to prior work. The main convergence result (Theorem 9) appears to follow primarily from Theorem 21 in the appendix, which restates an existing result from Kalogiannis et al. (2025). As far as I understand, the main additional technical contribution is verifying the two-sided pPŁ condition for the reference-KL-regularized objective under constrained softmax parameterization. While this is useful, it is unclear whether it constitutes a sufficiently substantial theoretical advance over prior work. The authors should more clearly distinguish their new technical contributions from existing results.
-
Clarity and consistency of the presentation. Some key results are restated in the appendix under different theorem numbers without explicit cross-references, making the logical dependencies difficult to follow. There are also inconsistencies in notation and definitions, such as the different expressions for the smoothness constant (\ell_U) in Lemmas 2 and 4. These issues make it harder to assess the precise assumptions and contributions of the theoretical results.
Questions for authors
Could the authors clarify the main technical novelty relative to Kalogiannis et al. (2025)? In particular, beyond establishing the two-sided pPŁ condition for reference-KL regularization under constrained softmax parameterization, are there any fundamentally new proof techniques or convergence arguments? It would be helpful to explain why this verification is technically nontrivial and what new theoretical insights or guarantees it provides beyond a direct application of existing convergence theorems.
3 comments
Thank you for the response and for fixing the appendix cross-references and the inconsistency in .
While these revisions improve clarity, the manuscript still feels somewhat rough and requires further technical polishing. Several mathematical issues remain:
-
Theorem 6 & Remark 1: The proof invokes Lemma 21 (which requires an isolated minimum) under only a local PŁ assumption without establishing isolation. Moreover, Remark 1 claims unconstrained softmax yields bounded optimal logits, overlooking that softmax is shift-invariant along the all-ones direction (making optimal logits unbounded without an explicit centering constraint).
-
Lemma 17 & Lemma 13: Lemma 17 states a modulus of , whereas its proof yields and bounds rather than , making its direct application with in Lemma 13 inconsistent.
-
Drafting errors: Minor typos persist, such as duplicated lines in the proof of Lemma 13 and a missing negative sign in the discounted entropy definition (Section 2.3).
More fundamentally, the clarification confirms that the main global guarantee (Theorem 9) is a direct application of Kalogiannis et al. (2025) once the pPŁ modulus is verified, while Theorem 6 relies on a standard linearization argument. Given the limited novelty and remaining technical roughness, I will maintain my original score.
We respectfully disagree that the use of an existing optimization theorem or a standard stability criterion makes the contribution routine. This is a paper about equilibrium learning in reference-regularized Markov games. The game-specific work is to show that regularizing both players preserves unilateral occupancy curvature, transfer that curvature through the occupancy and constrained-softmax maps to an explicit two-sided pPŁ modulus, and obtain last-iterate and sampled-gradient guarantees for cMGs, including ordinary zero-sum Markov games. To our knowledge, this game-specific softmax guarantee was not previously established. Kalogiannis et al.'s alternating theorem supplies the final optimization implication; it does not establish these hypotheses or rates for this game class and policy parameterization.
The local simultaneous-GDA result also merits assessment by its statement, rather than by the familiarity of Lyapunov's linearization criterion. There is extensive work on nonconvex min–max dynamics, but the closest results address different dynamics: Doan (2022) studies continuous-time, two-timescale GDA, while Mourrat (2026, Proposition 1.3) proves local convergence of the continuous-time GDA flow and explicitly leaves the discrete-time case open. To our knowledge, the local linear guarantee for discrete-time, simultaneous equal-step GDA under the stated global two-sided PŁ and bounded-optimizer assumptions had not previously been established. We strengthened its proof using Ben Nejma's recent uniqueness and local-curvature result: isolation follows from the assumptions rather than being postulated.
On the constants, the claimed modulus is a valid weakening of ; that factor of two does not contradict the statement. An -smooth function is also -smooth. The reviewer is right that this fact alone does not identify with . We have therefore replaced the calculation with a direct proof using throughout. It yields the stronger modulus under the stated normalization, so the conservative bound and the ensuing rates remain valid. In any case, factors of two or eight alter only universal constants in the iteration and trajectory bounds; they do not change any claimed polynomial dependence on , , or the game parameters. We also corrected the softmax gauge remark, removed the repeated lines, and clarified that denotes discounted negative entropy.
We appreciate the careful reading, but respectfully ask that the novelty assessment account for the game-specific geometry and discrete-time guarantee, rather than the fact that the final steps invoke established optimization and stability tools.
We thank the reviewer for asking us to distinguish the new results from prior work. The alternating pPŁ theorem used for our global guarantee is due to Kalogiannis et al. (2025, Theorem 3.4 / D.8); we now identify it as an imported premise. Our new results are (i) a separate local linear convergence theorem for simultaneous GDA, proved by a direct stability argument under local two-sided PL and the stated boundedness condition, and (ii) a quantitative two-sided pPŁ condition for reference-KL cMGs with constrained softmax policies. The latter gives explicit softmax policy gradient rates for cMDPs and two-player cMGs, including ordinary zero-sum Markov games. Theorem 9 applies the imported alternating theorem once this condition is established; we do not claim a new abstract alternating-GDA theorem.
The pPŁ verification is more than adding KL to a known bound. With the opponent policy fixed, its occupancy satisfies ν(s,b)=π2(b∣s)∑aμ(s,a), so the opponent's KL term is linear in the acting player's occupancy. The acting player's reference-KL term retains the strong curvature of discounted negative entropy. We prove these statements for both players, then transfer the occupancy bound to softmax logits. This requires controlling the occupancy inverse and the nonzero singular values of the softmax Jacobian on XR×ΨR, while accounting for its all-ones null direction. The resulting explicit modulus ατ is the hypothesis needed by the imported theorem.
We have added a brief dependency chain after Theorem 9 and direct main-text/appendix cross-references to make the proof dependencies and numbering clear. The reviewer is also right that the previous ℓU formulas were inconsistent. We corrected Lemma 2 to bound the unregularized logit objective, including the softmax chain rule, and Lemma 4 to bound the smoothness of Uτ in logits, including its dependence on τ, R, and the full-support reference policies. The proofs are in Appendix B.1. All convergence statements now use the regularized bound from Lemma 4. For fixed game and references, 0<τ≤1, and R=Θ(log(1/ϵ)), this bound is O(1+log(1/ϵ)), so the stated polynomial exponents are unchanged; outside this regime the full ℓU dependence must be retained.
Zhang et al. (2020) analyze single-agent general utilities under structural conditions, while Zhang et al. (2022) study Markov potential games. For standard zero-sum Markov games, Zeng, Doan, and Romberg (2022) obtain an O(ϵ−3) rate for alternating softmax GDA with exact gradients. Their analysis assumes a constant c>0 that lower-bounds every action probability of the entropy-regularized equilibrium uniformly over the regularization strength, and their rate depends on c. Our constrained-softmax rate has no dependence on this unknown equilibrium-support constant and does not require that assumption: it gives explicit dependence on the logit radius, regularization strength, and problem parameters for reference-KL cMGs, including standard zero-sum Markov games. Our rate has a different exponent and uses sampled policy gradients, so we do not claim a faster iteration bound.