acceptodds
Under review as a conference paper at ICLR 2027

Expert-Regularized Equilibrium Computation via Convex Markov Games

Abstract

We investigate the optimization landscape of Markov game equilibria that are anchored on (expert) reference policies. The technique of anchoring, coupled with self-play training, has achieved super-human performance in several games. Despite its strong empirical success, its formal analysis has lagged behind and has so far been restricted to stateless matrix games and/or direct policy parametrizations. We show that any reference-regularized Markov game can naturally be placed within the framework of a convex Markov game (cMG). This introduces a novel instance of “imitation” within the cMG framework—complementing previously recognized aspects such as behavioral imitation, creativity, safety, and equilibrium fairness. Framing the setting in this way, we establish two complementary convergence results. First, in the unconstrained case, we prove that simultaneous gradient descent-ascent converges locally to a (regularized) Nash equilibrium, offering theoretical support for the simultaneous-update schemes that dominate practice. Such guarantees, however, cannot in general be promoted to global ones: simultaneous GDA is known to fail globally even under a two-sided Polyak-Łojasiewicz condition. To obtain global convergence, we turn to softmax policies under alternating updates. We prove that saddle-point computation satisfies a two-sided (proximal) Polyak-Łojasiewicz condition for softmax parametrizations and design an alternating policy gradient scheme that converges to a (regularized) Nash equilibrium with an explicit polynomial rate and sample complexity. In doing so, we obtain the first convergence proof of softmax policy gradient to a Nash equilibrium in convex Markov games, offering a crisp theoretical justification for the use of softmax policy gradient updates in numerous practical applications.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, self-play, multi-agent reinforcement learning, nonconvex optimization, min-max optimization, PL condition

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_qcqjOpenReview ↗
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
  1. 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.

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

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)\nu(s,b)=\pi_2(b\mid s)\sum_a\mu(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×ΨRX_R\times\Psi_R, while accounting for its all-ones null direction. The resulting explicit modulus ατ\alpha_\tau 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\ell_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τU^\tau in logits, including its dependence on τ\tau, RR, 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<τ≤10<\tau\leq1, and R=Θ(log⁡(1/ϵ))R=\Theta(\log(1/\epsilon)), this bound is O(1+log⁡(1/ϵ))O(1+\log(1/\epsilon)), so the stated polynomial exponents are unchanged; outside this regime the full ℓU\ell_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)O(\epsilon^{-3}) rate for alternating softmax GDA with exact gradients. Their analysis assumes a constant c>0c>0 that lower-bounds every action probability of the entropy-regularized equilibrium uniformly over the regularization strength, and their rate depends on cc. 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.

Thank you for the response and for fixing the appendix cross-references and the inconsistency in ℓU\ell_U.

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 1\mathbf{1} (making optimal logits unbounded without an explicit centering constraint).

  • Lemma 17 & Lemma 13: Lemma 17 states a modulus of μkl/202\mu_{kl}/202, whereas its proof yields μkl/101\mu_{kl}/101 and bounds D(x,8l)\mathcal{D}(x, 8l) rather than D(x,l)\mathcal{D}(x, l), making its direct application with l=lUl = l_U 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 μKL/202\mu_{\mathrm{KL}}/202 modulus is a valid weakening of μKL/101\mu_{\mathrm{KL}}/101; that factor of two does not contradict the statement. An ℓ\ell-smooth function is also 8ℓ8\ell-smooth. The reviewer is right that this fact alone does not identify D(x,8ℓ)\mathcal D(x,8\ell) with D(x,ℓ)\mathcal D(x,\ell). We have therefore replaced the calculation with a direct proof using D(x,ℓU)\mathcal D(x,\ell_U) throughout. It yields the stronger modulus μKL/7\mu_{\mathrm{KL}}/7 under the stated normalization, so the conservative μKL/202\mu_{\mathrm{KL}}/202 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 ϵ\epsilon, τ\tau, or the game parameters. We also corrected the softmax gauge remark, removed the repeated lines, and clarified that H\mathcal H 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.

Reviewer_NDJSOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies KL-regularized equilibrium computation in finite two-player zero-sum convex Markov games. It derives curvature properties of discounted entropy and uses them to claim local linear convergence of simultaneous gradient descent-ascent and global convergence of constrained alternating softmax policy gradients. The global analysis gives explicit optimization and trajectory bounds, conditional on access to occupancy-utility derivatives, and a truncation argument for deviations over the full policy simplices. Experiments on Pig, Kuhn poker, and Oshi Zumo compare unconstrained, exact-gradient implementations of simultaneous and alternating piKL.

Critical strengths

The paper aims to extend softmax policy gradient convergence analysis to regularized convex Markov games, offering a potential foundation for developing algorithms for a broader class of Markov game settings.

Critical weaknesses
  1. Lemma 14 invokes the α\alpha-strong convexity of the regularized F~(μ)\widetilde F(\mu) to establish gradient domination, but does not establish this property under the stated assumptions. Since this step is essential to the convergence analysis, the missing justification raises a significant soundness and correctness concern.

  2. Section 6 primarily compares alternating and simultaneous updates, providing limited empirical support for the quantitative theoretical claims. It lacks systematic sensitivity analyses for the algorithm parameters, or assessment of the gap between regularized and unregularized solutions.

Questions for authors
  1. How is the α\alpha-strong convexity of F~(μ)\widetilde F(\mu) established in Lemma 14? Fixing ψ\psi gives νψ(μ)(s,b)=πψ(b∣s)∑aμ(s,a)\nu_\psi(\mu)(s,b)=\pi_\psi(b\mid s)\sum_a\mu(s,a). Convexity of F(μ,ν)F(\mu,\nu) in μ\mu for fixed ν\nu therefore does not imply convexity of the induced objective F(μ,νψ(μ))F(\mu,\nu_\psi(\mu)). What additional assumption or argument justifies the required strong convexity?

  2. Further empirical evidence, such as sensitivity analyses for the step size and regularization strength, and an examination of the gap between regularized and unregularized solutions, would help validate the theoretical guarantees of the paper.

1 comment

We thank the reviewer for identifying a gap in the stated cMG assumption. Convexity of F(μ,ν)F(\mu,\nu) with ν\nu held fixed does not imply convexity when the opponent's policy is fixed, because its occupancy changes with μ\mu. We have revised the cMG definition to state the fixed-opponent-policy concavity assumption used by Kalogiannis et al. (2025), with their two-utility convention F1=−F2F_1=-F_2 and F:=F2=−F1F:=F_2=-F_1. For every fixed opponent policy π2\pi_2, we explicitly assume that the induced player-1 utility F1(μ;π2):=F1(μ,νπ2(μ))F_1(\mu;\pi_2):=F_1(\mu,\nu_{\pi_2}(\mu)) is concave on the feasible occupancy set; equivalently, F(μ;π2)F(\mu;\pi_2) is convex. Symmetrically, F2(ν;π1):=F2(μπ1(ν),ν)F_2(\nu;\pi_1):=F_2(\mu_{\pi_1}(\nu),\nu) is concave for every fixed π1\pi_1. This assumption fixes the opponent's policy rather than their occupancy; it cannot be inferred from coordinatewise convexity/concavity with the other occupancy fixed. Conventional two-player zero-sum Markov games with per-stage rewards satisfy it: against a fixed opponent policy, the acting player's expected payoff is linear in their occupancy.

For Lemma 14, ν(μ)s,b=π2(b∣s)\nu (\mu)_{s,b} =\pi_2(b | s) $\sum_a \mu(s,a) $.

Thus player 2's reference-KL term is linear in μ\mu, whereas player 1's reference-KL term is discounted negative entropy plus a linear function. Our entropy-curvature lemma makes the latter ταH\tau\alpha_{\mathcal {H} }-strongly convex on the fixed-π2\pi_2 occupancy set. Adding the assumed convex F(μ;π2)F(\mu;\pi_2) preserves this modulus; the argument for player 2 is symmetric. The revised definition now makes the assumption needed for Lemma 14 explicit.

We also added an appendix sensitivity study varying τ\tau and the alternating step pair on Pig, Kuhn poker, Oshi Zumo, and 3×33\times3 Hex, with ten paired seeds and matched budgets within each game. For Pig, Oshi, and Hex, the trajectory plots report the full best-response gap in both the original and KL-regularized games; the heatmaps compare the original-game gap. Kuhn reports only the original-game gap and is outside our cMG theorem. The two gaps expose a finite-time optimization/bias tradeoff: for Oshi at 30,00030{,}000 iterations and steps (3,30)(3,30), τ=0.05\tau=0.05 gives mean (original, regularized) gaps (0.3856,0.0728)(0.3856,0.0728), while τ=0.1\tau=0.1 gives (0.4712,0.00578)(0.4712,0.00578). As a separate equilibrium-bias check, exact KL equilibria in Pig have original-game gaps approximately 00, 9.65×10−69.65\times10^{-6}, and 0.31860.3186 at τ=0.001,0.01,0.1\tau=0.001,0.01,0.1, respectively. These experiments use exact gradients and unconstrained logits, so they illustrate sensitivity rather than test the constrained-softmax stochastic guarantee.

Reviewer_7UsvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors study expert-anchored self-play in zero-sum Markov games of two players. Expert anchoring means that the players' utilities are regularized based on the KL divergence between their policies and a pair of reference policies. The authors cast these games as convex zero-sum Markov Games (cMG) and study properties of expert KL-regularization and derive (1) convergence of local simultaneous GDA (2) global convergence of alternating softmax policy gradients (Alt-piKL) in cMGs and provide convergence rates/costs.

Critical strengths

The connections made in this work are interesting in practice for someone interested in this specific type of regularization, that is by experts' policies. The authors manage to connect slightly different definitions and classical properties/assumptions that are used for convergence in MGs (like PŁ conditions) in a clever way. The study of the properties of expert-KL regularization and their consequences on convergence in games of certain procedures seems to me the central part of this work. Some of those seems to be potentially useful in future work as well.

Critical weaknesses

A major problem of the paper for me is the presentation. Starting from Section 3, I feel like it is not as flawless as it should be. Even if the authors stated in the Introduction which results they were going to prove, somehow it was difficult for me to really understand the flow and consequential order of them in the paper. This can be due to various things: it is very compact, the preliminaries section is very long and there are many definitions and previous results involved. There are other problems as well. For instance, on page 6 it seems that the statement of a result is missing at line 312 (that, to my understanding, is reported in the appendices as Lemma 14). Moreover, the results reported in the appendices do not share the same numbers with the ones in the main paper, making it difficult to clearly connect them.

Another point is the convergence rates of Theorem 9 and Corollary 10. I suppose these have to be considered more of theoretical statements, but one wonders if they are comparable with other results on these games or they can be made better somehow. A discussion about it would benefit this work, in my opinion.

Questions for authors

Can you comment about the convergence rates/computational costs result?

1 comment

We thank the reviewer for their valuable comments. We updated the draft following their corrections.

Our new results are a local linear convergence theorem for simultaneous GDA, a two-sided pPŁ bound for reference-KL cMGs under constrained softmax, and softmax policy gradient rates for cMDPs and cMGs with explicit dependence on problem parameters. The global alternating result applies the theorem of Kalogiannis et al., which we credit to them. Below we explain the proof order and compare convergence rates.

Regarding Section 3: We now point directly to the two-sided pPŁ statement in Appendix Lemma 13. The steps are: Lemma 5 gives curvature of discounted entropy in occupancy space; Lemma 7 shows that regularizing both players preserves the needed convexity and concavity; and Appendix Lemma 13 gives the pPŁ modulus for constrained softmax policies. We then apply the alternating pPŁ theorem of Kalogiannis et al. (2025, Theorem 3.4 / D.8) and the REINFORCE bounds to prove Theorem 9. Corollary 10 chooses the logit radius and regularization strength to obtain an unregularized ϵ\epsilon-NE. We have removed repeated appendix statements and added direct links to the proofs.

For fixed τ\tau, Theorem 9 and the full-simplex approximation give O~(τ−3ϵ−6)\widetilde O(\tau^{-3}\epsilon^{-6}) alternating iterations, O~(τ−6ϵ−13)\widetilde O(\tau^{-6}\epsilon^{-13}) trajectories, and O~((1−γ)−1τ−6ϵ−13)\widetilde O((1-\gamma)^{-1}\tau^{-6}\epsilon^{-13}) sampled transitions for an ϵ\epsilon-RNE. Corollary 10 takes τ=Θ(ϵ)\tau=\Theta(\epsilon) to obtain an ϵ\epsilon-NE of the unregularized game, requiring O~(ϵ−9)\widetilde O(\epsilon^{-9}) iterations and O~(ϵ−19)\widetilde O(\epsilon^{-19}) trajectories. One iteration updates each player once and uses two joint gradient evaluations. These counts assume access to z=∇μFz=\nabla_\mu F as a pseudo-reward; they do not include the cost of computing it.

We do not claim a faster rate than prior methods. The ατ−3\alpha_\tau^{-3} iteration dependence comes from the alternating pPŁ theorem of Kalogiannis et al.; our new step is to establish its two-sided condition for reference-KL cMGs with constrained softmax. Zeng et al. (2022) obtain O(ϵ−3)O(\epsilon^{-3}) exact-gradient updates for a standard Markov game, but assume that every regularized equilibrium policy has action probabilities bounded below uniformly in τ\tau. Kalogiannis et al. also give an O(ϵ−6)O(\epsilon^{-6}) iteration bound for general cMGs using a different regularization and output rule. These results use different assumptions and oracle costs, so their iteration counts are not direct sample-cost comparisons.

The main source of our exponent is ατ∝τe−4R\alpha_\tau\propto\tau e^{-4R}. To approximate deviations over the full policy simplices, we take R=Θ(log⁡(1/ϵ))R=\Theta(\log(1/\epsilon)); the imported rate then scales as ατ−3\alpha_\tau^{-3}. The batch size adds to the trajectory cost. A sharper modulus or a different algorithm might improve these bounds.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.