  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 the non-asymptotic analysis and the performance gain
of parallelism (a.k.a. speedup). This paper revisits the A3C algorithm with
TD(0) for the critic update, termed A3C-TD(0), with provable convergence
guarantees. With linear value function approximation for the TD update, the
convergence of A3C-TD(0) is established under both i.i.d. and Markovian
sampling. Under i.i.d. sampling, A3C-TD(0) 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-TD(0)
achieves \emph{linear speedup}, which justifies the advantage of parallelism
and asynchrony in AC algorithms theoretically for the first time. Numerical
tests on synthetically generated instances and OpenAI Gym environments have
been provided to verify our theoretical analysis.
