# Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Dec 2020.

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

- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis](https://mlsanity.com/paper/2404.08003/) (2024)
- [Distributed TD(0) with Almost No Communication](https://mlsanity.com/paper/2305.16246/) (2023)
- [ReLU to the Rescue: Improve Your On-Policy Actor-Critic with Positive Advantages](https://mlsanity.com/paper/2306.01460/) (2023)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (2024)
- [On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representations](https://mlsanity.com/paper/2411.15014/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [MDP Geometry, Normalization and Reward Balancing Solvers](https://mlsanity.com/paper/2407.06712/) (2024)
- [DASA: Delay-Adaptive Multi-Agent Stochastic Approximation](https://mlsanity.com/paper/2403.17247/) (2024)
- [CAESAR: Enhancing Federated RL in Heterogeneous MDPs through Convergence-Aware Sampling with Screening](https://mlsanity.com/paper/2403.20156/) (2024)
- [Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis](https://mlsanity.com/paper/2503.17454/) (2025)
- [Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling](https://mlsanity.com/paper/2504.11645/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Finite-time Convergence Analysis of Actor-Critic with Evolving Reward](https://mlsanity.com/paper/2510.12334/) (2025)
- [Asynchronous Parallel Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/2407.03233/) (2024)
- [In-Context Compositional Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2509.24067/) (2025)
- [Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environments](https://mlsanity.com/paper/2510.07436/) (2025)
- [Distributed TD(0) with Almost No Communication](https://mlsanity.com/paper/2104.07855/) (2021)
- [Single-Loop Federated Actor-Critic across Heterogeneous Environments](https://mlsanity.com/paper/2412.14555/) (2024)
- [Highly Parallelized Reinforcement Learning Training with Relaxed Assignment Dependencies](https://mlsanity.com/paper/2502.20190/) (2025)
- [Limiting-Kernel Q(λ): Bridging Short and Long Horizons](https://mlsanity.com/paper/2609.27741/) (2026)
- [Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning](https://mlsanity.com/paper/2610.06918/) (2026)

## Abstract (arXiv)

Asynchronous and parallel implementation of standard reinforcement learning (RL) algorithms is a key enabler of the tremendous success of modern RL. Among many asynchronous RL algorithms, arguably the most popular and effective one is the asynchronous advantage actor-critic (A3C) algorithm. Although A3C is becoming the workhorse of RL, its theoretical properties are still not well-understood, including its non-asymptotic analysis and the performance gain of parallelism (a.k.a. linear speedup). This paper revisits the A3C algorithm and establishes its non-asymptotic convergence guarantees. Under both i.i.d. and Markovian sampling, we establish the local convergence guarantee for A3C in the general policy approximation case and the global convergence guarantee in softmax policy parameterization. Under i.i.d. sampling, A3C obtains sample complexity of O(ε-2.5/N) per worker to achieve ε accuracy, where N is the number of workers. Compared to the best-known sample complexity of O(ε-2.5) for two-timescale AC, A3C achieves linear speedup, which justifies the advantage of parallelism and asynchrony in AC algorithms theoretically for the first time. Numerical tests on synthetic environment, OpenAI Gym environments and Atari games have been provided to verify our theoretical analysis.