Nash Policy Gradient: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria

## Abstract

Abstract Finding Nash equilibria in imperfect-information games remains a central challenge in multi-agent reinforcement learning. While regularization-based methods have recently achieved last-iteration convergence to a regularized equilibrium, they require the regularization strength to shrink toward zero to approximate a Nash equilibrium, often leading to unstable learning in practice. Instead, we fix the regularization strength at a large value for robustness and achieve convergence by iteratively refining the reference policy. Our main theoretical result shows that this procedure guarantees strictly monotonic improvement and convergence to an exact Nash equilibrium in two-player zero-sum games, without requiring a uniqueness assumption. Building on this framework, we develop a practical algorithm, Nash Policy Gradient ( NashPG ), which preserves the generalizability of policy gradient methods while relying solely on the current and reference policies. Empirically, NashPG achieves comparable or lower exploitability than prior model-free methods on classic benchmark games and scales to large domains such as Battleship and No-Limit Texas Hold’em , where NashPG consistently attains higher Elo ratings.

## 1 Introduction

The success of Deep Reinforcement Learning has sparked significant interest in Multi-agent Reinforcement Learning (MARL) [7, 31], where algorithms must handle environments with multiple interacting agents. While impressive results have been achieved in settings with fully known environment models and perfect-information [32, 33], learning in imperfect-information games remains challenging, as agents must reason under uncertainty about their opponents to approach Nash equilibria.

In multi-agent systems, Nash equilibria serve as the central solution concept: no agent can unilaterally improve its payoff. In two-player zero-sum games, these equilibria correspond to strategies that are unexploitable even against optimal adversaries. Traditionally, the most prominent approaches in these games have been *CFR-inspired methods* [22] and *population-based methods* [1]. However, both come with drawbacks: CFR-inspired methods requires access to an exact environment model to perform well, while population-based methods are computationally expensive as they require training multiple agents from scratch. Further, both approaches typically offer only average-iteration convergence guarantees, which are inconvenient in deep learning contexts. These limitations hinder their adoption as general-purpose solvers.

Recently, a new class of regularization-based methods [23] has emerged. These approaches add a regularization term in objective function [14], which guarantees last-iteration convergence to a regularized equilibrium. To approximate Nash equilibria, they typically rely on setting the regularization strength to be small or gradually decaying it. However, these methods have yet to demonstrate strong empirical success beyond tabular settings where exact, non-sampled feedback is accessible. A key challenge is that when the regularization strength becomes too small, noise in stochastic gradient estimations can dominate the diminishing regularization signal, leading to cycling or even divergence. As a result, training is highly sensitive to careful tuning of both the regularization parameter and the learning rate.

Motivated by these challenges, we propose an alternative: instead of decaying the regularization strength, we fix it at a large value for robustness and achieve convergence by iteratively refining the reference policy. Our main theoretical result shows that this iterative-refinement procedure ensures strictly monotonic improvement and convergence to a Nash equilibrium, without assuming uniqueness of the Nash equilibrium.

###### Theorem 1 (Informal) .

For a two-player zero-sum game, let $z^{*}$ be any Nash equilibrium. Starting from an initial policy $z_{0}$, our proposed iterative-refinement procedure generates a sequence of policies $\{z_{t}\}$ such that

$$ $B_{\psi}(z^{*};z_{t})>B_{\psi}(z^{*};z_{t+1}),$ (1) $$

whenever convergence has not yet occurred. Here, $B_{\psi}$ denotes the Bregman divergence with generating function $\psi$. Moreover, the sequence is guaranteed to converge to a Nash equilibrium, i.e., $\lim_{t\to\infty}z_{t}$ is a Nash equilibrium.

Building on this theory, we adapt the procedure into a practical MARL algorithm, which we call *Nash Policy Gradient* (NashPG). NashPG retains the advantages of standard policy gradient methods, allowing decentralized updates where each agent updates its policy without explicitly reasoning about others. Additionally, it is lightweight, requiring only the maintenance of current and reference policies. Despite departing from the exact theoretical setting, NashPG empirically converges to Nash equilibria. In experiments, we show that NashPG achieves comparable or lower exploitability than prior model-free methods on classic benchmark games. To demonstrate scalability, we further evaluate NashPG on large-scale real-world domains such as Battleship and No-Limit Texas Hold’em, where it consistently achieves higher Elo ratings.

###### Theorem 1 (Informal) .

## 2 Related Work

Existing methods for solving two-player zero-sum imperfect-information games in MARL can be broadly partitioned into three categories.

Population-Based Methods.
Population-based methods, such as Neural Fictitious Self-Play (NFSP) [13] and Policy Space Response Oracles (PSRO) [17], iteratively compute best-responses against mixtures of prior policies using deep reinforcement learning (DRL). These model-free approaches scale to complex domains like StarCraft [36]. However, they require repeated best-response computations, resulting in high computational overhead. Moreover, they only guarantee average-iterate convergence where policy extraction is non-trivial in DRL settings, often requiring supervised learning or the storage of historical agents to obtain a final policy. Recent works have focused on accelerating empirical convergence [26, 24].

CFR-Inspired Methods.
Counterfactual Regret Minimization (CFR) [37], most notable for its success in poker games, enabled superhuman performance in heads-up limit Texas Hold’em [4]. Deep CFR [6] integrates function approximation for larger state spaces. However, CFR relies on explicit game models for tree traversal, which limits its generalizability, and often relies on high-variance sampling to estimate counterfactual values. While some model-free variants do exist [35], they still suffer from large variance issues, and variance-reduction techniques [25] can introduce exploration biases. Like population-based methods, CFR approaches typically guarantee only average-iterate convergence, requiring additional steps to extract a final policy.

Regularization-Based Methods.
Recent regularization-based algorithms address last-iterate convergence by reformulating games with strongly convex-concave objectives, typically converging to entropy-regularized Nash equilibria such as Quantal Response Equilibria (QRE) [27]. Several works [8, 34, 23] establish linear convergence rates to QRE, demonstrating the efficiency of solving regularized games. This has spurred efforts to reach exact Nash equilibria, often through decaying regularization strengths or adaptive step sizes [23, 15, 21]. While effective in tabular settings with exact feedback, it remains unclear whether these techniques are robust to stochastic sampling errors, which risk instability or cycling [10]. We include an empirical study of this issue in Appendix [C.1](https://arxiv.org/html/2510.18183v1#A3.SS1). Some theoretical convergence to Nash equilibria has been shown [9, 20, 28], but these results require the assumption of a unique Nash equilibrium or that all Nash equilibria are interior. Empirically, regularization-based methods remain underexplored beyond normal-form games or simple extensive-form benchmarks (e.g., Kuhn or Leduc poker) where exact feedback is accessible.

## 3 Preliminaries

In this paper, we focus on analyzing two-player zero-sum games. We first establish the necessary background and notation for extensive-form games, then present their connection to variational inequality problems and regularized variants that form the foundation of our approach. We use standard mathematical notation for concepts such as L-smoothness, strong convexity, monotonicity, and Bregman divergence (see Appendix [A.1](https://arxiv.org/html/2510.18183v1#A1.SS1) for formal definitions).

### 3.1 Game Theory Background

We consider two-player zero-sum extensive-form games (EFG) with perfect recall. The game is represented by a finite game tree with the following components: Let the players be denoted by $i\in\{1,2\}$. The set of states is denoted by ${\mathcal{S}}$, with terminal states ${\mathcal{Q}}\subseteq{\mathcal{S}}$ determining payoffs, where player 1’s payoff is the negative of player 2’s payoff. Each non-terminal state $s\in{\mathcal{S}}\setminus{\mathcal{Q}}$ is controlled by either a player or chance. For each player $i$, decision nodes are partitioned into information sets $I\in{\mathcal{I}}_{i}$, where the player cannot distinguish between states within the same information set. The set of actions available at information set $I$ is denoted by $A(I)$. A behavioral strategy for player $i$ is a mapping $\pi^{(i)}\colon{\mathcal{I}}_{i}\to\Delta(A(I))$, assigning a probability distribution over actions at each information set. A strategy profile $\pi$ is a collection of both players’ strategies, and $\pi^{(-i)}$ refers to player $i$’s opponent strategy.

A two-player zero-sum extensive-form game induces an equivalent normal-form game [16] with payoff matrix ${\bm{A}}$, where each row and column correspond to a pure strategy (deterministic action plan across all information sets) for players 1 and 2, respectively. A mixed strategy is a probability distribution over pure strategies. Let ${\mathcal{X}}$ and ${\mathcal{Y}}$ denote the mixed strategy spaces for players 1 and 2, with $x\in{\mathcal{X}}$ and $y\in{\mathcal{Y}}$ representing their mixed strategies. The payoff function $f(x,y)=x^{\top}{\bm{A}}y$ gives player 1’s expected payoff, similarly, player 2’s expected payoff is is $-f(x,y)$. When referring to mixed strategies in EFGs, we refer to those defined through this normal-form representation.

A Nash equilibrium (NE) is a strategy profile $\pi^{*}=(\pi^{(1)*},\pi^{(2)*})$ in behavioral strategies or $z^{*}=(x^{*},y^{*})$ in mixed strategies, where each player’s strategy is a best-response to the other’s. Formally, for the normal-form representation, a Nash equilibrium satisfies:

$$ $x^{*}\in\arg\max_{x\in{\mathcal{X}}}f(x,y^{*})\quad\text{and}\quad y^{*}\in\arg\max_{y\in{\mathcal{Y}}}-f(x^{*},y)$ $$

That is, no player can improve their expected payoff by unilaterally deviating from their equilibrium strategy. Our goal is to develop efficient algorithms to find Nash equilibria in these games.

### 3.2 Connection With Variational Inequality

Finding the Nash equilibrium is equivalent to solving the variational inequality (VI) problem, which forms the foundation for understanding both the challenges and opportunities in our approach.

###### Definition 1 (Variational Inequality Problem) .

Given a closed convex set ${\mathcal{Z}}\subseteq\mathbb{R}^{n}$ and a mapping $G:{\mathcal{Z}}\to\mathbb{R}^{n}$, the variational inequality problem $\mathrm{VI}({\mathcal{Z}},G)$ is to find $z^{*}\in{\mathcal{Z}}$ such that

$$ $\langle G(z^{*}),z-z^{*}\rangle\geq 0\quad\forall z\in{\mathcal{Z}}.$ (2) $$

In a two-player zero-sum extensive-form game, let ${\mathcal{X}}$ and ${\mathcal{Y}}$ denote the mixed strategy spaces for players 1 and 2, respectively, and let ${\bm{A}}$ be the payoff matrix of the equivalent normal-form game. We recall the fundamental connection between Nash equilibria and variational inequalities by defining ${\mathcal{Z}}={\mathcal{X}}\times{\mathcal{Y}}$ with strategy profile $z=(x,y)\in{\mathcal{Z}}$ and the operator $F\colon{\mathcal{Z}}\to\mathbb{R}^{n}$:

$$ $F(z)=\begin{bmatrix}-\nabla_{x}f(x,y)\\ \nabla_{y}f(x,y)\end{bmatrix}$ (3) $$

where $f(x,y)=x^{\top}{\bm{A}}y$ is the payoff function.

###### Theorem 2 (Nash-VI Equivalence) .

A strategy profile $z^{*}\in{\mathcal{Z}}$ is a Nash equilibrium if and only if it solves the variational inequality problem $\mathrm{VI}({\mathcal{Z}},F)$ [11, Section 1.4.2]:

$$ $\langle F(z^{*}),z-z^{*}\rangle\geq 0\quad\forall z\in{\mathcal{Z}}.$ (4) $$

Thus, computing Nash equilibrium reduces to solving $\mathrm{VI}({\mathcal{Z}},F)$. However, this creates a significant computational challenge: The operator $F$ is monontone but not strongly monotone, making $\mathrm{VI}({\mathcal{Z}},F)$ difficult to solve directly.

###### Definition 1 (Variational Inequality Problem) .

###### Theorem 2 (Nash-VI Equivalence) .

### 3.3 Regularized Variational Inequality

To address the lack of strong monotonicity, Sokota et al. [34] consider a *regularized* VI problem $\mathrm{VI}({\mathcal{Z}},G_{\rho})$, where a strongly convex regularizer is added to the operator $F$. The resulting operator $G_{\rho}$ becomes *strongly monotone*, ensuring a unique solution [19] and enabling efficient algorithms.

Formally, let $\rho=(\rho_{1},\rho_{2})\in{\mathcal{Z}}$ be a reference strategy profile. With a strongly convex function $\psi(z)=\psi_{1}(x)+\psi_{2}(y)$, the associated Bregman divergence is

$$ $B_{\psi}(z;\rho)=B_{\psi_{1}}(x;\rho_{1})+B_{\psi_{2}}(y;\rho_{2}),$ (5) $$

where $\psi_{1}$ and $\psi_{2}$ are strongly convex for each player. The regularized operator $G_{\rho}:{\mathcal{Z}}\to\mathbb{R}^{n}$ is

$$ $G_{\rho}(z)=F(z)+\alpha\nabla_{z}B_{\psi}(z;\rho),$ (6) $$

with regularization parameter $\alpha>0$. The corresponding variational inequality seeks $\hat{z}\in{\mathcal{Z}}$ such that

$$ $\langle G_{\rho}(\hat{z}),z-\hat{z}\rangle\geq 0\quad\forall z\in{\mathcal{Z}}.$ (7) $$

Under Assumption [1](https://arxiv.org/html/2510.18183v1#Thmassumption1), The VI problem $\mathrm{VI}({\mathcal{Z}},G_{\rho})$ can be solved efficiently by Magnetic Mirror Descent (MMD) [34]:

###### Assumption 1 (MMD’s Convergence Conditions) .

- 1.
$\psi$ is $\mu$-strongly convex over ${\mathcal{Z}}$ and differentiable on $\operatorname{int}\operatorname{dom}\psi$ for some $\mu>0$.
- 2.
$z_{t+1}\in\operatorname{int}\operatorname{dom}\psi$ for all iterations.
- 3.
$F$ is $L$-smooth and $\alpha,\eta$ satisfy $\alpha\geq\mu\eta L^{2}$.

###### Algorithm 1 (Magnetic Mirror Descent (MMD)) .

Initialize $z_{0}=(x_{0},y_{0})\in\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$, reference $\rho=(\rho_{1},\rho_{2})\in\operatorname{int}\operatorname{dom}\psi$, and step size $\eta>0$. At each iteration $t$:

$$ $\displaystyle x_{t+1}$ $\displaystyle=\operatorname*{arg\,max}_{x\in{\mathcal{X}}}\Big\{\eta\big(\langle\nabla_{x_{t}}f(x_{t},y_{t}),x\rangle-\alpha B_{\psi_{1}}(x;\rho_{1})\big)-B_{\psi_{1}}(x;x_{t})\Big\},$ $\displaystyle y_{t+1}$ $\displaystyle=\operatorname*{arg\,min}_{y\in{\mathcal{Y}}}\Big\{\eta\big(\langle\nabla_{y_{t}}f(x_{t},y_{t}),y\rangle+\alpha B_{\psi_{2}}(y;\rho_{2})\big)+B_{\psi_{2}}(y;y_{t})\Big\}.$ $$

With Assumption [1](https://arxiv.org/html/2510.18183v1#Thmassumption1), MMD converges to the unique solution of $\mathrm{VI}({\mathcal{Z}},G_{\rho})$.

However, this creates a fundamental limitation of using MMD as a Nash equilibrium solver. To recover the exact equilibrium, one must shrink $\alpha\to 0$ so that $G_{\rho}$ closely approximates the original operator $F$. Yet Assumption [1](https://arxiv.org/html/2510.18183v1#Thmassumption1) requires $\alpha\geq\mu\eta L^{2}$, forcing either vanishingly small stepsizes (and thus negligible progress) or risking divergence when the condition is violated. Conversely, keeping $\alpha$ large ensures stability and efficient updates but biases the solution away from the true equilibrium, since $G_{\rho}$ no longer approximates $F$. Thus, there is an inherent tension between approximation quality (small $\alpha$) and algorithmic stability (large $\alpha$). This motivates our approach, which breaks this tradeoff by allowing large $\alpha$ while still guaranteeing convergence to a Nash equilibrium.

###### Assumption 1 (MMD’s Convergence Conditions) .

###### Algorithm 1 (Magnetic Mirror Descent (MMD)) .

## 4 Methodology

We propose a new approach to computing Nash equilibria based on *iteratively refined regularization*. Unlike prior methods that rely on shrinking the regularization strength $\alpha$ to approximate the original VI problem $\mathrm{VI}({\mathcal{Z}},F)$, we instead solve a sequence of regularized problems $\mathrm{VI}({\mathcal{Z}},G_{\rho})$, where the solution from each step becomes the reference strategy profile $\rho$ for the next.

Our approach unfolds in two stages. First, we establish the theoretical basis of this iterative procedure (Sections [4.1](https://arxiv.org/html/2510.18183v1#S4.SS1)–[4.2](https://arxiv.org/html/2510.18183v1#S4.SS2)), proving strictly monotone improvement and convergence to a Nash equilibrium without assuming uniqueness. Next, we derive a practical algorithm, *Nash Policy Gradient* (NashPG), via a series of approximations (Section [4.3](https://arxiv.org/html/2510.18183v1#S4.SS3)), yielding a method that integrates naturally with reinforcement learning (RL) frameworks.

### 4.1 Regularized VI as an Operator

We begin by viewing the regularized VI problem as an operator that maps a reference strategy profile $\rho$ to the unique solution of $\mathrm{VI}({\mathcal{Z}},G_{\rho})$.

###### Definition 2 (Regularized VI Operator) .

Define the operator ${\mathcal{M}}:\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}\to\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$, where the input is the reference strategy profile $\rho$ and the output ${\mathcal{M}}(\rho)$ is the unique solution of $\mathrm{VI}({\mathcal{Z}},G_{\rho})$. We assume ${\mathcal{M}}(\rho)\in\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$.

Our theoretical results show that this operator satisfies three key properties.

First, applying ${\mathcal{M}}$ never increases the Bregman divergence to a Nash equilibrium. This establishes the soundness of ${\mathcal{M}}$ as a refinement step.

[Distance Non-increase Property]lemmadistancenonincreaselemma
Given $\alpha>0$, let $\rho\in\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$ and $z^{*}$ be any Nash equilibrium (i.e., a solution of $\mathrm{VI}({\mathcal{Z}},F)$). Then:

$$ $B_{\psi}(z^{*};\rho)\geq B_{\psi}(z^{*};{\mathcal{M}}(\rho))+B_{\psi}({\mathcal{M}}(\rho);\rho).$ (8) $$

(Proof in Appendix [A.4.1](https://arxiv.org/html/2510.18183v1#A1.SS4.SSS1).)

Second, the fixed points of ${\mathcal{M}}$ are precisely the Nash equilibria. In other words, once the procedure reaches a Nash equilibrium, it remains there, this naturally characterizes the termination criterion for our refinement process.

[Fixed Point Characterization]lemmafixedpointlemma
A strategy profile $z^{*}\in{\mathcal{Z}}$ is a Nash equilibrium if and only if it is a fixed point of the regularized VI operator: $z^{*}={\mathcal{M}}(z^{*})$.
(Proof in Appendix [A.4.2](https://arxiv.org/html/2510.18183v1#A1.SS4.SSS2).)

Finally, the operator ${\mathcal{M}}$ is continuous, which will be useful in establishing convergence guarantees in the next section.

[Continuity of ${\mathcal{M}}$]lemmacontinuitylemma
Assume $\psi$ is $\mu$-strongly convex and continuously differentiable on
$\operatorname{int}\operatorname{dom}\psi$ for some $\mu>0$. Then the operator ${\mathcal{M}}$ is continuous.
(Proof in Appendix [A.4.3](https://arxiv.org/html/2510.18183v1#A1.SS4.SSS3).)

###### Definition 2 (Regularized VI Operator) .

### 4.2 Iterative Refinement toward Equilibrium

Motivated by the above properties, we propose the following procedure: starting from an arbitrary strategy profile, repeatedly apply the operator ${\mathcal{M}}$ until convergence.

###### Algorithm 2 (Iterative ${\mathcal{M}}$ Method) .

Starting with $z_{0}\in\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$, at each iteration $t$ compute:

$$ $z_{t+1}={\mathcal{M}}(z_{t})$ (9) $$

Where we assume $z_{t}\in\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$ for all iterations.

The convergence guarantee follows from Lemmas [2](https://arxiv.org/html/2510.18183v1#Thmdefinition2) and [2](https://arxiv.org/html/2510.18183v1#Thmdefinition2) and the continuity of ${\mathcal{M}}$. We show that each refinement step *strictly* reduces the Bregman divergence to any Nash equilibrium until convergence is reached.

[Convergence of Iterative ${\mathcal{M}}$]theoremconvergencetheorem
Let $z^{*}$ be any Nash equilibrium. Algorithm [2](https://arxiv.org/html/2510.18183v1#Thmalgorithmdef2) generates a sequence $\{z_{t}\}$ such that

$$ $B_{\psi}(z^{*};z_{t})>B_{\psi}(z^{*};z_{t+1}),$ (10) $$

whenever convergence has not yet occurred. Moreover, the sequence is guaranteed to converge to a Nash equilibrium, i.e., $\lim_{t\to\infty}z_{t}$ is a Nash equilibrium.
(Proof in Appendix [A.4.4](https://arxiv.org/html/2510.18183v1#A1.SS4.SSS4).)

To implement this iterative method, we employ MMD to solve each regularized VI subproblem. Under Assumption [1](https://arxiv.org/html/2510.18183v1#Thmassumption1), this yields a theoretically well-justified algorithm for finding Nash equilibria in two-player zero-sum games (Algorithm [1](https://arxiv.org/html/2510.18183v1#alg1)). Crucially, our approach introduces no additional assumptions beyond those required for MMD convergence, and we allows $\alpha$ to be set to large values that easily satisfy the convergence constraint $\alpha\geq\mu\eta L^{2}$, while still guaranteeing convergence to a Nash equilibrium.

Figure: Algorithm 1 MMD-based Iterative ${\mathcal{M}}$ Method

###### Algorithm 2 (Iterative ℳ {\mathcal{M}} Method) .

### 4.3 Practical Implementation: Nash Policy Gradient Algorithm

Although Algorithm [1](https://arxiv.org/html/2510.18183v1#alg1) provides theoretical guarantees, its reliance on mixed strategies makes it unclear how to mitigate the exponential complexity in the size of the game tree. To address this computational barrier, we develop a practical approximation that preserves the iterative refinement structure while enabling efficient implementation in RL frameworks.

##### From Mixed Strategies to Behavioral Strategies.

We illustrate the transformation for player 1, the case for player 2 is symmetric. Consider the mirror-ascent subproblem in line 7 of Algorithm [1](https://arxiv.org/html/2510.18183v1#alg1). Setting $\psi_{1}$ to the negative entropy (the canonical choice on the probability simplex) shows that, for sufficiently small step size $\eta$, the mirror step is first-order equivalent to a gradient ascent step on the regularized objective:

$$ $g(x_{t,k})=f(x_{t,k},y_{t,k})-\alpha D_{\mathrm{KL}}(x_{t,k}\,\|\,\rho_{1}).$ (11) $$

This mixed-strategy formulation inspired a behavioral strategy analogue. For behavioral strategy profile $\pi=(\pi^{(1)},\pi^{(2)})$ and reference behavioral strategy profile $\rho=(\rho^{(1)},\rho^{(2)})$, we design the analogous objective:

$$ $g(\pi^{(1)})=\mathbb{E}_{\tau\sim\pi}[R_{1}(\tau)]-\alpha\,\mathbb{E}_{o\sim\pi}\Big[D_{\mathrm{KL}}\big(\pi^{(1)}(\cdot\mid o)\,\|\,\rho^{(1)}(\cdot\mid o)\big)\Big]$ (12) $$

where $R_{1}(\tau)$ denotes player 1’s payoff along trajectory $\tau$ (a path of actions to a terminal node), $o$ denotes an observation (information set) of player 1, and both trajectories $\tau$ and observations $o$ are sampled under the strategy profile $\pi$. The first term preserves the expected payoff structure, while the regularization term aggregates Kullback–Leibler (KL) divergences across all observations. This design choice for regularization enables efficient estimation within RL frameworks, though it introduces a heuristic element by depending on the opponent’s strategy $\pi^{(2)}$.

##### Connection to Partially Observable MDPs.

The shift to behavioral strategies allows a crucial reduction to single-agent RL. When opponent’s strategy $\pi^{(-i)}$ is fixed, the game reduces to a Partially Observable Markov Decision Process (POMDP) from player $i$’s perspective [12]. In this view, a behavioral strategy is equivalent to a stochastic policy in POMDP. Thus, we can leverage any single-agent policy gradient method to optimize the regularized objective in Equation [12](https://arxiv.org/html/2510.18183v1#S4.E12). Specifically, the policy and KL regularization gradients can both be estimated via trajectory sampling.

##### Practical Algorithm.

These insights lead to our main algorithmic contribution, *Nash Policy Gradient* (NashPG) presented in Algorithm [2](https://arxiv.org/html/2510.18183v1#alg2). At each iteration, trajectories are collected under the current joint policy. Both players then use these trajectories to estimate their policy and KL regularization gradients, and perform regularized policy gradient updates. After $K$ such updates, the reference policies are reset to the updated policies, and this process is repeated for $T$ outer iterations. The parameters $K$ and $T$ can be chosen according to the available computational budget.

A key advantage of NashPG is its modularity: it is agnostic to the choice of policy gradient estimator and can be seamlessly combined with modern single-agent RL methods. For instance, when adopting PPO, we simply replace the vanilla policy gradient update with PPO’s clipped surrogate objective, while leaving the regularization term unchanged. This design allows NashPG to directly inherit algorithmic advances from the single-agent RL literature.

Figure: Algorithm 2 Nash Policy Gradient (NashPG)

## 5 Experiments

This section outlines our experimental setup and highlights the main empirical results. Comprehensive settings and extra studies are deferred to Appendix [B](https://arxiv.org/html/2510.18183v1#A2). All code needed to reproduce our experiments are publicly available at [nash_policy_gradient](https://github.com/easonyu0203/nash_policy_gradient_public).

### 5.1 Experimental Setup

Environments: We evaluate all algorithms across seven two-player games spanning from classic benchmark environments to widely played
real-world games. Benchmarks include Kuhn Poker, Leduc Poker, Dark Hex (3$\times$3) and Phantom Tic-Tac-Toe [18]. To probe scalability beyond
synthetic benchmarks, we also evaluate on real-world games: Liar’s Dice, Battleship, and Heads-Up No-Limit Texas Hold’em. These environments
reflect authentic gameplay dynamics and are dramatically more complex. Complete rules, parameter settings, and complexity statistics (e.g., number of non-terminal histories) are deferred to Appendix [B.3](https://arxiv.org/html/2510.18183v1#A2.SS3).

Baseline Algorithms: We compare NashPG against three established model-free baselines: NFSP [13], PSRO [17], and MMD [34]. NFSP and PSRO train their best-response policies against a mixture of past agents using PPO [30]. For MMD, we set its magnetic coefficient $\alpha$ to $0.05$ and use a PPO-based policy gradient update.

Evaluation Metrics: We assess performance using *exploitability* and *Elo ratings*. Since exact best-response policies are intractable in large games, we approximate exploitability by training best-response agents using PPO. For Elo ratings, we save a checkpoint every $2{,}000$ training steps for each algorithm and run a Swiss-style tournament across all checkpoints, yielding roughly 800 tournament entries (4 algorithms $\times$ repeat 4 runs $\times$ 50 checkpoints). Detailed definitions and implementation are provided in Appendix [B.2](https://arxiv.org/html/2510.18183v1#A2.SS2).

Implementation: All environments and algorithms are implemented in JAX [2] for efficient training and evaluation. Within each game, all methods share identical model architectures and computational budgets to ensure fair comparison, and training follows standard PPO settings. Each experiment is repeated 4 times with different random seeds, and we report results as mean $\pm$ standard deviation. Detailed architectures, hyperparameters, and reward formulations are provided in Appendix [B.1](https://arxiv.org/html/2510.18183v1#A2.SS1) and Appendix [B.3](https://arxiv.org/html/2510.18183v1#A2.SS3).

### 5.2 Hyperparameter Tuning

**Table 1: Final exploitability of NashPG across different regularization strengths $\alpha$ on Kuhn Poker and Leduc Poker after $50{,}000$ training steps (mean $\pm$ standard deviation over 4 runs).**
| Regularization Strength | Kuhn Poker | Leduc Poker |
| --- | --- | --- |
| $\alpha=0.1$ | $0.0138\pm 0.0088$ | $0.0075\pm 0.0068$ |
| $\bm{\alpha=0.2}$ | $\mathbf{0.0046\pm 0.0037}$ | $\mathbf{0.0028\pm 0.0037}$ |
| $\alpha=0.4$ | $0.0059\pm 0.0032$ | $0.0029\pm 0.0026$ |

We first study the impact of the regularization coefficient $\alpha$ for NashPG, varying $\alpha$ over the values $0.1$, $0.2$, and $0.4$ in Kuhn Poker and Leduc Poker, which serve as representative small-scale domains. Table [1](https://arxiv.org/html/2510.18183v1#S5.T1) reports the final exploitability for each setting. Both $\alpha=0.2$ and $\alpha=0.4$ yield stable training dynamics, with $\alpha=0.2$ achieving the lowest exploitability. For all subsequent experiments, we use $\alpha=0.2$ for NashPG.

### 5.3 Results in Benchmarks

[Figure 1](https://arxiv.org/html/2510.18183v1#S5.F1) plots the exploitability curves for Kuhn Poker, Leduc Poker, Dark Hex $3\times 3$, and Phantom Tic-Tac-Toe. All algorithms converge in Kuhn and Leduc Poker but with different convergence speeds: both MMD and NashPG converge faster than the population-based methods. In Dark Hex $3\times 3$ and Phantom Tic-Tac-Toe, as the environments become more complex, NashPG achieves the lowest exploitability, whereas MMD plateaus at a higher value, reflecting the influence of its regularization term, which biases the converged policy. Population-based algorithms exhibit slow convergence in these games, with NFSP attains the highest exploitability across all games and fails to converge entirely on Dark Hex $3\times 3$. Overall, NashPG demonstrates scalability and consistently fast convergence as game complexity grows, motivating evaluation on more challenging, real-world environments.

Figure: Figure 1: Exploitability curves for our benchmarks. NashPG consistently achieves lower final exploitability across all tested environments except Kuhn Poker. Error bars show standard deviation over 4 runs.
Refer to caption: x1.png

### 5.4 Evaluation on Real-World Games

Limitations of Exploitability in Large Real-World Games. [Figure 2](https://arxiv.org/html/2510.18183v1#S5.F2) presents exploitability curves for Liar’s Dice, Battleship, and Heads-Up No-Limit Texas Hold’em. As game complexity grows, exploitability becomes increasingly unreliable under limited computational budgets. In [Figure 2](https://arxiv.org/html/2510.18183v1#S5.F2)b-c, measured exploitability drops below zero; in particular, NashPG plateaus near $-1$ in [Figure 2](https://arxiv.org/html/2510.18183v1#S5.F2)b, indicating that our best-response approximation either receives diminishing learning signals against strong policies (where random play has a negligible winning probability) or that the training budget (2,000 steps) is insufficient to estimate a meaningful best-response in such domains. These observations motivate adopting Elo ratings as an alternative metric.

Figure: Figure 2: Exploitability in real-world games. Battleship and Texas Hold’em show negative values (theoretically impossible), highlighting the limitations of exploitability-based evaluation under limited computational budgets in complex domains.
Refer to caption: x2.png

Elo Ratings as a Measure of Relative Strength. Given the limitations of exploitability, we adopt Elo ratings as the alternative evaluation metric in large real-world games. Widely used in competitive games, this metric captures relative skill through head-to-head matchups without requiring best-response computation. Implementation details are provided in Appendix [B.2](https://arxiv.org/html/2510.18183v1#A2.SS2). [Figure 3](https://arxiv.org/html/2510.18183v1#S5.F3) presents Elo rating curves for the these games. The results show clear and consistent trends favoring NashPG, which achieves the highest final Elo ratings across all three games. Interestingly, PSRO performs well in Heads-Up Texas Hold’em, even surpassing NashPG during the early iterations ($<25{,}000$ steps), yet fails to maintain this trend in the other games, suggesting that population-based methods are more selective with respect to game type.

Figure: Figure 3: Elo ratings in large real-world games. NashPG achieves consistently higher final Elo ratings across complex domains where exploitability is unreliable. Error bars denote standard deviation over 4 runs.
Refer to caption: x3.png

## 6 Conclusion and Future Work

We proposed a regularization-based framework that achieves convergence to Nash equilibria by iteratively refining the reference policy. We proved strictly monotonic improvement of the solution over iterations, and established convergence guarantees for our algorithm. Inspired by these theoretical findings, we developed NashPG, a practical algorithm that closely mirrors standard policy gradient methods while adding a KL regularization term and periodically updated reference policy. Empirically, NashPG achieves low exploitability and scales effectively to large domains such as Battleship and No-Limit Texas Hold’em.

A central appeal of NashPG is its accessibility: the method requires only minor modifications to conventional policy gradient algorithms, lowering the barrier to entry for practitioners in MARL. For future work, several directions remain open. On the theoretical side, our heuristic approximations would benefit from theoretically grounded justification. Empirically, benchmarking NashPG against domain-specific state-of-the-art methods, such as Pluribus [5], in large poker settings would further clarify its strengths. Extending it to continuous-action domains and to high-dimensional environments, such as Atari, would provide a further test of scalability.

## References

- Bighashdel et al. [2024]
Ariyan Bighashdel, Yongzhao Wang, Stephen McAleer, Rahul Savani, and Frans A.
Oliehoek.
Policy space response oracles: A survey.
In *IJCAI*, pages 7951–7961. ijcai.org, 2024.
- Bradbury et al. [2018]
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary,
Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye
Wanderman-Milne, and Qiao Zhang.
JAX: composable transformations of Python+NumPy programs,
2018.
URL [http://github.com/jax-ml/jax](http://github.com/jax-ml/jax).
- Brown [1951]
George W Brown.
Iterative solution of games by fictitious play.
*Act. Anal. Prod Allocation*, 13(1):374,
1951.
- Brown and Sandholm [2018]
Noam Brown and Tuomas Sandholm.
Superhuman ai for heads-up no-limit poker: Libratus beats top
professionals.
*Science*, 359(6374):418–424, 2018.
doi: 10.1126/science.aao1733.
URL [https://www.science.org/doi/abs/10.1126/science.aao1733](https://www.science.org/doi/abs/10.1126/science.aao1733).
- Brown and Sandholm [2019]
Noam Brown and Tuomas Sandholm.
Superhuman ai for multiplayer poker.
*Science*, 365(6456):885–890, 2019.
doi: 10.1126/science.aay2400.
URL [https://www.science.org/doi/abs/10.1126/science.aay2400](https://www.science.org/doi/abs/10.1126/science.aay2400).
- Brown et al. [2019]
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm.
Deep counterfactual regret minimization.
In *ICML*, volume 97 of *Proceedings of Machine Learning
Research*, pages 793–802. PMLR, 2019.
- Busoniu et al. [2008]
Lucian Busoniu, Robert Babuska, and Bart De Schutter.
A comprehensive survey of multiagent reinforcement learning.
*IEEE Transactions on Systems, Man, and Cybernetics, Part C
(Applications and Reviews)*, 38(2):156–172, 2008.
- Cen et al. [2021]
Shicong Cen, Yuting Wei, and Yuejie Chi.
Fast policy extragradient methods for competitive games with entropy
regularization.
In *NeurIPS*, pages 27952–27964, 2021.
- Daskalakis and Panageas [2019]
Constantinos Daskalakis and Ioannis Panageas.
Last-iterate convergence: Zero-sum games and constrained min-max
optimization.
In *ITCS*, volume 124 of *LIPIcs*, pages 27:1–27:18.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
- Daskalakis et al. [2018]
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.
Training gans with optimism.
In *ICLR (Poster)*. OpenReview.net, 2018.
- Facchinei and Pang [2003]
Francisco Facchinei and Jong-Shi Pang.
*Finite-dimensional variational inequalities and complementarity
problems*.
Springer, 2003.
- Greenwald et al. [2013]
Amy Greenwald, Jiacui Li, Eric Sodomka, and Michael Littman.
Solving for best responses in extensive-form games using
reinforcement learning methods.
In *Proceedings of the conference on reinforcement learning and
decision making*, pages 116–120. Citeseer, 2013.
- Heinrich and Silver [2016]
Johannes Heinrich and David Silver.
Deep reinforcement learning from self-play in imperfect-information
games.
*CoRR*, abs/1603.01121, 2016.
- Hofbauer and Hopkins [2005]
Josef Hofbauer and Ed Hopkins.
Learning in perturbed asymmetric games.
*Games Econ. Behav.*, 52(1):133–152, 2005.
- Hsieh et al. [2021]
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos.
Adaptive learning in continuous games: Optimal regret bounds and
convergence to nash equilibrium.
In *COLT*, volume 134 of *Proceedings of Machine Learning
Research*, pages 2388–2422. PMLR, 2021.
- Kuhn [1953]
Harold W Kuhn.
Extensive games and the problem of information.
*Contributions to the Theory of Games*, 2(28):193–216, 1953.
- Lanctot et al. [2017]
Marc Lanctot, Vinícius Flores Zambaldi, Audrunas Gruslys, Angeliki
Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel.
A unified game-theoretic approach to multiagent reinforcement
learning.
In *NIPS*, pages 4190–4203, 2017.
- Lanctot et al. [2019]
Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinicius Zambaldi,
Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers,
Karl Tuyls, Shayegan Omidshafiei, Daniel Hennes, Dustin Morrill, Paul Muller,
Timo Ewalds, Ryan Faulkner, János Kramár, Bart De Vylder, Brennan
Saeta, James Bradbury, David Ding, Sebastian Borgeaud, Matthew Lai, Julian
Schrittwieser, Thomas Anthony, Edward Hughes, Ivo Danihelka, and Jonah
Ryan-Davis.
OpenSpiel: A framework for reinforcement learning in games.
*CoRR*, abs/1908.09453, 2019.
URL [http://arxiv.org/abs/1908.09453](http://arxiv.org/abs/1908.09453).
- Larsson and Patriksson [1994]
Torbjörn Larsson and Michael Patriksson.
A class of gap functions for variational inequalities.
*Mathematical Programming*, 64(1):53–79,
1994.
- Lee et al. [2021]
Chung-Wei Lee, Christian Kroer, and Haipeng Luo.
Last-iterate convergence in extensive-form games.
In *NeurIPS*, pages 14293–14305, 2021.
- Li et al. [2020]
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen.
Sample complexity of asynchronous q-learning: Sharper analysis and
variance reduction.
In *NeurIPS*, 2020.
- Li et al. [2021]
Huale Li, Xuan Wang, Fengwei Jia, Yifan Li, and Qian Chen.
A survey of nash equilibrium strategy solving based on cfr.
*Archives of Computational Methods in Engineering*, 28(4), 2021.
- Liu et al. [2023]
Mingyang Liu, Asuman E. Ozdaglar, Tiancheng Yu, and Kaiqing Zhang.
The power of regularization in solving extensive-form games.
In *ICLR*. OpenReview.net, 2023.
- McAleer et al. [2020]
Stephen McAleer, John B. Lanier, Roy Fox, and Pierre Baldi.
Pipeline PSRO: A scalable approach for finding approximate nash
equilibria in large games.
In *NeurIPS*, 2020.
- McAleer et al. [2023]
Stephen Marcus McAleer, Gabriele Farina, Marc Lanctot, and Tuomas Sandholm.
ESCHER: eschewing importance sampling in games by computing a
history value function to estimate regret.
In *ICLR*. OpenReview.net, 2023.
- McAleer et al. [2024]
Stephen Marcus McAleer, JB Lanier, Kevin A. Wang, Pierre Baldi, Tuomas
Sandholm, and Roy Fox.
Toward optimal policy population growth in two-player zero-sum games.
In *ICLR*. OpenReview.net, 2024.
- McKelvey and Palfrey [1995]
Richard D. McKelvey and Thomas R. Palfrey.
Quantal response equilibria for normal form games.
*Games and Economic Behavior*, 10(1):6–38,
1995.
ISSN 0899-8256.
doi: https://doi.org/10.1006/game.1995.1023.
URL
[https://www.sciencedirect.com/science/article/pii/S0899825685710238](https://www.sciencedirect.com/science/article/pii/S0899825685710238).
- Pérolat et al. [2021]
Julien Pérolat, Rémi Munos, Jean-Baptiste Lespiau, Shayegan
Omidshafiei, Mark Rowland, Pedro A. Ortega, Neil Burch, Thomas W. Anthony,
David Balduzzi, Bart De Vylder, Georgios Piliouras, Marc Lanctot, and Karl
Tuyls.
From poincaré recurrence to convergence in imperfect
information games: Finding equilibrium via regularization.
In *ICML*, volume 139 of *Proceedings of Machine Learning
Research*, pages 8525–8535. PMLR, 2021.
- Rudolph et al. [2025]
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 imperfect-information games,
2025.
URL [https://arxiv.org/abs/2502.08938](https://arxiv.org/abs/2502.08938).
- Schulman et al. [2017]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
*CoRR*, abs/1707.06347, 2017.
- Shoham et al. [2007]
Yoav Shoham, Rob Powers, and Trond Grenager.
If multi-agent learning is the answer, what is the question?
*Artificial intelligence*, 171(7):365–377,
2007.
- Silver et al. [2016]
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George
van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas
Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal
Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray
Kavukcuoglu, Thore Graepel, and Demis Hassabis.
Mastering the game of go with deep neural networks and tree search.
*Nat.*, 529(7587):484–489, 2016.
- Silver et al. [2018]
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew
Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore
Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis.
A general reinforcement learning algorithm that masters chess, shogi,
and go through self-play.
*Science*, 362(6419):1140–1144, 2018.
doi: 10.1126/science.aar6404.
URL [https://www.science.org/doi/abs/10.1126/science.aar6404](https://www.science.org/doi/abs/10.1126/science.aar6404).
- Sokota et al. [2023]
Samuel Sokota, Ryan D’Orazio, J. Zico Kolter, Nicolas Loizou, Marc Lanctot,
Ioannis Mitliagkas, Noam Brown, and Christian Kroer.
A unified approach to reinforcement learning, quantal response
equilibria, and two-player zero-sum games.
In *ICLR*. OpenReview.net, 2023.
- Steinberger et al. [2020]
Eric Steinberger, Adam Lerer, and Noam Brown.
DREAM: deep regret minimization with advantage baselines and
model-free learning.
*CoRR*, abs/2006.10410, 2020.
- Vinyals et al. [2019]
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu,
Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds,
Petko Georgiev, et al.
Grandmaster level in starcraft ii using multi-agent reinforcement
learning.
*nature*, 575(7782):350–354, 2019.
- Zinkevich et al. [2007]
Martin Zinkevich, Michael Johanson, Michael H. Bowling, and Carmelo Piccione.
Regret minimization in games with incomplete information.
In *NIPS*, pages 1729–1736. Curran Associates, Inc., 2007.

## Appendix A Theoretical Analysis

In this appendix, we provide detailed proofs for the main theoretical results presented in Section [4.1](https://arxiv.org/html/2510.18183v1#S4.SS1) and Section [4.2](https://arxiv.org/html/2510.18183v1#S4.SS2). We begin by establishing the mathematical foundation and recall the problem setup.

### A.1 Mathematical Notation

For a function $f$, we denote its domain by $\operatorname{dom}f$ and for a set $\mathcal{D}$, we write $\operatorname{int}\mathcal{D}$ for its interior.

###### Definition 3 ( $L$ -smooth function) .

A differentiable function $f:\mathcal{Z}\to\mathbb{R}$ is $L$-smooth on $\mathcal{Z}\subseteq\mathbb{R}^{n}$ if its gradient is $L$-Lipschitz continuous:

$$ $\|\nabla f(z)-\nabla f(z^{\prime})\|\leq L\|z-z^{\prime}\|\quad\forall z,z^{\prime}\in\mathcal{Z}.$ $$

###### Definition 4 ( $\mu$ -strong convex function) .

A differentiable function $f:\mathcal{Z}\to\mathbb{R}$ is $\mu$-strongly convex on $\mathcal{Z}$ if there exists $\mu>0$ such that

$$ $f(z^{\prime})\geq f(z)+\langle\nabla f(z),z^{\prime}-z\rangle+\tfrac{\mu}{2}\|z^{\prime}-z\|^{2}\quad\forall z,z^{\prime}\in\mathcal{Z}.$ $$

###### Definition 5 (Monotone operator) .

An operator $G:\mathcal{Z}\to\mathbb{R}^{n}$ is monotone on $\mathcal{Z}$ if

$$ $\langle G(z)-G(z^{\prime}),z-z^{\prime}\rangle\geq 0\quad\forall z,z^{\prime}\in\mathcal{Z}.$ $$

It is $\mu$-strongly monotone on $\mathcal{Z}$ if there exists $\mu>0$ such that

$$ $\langle G(z)-G(z^{\prime}),z-z^{\prime}\rangle\geq\mu\|z-z^{\prime}\|^{2}\quad\forall z,z^{\prime}\in\mathcal{Z}.$ $$

###### Definition 6 (Bregman divergence) .

Let $\psi:\mathcal{Z}\to\mathbb{R}$ be a differentiable, strongly convex function.
For $z\in\operatorname{dom}\psi$ and $z^{\prime}\in\operatorname{int}\operatorname{dom}\psi$, the Bregman divergence is defined as

$$ $B_{\psi}(z;z^{\prime})=\psi(z)-\psi(z^{\prime})-\langle\nabla\psi(z^{\prime}),z-z^{\prime}\rangle,$ $$

which satisfies $B_{\psi}(z;z^{\prime})\geq 0$.

###### Definition 3 ( L L -smooth function) .

###### Definition 4 ( μ \mu -strong convex function) .

###### Definition 5 (Monotone operator) .

###### Definition 6 (Bregman divergence) .

### A.2 Problem Setup

##### Two-Player Zero-Sum Games.

We consider two-player zero-sum extensive-form games with perfect recall. Their equivalent normal-form representation is given by a payoff matrix ${\bm{A}}$, where rows and columns correspond to the pure strategies of players 1 and 2. Let ${\mathcal{X}}$ and ${\mathcal{Y}}$ denote the mixed strategy spaces (probability simplices) of the two players, and define the strategy profile space ${\mathcal{Z}}={\mathcal{X}}\times{\mathcal{Y}}$. A strategy profile is $z=(x,y)\in{\mathcal{Z}}$, and the payoff to player 1 is

$$ $f(x,y)=x^{\top}{\bm{A}}y.$ $$

##### Nash Equilibrium.

A strategy profile $z^{*}=(x^{*},y^{*})\in{\mathcal{Z}}$ is a Nash equilibrium if neither player can improve unilaterally:

$$ $x^{*}\in\arg\max_{x\in{\mathcal{X}}}f(x,y^{*})\quad\text{and}\quad y^{*}\in\arg\max_{y\in{\mathcal{Y}}}-f(x^{*},y).$ $$

##### Variational Inequality Formulation.

The Nash equilibrium problem can be equivalently expressed as a variational inequality (VI). Define the operator $F:{\mathcal{Z}}\to\mathbb{R}^{n}$ by

$$ $F(z)=\begin{bmatrix}-\nabla_{x}f(x,y)\[4.0pt] \nabla_{y}f(x,y)\end{bmatrix}=\begin{bmatrix}-{\bm{A}}y\\ {\bm{A}}^{\top}x\end{bmatrix}.$ (13) $$

Then $z^{*}$ is a Nash equilibrium if and only if it solves $\mathrm{VI}({\mathcal{Z}},F)$:

$$ $\langle F(z^{*}),z-z^{*}\rangle\geq 0\quad\forall z\in{\mathcal{Z}}.$ $$

##### Regularized Variational Inequality.

With a strongly convex regularizer $\psi(z)=\psi_{1}(x)+\psi_{2}(y)$ with associated Bregman divergence

$$ $B_{\psi}(z;\rho)=B_{\psi_{1}}(x;\rho_{1})+B_{\psi_{2}}(y;\rho_{2}),$ $$

where $\rho=(\rho_{1},\rho_{2})\in{\mathcal{Z}}$ is a reference strategy profile. The regularized operator is defined as

$$ $G_{\rho}(z)=F(z)+\alpha\nabla_{z}B_{\psi}(z;\rho)\quad\alpha>0,$ (14) $$

or equivalently

$$ $G_{\rho}(z)\;=\;F(z)+\alpha\big(\nabla\psi(z)-\nabla\psi(\rho)\big)\quad\alpha>0.$ (15) $$

The corresponding regularized VI seeks $\hat{z}\in{\mathcal{Z}}$ such that

$$ $\langle G_{\rho}(\hat{z}),z-\hat{z}\rangle\geq 0\quad\forall z\in{\mathcal{Z}}.$ $$

##### Regularized VI Operator.

The central object of our analysis is the mapping

$$ ${\mathcal{M}}:\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}\;\to\;\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}},$ $$

which takes a reference profile $\rho$ to the unique solution ${\mathcal{M}}(\rho)$ of $\mathrm{VI}({\mathcal{Z}},G_{\rho})$. Formally, ${\mathcal{M}}(\rho)$ is the unique point satisfying

$$ $\langle G_{\rho}({\mathcal{M}}(\rho)),z-{\mathcal{M}}(\rho)\rangle\geq 0\quad\forall z\in{\mathcal{Z}}.$ $$

### A.3 Preliminary Results

###### Lemma 1 (Three-Point Property) .

For any strongly convex function $\psi$ and points $a\in\operatorname{dom}\psi$ and $\{b,c\}\subset\operatorname{int}\operatorname{dom}\psi$, the Bregman divergence satisfies:

$$ $B_{\psi}(a;b)=B_{\psi}(a;c)+B_{\psi}(c;b)+\langle\nabla\psi(c)-\nabla\psi(b),a-c\rangle$ (16) $$

###### Proof.

By definition of Bregman divergence:

$$ $\displaystyle B_{\psi}(a;b)$ $\displaystyle=\psi(a)-\psi(b)-\langle\nabla\psi(b),a-b\rangle$ (17) $\displaystyle B_{\psi}(a;c)$ $\displaystyle=\psi(a)-\psi(c)-\langle\nabla\psi(c),a-c\rangle$ (18) $\displaystyle B_{\psi}(c;b)$ $\displaystyle=\psi(c)-\psi(b)-\langle\nabla\psi(b),c-b\rangle$ (19) $$

Direct algebraic manipulation yields the result.
∎

###### Lemma 2 (Monotonicity of Operator $F$ ) .

The operator $F:{\mathcal{Z}}\to\mathbb{R}^{n}$ defined in the problem setup is monotone on ${\mathcal{Z}}$.

###### Proof.

Let $z_{1}=(x_{1},y_{1})$ and $z_{2}=(x_{2},y_{2})$ be two strategy profiles in ${\mathcal{Z}}$. We have:

$$ $\displaystyle\langle F(z_{1})-F(z_{2}),z_{1}-z_{2}\rangle$ (20) $\displaystyle=\langle-{\bm{A}}y_{1}+{\bm{A}}y_{2},x_{1}-x_{2}\rangle+\langle{\bm{A}}^{\top}x_{1}-{\bm{A}}^{\top}x_{2},y_{1}-y_{2}\rangle$ (21) $\displaystyle=-(x_{1}-x_{2})^{\top}{\bm{A}}(y_{1}-y_{2})+(x_{1}-x_{2})^{\top}{\bm{A}}(y_{1}-y_{2})$ (22) $\displaystyle=0\geq 0$ (23) $$

where we used the definition $F(z)=[-{\bm{A}}y;{\bm{A}}^{\top}x]$ from the problem setup.
∎

###### Lemma 3 (Strong Monotonicity of $G_{\rho}$ ) .

Let $\psi$ be $\mu$-strongly convex on $\operatorname{int}\operatorname{dom}\psi$ with $\mu>0$, then $G_{\rho}$ is $\alpha\mu$-strongly monotone on ${\mathcal{Z}}$, i.e.,

$$ $\langle G_{\rho}(u)-G_{\rho}(v),\,u-v\rangle\;\geq\;\alpha\mu\|u-v\|^{2}\quad\text{for all }u,v\in{\mathcal{Z}}.$ $$

###### Proof.

For any $u,v\in{\mathcal{Z}}$,

$$ $\langle G_{\rho}(u)-G_{\rho}(v),u-v\rangle=\langle F(u)-F(v),u-v\rangle+\alpha\langle\nabla\psi(u)-\nabla\psi(v),u-v\rangle.$ $$

By Lemma [2](https://arxiv.org/html/2510.18183v1#Thmlemma2), $F$ is monotone, so the first term is nonnegative.
By $\mu$-strong convexity of $\psi$, the second term is at least $\alpha\mu\|u-v\|^{2}$.
This proves $\alpha\mu$-strong monotonicity of $G_{\rho}$.
∎

###### Lemma 1 (Three-Point Property) .

###### Proof.

###### Lemma 2 (Monotonicity of Operator F F ) .

###### Proof.

###### Lemma 3 (Strong Monotonicity of G ρ G_{\rho} ) .

###### Proof.

### A.4 Main Theoretical Results

#### A.4.1 Proof of Lemma 2

*

###### Proof.

For notational convenience, define $z_{\rho}\coloneqq{\mathcal{M}}(\rho)$.
The Nash equilibrium $z^{*}$ satisfies the VI optimality condition for $F$:

$$ $\langle F(z^{*}),z-z^{*}\rangle\geq 0,\quad\forall z\in{\mathcal{Z}}.$ (24) $$

Similarly, $z_{\rho}$ satisfies the VI optimality condition for the regularized operator $G_{\rho}$:

$$ $\langle G_{\rho}(z_{\rho}),z-z_{\rho}\rangle\geq 0,\quad\forall z\in{\mathcal{Z}}.$ (25) $$

Substitute $z=z_{\rho}$ in equation [24](https://arxiv.org/html/2510.18183v1#A1.E24) and $z=z^{*}$ in equation [25](https://arxiv.org/html/2510.18183v1#A1.E25), then add the two inequalities:

$$ $\langle F(z^{*}),z_{\rho}-z^{*}\rangle+\langle F(z_{\rho})+\alpha\nabla_{z_{\rho}}B_{\psi}(z_{\rho};\rho),z^{*}-z_{\rho}\rangle\geq 0.$ (26) $$

Rearranging equation [26](https://arxiv.org/html/2510.18183v1#A1.E26) gives

$$ $\alpha\langle\nabla_{z_{\rho}}B_{\psi}(z_{\rho};\rho),z^{*}-z_{\rho}\rangle\geq\langle F(z^{*})-F(z_{\rho}),z^{*}-z_{\rho}\rangle.$ (27) $$

By Lemma [2](https://arxiv.org/html/2510.18183v1#Thmlemma2), $F$ is monotone on ${\mathcal{Z}}$, so the right-hand side of equation [27](https://arxiv.org/html/2510.18183v1#A1.E27) is nonnegative. Hence, since $\alpha>0$, we obtain

$$ $\langle\nabla_{z_{\rho}}B_{\psi}(z_{\rho};\rho),z^{*}-z_{\rho}\rangle\geq 0.$ (28) $$

And since $\nabla_{z_{\rho}}B_{\psi}(z_{\rho};\rho)=\nabla\psi(z_{\rho})-\nabla\psi(\rho)$, equation [28](https://arxiv.org/html/2510.18183v1#A1.E28) becomes

$$ $\langle\nabla\psi(z_{\rho})-\nabla\psi(\rho),z^{*}-z_{\rho}\rangle\geq 0.$ (29) $$

Finally, applying the three-point property of Bregman divergences (Lemma [1](https://arxiv.org/html/2510.18183v1#Thmlemma1)) with $a=z^{*}$, $c=z_{\rho}$, and $b=\rho$, we have

$$ $B_{\psi}(z^{*};\rho)=B_{\psi}(z^{*};z_{\rho})+B_{\psi}(z_{\rho};\rho)+\langle\nabla\psi(z_{\rho})-\nabla\psi(\rho),z^{*}-z_{\rho}\rangle.$ (30) $$

Combining equation [30](https://arxiv.org/html/2510.18183v1#A1.E30) with equation [29](https://arxiv.org/html/2510.18183v1#A1.E29) immediately gives

$$ $B_{\psi}(z^{*};\rho)\geq B_{\psi}(z^{*};z_{\rho})+B_{\psi}(z_{\rho};\rho).$ $$

∎

###### Proof.

#### A.4.2 Proof of Lemma 2

*

###### Proof.

($\Rightarrow$) Suppose $z^{*}$ is a Nash equilibrium. By definition, $z^{*}$ solves $\mathrm{VI}({\mathcal{Z}},F)$:

$$ $\langle F(z^{*}),z-z^{*}\rangle\geq 0,\quad\forall z\in{\mathcal{Z}}.$ (31) $$

Consider the regularized operator $G_{z^{*}}(z)$. By the VI optimality condition, $z^{*}$ also solves $\mathrm{VI}({\mathcal{Z}},G_{z^{*}})$, since

$$ $\langle G_{z^{*}}(z^{*}),z-z^{*}\rangle=\langle F(z^{*}),z-z^{*}\rangle+\alpha\langle\nabla_{z}B_{\psi}(z^{*};z^{*}),z-z^{*}\rangle=\langle F(z^{*}),z-z^{*}\rangle\geq 0,$ $$

using $\nabla_{z}B_{\psi}(z^{*};z^{*})=0$. By definition of the operator ${\mathcal{M}}$, the unique solution of $\mathrm{VI}({\mathcal{Z}},G_{z^{*}})$ is ${\mathcal{M}}(z^{*})$. Therefore implies $z^{*}={\mathcal{M}}(z^{*})$.

($\Leftarrow$) Conversely, suppose $z^{*}={\mathcal{M}}(z^{*})$. By definition of operator ${\mathcal{M}}$, $z^{*}$ solves $\mathrm{VI}({\mathcal{Z}},G_{z^{*}})$:

$$ $\langle G_{z^{*}}(z^{*}),z-z^{*}\rangle\geq 0,\quad\forall z\in{\mathcal{Z}}.$ (32) $$

Expanding $G_{z^{*}}(z^{*})=F(z^{*})+\alpha\nabla_{z}B_{\psi}(z^{*};z^{*})=F(z^{*})$, we see that $z^{*}$ satisfies

$$ $\langle F(z^{*}),z-z^{*}\rangle\geq 0,\quad\forall z\in{\mathcal{Z}},$ $$

i.e., $z^{*}$ is a Nash equilibrium.
∎

###### Proof.

#### A.4.3 Proof of Lemma 2

*

###### Proof.

Fix $\rho\in\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$, let $\{\rho_{n}\}\subset\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$ be any sequence with $\rho_{n}\to\rho$, and for notational convenience we write

$$ $z_{n}\coloneqq{\mathcal{M}}(\rho_{n}),\qquad z_{\rho}\coloneqq{\mathcal{M}}(\rho).$ $$

By the VI optimality conditions for $z_{n}$ and $z_{\rho}$ we have

$$ $\langle G_{\rho_{n}}(z_{n}),z_{\rho}-z_{n}\rangle\geq 0\quad\text{and}\quad\langle G_{\rho}(z_{\rho}),z_{n}-z_{\rho}\rangle\geq 0.$ $$

Adding these two inequalities yields

$$ $\langle G_{\rho_{n}}(z_{n})-G_{\rho}(z_{\rho}),\,z_{\rho}-z_{n}\rangle\geq 0,$ $$

rearranges to get

$$ $\langle G_{\rho_{n}}(z_{n})-G_{\rho_{n}}(z_{\rho}),\,z_{n}-z_{\rho}\rangle\leq\langle G_{\rho_{n}}(z_{\rho})-G_{\rho}(z_{\rho}),\,z_{\rho}-z_{n}\rangle.$ (33) $$

By $\alpha\mu$-strong monotonicity of $G_{\rho_{n}}$ (Lemma [3](https://arxiv.org/html/2510.18183v1#Thmlemma3)), the left-hand side of equation [33](https://arxiv.org/html/2510.18183v1#A1.E33) is bounded below by $\alpha\mu\|z_{n}-z_{\rho}\|^{2}$.
Applying the Cauchy–Schwarz inequality to the right-hand side of equation [33](https://arxiv.org/html/2510.18183v1#A1.E33) yields

$$ $\alpha\mu\|z_{n}-z_{\rho}\|^{2}\;\leq\;\|G_{\rho_{n}}(z_{\rho})-G_{\rho}(z_{\rho})\|\cdot\|z_{n}-z_{\rho}\|.$ $$

If $z_{n}=z_{\rho}$ the desired convergence holds trivially. Otherwise we divide both sides by $\|z_{n}-z_{\rho}\|>0$ to obtain

$$ $\|z_{n}-z_{\rho}\|\leq\frac{1}{\alpha\mu}\,\|G_{\rho_{n}}(z_{\rho})-G_{\rho}(z_{\rho})\|.$ (34) $$

Since

$$ $G_{\rho_{n}}(z_{\rho})-G_{\rho}(z_{\rho})=\alpha\big(\nabla\psi(\rho)-\nabla\psi(\rho_{n})\big),$ $$

we have that equation [34](https://arxiv.org/html/2510.18183v1#A1.E34) simplifies to

$$ $\|z_{n}-z_{\rho}\|\leq\frac{1}{\mu}\,\|\nabla\psi(\rho_{n})-\nabla\psi(\rho)\|.$ (35) $$

Since $\nabla\psi$ is continuous on $\operatorname{int}\operatorname{dom}\psi$ and $\rho_{n}\to\rho$, the right-hand side of equation [35](https://arxiv.org/html/2510.18183v1#A1.E35) vanishes as $n\to\infty$. Therefore ${\mathcal{M}}(\rho_{n})\to{\mathcal{M}}(\rho)$. As this holds for every sequence $\rho_{n}\to\rho$, the mapping ${\mathcal{M}}$ is continuous on $\operatorname{int}\operatorname{dom}\psi\cap{\mathcal{Z}}$.
∎

###### Proof.

#### A.4.4 Proof Convergence of Iterative Refinement Procedure

*

###### Proof.

Fix any Nash equilibrium $z^{\ast}$. For the first part of the theorem, we show the strictly inequality holds for all iterations before convergence occur.
Apply Lemma [2](https://arxiv.org/html/2510.18183v1#Thmdefinition2) with $\rho=z_{t}$ and recall $z_{t+1}={\mathcal{M}}(z_{t})$ to obtain

$$ $B_{\psi}(z^{*};z_{t})\geq B_{\psi}(z^{*};z_{t+1})+B_{\psi}(z_{t+1};z_{t}).$ $$

If the iteration has not converged then $z_{t+1}\neq z_{t}$, therefore $B_{\psi}(z_{t+1};z_{t})>0$. Hence the preceding inequality is strict, yielding

$$ $B_{\psi}(z^{*};z_{t})>B_{\psi}(z^{*};z_{t+1}).$ $$

Next, we show the sequence converge to a Nash equilibrium. Iterating the inequality from Lemma [2](https://arxiv.org/html/2510.18183v1#Thmdefinition2), we get, for any $k\geq 1$,

$$ $\displaystyle B_{\psi}(z^{*};z_{0})$ $\displaystyle\geq B_{\psi}(z^{*};z_{1})+B_{\psi}(z_{1};z_{0})$ $\displaystyle\geq B_{\psi}(z^{*};z_{2})+B_{\psi}(z_{2};z_{1})+B_{\psi}(z_{1};z_{0})$ $\displaystyle\geq B_{\psi}(z^{*};z_{k})+\sum_{\ell=0}^{k-1}B_{\psi}(z_{\ell+1};z_{\ell})\;.$ (36) $$

As all terms in the RHS are non-negative, this implies that the partial sums of the series of non-negative terms $\sum_{\ell=0}^{k-1}B_{\psi}(z_{\ell+1};z_{\ell})$ are uniformly bounded, and so the series converges. In particular $B_{\psi}(z_{k+1};z_{k})\to 0$, which we will use below. Moreover, Equation equation [36](https://arxiv.org/html/2510.18183v1#A1.E36) also implies
$B_{\psi}(z^{*};z_{k})\leq B_{\psi}(z^{*};z_{0})$, and the sequence $\{z_{k}\}_{k}$ belongs to the closed, bounded Bregman ball of radius $r\coloneqq B_{\psi}(z^{*};z_{0})$. As a result, there exists a convergent subsequence $\{z_{\phi(k)}\}_{k}$ converges (where $\phi\colon\mathbb{N}\to\mathbb{N}$ is increasing): denote its limit by

$$ $z_{\infty}\coloneqq\lim_{k\to\infty}z_{\phi(k)}\,.$ $$

Then, we claim that $z_{\infty}$ is a Nash equilibrium. Indeed, we have, from the above,

$$ $B_{\psi}(\mathcal{M}(z_{\phi(k)});z_{\phi(k)})=B_{\psi}(z_{\phi(k)+1};z_{\phi(k)})\xrightarrow[k\to\infty]{}0$ $$

while, by continuity of the Bregman divergence and of the $\mathcal{M}$ operator ([Definition 2](https://arxiv.org/html/2510.18183v1#Thmdefinition2)),

$$ $B_{\psi}(\mathcal{M}(z_{\phi(k)});z_{\phi(k)})\xrightarrow[k\to\infty]{}B_{\psi}(\mathcal{M}(z_{\infty});z_{\infty})$ $$

and so, by uniqueness of the limit, $B_{\psi}(\mathcal{M}(z_{\infty});z_{\infty})=0$. [Definition 2](https://arxiv.org/html/2510.18183v1#Thmdefinition2) then allows us to conclude that $z_{\infty}$ is a Nash equilibrium.

We can then conclude that $z_{t}$ converges to $z_{\infty}$: indeed, applying Lemma [2](https://arxiv.org/html/2510.18183v1#Thmdefinition2) to the Nash equilibrium $z_{\infty}$, we get as the beginning of the proof that, for all $t,s\geq 0$,

$$ $B_{\psi}(z_{\infty};z_{t})\geq B_{\psi}(z_{\infty};z_{t+s})$ $$

(i.e., $B_{\psi}(z_{\infty};z_{t})$ is a non-increasing, non-negative sequence). Since $\lim_{k\to\infty}z_{\phi(k)}=z_{\infty}$, this easily allows us to conclude that the sequence $\{z_{t}\}_{t}$ converges to $z_{\infty}$ as well. (In more detail: fixing $\varepsilon>0$, there exists $k_{\varepsilon}\geq 0$ such that, for all $k\geq k_{\varepsilon}$, $B_{\psi}(z_{\infty};z_{\phi(k)})\leq\varepsilon$. Then, for all $t\geq\phi(k_{\varepsilon})$, we have $B_{\psi}(z_{\infty};z_{t})\leq B_{\psi}(z_{\infty};z_{\phi(k_{\varepsilon})})\leq\varepsilon$.) This concludes the proof.
∎

###### Proof.

## Appendix B Experiment Details

### B.1 Algorithm Settings

We evaluate NashPG with three established model-free baselines: Neural Fictitious Self-Play (NFSP) [13], Policy Space Response Oracles (PSRO) [17], and Magnetic Mirror Descent (MMD) [34]. All methods employ PPO as the primary training framework for best-response learning and policy-gradient updates, with hyperparameters listed in [Table 2](https://arxiv.org/html/2510.18183v1#A2.T2). Detailed implementation notes for each algorithm are provided below.

NFSP. Maintains a uniform mixture of policies comprising all previously trained agents. Each iteration, a new agent is initialized and use PPO to train a approximate best-response agent against the mixture of prior policies. The newly trained agent is added to the population after each iteration.

PSRO. The setup follows NFSP but replaces uniform mixing with a meta-game constructed from pairwise interactions among historical agents. Each entry of the payoff matrix is estimated from rollouts with $128$ parallel environments and $1{,}000$ steps per environment. A Nash equilibrium of this meta-game is then approximated via fictitious play [3] for $10{,}000$ iterations, and the resulting mixed strategy defines the new population distribution. Training then continues with a newly initialized agent.

MMD. A single policy is trained in self-play using PPO. The original paper states they use PPO but change forward KL to reversed KL; however, we hypothesize their intention is to add an additional KL regularization term. Based on their setup, the reference policy is set to a uniform policy. Following Sokota et al. [34], we evaluate magnet coefficients in $\{0.05,0.1,0.2\}$ and find most of the time $0.05$ yields better performance, hence use it for all experiments.

**Table 2: PPO hyperparameters**
| Hyperparameter | Value |
| --- | --- |
| Optimizer | AdamW |
| Step size($\eta$) | $3.0\text{\times}{10}^{-4}$ |
| Num. epochs | 4 |
| Minibatch size | 4 |
| Discount ($\gamma$) | 1 |
| GAE parameter ($\lambda$) | 0.95 |
| Clipping parameter ($\epsilon$) | 0.2 |
| Entropy coeff. | 0.05 |
| Number of envs. | 32 |
| Rollout length | 128 |

### B.2 Evaluation Metrics

In our work, we employ both exploitability and Elo ratings to evaluate the policies of all baselines and NashPG.

Exploitability: Consider a two-player zero-sum game with player’s behavioural strategies $\pi_{1}$ and $\pi_{2}$. Let $\mu_{i}(\pi_{i},\pi_{-i})$ denote the expected payoff for player $i$, where $-i$ denotes the opponent of player $i$. The best-response strategy for player $i$ is defined as

$$ $BR_{i}(\pi_{-i})=\arg\max_{\pi_{i}^{\prime}}\mu_{i}(\pi_{i}^{\prime},\pi_{-i})$ $$

Given a suboptimal strategy $\pi_{i}$, the incentive for player $i$ to deviate is

$$ $\delta_{i}=\mu_{i}\bigl(BR_{i}(\pi_{-i}),\pi_{-i}\bigr)-\mu_{i}(\pi_{i},\pi_{-i})$ $$

The exploitability is then defined as

$$ $\text{Exploitability}=\mathbb{E}_{i\sim\text{Uniform}}\bigl[\delta_{i}\bigr]$ $$

In our experiments, we approximate $BR_{i}(\pi_{-i})$ by training a newly initialized agent with PPO against the fixed strategy $\pi_{-i}$ at each evaluation checkpoint. For convenience of implementation, we augment each environment so at the beginning of each game, we randomly assign player positions. The exploiter is trained for $2{,}000$ steps. All other optimization and algorithmic hyperparameters follow the settings reported in [Table 2](https://arxiv.org/html/2510.18183v1#A2.T2).

Elo ratings: This system produces a scalar ranking based on empirical match outcomes. Given two players A and B with current Elo ratings $\mathrm{Elo}_{A}$ and $\mathrm{Elo}_{B}$, the expected score of player A is

$$ $E_{A}=\frac{1}{1+10^{(\mathrm{Elo}_{B}-\mathrm{Elo}_{A})/400}}$ $$

After a match, the realized outcome $R_{A}\in\{0,\,0.5,\,1\}$ is recorded, where $1$ denotes a win for A, $0.5$ a draw, and 0 a loss. Ratings are then updated as

$$ $\mathrm{Elo}_{A}\leftarrow\mathrm{Elo}_{A}+K\cdot(R_{A}-E_{A})\qquad\mathrm{Elo}_{B}\leftarrow\mathrm{Elo}_{B}+K\cdot\big((1-R_{A})-(1-E_{A})\big)$ $$

where $K$ is the update factor. In our experiments, we set $K=32$ and initialize all agents at an Elo rating of $1500$. We evaluate policies from different algorithms by running a Swiss-style tournament consisting of $100$ rounds. For each of the four algorithms, we save a checkpoint every $2{,}000$ steps (50 checkpoints per run) and perform four independent runs, yielding approximately 800 tournament entries (4 algorithms $\times$ 4 runs $\times$ 50 checkpoints). At the beginning of each round, all players are sorted by their current Elo rating and paired with their nearest neighbor. Each pairing is evaluated over $100$ repeated games. The cumulative reward difference across these $100$ games determines the match result: if one player achieves higher total reward, they are assigned $R=1$ and the opponent $R=0$; if totals are equal, both receive $R=0.5$. Elo ratings are then updated according to the above rule.

**Table 3: Summary of environments and model architectures**
| Environment | Kuhn | Leduc | Dark Hex | Phantom | Liar’s | Battleship | Heads-Up |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Poker | Poker | (3$\times$3) | Tic-Tac-Toe | Dice |  | Hold’em |  |
| Players | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| Obs. Dim. | 7 | 49 | 9 | 9 | 54 | 111 | 285 |
| Action spaces | 2 | 3 | 9 | 9 | 61 | 100 | 16 |
| Feature Extractor | Linear | Linear | Linear | Linear | Transformer | CNN | Transformer |
| Layers | 2 | 2 | 2 | 2 | 1 | 2 | 2 |
| Hidden Dim. | 16 | 64 | 64 | 64 | 64 | 128 | 256 |
| Attention Heads | – | – | – | – | 1 | – | 8 |
| History Length | – | – | – | – | 16 | – | 64 |
| Policy Head | Linear | Linear | Linear | Linear | Linear | CNN | Linear |
| Policy Layers | 1 | 1 | 1 | 1 | 2 | 2 | 2 |
| Critic Head | Linear | Linear | Linear | Linear | Linear | Linear | Linear |
| Critic Layers | 1 | 1 | 1 | 1 | 2 | 1 | 2 |
| Reward Design | $\Delta$ | $\Delta/20$ | $\pm 1$ | $\pm 1$, 0 | $\pm 1$ | $\pm 1$ | $\Delta/\text{Stack}$ |
| Outer Iteration | 50 | 50 | 50 | 50 | 50 | 50 | 50 |
| Inner Iteration | 1000 | 1000 | 2000 | 2000 | 2000 | 2000 | 2000 |

### B.3 Environment Domain

We evaluate NashPG across seven two-player zero-sum games, Our benchmark covers Kuhn Poker, Leduc Poker, Dark Hex (3$\times$3), and Phantom Tic-Tac-Toe, with approximately $54$, $9{,}300$, $2.9\times 10^{10}$, and $2.7\times 10^{10}$ non-terminal histories, respectively [34, 29].
We also evaluate on three real-world domains: Liar’s Dice, Battleship, and Heads-Up No-Limit Texas Hold’em. Liar’s Dice alone comprises roughly $10^{20}$ non-terminal histories, while Battleship and Heads-Up No-Limit Texas Hold’em are vastly larger.
All environments use lightweight neural architectures comprising a feature extractor, a policy head, and a critic head, keeping capacity low to emphasise learning dynamics.
For the two imperfect-information board games (Dark Hex and Phantom Tic-Tac-Toe), we apply the *abrupt* turn rule, i.e. any blocked move immediately ends the acting player’s turn, and we follow the configurations provided by OpenSpiel [18]. Architectural details are summarised in Table [3](https://arxiv.org/html/2510.18183v1#A2.T3). We denote by $\Delta$ the true gain or loss within a game or hand in poker-related environments. For instance, in Heads-Up No-Limit Texas Hold’em, if two players build a $50 pot through betting and calling, and Player 1 bets an additional $30 and Player 2 folds, then $\Delta=+25$ for Player 1 and $-25$ for Player 2.
Comprehensive environment rules, architectural specifications, and reward formulations are listed below for reproducibility.

Kuhn Poker:
A three-card, two-player imperfect-information poker game in which both players ante one chip and act sequentially by betting or passing. We encode the private card and betting sequence into a vector, process it with two linear layers, and apply linear policy and critic heads. Rewards are zero during play; at termination, the winner receives the pot and the loser forfeits their contribution. Observations include three dimensions for one-hot encoding of the private card (J=0, Q=1, K=2) and four dimensions for the complete betting history from the current player’s perspective.

Leduc Poker:
An variant of Poker with six cards (two suits, three ranks), two betting rounds, and a public card revealed in the second round; raises are of fixed size. Rewards are zero during play; a fold immediately ends the hand in favour of the non-folding player, otherwise showdown is decided by pair strength or high card. In our implementation, we normalize the reward by factor of $20$. Observations include 14 dimensions for one-hot encoding of the public and private cards (J$\spadesuit$=0, Q$\spadesuit$=1, K$\spadesuit$=2, J$\heartsuit$=3, Q$\heartsuit$=4, K$\heartsuit$=5), one for the revealed public-card indicator, two for the round indicator, two for player position, and 32 for the full betting history.

Dark Hex (3$\times$3):
A two-player imperfect-information variant of Hex on a $3\times 3$ board: Player 0 aims to connect top to bottom, and Player 1 aims to connect left to right. Each player observes only their own successful placements and opponent stones discovered by attempting an already-occupied cell (a blocked move). We apply the *abrupt* rule. Rewards are zero during play; a successful placement that completes the acting player’s connection immediately ends the game with $\pm 1$ (Hex admits no draws on a filled board). Observations are a length-9 vector with entries $\{-1,0,1\}$ denoting unknown, own stone, anddiscovered opponent stone.

Phantom Tic-Tac-Toe:
A two-player imperfect-information version of Tic-Tac-Toe on a $3\times 3$ grid: players alternate attempting to place a mark but observe only their own successful placements and cells where a previous attempt was blocked (revealing an opponent mark). We also use the *abrupt* rule. Rewards are zero during play; a successful placement forming three-in-a-row yields $\pm 1$, and a full board with no line results in a draw with 0 to both players. Observations are a length-9 vector with $\{-1,0,1\}$ encoding unknown, own mark, and discovered opponent mark.

Liar’s Dice:
We implement a single-hand version with 5 dice, each having 6 faces. This is a sequential bidding game in which each player privately rolls dice and alternately bids on the total count of a face value across both players until someone issues a challenge; the dice are then revealed to resolve the claim. Rewards are zero until a challenge occurs; the previous bidder wins if the claim is correct, and the challenger wins otherwise, yielding $\pm 1$. Observations contain 16 historical bidding states, each using three dimensions to record player ID, bid quantity, and bid face, plus six dimensions for the counts of each face in the player’s private dice.

Battleship:
A two-stage, two-player game on a $10\times 10$ grid: players first place ships, then alternate attacks until one fleet is destroyed. Rewards are $+1$ for victory and $-1$ for defeat; termination occurs when a player’s fleet is eliminated. Observations include 100 dimensions for the grid state, 10 for remaining ship statuses, and one for the current stage.

Heads-Up No-Limit Texas Hold’em:
A two-player no-limit poker variant with blinds and four betting streets (preflop, flop, turn, river) and up to five community cards. Actions include folding, checking/calling, a 16 different fractional pot-sized raises, and all-in moves. At the beginning, the small blind/big blind is set to 1/2 and stacks are initialized at 200 chips (100 big blinds) per player. Rewards are zero during play and correspond to normalized stack changes at the end of each hand; termination within a hand occurs upon a fold or at showdown (the overall match ends if a player goes bankrupt). Observations include two dimensions for the private and five for community cards, two for each player’s stacks, two for each player’s bets, one for pot size, one for the current street ID, and a sequence of historical actions. We use a history window of 64, each entry containing four dimensions (player ID, street ID, action taken, and betting amount).

## Appendix C Additional Experiments

### C.1 Anneal Regularization Strength as Nash Equilibria solver

Sokota et al. [34] introduced *Magnetic Mirror Descent* (MMD) and suggested two potential strategies for applying MMD to compute Nash equilibria: (i) *moving magnet*, which interpolates between the magnet policy and the current policy, and (ii) *annealing the regularization strength*. While the moving magnet approach is conceptually appealing, it requires geometric blending of policies at every information set, which is computationally infeasible in large games. This leaves annealing as the more practical alternative.

Here, we examine the feasibility of annealing regularization strength in the presence of stochastic sampling noise, i.e., when gradients are estimated from sampled trajectories rather than exact feedback. We conduct experiments on *Kuhn Poker*, a small imperfect-information game that exact computation of exploitability is feasible, making it a suitable testbed.

We use the same PPO hyperparameters as all other experiments and investigate the effect of linearly decaying the magnet coefficient $\alpha$. Specifically, we test initial values $\alpha\in\{0.2,0.4\}$, annealed linearly to $0.001$. We additionally consider jointly decaying both $\alpha$ and the learning rate $\eta$, with $\eta$ decayed linearly to zero. Each setting is repeated over four runs, and we report the mean and standard deviation of exploitability. Results are shown in Figure [4](https://arxiv.org/html/2510.18183v1#A3.F4).

Figure: Figure 4: Exploitability under annealing different initial values for $\alpha$ (optionally annealing $\eta$). In all cases, exploitability diverges as $\alpha$ decreases.
Refer to caption: x4.png

The results reveal a consistent pattern: exploitability decreases steadily during the early stages of training, but as $\alpha$ becomes small, performance deteriorates and eventually diverges. Even when annealing $\eta$ jointly with $\alpha$, training proceeds more slowly and still exhibits divergence at later stages. These findings indicate that annealing regularization strength is inherently unstable in the stochastic setting. While careful hyperparameter tuning may mitigate these issues, the dependence of the dynamics on both $\alpha$ and $\eta$ (recall the MMD convergence constraint $\alpha\geq\mu\eta L^{2}$) makes annealing regularization an unattractive choice as a general-purpose solver for Nash equilibria.

### C.2 Runtime and Memory Analysis

**Table 4: Hardware specifications for all experiments.**
| Component | Specification |
| --- | --- |
| CPU | AMD Ryzen Threadripper 3970X, 32 cores / 64 threads, |
|  | 3.7 GHz (boost enabled), 128 MB L3 cache |
| RAM | 256 GB DDR4 |
| GPU | 4 × NVIDIA GeForce RTX 4090 (24 GB GDDR6X each, PCIe) |
| Storage | 2 × 2 TB NVMe SSDs |
| OS | Ubuntu 20.04 LTS |

To complement our performance analysis, we measured both real (wall-clock) training time and peak GPU memory allocation throughout the experiments. The hardware configuration used in our experiments is listed in Table [4](https://arxiv.org/html/2510.18183v1#A3.T4), and all experiments were run with a single algorithm assigned to a single GPU at a time to ensure consistency. For brevity, we report results for four environments: *Kuhn Poker*, *Leduc Poker*, *Battleship*, and *Heads-Up No-Limit Texas Hold’em*. Detailed settings are summarized in Table [3](https://arxiv.org/html/2510.18183v1#A2.T3). However, our results should be interpreted with caution, as population-based methods are sensitive to implementation details and may vary across studies. We aimed to provide a fair comparison but note that our implementation may not be the most efficient. For example, prior work such as Pipeline PSRO [24] makes PSRO parallelizable, whereas we implemented the vanilla version.

Figure: Figure 5: Maximum GPU memory usage during training across environments and algorithms.
Refer to caption: x5.png

Memory Footprint: [Figure 5](https://arxiv.org/html/2510.18183v1#A3.F5) shows the peak GPU memory usage during training under the settings described in Appendix [B.1](https://arxiv.org/html/2510.18183v1#A2.SS1). Population-based methods (NFSP and PSRO) consume substantially more memory than single-agent approaches, as our implementation requires storing all historical agents. This limits scalability with larger models in complex environments. For example, in No-Limit Texas Hold’em, our current model size is approximately 4.6 MiB, yet PSRO and NashPG differ by about 316 MiB—roughly 67$\times$ the model size—after 50 meta-updates.

Figure: Figure 6: Total wall-clock time during training across all evaluated environments and algorithms.
Refer to caption: x6.png

Runtime: As shown in [Figure 6](https://arxiv.org/html/2510.18183v1#A3.F6), *PSRO* incurs significantly higher wall-clock costs, requiring approximately 3.1–7.3$\times$ more time than NashPG and *MMD* across all tested environments. *NFSP* is also slower, with 1.3–2.8$\times$ higher runtime. One contributing factor to this overhead is that the meta-update stage in PSRO requires evaluating pairwise interactions with all previously trained agents, resulting in an $O(n^{2})$ runtime complexity as the population grows. Additionally, as the population increases in NFSP and PSRO, the computation graph changes, causing JAX to recompile every outer iteration, which introduces further overhead.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 2
presentation: 2
questions: I think the paper would strongly benefit from having a table of sort describing the different contribution of this work vs mmd vs R-NaD (deep Nash, FoReL, etc).

Why are the MMD experiment ran with PPO? Is it unreasonable to do vanilla policy gradient directly? This is the first MMD implementation I've seen that uses PPO.

The claim @206 that the need to decrease learning rate must decrease with temperature is problematic is not evaluated. As the temperature decreases the movement of the regularized Nash also decreases (at least empirically) as it moves on a finite curve from the objective with alpha_0 regularization to the maximum entropy objective with no entropy. Are there any evidence that these vanishing step sizes are problematic?
soundness: 2
strengths: On the more material side of things, the paper is well written, the accompanying Jax codebase is also easy to read. The paper proposes a natural way of updating the magnet of MMD which has been used successfully in R-NaD.
summary: Regularized Nash equilibriums are easier to compute compared their non-regularized counterpart but are exploitable in the original game. There exists a body of works that try to shrink this gap. Commonly, this is done via temperature decay. Unfortunately, lower temperatures are often unstable and converge slowly. R-NaD and FoReL proposed to iteratively regularize to the previous Nash equilibrium in an iterative process. This work proposes a policy space version of the same result.
weaknesses: The theoretical results are not exciting. They are equivalent to the theorems of R-NaD (FoReL) but for mirror decent instead of follow the regularized leader (FTRL).

The experiments are questionable. For starters, the choice of using a linear policy is questionable. This is particularly concerning as the results do not match, for instance those of Rudolph et al 2025 (cited @965).  Calculating exploitability with neural networks has been shown to be extremely unreliable but the authors do not measure it for the 4 games @ 413 even thought exploitability calculation is readily available. Plotting standard deviation with 4 samples is somewhat questionable. Negative exploitability is a clear indicator of  bug or learning issues. In the worst case it should be zero by initializing the best response policies with the best policy available. The use of ELO for hold'em is questionable as the average win points is the quantity of interest. Similarly, given that imperfect information games are cyclic in nature, the use of ELO is also questionable. In all cases EVs should have been reported instead. Furthermore, for hold'em, a comparison with slumbot is necessary to gauge the strength of the policy. The "real games" are not necessary real games, for liars dice, the 6th dice is missing and the observations are not open spiel compatible.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. Could you compare the theoretical results with references [1,2,3,4] to further explain what leads to the advantage of your theory?

2. Could you also compare NashPG with NeuRD [5] or explain the reason why you prefer not to compare it in the experiment?
soundness: 3
strengths: 1. This paper is well-written and easy to follow. The background of solving regularized variational inequalities is well-introduced.

2. The theoretical results of iterative improvement are clearly demonstrated without assuming interior or unique NE.

3. The construction of NashPG is elegant, making the algorithm generally applicable under different single-agent RL algorithms.

4. Extensive experiments convince me that NashPG is efficient. The choices of performance measure are also reasonably explained.
summary: This paper examines regularization-based equilibrium finding in two-player zero-sum games. The paper proves that iteratively replacing the reference policy in Magnetic Mirror Descent (MMD) with the fixed-point policy of the last learning round guarantees monotonic improvement and last-iterate convergence towards Nash equilibrium (NE). Based on this finding, the paper proposes a reinforcement learning algorithm called Nash Policy Gradient (NashPG) that iteratively reduces the exploitability of the learned policy for practically solving large-scale games. Experiments in benchmark or real-world games demonstrate the superiority of NashPG over MMD and average-iterate-based algorithms like Neural Fictitious Self-Play (NFSP) and Policy-Space Response Oracles (PSRO).
weaknesses: 1. The idea of iteratively replacing the reference policy is not that novel in view of the existing literature [1,2,3,4] in the field of equilibrium finding.

2. More recent RL algorithms for solving imperfect-information games (like NeuRD [5]) could also be considered as comparative methods.

[1] Julien Perolat, et al. From Poincare recurrence to convergence in imperfect information games: Finding equilibrium via regularization. ICML, 2021.

[2] Kenshi Abe, et al. Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games. UAI, 2022.

[3] Kenshi Abe, et al. Adaptively perturbed mirror descent for learning in games. ICML, 2024.

[4] Runyu Lu, et al. Divergence-regularized discounted aggregation: Equilibrium finding in multiplayer partially observable stochastic games. ICLR, 2025.

[5] Julien Perolat, et al. Mastering the game of Stratego with model-free multiagent reinforcement learning. Science, 2022.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: - How about multi-agent RL beyond two-player zero-sum?
- How does this compare or relate to the anchor changing algorithm [2] in single-agent RL?
Zhou, Ruida, et al. "Anchor-changing regularized natural policy gradient for multi-objective reinforcement learning." Advances in neural information processing systems 35 (2022): 13584-13596.
- In the experiments, what does the step number represent? Since the proposed NashPG is a dual-loop method, whereas some other baseline methods are single-loop. Does step number represent T or KT? It could be an unfair advantage for the other algorithms. A better approach is to compare the number of gradient calculations across different algorithms.
soundness: 3
strengths: The idea of iterative refinement under fixed regularization strength was not previously explored in MARL. The analytical results seem rigorous and intuitive to the reviewer.
The empirical evaluation of NashPG is not limited to toy examples to validate the theoretical result. The authors also included more complicated games with imperfect information to demonstrate the performance and effectiveness of NashPG compared to baseline methods.
The paper is well written with clear motivations, and the theoretical and experimental results are also presented in a concise and readable manner.
summary: This paper introduces Nash Policy Gradient (NashPG), a novel algorithm for finding Nash equilibria in two-player zero-sum games. The authors fix regularization at a large value for stability and achieve convergence through iterative refinement of a reference policy. Theoretically, the authors showed that NashPG demonstrates monotonic improvement and convergence to the Nash equilibrium. Experiments on benchmark and imperfect-information games show that NashPG not only exhibit faster convergence, but also achieves lower exploitability and higher Elo ratings than population-based and CFR-inspired baselines.
weaknesses: Although the authors did provide a theoretical analysis, no convergence guarantees in finite time were provided; instead, there were only a few lemmas. This significantly hurt the theoretical contribution of this work, especially since existing policy gradient algorithms such as [1] have been shown to guarantee convergence to NE in finite time. The author also did not cite this paper and a few other closely related works.
[1] Zhang, Kaiqing, et al. "Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity." Journal of Machine Learning Research 24.175 (2023): 1-53.

The authors should include synthetic examples in order to show convergence properties. Current experiments are very different from the algorithms in the previous sections. At the very least, the authors should have had experiments demonstrating the monotonic descent properties of NashPG in practice.

---

confidence: 4
contribution: 1
initial_rating: 2
presentation: 3
questions: See weaknesses. May the authors explain the main contribution of this paper compared to [1]? I would be happy to re-evaluate the paper if the authors could clarify this.
soundness: 3
strengths: - The presentation is clear and easy to follow
- The paper includes deep learning experiments and achieves better performance compared to the baselines
summary: The paper solves Nash equilibrium in two-player zero-sum extensive-form games by adding additional regularization. By switching the reference strategy periodically, the algorithm converges to the NE of the original game rather than the regularized game. The paper proves convergence theoretically and empirically evaluates its performance.
weaknesses: My major concern is that the comparison with previous work is not enough. The most relevant paper I can think of, [1], is not included in this paper.

[1] added additional regularization and changed the reference strategy periodically. Moreover, [1] had theoretical guarantees on convergence.

[1] Abe, Kenshi, et al. "Adaptively perturbed mirror descent for learning in games." arXiv preprint arXiv:2305.16610 (2023).