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

1. Problem Statement

The paper addresses the challenge of finding Nash Equilibria (NE) in two-player zero-sum imperfect-information games (2p0s IIGs) using Multi-Agent Reinforcement Learning (MARL).

• The Core Difficulty: While Deep Reinforcement Learning (DRL) has succeeded in perfect-information games, 2p0s IIGs (like Poker) involve partial observability and hidden information.
• Limitations of Existing Methods:
  • Population-based methods (e.g., PSRO, NFSP): Often require expensive best-response computations and only guarantee convergence to an average policy, not the last iteration. Extracting a final policy in DRL settings is non-trivial.
  • Counterfactual Regret Minimization (CFR): Requires full game tree enumeration (model-based), making it intractable for large domains.
  • Regularization-based methods (e.g., R-NaD): Recent approaches use regularization to ensure last-iteration convergence to a regularized equilibrium. However, these are not necessarily true Nash Equilibria (they remain exploitable). Furthermore, existing practical implementations (like R-NaD) rely on Neural Replicator Dynamics (NeuRD), which has shown inferior performance compared to standard policy gradient methods in benchmarks.
• The Gap: There is a lack of a scalable, model-free, policy-gradient-based algorithm that provably converges to an exact Nash Equilibrium in large-scale IIGs.

2. Methodology

The authors propose a two-stage approach: a theoretical framework (IMMD) and a practical algorithm (NASHPG).

A. Theoretical Framework: Iterative MMD (IMMD)

The authors extend Magnetic Mirror Descent (MMD), a method that solves regularized Variational Inequalities (VI).

• Regularized VI: Standard VI problems for Nash Equilibria are monotone but not strongly monotone, making them hard to solve directly. MMD adds a strongly convex regularizer (based on Bregman divergence) to create a strongly monotone operator, ensuring a unique solution.
• Iterative Refinement: Instead of solving one regularized problem, IMMD solves a sequence of them.
  1. Start with an initial strategy profile $\rho$.
  2. Solve the regularized VI problem $VI(Z, G_\rho)$ to find a new strategy $z = M(\rho)$.
  3. Use this new strategy $z$ as the reference $\rho$ for the next round.
• Theoretical Guarantee: The paper proves that this iterative process yields a strictly monotonic reduction in the Bregman divergence to any Nash Equilibrium. Consequently, the sequence of strategies converges to a true Nash Equilibrium.

B. Practical Algorithm: Nash Policy Gradient (NASHPG)

To make IMMD applicable to large-scale games where full enumeration is impossible, the authors derive NASHPG:

• From Mixed to Behavioral Strategies: They approximate the mixed-strategy Bregman divergence (used in IMMD) with a Kullback-Leibler (KL) divergence between behavioral policies (stochastic policies in RL).
• Objective Function: The algorithm optimizes a regularized policy objective:
  $$\text{Objective} = \mathbb{E}[R] - \alpha \cdot \mathbb{E}_{o} [ D_{KL}(\pi(\cdot|o) \parallel \rho(\cdot|o)) ]$$
  Where $\pi$ is the current policy, $\rho$ is the reference policy (from the previous outer loop), and $\alpha$ is the regularization strength.
• Algorithm Structure:
  1. Inner Loop: Perform $K$ steps of standard policy gradient updates (e.g., using PPO) to optimize the regularized objective against the current reference $\rho$.
  2. Outer Loop: After $K$ steps, update the reference policy $\rho$ to the current policy $\pi$, and repeat.
• Modularity: NASHPG is agnostic to the specific policy gradient estimator. It can seamlessly integrate with advanced single-agent RL algorithms like PPO (Proximal Policy Optimization).

3. Key Contributions

1. Theoretical Convergence: Introduced IMMD, a multi-round regularization framework that guarantees strictly monotonic reduction in Bregman divergence and convergence to an exact Nash Equilibrium in 2p0s extensive-form games.
2. Practical Algorithm (NASHPG): Developed a scalable, model-free algorithm that implements the IMMD framework using standard policy gradient methods (like PPO) and KL regularization.
3. Hypothesis Validation: Provided empirical evidence that the poor performance of previous regularization methods (like R-NaD) was due to the use of NeuRD as the inner solver, rather than the regularization framework itself. Replacing NeuRD with PPO in a similar framework significantly improved performance.
4. Scalability: Demonstrated the ability to solve large-scale domains (e.g., Battleship, Heads-Up No-Limit Texas Hold'em) where exact enumeration is impossible.

4. Experimental Results

The authors evaluated NASHPG on seven games ranging from small (Kuhn Poker) to massive (Heads-Up No-Limit Texas Hold'em).

• Convergence & Stability: NASHPG showed stable convergence without divergence, even with high regularization strengths, unlike some baselines.
• Performance vs. Baselines:
  • Small Games: NASHPG achieved comparable or lower exploitability than NFSP, PSRO, MMD, and R-NaD on Kuhn Poker, Leduc Poker, Dark Hex, and Phantom Tic-Tac-Toe.
  • Large Games: In Battleship and Heads-Up No-Limit Texas Hold'em (where exact exploitability is intractable), NASHPG achieved higher average payoffs in head-to-head matches against all baselines (NFSP, PSRO, R-NaD, MMD).
• Ablation Study (R-NaD vs. PPO): A controlled experiment replaced NeuRD with PPO in the R-NaD framework (creating RNaD-PPO).
  • In small games, the update rule mattered less.
  • In large games, RNaD-PPO dramatically outperformed standard R-NaD, narrowing the gap with NASHPG. This confirmed that the inner optimization rule (PPO vs. NeuRD) is the primary bottleneck in sample-based multi-round regularization.
• Efficiency: The implementation required only ~20 lines of code modification over standard Independent PPO, highlighting its accessibility.

5. Significance

• Bridging Theory and Practice: The paper successfully bridges the gap between theoretical convergence guarantees (often limited to small, enumerated games) and practical, scalable MARL algorithms.
• New Paradigm for MARL: It establishes that iteratively refining a regularization reference combined with standard policy gradients is a superior approach for finding Nash Equilibria compared to population-based methods or older regularization techniques.
• Accessibility: By relying on standard PPO and simple KL regularization, NASHPG lowers the barrier to entry for practitioners, allowing them to apply advanced game-theoretic convergence guarantees without needing complex custom solvers or full game tree enumeration.
• State-of-the-Art Performance: It sets a new benchmark for model-free methods in imperfect-information games, outperforming established baselines in both small and large domains.