google-deepmind / google-deepmind/open_spiel

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

Open
#1,596 1 comment 1 reaction 0 assignees View on GitHub
contribution welcome
Dominant language
C++
Stars
5.5k
Forks
1.2k
Avg merge
2d 8h
Merged PRs (30d)
4

Description

## Summary

I'd like to contribute NashPG ([arXiv:2510.18183](https://arxiv.org/abs/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:

```python
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.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the proposed open_spiel/python/pytorch/nash_pg.py design alongside the AbstractAgent, NFSP, and DQN patterns, then inspect the reference implementation. Add the lightweight nash_pg_pytorch_test.py, register it in python/CMakeLists.txt, and create examples/nash_pg_example.py. Done includes the algorithms.md entry, Kuhn-tuned defaults, and exploitability curves for Kuhn and Leduc across five seeds.

Written by the indexing model from the issue text.

Assessment

Tech stack
python, pytorch
Domain
machine-learning
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.