mlsanityData to 7 Oct 2026

Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games

arXiv 2303.04865 ↗First posted 8 Mar 2023cs.LG cs.AI cs.MAcited by 9

Not on the map. Why?

Abstract (arXiv)

We introduce a class of networked Markov potential games in which agents are associated with nodes in a network. Each agent has its own local potential function, and the reward of each agent depends only on the states and actions of the agents within a neighborhood. In this context, we propose a localized actor-critic algorithm. The algorithm is scalable since each agent uses only local information and does not need access to the global state. Further, the algorithm overcomes the curse of dimensionality through the use of function approximation. Our main results provide finite-sample guarantees up to a localization error and a function approximation error. Specifically, we achieve an tildeO(tildeε-4) sample complexity measured by the averaged Nash regret. This is the first finite-sample bound for multi-agent competitive games that does not depend on the number of agents.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 24 of its 49 references that are in the map. First posted on arXiv 8 Mar 2023.

Builds on

24 of 49 references.

References · 24

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  4. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  5. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  6. 2017On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learningcited by 136
  7. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  8. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  9. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  10. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  11. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  12. 2020Mean-Field Controls with Q-learning for Cooperative MARL: Convergence and Complexity Analysiscited by 44
12 more
  1. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  2. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  3. 2020Multi-Agent Reinforcement Learning in Stochastic Networked Systemscited by 30
  4. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 27
  5. 2014Control of Robotic Mobility-On-Demand Systems: a Queueing-Theoretical Perspectivecited by 24
  6. 2022On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Gamescited by 22
  7. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 20
  8. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 18
  9. 2021Stability Constrained Reinforcement Learning for Real-Time Voltage Controlcited by 11
  10. 2022Can Mean Field Control (MFC) Approximate Cooperative Multi Agent Reinforcement Learning (MARL) with Non-Uniform Interaction?cited by 6
  11. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  12. 2022On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learningcited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

9 papers.

  1. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  2. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  3. 2023Markov α-Potential Gamescited by 6
  4. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  5. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  6. 2025Independent Learning in Performative Markov Potential Gamescited by 5
  7. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3
  8. 2025Connectivity Management in Satellite-Aided Vehicular Networks with Multi-Head Attention-Based State Estimationcited by 0
  9. 2026Distributed Zeroth-Order Policy Gradient for Networked Multi-agent Reinforcement Learning from Human Feedbackcited by 0