Finite-time Analysis Of Fully Decentralized Single-timescale Actor-critic

Abstract

Decentralized Actor-Critic (AC) algorithms have been widely utilized for multi-agent reinforcement learning (MARL) and have achieved remarkable success. Apart from its empirical success, the theoretical convergence property of decentralized AC algorithms is largely unexplored. Most of the existing finite-time convergence results are derived based on either double-loop update or two-timescale step sizes rule, and this is the case even for centralized AC algorithm under a single-agent setting. In practice, the *single-timescale* update is widely utilized, where actor and critic are updated in an alternating manner with step sizes being of the same order. In this work, we study a decentralized *single-timescale* AC algorithm.Theoretically, using linear approximation for value and reward estimation, we show that the algorithm has sample complexity of \(\tilde\{\mathcal\{O\}\}(\epsilon^\{-2\})\) under Markovian sampling, which matches the optimal complexity with a double-loop implementation

Stats

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

Related papers

• A Finite Time Analysis Of Two Time-scale Actor Critic Methods (2020)0.00
• Finite-time Analysis Of Single-timescale Actor-critic (2022)0.00
• Global Convergence Of Two-timescale Actor-critic For Solving Linear Quadratic Regulator (2022)4.52
• Non-asymptotic Convergence Analysis Of Two Time-scale (natural) Actor-critic Algorithms (2020)0.00
• Improving Sample Complexity Bounds For (natural) Actor-critic Algorithms (2020)0.00
• Single-timescale Actor-critic Provably Finds Globally Optimal Policy (2020)0.00
• Non-asymptotic Analysis For Single-loop (natural) Actor-critic With Compatible Function Approximation (2024)0.00
• Learning To Coordinate In Multi-agent Systems: A Coordinated Actor-critic Algorithm And Finite-time Guarantees (2021)0.00