Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis
Authors: Guangchen Lan
Dong-Jun Han
Abolfazl Hashemi
Vaneet Aggarwal
Christopher Brinton
Venue: ICLR 2025 Poster (2025)
Keywords: Reinforcement Learning
Federated Learning
Asynchronous System
Primary area: reinforcement learning
TL;DR: We propose a asynchronous federated reinforcement learning framework, which constructs a global policy through collaboration among $N$ agents using policy gradient (PG) updates. It improves both sample and time complexity.

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$ 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 $\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$ sample complexity for global convergence 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}({\sum_{i=1}^{N} \frac{1}{t_{i}}})^{-1}$, where $t_{i}$ denotes the time consumption in each iteration at 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 becomes significant in large-scale federated settings with heterogeneous computing powers ($t_{\max}\gg t_{\min}$). 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.

Published as a conference paper at ICLR 2025
ASYNCHRONOUS FEDERATED REINFORCEMENT LEARNING WITH POLICY GRADIENT UPDATES: ALGO- RITHM DESIGN AND CONVERGENCE ANALYSIS
Guangchen Lan', Dong-Jun Han?, Abolfazl Hashemi', Christopher G. Brinton
Vaneet Aggarwal'
Purdue University, West Lafayette, IN, USA, Yonsei University, Seoul, South Korea (1an44, abol fazl, vaneet, cgb (eggb/@puruee.com edu, ddjh@oonsel. ac.
ABSTRACT
To improve the efficiency of reinforcement learning (RL), we propose novel asyn- chronous federated reinforcement learning (FedRL) framework termed AFedPG, which constructs a global model through collaboration among N agents using policy gradient (PG) updates. To address the challenge of lagged policies in asyn- chronous settings, we design a delay-adaptive lookahead technique specifically for FedRI. 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 2.6
and time complexity. Specifically, our AFedPG method achieves O N sample complexity for global convergence each agent on average. Compared the single agent setting with ((c-2.5) sample complexity. it enjoys linear speedup with respect the number of agents. Moreover, compared synchronous FedPG, AFedPG improves the time complexity from O famux) to O 1,)-, where t denotes the time consumption in each iteration at agent i, and max is the largest one. The latter complexity O ) and this improvement becomes significant in large-scale federated settings with heterogeneous computing powers (4max mmin).. Finally, 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 is always smaller than the former one,
INTRODUCTION
Policy gradient (PG) methods, also known as REINFORCE (Williams) 1992). are widely used to solve reinforcement learning (RL) problems across range of applications, with recent notable examples including reinforcement learning from human feedback (RLHF) Google's Gemma (Team) DeepMind 2024). OpenAl's InstructGPP (Ouyang al. 2022). and ChatGPT (GPT-4 (OpenAI 2023)). PG-based methods has also garnered significant attention in several applications including
transportation systems (Al-Abbasi et 2019), networking (Geng et al. 2023) data-center resource
allocation (Chen et al. 2023 2024a] Zhang et al. 2023). streaming (Elgabli et al. 2024 Liu & Zhu
2023). roboties (Gonzalez et 2023), and diffusion models (Zhang et al.) (2024b).
Most practical RL applications operate at large scales and rely on huge amount of data samples for
model training in online behavior (Provost & Fawceti 2013 Liu et al.)
202T). which is considered
as a key bottleneck in RL. (Dulac-Amold et al.) 2021 Ladosz et al.) 2022). To reduce sample
complexity while enabling training on massive data, conventional approach involves transmitting locally collected samples from distributed agents to 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 large
training time is intolerable (Brinton et al. 2025) Chu et al.) 2024a Yuan et al. [0024] Niknam et al.
2020 Elgabli al. 2020), such wireless edge devices (Lan al. 2023a Ching et al.
2023 2024

---

Published as a conference paper at ICLR 2025
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 (Global)
Methods
Global Time
(FOSP)
Vanilla PG
0
O(E
(Yuan et al. 2022
Normalized PG
(66-2.))
Fatkhullin et al.
2023
FedPG
O(=
0( 3.3
O(=N))
0 Opprpe -2.5)
N
AFedPG
3.5 0 N -(
x(
((=))) N
Ofte -2.5) 2.5)
cloud computing (Chen et al. 2024b; Xu et al. 2024), autonomous driving (Kiran et al. 2022). and financial applications (Long et al., 22024 Liang al. 2024). 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 al., 2023). resulting
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) (McMahan et al. 2017) offers a promising solution to the above challenges distributed setting. FL. instead directly transmitting the raw datasets to the central server, agents only communicate locally trained model parameters (or gradients) with the server. In Chu ict al. (2025 2024b). shows that FL could achieve fairness among different agents. 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 & Song 2023). FedRL has been studied in the tabular case (Agarwal al. b021b Jin al. [022]] Khodadadian al. 2022), and for falue-function based algorithms (Wang et al. 2024bb Xie & Song, 2023), where linear speedup has been demonstrated. For policy- gradient based algorithms, namely FedPG, we note that a linear speedup easy achieve, given that trajectories collected at different agents can be processed in parallel (Lan et al. 2023b). Ganesh al. (2024a) proposed a policy gradient- based approach that is robust to adversarial agents and achieves optimal sample complexity in the presence of adversaries. [iu & Zhu (2022) analyzes the performances in the multi-agent setting. Zhu al. (2224) extends the result to the multi-task setting. However, policy-gradient based FedRL has not been well studied in terms of global (non-local) 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 (Xiong et al. 2024 Xie 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 (Badita al.) | Mishchenko al. 2022). In this paper, we aim to tackle this issue by strategically leveraging asy asynchronous federated learning (A-FL) in policy-based FedRL for the first time. A-FL (Xie et al. 2020 Chang al. 2024) shows superiority compared synchronous FL, and recent works (Mishchenko et al. 2002 Koloskova et al. 2022) further improve convergence performances with theoretical guarantees.
Challenges: However, compared to prior A-FL approaches focusing on supervised learning, integrat- ing A-FL with policy-based FedRI. 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 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 looked in existing research, despite the significance of employing FL in RL, The key question that this paper aims to address is:
2

---

Published as a conference paper at ICLR 2025
Despite the inherent challenge of dealing with lagged policies among different agents, 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 delly-adaptivve 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 conventional supervised FL, effectively addressing the unique challenges of asynchronous FedRL. The improvement of AFedPG over other approaches is summarized in Table [T] Here, the global time is measured by the number of global updates x time complexity in each iteration. In terms of sample complexity, the federated learning technique brings a linear speedup with respect the number of agents N. As for the global time, AFedPG improves from O "N E 2.5) to O 2.5), where i = 1/ E/E f, is a harmonic average which is less than or equal to mmax/N N, and 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 FedRL. To handle the delay issue in the asynchronous FedRL setting.
we design adaativee lookahead technique. Specifically, in the k-th iteration of training,
the agent collects samples according the local model parameters 0z. + 02 1-a4-64, (Ok-
ai-6
1),, where & is the delay. Unlike (supervised) FL, second-order correction term (marked blue in equation 32) only occurs in RL because of the sampling mechanism. This updating technique cancels out the second-order correction terms ((1 ak-6, ) J(a)) 0x)
0g 8 2 (Ox) (+,- 0z) 0) and thus assists the convergence analysis. This technique specifically designed for AFedRI, 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 our AFedPG approach improves the sample complexity in each agent from (c--2.5) (single agent PG) O( (==)), ), 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 O (umee)) to Of Σ )) The latter is always smaller than the former. This
improvement is significant in large-scale federated settings with heterogeneous delays (fmax >>
bmin).
5. Experiments under the MuJoCo environment: We empirically verify the improved perfor- mances AFedPG 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 the updated policy.
Notation:
We denote the Euclidean norm by || ||. and the vector inner product by (-). For a vector E R", use a to denote the transpose of A calligraphic font letter denotes set, e.g., C, and [C] denotes its cardinality. We use { to denote a set that contains all the elements in C except for j.
3

---

Published as a conference paper at ICLR 2025
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-an art result is presented in Yuan et al. (022 achieving a sample complexity of Ō(e-4) for the local convergence. Several recent works have improved this boundary with PG variants. In [Huan et al. (2020), a PG with momentum method is proposed with convergence rate O(c-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 (). In Fatkhullin et al. (0023). normalized PG technique is introduced and improves the global convergence rate to { (2)) In Mondal Aggarwal (2024), an acceleration- based natural policy gradient method is proposed with sample complexity TT 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 practical federated PG setting with distributed agents 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. (020), the superiority of asynchronous federated learning (A-FL) has been empirically shown compared 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), dropout regularization method is introduced to handle the heterogeneous problems in A-FL. About the same time, recent works (Mishchenko et al., (022)) Koloskova et al. (022) 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, 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, [Zhng et al. (2024); Vin et al. (2022); Woo al. (2023)
analyze the convergence performances with environment heterogeneity. Salgia & Chi (2024) analyzes the trade-off between sample and communication complexity. Zheng et al. (2024); ); Khodadadian
et al. (2022) shows a linear speedup with respect to the number of agents. Zhang et al. (2024a) 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 (AC) based method, Wang et al. (202bb) analyzes the convergence performances with the linear function approximation. Mnih et al. 2016) builds practical system to implement the neural network approximation. Yang iet al. (2024) analyzes the sample complexity in the multi-task setting. In Xie & Song (2023), adds KL divergence and experimentally validates the actor-critic based method with neural network approximation. For policy-based methods, Chen et al. (002 gives a convergence guarantee for the vanilla FedPG. (Wang al. 2024a) analyzes the performance in the heterogencous setting, Lan et al. (20235) 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 RI. even in the presence of adversaries is studied in Ganesh et al. (2024a). However, with online behavior, is not practical perform synchronous global updates with heterogencous computing power, and the global time consumption heavily depends on the stragglers (Mishchenko al., 2022). This motivates us to consider the asynchronous policy-baser method for FedRL. We demonstrate both theoretically and empirically that our method further reduces the time complexity compared to the synchronous FedRL approach.
meeh
PROBLEM SETUP
Markoy decision process: We consider the Markov decision process (MDP) as a tuple (S,A, P. R,,,, where S is the state space, A is finite action space, P S A x S + R is a Markov kernel that determines transition probabilities, R S x A + R is a reward function, and 7 (0, 1) is discount factor. At each time step 1, the agent executes action o, A from the
4

---

Published as a conference paper at ICLR 2025
current state 8t S, following stochastic policy म, f.e., as (-(ss)). The corresponding reward is defined as rt. The state value function is defined as
V (s)
E ae (eleeae)))
Σ (rr(s a0lso
(1)
Similarly, the state-action value function (Q-function) defined as
(s)
Σ (r((s,, aellso =s a0 =a
(2)
as). P
An advantage function is then define An(s, a) policy is parameterized by 0 E Rd and then the policy is referred (Deep RL parameterizes by deep neural networks). A state-action visitation measure induced by my is given as
With continuous states, the
Uxo (8. a)
7)
E egrup
Σ
P(s = a|s0 me
where the starting state Su is drawn from a distribution p. The goal of the agent maximize the expected discounted return defined as follows:
max ((0) = E [v (s)].
(4)
grup
The gradient of J(0) (Schulman et al.
2018) can be written as:
VoJ(0) =
Σ Vo log To(aels)) Ano (st, at)
(5)
where = (So, d0. ro, 81, 71 ...) is a trajectory induced by policy We omit the 0 notation in the gradient operation and denote the policy gradient by g for short. Then, is estimated by
((,
V log (a
"r(snn
6
Federated policy gradient: We aim solve the above problem in an FL setting, where N agents collaboratively train common policy me. Specifically, each agent collects trajectories and corre- sponding reward ()) based its local policy. Then, each agent estimates g(0,, r) for training the model 0, 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 an FL setting.
4 PROPOSED ASYNCHRONOUS FEDPG
The proposed algorithm consists of K global iterations, indexed by = 0......, 1. We first introduce the definition concurrency and delay our asynchronous federated setting. We then present the proposed AFedPG methodology.
Definition 4.1. (Concurrency) We denote C₁ as the set of active agents in the k-th global iteration, and define We = [C&] as the concurrency. We define the average and maximum concurrency as @ = Σ 0 Wk, and Wmax == max Wk. respectively.
each global iteration of AFedPG, the server applies only one gradient to update the model from agent who has finished its local computation, while the other N agents keep computing local gradients (unapplied gradients) in parallel. In this asynchronous setting, the models used in each agent outdated, the server keeps updating the model. Thus, we introduce the notion of delay (or staleness) 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.

---

Published as a conference paper at ICLR 2025
Global Steps
81-1 received poicy
dalcy adspted
smpples
updcting dinection
Server
Server
Server
computing
finished
computing
di-h
B2
dg-
do-by
Octi
2
2
N
2
N
compling
compling
Enancemert
Enveineent
Ennreeeent
(So, Po.
4. p(
Environment
&
p( 1
An illustration of the asynchronous federated policy gradient updates. Each agent has 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, 62 E N is the delay, A is the sample collected according to the policy -ō.- and d is the updating direction calculated from the sample 7k-
Figure I:
Definition 4.2. (Delay) In the k-th global iteration, we denote the delay of the applied gradient as 5e N (an integer), and the delays of the unapplied gradients as 18HNec (ua), where js denotes the agent that communicates with the server. 8f. is the difference between the k-th iteration and the iteration where the agent started to compute the latest gradient. In the final K-th global iteration, we have K applied gradients (5x j -1 and unapplied gradients (5) hiEck \ix) The average delay can be expressed as
K
8=
8
8k).
K K- 1+ CK
Xxxx
Asynchronous FedPG:
Our goal is to train global policy with parameters 0 E: Ed via FL across N distributed agents. As shown in Figure T during the training process, agent i collects trajectories in an online behavior, and computes gradients 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 mg, from the server in the j-th global iteration. Agent i collects its own local trajectory Ty based its current policy no,- Agent i then computes its local updating direction dj T based on the trajectory Tj. 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, from agent i. Thus, denote dR-6, d,. where &y is the delay in the k-th global iteration. The server updates global policy parameters by +- 0 ndx- where is the learning rate.
Downlink transmission: The server transmits the current global policy parameters 0 e Rd back to the agent as soon finishes the global update.
The server side procedure of AFedPG is shown in Algorithm I 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 and 5) as soon as it receives a direction da-6, from an agent with delay dz. 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 0x according to Step 2, and then collects samples based on the policy Tg. (Steps 3). At last, the agent computes the updating direction de. and sends it to the server 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 I
Normalized update at the server: In Step of Algorithm D to handle the updates with various delays, we normalized gradients with controllable sizes. Specifically, the error term [[e]]] in

---

Published as a conference paper at ICLR 2025
Algorithm 1 AFedPG: Server.
Require: MDP AS, P, RR,); 7): Number of iterations K; Step size TJk, Ou: Initial lo do E R Broadcast 0g N agents.
2: for k = 1.... K do
3:
Uplink Transmit
4: Receive g(Tk-6x: 0x-6e) from the agent ig.
5:
da-b, h, + (1 Ohk 5 )d o + as 6n (Tk b, on Ok-b,)
6:
Server update
d2-62
7:
On + OK-1 + I1k=-1 T522
8g + 0₂ 1-on " (0x- Ox-1) Lookahead
8:
06-5x
9:
Downlink Transmit
10:
Transmit 0g back to the agent ig.
11:
end for
Ensure: 8K
Algorithm 2 AFedPG: Agent i Update, i 1,... , N.
Require: 02. E IRd
1: Receive Og from the server.
2: Tke ~ p(,)TT
Sampling
3: Estimate policy gradient g(Fv, 0xr) according to equation
4: When finish computing, transmit g(F O2) the server. gradient, it is the k-th step on the server, where k - 5x = K.
When the server receives the policy
Ensure: g(Fv, )k.)
Lemma B.9 is related (V)(O))))) J(())) and ||VJ(0 [Ox))] With the smoothness
in Lemma B.7 we are able to bound the error as | 0&l = - The details of the boundaries
shown equation 34
Delay-adaptive lookahead at the agent: In Step 7 of Algorithm 1 (in blue), we design a delay- adaptive lookahead update technique, which is designed specifically for asynchronous FedPG. operates as follows:
02 (1 ak-6,) 04 0z.
(8)
We note that equation ijs the conventional momentum method, because the orders different. Here, 0g "looks ahead" based on global policies Q and 0g. and the learning rate ag-6, depends on the delay 5g-
In equation 8 the agent collects samples according to the current parameter 0, in online behavior, which only happens in the RI. setting. This makes the problem fundamentally different from the conventional FL. on supervised learning with fixed dataset. This mechanism cancels out the second-order Hessian correction terms:
(1 - ax- (1- vZ- 0x) + aa-55 (2J( - 0x) - 0,
and thus assists the convergence analysis. The details of the derivation are shown in Appendix B.4 marked in blue.
5 CONVERGENCE ANALYSIS
In this section, we derive the convergence rates AFedPG with the following criterions for the FOSP and global convergence, respectively.
We focus on the global convergence, i.e., finding the parameter s.t. J J(0) < é, where J is the optimal expected return.
Global Criterion:
FOSP Criterion: We focus on the first-order stationary convergence, i.e., finding the parameter s.f.
(()]] <.
7

---

Published as a conference paper at ICLR 2025
We use several standard assumptions listed in Appendix B. Based these assumptions, the convergence rates of AFedPG are given Theorem
5.2 and 5.1
Theorem 5.1. (Globul) Let Assumption B. and B. hold. With suitable learning rates me and o'k- after K global iterations, AFedPG satisfies
J - =[][((( S -
(1-7)-3)
VCbias
(10)
where Ebiss is from equation 13
Thus, satisfy J J(OK((K) c+
V I-7
need K O
[I-))T
iterations. As only one trajectory is required in each iteration, the number of trajectories is equal to K, i.e., the sample complexity is O(
2.5
Theorem 5.2. (FOSP) Let Assumption B.1
hold. With suitable learning rates Ti and Odk, after K
global iterations, AFedPG satisfies
[(Kk]
&
(11)
is the average of gradient expectations. To satisfy J(OK) S 6, we need K = O (1-))))))) iterations. As only one trajectory is required in each itera- tion, the number of collected trajectories is equal to K, i.e., the sample complexity O (1-1))))
where E[
K
96 (((0))
Comparison to the synchronous setting: Synchronous FedPG needs O(c-2.5) trajectories in total, and each agent needs O( (-=x)) 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, denote the time consumption for agent = 1, 1.... N at local steps with finite values. As the agent has the same computation requirement in each iteration (The number of collected samples is the same.), we assume that the time complexity in each iteration is the same. Then, the waiting time on the server for each step becomes 4max max L 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, Luna
speeding up training. Specifically, the average waiting time on the server is Σ 17
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 fmax >> mmins which occurs in many practical settings with heterogeneous computation powers across different agents. We illustrate the advantage of AFedPG over synchronous FedPG in Figure Appendix [A.1] As the server only operates one simple summation, without loss of generality, the time consumption at the server side is negligible.
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) (Toorov et al., (2012) with the MIT License. Both the state and action spaces are continuous. Environmental details are described in Table Appendix A.2 and the MuJoCo tasks are visualized in Figure
Measurement: All convergence performances are measured over 10 runs with random seeds from 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) baselneess
with settings listed in Table 3 in Appendix A. We follow the practical settings (Rfffnn et al., 2021) to update models with generalized advantage estimation (GAE) (0.95) (Schulman ct al. (018)) in our implementation. We use Py Torch (Paszke et al. 2019)) to implement deep neural networks (DNNs). All tasks are trained NVIDIA ATOO GPUs with 40 GB of memory.
8

---

Published as a conference paper at ICLR 2025
Baselines: We first consider the conventional PG approach with N = 1, the effect of using multiple agents for improving sample complexity. We then consider the synchronous FedPG method baseline to observe the impact of usynchronous updates 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 Finally, we consider A3C (Mnih et al. 2016), an asynchronous method designed for RL. We note that only few prior works could be used on the federated PG problem, e.g., A3C, and many existing works in federated supervised learning 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.
(a) Swimmer-v4
(b) Hopper-v4
(c) Walker2D-v4
(d) Humanoid-v4
Figure 2: Visualization of the four MuJoCo tasks considered in this paper for experiments.
6.2 RESULTS
Sample complexity improvement: First, to verify the improvement of sample complexity in the first row of T 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 and the single agent PG (N 1). The x-axis is the number of samples collected by each agent average, and the y-axis is the reward. all four MuloCo 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.
AFedPG (N = 2, 4, 8)
100
#Sarple
(a) Swimmer-y4
(b) Hopper-v4
(c) Walker2D-v4
(d) Humanoid-v4
Figure Reward performances of AFedPG (N 2, 4,8) 8) and PG (N 1) on various MuJoCo environments, where N is the number of federated agents. The solid lines are averaged results over 10 runs with random seeds from to 9. The shadowed areas are confidence intervals with 95% confidence level.
Speedup in global time complexity: Second, to verify the improvement of global time complexity in the second row of Table compared the time consumption in the asynchronous and synchronous settings. In Figure 4 we set N 4, 8 and fix the number samples collected by all agents. Here, Imax is about 4 times more than Lmin- The numbers of total samples (trajectories) are 8 x 103.

---

Published as a conference paper at ICLR 2025
200
0.
24
24
08
(a) Swimmer-v4
(b) Hopper-v4
(c) Walker2D-v4
(d) Humanoid-va
Figure 4: Global time of AFedPG and FedPG with certain numbers of collected samples on various MuJoCo environments, where N is the number of federated agents. The solid lines are averaged results over 10 runs. The shadowed areas are confidence intervals with 95% confidence level.
1.6 x 10t, x 10 and 1.2 x 10 for the Swimmer-y4 task, the Hopper-v4 task, the Walker2D-vá task, and the Humanoid-ve task individually when N = 8. When = 4, the numbers are halved. In all four environments, AFedPG has much lower time consumption compared the synchronous FedPG, confirming the enhancement in terms of time complexity. Compared to the A3C baseline, AFedPG achieves much higher rewards with less variance.
In Figure 4 we also observe the impact of our delay-adaptive lookahead approach. is seen that the vanilla scheme without the delay-adaptive lookahead technique does not provide satisfactory performance, confirming the importance of the proposed approach. We also analyze the effect of computation heterogeneity Appendix A.3
Ablation study:
DISCUSSIONS
Conclusions: We proposed AFedPG, a novel asynchronous FedRL framework that 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 ( 2-)) ( sample complexity at each agent for global convergence. Compared to the SOTA result in the single agent setting, i.e. PG, with -255) sample complexity, it enjoys linear speedup with respect to the number of agents N. Second, compared to synchronous FedPG, AFedPG improves the time complexity from O (maz)) ) to O ))-1, where L; denotes the time complexity in each iteration at the agent i, and fmax is the largest one. The latter complexity O i. ) is always smaller than the former one, and this improvement is significant in large-scale federated setting with heterogeneous computing powers (fmax >> fmin). 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.
Limitations and future work directions: (i) Although the system is resilient to stragglers, addressing threats posed by adversarial or malicious workers this setup remains an open problem. While robustness to such attacks has been explored in the synchronous setting (Ganesh et al., (024a)). extending these methods an asynchronous environment is both a challenging and promising avenue for future research. (ii) It is worth studying 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, (iii) Extending second-order policy optimization methods, such as natural policy gradient methods, which achieve optimal sample complexity in centralized settings (Mondal & Aggarwal 2024). to asynchronous federated setup is important direction for future work. (iv) While this paper focuses on discounted rewards, exploring such results for average reward 2024b) is an important open direction.
setup (Bai al. 2024 Ganesh et al. 2025
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
In this statement, we discuss the efforts that have been made to ensure reproducibility.
For thcoretical results, we clearly explain all assumptions in Appendix B.1 and complete proof of the lemmas and theorems in Appendix B
For algorithms, we provide the pseudocode in Algorithm | 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
ACKNOWLEDGMENTS
This work was supported in part by the National Science Foundation (NSF) under grants CPS-2313 109 and ITE-2326898, and by the Office of Naval Research (ONR) under grants N00014-22-1-2305 and N00014-23-1-2532.
REFERENCES
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(1):4431-4500 2021a.
Mridul Agarwal, Bhargav Ganguly, and Vaneet Aggarwal. Communication efficient parallel rein- forcement learning. In Uncertainty in Artificial Intelligence (UAI), volume 161 of Proceedings of Machine Learning Research, 247-256. PMLR, 27-30 Jul 2021b.
Abubakr O. Al-Abbasi, Arob Ghosh, and Vaneet Aggarwal. DeepPool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions Intelligent Transportation Systems, 20(12):4714 2019.
Ajay Badita, Parimal Parag, and Vaneet Aggarwal. Single-forking coded subtasks for straggler mitigation. JEEE/ACM Transactions Nerworking, 29(6):2413-2422 2021.
Qinbo Bai, Washim Uddin Mondal, and Vaneet Aggarwal. Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 10980-10988, 2024.
Christopher G Brinton, Mung Chiang, Kwang Taik Kim, David J Love, Michael Beesley, Morris Repeta, John Roese, Per Beming, Erik Ekudden, Clara Li, et al. Key focus areas and enabling technologies for 6G. IEEE Communications Magazine, 2025.
Zhan-Lun Chang, Seyyedali Hosseinalipour, Mung Chiang, and Christopher G. Brinton. Asyn- chronous multi-model dynamic federated learning over wireless networks: Theory, modeling, and optimization. IEEE Transactions on Cognitive Communications and Networking, 10(5):1989-200 2024.
Chang-Lin Chen, Hanhan Zhou, Jiayu Chen, Mohammad Pedramfar, Vaneet Aggarwal, Tian Lan, Zheqing Zhu, Chi Zhou, Tim Gasser, Pol Mauri Ruiz, et al. Two-tiered online optimization of region-widk datacenter resource allocation via deep reinforcement learning. arXiv preprint arXiv:2306. / 17054, 2023.
Jianlong Chen, Jue Xiao, and Wei Xu. A hybrid stacking method for short-term price forecasting in electricity trading market. In 2024 8th International Conference on Information Technology. Information Systems and Electrical Engineering (ICITISEE), pp. 1-5, 2024a.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. VAFL: A method of vertical asynchronous
federated learning. arXiv preprint arXiv:2007.06600 2020.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Başar. communication-effficin policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems, 9(2):917-929, 2021.
11

---

Published as a conference paper at ICLR 2025
Yuning Chen, Kang Yang, Zhiyu An, Brady Holder, Luke Paloutzian, Khaled M. Bali, and Wan Du. MARLP: Time-series forecasting control for agricultural managed aquifer recharge. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '24, pp. 4872-4872. Association for Computing Machinery, 2024b.
Cheng-Wer Wei Ching, Jia-Ming Chang, Jian-Jhih Kuo, and Chih-Ye Yu Wang. Dual-objective personalized federated service system with partially-labeled data over wireless networks. IEEE Transactions on Services Computing, 1665):3265-3279 2023.
Cheng-Wei Ching, Xin Chen, Taehwan Kim, Bo Ji, Qingyang Wang, Dilma Da Silva, and Liting Hu. Totoro: A scalable federated learning engine for the edge. In Proceedings of the Nineteenth European Conference on Computer Systems, EuroSys '24, pp. 182-199. Association for Computing Machinery, 2024.
Yun-Wet Chu, Dong-Jun Han, and Christopher G Brinton. Only send what you need: Learning to communicate efficiently in federated multilingual machine translation. In Companion Proceedings of the ACM on Web Conference (WWW), pp. 1548-1557, 2024a.
Yun-Wei Chu, Dong-Jun Han, Seyyedali Hosseinalipour, and Christopher G Brinton. Rethinking the starting point: Enhancing performance and fairness of federated learning via collaborative pre-training. arXiv preprint arXiv:2402.0223 2024b.
Yun-Wei Chu, Dong-Jun Han, Seyyedali Hosseinalipour, and Christopher Brinton. Unlocking the potential of model calibration in federated learning. In The Thirteenth International Conference Learning Representations (ICLR), 2025.
Dongsheng Ding, Kaiging Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained Markov decision processes. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 8378-8390. Curran Associates, Inc., 2020.
Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum- based policy gradient. In Proceedings The 25th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, pp. 1910-1934. PMLR, 28-30 Mar 2022.
Gabriel Dulac-Amold, Nir Levine, Daniel J Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: Definitions, benchmarks and analysis. Machine Learning, 1109))2441--2468, 2021.
Chen Dun, Mirian Hipolito, Chris Jermaine, Dimitrios Dimitriadis, and Anastasios Kyrillidis. Efficient and lighh- federated learning via asynchronous distributed dropout. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 206 of Proceedings of Machine Learning Research, pp. 6630-6660, Palau de Congressos, Valencia, Spain, 25-27 Apr 2023. PMLR.
Anis Elgabli, Jihong Park, Amrit Singh Bedi, Chaouki Ben Issaid, Mchdi Bennis, and Vaneet Aggarwal. Q-GADMM: Quantized group ADMM for communication efficient decentralized machine learning. IEEE Transactions on Communications, 69(1) 11:11611111 2020.
Anis Elgabli, Mohammed S Elbamby, Cristina Perfecto, Mounssif Krouka, Mehdi Bennis, and Vaneet Aggarwal. Cross layer optimization and distributed reinforcement learning for wireless 360 video streaming. In Proceedings of IEEE International Conference on Mobile Ad-Hoc and Smart Systems (MASS), 2024.
Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for Fisher--oo--degenerate policies. In International Conference on Muchine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pp. 9827-9869, Honolulu, HI, USA, 23 29 Jul 2023. PMLR.
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-tine timescale actor-critic provably finds globally optimal policy. In International Conference Learning Representations (ICLR), 2021.
12

---

Published as a conference paper at ICLR 2025
Swetha Ganesh, Jiayu Chen, Gugan Thoppe, and Vaneet Aggarwal. Global convergence guarantees for federated policy gradient methods with adversaries. Transactions on Machine Learning Research, 2024a. ISSN 2835-8856.
Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal global convergence for average reward reinforcement learning via actor-critic approach. arXiv preprint arXiv:2407.18878, 2024b.
Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal regret with novel policy gradient approaches in infinite horizon average reward mdps. In International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 2025.
Mudit Gaur, Amrit S. Bedi, Di Wang, and Vaneet Aggarwal. Closing the gap: Achieving global conver- gence (last iterate) of actor-critic under Markovian sampling with neural network parametrization. In International Conference on Machine Learning (ICML), 2024.
Nan Geng, Qinbo Bai, Chenyi Liu, Tian Lan, Vaneet Aggarwal, Yuan Yang, and Mingwei Xu. A reinforcement learning framework for vehicular network routing under peak and average constraints. IEEE Transactions Vehicular Technology, 7265):6533-674 2023.
Glebys Gonzalez, Mythra Balakuntala, Mridul Agarwal, Tomas Low, Bruce Knoth, Andrew W Kirkpatrick, Jessica McKee, Gregory Hager, Vaneet Aggarwal, Yexiang Xue, et al. ASAP: A semi-autonomous precise system for telesurgery during communication delays. IEEE Transactions on Medical Robotics and Bionics, 5(1):66-78, 2023.
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-basee policy gradient methods. In International conference on machine learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 4422 4433. PMLR, 13 Jul 2020.
Hao Jin, Yang Peng. Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics (AISTA7S), volume 151 of Proceedings of Machine Learning Research, pp. 18-37. PMLR, 28-30 Mar 2022.
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. Ad- vances and open problems in federated learning. Foundations and trends@ in machine learning. 14(1-2):1-2) 2100, 2021.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under Markovian sampling. In International Conference Machine Learning (ICML), volume 162, pp. 10997-11057, Baltimore, MD, USA, 2022. PMLR.
B. Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: survey. IEEE Transactions on Intelligent Transportation Systems, 23(6):499--4926, 2022.
Anastasiia Koloskova, Sebastian U. Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. In Advances Neural Information Processing Systems (NeurIPS), volume 35, pp. 17202-17215, New Orleans, LA, USA, 28 Nov Dec 2022. PMLR.
Pawel Ladosz, Lilian Weng, Minwoo Kim, and Hyondong Oh. Exploration in deep reinforcement learning: A survey. Information Fusion, 85:1 2022.
Guangchen Lan, Xiao Yang Liu, Yijing Zhang, and Xiaodong Wang. Communication-effeen federated learning for assource-constriines edge devices. IEEE Transactions on Machine Learning in Communications and Networking. 1:210-224, 2023a.
Guangchen Lan, Han Wang, James Anderson, Christopher Brinton, and Vaneet Aggarwal. Improved communication efficiency in federated natural policy gradient via ADMM-based gradient updates. In Thirrh-seventhh Conference on Neural Information Processing Systems (NeurIPS), volume 36, pp. 59873-59885 New Orleans, LA, USA, 10-16 Dec 2023b. Curran Associates, Inc.
13

---

Published as a conference paper at ICLR 2025
Yaxin Liang, Erdi Gao, Yuhan Ma, Qishi Zhan, Dan Sun, and Xingxin Gu. Contextual analysis using deep learning for sensitive information detection. In International Conference on Computers. Information Processing and Advanced Education (CIPAE), 2024.
Shicheng Liu and Minghui Zhu. Distributed inverse constrained reinforcement learning for multi- agent systems. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 33444-33456, 2022.
Shicheng Liu and Minghui Zhu. Learning multi-agent behaviors from distributed and streaming demonstrations. In Advances in Neural Information Processing Systems (NeurlPS), 2023.
Xiao- Xiao-Yang Liu, Zechu Li, Zhuoran Yang. Jiahao Zheng, Zhaoran Wang, Anwar Walid, Jian Guo, and Michael I Jordan. ElegantR--Podracer Scalable and elastic library for cloud-native deep reinforcement learning. In Advances in Neural Information Processing Systems Workshop on Deep Reinforcement Learning, 2021.
Yanli Liu, Kaiqing Zhang. Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 7624-7636. Curran Associates, Inc., 2020.
Shiqing Long, Didi Yi, Mohan Jiang, Minghao Liu, Guanming Huang, and Junliang Du Adaptive transaction sequence neural network for enhanced money laundering detection. In International Conference on Electronics and Devices, Computational Science (ICEDCS), 2024.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Conmunicaiion-effiieenn learning of deep networks from decentralized data. In International Conference Artificial Intelligence and Statistics (AISTATS), volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282, Ft. Lauderdale, FL., USA, 20-22 Apr 2017. PMLR.
Konstantin Mishchenko. Francis Bach, Mathieu Even, and Blake E Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. In Advances in Neural Information P Processing Systems (NeurIPS), volume 35, pp. 420-433, New Orleans, LA, USA, 28 Nov Dec 2022. PMLR.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proceedings of The 33rd International Conference on Machine Learning (ICML), volume 48 of Proceedings of Machine Learning Research, pp. 1928-1937, New York, NY, USA, 20-22 Jun 2016. PMLR.
Washim U Mondal and Vaneet Aggarwal. Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward Markov decision processes. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3097-3105 PMLR, 2024.
Viraaji Mothukuri, Reza M. Parizi, Seyedamin Pouriyeh, Yan Huang, Ali Dehghantanha, and Gautam Srivastava. A survey security and privacy of federated learning. Future Generation Computer Systems, 115:619-640, 640, 2021.
Solmaz Niknam, Harpreet S. Dhillon, and Jeffrey H. Reed. Federated learning for wireless communi- cations: Motivation, opportunities, and challenges. IEEE Communications Magazine, 5866)44-51, 2020.
OpenAl. GPT-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
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. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 17730-27744 New Orleans, LA, USA, 28 Nov- 9 Dec 2022. Curran Associates, Inc.
14

---

Published as a conference paper at ICLR 2025
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco. Matteo Pirotta, and Marcello Restelli. Stochas- tic suriance-reduced policy gradient. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 4026- 4035, Stockholm, Sweden, 10-15 Jul 2018. PMIR.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, Vancouver, Canada, 8 - 14 Dec 2019. Curran Associates, Inc.
Joel B. Predd. Sanjeev B. Kulkarni, and H. Vincent Poor. Distributed learning in wireless sensor networks. IEEE Signal Processing Magazine, 23(4):56-69, 2006.
Foster Provost and Tom Fawcett. Data science and its relationship to big data and data-driven decision making. Big Data, 1(1):51-59, 2013.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. cablle-asselinss. Reliable reinforcement learning implementations. Journal of Machine Learning Rexearch, 22(268):1 2021.
Sudeep Salgia and Yuejie Chi. The sample-communication complexity trade-off in federated Q- learning. arXiv preprint arXiv:2408. 16981, 2024.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint urXiv:1506.02435 2018.
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEEE Transactions on Signal Processing. 71:2579-22 25994, 2023.
Gemma Team and Google DeepMind. Gemma: Open models based Gemini research and technology. arXiv preprint arXiv:2403.08295. 2024.
Emanuel Todorov, Tom Erez, and Yuval Tassa. MuloCo: A physies engine for model- -ased control. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5026-5033. Vilamoura-Algarve, Portugal, 2012.
Han Wang, Sihong He, Zhili Zhang, Fei Miao, and James Anderson. Momentum for the win: Col- laborative federated reinforcement learning across heterogeneous environments. In International Conference on Machine Learning (ICML), 2024a.
Han Wang, Aritra Mitra, Hamed Hassani, George Pappas, and James Anderson. Federated TD learning with linear function approximation under environmental heterogeneity. Transactions Machine Learning Research, 2024b. ISSN 2835-8856.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations (ICLR), 2020.
Ronald Williams. Simple statistical fralient- algorithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Jiin Woo, Gauri Joshi, and Yuejie Chi. The blessing of heterogeneity in federated Q-learning: Linear speedup and beyond. In International Conference on Machine Learning (ICML), pp. 37157-37216. PMLR, 2023.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. In 12th Annual Workshop on Optimization for Machine Learning (OPT), 2020.
Zhijie Xie and Shenghui Song. FedKL: Tackling data heterogeneity in federated reinforcement learning by penalizing KL divergence. IEEE Journal on Selected Areas in Communications, 41()): 1227-1242, 2023.
15

---

Published as a conference paper at ICLR 2025
Guojun Xiong, Shufan Wang. Daniel Jiang, and Jian Li. Personalized federated reinforcement learning with shared representations. In Deployable RL: From Research to Practice @ Reinforcement Learning Conference, 2024.
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. In International Conference on Learming Representations (ICLR), 2020.
Yifei Xu, Yuning Chen, Xumiao Zhang. Xianshang Lin, Pan Hu, Yunfei Ma, Songwu Lu, Wan Du, Zhuoqing Mao, Ennan Zhai, al. GooudEvalYYAMis A practical benchmark for cloud configuration generation. Proceedings of Machine Learning and Systems, 6:173-195, 2024.
Tong Yang, Shicong Cen, Yuting Wei, Yuxin Chen, and Yuejie Chi. Federated natural policy gradient and actor critic methods for multi-task reinforcement learning. In The Thirty-eighth Annual Conference Neural Information Processing Systems (NeurIPS), 2024.
Liangqi Yuan, Dong-Jun Han, Su Wang, Devesh Upadhyay, and Christopher G Brinton. Communication-cfficcnn multimodal federated learning: Joint modality and client selection. arXiv preprint arXiv:2401. /6685, 2024.
Rui Yuan, Robert M. Gower, and Alessandro Lazaric. general sample complexity analysis of vanilla policy gradient. In Proceedings of The 25th International Conference Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, pp. 3332-3380. PMLR, 28-30 Mar 2022.
Chenyu Zhang, Han Wang, Aritra Mitra, and James Anderson. Finite-time analysis of on-policy hetcrogeneous federated reinforcement learning. In The Twelfth International Conference on Learning Representations (ICLR), 2024a.
Daoan Zhang, Guangchen Lan, Dong-Jun Han, Wenlin Yao, Xiaoman Pan, Hongming Zhang, Mingxiao Li, Pengcheng Chen, Yu Dong, Christopher Brinton, and Jiebo Luo. SePPO: Semi- policy preference optimization for diffusion aligmment. arXiv preprint arXiv:2410.05255, 2024b.
Jingyuan Zhang, Ao Wang, Xiaolong Ma, Benjamin Carver, Nicholas John Newman, Ali Anwar, Lukas Rupprecht, Vasily Tarasov, Dimitrios Skourtis, Feng Yan, and Yue Cheng. Infinistore: 2023.
Elastic serverless cloud storage. Proc. VLDB Endow.,
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6): 3586-3612, 2020.
Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Federated Q-learning with reference-advantage decomposition: Almost optimal regret and logarithmic communication cost. arXiv preprint arXiv:2405.18795. 2024.
Feng Zhu, Robert W Heath Jr, and Aritra Mitra. Towards fast rates for federated and multi-task reinforcement learning, arXiv preprint arXiv:2409 05291, 2024.
16

---

225) as harmonic average of Published as a conference paper at ICLR 2025
A SUPPLEMENTARY RESULTS
In this section, first compare the time complexity between the synchronous and the asynchronous settings. We then list the experimental settings in Appendix A.2 At last, we have supplementary experiments in Appendix A.3
A.1 COMPARISON TO THE SYNCHRONOUS SETTING
Let T' be the computation time during the entire training process achieve given number K of cumulative communication rounds of all agents, where K = ((E -2.5 )) for a global convergence
according to Theorem 5.1
In AFedPG, for agent i, the number of communication rounds is T. For all agents, the total number ΣN O
is Σ I. E. As
Em I K, we have T
all agents.
In FedPG, the number of global communication rounds on the server is Tmax
As
we have
Tmax
N
T Kiyua O fuma -2.5) O
Fx rt -2.5) as the harmonic mean is always smaller or equal
the maximum one.
The asynchronous FedPG achieves better time complexity than the synchronous approach regardless of the delay pattern. The advantage is significant when max > fmin. which occurs in many practical settings with heterogeneous computation powers across different agents. We illustrate the advantage of AFedPG over synchronous FedPG in Figure As the server only operates one simple summation, without loss of generality, the time consumption at the server-side is negligible.
noticeable that we do not make any assumptions or requirements on tmax in the analysis of AFedPG. In the extreme case, the slowest agent does not communicate with the server, and thus, mmx is infinite, In this scenario, the time consumption of AFedPG does hurt lot, while the time consumption of FedPG becomes infinite.
Synchronous
Agent 1
tma
2
Agent 2
t min
time
Agent 1
5
Agent 2
3
4
Asynchronous
Figure 5: Comparison of time consumptions between synchronous and asynchronous approaches. The circled numbers denote the indices of global steps.
A.2 SUPPLEMENTARY EXPERIMENTAL SETTINGS
In Section 6.I we list the key experimental settings. We list the rest with details in this subsection. The environmental details (the four MuJoCo tasks) are described in Table - The policies my are parameterized by fully connected multi-layer perceptions (MLPs) with settings listed in Table
17

---

Published as a conference paper at ICLR 2025
Table 2: Detailed descriptions of the four tasks in the MuJoCo environment.
Action Space
State Space
MuJoCo Tasks
Agent Types
Dimension
Dimension
Three-link swimming robot Two-dimensional one-legged robot
Swimmer-v4
Hopper-v4
Two-dimensional bipedal robot
Walker2D-y4
17
Three-dimensionall
Humanoid-v4
17
376
bipedal robot
Table 3: Hyperparameters of AFedPG and the MLP policy parameterization settings.
Hyperparameter
Setting
Task
Swimmer-v4
Hopper-v4
Walker2D-v4
Humanoid-v4
MLP
64 x 64
256
256
512 x 512
512 512 x 512 ReLU Tanh
Activation function
ReLU
ReLU
ReLU
Output function
Tanh
Tanh
Tanh
Learning rate (a)
10
1 x 10-3
x 10
x 10
Discount (n)
0.99
0.99
0.99
0.99
Timesteps (T)
2048
1024
1024
512
Iterations (K)
10
2 x 103
5 10a
1.5 10*
Learning rate (17)
3 10
1 1 10
5 10
1 x 10
A.3 SUPPLEMENTARY EXPERIMENTS
In this subsection, show three experimental results study the effect of computation heterogeneity, communication overhead, and reward performances with long runs.
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 fums, and the effect is measured by the speedup, which the global time of FedPG divided by that A FedPGG Without loss of generality, we the performances with (1) One straggler, which is one agent has Emin time consumption, and all the other agents have fmax time consumption. This is the scenario with the largest speedup. (2) One leader, which is one agent has fuax and the others have fmin- This is the scenario with the smallest speedup.
Tmii
In Figure the results show that the speedup increases as the heterogeneity ratio fuax increases. With one leader, more agents participate. the speedup approximately decreases 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 very large RL system, particularly in scenarios with extreme stragglers (The ratio is large: mmax > bmin).
tmin
Communication overhead analysis. We compare the communication overhead of FedPG and AFedPG in Figure 7 For neural network parameters, we use the standard format float32. The communication overhead is measured by the number of transmitted bytes. The number of federated agents N set to The MuJoCo task is Swimmer-v4. Overall, the commutative communication overhead is similar. However, when dive deep into the agent side and the server side separately in fine-grained time, AFedPG shows advantages on both sides.
On the agent side, Figure 7 (a) shows the cumulative communication bytes during the training process. The cumulative communication overhead is similar in FedPG and AFedPG. In AFedPG, the faster ones, e.g., Agent 8, communicate more, and the slower ones, e.g., Agent 1, communicate
18

---

Published as a conference paper at ICLR 2025
N
450
N
N
N
300
= 16
N 16
speeoup
speedup
250
154
202
100
Ratio
Ratio
(a) one straggler
(b) With one leader
Figure 6: The time complexity speedup of AFedPG compared to FedPG. N is the number of agents. The x-axis is the heterogeneity ratio of computing power measured by faaxx time of FedPG divided by that of AFedPG.
The y-axis is the global Emin
less, which more reasonable than the equal allocation in the synchronous setting. The Agent 1, in fact, commutes with the server during the training process, but it is insignificant in the plot with log scale.
The agents have heterogeneous resources, but equal allocation could bring too much burden for the slower ones. AFedPG, it naturally shifts these burdens to the faster ones considering the local resources.
On the server side, we show the downlink communication overhead in a time window in Figure (b). The time window is "one global round in the synchronous setting". At time step is higher hecause two agents communicate with the server in short time period. The total amounts of AFedPG and FedPG similar. AFedPG, it is almost evenly distributed during the time span, while in FedPG, the server has huge burden with peak. This makes the server in FedPG require huge resources.
AFedPG
FedPG
AFedPG
FedPG
Communicatinon Overhedd 198)
Conerurkitinn Dee 900
423
Agent Agent
Agent: Agent
Agent
Time Stp
(a) On the agent side
(b) Downlink on the server side
Figure 7: The communication overhead of AFedPG compared to FedPG. The number of agents = 8. (a) The cumulative communication overhead on the agent side. (b) The downlink communication overhead in time window the server side.
19

---

Published as a conference paper at ICLR 2025
Reward performances with long runs. To further enhance the results in Figure extend the running time with more samples. Compared to the results in Figure 3 we increase the number of samples by 5 times in each Mujoco task in Figure The solid lines are averaged results over 5 runs with random seeds from to 4. The shadowed areas are confidence intervals with 95% confidence level.
With enough samples, it basically achieves a similar reward performance for different numbers of agents N in AFedPG. However, the more agents engage, the faster achieves. Notably, the solid line is the average result with 5 independent runs. With different numbers of agents, the shadowed area has a large overlap. The more overlaps they have, the more runs that have similar reward performances because of the inherent randomness (with different random seeds) in the deep reinforcement learning tasks.
For the Humanoid-và task, though in some runs (shadowed area), PG achieves the optimal reward performance, the average (solid line) performance of PG is relatively lower than the others in AFedPG. The reason is that the Humanoid-v4 task has the largest state and action space, which makes the hyperparameter tuning difficult, egg. learning rates, and brings huge GPU hours. The hyperparameter setting of PG is suboptimal here, has contribution to our main claim. Recall that we aim to use these experiments to verify the speedup effect AFedPG in Table The suboptimal hyperparameters of PG in the Humanoid-ve task do not influence the conclusion: The more agents in AFedPG, the faster the optimal reward will be achieved.
120
2500
2000
Rewards
Rewards
1500
1000
1)
AFedPG (N
AFedPG 2)
20
AFedPG (N 4)
500
AFedPG (N 4)
AFedPG (N
AFedPG
0
0
0
2
3
0.0
0.2
0.4
0.6
0.8
1.0
Samples
Samples
(a) Swimmer-v4
(b) Hopper-v4
1200
2500
1000
2000
Rewards
Rewards
1500
600
1000
(N 1)
400
AFodPG
AFedPG (N =2)
500
AF AFedPG 4)
203
AFedPG (N -
AF+JPG
AFedPG
0
2 Samples
2
6
164
Samples
1e4
(c) Walker2D-v4
(d) Humanoid-va
Figure 8: Reward performances of AFedPG (N 2,4,8) and PG (N = 1) on various MuJoCo environments, where N is the number of federated agents. The solid lines are averaged results over 5 runs with random seeds from 0 to 4. The shadowed areas are confidence intervals with 95% confidence level.
20

---

Published as a conference paper at ICLR 2025
B THEORETICAL PROOFS
In this section, we give the assumptions in Appendix B.1 the technical lemmas in Appendix B.2 our key lemmas in Appendix B.3. the proof of Theorem 5.1 (the global convergence) in Appendix B.4 and the proof of Theorem 5.2
(the FOSP convergence) in Appendix B.5
B.1 ASSUMPTIONS
In order to derive the global convergence rates, we make the following standard assumptions (Agarwal al. 2021a Ding et al. 2020 Liu et al. 2020 Papini et al. 2018 Xu et al. 2020) policy gradients, and rewards.
Assumption B.1.
1. The score function is bounded as | log (a s)ll s Mg. for all 0 E RR, S, and a E A.
2. The score function is M, Mip-hihcchtzz continuous. In other words, for all 0s 02 E Rd A, we have
S, and
V log no, (a 8) log (a s]]l Mn. 110. 02
(12)
3. The reward function is bounded as r(s, a) E [0, R]. for all S, and A.
These standard assumptions naturally state that the reward, the first-order, and the 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 Te, the approximation error may not be in practice.
Thus, we follow previous works Liu et al. 2020); Agarwal et al. (2021a) Ding et al. (2022); Huang et al. (2020) with an assumption on the expressivity of the policy parameterization class.
Assumption B.2. (Function approximation) bias 2 0 s.r. for all E RRd, the transfer error satisfies
Bi(AT, (s, a) (1 --)"" (a)u(((1 (0) V log mo(a s)) S Cbiass
(13)
where u (0) = F((0) ()))), and (0)t is the Moore-Penrose pscudo-inverse of the Fisher matrix Fp.
It means that the parameterized policy Ty makes the advantage function A (s, a) approximated by the score function V log (a s) as the features. This assumption is widely used with Fisher-non- degenerate parameterization. ébias can be very small with rich neural network parameterization, and with a soft-max parameterization (Wang et al. 2020).
To achieve the global convergence, we make standard assumption the Fisher information matrix (Liu et al. 2020 Ding et al. 2022 Lan et al. 2023b).
Assumption B.3. (Positive definite) For all Rd. there exists a constant μ4f S.t. the Fisher information matrix (0) induced by the policy mo and the initial state distribution satisfies
(0) > PF AF.I,
(14)
where / E R is an identity matrix.
For any two symmetric matrices A and with the same dimension, A > denotes that the eigenvalues of A greater or equal zero.
B.2 TECHNICAL LEMMAS
Lemma B.4. For arbitrary vectors (a; E Rdin
Timp we have
Σ
a
2
< n
|a 2
(15)
T=1
21

---

Published as a conference paper at ICLR 2025
Lemma B.5. Let ag (ffe) P. vp [0, 1] and 2 1, we have
ak+1
1 aK+1 S
(16)
Proof.
09+11
=
8+ 1
< ++1+c
(17)
ak+11
Ohk
Straightforwardly, we have
K-1
II
(1 01+1))
S
OK
(18)
O
Lemma B.6. Let a = k+1 ) and nh = no 4+1 ). Vp E [0, 1), q 2 and no 2 0, we have
K
K-1
Σ k=
II (1-as) S c(p, 4) OK i=++1
(19)
where c(p,4)
2
a exp ((1 p))pat-p) is constant with specified p and q, and a
1-p
max ((11-112F)
2(
p) )r)
B.3 KEY LEMMAS
In this subsection, list four useful (key) lemmas construct the proofs of Theorem 5.1 and Theorem 5.2
Under Assumption B.I on score functions, the following lemma holds based the results (Lemma 5.4) in ZZhang et al. (2020).
Lemma B.7. The gradient of the expected return is Lg- Lontinunuu and L smooth as follows
[[V](() - v.((6') < Lgl10 8'11.
(20)
(0) ((' < | 0'|1,
where Lg = Mb) (1-7)² and Ln = [1-7]3 (1-7)²
RMC
RM,M,
O 71)1)
Under Assumption B.
B.2 and B.3 utilize the result (Lemma 4.7) in Ding al. (2022) as the
Lemma B.8
Lemma B.8. (Relaxed weak gradient domination) Under Assumptions B.1 B.2 and B.3
it holds that
[VJ(0)] + 2 - -
(21)
where Eg
BF Ciina and μ
2²
M,(1
2M
Based on Lemma B.7 we derive our milestone (new), the ascent lemma with delayed updates, as follows:
Lemma B.9. (Ascent Lemma with Delay) Under Assumptions B.l it holds that
Lg 2
-J(0x+1) S -J(0x) (000)>~mm11100 [
mr lell +
2 1lk
(22)
where eg dR-6n, vJ((k)-
22

---

Published as a conference paper at ICLR 2025
This ascent lemma is specific to the asynchronous setting, which constructs the lower bound for the global increment, J(0x+1) - ((x), through the normalized policy gradients and our updating rules with delay òk.
Proof. With the smoothness of the expected return J(0) and the updating rule, we have
Lg
-](0k+1) s -J(0k) - (V.) 0x+1
Oz)
+
110 - 0x11
2
(23)
= -J((k) - (VJ(0k), (.0)),xx-.. dx-bu)
Lg
+
nk.
|d
2
If |exe|| $ [0=)l( we have
(VJ(Ok), dx [[ + (VJ(Ok), ex²
dk- 11
[dk-
-1 + J
144-6..1 - -I )12 + 1 [++))]
(24)
[V+(0))] + ||ex|
1 JJ(w)]l
If [|x] 2 (ll=)l] we have
(V.(Ox), dR-
I [[VJ(())]
|d 6b
[J(00)1 +
/ [OW(
(25)
5 [J(WW]]+ / leall.
Combining these two conditions, and plugging the result into equation as follows
23 the lemma can be proved
(VJ(O)). de dz
Lg 2
-J(Ok+1) S -J(s)) -
m
dd Se
(26)
Lg 2 me.
S -J(()) - Ths
VJ (0x)
3 mnllexll +
Next, we construct the relationship between the average concurrency @ and the average delay 8 in Lemma 10 This lemma gives the boundary (our result) of delays as corollary of the result in Koloskova et al. (2022).
Lemma B.10. The average delay ă depends on the average concurrency w, and they can be upper bounded as
K +
8
N.
(27)
CK
Proof. Recall that (ech M 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
8, +
Σ
8441 =
Σ ==
8 +
Σ
o% + Wh+t
(28)
0=
iECo+1 Mintil
VEC,
Minl
23

---

Published as a conference paper at ICLR 2025
We note that there is no delay the initial step (0-th iteration) of the algorithm. Therefore, we have 6 = for all agents. Unrolling the above expression, at the K-th step, we have
6
Wk+1 = (K + 1)
(29)
iECK \(x}
According to equation
7 and [Cxl 2 2, we achieve
K +
S 2 S N.
(30)
K + CK
In practice, need to use all the resources to speed up the training process. Thus, all agents engage in training, and / = Wmax N. Since the maximum concurrency is equal to the number of agents N, we have the upper boundary of the average delay 8 S Wmax S N.
Notably, we do not make any assumption on the largest delay 6max, while we achieve the upper boundary of the average delay 8.
B.4 PROOF OF THEOREM 5.1 (GLOBAL CONVERGENCE RATE)
Under Assumption B.I and Assumption AFedPG.
B.2 we derive the global convergence rate of the proposed
First, we denote the difference between the policy gradient estimation g( 0%) and the true policy gradient as
& = g 02) (Ox), and the expectation of the norm is bounded by Tg..
(31)
Second, according the updating rules Algorithm and Algorithm 2. we expand the error term in Lemma B.9 as follows
ek ark - )d, 1 1 vJ(Os) on an-a, 0x-86)
(1 - ak 52 (dk-1-6r-1 vJ((k=1)) + (1 -4 (V [V](kk-1)) VJ((k))
+ +0k-8 8 (g( Th 66 OR-b,)) VJ(O.))
= 5e (1 0k (60-- + (1 -06- ( -
+ +.k-6. V J (0k-6)) - V.J(E)))
= =o Ek 5n + (1 04 -4. 66
ak (VJJ((A-1) - V)((K))
+ + V (0x 5,) - VJ(Oa)) 0Ak by (VJ(O.) VJ(O)))
(32)
-22-6EE-66 de + (1 a4 - C# (V. (V)(0)-6))) vJ(O.))
+ +1 ap 8,
( (VJ V V 6k))
+ V (0.) ((())) V2. 02))
(1 a 22 ((.))
02) - a V (=J(()) 0k)
8
Dkk 02-6254-65 + (1 04 6 04 (VJ vJ(Ok))
+ (1 - ax 64 (VJ (V
V ((0h) + ('
0s))
+ a4- V. (0x) v((A)) + (=)000))0-1110 0z)).
Thus, the error term Ek can be written in a recursive way (contains ex-1) with serval terms that contain policy gradients. We aim to derive the upper boundary for each term at the next step.
The Hessian correction terms (in blue) are equal to according to our updating rules adelay-ad lookahead update) in Step 8 of Algorithm We design this technique to cancel out the recond-order terms, and thus achieve the desired convergence rate. Without our technique, would be hard to bound the above errors.
Remark:
24

---

Published as a conference paper at ICLR 2025
Next, we denote each term in equation 32
separately as follows
Aş = vJ((k-1) VJ(()) + V 0k).
B₃ V.((A)) V.J(O)) V=J(BL) 0x).
(33)
C VJ((k-oo) V-)(Ae)
Now, we start to bound each term. With the smoothness of the expected discounted return function in Lemma B.7 and the non-increasing learning rates, we have
||Ax|| & 1n|10=-1 - 0x|1² = LaAE -1
(1 66) )2
|B & LA 0xll2 = Ln
2
1
a
|C & Lg 10-6 - 0x1l
Lg Σ
0++1 02
1-1
< L
10,+1 - 041l
i= db
k-1
a (0, 0/_1)
Lig
(0++1 - 01) +
(34)
01+1-0141
a;- 8:
i=k bn
(0+41 - 0i)
1 ai-b: (0: 0z-1)
<
Lag
+
0i+1 11+11
0i-6:
1 - as-bi 1)-) +
L.g
0i+1-8:41
0:-6:
k=k-6z
k-1
2
< Log
(p-bb))
Mp
ak-1
İ=
217x-b4
= 8x Ly
ax-1
where the equalities simple plugins according the updating rules in Algorithm 1 The last step in equation 34 happens, because there is no index inside the summation operation, and sums constant for dş times.
We denote 3x = II 1+ aa-8,) & with 3x 1. Next, unrolling the recursion equation 32 have the error at the K-th step as follows
K
K
K (Bt + Ck). (35)
ск = Bocp +
az
BaEx +
- az
a )& + Σ a
k=l
k=1
kml
25

---

Published as a conference paper at ICLR 2025
Choose learning rates 0g (x+1)) and 7 No K+I where yu is constant and we will show the value later. Using Jensen's s inequality and technical lemmas, we achieve the following bound
K
nk 62 B55N- 11)
E||ee||]
$ &oBllllooll
+
E
Oz O' [.
Ok 5u 3x
Bx + I+I)
k
K
S BoB[[eeoll +
Σ
a A4 B
[160-62l1)
+
(1
-x- 18,E Ax
ax
k=1
K
O4 64 3u (B Ba |I] + II]
1/4
K
K
381
800g
F [1EA- [2]
+
Ln
O -b
)
k=1
K
nh-
K
Th BR aK-1
(36)
+ Lb
3 (1
ag )
+ 2L 9
Σ
5x B4
k=1
k=1
K
S Bo0g
a 38
|1EA-66 8z 12]
+ Ln
Ol OK-- 5%
K
mh
+ 20 _oo
Ok Bcd
ax-1
k=
B&dg nh-
PK
Og
Li
8k
+ 2Lg
Σ
ak
be
ak-ōz
aK-1
kml
km
$ 3000 +
K
0g +
9hp
K
BR
1
+ 22g Σ
K
ak-
3k0g mh-zz
4
aa-1
k=
k=
2
2
0g + C aiaax
+ 12
+ C
8,
2
1,75
ak
a
where 01 : defined in Lemma B.6
2/
/ 16) are constants, and the values of c(.,)) are ( 1), 02 = clg. c2 = s
Notably, as we state in the last paragraph in Section 5 t; is pre-determined by the computation resource at agent i and is fixed. Thus, the delay òg is prtedmmmr by the system. It is not random variable, but unknown until given the exact system setting. This allows us to derive the first inequality in equation 36 This pre-determined property is also suitable for all the derivations below.
26

---

Published as a conference paper at ICLR 2025
We explain the boundary derivation details here. We first derive the first term of the boundary in equation 36 as follows
K
8o
(4-6,)
(=1
K
04))
==1
(37)
K-1
a1+1)
i=0
aKK
00
ok-
In the training process, at step k. when an agent sends the update to the server, as long as the agent communicates with the server during the last half training process, the delay d% 2. almost certain when k is large and l is usually much larger than the upper bound of the currency N. Thus, have
& This becomes
+
1
+
+
k +
5/
k -
(38)
+
2(
k +
20
We then derive the second term of the boundary in equation 36 as follows
K
K
6
K
k=1
K
K
K
(1
&
II (1-a;-8)
k=1
i=k+1
i=++1
K
K
K
$
II imk+1
(1 - o5)
II
(1
as)
i=k-1
K
K-1
O
(1 0s)
II
0441)
i=k+1
i=k
K
K-1
(39)
4
(1 05)
akk
K-1
4
(1-o3)
(=++1
4o.k
0
II
05))
k=0
kmk+1
10
4. O.K
40 c
5' αK
4ax
5' )
27

---

Published as a conference paper at ICLR 2025
Next, we derive the third term of the boundary in equation 36 as follows
K
K
3k
116
8
C
k +
1=
K
76
(1 - 6.)
k +
km
1m
K
K
7
(1-oi) os)
k
+
km
K- (1-aa)
(40)
k
(=++1
K
K-1
II (1 (1-aa) o2))
h: +
k=
14
4 6
76
5 5
K
4 6 n
c
5 5
At last, we derive the fourth term of the boundary in equation 36 We use Cauchy-Schwarz inequality and the fact that the second norm of a vector always equal or smaller than the first norm.
K
K
Th bc
Ok
3r
<
Mk 5x 3róz
ak-1
x=1
K
k
1+1
2
7h
k:
+
km
2
4
5x
K
< 41h
2
1
k=1
1=
1/
K
< 47
3
Σ
1: +
S K8 Kö
82
k +
< Kg
II
(1 ai-bi)
k
i=k+1
28

---

Published as a conference paper at ICLR 2025
K
4
OK
16
4gg
aK
+
K
K
4n
OK
II (1 04-61))
k=1
x=k+1
< K8
II (1 aa: i=k+1
OK
k=1
(41)
16
K8
aK
(1-a#)
i=k+1
16
1
Kō
axc(
(
5 5
K
4 16
K8
5'
K
+
4
16
4n68
c
5'
K
Ti
45
d
5 5
1,75
K
Now, we derive the final convergence rate. After plugging the result into Lemma B.9 and using Lemma B.S (Ascent Lemma with Delay), achieve the following inequality
V2
8 nm
+ Lg
J - [[J((++1)] <
(J* B(J(Ox)))
cg
KDH
-R(((O))
1/k
cg
+
Lg
(42)
3
(1no + tc1040 + 00
4
9
Ln
nk
0g
L
1.75 6).
Okk
Unrolling this recursion, we have
J - [[](()) s
77
gg + J [0)(
C3
8n
Lg
+ n7 Lg
3
(K + 1)2
3 (K 1)
2 K +1
(43)
8/
0g
+
8/j0
0g
+ 602m
Lu
3
(K 1)3
3
(K 1)3
(K + +1
Note that, introduced in Lemma B.7
the discount factor y is contained in Lg = O(1 - --) and
LA ((1 33) Comparing with the definition of cg in Lemma B.8 we choose
3uF for M,
the criteria. Thus, to satisfy the global convergence criterion J [[J()))] S +
yiui T- we have
the iteration complexity K = O(c-0.(2))) 2.5). In our algorithms, the sample complexity is equal to the iteration complexity, which also (6
B.5 PROOF OF THEOREM 5.2 (FOSP CONVERGENCE RATE)
Under Assumption B.I and Assumption B. AFedPG. Notably, the FOSP convergence does not require Assumption B.2, which makes assumptions on the neural network approximation error.
derive the first-order stationary convergence rate of
29

---

Published as a conference paper at ICLR 2025
First, denote the average of gradient expectations
[[|VJ(0x>]| = Σ The (o.))
(44)
2k=1
1/k
Next, rearranging the terms in Lemma B.9 we achieve the inequality below
(Ascent Lemma with Delay) and summing up the inequality,
E [J((((
3
(J+ B[J(Bu))) +
K
Blleell
Σ k 7k
Σ
km
km
(45)
3Lg
Σ
> k=
1h k=1
Choose learning rates have shown in Appendix B.4 we have
and 1o0 K+T
3.
Plug in the result into equation 36 that we
3(J* B[J(O))))
Lg
37
V((k))
+ 1603n0
+
(K +1
(K 1) (K + +1
(46)
+ 1670
0g
+ 16c1
0g
366220 3
La
(K + 1)
(K + +)
(K + 1)
Thus, to satisfy the FOSP convergence criterion ([ S e, we have the iteration complexity K O(e 3.5). In our algorithms, the sample complexity is equal to the iteration complexity, which also O(e 3.5).
Notably, this result does not rely Lemma B.8 and Assumption B.I The norm of the average gradient approaching an arbitrarily small value during the training process, regardless of the function approximation error bias-
30

---

Published as a conference paper at ICLR 2025
C FURTHER DISCUSSIONS
C.I COMPARISON WITH PREVIOUS WORKS
Comparison with (Shen et al. 2023). We first acknowledge the theoretical contribution of this pioneer work. However, there are several limitations and differences.
(Different RL Algorithm Class) Instead of PG, Shen et al. (2023) is an actor-critic (AC) method with extra value networks, which requires much more computation and memory cost compared to the pure policy gradient (PG) method. Thus, the fine-tuning of Gemini (Team & DeepMind 2024) and GPT-4 (OpenAl 2023) uses PG methods instead of AC methods.
(General Function Parameterization) Shen et al. (023) only has Linear Parameterization (Deep RL is not included.) for the global convergence analysis, which has limited practical meaning. With General Function Parametrization, e,g., neural networks (Deep RL), there no such a result. We consider general and practical setting with General Function Parameterization in our work.
(Convergence Performance) Even in the single-agent setting (without federated agents), the SOTA result of the AC method is ())-9) (Gaur et al. 2024) and the previous approach is O(e ") (Fu the federated setting, there is no result that achieves 3) 3) for AC methods. Moreover, with general function parameterization, compare the performances of their A3C in Figure 4 which is much worse.
ctt al. 2021), which still worse than our O (()
4. (Assumptions)) Shen et al. 2023) relies strong and unpractical assumption, their Assumption 2. It assumes that the largest delay is bounded by a constant Ko. However, in practice, the slowest agent may not communicate with the server, and thus, has infinite delay. In analysis, do not require any boundary for the largest delay, because we only contain the average delay in the convergence rate, and the average delay is naturally bounded by the number of agents in Lemma B.10 (our corollary).
C.2 DIFFERENCE BETWEEN FI., FEDRI., AND AFEDRI.
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 global policy no. However, in AFedRL, even if all agents have an identical environment, each agent collects samples according to different policies ты ~ p(-(TT,,) ), 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 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 their own (different) policies, fundamental difficulty that our AFedPG paper solves, as verified theoretically and empirically.
31


Reviews:
[{"review_id": "yf4s2H1Kzz", "reviewer": "Reviewer_YjHR", "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.", "questions": "See my questions from the previous section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Contributions claimed in the paper include,\n\n--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.\n\n-- Provides theoretical convergence guarantees, including global and first-order stationary point convergence, for the asynchronous federated policy-based RL.\n\n-- 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.)\n\n  -- 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.\n\n-- Empirically validates AFedPG's performance in various MuJoCo environments, demonstrating faster convergence (time-wise) over synchronous FedPG and other baselines.", "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:\n\n-- 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$.\n\n-- 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.\n \n-- 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. \n\n-- 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}}$. \n\n--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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K1dexS7eAX", "reviewer": "Reviewer_T8LV", "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.", "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. \n\n5. What’s the technical contributions beyond existing FedRL? Technical differences of AFedPG compared to FedPG seems limited.\n\n6. Authors first get the results of global convergence, then FOSP results. Why FOSP results are placed first in main text?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Convergence results are provided. \n2. Asynchronous federated reinforcement learning framework is proposed.", "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.\n\n[1] Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments, ICML24.\n[2] Federated Reinforcement Learning with Environment Heterogeneity, AISTATS22.\n\n2. 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.\n[3] Towards understanding asynchronous advantage actor-critic: convergence and linear speedup.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8XbQxumQZl", "reviewer": "Reviewer_KckT", "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.", "questions": ".", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The work provides asynchronous synchronization updates tailored for federated RL.\n2. 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.", "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.\n2. 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.\n\n[1] Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments, Wang et al., ICML 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qUF1DrMQbk", "reviewer": "Reviewer_ui29", "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.", "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?\n* 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. \n* Is there any analysis or experiment of communication cost?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Numerical experiments on MuJoCo demonstrate impressive results that support the better time complexity of the proposed method\n* 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", "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.\n* There are some typos in the manuscript. For example, you write *MoJuCo* instead of *MuJoCo* in the caption of Figures 3 and 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5zDtzv9Zsq", "reviewer": "Reviewer_oswF", "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.", "questions": "See the weakness.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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.\n\n2. 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.\n\n3. Numerical experiments demonstrate that the authors accelerate the training process compared to the synchronous algorithm.", "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.\n\n2. 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.\n\n3. 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}}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)