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

arXiv: https://arxiv.org/abs/2109.03699 · HTML: https://mlsanity.com/paper/2109.03699/

## Key facts

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

## Builds on (most cited first, 30 of 37)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Contrasting Centralized and Decentralized Critics in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2102.04402/) (2021)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [Actor-Critic Policy Optimization in Partially Observable Multiagent Environments](https://mlsanity.com/paper/1810.09026/) (2018)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimization](https://mlsanity.com/paper/2005.07041/) (2020)
- [RMIX: Learning Risk-Sensitive Policies for Cooperative Reinforcement Learning Agents](https://mlsanity.com/paper/2102.08159/) (2021)
- [Momentum-Based Policy Gradient Methods](https://mlsanity.com/paper/2007.06680/) (2020)
- [Delay-Aware Multi-Agent Reinforcement Learning for Cooperative and Competitive Environments](https://mlsanity.com/paper/2005.05441/) (2020)
- [A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1903.06372/) (2019)
- [Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality](https://mlsanity.com/paper/2102.11866/) (2021)
- [Intelligent Electric Vehicle Charging Recommendation Based on Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2102.07359/) (2021)
- [Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms](https://mlsanity.com/paper/2011.05053/) (2020)
- [Distributed Policy Evaluation Under Multiple Behavior Strategies](https://mlsanity.com/paper/1312.7606/) (2013)
- [Sample Complexity of Policy Gradient Finding Second-Order Stationary Points](https://mlsanity.com/paper/2012.01491/) (2020)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [A Communication-Efficient Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1907.03053/) (2019)
- [Multi-Agent Fully Decentralized Value Function Learning with Linear Convergence Rates](https://mlsanity.com/paper/1810.07792/) (2018)
- [Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis](https://mlsanity.com/paper/2010.13272/) (2020)
- [Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm](https://mlsanity.com/paper/2105.14125/) (2021)
- [Distributed off-Policy Actor-Critic Reinforcement Learning with Policy Consensus](https://mlsanity.com/paper/1903.09255/) (2019)
- [Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1911.00934/) (2019)

## Built on by (most cited first, 26 of 26)

- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (2024)
- [Communication-Efficient Actor-Critic Methods for Homogeneous Markov Games](https://mlsanity.com/paper/2202.09422/) (2022)
- [Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update](https://mlsanity.com/paper/2403.15935/) (2024)
- [Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2405.03082/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [MDP Geometry, Normalization and Reward Balancing Solvers](https://mlsanity.com/paper/2407.06712/) (2024)
- [On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks](https://mlsanity.com/paper/2409.12882/) (2024)
- [Consensus-based Decentralized Multi-agent Reinforcement Learning for Random Access Network Optimization](https://mlsanity.com/paper/2508.07001/) (2025)
- [Scalable and Sample Efficient Distributed Policy Gradient Algorithms in Multi-Agent Networked Systems](https://mlsanity.com/paper/2212.06357/) (2022)
- [Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis](https://mlsanity.com/paper/2503.17454/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic](https://mlsanity.com/paper/2206.05733/) (2022)
- [Faster Adaptive Decentralized Learning Algorithms](https://mlsanity.com/paper/2408.09775/) (2024)
- [A Communication-Efficient Decentralized Actor-Critic Algorithm](https://mlsanity.com/paper/2510.19199/) (2025)
- [Multi-Agent Conditional Diffusion Model with Mean Field Communication as Wireless Resource Allocation Planner](https://mlsanity.com/paper/2510.22969/) (2025)
- [Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces](https://mlsanity.com/paper/2607.18554/) (2026)
- [Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processes](https://mlsanity.com/paper/2311.11789/) (2023)
- [Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2505.18433/) (2025)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)
- [FedCritic-MIMO: Communication-Efficient Serverless Federated Critic Learning for Massive-MIMO Resource Control in Open and Disaggregated 6G RANs](https://mlsanity.com/paper/2608.03852/) (2026)
- [A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning](https://mlsanity.com/paper/2610.14041/) (2026)

## 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.