mlsanityData to 7 Oct 2026

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

arXiv 2012.15511 ↗First posted 31 Dec 2020cs.LG math.OCcited by 23

Not on the map. Why?

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.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 Dec 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

23 papers.

Sort:

By area:

  1. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  2. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  3. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
  4. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  5. 2023Distributed TD(0) with Almost No Communicationcited by 11
  6. 2023ReLU to the Rescue: Improve Your On-Policy Actor-Critic with Positive Advantagescited by 10
  7. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  8. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 5
  9. 2024On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representationscited by 4
  10. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  11. 2024CAESAR: Enhancing Federated RL in Heterogeneous MDPs through Convergence-Aware Sampling with Screeningcited by 2
  12. 2024MDP Geometry, Normalization and Reward Balancing Solverscited by 2
11 more
  1. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2
  2. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  3. 2024DASA: Delay-Adaptive Multi-Agent Stochastic Approximationcited by 1
  4. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  5. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1
  6. 2021Distributed TD(0) with Almost No Communicationcited by 0
  7. 2024Single-Loop Federated Actor-Critic across Heterogeneous Environmentscited by 0
  8. 2025Highly Parallelized Reinforcement Learning Training with Relaxed Assignment Dependenciescited by 0
  9. 2025In-Context Compositional Q-Learning for Offline Reinforcement Learningcited by 0
  10. 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Rewardcited by 0
  11. 2026Limiting-Kernel Q(λ): Bridging Short and Long Horizonscited by 0