# Asynchronous Federated Reinforcement Learning with Policy Gradient Updates:
Algorithm Design and Convergence Analysis

Guangchen Lan, Dong-Jun Han, Abolfazl Hashemi, Vaneet Aggarwal, Christopher G.
Brinton
Purdue University, West Lafayette, IN, USA
{lan44, han762, abolfazl, vaneet<EMAIL_ADDRESS>
(2024; 8 April 2024)

###### Abstract.

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. 111The
Technical Report with proof details is available on arXiv (Lan et al., 2024).

Reinforcement Learning, Policy Gradient, Federated Learning, Asynchronous,
Optimization

††copyright: acmlicensed††journalyear: 2024††doi: XXXXXXX.XXXXXXX††conference:
International Symposium on Theory, Algorithmic Foundations, and Protocol
Design for Mobile Networks and Mobile Computing; October 14–17, 2024; Athens,
Greece††isbn: 978-1-4503-XXXX-X/18/06††ccs: Computing methodologies Machine
learning††ccs: Computing methodologies Artificial intelligence Distributed
artificial intelligence††ccs: Computer systems organization Distributed
architectures††ccs: Networks Network services

##  1\. Introduction

Policy gradient (PG) methods, also known as REINFORCE (Williams, 1992), are
widely used to solve reinforcement learning (RL) problems across a range of
applications, with recent notable examples including reinforcement learning
from human feedback (RLHF) in Google’s Gemma (Team and DeepMind, 2024),
OpenAI’s InstructGPT (Ouyang et al., 2022), and ChatGPT (GPT-4 (OpenAI,
2023)). It has also garnered significant attention in networking and
communication communities for solving network optimization problems, e.g.,
scheduling (Wei et al., 2023) and queueing (Hu et al., 2022), and solving
wireless communication problems, e.g., wireless video streaming (Yu et al.,
2023), MAC design (Moon et al., 2021) and metaverse latency optimization
(Xiong et al., 2022).

Most practical RL applications are on large scales and rely on a huge amount
of data samples for model training in an online behavior (Provost and Fawcett,
2013; Liu et al., 2021), which is considered as the key bottleneck of RL
(Dulac-Arnold et al., 2021; Ladosz et al., 2022). To reduce sample complexity
while enabling training on massive data, a conventional approach involves
transmitting locally collected samples from distributed agents to a central
server (Predd et al., 2006). The transmitted samples can then be used for
policy learning on the server side. However, this may not be feasible in real-
world mobile systems where the communication bandwidth is limited and a large
training time is intolerable (Hu et al., 2024; Lan et al., 2023a; Niknam et
al., 2020), such as wireless edge devices (Han et al., 2023; Lan et al.,
2023a), Internet of Things (Nguyen et al., 2021; Fang et al., 2023),
autonomous driving (Kiran et al., 2022), and vehicle transportation (Al-Abbasi
et al., 2019; Haliem et al., 2021). In RL, since new data is continuously
generated based on the current policy, the samples collected at the agents
need to be transmitted frequently to the server throughout the training
process, resulting in a significant bottleneck with large delays. Furthermore,
the sharing of individual data collected by agents may lead to privacy and
legal issues (Kairouz et al., 2021; Mothukuri et al., 2021).

Federated learning (FL) (Hosseinalipour et al., 2020; McMahan et al., 2017)
offers a promising solution to the above challenges in a distributed setting.
In FL, instead of directly transmitting the raw datasets to the central
server, agents only communicate locally trained model parameters (or
gradients) with the server. Although FL has been mostly studied for supervised
learning problems, several recent works expanded the scope of FL to federated
reinforcement learning (FedRL), where $N$ agents collaboratively learn a
global policy without sharing the trajectories they collected during agent-
environment interaction (Jin et al., 2022; Khodadadian et al., 2022; Xie and
Song, 2023). FedRL has been studied in the tabular case (Agarwal et al.,
2021a; Jin et al., 2022; Khodadadian et al., 2022), and for value-function
based algorithms (Wang et al., 2023; Xie and Song, 2023), where a linear
speedup has been demonstrated. For policy-gradient based algorithms, namely
FedPG, we note that linear speedup is easy to see as the trajectories
collected by each agent could be parallelized (Lan et al., 2023b). However,
policy-gradient based FedRL has not been well studied in terms of global (non-
local) convergence and time complexity.

Despite all the aforementioned works in FedRL, they still face challenges in
terms of time complexity, primarily due to their focus on synchronous model
aggregation. In large-scale heterogeneous settings (Xie et al., 2020; Chen et
al., 2020), performing synchronous global updates has limitations, as the
overall time consumption heavily depends on the slow agents, i.e., stragglers
(Mishchenko et al., 2022). In this paper, we aim to tackle this issue by
strategically leveraging asynchronous federated learning (A-FL) in policy-
based FedRL for the first time. A-FL (Xie et al., 2020) shows superiority
compared to synchronous FL, and recent works (Mishchenko et al., 2022;
Koloskova et al., 2022) further improve convergence performances with
theoretical guarantees. However, compared to prior A-FL approaches focusing on
supervised learning, integrating A-FL with policy-based FedRL introduces new
challenges due to the presence of lagged policies in asynchronous settings.
Unlike supervised FL where the datasets of the clients are fixed, in RL,
agents collect new samples in each iteration based on the current policy. This
dynamic nature of the data collection process makes both the problem itself
and the theoretical analysis challenging. To the best of our knowledge, this
problem setting and its challenges have been largely overlooked in existing
research, despite the significance of employing FL in RL. The key question
that this paper aims to address is:

Table 1. Performance improvements of our AFedPG over other policy gradient methods. We compare the complexity for global convergence in each agent. | PG | FedPG | AFedPG (ours)
---|---|---|---
Sample Complexity | $\mathcal{O}({\epsilon}^{-2.5})$ | $\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$ | $\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$
Global Time | - | $\mathcal{O}(\frac{t_{\max}}{N}{\epsilon}^{-2.5})$ | $\mathcal{O}(\bar{t}{\epsilon}^{-2.5})$

Despite the inherent challenge of dealing with lagged policies among different
agents, can we improve the efficiency of FedPG through asynchronous methods
while ensuring theoretical convergence?

We answer this question in the affirmative by proposing AFedPG, an algorithm
that asynchronously updates the global policy using policy gradients from
federated agents. The key components of the proposed AFedPG include a delay-
adaptive lookahead technique, which addresses the inconsistent arrival times
of updates during the training process. The improvement of AFedPG over other
approaches is summarized in Table 1. Here, the global time is measured by the
number of global updates $\times$ time complexity in each iteration. In terms
of sample complexity, the federated learning technique brings a linear speedup
with respect to the number of agents $N$. As for the global time, AFedPG
improves from $\mathcal{O}(\frac{t_{\max}}{N}{\epsilon}^{-2.5})$ to
$\mathcal{O}(\bar{t}{\epsilon}^{-2.5})$, where $\bar{t}\coloneqq
1/\sum_{i=1}^{N}\frac{1}{t_{i}}$ is a harmonic average and always smaller than
$t_{\max}/N$, and $t_{i}$ denotes the time complexity in each iteration at
agent $i$.

###  1.1. Summary of Contributions

Our main contributions can be summarized as follows:

  1. (1)

New methodology with a delay-adaptive technique: We propose AFedPG, an
asynchronous training method tailored to FedRL. To handle the delay issue in
the asynchronous FedRL setting, we design a delay-adaptive lookahead
technique. Specifically, in the $k$-th iteration of training, the agent
collects samples according to the local model parameters
$\widetilde{\theta}_{k}\leftarrow\theta_{k}+\frac{1-\alpha_{k-\delta_{k}}}{\alpha_{k-\delta_{k}}}(\theta_{k}-\theta_{k-1})$,
where $\delta_{k}$ is the delay. This updating technique cancels out the
second-order correction terms and thus assists the convergence analysis.

  2. (2)

Convergence analysis: This work gives the global convergence guarantees of the
federated policy-based RL for the first time. We analytically characterize the
convergence bound of AFedPG using the key lemmas, and show the impact of
various parameters including delay and number of iterations in our analysis.

  3. (3)

Linear speedup in sample complexity: As shown in Table 1, our federated method
improves the sample complexity in each agent from
$\mathcal{O}({\epsilon}^{-2.5})$ (single agent PG) to
$\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$, where $N$ is the number of
federated agents. This represents the linear speedup with respect to the
number of agents $N$.

  4. (4)

Time complexity improvement: Our AFedPG also reduces the time complexity of
synchronous FedPG from $\mathcal{O}(\frac{t_{\max}}{N})$ to
$\mathcal{O}(\bar{t}\coloneqq\frac{1}{\sum_{i=1}^{N}\frac{1}{t_{i}}})$. The
latter is always smaller than the former. This gap is significant in large-
scale federated settings with heterogeneous computing powers ($t_{\max}\gg
t_{\min}$).

  5. (5)

Experiments under MuJoCo environment: We empirically verify the improved
performances of AFedPG in three different MuJoCo environments with varying
numbers of agents. We also demonstrate the improvements with different
computing heterogeneity.

To the best of our knowledge, this is the first work to successfully integrate
policy-based reinforcement learning with asynchronous federated learning and
analyze its behavior. This new setting necessitates us to deal with the lagged
policies under a time-varying data scenario depending on the current policy.

Notation: We denote the Euclidean norm by $\|\cdot\|$, and the vector inner
product by $\langle\cdot\rangle$. For a vector $a\in\mathbb{R}^{n}$, we use
$a^{\top}$ to denote the transpose of $a$. A calligraphic font letter denotes
a set, e.g., $\mathcal{C}$, and $|\mathcal{C}|$ denotes its cardinality. We
use $\mathcal{C}\setminus\\{j\\}$ to denote a set that contains all the
elements in $\mathcal{C}$ except for $j$.

The remainder of this paper is organized as follows. In the next subsection,
we summarize the related works. In Section 2, we introduce our problem
setting, including some backgrounds on reinforcement learning and policy
gradients. In Section 3, we describe our proposed AFedPG method. In Section 4,
we analyze the global convergence rate of AFedPG and discuss its time
complexity compared to the synchronous setting. Section 5 presents the
experimental results, and we conclude this paper in Section 6.

###  1.2. Related Work

In this subsection, we review previous works that are most relevant to the
present work.

Policy gradient methods: For vanilla PG, the state-of-the-art result is
presented in (Yuan et al., 2022), achieving a sample complexity of
$\widetilde{\mathcal{O}}({\epsilon}^{-4})$ for the local convergence. Several
recent works have improved this boundary with PG variants. In (Huang et al.,
2020), a PG with momentum method is proposed with convergence rate
$\mathcal{O}({\epsilon}^{-3})$ for the local convergence. The authors of (Ding
et al., 2022) further improve the convergence analysis of PG with momentum and
achieve a global convergence with the rate $\mathcal{O}({\epsilon}^{-3})$. In
(Fatkhullin et al., 2023), a normalized PG technique is introduced and
improves the global convergence rate to $\mathcal{O}({\epsilon}^{-2.5})$. In
(Mondal and Aggarwal, 2024), an acceleration-based natural policy gradient
method is proposed with sample complexity $\mathcal{O}({\epsilon}^{-2})$, but
second-order matrices are computed in each iteration (with first-order
information), which brings more computational cost. However, all previous
works have focused on the single-agent scenario, and the federated PG has not
been explored. Compared to these works, we focus on a practical federated PG
setting with distributed agents to improve the efficiency of RL. Our scheme
achieves linear speedup with respect to the number of agents, significantly
reducing the sample complexity compared to the conventional PG approaches.

Asynchronous FL: In (Xie et al., 2020), the superiority of asynchronous
federated learning (A-FL) has been empirically shown compared to synchronous
FL in terms of convergence performances. In (Chen et al., 2020), the
asynchronous analysis is extended to the vertical FL with a better convergence
performance compared to the synchronous setting. In (Dun et al., 2023), a
dropout regularization method is introduced to handle the heterogeneous
problems in A-FL. About the same time, recent works (Mishchenko et al., 2022;
Koloskova et al., 2022) further improve the convergence performance with
theoretical guarantees, and show that A-FL always exceeds synchronous FL
without any changes to the algorithm. We note that all previous A-FL works
focus on supervised learning with fixed datasets on the client side. However,
in RL, agents collect new samples that depend on the current policy (model
parameters) in each iteration, which makes the problem fundamentally different
and challenging. In this work, we address this challenge by developing an A-FL
method highly tailored to policy gradient.

FedRL: For value-function based algorithms, (Jin et al., 2022) analyzes the
convergence performances with environment heterogeneity. In (Agarwal et al.,
2021a), a local update method is used to reduce communication costs.
(Khodadadian et al., 2022) shows a linear speedup with respect to the number
of agents. All of the above works are limited to tabular RL analysis. For
actor-critic based method, (Wang et al., 2023) analyzes the convergence
performances with linear function approximation. (Mnih et al., 2016) builds a
practical system to implement the neural network approximation. In (Xie and
Song, 2023), it adds KL divergence and experimentally validates the actor-
critic based method with neural network approximation. For policy-based
methods, in (Lan et al., 2023b), it shows simplicity compared to the other RL
methods, and a linear speedup has been demonstrated in the synchronous
setting. However, with an online behavior, it is not practical to perform
synchronous global updates with heterogeneous computing power, and the global
time consumption heavily depends on the stragglers (Mishchenko et al., 2022).
This motivates us to consider the asynchronous policy-based method for FedRL.
We demonstrate both theoretically and empirically that our method further
reduces the time complexity compared to the synchronous FedRL approach.

##  2\. Problem Setup

Markov decision process: We consider the Markov decision process (MDP) as a
tuple $(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$, where
$\mathcal{S}$ is the state space, $\mathcal{A}$ is a finite action space,
$\mathcal{P}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$
is a Markov kernel that determines transition probabilities,
$\mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is a reward
function, and $\gamma\in(0,1)$ is a discount factor. At each time step $t$,
the agent executes an action $a_{t}\in\mathcal{A}$ from the current state
$s_{t}\in\mathcal{S}$, following a stochastic policy $\pi$, i.e.,
$a_{t}\sim\pi(\cdot|s_{t})$. The corresponding reward is defined as $r_{t}$.
The state value function is defined as

(1) $V_{\pi}(s)=\mathop{\mathbb{E}}_{a_{t}\sim\pi(\cdot|s_{t}),\atop
s_{t+1}\sim
P(\cdot|s_{t},a_{t})}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s\right].$

Similarly, the state-action value function (Q-function) is defined as

(2) $Q_{\pi}(s,a)=\mathop{\mathbb{E}}_{a_{t}\sim\pi(\cdot|s_{t}),\atop
s_{t+1}\sim
P(\cdot|s_{t},a_{t})}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,~{}a_{0}=a\right].$

An advantage function is then define as
$A_{\pi}(s,a)=Q_{\pi}(s,a)-V_{\pi}(s)$. With continuous states, the policy is
parameterized by $\theta\in\mathbb{R}^{d}$, and then the policy is referred as
$\pi_{\theta}$ (Deep RL parameterizes $\pi_{\theta}$ by deep neural networks).
A state-action visitation measure induced by $\pi_{\theta}$ is given as

(3)
$\nu_{\pi_{\theta}}(s,a)=(1-\gamma)\mathop{\mathbb{E}}_{s_{0}\sim\rho}\left[\sum_{t=0}^{\infty}\gamma^{t}P(s_{t}=s,~{}a_{t}=a|s_{0},~{}\pi_{\theta})\right],$

where the starting state $s_{0}$ is drawn from a distribution $\rho$. The goal
of the agent is to maximize the expected discounted return defined as follows:

(4)
$\max_{\theta}J(\theta)\coloneqq\mathop{\mathbb{E}}_{s\sim\rho}\left[V_{\pi_{\theta}}(s)\right].$

The gradient of $J(\theta)$ can be written as (Schulman et al., 2018):

(5)
$\nabla_{\theta}J(\theta)=\mathop{\mathbb{E}}_{\tau}\left[\sum_{t=0}^{\infty}\nabla_{\theta}\log\pi_{\theta}(a_{t}|s_{t})\cdot
A_{\pi_{\theta}}(s_{t},a_{t})\right],$

where $\tau=(s_{0},a_{0},r_{0},s_{1},a_{1},r_{1}\cdots)$ is a trajectory
induced by policy $\pi_{\theta}$. We omit the $\theta$ notation in the
gradient operation and denote the policy gradient by $g$ for short. Then, $g$
is estimated by

(6)
$g(\theta,\tau)=\sum_{t=0}^{\infty}\nabla\log\pi_{\theta}(a_{t}|s_{t})\sum_{h=t}^{\infty}\gamma^{h}r(s_{h},a_{h}).$

Federated policy gradient: We aim to solve the above problem in an FL setting,
where $N$ agents collaboratively train a common policy $\pi_{\theta}$.
Specifically, each agent collects trajectories and corresponding reward
$r(s_{h},a_{h})$ based on its local policy. Then, each agent $i$ estimates
$g(\theta_{i},\tau)$ for training the model $\theta$, and the updated models
are aggregated at the server. Motivated by the limitations of synchronous
model aggregation in terms of time complexity, in the next section, we present
our AFedPG methodology that takes an asynchronous approach to solve (4) in a
FL setting.

##  3\. Proposed Asynchronous FedPG

Figure 1. An illustration of the asynchronous federated policy gradient
updates. Each agent has a local copy of the environment, and agents may
collect data according to different local policies. At each iteration, the
agent in the yellow color finishes the local process and then communicates
with the server, while the other agents keep sampling and computing local
gradients in parallel. In the $k$-th global iteration,
$\delta_{k}\in\mathbb{N}$ is the delay, $\widetilde{\tau}_{k-\delta_{k}}$ is
the sample collected according to the policy
$\pi_{\widetilde{\theta}_{k-\delta_{k}}}$, and $d_{k-\delta_{k}}$ is the
updating direction calculated from the sample
$\widetilde{\tau}_{k-\delta_{k}}$.

The proposed algorithm consists of $K$ global iterations, indexed by
$k=0,1,\dots,K-1$. We first introduce the definition of concurrency and delay
in our asynchronous federated setting. We then present the proposed AFedPG
methodology.

###### Definition 3.1.

(Concurrency) We denote $\mathcal{C}_{k}$ as the set of active agents in the
$k$-th global iteration, and define $\omega_{k}\coloneqq|\mathcal{C}_{k}|$ as
the concurrency. We define the average and maximum concurrency as
$\bar{\omega}\coloneqq\frac{1}{K}\sum_{k=0}^{K-1}\omega_{k}$, and
$\omega_{\max}\coloneqq\max\omega_{k}$, respectively.

In each global iteration of AFedPG, the server applies only one gradient to
update the model from the agent who has finished its local computation, while
the other $N-1$ agents keep computing local gradients (unapplied gradients) in
parallel. In this asynchronous setting, the models used in each agent are
outdated, as the server keeps updating the model. Thus, we introduce the
notion of delay (or staleness) $\delta\in\mathbb{N}$, which measures the
difference between the current global iteration and the past global iteration
when the agent received the updated model from the server.

###### Definition 3.2.

(Delay) In the $k$-th global iteration, we denote the delay of the applied
gradient as $\delta_{k}\in\mathbb{N}$, and the delays of the unapplied
gradients as $\\{\delta_{k}^{i}\\}_{i\in\mathcal{C}_{k}\setminus\\{j_{k}\\}}$,
where $j_{k}$ denotes the agent that communicates with the server.
$\delta_{k}^{i}$ is the difference between the $k$-th iteration and the
iteration where the agent $i$ started to compute the latest gradient. In the
final $K$-th global iteration, we have $K$ applied gradients
$\\{\delta_{k}\\}_{k=0}^{K-1}$ and unapplied gradients
$\\{\delta_{k}^{i}\\}_{i\in\mathcal{C}_{K}\setminus\\{j_{K}\\}}$. The average
and maximum delays can be expressed as

(7)
$\displaystyle\bar{\delta}~{}\coloneqq~{}\frac{1}{K-1+|\mathcal{C}_{K}|}\big{(}\sum_{k=0}^{K-1}\delta_{k}+\sum_{i\in\mathcal{C}_{K}\setminus\\{j_{K}\\}}\delta_{K}^{i}\big{)},$

and
$\delta_{\max}\coloneqq\max(\max_{k}\delta_{k},\max_{i\in\mathcal{C}_{K}}\delta_{K}^{i})$,
respectively.

Asynchronous FedPG: Our goal is to train a global policy with parameters
$\theta\in\mathbb{R}^{d}$ via FL across $N$ distributed agents. As shown in
Figure 1, during the training process, agent $i$ collects trajectories in an
online behavior, and computes gradients or updating directions using its local
trajectories (also known as samples). Then, agent $i$ transmits local
gradients to the central server. In particular, in the $k$-th global
iteration, the training of our AFedPG consists of the following three steps:

  * •

Local computation and uplink transmission: Agent $i$ receives the previous
policy $\pi_{\theta_{j}}$ from the server in the $j$-th global iteration.
Agent $i$ collects its own local trajectory $\tau_{j}$ based on its current
policy $\pi_{\theta_{j}}$. Agent $i$ then computes its local updating
direction $d_{j}\in\mathbb{R}^{d}$ based on the trajectory $\tau_{j}$, and
sends it back to the server.

  * •

Server-side model update: The server starts to operate the $k$-th global
iteration as soon as it receives $d_{j}$ from agent $i$. Thus, denote
$d_{k-\delta_{k}}=d_{j}$, where $\delta_{k}$ is the delay in the $k$-th global
iteration. The server updates global policy parameters by
$\theta\leftarrow\theta-\eta d_{k-\delta_{k}}$, where $\eta$ is the learning
rate.

  * •

Downlink transmission: The server transmits the current global policy
parameters $\theta\in\mathbb{R}^{d}$ back to agent $i$ as soon as it finishes
the global update.

The server side procedure of AFedPG is shown in Algorithm 1 and the process at
the agent side is shown in Algorithm 2. In the $k$-th global iteration, the
server operates one global update (Steps 4 and 5) as soon as it receives a
direction $d_{k-\delta_{k}}$ from an agent with delay $\delta_{k}$. After the
global update, the server sends the updated model back to that agent. In
Algorithm 2, after receiving the global model from the server, an agent first
gets model parameters $\widetilde{\theta}_{k}$ according to Step 2, and then
collects samples based on the policy $\pi_{\widetilde{\theta}_{k}}$ (Steps 3).
At last, the agent computes the updating direction $d_{k}$, and sends it to
the server as soon as it finishes the local process. Overall, all agents
conduct local computation in parallel, but the global model is updated in an
asynchronous manner as summarized in Figure 1.

Normalized update at the server: In Step 5 of Algorithm 1, to handle the
updates with various delays, we use normalized gradients with controllable
sizes. Specifically, the error term $\|e_{k}\|$ in Lemma 4.6 is related to
$\|\nabla J(\widetilde{\theta}_{k-\delta_{k}})-\nabla
J(\widetilde{\theta}_{k})\|$ and $\|\nabla J(\theta_{k-1})-\nabla
J(\theta_{k})\|$. With the smoothness in Lemma 4.4, we are able to bound the
error as $\|\theta_{k-1}-\theta_{k}\|=\eta_{k-1}$. The details of the
boundaries are shown in (34).

Delay-adaptive lookahead at the agent: In Step 2 of Algorithm 2 (in blue), we
design a delay-adaptive lookahead update technique, which operates as follows:

(8)
${\theta}_{k}=(1-\alpha_{k-\delta_{k}}){\theta}_{k-1}+\alpha_{k-\delta_{k}}\widetilde{\theta}_{k}.$

We note that (8) is not the conventional momentum method, because the orders
are different. Here, $\widetilde{\theta}_{k}$ ”looks ahead” based on
${\theta}_{k-1}$ and ${\theta}_{k}$, and the learning rate
$\alpha_{k-\delta_{k}}$ depends on the delay $\delta_{k}$.

In (8), the agent collects samples according to the current parameter
$\widetilde{\theta}_{k}$ in an online behavior, which only happens in the RL
setting. This makes the problem fundamentally different from the conventional
FL on supervised learning with a fixed dataset. This mechanism cancels out the
second-order Hessian correction terms:

(9)
$(1-\alpha_{k-\delta_{k}})\nabla^{2}J(\theta_{k})(\theta_{k-1}-\theta_{k})+\alpha_{k-\delta_{k}}\nabla^{2}J(\theta_{k})(\widetilde{\theta}_{k}-\theta_{k})\rightarrow
0,$

and thus assists the convergence analysis. The details are shown in Appendix
A.2 in the Technical Report (Lan et al., 2024).

Algorithm 1 AFedPG: Server.

0: MDP $(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$; Number of
iterations $K$; Step size $\eta_{k}$, $\alpha_{k}$; Initial
$\theta_{0}\in\mathbb{R}^{d}$.

1: Broadcast $\theta_{0}$ to $N$ agents.

2: for $k=0,\cdots,K$ do

3: $\rhd$ Server update

4: Receive $d_{k-\delta_{k}}$ from the agent $i_{k}$.

5:
$\theta_{k+1}\leftarrow\theta_{k}+\eta_{k}\frac{d_{k-\delta_{k}}}{\|d_{k-\delta_{k}}\|}$

6: $\rhd$ Server broadcast

7: Transmit $\theta_{k+1}$ back to the agent $i_{k}$.

8: end for

8: ${\theta^{K+1}}$

Algorithm 2 AFedPG: Agent $i$ Update, $i=1,\cdots,N$.

0: $\theta_{k}\in\mathbb{R}^{d}$

1: Receive $\theta_{k}$ from the server.

2:
$\widetilde{\theta}_{k}\leftarrow\theta_{k}+\frac{1-\alpha_{k-\delta_{k}}}{\alpha_{k-\delta_{k}}}(\theta_{k}-\theta_{k-1})$

3: $\widetilde{\tau}_{k}\sim p(\cdot|\pi_{\widetilde{\theta}_{k}})$

4:
$d_{k}\leftarrow(1-\alpha_{k})d_{k-1}+\alpha_{k}g(\widetilde{\tau}_{k},\widetilde{\theta}_{k})$

5: When finish computing, transmit ${d}_{k}$ to the server.

5: ${d}_{k}$

##  4\. Convergence Analysis

In this section, we derive the convergence rate of AFedPG with the following
criteria for the global convergence.

Criteria: In this work, we focus on the global convergence, i.e., finding the
parameter $\theta$ s.t. $J^{\star}-J(\theta)\leq\epsilon^{\prime}$, where
$J^{\star}$ is the optimal expected return.

###  4.1. Assumptions

In order to derive the global convergence rates, we make the following
standard assumptions (Agarwal et al., 2021b; Ding et al., 2020; Liu et al.,
2020; Papini et al., 2018; Xu et al., 2020) on policy gradients, and rewards.

###### Assumption 4.1.

  1. (1)

The score function is bounded as $\left\|\nabla\log\pi_{\theta}(a\mid
s)\right\|\leq M_{g}$, $\text{ for all }\theta\in\mathbb{R}^{d}$,
$s\in\mathcal{S}$, and $a\in\mathcal{A}$.

  2. (2)

The score function is $M_{h}$-Lipschitz continuous. In other words,
$\forall~{}\theta_{i},~{}\theta_{j}\in\mathbb{R}^{d},~{}s\in\mathcal{S},~{}\text{and}~{}a\in\mathcal{A}$,
we have

(10) $\displaystyle\left\|\nabla\log\pi_{\theta_{i}}(a\mid
s)-\nabla\log\pi_{\theta_{j}}(a\mid s)\right\|$ $\displaystyle\leq
M_{h}\left\|\theta_{i}-\theta_{j}\right\|.$

  3. (3)

The reward function is bounded as $r(s,a)\in[0,R],\text{ for all
}s\in\mathcal{S}$, and $a\in\mathcal{A}$.

These standard assumptions naturally state the reward, first-order and second-
order derivatives of the score function are not infinite, and they hold with
common practical parametrization methods, e.g., softmax policies. With
function approximation $\pi_{\theta}$, the approximation error may not be $0$
in practice. Thus, we follow previous works (Liu et al., 2020; Agarwal et al.,
2021b; Ding et al., 2022; Huang et al., 2020) with an assumption on the
expressivity of the policy parameterization class.

###### Assumption 4.2.

(Function approximation) $\exists~{}\epsilon_{bias}\geq 0$ s.t. for
$\forall~{}\theta\in\mathbb{R}^{d}$, the transfer error satisfies

(11)
$\mathbb{E}[\big{(}A_{\pi_{\theta}}(s,a)-(1-\gamma)u^{\star}(\theta)^{\top}\nabla\log\pi_{\theta}(a\mid
s)\big{)}^{2}]\leq\epsilon_{bias},$

where $u^{\star}(\theta)\coloneqq F_{\rho}(\theta)^{\dagger}\nabla J(\theta)$,
and $F_{\rho}(\theta)^{\dagger}$ is the Moore-Penrose pseudo-inverse of the
Fisher matrix $F_{\rho}$.

It means that the parameterized policy $\pi_{\theta}$ makes the advantage
function $A_{\pi_{\theta}}(s,a)$ approximated by the score function
$\nabla\log\pi_{\theta}(a\mid s)$ as the features. This assumption is widely
used with Fisher-non-degenerate parameterization. $\epsilon_{bias}$ can be
very small with rich neural network parameterization (Wang et al., 2020), and
$0$ with a soft-max parameterization (Ding et al., 2022).

###  4.2. Convergence Rates

Based on the above assumptions, the converges rate of AFedPG is given in
Theorem 4.3.

######  Theorem 4.3.

Let Assumption 4.1 and 4.2 hold. With suitable learning rates $\eta_{k}$ and
$\alpha_{k}$, after $K$ global iterations, AFedPG satisfy

(12) $\displaystyle
J^{\star}-\mathbb{E}[J(\theta_{K})]~{}\leq~{}\mathcal{O}\big{(}{K^{-\frac{2}{5}}}\cdot(1-\gamma)^{-3}\big{)}+\frac{\sqrt{\epsilon_{bias}}}{1-\gamma},$

where $\epsilon_{bias}$ is from (11). Thus, to satisfy
$J^{\star}-J(\theta_{K})\leq\epsilon+\frac{\sqrt{\epsilon_{bias}}}{1-\gamma}$,
we need $K=\mathcal{O}(\frac{\epsilon^{-2.5}}{(1-\gamma)^{7.5}})$ iterations.
As only one trajectory is required in each iteration, the number of
trajectories is equal to $K$, i.e., the sample complexity is
$\mathcal{O}(\frac{\epsilon^{-2.5}}{(1-\gamma)^{7.5}})$.

Comparison to the synchronous setting: Synchronous FedPG needs
$\mathcal{O}(\epsilon^{-2.5})$ trajectories in total, and each agent needs
$\mathcal{O}(\frac{\epsilon^{-2.5}}{N})$ trajectories. However, in synchronous
FedGP the server has to wait for the slowest agent at each global step, which
can still slow down the training process. Let $t_{i}$ denote the time
consumption for agent $i=1,\cdots,N$ at local steps with finite values. Then,
the waiting time on the server for each step becomes $t_{\max}\coloneqq\max
t_{i}$ for FedPG. Our AFedPG approach keeps the same sample complexity as
FedPG, but the server processes the global step as soon as it receives an
update, speeding up training. Specifically, the average waiting time on the
server is
$\bar{t}\coloneqq\frac{1}{\sum_{i=1}^{N}\frac{1}{t_{i}}}<\frac{t_{\max}}{N}$
at each step. Thus, the asynchronous FedPG achieves better time complexity
than the synchronous approach regardless of the delay pattern. The advantage
is significant when $t_{\max}\gg t_{min}$, which occurs in many practical
settings with heterogeneous computation powers across different agents. We
illustrate the advantage of AFedPG over synchronous FedPG in Figure 2. As the
server only operates one simple summation, without loss of generality, the
time consumption at the server-side is negligible.

Figure 2. Comparison of time consumptions between synchronous and asynchronous
approaches. The circled numbers denote the indices of global steps.

###  4.3. Key Lemmas

We list some useful lemmas to construct the proof sketch of Theorem 4.3. The
details of the proof can be found in Appendix A in the Technical Report (Lan
et al., 2024).

Under Assumption 4.1 on score functions, the following lemma holds based on
the results in (Zhang et al., 2020).

######  Lemma 4.4.

The gradient of the expected return is $L_{g}$-continuous and $L_{h}$-smooth
as follows

(13) $\displaystyle\|\nabla J(\theta)-\nabla J(\theta^{\prime})\|~{}\leq$
$\displaystyle~{}L_{g}\|\theta-\theta^{\prime}\|,$
$\displaystyle\|\nabla^{2}J(\theta)-\nabla^{2}J(\theta^{\prime})\|~{}\leq$
$\displaystyle~{}L_{h}\|\theta-\theta^{\prime}\|,$

where $L_{g}\coloneqq\frac{R(M_{g}^{2}+M_{h})}{(1-\gamma)^{2}}$ and
$L_{h}\coloneqq\frac{RM_{g}^{3}(1+\gamma)}{(1-\gamma)^{3}}+\frac{RM_{g}M_{h}}{(1-\gamma)^{2}}+\mathcal{O}\big{(}(1-\gamma)^{-1}\big{)}$.

Under Assumption 4.1 and 4.2, we utilize the result in (Ding et al., 2022) as
the Lemma 4.5.

######  Lemma 4.5.

(Relaxed weak gradient domination) Under Assumptions 4.1 and 4.2, it holds
that

(14) $\|\nabla
J(\theta)\|+\epsilon_{g}~{}\geq~{}\sqrt{2\mu}(J^{\star}-J(\theta)),$

where $\epsilon_{g}=\frac{\mu_{F}\sqrt{\epsilon_{bias}}}{M_{g}(1-\gamma)}$ and
$\mu=\frac{\mu_{F}^{2}}{2M_{g}^{2}}$.

Based on Lemma 4.4, we derive our milestone, the ascent lemma with delayed
updates, as follows:

######  Lemma 4.6.

(Ascent Lemma with Delay) Under Assumptions 4.1, it holds that

(15)
$\displaystyle-J(\theta_{k+1})~{}\leq~{}-J(\theta_{k})-\frac{1}{3}\eta_{k}\|\nabla
J(\theta_{k})\|+\frac{8}{3}\eta_{k}\|e_{k}\|+\frac{L_{g}}{2}\eta_{k}^{2},$

where $e_{k}\coloneqq d_{k-\delta_{k}}-\nabla J(\theta_{k})$.

This ascent lemma is specific to the asynchronous setting, which constructs
the lower bound for the global increment, $J(\theta_{k+1})-J(\theta_{k})$,
through the normalized policy gradients and our updating rules with delay
$\delta_{k}$.

###### Proof.

With the smoothness of the expected return $J(\theta)$ and the updating rule,
we have

(16) $\displaystyle-J(\theta_{k+1}){}$
$\displaystyle\leq~{}-J(\theta_{k})-\langle\nabla
J(\theta_{k}),\theta_{k+1}-\theta_{k}\rangle+\frac{L_{g}}{2}\|\theta_{k+1}-\theta_{k}\|^{2}$
$\displaystyle=~{}-J(\theta_{k})-\eta_{k}\frac{\langle\nabla
J(\theta_{k}),d_{k-\delta_{k}}\rangle}{\|d_{k-\delta_{k}}\|}+\frac{L_{g}}{2}\eta_{k}^{2}.$

If $\|e_{k}\|\leq\frac{1}{2}\|\nabla J(\theta_{k})\|$, we have

(17) $\displaystyle-\frac{\langle\nabla
J(\theta_{k}),d_{k-\delta_{k}}\rangle}{\|d_{k-\delta_{k}}\|}{}$
$\displaystyle=~{}-\frac{\|\nabla J(\theta_{k})\|^{2}+\langle\nabla
J(\theta_{k}),e_{k}\rangle}{\|d_{k-\delta_{k}}\|}$
$\displaystyle\leq~{}\frac{-\|\nabla J(\theta_{k})\|^{2}+\|\nabla
J(\theta_{k})\|\|e_{k}\|}{\|d_{k-\delta_{k}}\|}$
$\displaystyle\leq~{}\frac{-\|\nabla J(\theta_{k})\|^{2}+\frac{1}{2}\|\nabla
J(\theta_{k})\|^{2}}{\|\nabla
J(\theta_{k})\|+\|e_{k}\|}\leq~{}-\frac{1}{3}\|\nabla J(\theta_{k})\|.$

If $\|e_{k}\|\geq\frac{1}{2}\|\nabla J(\theta_{k})\|$, we have

(18) $\displaystyle-\frac{\langle\nabla
J(\theta_{k}),d_{k-\delta_{k}}\rangle}{\|d_{k-\delta_{k}}\|}\leq~{}\|\nabla
J(\theta_{k})\|$ $\displaystyle=~{}-\frac{1}{3}\|\nabla
J(\theta_{k})\|+\frac{4}{3}\|\nabla J(\theta_{k})\|\leq~{}-\frac{1}{3}\|\nabla
J(\theta_{k})\|+\frac{8}{3}\|e_{k}\|.$

Combine these two conditions, and plugging the result in (16), the lemma can
be proved as

(19) $\displaystyle-J(\theta_{k+1}){}$
$\displaystyle\leq~{}-J(\theta_{k})-\eta_{k}\frac{\langle\nabla
J(\theta_{k}),d_{k-\delta_{k}}\rangle}{\|d_{k-\delta_{k}}\|}+\frac{L_{g}}{2}\eta_{k}^{2}$
$\displaystyle\leq~{}-J(\theta_{k})-\frac{1}{3}\eta_{k}\|\nabla
J(\theta_{k})\|+\frac{8}{3}\eta_{k}\|e_{k}\|+\frac{L_{g}}{2}\eta_{k}^{2}.$

∎

Next, we construct the relationship between the average concurrency
$\bar{\omega}$ and the average delay $\bar{\delta}$ in Lemma 4.7. This lemma
gives the boundary (our result) of delays as a corollary of the result in
(Koloskova et al., 2022).

######  Lemma 4.7.

The average delay $\bar{\delta}$ depends on the average concurrency
$\bar{\omega}$ as

(20)
$\bar{\delta}=\frac{K+1}{K-1+|\mathcal{C}_{K}|}\bar{\omega}\leq\bar{\omega}\leq
N.$

###### Proof.

Recall that $\\{\delta_{k}^{i}\\}_{i\in\mathcal{C}_{k}\setminus\\{j_{k}\\}}$
is the set of delays at the $k$-th global steps. After one global step, the
number of cumulative delays over all agents increases by the current
concurrency. Thus, we have the following connection

(21)
$\displaystyle\sum_{i=0}^{k}\delta_{i}+\sum_{i\in\mathcal{C}_{k+1}\setminus\\{j_{k+1}\\}}\delta^{i}_{k+1}{}$
$\displaystyle=~{}\sum_{i=0}^{k-1}\delta_{i}+\sum_{i\in\mathcal{C}_{k}\setminus\\{j_{k}\\}}\delta^{i}_{k}+\omega_{k+1}.$

At the initial step, there is no delay. Therefore, we have $\delta^{i}_{0}=0$
for all agents. Unrolling the above expression, at the $K$-th step, we have

(22)
$\displaystyle\sum_{i=0}^{K-1}\delta_{i}+\sum_{i\in\mathcal{C}_{K}\setminus\\{j_{K}\\}}\delta^{i}_{K}{}$
$\displaystyle=~{}\sum_{i=0}^{K}\omega_{k+1}~{}=~{}(K+1)\bar{\omega}.$

According to (7) and $|\mathcal{C}_{K}|\geq 2$, we achieve

(23)
$\bar{\delta}~{}=~{}\frac{K+1}{K-1+|\mathcal{C}_{K}|}\bar{\omega}\leq\bar{\omega}\leq
N.$

In practice, we need to use all resources to speedup the training process, and
thus, $\bar{\omega}=\omega_{\max}=N$. Since the maximum concurrency is equal
to the number of agents $N$, we have the boundary of the average delay as
$\bar{\delta}\leq\omega_{\max}\leq N$. ∎

###  4.4. Proof sketch of Theorem 4.3

Here, we briefly give the main idea of our proof of Theorem 4.3. The complete
details and the technical lemmas are provided in Appendix A in the Technical
Report (Lan et al., 2024).

First, we prove the ascent lemma 4.6 based on Lemma 4.4 and the updating rule
of AFedPG in Algorithm 1 and 2. We then plug it into (14) in Lemma 4.5 in the
expectation form, and get the following inequality

(24) $\displaystyle J^{\star}-\mathbb{E}[J(\theta_{k+1})]~{}\leq$
$\displaystyle~{}(1-\frac{\sqrt{2\mu}\eta_{k}}{3})\big{(}J^{\star}-\mathbb{E}[J(\theta_{k})]\big{)}$
$\displaystyle~{}+\frac{\eta_{k}}{3}\epsilon_{g}+\frac{8}{3}\eta_{k}\mathbb{E}[\|e_{k}\|]+\frac{L_{g}}{2}\eta_{k}^{2}.$

Second, we bound the expected error term $\mathbb{E}[\|e_{K}\|]$ in the ascent
lemma with delayed updates. Here we utilize the normalization and look-ahead
sampling in Algorithm 1 and 2 to bound the error with an average delay term
$\bar{\delta}$ from Lemma 4.7. With suitable learning rates as
$\alpha_{k}=(\frac{1}{k+1})^{\frac{4}{5}}$ and
$\eta_{k}=\eta_{0}\frac{1}{k+1}$, the upper bound of $\mathbb{E}[\|e_{K}\|]$
is given as follows

(25) $\displaystyle\mathbb{E}[\|e_{K}\|]{\leq}$
$\displaystyle~{}\alpha_{K}\sigma_{g}+c_{1}\sqrt{\alpha_{K}}\sigma_{g}+\frac{9}{4}c_{2}L_{h}\frac{\eta_{K}^{2}}{\alpha_{K}^{2}}+2c_{3}L_{g}\frac{\eta_{K}^{2}}{\alpha_{K}}\bar{\delta},$

where $c_{1}$, $c_{2}$ and $c_{3}$ are constants, and their values are given
in Appendix A.2 in the Technical Report (Lan et al., 2024).

Third, unroll the recursion of (24), and then plug the upper bound result (25)
into the unrolled form. We now have the following inequality

(26) $\displaystyle J^{\star}$
$\displaystyle-\mathbb{E}[J(\theta_{K})]~{}\leq~{}\frac{\eta_{0}}{3}\epsilon_{g}+\frac{J^{\star}-\mathbb{E}[J(\theta_{0})]}{(K+1)^{2}}+c_{3}\frac{16\eta_{0}^{2}}{3}\frac{L_{g}}{(K+1)^{\frac{7}{5}}}\bar{\delta}$
$\displaystyle+\frac{\eta_{0}^{2}}{2}\frac{L_{g}}{K+1}+\frac{8\eta_{0}}{3}\frac{\sigma_{g}}{(K+1)^{\frac{4}{5}}}+c_{1}\frac{8\eta_{0}}{3}\frac{\sigma_{g}}{(K+1)^{\frac{2}{5}}}+6c_{2}\eta_{0}^{3}\frac{L_{h}}{(K+1)^{\frac{2}{5}}}.$

With an initial learning rate as $\eta_{0}=\frac{3\mu_{F}}{M_{g}}$, we achieve
the global convergence rate in Theorem 4.3.

##  5\. Experiments

###  5.1. Setup

Environment: To validate the effectiveness of our approach via experiments, we
consider three popular MuJoCo environments (Swimmer-v4, Hopper-v4, and
Humanoid-v4) (Todorov et al., 2012) with the MIT License. Both the state and
action spaces are continuous. Environmental details are described in Table 2
and the MuJoCo tasks are visualized in Figure 3.

(a) Swimmer-v4

(b) Hopper-v4

(c) Humanoid-v4

Figure 3. Visualization of the three MuJoCo tasks considered in this paper for experiments. Table 2. Detailed descriptions of the three tasks in the MuJoCo environment. |  | Action Space | State Space
---|---|---|---
MuJoCo Tasks | Agent Types | Dimension | Dimension
| Three-link |  |
Swimmer-v4 | swimming robot | $2$ | $8$
| Two-dimensional |  |
Hopper-v4 | one-legged robot | $3$ | $11$
| Three-dimensional |  |
Humanoid-v4 | bipedal robot | $17$ | $376$
Table 3. Hyperparameters of AFedPG and the MLP policy parameterization settings. Hyperparameter | Setting
---|---
Task | Swimmer-v4 | Hopper-v4 | Humanoid-v4
MLP | $64\times 64$ | $256\times 256$ | $512\times 512\times 512$
Activation function | ReLU | ReLU | ReLU
Output function | Tanh | Tanh | Tanh
Learning rate ($\alpha$) | $1\times 10^{-3}$ | $1\times 10^{-3}$ | $1\times 10^{-3}$
Discount ($\gamma$) | $0.99$ | $0.99$ | $0.99$
Timesteps ($T$) | $2048$ | $1024$ | $512$
Iterations ($K$) | $1\times 10^{3}$ | $2\times 10^{3}$ | $1.5\times 10^{4}$
Learning rate ($\eta$) | $3\times 10^{-4}$ | $1\times 10^{-4}$ | $1\times 10^{-5}$

(a) Swimmer-v4

(b) Hopper-v4

(c) Humanoid-v4

Figure 4. Reward performances of AFedPG ($N=2,4,8$) and PG ($N=1$) on various
MoJuCo environments, where $N$ is the number of federated agents. The solid
lines are averaged results over $10$ runs and the shadowed areas are
confidence intervals with $95\%$ confidence level.

Measurement: All convergence performances are measured over $10$ runs with
random seeds from $0$ to $9$. The solid lines in our main experimental results
are the averaged results, and the shadowed areas are confidence intervals with
the confidence level $95\%$. The lines are smoothed for better visualization.

Implementation: Policies are parameterized by fully connected multi-layer
perceptions (MLPs) with settings listed in Table 3. We follow the practical
settings in stable-baselines3 (Raffin et al., 2021) to update models with
generalized advantage estimation (GAE) ($0.95$) (Schulman et al., 2018) in our
implementation. We use PyTorch (Paszke et al., 2019) to implement deep neural
networks (DNNs). All tasks are trained on NVIDIA A100 GPUs with $40$ GB of
memory.

Baselines: We first consider the conventional PG approach with $N=1$, to see
the effect of using multiple agents for improving sample complexity. We also
consider the synchronous FedPG method as a baseline to observe the impact of
asynchronous update for enhancing the time complexity. We note that only a few
prior works have focused on the federated PG problem, and many existing works
in federated supervised learning are not directly applicable to our federated
RL setting.

Performance metrics: We consider the following metrics:

  1. (1)

Rewards: the average trajectory rewards collected at each iteration;

  2. (2)

Convergence: rewards versus iterations during the training process;

  3. (3)

Time consumption: global time with certain numbers of collected samples.

###  5.2. Results

Speedup of sample complexity: First, to verify the improvement of sample
complexity in the first row of Table 1, we evaluate the speedup effects of the
number of federated agents $N$. In Figure 4, with different numbers of agents,
we test the convergence performances of AFedPG ($N=2,4,8$) and the single
agent PG ($N=1$). The x-axis is the number of samples collected by each agent
on average, and the y-axis is the reward. In all three MuJoCo tasks, AFedPG
beats the single-agent PG: AFedPG converges faster, has lower variances, and
achieves higher final rewards when more agents are involved in collecting
trajectories and estimating policy gradients. These results confirm the
advantage of AFedPG in terms of sample complexity.

(a) Swimmer-v4

(b) Hopper-v4

(c) Humanoid-v4

Figure 5. Global time of AFedPG and FedPG with certain numbers of collected
samples on various MoJuCo environments, where $N$ is the number of federated
agents. The solid lines are averaged results over $10$ runs and the shadowed
areas are confidence intervals with $95\%$ confidence level. Figure 6. The
time complexity speedup of AFedPG compared to FedPG. The x-axis is the
heterogeneous ratio of computing power measured by
$\frac{t_{\max}}{t_{\min}}$. The y-axis is the global time of FedPG divided by
that of AFedPG.

Improvement of global time complexity: Second, to verify the improvement of
global time complexity in the second row of Table 1, we compared the time
consumption in the asynchronous and synchronous settings. In Figure 5, we set
$N=4,~{}8$ and fix the number of samples collected by all agents. Here,
$t_{\max}$ is about $4$ times more than $t_{\min}$. The numbers of total
samples (trajectories) are $8\times 10^{3}$, $16\times 10^{3}$, and $8\times
10^{4}$ for the Swimmer-v4 task, Hopper-v4 task, and Humanoid-v4 task
individually when $N=8$. When $N=4$, the numbers are halved. In all three
environments, AFedPG has much lower time consumption compared to the
synchronous FedPG, confirming the enhancement in terms of time complexity.

Effect of computation heterogeneity: At last, we study the effect of the
computation heterogeneity among federated agents. The heterogeneity of
computing powers is measured by the ratio $\frac{t_{\max}}{t_{\min}}$, and the
effect is measured by the speedup, which is the global time of FedPG divided
by that of AFedPG. Without loss of generality, we test the performances with
one straggler here, which is one agent has $t_{\max}$ time consumption, and
all the other agents have $t_{\min}$ time consumption. In Figure 6, the
results show that the speedup increases in a nearly linear behavior as the
heterogeneity ratio $\frac{t_{\max}}{t_{\min}}$ increases. On the other hand,
the more agents that participate in the training process, the higher speedup
they achieve. The overall results indicate that AFedPG has the potential to
scale up to a very large mobile RL system, particularly in scenarios with
extreme stragglers ($t_{\max}\gg t_{\min}$).

##  6\. Conclusion

In this paper, we proposed AFedPG, a novel asynchronous federated
reinforcement learning framework which updates the global model using policy
gradients from multiple agents. To handle the challenge of lagged policies in
the asynchronous setting, we designed a delay-adaptive lookahead technique and
used normalized updates to integrate policy gradients. With the above methods,
AFedPG achieves speedup for both sample complexity and time complexity. First,
our AFedPG method achieves $\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$ sample
complexity at each agent. Compared to the single agent setting (PG) with
$\mathcal{O}(\epsilon^{-2.5})$ sample complexity, it enjoys a linear speedup
with respect to the number of agents $N$. Second, compared to synchronous
FedPG, AFedPG improves the time consumption 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 can be significant in a large-scale
federated setting with heterogeneous computing powers ($t_{\max}\gg
t_{\min}$). Finally, we empirically verified the performances of AFedPG
compared to PG and FedPG in three MuJoCo environments with different $N$. We
also demonstrate the improvements with different computing heterogeneity. In
summary, AFedPG achieves speedup in terms of both sample complexity and time
complexity when it is scaled up to a large mobile RL system, especially with
large computing power heterogeneity.

Investigating asynchronous FedRL with the second-order methods (e.g., natural
policy gradients) and adversarial attacks are interesting directions for
future research.

## References

  * (1)
  * Agarwal et al. (2021b) Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. 2021b.  On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift.  _Journal of Machine Learning Research_ 22, 1 (2021), 4431–4506.
  * Agarwal et al. (2021a) Mridul Agarwal, Bhargav Ganguly, and Vaneet Aggarwal. 2021a.  Communication Efficient Parallel Reinforcement Learning. In _Uncertainty in Artificial Intelligence (UAI 2021)_ _(Proceedings of Machine Learning Research, Vol. 161)_. PMLR, 247–256.
  * Al-Abbasi et al. (2019) Abubakr O. Al-Abbasi, Arnob Ghosh, and Vaneet Aggarwal. 2019.  DeepPool: Distributed Model-free Algorithm for Ride-sharing Using Deep Reinforcement Learning.  _IEEE Transactions on Intelligent Transportation Systems_ 20, 12 (2019), 4714–4727.
  * Chen et al. (2020) Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. 2020.  VAFL: A Method of Vertical Asynchronous Federated Learning.  _arXiv preprint arXiv:2007.06081_ (2020).
  * Ding et al. (2020) Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. 2020.  Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes. In _Advances in Neural Information Processing Systems (NeurIPS 2020)_ , Vol. 33. Curran Associates, Inc., 8378–8390.
  * Ding et al. (2022) Yuhao Ding, Junzi Zhang, and Javad Lavaei. 2022.  On the Global Optimum Convergence of Momentum-based Policy Gradient. In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (AISTAT 2022)_ _(Proceedings of Machine Learning Research, Vol. 151)_. PMLR, 1910–1934.
  * Dulac-Arnold et al. (2021) Gabriel Dulac-Arnold, Nir Levine, Daniel J Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. 2021.  Challenges of Real-world Reinforcement Learning: Definitions, Benchmarks and Analysis.  _Machine Learning_ 110, 9 (2021), 2419–2468.
  * Dun et al. (2023) Chen Dun, Mirian Hipolito, Chris Jermaine, Dimitrios Dimitriadis, and Anastasios Kyrillidis. 2023.  Efficient and Light-Weight Federated Learning via Asynchronous Distributed Dropout. In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (AISTAT 2023)_ _(Proceedings of Machine Learning Research, Vol. 206)_. PMLR, Palau de Congressos, Valencia, Spain, 6630–6660.
  * Fang et al. (2023) Wenzhi Fang, Dong-Jun Han, and Christopher G. Brinton. 2023.  Submodel Partitioning in Hierarchical Federated Learning: Algorithm Design and Convergence Analysis.  _arXiv preprint arXiv:2310.17890_ (2023).
  * Fatkhullin et al. (2023) Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. 2023.  Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies. In _International Conference on Machine Learning (ICML 2023)_ _(Proceedings of Machine Learning Research, Vol. 202)_. PMLR, Honolulu, HI, USA, 9827–9869.
  * Haliem et al. (2021) Marina Haliem, Ganapathy Mani, Vaneet Aggarwal, and Bharat Bhargava. 2021.  A Distributed Model-free Ride-sharing Approach for Joint Matching, Pricing, and Dispatching Using Deep Reinforcement Learning.  _IEEE Transactions on Intelligent Transportation Systems_ 22, 12 (2021), 7931–7942.
  * Han et al. (2023) Dong-Jun Han, Do-Yeon Kim, Minseok Choi, David Nickel, Jaekyun Moon, Mung Chiang, and Christopher G. Brinton. 2023.  Federated Split Learning With Joint Personalization-Generalization for Inference-Stage Optimization in Wireless Edge Networks.  _IEEE Transactions on Mobile Computing_ (2023).
  * Hosseinalipour et al. (2020) Seyyedali Hosseinalipour, Christopher G. Brinton, Vaneet Aggarwal, Huaiyu Dai, and Mung Chiang. 2020.  From Federated to Fog Learning: Distributed Machine Learning over Heterogeneous Wireless Networks.  _IEEE Communications Magazine_ 58, 12 (2020), 41–47.
  * Hu et al. (2024) Pihe Hu, Yu Chen, Ling Pan, Zhixuan Fang, Fu Xiao, and Longbo Huang. 2024.  Multi-User Delay-Constrained Scheduling with Deep Recurrent Reinforcement Learning.  _IEEE/ACM Transactions on Networking_ (2024).
  * Hu et al. (2022) Pihe Hu, Ling Pan, Yu Chen, Zhixuan Fang, and Longbo Huang. 2022.  Effective Multi-user Delay-constrained Scheduling with Deep Recurrent Reinforcement Learning. In _Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (MobiHoc 2022)_. Association for Computing Machinery, Seoul, South Korea, 1–10.
  * Huang et al. (2020) Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. 2020.  Momentum-based Policy Gradient Methods. In _International conference on machine learning (ICML 2020)_ _(Proceedings of Machine Learning Research, Vol. 119)_. PMLR, 4422–4433.
  * Jin et al. (2022) Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang. 2022.  Federated Reinforcement Learning with Environment Heterogeneity. In _International Conference on Artificial Intelligence and Statistics (AISTAT 2022)_ _(Proceedings of Machine Learning Research, Vol. 151)_. PMLR, 18–37.
  * Kairouz et al. (2021) Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. 2021\.  Advances and Open Problems in Federated Learning.  _Foundations and trends® in machine learning_ 14, 1–2 (2021), 1–210.
  * Khodadadian et al. (2022) Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. 2022.  Federated Reinforcement Learning: Linear Speedup under Markovian Sampling. In _International Conference on Machine Learning (ICML 2022)_ , Vol. 162. PMLR, Baltimore, MD, USA, 10997–11057.
  * Kiran et al. (2022) B. Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab, Senthil Yogamani, and Patrick Pérez. 2022.  Deep Reinforcement Learning for Autonomous Driving: A Survey.  _IEEE Transactions on Intelligent Transportation Systems_ 23, 6 (2022), 4909–4926.
  * Koloskova et al. (2022) Anastasiia Koloskova, Sebastian U. Stich, and Martin Jaggi. 2022.  Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning. In _Advances in Neural Information Processing Systems (NeurIPS 2022)_ , Vol. 35. PMLR, New Orleans, LA, USA, 17202–17215.
  * Ladosz et al. (2022) Pawel Ladosz, Lilian Weng, Minwoo Kim, and Hyondong Oh. 2022.  Exploration in Deep Reinforcement Learning: A Survey.  _Information Fusion_ 85 (2022), 1–22.
  * Lan et al. (2024) Guangchen Lan, Dong-Jun Han, Abolfazl Hashemi, Vaneet Aggarwal, and Christopher G. Brinton. 2024.  Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis.  _arXiv preprint arXiv:2404.08003_ (2024).
  * Lan et al. (2023a) Guangchen Lan, Xiao-Yang Liu, Yijing Zhang, and Xiaodong Wang. 2023a.  Communication-efficient Federated Learning for Resource-constrained Edge Devices.  _IEEE Transactions on Machine Learning in Communications and Networking_ 1 (2023), 210–224.
  * Lan et al. (2023b) Guangchen Lan, Han Wang, James Anderson, Christopher Brinton, and Vaneet Aggarwal. 2023b.  Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updates. In _Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023)_ , Vol. 36. Curran Associates, Inc., New Orleans, LA, USA, 59873–59885.
  * Liu et al. (2021) Xiao-Yang Liu, Zechu Li, Zhuoran Yang, Jiahao Zheng, Zhaoran Wang, Anwar Walid, Jian Guo, and Michael I Jordan. 2021.  ElegantRL-Podracer: Scalable and Elastic Library for Cloud-Native Deep Reinforcement Learning. In _Advances in Neural Information Processing Systems Workshop on Deep Reinforcement Learning_.
  * Liu et al. (2020) Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. 2020.  An Improved Analysis of (Variance-reduced) Policy Gradient and Natural Policy Gradient Methods. In _Advances in Neural Information Processing Systems (NeurIPS 2020)_ , Vol. 33. Curran Associates, Inc., 7624–7636.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017.  Communication-efficient Learning of Deep Networks from Decentralized Data. In _International Conference on Artificial Intelligence and Statistics (AISTAT 2017)_ _(Proceedings of Machine Learning Research, Vol. 54)_. PMLR, Ft. Lauderdale, FL, USA, 1273–1282.
  * Mishchenko et al. (2022) Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. 2022.  Asynchronous SGD Beats Minibatch SGD under Arbitrary Delays. In _Advances in Neural Information Processing Systems (NeurIPS 2022)_ , Vol. 35. PMLR, New Orleans, LA, USA, 420–433.
  * Mnih et al. (2016) Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. 2016.  Asynchronous Methods for Deep Reinforcement Learning. In _Proceedings of The 33rd International Conference on Machine Learning (ICML 2016)_ _(Proceedings of Machine Learning Research, Vol. 48)_. PMLR, New York, NY, USA, 1928–1937.
  * Mondal and Aggarwal (2024) Washim Uddin Mondal and Vaneet Aggarwal. 2024.  Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes.  _arXiv preprint arXiv:2310.11677_ (2024).
  * Moon et al. (2021) Sangwoo Moon, Sumyeong Ahn, Kyunghwan Son, Jinwoo Park, and Yung Yi. 2021.  Neuro-DCF: Design of Wireless MAC via Multi-Agent Reinforcement Learning Approach. In _Proceedings of the Twenty-Second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing_ (Shanghai, China) _(MobiHoc 2021)_. Association for Computing Machinery, 141–150.
  * Mothukuri et al. (2021) Viraaji Mothukuri, Reza M. Parizi, Seyedamin Pouriyeh, Yan Huang, Ali Dehghantanha, and Gautam Srivastava. 2021.  A Survey on Security and Privacy of Federated Learning.  _Future Generation Computer Systems_ 115 (2021), 619–640.
  * Nguyen et al. (2021) Dinh C. Nguyen, Ming Ding, Pubudu N. Pathirana, Aruna Seneviratne, Jun Li, and H. Vincent Poor. 2021.  Federated Learning for Internet of Things: A Comprehensive Survey.  _IEEE Communications Surveys & Tutorials_ 23, 3 (2021), 1622–1658.
  * Niknam et al. (2020) Solmaz Niknam, Harpreet S. Dhillon, and Jeffrey H. Reed. 2020.  Federated Learning for Wireless Communications: Motivation, Opportunities, and Challenges.  _IEEE Communications Magazine_ 58, 6 (2020), 46–51.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  _arXiv preprint arXiv:2303.08774_ (2023).
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022.  Training Language Models to Follow Instructions with Human Feedback. In _Advances in Neural Information Processing Systems (NeurIPS 2022)_ , Vol. 35. Curran Associates, Inc., New Orleans, LA, USA, 27730–27744.
  * Papini et al. (2018) Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. 2018.  Stochastic Variance-Reduced Policy Gradient. In _Proceedings of the 35th International Conference on Machine Learning (ICML 2018)_ _(Proceedings of Machine Learning Research, Vol. 80)_. PMLR, Stockholm, Sweden, 4026–4035.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  PyTorch: An Imperative Style, High-performance Deep Learning Library. In _Advances in Neural Information Processing Systems (NeurIPS 2019)_ , Vol. 32. Curran Associates, Inc., Vancouver, Canada.
  * Predd et al. (2006) Joel B. Predd, Sanjeev B. Kulkarni, and H. Vincent Poor. 2006.  Distributed Learning in Wireless Sensor Networks.  _IEEE Signal Processing Magazine_ 23, 4 (2006), 56–69.
  * Provost and Fawcett (2013) Foster Provost and Tom Fawcett. 2013.  Data Science and Its Relationship to Big Data and Data-driven Decision Making.  _Big Data_ 1, 1 (2013), 51–59.
  * Raffin et al. (2021) Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. 2021.  Stable-Baselines3: Reliable Reinforcement Learning Implementations.  _Journal of Machine Learning Research_ 22, 268 (2021), 1–8.
  * Schulman et al. (2018) John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. 2018.  High-Dimensional Continuous Control Using Generalized Advantage Estimation.  _arXiv preprint arXiv:1506.02438_ (2018).
  * Team and DeepMind (2024) Gemma Team and Google DeepMind. 2024.  Gemma: Open Models Based on Gemini Research and Technology.  _arXiv preprint arXiv:2403.08295_ (2024).
  * Todorov et al. (2012) Emanuel Todorov, Tom Erez, and Yuval Tassa. 2012.  MuJoCo: A Physics Engine for Model-based Control. In _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2012)_. IEEE, Vilamoura-Algarve, Portugal, 5026–5033.
  * Wang et al. (2023) Han Wang, Aritra Mitra, Hamed Hassani, George J Pappas, and James Anderson. 2023.  Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity.  _arXiv preprint arXiv:2302.02212_ (2023).
  * Wang et al. (2020) Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. 2020.  Neural Policy Gradient Methods: Global Optimality and Rates of Convergence. In _International Conference on Learning Representations (ICLR 2020)_.
  * Wei et al. (2023) Honghao Wei, Xin Liu, Weina Wang, and Lei Ying. 2023.  Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networks. In _Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023)_ , Vol. 36. Curran Associates, Inc., New Orleans, LA, USA, 2033–2055.
  * Williams (1992) Ronald J. Williams. 1992.  Simple Statistical Gradient-following Algorithms for Connectionist Reinforcement Learning.  _Machine learning_ 8 (1992), 229–256.
  * Xie et al. (2020) Cong Xie, Sanmi Koyejo, and Indranil Gupta. 2020.  Asynchronous Federated Optimization. In _12th Annual Workshop on Optimization for Machine Learning (OPT 2020)_.
  * Xie and Song (2023) Zhijie Xie and Shenghui Song. 2023.  FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergence.  _IEEE Journal on Selected Areas in Communications_ 41, 4 (2023), 1227–1242.
  * Xiong et al. (2022) Guojun Xiong, Xudong Qin, Bin Li, Rahul Singh, and Jian Li. 2022.  Index-aware Reinforcement Learning for Adaptive Video Streaming at the Wireless Edge. In _Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (MobiHoc 2022)_. Association for Computing Machinery, Seoul, South Korea, 81–90.
  * Xu et al. (2020) Pan Xu, Felicia Gao, and Quanquan Gu. 2020.  Sample Efficient Policy Gradient Methods with Recursive Variance Reduction. In _International Conference on Learning Representations (ICLR 2020)_.
  * Yu et al. (2023) Wenhan Yu, Terence Jie Chua, and Jun Zhao. 2023.  Asynchronous Hybrid Reinforcement Learning for Latency and Reliability Optimization in the Metaverse Over Wireless Communications.  _IEEE Journal on Selected Areas in Communications_ 41, 7 (2023), 2138–2157.
  * Yuan et al. (2022) Rui Yuan, Robert M. Gower, and Alessandro Lazaric. 2022.  A General Sample Complexity Analysis of Vanilla Policy Gradient. In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (AISTAT 2022)_ _(Proceedings of Machine Learning Research, Vol. 151)_. PMLR, 3332–3380.
  * Zhang et al. (2020) Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. 2020.  Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies.  _SIAM Journal on Control and Optimization_ 58, 6 (2020), 3586–3612.

##  Appendix A Proofs

###  A.1. Technical Lemmas

######  Lemma A.1.

For arbitrary $n$ vectors $\\{\mathbf{a}_{i}\in\mathbb{R}^{d}\\}_{i=1}^{n}$,
we have

(27)
$\|\sum_{i=1}^{n}\mathbf{a}_{i}\|^{2}~{}\leq~{}n\sum_{i=1}^{n}\|\mathbf{a}_{i}\|^{2}.$

######  Lemma A.2.

Let $\alpha_{k}=(\frac{c}{t+c})^{p}$. $\forall p\in[0,1]$ and $c\geq 1$, we
have

(28) $1-\alpha_{k+1}~{}\leq~{}\frac{\alpha_{k+1}}{\alpha_{k}}.$

###### Proof.

(29) $\displaystyle 1-\alpha_{k+1}~{}=$
$\displaystyle~{}1-(\frac{c}{t+1+c})^{p}$ $\displaystyle~{}\leq$
$\displaystyle~{}1-\frac{1}{t+1+c}$ $\displaystyle~{}\leq$
$\displaystyle~{}\frac{\alpha_{k+1}}{\alpha_{k}}.$

Straightforwardly, we have

(30) $\displaystyle\prod_{i=k}^{K-1}(1-\alpha_{i+1})~{}\leq$
$\displaystyle~{}\frac{\alpha_{K}}{\alpha_{k}}.$

∎

######  Lemma A.3.

Let $\alpha_{k}=(\frac{1}{k+1})^{p}$ and
$\eta_{k}=\eta_{0}(\frac{1}{k+1})^{q}$. $\forall p\in[0,1)$, $q\geq 0$ and
$\eta_{0}\geq 0$, we have

(31)
$\sum_{k=0}^{K-1}\eta_{k}\prod_{i=k+1}^{K-1}(1-\alpha_{i})~{}\leq~{}c(p,q)\frac{\eta_{K}}{\alpha_{K}},$

where
$c(p,q)\coloneqq\frac{2^{q-p}}{1-p}a\exp{\big{(}(1-p)2^{p}a^{1-p}\big{)}}$ is
a constant, and
$a=\max\big{(}(\frac{q}{(1-p)2^{p}})^{\frac{1}{1-p}},(\frac{2(q-p)}{(1-p)^{2}})^{\frac{1}{1-p}}\big{)}$.

###  A.2. Proof of Theorem 4.3

Denote $\xi_{k}\coloneqq g(\widetilde{\tau}_{k},\widetilde{\theta}_{k})-\nabla
J(\widetilde{\theta}_{k})$. First, according to the updating rules in Algo. 1
and Algo. 2 , we expand the error term in Lemma 4.6 as follows

(32) $\displaystyle e_{k}~{}=$
$\displaystyle~{}(1-\alpha_{k-\delta_{k}})d_{\delta_{k-1}}+(1-\alpha_{k-\delta_{k}})\big{(}\nabla
J(\theta_{k-1})-\nabla
J(\theta_{k})\big{)}+\alpha_{k-\delta_{k}}\big{(}g(\widetilde{\tau}_{k-\delta_{k}},\widetilde{\theta}_{k-\delta_{k}})-\nabla
J(\theta_{k})\big{)}$ $\displaystyle~{}=$
$\displaystyle~{}\alpha_{k-\delta_{k}}\xi_{k-\delta_{k}}+(1-\alpha_{k-\delta_{k}})e_{k-1}+(1-\alpha_{k-\delta_{k}})\big{(}\nabla
J(\theta_{k-1})-\nabla J(\theta_{k})\big{)}+\alpha_{k-\delta_{k}}\big{(}\nabla
J(\widetilde{\theta}_{k-\delta_{k}})-\nabla J(\theta_{k})\big{)}$
$\displaystyle~{}=$
$\displaystyle~{}\alpha_{k-\delta_{k}}\xi_{k-\delta_{k}}+(1-\alpha_{k-\delta_{k}})e_{k-1}+(1-\alpha_{k-\delta_{k}})\big{(}\nabla
J(\theta_{k-1})-\nabla J(\theta_{k})\big{)}$
$\displaystyle+\alpha_{k-\delta_{k}}\big{(}\nabla
J(\widetilde{\theta}_{k-\delta_{k}})-\nabla
J(\widetilde{\theta}_{k})\big{)}+\alpha_{k-\delta_{k}}\big{(}\nabla
J(\widetilde{\theta}_{k})-\nabla J(\theta_{k})\big{)}$ $\displaystyle~{}=$
$\displaystyle~{}\alpha_{k-\delta_{k}}\xi_{k-\delta_{k}}+(1-\alpha_{k-\delta_{k}})e_{k-1}+(1-\alpha_{k-\delta_{k}})\big{(}\nabla
J(\theta_{k-1})-\nabla
J(\theta_{k})+\nabla^{2}J(\theta_{k})(\theta_{k-1}-\theta_{k})\big{)}$
$\displaystyle+\alpha_{k-\delta_{k}}\big{(}\nabla
J(\widetilde{\theta}_{k-\delta_{k}})-\nabla
J(\widetilde{\theta}_{k})\big{)}+\alpha_{k-\delta_{k}}\big{(}\nabla
J(\widetilde{\theta}_{k})-\nabla
J(\theta_{k})+\nabla^{2}J(\theta_{k})(\theta_{k-1}-\theta_{k})\big{)}$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-(1-\alpha_{k-\delta_{k}})\nabla^{2}J(\theta_{k})(\theta_{k-1}-\theta_{k})-\alpha_{k-\delta_{k}}\nabla^{2}J(\theta_{k})(\widetilde{\theta}_{k}-\theta_{k})}$
$\displaystyle~{}\stackrel{{\scriptstyle\eqref{eq:delay_adaptive}}}{{=}}$
$\displaystyle~{}\alpha_{k-\delta_{k}}\xi_{k-\delta_{k}}+(1-\alpha_{k-\delta_{k}})e_{k-1}+(1-\alpha_{k-\delta_{k}})\big{(}\nabla
J(\theta_{k-1})-\nabla
J(\theta_{k})+\nabla^{2}J(\theta_{k})(\theta_{k-1}-\theta_{k})\big{)}$
$\displaystyle+\alpha_{k-\delta_{k}}\big{(}\nabla
J(\widetilde{\theta}_{k-\delta_{k}})-\nabla
J(\widetilde{\theta}_{k})\big{)}+\alpha_{k-\delta_{k}}\big{(}\nabla
J(\widetilde{\theta}_{k})-\nabla
J(\theta_{k})+\nabla^{2}J(\theta_{k})(\theta_{k-1}-\theta_{k})\big{)}.$

Remark: The Hessian correction terms (in blue) are equal to $0$ according to
our updating rules (delay-adaptive lookahead update) in Step 2 of Algo. 2. We
design this technique to cancel out the second-order terms, and thus achieve
the desired convergence rate.

Next, we denote

(33) $\displaystyle A_{k}~{}\coloneqq$ $\displaystyle~{}\nabla
J(\theta_{k-1})-\nabla
J(\theta_{k})+\nabla^{2}J(\theta_{k})(\theta_{k-1}-\theta_{k}),$
$\displaystyle B_{k}~{}\coloneqq$ $\displaystyle~{}\nabla
J(\widetilde{\theta}_{k})-\nabla
J(\theta_{k})+\nabla^{2}J(\theta_{k})(\theta_{k-1}-\theta_{k}),$
$\displaystyle C_{k}~{}\coloneqq$ $\displaystyle~{}\nabla
J(\widetilde{\theta}_{k-\delta_{k}})-\nabla J(\widetilde{\theta}_{k}).$

With the smoothness in Lemma 4.4 and the non-increasing learning rates, we
have

(34) $\displaystyle\|A_{k}\|{}$
$\displaystyle\leq~{}L_{h}\|\theta_{k-1}-\theta_{k}\|^{2}=L_{h}\eta_{k-1}^{2},$
$\displaystyle\|B_{k}\|{}$
$\displaystyle\leq~{}L_{h}\|\widetilde{\theta}_{k}-\theta_{k}\|^{2}=L_{h}\frac{(1-\alpha_{k-\delta_{k}})^{2}}{\alpha_{k-\delta_{k}}^{2}}\eta_{k-1}^{2},$
$\displaystyle\|C_{k}\|{}$
$\displaystyle\leq~{}L_{g}\|\widetilde{\theta}_{k-\delta_{k}}-\widetilde{\theta}_{k}\|$
$\displaystyle=~{}L_{g}\left\|\sum_{i=k-\delta_{k}}^{k-1}\widetilde{\theta}_{i+1}-\widetilde{\theta}_{i}\right\|$
$\displaystyle\leq~{}L_{g}\sum_{i=k-\delta_{k}}^{k-1}\|\widetilde{\theta}_{i+1}-\widetilde{\theta}_{i}\|$
$\displaystyle\leq~{}L_{g}\sum_{i=k-\delta_{k}}^{k-1}(\frac{1}{\alpha_{i+1-\delta_{i+1}}}\eta_{i}+\frac{1-\alpha_{i-\delta_{i}}}{\alpha_{i-\delta_{i}}}\eta_{i-1})$
$\displaystyle\leq~{}L_{g}\sum_{i=k-\delta_{k}}^{k-1}(\frac{2}{\alpha_{k-1}}\eta_{k-\delta_{k}})$
$\displaystyle=~{}\delta_{k}L_{g}\frac{2\eta_{k-\delta_{k}}}{\alpha_{k-1}}.$

Denote $\beta_{k}\coloneqq\prod_{i=k+1}^{K}(1-\alpha_{i-\delta_{i}})$ with
$\beta_{K}=1$. Unrolling the recursion (32), we have

(35) $\displaystyle e_{K}{}$
$\displaystyle=~{}\beta_{0}e_{0}+\sum_{k=1}^{K}\alpha_{k-\delta_{k}}\beta_{k}\xi_{k-\delta_{k}}+\sum_{k=1}^{K}(1-\alpha_{k-\delta_{k}})\beta_{k}A_{k}+\sum_{k=1}^{K}\alpha_{k-\delta_{k}}\beta_{k}B_{k}.$

Choose learning rates $\alpha_{k}=(\frac{1}{k+1})^{\frac{4}{5}}$ and
$\eta_{k}=\eta_{0}\frac{1}{k+1}$, where $\eta_{0}$ is a constant and we will
show the value later. Using Jensen’s inequality and technical lemmas, we
achieve the following bound

(36) $\displaystyle\mathbb{E}[\|e_{K}\|]~{}\leq$
$\displaystyle~{}\beta_{0}\mathbb{E}[\|e_{0}\|]+\mathbb{E}\left[\left\|\sum_{k=1}^{K}\alpha_{k-\delta_{k}}\beta_{k}\xi_{k-\delta_{k}}\right\|^{2}\right]^{\frac{1}{2}}+\sum_{k=1}^{K}(1-\alpha_{k-\delta_{k}})\beta_{k}\mathbb{E}[\|A_{k}\|]$
$\displaystyle+\sum_{k=1}^{K}\alpha_{k-\delta_{k}}\beta_{k}(\mathbb{E}[\|B_{k}\|]+\mathbb{E}[\|C_{k}\|])$
$\displaystyle~{}\stackrel{{\scriptstyle\eqref{eq:ab_bound}}}{{\leq}}$
$\displaystyle~{}\beta_{0}\sigma_{g}+\left(\sum_{k=1}^{K}\alpha_{k-\delta_{k}}^{2}\beta_{k}^{2}\mathbb{E}\left[\left\|\xi_{k-\delta_{k}}\right\|^{2}\right]\right)^{\frac{1}{2}}+L_{h}\sum_{k=1}^{K}(1-\alpha_{k-\delta_{k}})\beta_{k}\eta_{k-1}^{2}$
$\displaystyle+L_{h}\sum_{k=1}^{K}\beta_{k}\frac{(1-\alpha_{k-\delta_{k}})^{2}}{\alpha_{k-\delta_{k}}}\eta_{k-1}^{2}+2L_{g}\sum_{k=1}^{K}\alpha_{k-\delta_{k}}\beta_{k}\delta_{k}\frac{\eta_{k-\delta_{k}}}{\alpha_{k-1}}$
$\displaystyle~{}\leq$
$\displaystyle~{}\beta_{0}\sigma_{g}+\left(\sum_{k=1}^{K}\alpha_{k-\delta_{k}}^{2}\beta_{k}^{2}\right)^{\frac{1}{2}}\sigma_{g}+L_{h}\sum_{k=1}^{K}\frac{1}{\alpha_{k-\delta_{k}}}\beta_{k}\eta_{k-1}^{2}+2L_{g}\sum_{k=1}^{K}\alpha_{k-\delta_{k}}\beta_{k}\delta_{k}\frac{\eta_{k-\delta_{k}}}{\alpha_{k-1}}$
$\displaystyle~{}\stackrel{{\scriptstyle\eqref{eq:lr_bound}}}{{\leq}}$
$\displaystyle~{}\alpha_{K}\sigma_{g}+\left(\sum_{k=1}^{K}\alpha_{k-\delta_{k}}^{2}\beta_{k}^{2}\right)^{\frac{1}{2}}\sigma_{g}+\frac{9L_{h}}{4}\sum_{k=1}^{K}\frac{\eta_{k}^{2}}{\alpha_{k}}\beta_{k}+2L_{g}\sum_{k=1}^{K}\alpha_{k-\delta_{k}}\beta_{k}\delta_{k}\frac{\eta_{k-\delta_{k}}}{\alpha_{k-1}}$
$\displaystyle~{}\stackrel{{\scriptstyle\eqref{eq:lr_seq_bound}}}{{\leq}}$
$\displaystyle~{}\alpha_{K}\sigma_{g}+c_{1}\sqrt{\alpha_{K}}\sigma_{g}+\frac{9}{4}c_{2}L_{h}\frac{\eta_{K}^{2}}{\alpha_{K}^{2}}+2c_{3}L_{g}\frac{\eta_{K}^{2}}{\alpha_{K}}\bar{\delta},$

where $c_{1}\coloneqq\sqrt{c(\frac{4}{5},\frac{8}{5})}$, $c_{2}\coloneqq
c(\frac{4}{5},\frac{6}{5})$, $c_{3}\coloneqq c(\frac{4}{5},0)$ are constants,
and the values of $c(\cdot,\cdot)$ are defined in Lemma A.3. After plugging
the result into Lemma 4.6 and using Lemma 4.5, we achieve

(37) $\displaystyle J^{\star}-\mathbb{E}[J(\theta_{k+1})]~{}\leq$
$\displaystyle~{}(1-\frac{\sqrt{2\mu}\eta_{k}}{3})\big{(}J^{\star}-\mathbb{E}[J(\theta_{k})]\big{)}+\frac{\eta_{k}}{3}\epsilon_{g}+\frac{8}{3}\eta_{k}\mathbb{E}[\|e_{k}\|]+\frac{L_{g}}{2}\eta_{k}^{2}$
$\displaystyle~{}\stackrel{{\scriptstyle\eqref{eq:error_k}}}{{\leq}}$
$\displaystyle~{}(1-\frac{\sqrt{2\mu}\eta_{k}}{3})\big{(}J^{\star}-\mathbb{E}[J(\theta_{k})]\big{)}+\frac{\eta_{k}}{3}\epsilon_{g}+\frac{L_{g}}{2}\eta_{k}^{2}$
$\displaystyle+\frac{8}{3}\eta_{k}\big{(}\alpha_{k}\sigma_{g}+c_{1}\sqrt{\alpha_{k}}\sigma_{g}+\frac{9}{4}c_{2}L_{h}\frac{\eta_{k}^{2}}{\alpha_{k}^{2}}+2c_{3}L_{g}\frac{\eta_{k}^{2}}{\alpha_{k}}\bar{\delta}\big{)}.$

Unrolling this recursion, we have

(38) $\displaystyle J^{\star}-\mathbb{E}[J(\theta_{K})]~{}\leq$
$\displaystyle~{}\frac{\eta_{0}}{3}\epsilon_{g}+\frac{J^{\star}-\mathbb{E}[J(\theta_{0})]}{(K+1)^{2}}+c_{3}\frac{16\eta_{0}^{2}}{3}\frac{L_{g}}{(K+1)^{\frac{7}{5}}}\bar{\delta}+\frac{\eta_{0}^{2}}{2}\frac{L_{g}}{K+1}+\frac{8\eta_{0}}{3}\frac{\sigma_{g}}{(K+1)^{\frac{4}{5}}}$
$\displaystyle+c_{1}\frac{8\eta_{0}}{3}\frac{\sigma_{g}}{(K+1)^{\frac{2}{5}}}+6c_{2}\eta_{0}^{3}\frac{L_{h}}{(K+1)^{\frac{2}{5}}}.$

Note that, introduced in Lemma 4.4, the discount factor $\gamma$ is contained
in $L_{g}=\mathcal{O}\big{(}(1-\gamma)^{-2}\big{)}$ and
$L_{h}=\mathcal{O}\big{(}(1-\gamma)^{-3}\big{)}$. Comparing with the
definition of $\epsilon_{g}$ in Lemma 4.5, we choose
$\eta_{0}=\frac{3\mu_{F}}{M_{g}}$ for the criteria. Thus, to satisfy
$J^{\star}-\mathbb{E}[J(\theta_{K})]\leq\epsilon+\frac{\sqrt{\epsilon_{bias}}}{1-\gamma}$,
we have the iteration complexity $K=\mathcal{O}({\epsilon}^{-2.5})$. In our
algorithms, the sample complexity is equal to the iteration complexity, which
is also $\mathcal{O}({\epsilon}^{-2.5})$.