Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
arXiv:2012.15511 · doi:10.1109/TSP.2023.3268475
Abstract
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 per worker to achieve accuracy, where is the number of workers. Compared to the best-known sample complexity of for two-timescale AC, A3C achieves \emph{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.
References in corpus (16)
- Continuous control with deep reinforcement learning
- Massively Parallel Methods for Deep Reinforcement Learning
- Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
- Infinite-Horizon Policy-Gradient Estimation
- Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
- Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-time Popularities
- -Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations
- Accelerated Methods for Deep Reinforcement Learning
- Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
- On the Global Convergence Rates of Softmax Policy Gradient Methods
- A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
- Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
- Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward
- Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
- Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation
- Gossip-based Actor-Learner Architectures for Deep Reinforcement Learning