google-deepmind / google-deepmind/open_spiel
Implement NashPG (Nash Policy Gradient): a Simple PPO-Based Nash Solver
- 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
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