Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
Authors:
- Han ShenHSHan Shen
- Kaiqing ZhangKZKaiqing Zhang
- Mingyi HongMHMingyi Hong
- Tianyi ChenTCTianyi Chen
Preprint
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 $\mathcal{O}(\epsilon^{-2.5}/N)$ per worker to achieve $\epsilon$ accuracy, where $N$ is the number of workers. Compared to the best-known sample complexity of $\mathcal{O}(\epsilon^{-2.5})$ 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.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- On the sample complexity of actor-critic method for reinforcement learning with function approximationMachine Learning, 2023
- Policy Gradient Importance Sampling for Bayesian InferenceIEEE Transactions on Signal Processing, 2021
- Byzantine-Resilient Decentralized Policy Evaluation With Linear Function ApproximationIEEE Transactions on Signal Processing, 2021
- Online Trajectory and Radio Resource Optimization of Cache-Enabled UAV Wireless Networks With Content and Energy RechargingIEEE Transactions on Signal Processing, 2020
- Joint Rate and Power Optimization for Multimedia Streaming in Wireless Fading Channels via Parametric Policy GradientIEEE Transactions on Signal Processing, 2019
- Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-Time PopularitiesIEEE Journal of Selected Topics in Signal Processing, 2017
- Decentralized Consensus Optimization With Asynchrony and DelaysIEEE Transactions on Signal and Information Processing over Networks, 2017
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic OptimizationIEEE Transactions on Automatic Control, 2016
- Natural actor–critic algorithmsAutomatica, 2009
- The actor-critic algorithm as multi-time-scale stochastic approximationSādhanā, 1997