# Decentralized Policy Gradient for Nash Equilibria Learning of General-sum Stochastic Games

arXiv: https://arxiv.org/abs/2210.07651 · HTML: https://mlsanity.com/paper/2210.07651/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 46 references that are in the map.
- First posted on arXiv 14 Oct 2022.

## Builds on (most cited first, 11 of 11)

- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems](https://mlsanity.com/paper/1810.10207/) (2018)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities](https://mlsanity.com/paper/2103.04410/) (2021)
- [Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2102.08903/) (2021)

## Built on by (most cited first, 2 of 2)

- [Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Survey](https://mlsanity.com/paper/2401.04934/) (2024)
- [Decentralized Bandit Learning of Markov Perfect Equilibria](https://mlsanity.com/paper/2610.14333/) (2026)

## Abstract (arXiv)

We study Nash equilibria learning of a general-sum stochastic game with an unknown transition probability density function. Agents take actions at the current environment state and their joint action influences the transition of the environment state and their immediate rewards. Each agent only observes the environment state and its own immediate reward and is unknown about the actions or immediate rewards of others. We introduce the concepts of weighted asymptotic Nash equilibrium with probability 1 and in probability. For the case with exact pseudo gradients, we design a two-loop algorithm by the equivalence of Nash equilibrium and variational inequality problems. In the outer loop, we sequentially update a constructed strongly monotone variational inequality by updating a proximal parameter while employing a single-call extra-gradient algorithm in the inner loop for solving the constructed variational inequality. We show that if the associated Minty variational inequality has a solution, then the designed algorithm converges to the k^{1/2}-weighted asymptotic Nash equilibrium. Further, for the case with unknown pseudo gradients, we propose a decentralized algorithm, where the G(PO)MDP gradient estimator of the pseudo gradient is provided by Monte-Carlo simulations. The convergence to the k^{1/4} -weighted asymptotic Nash equilibrium in probability is achieved.