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

## Abstract

Abstract To improve the efficiency of reinforcement learning (RL), we propose a novel asynchronous federated reinforcement learning (FedRL) framework termed AFedPG, which constructs a global model through collaboration among N 𝑁 N italic_N agents using policy gradient (PG) updates. To address the challenge of lagged policies in asynchronous settings, we design a delay-adaptive lookahead technique specifically for FedRL that can effectively handle 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 𝒪 ⁢ ( ϵ − 2.5 N ) 𝒪 superscript italic-ϵ 2.5 𝑁 \mathcal{O}(\frac{{\epsilon}^{-2.5}}{N}) caligraphic_O ( divide start_ARG italic_ϵ start_POSTSUPERSCRIPT - 2.5 end_POSTSUPERSCRIPT end_ARG start_ARG italic_N end_ARG ) sample complexity for global convergence at each agent on average. Compared to the single agent setting with 𝒪 ⁢ ( ϵ − 2.5 ) 𝒪 superscript italic-ϵ 2.5 \mathcal{O}(\epsilon^{-2.5}) caligraphic_O ( italic_ϵ start_POSTSUPERSCRIPT - 2.5 end_POSTSUPERSCRIPT ) 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 𝒪 ⁢ ( t max N ) 𝒪 subscript 𝑡 𝑁 \mathcal{O}(\frac{t_{\max}}{N}) caligraphic_O ( divide start_ARG italic_t start_POSTSUBSCRIPT roman_max end_POSTSUBSCRIPT end_ARG start_ARG italic_N end_ARG ) to 𝒪 ⁢ ( ∑ i = 1 N 1 t i ) − 1 𝒪 superscript superscript subscript 𝑖 1 𝑁 1 subscript 𝑡 𝑖 1 \mathcal{O}({\sum_{i=1}^{N}\frac{1}{t_{i}}})^{-1} caligraphic_O ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_N end_POSTSUPERSCRIPT divide start_ARG 1 end_ARG start_ARG italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_ARG ) start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT , where t i subscript 𝑡 𝑖 t_{i} italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT denotes the time consumption in each iteration at agent i 𝑖 i italic_i , and t max subscript 𝑡 t_{\max} italic_t start_POSTSUBSCRIPT roman_max end_POSTSUBSCRIPT is the largest one. The latter complexity 𝒪 ⁢ ( ∑ i = 1 N 1 t i ) − 1 𝒪 superscript superscript subscript 𝑖 1 𝑁 1 subscript 𝑡 𝑖 1 \mathcal{O}({\sum_{i=1}^{N}\frac{1}{t_{i}}})^{-1} caligraphic_O ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_N end_POSTSUPERSCRIPT divide start_ARG 1 end_ARG start_ARG italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_ARG ) start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT is always smaller than the former one, and this improvement becomes significant in large-scale federated settings with heterogeneous computing powers ( t max ≫ t min much-greater-than subscript 𝑡 subscript 𝑡 t_{\max}\gg t_{\min} italic_t start_POSTSUBSCRIPT roman_max end_POSTSUBSCRIPT ≫ italic_t start_POSTSUBSCRIPT roman_min end_POSTSUBSCRIPT ). Finally, we empirically verify the improved performance of AFedPG in four widely-used MuJoCo environments with varying numbers of agents. We also demonstrate the advantages of AFedPG in various computing heterogeneity scenarios.

## 1 Introduction

Policy gradient (PG) methods, also known as REINFORCE (Williams, ), 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 & DeepMind, ), OpenAI’s InstructGPT (Ouyang et al., ), and ChatGPT (GPT-4 (OpenAI, )). PG based methods has also garnered significant attention in several applications including transportation systems Al-Abbasi et al. (), networking Geng et al. (), data-center resource allocation Chen et al. (), video streaming Elgabli et al. (), and robotics Gonzalez et al. ().

Most practical RL applications operate at large scales and rely on a huge amount of data samples for model training in an online behavior (Provost & Fawcett, ; Liu et al., ), which is considered as a key bottleneck in RL (Dulac-Arnold et al., ; Ladosz et al., ). 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., ). 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., ; Lan et al., ; Niknam et al., ; Elgabli et al., ), such as wireless edge devices (Han et al., ; Lan et al., ), Internet of Things (Fang et al., ), and autonomous driving (Kiran et al., ).
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 (Shen et al., ), 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., ; Mothukuri et al., ).

Federated learning (FL) (McMahan et al., ) 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., ; Khodadadian et al., ; Xie & Song, ). FedRL has been studied in the tabular case (Agarwal et al., ; Jin et al., ; Khodadadian et al., ), and for value-function based algorithms (Wang et al., ; Xie & Song, ), where a linear speedup has been demonstrated. For policy-gradient based algorithms, namely FedPG, we note that linear speedup is easy to achieve, given that trajectories collected at different agents can be processed in parallel (Lan et al., ; Ganesh et al., ). 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., ; Chen et al., ), performing synchronous global updates has limitations, as the overall time consumption heavily depends on the slow agents, i.e., stragglers (Badita et al., ; Mishchenko et al., ). 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., ) shows superiority compared to synchronous FL, and recent works (Mishchenko et al., ; Koloskova et al., ) further improve convergence performances with theoretical guarantees.

Challenges: 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. Guaranteeing the global convergence of the algorithm is especially non-trivial under the asynchronous FedRL setting with lagged policies. 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 first-order policy gradient methods. We compare the complexity for convergence in each agent.**
|  | Sample Complexity | Sample Complexity |  |
| --- | --- | --- | --- |
| Methods | (FOSP) | (Global) | Global Time |
| Vanilla PG |  |  |  |
| (Yuan et al., ) | $\mathcal{O}({\epsilon}^{-4})$ | $\mathcal{O}({\epsilon}^{-3})$ | - |
| Normalized PG |  |  |  |
| (Fatkhullin et al., ) | $\mathcal{O}({\epsilon}^{-3.5})$ | $\mathcal{O}({\epsilon}^{-2.5})$ | - |
| FedPG | $\mathcal{O}(\frac{{\epsilon}^{-3.5}}{N})$ | $\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$ | $\mathcal{O}(\frac{t_{\max}}{N}{\epsilon}^{-2.5})$ |
| AFedPG | $\mathcal{O}(\frac{{\epsilon}^{-3.5}}{N})$ | $\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$ | $\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 approach include a delay-adaptive lookahead technique tailored to PG, which addresses the inconsistent arrival times of updates during the training process. This new approach eliminates the second-order correction terms that do not appear in conventional supervised FL, effectively addressing the unique challenges of asynchronous FedRL. 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 which is less than or equal to $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.
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. Unlike (supervised) FL, a second-order correction term (marked blue in equation 30) only occurs in RL because of the sampling mechanism. This updating technique cancels out the second-order correction terms ($(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}
)=0$) and thus assists the convergence analysis. This technique is specifically designed for AFedRL, and not developed by previous FL works.
- 2.
Convergence analysis: This work gives both the global and the first-order stationary point (FOSP) convergence guarantees of the asynchronous 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.
- 3.
Linear speedup in sample complexity: As shown in Table 1, our AFedPG approach 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 of our method with respect to the number of agents $N$.
- 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 improvement is significant in large-scale federated settings with heterogeneous delays ($t_{\max}\gg t_{\min}$).
- 5.
Experiments under the MuJoCo environment: We empirically verify the improved performances of AFedPG in four 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, accompanied by theoretical convergence guarantees. This new setting necessitates us to deal with the lagged policies under a time-varying data scenario depending on the updated 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$.

## 2 Related Work

In this section, 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. (), 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. (), a PG with momentum method is proposed with convergence rate $\mathcal{O}({\epsilon}^{-3})$ for the local convergence. The authors of Ding et al. () 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. (), a normalized PG technique is introduced and improves the global convergence rate to $\mathcal{O}({\epsilon}^{-2.5})$. In Mondal & Aggarwal (), 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. (), 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. (), the asynchronous analysis is extended to the vertical FL with a better convergence performance compared to the synchronous setting. In Dun et al. (), a dropout regularization method is introduced to handle the heterogeneous problems in A-FL. About the same time, recent works (Mishchenko et al., ; Koloskova et al., ) 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, leveraging the proposed delay-adaptive lookahead technique.

FedRL: For value-function based algorithms, Jin et al. (); Woo et al. () analyze the convergence performances with environment heterogeneity. Salgia & Chi () analyzes the trade-off between sample and communication complexity. Khodadadian et al. () shows a linear speedup with respect to the number of agents. Zhang et al. () extends the result with linear function approximation. However, all of the above works are limited to tabular or linear approximation analysis (without deep learning). For actor-critic based method, Wang et al. () analyzes the convergence performances with the linear function approximation. Mnih et al. () builds a practical system to implement the neural network approximation. Yang et al. () analyzes the sample complexity in the multi-task setting. In Xie & Song (), it adds KL divergence and experimentally validates the actor-critic based method with neural network approximation. For policy-based methods, Chen et al. () gives a convergence guarantee for the vanilla FedPG. Lan et al. () further shows the simplicity compared to the other RL methods, and a linear speedup has been demonstrated in the synchronous setting. Further, optimal sample complexity for global optimality in federated RL even in the presence of adversaries is studied in Ganesh et al. (). However, with 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., ). 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.

## 3 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

$$ $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].$ (1) $$

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

$$ $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].$ (2) $$

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

$$ $\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],$ (3) $$

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:

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

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

$$ $\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],$ (5) $$

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

$$ $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}).$ (6) $$

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 equation 4 in a FL setting.

## 4 Proposed Asynchronous FedPG

Figure: 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}}$.
Refer to caption: x1.png

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 4.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 4.2 .

(Delay) In the $k$-th global iteration, we denote the delay of the applied gradient as $\delta_{k}\in\mathbb{N}$ (an integer), 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 delay can be expressed as

$$ $\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{)}.$ (7) $$

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 the 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 B.8 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 B.6, we are able to bound the error as $\|\theta_{k-1}-\theta_{k}\|=\eta_{k-1}$. The details of the boundaries are shown in equation 32.

Delay-adaptive lookahead at the agent: In Step 2 of Algorithm 2 (in blue), we design a delay-adaptive lookahead update technique, which is designed specifically for asynchronous FedPG. It operates as follows:

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

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

In equation 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:

$$ $(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,$ (9) $$

and thus assists the convergence analysis. The details of the derivation are shown in Appendix B.4 marked in blue.

Figure: Algorithm 1 AFedPG: Server.

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

###### Definition 4.1 .

###### Definition 4.2 .

## 5 Convergence Analysis

In this section, we derive the convergence rates of AFedPG with the following criterions for the FOSP and global convergence, respectively.

FOSP Criterion: We focus on the first-order stationary convergence, i.e., finding the parameter $\theta$ s.t. $\|\nabla J(\theta)\|\leq\epsilon$.

Global Criterion: 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.

We use several standard assumptions listed in Appendix B.1. Based on these assumptions, the convergence rates of AFedPG are given in Theorem 5.1 and 5.2.

###### Theorem 5.1 .

(FOSP) Let Assumption B.1 hold. With suitable learning rates $\eta_{k}$ and $\alpha_{k}$, after $K$ global iterations, AFedPG satisfies

$$ $\displaystyle\mathbb{E}[\|\nabla J(\theta_{K})\|]~{}\leq~{}\mathcal{O}\big{(}{ K^{-\frac{2}{7}}}\cdot(1-\gamma)^{-3}\big{)}+\frac{\sqrt{\epsilon_{{\rm bias}} }}{1-\gamma}.$ (10) $$

To satisfy $\nabla J(\theta_{K})\leq\epsilon$, we need $K=\mathcal{O}(\frac{\epsilon^{-3.5}}{(1-\gamma)^{7.5}})$ iterations. As only one trajectory is required in each iteration, the number of collected trajectories is equal to $K$, i.e., the sample complexity is $\mathcal{O}(\frac{\epsilon^{-3.5}}{(1-\gamma)^{7.5}})$.

###### Theorem 5.2 .

(Global) Let Assumption B.1 and B.2 hold. With suitable learning rates $\eta_{k}$ and $\alpha_{k}$, after $K$ global iterations, AFedPG satisfies

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

where $\epsilon_{{\rm bias}}$ is from equation 13. Thus, to satisfy $J^{\star}-J(\theta_{K})\leq\epsilon+\frac{\sqrt{\epsilon_{{\rm 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 less 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 5 in Appendix A.1. As the server only operates one simple summation, without loss of generality, the time consumption at the server side is negligible.

###### Theorem 5.1 .

###### Theorem 5.2 .

## 6 Experiments

### 6.1 Setup

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

Measurement: All convergence performances are measured over $10$ runs with random seeds from 0 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 in Appendix A.1. We follow the practical settings in stable-baselines3 (Raffin et al., ) to update models with generalized advantage estimation (GAE) ($0.95$) (Schulman et al., ) in our implementation. We use PyTorch (Paszke et al., ) 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 then consider the synchronous FedPG method as a baseline to observe the impact of asynchronous updates on enhancing the time complexity. To see the effect of our delay-adaptive technique, we also consider the performance of AFedPG without the delay-adaptive updates, namely vanilla in Figure 4. Finally, we consider A3C (Mnih et al., ), an asynchronous method designed for RL. We note that only a few prior works could be used on the federated PG problem, e.g., A3C, 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.
Rewards: the average trajectory rewards collected at each iteration;
- 2.
Convergence: rewards versus iterations during the training process;
- 3.
Time consumption: global time with certain numbers of collected samples.

Figure: (a) Swimmer-v4
Refer to caption: extracted/5896638/figures/swimmer_img.png

### 6.2 Results

Sample complexity improvement: 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 3, 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 four 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.

Figure: (a) Swimmer-v4
Refer to caption: extracted/5896638/figures/swimmer.png

Figure: (a) Swimmer-v4
Refer to caption: extracted/5896638/figures/swimmer_comp_leg.png

Speedup in 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 4, 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}$, $1.6\times 10^{4}$, $8\times 10^{4}$, and $1.2\times 10^{5}$ for the Swimmer-v4 task, the Hopper-v4 task, the Walker2D-v4 task, and the Humanoid-v4 task individually when $N=8$. When $N=4$, the numbers are halved. In all four environments, AFedPG has much lower time consumption compared to the synchronous FedPG, confirming the enhancement in terms of time complexity. Compared to the A3C baseline, AFedPG achieves much higher rewards with less variance.

Ablation study: In Figure 4, we also observe the impact of our delay-adaptive lookahead approach. It is seen that the vanilla scheme without delay-adaptive lookahead technique does not provide a satisfactory performance, confirming the importance of the proposed approach. We also analyze the effect of computation heterogeneity in Appendix A.3.

## 7 Discussions

### 7.1 Limitations

- 1.
While the system is robust to stragglers, exploring the robustness, e.g., fault-tolerance, with malicious agents is open;
- 2.
It is worth to study whether the asynchronous method is compatible with other methods, e.g., local update, quantization, and low-rank decomposition, to improve communication efficiency in the deep RL setting;
- 3.
How to extend this approach to second-order policy optimization methods, e.g., natural policy gradient methods, is open;
- 4.
In the experimental study, limited by computing resources, it would be more persuasive to extend the number of federated agents to a larger scale.

### 7.2 Conclusion

We proposed AFedPG, a novel asynchronous FedRL framework which updates the global model using PGs from multiple agents. To handle the challenge of lagged (heterogeneous) policies in the asynchronous setting, we designed a delay-adaptive lookahead technique and used normalized updates to integrate PGs. We then analytically characterized the convergence bound of AFedPG and showed both global and first-order stationary point convergence guarantees. We also showed that AFedPG achieves a 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 for global convergence. Compared to the SOTA result in the single agent setting, i.e. 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 complexity from $\mathcal{O}(\frac{t_{\max}}{N})$ to $\mathcal{O}(={\sum_{i=1}^{N}\frac{1}{t_{i}}})^{-1}$, where $t_{i}$ denotes the time complexity in each iteration at the agent $i$, and $t_{\max}$ is the largest one. The latter complexity $\mathcal{O}({\sum_{i=1}^{N}\frac{1}{t_{i}}})^{-1}$ is always smaller than the former one, and this improvement is 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 various baselines in four MuJoCo environments with different $N$. We also demonstrated improvements with different computing heterogeneity. It is shown that AFedPG achieves speedup in terms of both sample complexity and time complexity, especially in scenarios with high computing power heterogeneity.

## Reproducibility Statement

In this statement, we discuss the efforts that have been made to ensure reproducibility.

For theoretical results, we clearly explain all assumptions in Appendix B.1, and a complete proof of the lemmas and theorems in Appendix B.

For algorithms, we provide the pseudocode in Algorithm 1 and Algorithm 2.

For datasets used in the experiments, we use open source datasets, and describe them in Section 6.1 and Appendix A.2.

## Appendix A Experimental Supplement

### A.1 Comparison to the Synchronous Setting

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 5. As the server only operates one simple summation, without loss of generality, the time consumption at the server-side is negligible.

Figure: Figure 5: Comparison of time consumptions between synchronous and asynchronous approaches. The circled numbers denote the indices of global steps.
Refer to caption: x2.png

### A.2 Experimental Settings

Environmental details are described in Table 2. Policies are parameterized by fully connected multi-layer perceptions (MLPs) with settings listed in Table 3.

**Table 2: Detailed descriptions of the four 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$ |
|  | Two-dimensional |  |  |
| Walker2D-v4 | bipedal robot | $6$ | $17$ |
|  | 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 | Walker2D-v4 | Humanoid-v4 |
| MLP | $64\times 64$ | $256\times 256$ | $512\times 512$ | $512\times 512\times 512$ |
| Activation function | ReLU | ReLU | ReLU | ReLU |
| Output function | Tanh | Tanh | Tanh | Tanh |
| Learning rate ($\alpha$) | $1\times 10^{-3}$ | $1\times 10^{-3}$ | $1\times 10^{-3}$ | $1\times 10^{-3}$ |
| Discount ($\gamma$) | $0.99$ | $0.99$ | $0.99$ | $0.99$ |
| Timesteps ($T$) | $2048$ | $1024$ | $1024$ | $512$ |
| Iterations ($K$) | $1\times 10^{3}$ | $2\times 10^{3}$ | $5\times 10^{3}$ | $1.5\times 10^{4}$ |
| Learning rate ($\eta$) | $3\times 10^{-4}$ | $1\times 10^{-4}$ | $5\times 10^{-5}$ | $1\times 10^{-5}$ |

### A.3 Supplementary Results

Effect of computation heterogeneity: 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 (1) One straggler, which is one agent has $t_{\min}$ time consumption, and all the other agents have $t_{\max}$ time consumption. This is the scenario with the largest speedup. (2) One leader, which is one agent has $t_{\max}$ and the others have $t_{\min}$. This is the scenario with the smallest speedup.

In Figure 6, the results show that the speedup increases as the heterogeneity ratio $\frac{t_{\max}}{t_{\min}}$ increases. With one leader, as more agents participate, the speedup approximately decreases to a quadratic function w.r.t. the time heterogeneity ratio. With one straggler, 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 RL system, particularly in scenarios with extreme stragglers (The ratio is large: $t_{\max}\gg t_{\min}$).

Figure: (a) With one straggler
Refer to caption: extracted/5896638/figures/speedup_straggler.png

## Appendix B Proofs

### B.1 Assumptions

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

###### Assumption B.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.
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
$\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\|.$
(12)
- 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 0 in practice. Thus, we follow previous works Liu et al. (); Agarwal et al. (); Ding et al. (); Huang et al. () with an assumption on the expressivity of the policy parameterization class.

###### Assumption B.2 .

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

$$ $\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_{{\rm bias}},$ (13) $$

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_{{\rm bias}}$ can be very small with rich neural network parameterization (Wang et al., ), and 0 0 with a soft-max parameterization (Ding et al., ).

###### Assumption B.1 .

###### Assumption B.2 .

### B.2 Technical Lemmas

###### Lemma B.3 .

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

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

###### Lemma B.4 .

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

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

###### Proof.

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

Straightforwardly, we have

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

∎

###### Lemma B.5 .

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

$$ $\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}},$ (18) $$

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 with specified $p$ and $q$, 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{)}$.

###### Lemma B.3 .

###### Lemma B.4 .

###### Proof.

###### Lemma B.5 .

### B.3 Key Lemmas

We list four useful lemmas to construct the proof of Theorem 5.2 and Theorem 5.1.

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

###### Lemma B.6 .

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

$$ $\displaystyle\|\nabla J(\theta)-\nabla J(\theta^{\prime})\|~{}\leq$ $\displaystyle~{}L_{g}\|\theta-\theta^{\prime}\|,$ (19) $\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 B.1 and B.2, we utilize the result in Ding et al. () as the Lemma B.7.

###### Lemma B.7 .

(Relaxed weak gradient domination) Under Assumptions B.1 and B.2, it holds that

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

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

Based on Lemma B.6, we derive our milestone (new), the ascent lemma with delayed updates, as follows:

###### Lemma B.8 .

(Ascent Lemma with Delay) Under Assumptions B.1, it holds that

$$ $\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},$ (21) $$

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

$$ $\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}$ (22) $\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

$$ $\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}}\|}$ (23) $\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}\|}$ $\displaystyle\leq~{}-\frac{1}{3}\|\nabla J(\theta_{k})\|.$ $$

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

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

Combining these two conditions, and plugging the result into equation 22, the lemma can be proved as follows

$$ $\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}$ (25) $\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 B.9. This lemma gives the boundary (our result) of delays as a corollary of the result in Koloskova et al. ().

###### Lemma B.9 .

The average delay $\bar{\delta}$ depends on the average concurrency $\bar{\omega}$, and they can be upper bounded as

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

###### 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

$$ $\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}.$ (27) $$

We note that there is no delay at the initial step (0 0-th iteration) of the algorithm. Therefore, we have $\delta^{i}_{0}=0$ for all agents. Unrolling the above expression, at the $K$-th step, we have

$$ $\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}.$ (28) $$

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

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

∎

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

###### Lemma B.6 .

###### Lemma B.7 .

###### Lemma B.8 .

###### Proof.

###### Lemma B.9 .

###### Proof.

### B.4 Proof of Theorem 5.2 (Global Convergence Rate)

Under Assumption B.1 and Assumption B.2, we derive the global convergence rate of the proposed AFedPG.

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

$$ $\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{)}$ (30) $\displaystyle+\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{)}$ $\displaystyle+\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}+\alpha_{k-\delta_{k}}\big{(}\nabla J(\widetilde{\theta}_{k-\delta_{ k}})-\nabla J(\widetilde{\theta}_{k})\big{)}$ $\displaystyle+(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})- \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\ref{eq:delay_adaptive}}}{{=}}$ $\displaystyle~{}\alpha_{k-\delta_{k}}\xi_{k-\delta_{k}}+(1-\alpha_{k-\delta_{k }})e_{k-1}+\alpha_{k-\delta_{k}}\big{(}\nabla J(\widetilde{\theta}_{k-\delta_{ k}})-\nabla J(\widetilde{\theta}_{k})\big{)}$ $\displaystyle+(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})- \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 0 according to our updating rules (delay-adaptive lookahead update) in Step 2 of Algorithm 2. We design this technique to cancel out the second-order terms, and thus achieve the desired convergence rate.

Next, we denote

$$ $\displaystyle A_{k}~{}\coloneqq$ $\displaystyle~{}\nabla J(\theta_{k-1})-\nabla J(\theta_{k})+\nabla^{2}J(\theta _{k})(\theta_{k-1}-\theta_{k}),$ (31) $\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 B.6 and the non-increasing learning rates, we have

$$ $\displaystyle\|A_{k}\|{}$ $\displaystyle\leq~{}L_{h}\|\theta_{k-1}-\theta_{k}\|^{2}=L_{h}\eta_{k-1}^{2},$ (32) $\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 equation 30, we have

$$ $\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}.$ (33) $$

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

$$ $\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 }\|]$ (34) $\displaystyle+\sum_{k=1}^{K}\alpha_{k-\delta_{k}}\beta_{k}(\mathbb{E}[\|B_{k} \|]+\mathbb{E}[\|C_{k}\|])$ $\displaystyle~{}\stackrel{{\scriptstyle\ref{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\ref{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\ref{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 B.5. After plugging the result into Lemma B.8 and using Lemma B.7, we achieve

$$ $\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}$ (35) $\displaystyle~{}\stackrel{{\scriptstyle\ref{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

$$ $\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}$ (36) $\displaystyle+\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}}}.$ $$

Note that, introduced in Lemma B.6, 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 B.7, 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_{{\rm 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})$.

### B.5 Proof of Theorem 5.1 (FOSP Convergence Rate)

Under Assumption B.1, we derive the first-order stationary convergence rate of AFedPG. Notably, the FOSP convergence does not require Assumption B.2, which makes assumptions on the neural network approximation error.

Denote the expectation of average gradients as $\mathbb{E}\|J(\bar{\theta}_{K})\|\coloneqq\frac{\sum_{k=1}^{K}\eta_{k}\mathbb{
E}\|\nabla J(\theta_{k})\|}{\sum_{k=1}^{K}\eta_{k}}$. Rearranging Lemma B.8
(Ascent Lemma with Delay) and summing up the inequality, we have

$$ $\displaystyle\mathbb{E}\|J(\bar{\theta}_{K})\|~{}\leq{}$ $\displaystyle\frac{3}{\sum_{k=1}^{K}\eta_{k}}\Big{(}J^{\star}-\mathbb{E}[J( \theta_{0})]\Big{)}+\frac{8}{\sum_{k=1}^{K}\eta_{k}}\sum_{k=1}^{K}\eta_{k} \mathbb{E}[\|e_{k}\|]$ (37) $\displaystyle+\frac{3L_{g}}{2\sum_{k=1}^{K}\eta_{k}}\sum_{k=1}^{K}\eta_{k}^{2}.$ $$

Choose $\alpha_{k}=(\frac{1}{k+1})^{\frac{4}{7}}$ and $\eta_{k}=\eta_{0}(\frac{1}{k+1})^{\frac{5}{7}}$. Plug in the result into equation 34 that we have shown in Appendix B.4, we have

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

To satisfy $\mathbb{E}\|J(\bar{\theta}_{K})\|\leq\epsilon$, we have the iteration complexity $K=\mathcal{O}({\epsilon}^{-3.5})$. In our algorithms, the sample complexity is equal to the iteration complexity, which is also $\mathcal{O}({\epsilon}^{-3.5})$.

Notably, this result does not rely on Lemma B.7 and Assumption B.1. The norm of the average gradient is approaching an arbitrarily small value during the training process, regardless of the function approximation error $\epsilon_{\rm bias}$.

## Appendix C Further Discussions

### C.1 Difference between FL, FedRL, and AFedRL

Unlike supervised FL where local datasets are fixed or pre-specified, in RL, agents collect new samples in each iteration based on the current local policies. The new data are collected with dynamic dependencies, which do not appear in all prior FL and A-FL works.

In synchronous FedRL, each agent collects samples according to the same global policy $\pi_{\theta}$. However, in AFedRL, even if all agents have an identical environment, each agent collects samples according to different policies $\tau_{k}\sim p(\cdot|\pi_{\theta_{k}})$, because of the delay. This dynamic nature makes both the problem itself and the theoretical analysis challenging. We propose a new delay-adaptive model aggregation strategy to tackle these unique challenges of FedRL.

Moreover, data collected by each agent are naturally (non-manually controlled) heterogeneous. Despite having identical environments, agents collect data according to their own (different) policies, a fundamental difficulty that our AFedPG paper solves, as verified theoretically and empirically.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: See my questions from the previous section.
soundness: 3
strengths: Contributions claimed in the paper include,

--Proposes a new asynchronous FedRL algorithm (AFedPG) tailored to policy gradient updates, using a delay-adaptive lookahead technique to manage lagging updates in asynchronous settings.

-- Provides theoretical convergence guarantees, including global and first-order stationary point convergence, for the asynchronous federated policy-based RL.

-- Achieves a linear speedup in sample complexity with an increasing number of agents, reducing the per-agent complexity from $O(\epsilon^{-2.5})$ to $O(\epsilon^{-2.5}/N)$. (However, the proof is unclear and it is hard to see how the authors can avoid a dependence on the delay in the sample complexity.)

  -- Improves time complexity over synchronous methods by reducing the dependency on the slowest agent’s computational time, with gains highlighted in scenarios of high computational heterogeneity.

-- Empirically validates AFedPG's performance in various MuJoCo environments, demonstrating faster convergence (time-wise) over synchronous FedPG and other baselines.
summary: The paper aims to enhance the efficiency of federated reinforcement learning (FedRL) by introducing an asynchronous framework, AFedPG, which leverages policy gradient (PG) updates from multiple agents without requiring synchronized updates. This approach is designed to address issues related to delayed updates and computational heterogeneity, which are common challenges in federated setups, especially with varying agent speeds and capacities.
weaknesses: In general, the paper is not clearly written. I don't see how the authors were able to avoid a dependence on the delay in their sample complexity. Their current derivations for bounding the error term (from the delay) have many typos and are hard to follow. Specific concerns/questions of the paper include:

-- Step 4 in Algorithm 2 is confusing. Where does the local agent get $d_{k-1}$ from? Did the authors mean $d_{k-\delta_k}$ instead? If the authors meant $d_{k-1}$, the current algorithm descriptions do not mention how $d_{k-1}$ can be made available to agent $i$.

-- A major component of the proof is bounding the error term $e_k := d_{k-\delta_k} - \nabla J(\theta_k)$, which arises from the delay. Equation (30) in the appendix provides a derivation of how $e_k$ can be expressed (and subsequently bounded). However, there seems to be serious typos in equation (30). For instance, in the first line, I am not sure why a term $d_{\delta_{k-1}}$ appears, when $e_k$ is actually $d_{k-\delta_k} - \nabla J(\theta_k)$. This makes it difficult to follow the argument in this derivation, and there is also no explanation of the derivation, which might have made it easier to follow the argument flow. Given that this is a particularly important term to bound to derive either first-order or global convergence rates, the authors should make an effort to clarify and explain these derivations.
 
-- The current convergence bound seems to have no dependence on the delay in the network, which is $N$ in the worst-case (e.g. assuming cyclic update). This is somewhat confusing to me; intuitively, even with a delay-adaptive step size for the $\theta$ update, there should be some price to pay for a cyclic delay structure. My current understanding is that perhaps the authors were able to bypass the dependence on the delay by their handling of the gradient-bias term $e_k$ (caused by the delay). However, given that the current derivation of bounding $e_k$ is highly unclear (see my earlier point), it is not clear to me whether the result as currently stated actually holds. If it holds, the authors should make it a lot clearer how and why they are able to avoid the dependence on the delay, as this is a key part of their contribution. 

-- The definition of the global time is unclear. The authors should make it more precise, and have a formal statement and proof of their current stated bound on the global time being $O(\frac{\bar{t}\epsilon^{-2.5}}{N})$, where $\bar{t} = \frac{1}{\sum_{i=1}^N \frac{1}{t_i}}$. 

--On a related note, the definition of $t_i$ seems a little unclear to me, given that at different iterations, agent $i$ might require varying amounts of time (i.e. there shouldn't be a single time complexity $t_i$ for each agent $i$). The authors should make their definition of what they mean by $t_i$ more precise.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 4. Why does Proof of theorems lack the index of agent i? Since the server does not aggregate gradients or parameters from agents periodically, Fed RL is not applicable in this paper. Besides, it is just similar to [3]. Notations also make confusing. 

5. What’s the technical contributions beyond existing FedRL? Technical differences of AFedPG compared to FedPG seems limited.

6. Authors first get the results of global convergence, then FOSP results. Why FOSP results are placed first in main text?
soundness: 3
strengths: 1. Convergence results are provided. 
2. Asynchronous federated reinforcement learning framework is proposed.
summary: This paper proposes an asynchronous federated reinforcement learning framework. Then it introduces a delay-adaptive lookahead technique and employs normalized updates to integrate policy gradients to deal with the challenges brought by the asynchrony. Furthermore, the paper provides the theoretical global convergence bound. The experiments verify the improved performance of the proposed algorithm.
weaknesses: 1. This paper is not built on a federated framework. FedRL is designed to address heterogeneous environments and allow local agents to perform multiple iterations [1,2]. However, these are not considered in this paper.

[1] Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments, ICML24.
[2] Federated Reinforcement Learning with Environment Heterogeneity, AISTATS22.

2. This work lack necessary comparisons with current works. Actor-critic is a policy-based approach. This paper needs careful comparisons in details with [3] since both emphasize the asynchrony, not mentioned in Introduction briefly.
[3] Towards understanding asynchronous advantage actor-critic: convergence and linear speedup.

3. Technical contributions are limited. Authors claimed that even if all agents have an identical environment, each agent collects samples according to different policies because of the delay. This dynamic nature makes both the problem itself and the theoretical analysis challenging. However, this is somehow solved by [3]. The challenges brought by the features of Fed RL are not considered in this paper.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: .
soundness: 3
strengths: 1. The work provides asynchronous synchronization updates tailored for federated RL.
2. The work presents a tight sample complexity analysis of the proposed algorithm, demonstrating a linear speedup that aligns with the single-agent state-of-the-art.
summary: This work investigates federated reinforcement learning with asynchronous synchronizations to improve the time complexity. They introduce the asynchronous federated policy gradient (AFedPG), which tackles lagged policies using a delay-adaptive lookahead. In addition, they present a sample complexity analysis of the algorithm, demonstrating a linear speedup compared to the single-agent scenario.
weaknesses: 1. The application of asynchronous updates from federated learning to federated policy gradients appears to be incremental, especially since much of the supervised federated learning literature has examined how to manage lagged models, while existing federated reinforcement learning research focuses on addressing the dynamic nature of reinforcement learning in federated settings.
2. It appears that a momentum method was introduced for federated policy gradients in heterogeneous environments to handle online sample collections dependent on $\theta$ in [1]. While the paper emphasizes its novelty by discussing the momentum design (delay-adaptive lookahead), which differs from asynchronous supervised federated learning, it remains uncertain whether this concept is genuinely unique in comparison to prior literature in federated reinforcement learning, which also addresses the issue of online sample collections that vary with policy updates.

[1] Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments, Wang et al., ICML 2024

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: * In Line 268, you mention *the set of active agents*. Does it mean the agents that can apply global iteration? If so, then the following paragraph mentions that *only one gradient to update the model from the agent who has finished its local computation.* In other words, does it allow more than one agent to apply policy gradient at the same iteration?
* For Figure 3, could you please let PG (N=1)  and AfedPG (N=2) train even longer to see if they can converge to a similar reward as the other two? If they cannot, I feel curious as to why they can't. 
* Is there any analysis or experiment of communication cost?
soundness: 3
strengths: * Numerical experiments on MuJoCo demonstrate impressive results that support the better time complexity of the proposed method
* Both FOSP and global sample complexity match the state-of-the-art while the global time complexity can have a tighter bound with heterogeneous arrival times
summary: This paper proposes a policy-based federated RL with an asynchronous setting to handle varying arrival times of policy gradient updates. Specifically, the authors analyzed the global and FOSP sample complexity as well as time complexity with a concrete algorithm design. The authors also provided simulation results on MuJoCo, which tackle sample and time complexity issues separately. The proposed method is more practical and can be adaptable to various computing heterogeneity scenarios.
weaknesses: * The ultimate goal of federated RL is to find the trade-off between sample and communication complexity while the emphasis of this work on communication complexity/strategy is limited and not clear to me. Please elaborate more about what the threshold or event triggered for any agent to have the synchronization/communication with the server in your proposed framework.
* There are some typos in the manuscript. For example, you write *MoJuCo* instead of *MuJoCo* in the caption of Figures 3 and 4.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: See the weakness.
soundness: 3
strengths: 1. The proposed framework handles the delayed arrival of policy-gradient and reduces the waiting time compared to the algorithm for the homogeneous setting.

2. The authors propose their special step size designs to cancel out a second-order error term when conducting the error analysis, which serves as a technical novelty.

3. Numerical experiments demonstrate that the authors accelerate the training process compared to the synchronous algorithm.
summary: This paper proposes an asynchronous federated reinforcement learning framework termed AFedPG for the policy gradient algorithm. It designs a delay-adaptive lookahead technique that can effectively handle heterogeneous arrival times of policy gradients. This work shows theoretical linear speedup in terms of the norm for policy gradient and verifies the speedup effect numerically.
weaknesses: 1. Issues in Section 4. The authors are encouraged to explain more about the concepts of active agents, concurrency, and delay. In algorithm 2, the authors are encouraged to explain more details about model sharing from the central server as how the agents hold $d_{k-1}$ and $\theta_{k-1}$ is not explicitly explained. In addition, the authors are encouraged to explain the relationship between their algorithms and the single-agent and homogeneous counterparts in the literature. Last, the authors assume that the agents can sample a trajectory with infinite lengths, which is impossible in practice. The authors are recommended to explain more on such assumptions.

2. Issues in Section 5. (a) In equations 10 and 11, RHS contains a constant term that does not depend on $K$, which originates from the function approximation error as indicated in the appendix. The authors are encouraged to explain this term in the main paper. (b) The authors are encouraged to explain how they get the total waiting time in line 394.

3. Issues in Appendix B (proofs). (a) The authors are encouraged to explain more about the definitions and notations that are already established in the literature, for example, $F_\rho(\theta),\mu_F,\sigma_g$. (b) In Lemmas B.6 and B.7, the authors are recommended to point out the cited lemma in the references. (c) The second term in line 1084 should be $(\mathbb{E}\cdot^2)^{1/2}$. (d) In equations 37 and 38, there are typos related to $\nabla$. (e) In line 1028, there is a typo related to $d_{\delta_{k-1}}$.

Meta-review: This paper introduces AFedPG, an asynchronous framework for federated reinforcement learning (FedRL), which utilizes policy gradient (PG) updates from multiple agents without requiring synchronized updates. The approach is specifically designed to address challenges in federated setups, such as delayed updates and computational heterogeneity due to varying agent speeds and capacities. The authors provide theoretical results, including first-order and global convergence rates, and conduct simulation experiments on MuJoCo to demonstrate improvements in sample and time complexity.

The reviewers raised several common concerns, including the need for clarification of notation and presentation, the absence of a communication cost analysis, and the novelty of the techniques. In their rebuttal, the authors successfully addressed these concerns. They clarified misunderstandings and corrected typos, leading to improved reviewer scores. Additionally, the inclusion of communication cost comparisons in the experiments strengthened the paper’s relevance to the federated setting. Regarding technical novelty, the authors convincingly argued that there were no prior results on the convergence of federated policy gradients for general policy parameterizations. Furthermore, their theoretical results outperform those of single-agent settings by achieving a linear speedup. These contributions, combined with the clarification of previously ambiguous points, make the paper a valuable addition to the FedRL literature. Based on these factors, I recommend weak acceptance of this paper.

Decision: Accept (Poster)