  To improve the efficiency of reinforcement learning, we propose a novel
asynchronous federated reinforcement learning framework termed AFedPG, which
constructs a global model through collaboration among $N$ agents using policy
gradient (PG) updates. To handle the challenge of lagged policies in
asynchronous settings, we design delay-adaptive lookahead and normalized update
techniques that can effectively handle the heterogeneous arrival times of
policy gradients. We analyze the theoretical global convergence bound of
AFedPG, and characterize the advantage of the proposed algorithm in terms of
both the sample complexity and time complexity. Specifically, our AFedPG method
achieves $\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$ sample complexity at each
agent on average. Compared to the single agent setting with
$\mathcal{O}(\epsilon^{-2.5})$ sample complexity, it enjoys a linear speedup
with respect to the number of agents. Moreover, compared to synchronous FedPG,
AFedPG improves the time complexity from $\mathcal{O}(\frac{t_{\max}}{N})$ to
$\mathcal{O}(\frac{1}{\sum_{i=1}^{N} \frac{1}{t_{i}}})$, where $t_{i}$ denotes
the time consumption in each iteration at the agent $i$, and $t_{\max}$ is the
largest one. The latter complexity $\mathcal{O}(\frac{1}{\sum_{i=1}^{N}
\frac{1}{t_{i}}})$ is always smaller than the former one, and this improvement
becomes significant in large-scale federated settings with heterogeneous
computing powers ($t_{\max}\gg t_{\min}$). Finally, we empirically verify the
improved performances of AFedPG in three MuJoCo environments with varying
numbers of agents. We also demonstrate the improvements with different
computing heterogeneity.
