Implement NashPG (Nash Policy Gradient): a Simple PPO-Based Nash Solver

[easonyu0203]

Summary

I'd like to contribute NashPG (arXiv:2510.18183, Yu et al. 2026; accepted in TMLR 2026; I'm the lead author). NashPG is a policy-gradient method for finding Nash equilibria.

Algorithmically, it is an independent PPO learner plus a KL-regularization term toward a "magnet" policy that is periodically refreshed to the current policy. It has a convergence guarantee in two-player zero-sum (2p0s) matrix games and scales empirically on 2p0s imperfect-information games from Kuhn poker up to no-limit heads-up Texas hold'em.

Relationship to R-NaD

NashPG targets a similar idea as R-NaD — iteratively refined regularization toward an anchor policy — but deliberately trades the machinery for simplicity:

• No V-trace, NeuRD, entropy schedule
• Just PPO + one KL term + a periodic magnet copy

Given R-NaD was removed as unmaintained (#1075, #1109, #1178), NashPG's simplicity may offer a much lower-maintenance way to keep a regularized-dynamics Nash solver in the repo. It also fits the independent-learner AbstractAgent model rather than a monolithic solver.

Proposed Implementation

• open_spiel/python/pytorch/nash_pg.py: one NashPG(rl_agent.AbstractAgent) instance per player, so it runs in the standard self-play loop and works with JointRLAgentPolicy for exploitability, exactly like NFSP/DQN.

• Independent per-player networks and per-player magnets. (The paper shares parameters across players by relying on ego-centric observations; since OpenSpiel doesn't guarantee that, independent networks are both more general and closer to the "independent learners" framing).

• Magnet refresh:

  • With auto_update_magnet=True (default), each learner refreshes its magnet every magnet_update_period of its own updates.

  • An update_magnet() method is also exposed, so a user can set auto_update_magnet=False and drive a synchronized refresh from their training loop:

    for agent in agents:
        agent.update_magnet()

    This allows the implementation to match the paper's synchronized procedure exactly.

Scope

• Convergence guarantee: 2p0s matrix (normal-form) games.
• Empirically validated in the paper: 2p0s turn-based imperfect-information games.
• Runs, but with no guarantees: General-sum games; More than 2 players; simultaneous-move games.
• Not supported: Turn-based games with intermediate rewards; Mean-field games.

Deliverables in the PR

• nash_pg.py
• nash_pg_pytorch_test.py (registered in python/CMakeLists.txt) Note: Designed to be lightweight and execute quickly in CI.
• examples/nash_pg_example.py
• One row in docs/algorithms.md under the MARL category, with status "lightly tested"
• Default hyperparameters tuned for Kuhn poker.
• Correctness evidence: Exact exploitability curves on Kuhn and Leduc across 5 seeds (to be included in the PR description).

Reference Implementation

https://github.com/ntu-agents/nashpg

Open Questions

• Does this structure and the design choices look right to you? Happy to change or clarify any of it before I open the PR.
• To keep the initial PR easy to review, I am planning to start with just the PyTorch implementation. A JAX version should port easily from the same design, glad to implement both together if you'd rather they land at once.

[lanctot]

This would be a very welcome addition! Design sounds great, thanks! 😁

Pytorch is fine, and you are someone can add a JAX impl later.