mlsanityData to 7 Oct 2026

Provable Policy Gradient Methods for Average-Reward Markov Potential Games

arXiv 2403.05738 ↗First posted 9 Mar 2024cs.LG cs.GTcited by 5

Not on the map. Why?

Abstract (arXiv)

We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an ε-Nash equilibrium with time complexity O(frac1ε2), given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with tildeO(frac1mins,aπ(a|s)δ) sample complexity to achieve δ approximation error w.r.t~the ℓ2 norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of tildeO(1/ε5). Simulation studies are presented.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 26 of its 59 references that are in the map. First posted on arXiv 9 Mar 2024.

Builds on

26 of 59 references.

References · 26

  1. 2019The StarCraft Multi-Agent Challengecited by 589
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  5. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  6. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  7. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  8. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  9. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  10. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  11. 2022Reinforcement Learning with Sparse Rewards using Guidance from Offline Demonstrationcited by 54
  12. 2020Multi-agent Reinforcement Learning for Networked System Controlcited by 51
14 more
  1. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  2. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  3. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  4. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 31
  5. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  6. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  7. 2022On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Gamescited by 22
  8. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 19
  9. 2021Average-Reward Reinforcement Learning with Trust Region Methodscited by 18
  10. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  11. 2020Reward Biased Maximum Likelihood Estimation for Reinforcement Learningcited by 11
  12. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  13. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  14. 2023Markov α-Potential Gamescited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 1.

5 papers.

  1. 2024Policy Optimization finds Nash Equilibrium in Regularized General-Sum LQ Gamescited by 2
  2. 2024Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularizationcited by 1
  3. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  4. 2025Policy Optimization and Multi-agent Reinforcement Learning for Mean-variance Team Stochastic Gamescited by 0
  5. 2025Independent policy gradient-based reinforcement learning for economic and reliable energy management of multi-microgrid systemscited by 0