Convergence Rates For Localized Actor-critic In Networked Markov Potential Games

Abstract

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 \(\tilde\{\mathcal\{O\}\}(\tilde\{\epsilon\}^\{-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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzhou2023convergence

Related papers

• Convergence Of Decentralized Actor-critic Algorithm In General-sum Markov Games (2024)3.58
• Independent And Decentralized Learning In Markov Potential Games (2022)0.00
• Communication-efficient Actor-critic Methods For Homogeneous Markov Games (2022)0.00
• Single-timescale Actor-critic Provably Finds Globally Optimal Policy (2020)0.00
• Independent Policy Gradient For Large-scale Markov Potential Games: Sharper Rates, Function Approximation, And Game-agnostic Convergence (2022)0.00
• Finite-time Analysis Of Single-timescale Actor-critic (2022)0.00
• Actor-critic Algorithms For Constrained Multi-agent Reinforcement Learning (2019)0.00
• Independent Learning In Constrained Markov Potential Games (2024)0.00