# Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 49 references that are in the map.
- First posted on arXiv 12 Jun 2022.

## Builds on (most cited first, 26 of 26)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Emergence of Grounded Compositional Language in Multi-Agent Populations](https://mlsanity.com/paper/1703.04908/) (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)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/1703.06182/) (2017)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [Bi-level Actor-Critic for Multi-agent Coordination](https://mlsanity.com/paper/1909.03510/) (2019)
- [Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy](https://mlsanity.com/paper/2008.00483/) (2020)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality](https://mlsanity.com/paper/2102.11866/) (2021)
- [Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms](https://mlsanity.com/paper/2011.05053/) (2020)
- [A Communication-Efficient Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1907.03053/) (2019)
- [Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1911.00934/) (2019)
- [Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation](https://mlsanity.com/paper/2104.02836/) (2021)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity](https://mlsanity.com/paper/2103.13147/) (2021)

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

- [A Communication-Efficient Decentralized Actor-Critic Algorithm](https://mlsanity.com/paper/2510.19199/) (2025)

## Abstract (arXiv)

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 tildeO(varepsilon-2) under Markovian sampling, which matches the optimal complexity with a double-loop implementation (here, tildeO hides a logarithmic term). When we reduce to the single-agent setting, our result yields new sample complexity for centralized AC using a single-timescale update scheme. The central to establishing our complexity results is the hidden smoothness of the optimal critic variable we revealed. We also provide a local action privacy-preserving version of our algorithm and its analysis. Finally, we conduct experiments to show the superiority of our algorithm over the existing decentralized AC algorithms.