mlsanityData to 7 Oct 2026

Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis

arXiv 2109.03699 ↗First posted 8 Sep 2021cs.LGcited by 25

Not on the map. Why?

Abstract (arXiv)

Actor-critic (AC) algorithms have been widely adopted in decentralized multi-agent systems to learn the optimal joint control policy. However, existing decentralized AC algorithms either do not preserve the privacy of agents or are not sample and communication-efficient. In this work, we develop two decentralized AC and natural AC (NAC) algorithms that are private, and sample and communication-efficient. In both algorithms, agents share noisy information to preserve privacy and adopt mini-batch updates to improve sample and communication efficiency. Particularly for decentralized NAC, we develop a decentralized Markovian SGD algorithm with an adaptive mini-batch size to efficiently compute the natural policy gradient. Under Markovian sampling and linear function approximation, we prove the proposed decentralized AC and NAC algorithms achieve the state-of-the-art sample complexities Obig(ε-2ln(ε-1)big) and Obig(ε-3ln(ε-1)big), respectively, and the same small communication complexity Obig(ε-1ln(ε-1)big). Numerical experiments demonstrate that the proposed algorithms achieve lower sample and communication complexities than the existing decentralized AC algorithm.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 37 of its 78 references that are in the map. First posted on arXiv 8 Sep 2021.

Builds on

37 of 78 references.

References · 37

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  2. 2017Counterfactual Multi-Agent Policy Gradientscited by 733
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  4. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
  5. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  6. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  7. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  8. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  9. 2021Contrasting Centralized and Decentralized Critics in Multi-Agent Reinforcement Learningcited by 54
  10. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  11. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  12. 2018Actor-Critic Policy Optimization in Partially Observable Multiagent Environmentscited by 35
25 more
  1. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  2. 2020SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimizationcited by 31
  3. 2021RMIX: Learning Risk-Sensitive Policies for Cooperative Reinforcement Learning Agentscited by 31
  4. 2020Momentum-Based Policy Gradient Methodscited by 28
  5. 2019A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learningcited by 21
  6. 2020Delay-Aware Multi-Agent Reinforcement Learning for Cooperative and Competitive Environmentscited by 21
  7. 2021Intelligent Electric Vehicle Charging Recommendation Based on Multi-Agent Reinforcement Learningcited by 20
  8. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 20
  9. 2020Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithmscited by 19
  10. 2013Distributed Policy Evaluation Under Multiple Behavior Strategiescited by 17
  11. 2019A Communication-Efficient Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learningcited by 16
  12. 2020Sample Complexity of Policy Gradient Finding Second-Order Stationary Pointscited by 16
  13. 2021Bregman Gradient Policy Optimizationcited by 15
  14. 2018Multi-Agent Fully Decentralized Value Function Learning with Linear Convergence Ratescited by 13
  15. 2020Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysiscited by 12
  16. 2021Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithmcited by 12
  17. 2019Distributed off-Policy Actor-Critic Reinforcement Learning with Policy Consensuscited by 11
  18. 2019Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximationcited by 9
  19. 2021Modeling the Interaction between Agents in Cooperative Multi-Agent Reinforcement Learningcited by 7
  20. 2021Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexitycited by 5
  21. 2020A Hysteretic Q-learning Coordination Framework for Emerging Mobility Systems in Smart Citiescited by 4
  22. 2020Model Free Reinforcement Learning Algorithm for Stationary Mean field Equilibrium for Multiple Types of Agentscited by 4
  23. 2019Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulatorcited by 3
  24. 2021Distributed Reinforcement Learning for Flexible and Efficient UAV Swarm Controlcited by 3
  25. 2021Shaping Advice in Deep Multi-Agent Reinforcement Learningcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 3; 2023: 3; 2024: 7; 2025: 8; 2026: 3.

25 papers.

Sort:

By area:

  1. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  2. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  3. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  4. 2021Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guaranteescited by 6
  5. 2022Communication-Efficient Actor-Critic Methods for Homogeneous Markov Gamescited by 5
  6. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 5
  7. 2024Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learningcited by 4
  8. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  9. 2024Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD updatecited by 3
  10. 2024On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attackscited by 3
  11. 2025Consensus-based Decentralized Multi-agent Reinforcement Learning for Random Access Network Optimizationcited by 3
  12. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 3
13 more
  1. 2022Scalable and Sample Efficient Distributed Policy Gradient Algorithms in Multi-Agent Networked Systemscited by 2
  2. 2024MDP Geometry, Normalization and Reward Balancing Solverscited by 2
  3. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2
  4. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  5. 2022Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Criticcited by 1
  6. 2024Faster Adaptive Decentralized Learning Algorithmscited by 1
  7. 2025A Communication-Efficient Decentralized Actor-Critic Algorithmcited by 1
  8. 2025Multi-Agent Conditional Diffusion Model with Mean Field Communication as Wireless Resource Allocation Plannercited by 1
  9. 2023Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processescited by 0
  10. 2025Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learningcited by 0
  11. 2026Multi-Agent Reinforcement Learning with Submodular Rewardcited by 0
  12. 2026Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spacescited by 0
  13. 2026FedCritic-MIMO: Communication-Efficient Serverless Federated Critic Learning for Massive-MIMO Resource Control in Open and Disaggregated 6G RANscited by 0