NashPG: Independent PPO with a Moving Magnet

I have always been drawn to what self-play can achieve. AlphaGo's move 37 against Lee Sedol [7], a move experts first took for a mistake. OpenAI's hide-and-seek agents discovering tool use just by playing the game [8]. Both came from agents competing against copies of themselves. However, "self-play" is a slippery term, since it is rarely made clear what the policy is actually trying to learn, i.e., the solution concept. If you look closely, when researchers talk about self-play, they usually mean learning a Nash equilibrium in a two-player zero-sum game.

So I started looking for practical algorithms that find Nash equilibria, and none of them satisfied me. They either maintain a growing population of agents, which is expensive to train, or they rely on complex update rules that are hard to implement correctly. I wanted something simple, something that looks like single-agent RL, where each player just does naive independent updates.

This led us to Nash Policy Gradient (NashPG) [1], published in TMLR. NashPG is essentially Independent PPO with a regularization target—a magnet—that periodically moves to the latest policy. The change is small, but it gives us a practical algorithm that is easy to implement and performs well from small benchmark games to large domains such as Battleship and Heads-Up No-Limit Texas Hold'em.

Why not just train a population?

Population-based algorithms such as Neural Fictitious Self-Play (NFSP) [2] and Policy Space Response Oracles (PSRO) [3] are important tools for competitive multi-agent learning. Instead of asking one policy to represent the solution, they train successive agents and reason about a mixture over the resulting population. This idea is powerful: population and league-based training played a central role in AlphaStar [4].

But the population is also the source of practical overhead. We must train and store many policies, and the equilibrium object is their mixture rather than any individual policy. Deploying one neural network then requires additional machinery, such as sampling from the population or distilling its behavior. The cost grows as more strategies are added.

Single-policy methods do exist. Regularization-based algorithms stabilize learning by pulling the current policy toward a reference policy. However, a fixed reference generally leads to a regularized equilibrium, which can remain exploitable. R-NaD addresses this by repeatedly updating its regularization policy and is the central learning algorithm behind DeepNash [5]. Still, practical single-policy methods often rely on specialized update rules, and their empirical performance has been mixed across studies.

Our question was therefore: Can we keep the iterative-regularization idea, but implement it with standard policy-gradient machinery?

The algorithm we wanted to use

NashPG keeps one independently trained policy for each player. For player \(i\), we optimize a regularized objective of the form

\[ \mathbb{E}[R_i] - \alpha\,\mathbb{E}_{o}\!\left[ \mathrm{KL}\!\left(\pi_i(\cdot\mid o)\,\|\,\rho_i(\cdot\mid o)\right) \right], \]

where \(\pi_i\) is the current policy and \(\rho_i\) is its magnet. Each player performs ordinary PPO-style updates on this objective. After several updates, we set the magnet to the latest policy and repeat. The players remain independent throughout: they need only their own trajectories, rewards, and KL term.

1. Train each player's policy independently with PPO.
2. Regularize each policy toward its current magnet.
3. Periodically move the magnet to the updated policy.

In our JAX codebase, NashPG differs from Independent PPO by only about 20 lines of code. This simplicity is the part I like most: improvements to the underlying policy-gradient optimizer can be inherited without redesigning the game-solving algorithm.

Why should moving the magnet help?

We first study an exact mixed-strategy version of this procedure, which we call Iterative Magnetic Mirror Descent (IMMD). Each round solves a regularized game using the previous solution as the new reference. We prove that, unless the current strategy is already a Nash equilibrium, every exact refinement step strictly reduces its Bregman divergence to a Nash equilibrium:

\[ B_{\psi}(z^*;z_{t+1}) < B_{\psi}(z^*;z_t). \]

Repeating the refinement converges to a Nash equilibrium under the assumptions in the paper [1]. This theorem is for the exact mixed-strategy procedure, not directly for practical NashPG. NashPG replaces the exact inner solution with finite policy-gradient updates and uses behavioral-policy KL regularization, trading the formal guarantee for scalability. We keep this distinction explicit: the theory motivates the design, while the experiments tell us whether the approximation works in practice.

Does the simple version work?

We test NashPG on seven two-player zero-sum imperfect-information games. The suite ranges from Kuhn Poker, with only 12 information states, to Liar's Dice, Battleship, and Heads-Up No-Limit Texas Hold'em, whose information-state spaces exceed \(10^{20}\). We compare against NFSP, PSRO, R-NaD, and Magnetic Mirror Descent (MMD) [6], using matched training budgets and five random seeds.

On the four games where exact exploitability is available, NashPG consistently reaches low exploitability and is competitive with or better than the other model-free methods. The exception is Kuhn Poker, where the methods are broadly comparable.

Exact exploitability is intractable in the three largest games, so we train PPO best responses to estimate it. These estimates are lower bounds on true exploitability and depend on the quality of best-response training. We therefore also run direct head-to-head matches. NashPG obtains positive average payoff against both PSRO and R-NaD in all three large games [1]. We are particularly proud of this result: a small modification to Independent PPO remains competitive while avoiding population training and specialized inner optimizers.

Takeaway

NashPG is not a claim that equilibrium finding has become easy. Its practical version does not inherit the full IMMD theorem, and approximate evaluation in large games remains imperfect. What the results show is that a simple design can go surprisingly far: train independently, add a KL magnet, and move that magnet over time.

You can find the project page, paper, and code online.

References

1. Eason Yu, Tzu Hao Liu, Clément L. Canonne, Yunke Wang, Chang Xu, Nguyen H. Tran, and Stefano V. Albrecht. "NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria." Transactions on Machine Learning Research, 2026.
2. Johannes Heinrich and David Silver. "Deep Reinforcement Learning from Self-Play in Imperfect-Information Games." arXiv:1603.01121, 2016.
3. Marc Lanctot, Vinícius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. "A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning." Advances in Neural Information Processing Systems, 2017.
4. Oriol Vinyals et al. "Grandmaster Level in StarCraft II Using Multi-Agent Reinforcement Learning." Nature, 575:350–354, 2019.
5. Julien Perolat et al. "Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning." Science, 378(6623):990–996, 2022.
6. 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." International Conference on Learning Representations, 2023.
7. David Silver et al. "Mastering the Game of Go with Deep Neural Networks and Tree Search." Nature, 529:484–489, 2016.
8. Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. "Emergent Tool Use From Multi-Agent Autocurricula." International Conference on Learning Representations, 2020.