Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Games
On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization
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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, 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.
Builds on
36 of 62 references.
References · 36
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
- 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 942
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
- 2017Learning with Opponent-Learning Awarenesscited by 222
- 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
- 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
- 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
- 2016Opponent Modeling in Deep Reinforcement Learningcited by 97
- 2019Learning to Schedule Communication in Multi-agent Reinforcement Learningcited by 93
- 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
- 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
24 more
- 2020Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Rewardcited by 50
- 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 37
- 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 36
- 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 34
- 2020Multi-Agent Reinforcement Learning in Stochastic Networked Systemscited by 32
- 2020Fictitious play in zero-sum stochastic gamescited by 26
- 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 21
- 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 20
- 2019Value Propagation for Decentralized Networked Deep Multi-agent Reinforcement Learningcited by 19
- 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 16
- 2020Networked Multi-Agent Reinforcement Learning with Emergent Communicationcited by 13
- 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 13
- 2021Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Gamescited by 10
- 2015Dynamic Potential Games in Communications: Fundamentals and Applicationscited by 8
- 2018Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seekingcited by 7
- 2021Learning to Share in Multi-Agent Reinforcement Learningcited by 5
- 2023Multi-Agent Reinforcement Learning for Pragmatic Communication and Controlcited by 3
- 2020Vehicle Tracking in Wireless Sensor Networks via Deep Reinforcement Learningcited by 2
- 2021Decentralized Fictitious Play in Near-Potential Games with Time-Varying Communication Networkscited by 2
- 2022Recursive Reasoning in Minimax Games: A Level k Gradient Play Methodcited by 2
- 2018Path Planning for Minimizing the Expected Cost until Successcited by 1
- 2019Distributed Fictitious Play in Potential Games with Time-Varying Communication Networkscited by 1
- 2023RAPID: Autonomous Multi-Agent Racing using Constrained Potential Dynamic Gamescited by 1
- 2024On Characterizations of Potential and Ordinal Potential Gamescited by 1
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2026Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games
- 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Games
- 2024A Scalable Game Theoretic Approach for Coordination of Multiple Dynamic Systems
- 2025Policy Gradient with Self-Attention for Model-Free Distributed Nonlinear Multi-Agent Games ↗
- 2024Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games
- 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
- 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence
- 2024Independent Learning in Constrained Markov Potential Games