# Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 36 of its 62 references that are in the map.
- First posted on arXiv 26 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Builds on (most cited first, 30 of 36)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [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)
- [Opponent Modeling in Deep Reinforcement Learning](https://mlsanity.com/paper/1609.05559/) (2016)
- [Learning to Schedule Communication in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1902.01554/) (2019)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [Multi-Agent Reinforcement Learning in Stochastic Networked Systems](https://mlsanity.com/paper/2006.06555/) (2020)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Learning Parametric Closed-Loop Policies for Markov Potential Games](https://mlsanity.com/paper/1802.00899/) (2018)
- [Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.17116/) (2022)
- [Value Propagation for Decentralized Networked Deep Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1901.09326/) (2019)
- [On the convergence of policy gradient methods to Nash equilibria in general stochastic games](https://mlsanity.com/paper/2210.08857/) (2022)
- [Networked Multi-Agent Reinforcement Learning with Emergent Communication](https://mlsanity.com/paper/2004.02780/) (2020)
- [Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games](https://mlsanity.com/paper/2310.09727/) (2023)
- [Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Games](https://mlsanity.com/paper/2111.04317/) (2021)
- [Dynamic Potential Games in Communications: Fundamentals and Applications](https://mlsanity.com/paper/1509.01313/) (2015)
- [Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking](https://mlsanity.com/paper/1809.07383/) (2018)
- [Learning to Share in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2112.08702/) (2021)
- [Multi-Agent Reinforcement Learning for Pragmatic Communication and Control](https://mlsanity.com/paper/2302.14399/) (2023)
- [Vehicle Tracking in Wireless Sensor Networks via Deep Reinforcement Learning](https://mlsanity.com/paper/2002.09671/) (2020)

## Abstract (arXiv)

We propose networked policy gradient play for solving Markov potential games with continuous and/or discrete state-action pairs. During the game, agents use parametrized and differentiable policies that depend on the current state and the policy parameters of other agents. During training, agents update their policy parameters following stochastic gradients. The gradient estimation involves two consecutive episodes, generating unbiased estimators of reward and policy score functions. In addition, it involves keeping estimates of others' parameters using consensus steps given local estimates received through a time-varying communication network. In Markov potential games, there exists a potential value function among agents with gradients corresponding to the gradients of local value functions. Using this structure, we prove almost sure convergence to a stationary point of the potential value function with rate O(1/ε2). Compared to previous works, our results do not require bounded policy gradients or initial agreement on the values of individual policy parameters. Numerical experiments on a dynamic multi-agent newsvendor problem verify the convergence of local beliefs and gradients. It further shows that networked policy gradient play converges as fast as independent policy gradient updates, while collecting higher rewards.