Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning
Authors: Alexander Tyurin
Andrei Spiridonov
Varvara Rudenko
Venue: ICLR 2026 Poster (2026)
Keywords: reinforcement learning
federated learning
distributed learning
asynchronous methods
Primary area: reinforcement learning

Abstract: We study distributed reinforcement learning (RL) with policy gradient methods under asynchronous and parallel computations and communications. While non-distributed methods are well understood theoretically and have achieved remarkable empirical success, their distributed counterparts remain less explored, particularly in the presence of heterogeneous asynchronous computations and communication bottlenecks. We introduce two new algorithms, Rennala NIGT and Malenia NIGT, which implement asynchronous policy gradient aggregation and achieve state-of-the-art efficiency. In the homogeneous setting, Rennala NIGT provably improves the total computational and communication complexity while supporting the AllReduce operation. In the heterogeneous setting, Malenia NIGT simultaneously handles asynchronous computations and heterogeneous environments with strictly better theoretical guarantees. Our results are further corroborated by experiments, showing that our methods significantly outperform prior approaches.

Published as a conference paper at ICLR 2026
ASYNCHRONOUS POLICY GRADIENT AGGREGA- TION FOR EFFICIENT DISTRIBUTED REINFORCEMENT LEARNING
Alexander Tyurin
Andrei Spiridonov AXXX, Moscow Russia
Varvara Rudenko AXXX, Moscow, Russia
AXXX, Moscow, Russia
Applied Al Institute, Moscow, Russia
ABSTRACT
We study distributed reinforcement learning (RL) with policy gradient methods under asynchronous and parallel computations and communications, While non- distributed methods are well understood theoretically and have achieved remark- able empirical success, their distributed counterparts remain less explored, partic- ularly the presence of heterogeneous asynchronous computations and commu- nication bottlenecks. We introduce two new algorithms, Rennala NIGT and Male- nia NIGT, which implement asynchronous policy gradient aggregation and achieve state-of-the-ane art efficiency. In the homogeneous setting, Rennala NIGT provably im- proves the total computational and communication complexity while supporting the AllReduce operation. In the heterogeneous setting, Malenia NIGT simultane- ously handles asynchronous computations and heterogencous environments with strictly better theoretical guarantees. Our results are further corroborated by ex- periments, showing that our methods significantly outperform prior approaches.
INTRODUCTION
Reinforcement Learning (RL) is one of the most important tools modern deep learning and large language model training. There are many applications, including robotics and control (Kober et al., 2013; Levine et al., 2016), recommender systems (Chen et al., 2019), and game playing such as Go, chess, and StarCraft II (Silver et al., 2017; Vinyals et al., 2019). Moreover, RL has used in the fine-tuning of large language models through reinforcement learning from human feedback (RLHF) (Christiano et al., 2017).
Modern machine learning and RL models are typically trained in distributed fashion, where many agents, workers, GPUs perform asynchronous computations in parallel and communicate period- ically (Dean et al., 2012; Recht et al., 2011; Goyal et al., 2017). This distributed paradigm enables training scale by efficiently utilizing massive computational resources. However, distributed train- ing poses many challenges, including communication bottlenecks (Alistarh et al., 2017: Lin et al., 2017), system heterogeneity across agents (Lian et al., 2015), and stragglers and fault tolerance (Chen et al., 2016). These challenges have motivated a large body of work on communication- efficient methods, asynchronous and decentralized optimization algorithms, and federated learning frameworks (Konečný et al., 2016; McMahan et al., 2017; Kairouz et al., 2021).
Policy Gradient (PG) methods are among the most popular and effective classes of RL algorithms (Williams, 1992; Sutton et al., 1998). They have demonstrated remarkable empirical performance across a wide range of challenging tasks. non-distributed settings, significant recent progress has been made, and PG-based methods are now well studied and better understood (Yuan et al., 2022; Masiha et al., 2022: Ding et al., 2022; Lan, 2023; Fatkhullin et al., 2023). However, distributed RL scenarios are less studied, and many critical challenges and open questions remain.
In this work, we study state-of of-the-rrt policy-based methods in parallel and asynchronous setups, where a large number of agents collaborate maximize the expected return of discrete-ting dis- counted Markov decision process. Our focus is on addressing computational and communication challenges that arise in distributed RI..

---

Published as a conference paper at ICLR 2026
1.1 RELATED WORK
Non-distributed PG methods. In tabular settings, Lan (2023) study policy mirror descent and es- tablish global guarantees for discrete state-action spaces. Alfano & Rebeschini (2022); Yuan et al. (2023) analyze PG methods with log-linear parameterizations. Our focus, however, is on general continuous state-action spaces with trajectory sampling and stochastic policy gradients. In this set- ting, Yuan et al. (2022) analyze Vanilla PG and prove a sample complexity of O(= for finding an e-stationary point. Several PG variants have since improved this rate. particular, Huang et al. (2020); Ding et al. (2022); Xu et al. (2020a:b); Fan et al. (2021) introduce momentum -based PG methods, but their analyses rely on importance sampling (IS) and therefore require strong additional assumptions (e.g,, variance of IS weights is bounded, in Assumption 4.4 of (Xu et al., 2020a)), which we ideally want to avoid. More recently, Fatkhullin et al. (2023), based on (Cutkosky & Mchta, 2020), propose normalized PG method that improves the rate for finding E-stationary point to (/--//2 under much weaker assumptions, requiring only second-order smoothness (with- out explicit use of Hessians). Hessian-aided PG methods have also been investigated (Fatkhullin et al., 2023; Ganesh et al., 2024); however, in practice, the stochastic Hessian-vector products sam- pled in these methods have much higher variance than stochastic gradients (Fatkhullin et al., 2023).
Parallel and asynchronous optimization. Distributed optimization is typically considered in two settings: homogeneous and heterogeneous. Both settings are equally important. The former, in the context of RI, implies that all agents access the same environment and data, while the heterogeneous setting, which is more prevalent in federated learning (FL) (Konečný et al., 2016), arises when the data and environments differ due to privacy constraints or the infeasibility of sharing environments.
In the homogeneous case, many studies have analyzed asynchronous variants of stochastic gradient descent, such as (Lian et al., 2015; Feyzmahdavian et al., 2016; Stich & Karimireddy, 2020; Sra et al., 2016). A common limitation of these works is the requirement that the delays in stochastic gradient indices remain bounded. Consequently, their results provide weaker guarantees on compu- tational time complexity compared to more recent analyses (Cohen et al., 2021; Koloskova et al., 2022; Mishchenko al., 2022; Tyurin & Richtárik, 2023; Maranjyan et al., 2025), which avoid this restriction. In the heterogeneous case, many works have also been proposed, including (Mishchenko et al., 2022; Koloskova et al., 2022; Wu et al., 2022; Tyurin & Richtárik, 2023; Islamov et al., 2024).
In order to compare parallel methods, Mishchenko et al. (2022) proposed the hi-fixed computation model in the context of stochastic optimization (see Assumption 2.5 in the context RL), assuming that it takes at most h; seconds to calculate one stochastic gradient agent i. Mishchenko et al. (2022); Koloskova et al. (2022) provided new analyses and proofs of Asynchronous SGD, show- ing that their versions of Asynchronous SGD have the time complexity ((1//n E
+ l/ne"), where the Big-O notation is up to an error tolerance and h4. Surprisingly. this complexity can be improved! to (mmin [1/m 2m i=1 1/h.) 1//e + 1/me²))), achieved by the Rennala SGD method from (Tyurin & Richtárík, 2023). For the heterogencous setting, they also developed the Malenia SGD method with the time complexity O (maa:<t<)) hu/e + (1/n >;=1 1/h,) Moreover, Tyurin & Richtárik (2023) proved that these complexities are optimal under smoothness and the bounded stochastic gradient assumption.
In the distributed RL domain, numerous works have been proposed. For instance, Fan et al. (2021); Ganesh et al. (2024) analyzed federated reinforcement learning with fault-tolerance approaches in settings with adversarial attacks, Jin et al. (2022): Ganesh et al. (2024); Labbi et al. (2025) studied federated policy gradient in synchronous homogeneous and heterogeneous settings, while Lu et al. (2021); Chen et al. (2021) investigated decentralized policy optimization with a focus on communi- cation efficiency.
The current state-of- central work for our study is the recent result of Lan et al. (2025), which considers an asynchronous PG method called AFedPG and provides the current ofate-of-the-art time complexity under sumptions. Their method builds on the idea of applying the NIGT method (Cutkosky & Mehta, 2020; Fatkhullin et al., 2023) to the asynchronous RL domain, aided by recent insights from Koloskova et al. (2022); Mishchenko et al. (2022). is worth noting that this combination is not straightforward and requires several technical steps to adapt the previous analysis RL problems.
method in asynchronous and parallel RL. The most relevant and
Notice that min g(m) I g(n) for any g NN + R. me/n
2

---

Published as a conference paper at ICLR 2026
Table 1: Homogeneous Setup. The time complexities of distributed methods find an e-stationary point in problem (1) up to an error tolerance E, number of agents n, computation times h3, commu- nication time k (see Section 4.1), and ignoring logarithmic factors.
Total Time Complexity
Method
Support AllReduce
Compatational Complexity
Communication Complexity
(Syncronous) Vanilla PG (Yuan et al., 2022)
max hi [e(n)
net
+
R x
ned
Yes
(Synoronous) NIGT (Fatkhullin et al., 2023)
?
max h4 x ne?/z 1E(m)
+
R. x 7772
Yes
Rennala PG/SGD (Tyurin & Richtánik, 2023)
mi [1]
h2
+
K -
Yes
(Lan et al., 2025)
AFedPG
n p
+
No
Hennala NIGT (new) (Theorem 4.4)
min me [n]
Σ
+
Yes
Lower o (new) (Theorem G.I) l)
m
min [1]
3/72
The total time complexity of Rennala NIGT better than that previous methods: i) for small-e, its computational complexity much better than that of Vanilla PG, NIGT, and Rennala PO; ii) Rennala NIGT supports AlReduce and its communication complexity is much better than that of AFedPG for small-s; jii) its computational complexity can be arbitrarily better'than that AFedPO, whese complexity can grow with n.
(4) The lower bound applies to methods that only access unbiased stochastic gradients of (Igg F, -twice smooth function with o-bounded variance, treating (3) as black-box oracle. Extending methods exploiting the full structure of J in (1) and closing the gap remains open. See discussion in Sections 4.1 and G.
However, AFedPG has several limitations: i) although motivated by and designed for federated learn- ing, this method does not support the heterogencous setting; ii) due to its greedy update strategy, the method has suboptimal communication time complexity (as we illustrate in Section 4.1 and Table 1) and does not support the AllReduce operation, which is essential in most distributed environments; iii) finally, its computational time complexity is also suboptimal and can be improved (Table 1).
1.2 CONTRIBUTIONS
We develop two new methods, Rennala NIGT and Malenia NIGT, which achieve new state-of-the-arr computational and communication time complexities in the homogeneous and heterogeneous set- tings, respectively. Our theory strictly improves upon the result of Lan al. (2025) in all aspects within the same setting, without requiring additional assumptions: i) we develop and analyze Malenia NIGT, which supports asynchronous computations in the heterogeneous setup; ii) our communication time complexity is provably better in the homogeneous setup. For example, in the small-e regime, Rennala NIGT improves AFedPG's s bound of ORK 3) to ORE 2). And in the worst case, the com- munication complexity of AFedPG can provably be as large as O -7/2) (see Section 4. 4.1). Further- more, both Rennala NIGT and Malenia NIGT support AllReduce; iii) our computational time complex- ity is also strictly better in the homogeneous setup. In the small-e regime, we improve their complex-
ity ((1/2 Σi= 1/h.) 1/h.))-(('"))) ////// + //n=*/)) to Ô Omiinmess
Σm= 1/h.)- 1//k.)-(((/22) + f/mm)//))) which can be arbitrarily smaller (see the discussion in Section 4). Even in the classical optimiza- tion setting, we significantly improve upon the current state-of-the-ar results of Tyurin & Richtárik (2023); Maranjyan et al. (2025) by leveraging momentum and normalization techniques, together with a mild second-order smoothness assumption. As a final contribution, we establish new lower bound, Theorem G.I from Section G, which enables us to quantify the remaining optimality gap.
We believe our new methods, analysis, insights, and numerical experiments are important for the RL community, as they achieve state-of-the-art time complexities in asynchronous and parallel RL (Tables and 2), an area that is rapidly gaining importance with the growing availability of compu- tational resources.
( -
(+ +.) ( - S
min m
77
3

---

Published as a conference paper at ICLR 2026
2 PROBLEM FORMULATION AND PRELIMINARIES
We consider a discrete-time discounted Markov decision process M = (S,..,))))))) where S and A denote the state and action spaces, P S X A x 8 + R is the transition kernel, r SS::S A - | mmax Fmax] is the reward function bounded by T'mx > 0, p is the initial state distribution, and (0, 1) is the discount factor (Puterman, 2014).
We assume n. agents operate asynchronously in parallel and interact with independent copies of the environment. Each agent selects action a, A in state 8, S according to the parameterized density function To (-1e))) The agent then receives the reward r(se; (t), and the environment transi- tions to the next state 8t+1 according the distribution P(.)s,,a)) One of the main problems in RL is to find A E R2 that maximize the expected return
Σ Nrronaaa
_(0) = (s)
max DERS
where So p()), a nO (-(()s)), and 8e+1 is infeasible to generate an infinite trajectory. Instead, each agent generates a finite tra- jectory T (so, 00, :.. ,8H-1,0H-1) of length 1/ > 1 from the density p(T(Te)
P(.sst, at) for all t 0. In practice,
p(so)=((an)ss) so) II,-1 ((s a0-1))))) (o-)))(((()s)))) We define the truncated expected return:
(n) = E
[H11 Σ
7"r((1s ai)
(2)
which approximates J().. Given the rewards, we can compute the truncated stochastic policy gra- dient
H-1 r an) log ne (aclss))
gH(T, 0) = Σ Σ (
10
where (So, Gn. 1H-1 ~ p() The random vector gız (T, 0) is unbiased estima-
tor of J+ (Sutton et al., 1998; Masiha et al., 2022): (+) = E, [g 0).. In total, sampling trajectories and caleulating gm, the goal of the agents is find an e-stationary point 0 E Rd i.e., point such that [[ < 8.
2.1 ASSUMPTIONS
We consider the standard assumptions from the RL literature: Assumption 2.1. For all s, a E x A, the function + Ts(a, s) is positive, twice continu- ously differentiable, V| log =o(a|s)]l s Mg. and Iog (o(a)s)] s Mn. for all 0 Rd where Mg Mr > 0.
Assumption 2.2. For all a,a E S A, the function 0 - no (als) is positive, twice continuously differentiable, and there exists l2 > 0, such that || V log a (als) - 2 log ] s L2 ||e 0 for all 0, 0 Rd.
Using the assumptions, we can derive the following useful properties. Proposition 2.3 (e.g. (Zhang et al., 2020; Masiha et al., 2022; Yuan et al., 2022)). Let Assumptions 2.1 and 2.2 hold. Then,
1. Function satisfies [[V VJ((')Il s Lg 110 0'll for all 0 e Rd, where Lg Tiax (M² + M1)/(1 - 7)2-
2. Function J satisfies || v2)(0']| < Ln 11 0'l1 for all 0,0' E Rdd where Ln.
Ma Mr (1-1)²
Tou: (1+)
My max Mh,
MM
May (M)(41)+))((1-)) I-7 M, I-7:
(1-7)3
I-7
1-7²
3. J VJ(O)II s T and ||
2 J (0) v2)(0)] < D for all 0 E Rd, where
D, : I-7 - + H and D,, (Mr M ym
M. Na
(
1-7
4. For 9н defined in (3), have JJH( E, (T, 0)] and E, [[19H(T,)) () - vJH(0)]]?] < 0²
vO E Rdd with o² == r2 raax M3/ (1 -17) 7)33
4

---

Published as a conference paper at ICLR 2026
Table Heterogeneous Setup. The time complexities of distributed methods to find an e-stationary point in problem (1) up to an error tolerance E, computation times h4s communication time (see Section 4.1), and ignoring logarithmic factors.
Total Time Complexity
Method
Support AllReduce
Compatational Complexity
Communication Complexity
(Syncronous) Vanilla PG (Yuan et al., 2022)
max ha Ja
max
med
+
x
ned
Yes
(Tyurin & Richtärik, 2023)
Malenia PG/SGD
max h, + + XEiN)
h4
+
N
x
Yes
AFedPG
does not support heterogeneous setup
(Lam 2025)
Malenia NIGT (new) (Thoorem 5.1)
max
hs
Yes
Similar NIGT (Table total time complexity Malenia NIGT is beller than that of previous methods in the heterogeneuus setup.
2.2 HOMOGENEOUS AND HETEROGENEOUS SETUPS
We consider two important settings: homogeneous and heterogeneous. The homogeneous setting arises in open-data scenarios, where each agent has access to the same enviromment and distribution. In contrast, the heterogeneous setting is more relevant in federated learning (FL) (Konečný et al., 2016; Kairouz et al., 2021), where agents aim preserve privacy or where sharing environments is infeasible.
Homogeneous setup. We start with the homogeneous setup, where agents have access to the same distribution, share the same reward function, and πа. This problem is the same as in (Lan et al., 2025) and defined in Section
Heterogeneous setup. However, unlike (Lan et al., 2025), our theory also supports the heteroge- neous setting, where agents have access to arbitrary heterogeneous distributions and reward func- tions, which is important in FL. We consider the problem of maximizing
J(0) = 1/4 Σ J.(0). where (1( = (s,,
Σ Ennn(ss
(4)
and 8;,0 ~ (=()), Oz,t T. T (-18,,), and 81,+11 (- aj,z) for all 2 0, [n]. We assume the fully general setting, where agents sample from arbitrary heterogeneous distributions, and both the reward function and TH, may differ. The truncated expected return and stochastic gradient are defined as
12 (0) and 9r gt 0) Σ (0) - Σ
H-1 H-1
Σ 7 (rr((s,n as.)) V log ((a,,,)s)))))) (5)
where (1. = E., EH= Trr,( ar)) and = "..0, 81,H- -1,H-1) from the density P:(T(T:.)) = P: (:() (a..0)50.)) - Pi(s,, (,, a...-1))T Section 2, (0) E.,, [gi, (T;, 0)] J. In the heterogeneous setting, Proposition 2.3-(1), (2), and (3) still hold. However, due to heterogeneity, the last property concerning the unbiasedness and the variance of stochastic gradients holds only locally, for 9t.H instead of g::
(a;,, (s..). Similarly to
Proposition 2.4. For all E [n], let Ts,0 satisfy Assumptions 2.1 and 2.2. Then, Proposition 2.3- (3). are satisfied in the heterogeneous setting (4) and for the functions J and Ju (follows from triangle's 's inequality.
E+(g,,1(7, and 4. For 9t.H defined in (5), we have (i,
E (I, (0o. o² for all 0 E Rdii i [n].
((),
2.3 COMPUTATION AND COMMUNICATION TIMES
To illustrate our improvements over the previous state-of-the-art results, we make the following assumption. Notice that it required for the convergence our methods.
5

---

Published as a conference paper at ICLR 2026
Assumption 2.5.
Computing single stochastic policy gradient 9H (or 9s. agent requires at most
h4 == h, x
seconds, where h; denotes the time required to obtain the next state, and H is the trajectory length. Without loss of generality, assume that in .... I hn; and consequently h1 S .... hn-
In the centralized setup (with server), transmitting a vector from agent to and from the server takes at most & seconds. In the decentralized setup, transmitting vectors between agents (e.g., via AllReduce) also takes at most seconds.
In order to compute stochastic gradient 9H an agent must generate a trajectory and collect the corresponding rewards. Since trajectories are generated sequentially in a Markov decision process, the time required grows linearly with the horizon length H. Therefore, natural to assume that the computation time is bounded by h4 H, where h; denotes the maximal time needed by agent to simulate or observe single state transition.
The second condition natural distributed training and optimization, where communication be- tween agents requires non-negligible time >> 0, for instance when performed over the Internet or via MPI-based message passing.
We consider heterogeneous computations h2 and the communication time compare methods and highlight our contributions in the asynchronous setup. All our new methods work without assuming these. Moreover, Theorem 4.3 illustrates how our time complexity results can be generalized to arbitrary computation patterns.
3 NEW METHODS: Rennala NIGT AND Malenia NIGT
In this section, we present our new algorithm, Rennala NIGT (Algorithm 1 and Algorithm 2). Later, we present its heterogeneous version, Malenia NIGT (Algorithm 1 and Algorithm 3). They are in- spired by (Cutkosky & Mehta, 2020; Fatkhullin et al., 2023: Tyurin & Richtárik, 2023). The core steps (Algorithm 1) are almost the same as in (Cutkosky & Mehta, 2020). Using the extrapolation steps, Cutkosky & Mehta (2020) showed that it possible to improve the oracle complexity of the vanilla SGD method (Lan, 2020) under the additional assumption that the Hessian is smooth. turns out that the oracle complexity from (Cutkosky & Mehta, 2020) can be improved with the STORMMVR method (Cutkosky & Orabona, 2019), but the latter requires calculating stochastic gra- dients at two different points using the same random variable, which cannot easily be applied in the RL context due to the non-stationarity of the distribution.
To adapt Algorithm 1 to parallel and asynchronous scenarios, we follow the idea from (Tyurin & Richtárik, 2023; Tyurin et al., 2024a) and design the AggregateRennala procedure. The method broadcasts 0 to all agents. Each agent i then starts sampling T;,1, obtaining the reward, and com- puting the stochastic gradient gи (Tr,1, 0) locally. Next, the algorithm enters loop and waits for any agent to complete these steps. Once an agent finishes, the algorithm increases the counter i and instructs that agent sample another trajectory and repeat the process. This continues until the total number of calculated stochastic gradients reaches M. Notice that, unlike (Lan et al., 2025), the agents can aggregate the stochastic gradients locally, thereby reducing the communication over- head. Finally, performing only one communication, the algorithm aggregates all vectors to ğ (e.g.. via AllReduce), which Algorithm uses to make the steps.
Our strategy offers several advantages: i) Rennala NIGT (Algorithm 1 and Algorithm 2) can be as Algorithm
applied in both centralized and decentralized settings; ii) it asynchronous- is resilient to stragglers: if agent is slow even disconnected, the procedure is not delayed, since AggeegateMalenia only needs to collect M stochastic gradients from all agents. This will be formalized in Section 4. iii) it is also cmmmunication-effiieenn as vector communication occurs only once at the end of Algorithm 2 (see Section 4.1). 1). iv) finally, our theoretical guarantees are provably better than those of the previous results.

---

Published as a conference paper at ICLR 2026
Algorithm 1 Rennala NIGT or Malenia NIGT
1: Input: momentum 1, and step size a, starting point O,, parameters Miit and M, horizon H
2: Initialize do AggregateRennalaa Muits H)
(or AggregateMalenia (8g, Minit H))
3: 81 = 8u + a ||do||
do
4: for = 1, 2, do
5: 0. 0, + - (0, 02-1)
6:
9t AggregateRennala(0, M, H)
(rr AggregateMalenia (0,, M, H))
7: d, = (1 -n)d + 19h
8: 0++1 = 0, + ||
dt
9: end for
A Algorithm 2 AggregateRennalll( M, H)
Algorithm 3 AggregateMalenia((,, M, H)
Init 9 = Rd and =
Init 9: E Rdd and M, for all E [n]
2: Broadcast / to all agents
2: Broadcast 0 to all agents
3: Each agent starts sampling TH, ~ p(-[T))
3: Each agent starts sampling Ti, ~ pc(-(
and calculating ()((1.10)
and calculating (T,,I
4: while S M do
4: while (2/n > 1/M.)-1 M/n do
5: Wait for 9H (Ty.k: 0) from agent
5:
Wait for 9j.1 (T, 0) from an agent j
6:
9H (Tj,k, -);i=i1
6:
Øj 9j + (j..H(Tj.k 0); Mj M2 +
7: Agent j starts sampling T4,++1 ~ p()
Agent starts sampling TjK+1
and calculating 9n (T).6+1,0)
(,;(+TT9,)) and calculating Hj (T,R+11 8: end while
8: end while
9: Stop all calculations
9: Stop all calculations
10:
Return y
(e.g., via AllReduce)
10: Return 1/n Σn= 8/M, (c.g.. via AllReduce)
Note: The agents can locally aggregate дH and 9i.H. after which the algorithm can perform a single AllReduce call collect all computed gradients. The trajectories (Ti,) are statistically independent.
4 TIME COMPLEXITY IN THE HOMOGENEOUS SETUP
Theorem 4.1. Let Assumptions 2.1 and 2.2 hold. Consider Rennala NIGT (Algo- rithm 1 and Algorithm 2) in the homogeneous setup, or Malenia NIGT (Algorithms and Algorithm 3) in the heterogeneous setup. Let n min & Mc* qVE min { "4T, H max { (og,, (e (.,)),11 = 0(/(1-0)). Let Or be uniformly sampled iterate from 10o.-. 11 Then E [ s after T M
1:442:20 2,
en
a² TTA global iterations. METts
M
Notice that Theorem 4.1 does not rely on Assumption 2.5; convergence is guaranteed even without Assumption 2.5. It an auxiliary result that holds for any choice of M and Mini-- We now establish the time complexity of Rennala NIGT in Theorem 4.1, our first main result.
Theorem 4.2. Consider the results and ussumptions of Theorem 4.1. Additionally, consider that Assumption 2.5 holds with x = (i.e., communication is free). Taking Mini = max {[
and M = max {[ + s'vInA) /
A 1}. the time required to find an e- 2012
stationary point by Rennala NIGT (Algorithms / and is
min mE(n)
L
ILA 372
2
o² oVLL me m27
(6)
ma?
We now compare this result with (Lan et al., 2025). Although that paper requires the impractical assumption that generated trajectories have infinite horizons, we assume that they also require h, x H seconds to generate trajectory for agent i. Then, they obtain least the time complexity

---

Published as a conference paper at ICLR 2026
Oi0h (n2P//2/0 2 1/3) up E, n, and h; constant factors. If n is large, which is the case in federated learning and distributed optimization, their complexity can be arbitrarily large due to the n//3 and (1/n Ei= l/h.) dependencies'. Notice that our complexity (6) can only decrease with larger n due to the O min ( Ei 3/h.)) (1/=² +/met\))))))) dependency. In Section 4.1, we show that the gap is even larger when start taking into account the communication factor.
Our time complexity (6) has harmonic-like dependency Ó mm 1i=1%) P/m)]) on { for == A/s + VTaA//2/2 and := d²/=² + o² AT. To the best of knowledge, this is the current state-of-the-art computational complexity for maximizing (1). It has many nice properties:
it is robust to stragglers. If we take h, 00, this complexity starts ignoring the slowest agent and becomes Ö minnme]n-1] (1/m >x= 1/h.) (A+ f/m) )); ii)
since the harmonic mean is less than or equal to the maximum term, this complexity is much better than the time complexity of the naive synchronized distributed version of NIGT with the complexity Ó( max (A + B/n)), where all agents synchronize after each has computed one stochastic gradient. Notice that we can easily generalize our result when the times non-static.
Theorem 4.3. Consider the results and assumptions of Theorem 4.1. Additionally, con- sider that computing a single stochastic policy gradient 9H on agent i in iteration quires at most heg H seconds. Taking Mint- max { and M mmxx {[(: + )/L
ATAA) the time required to find an E-stationary point by Rennala NIGT (Algorithmss 1 and 2) is O(/1-9 Et minmm[al [( Eim1 1/hemen) (M/m 1//++1) +1] + Ei=1//n
o² d'vInA
2112
(Man/m + 1)(),, where T O (Tng//22 +10/2///T///// VTn and Te is a permutation such that he. S .... & he.
minmml)))
To simplify the discussion, we further focus on Assumption 2.5 and assume that the bounds on computation times are {h,}-
4.1 TIME COMPLEXITY WITH COMMUNICATION TIMES
We now generalize Theorem 4.2 by taking into account the communication time k:
Theorem 4.4. Consider the results and assumptions of Theorem 4.1. Additionally, con-
sider that Assumption 2.5 holds. Taking Mini = max { and M = max {[( +
o² TTTAA
(1 L.A y A ]1 1,,,, the time required to find an e-stationary point by Rennala 2372
2012
NIGT (Algorithms 1 and 2) is
K
2//2
A
min ME
me?
o²
d'VLTA me?
Compared (6), obtain additional time term (L,4/2² + vLnA//3/)). which accounts for the communication time complexity. Recall that the method of Lan et al. (2025) performs asynchronous updates, where each agents independently send gradients to the server, which is citoommmniatton-ffficiiee
For small E, in Lan et al. (2025), the fastest agent sends at least (max (omxx(n243// 4// ,n ---g-1/2g) stochastic gradients (according to their Theorem 5.2). Conse- quently, their communication time complexity is at least" OKKE whereas our algorithm achieves a significantly better dependence on s, namely O(ke 2). In the extreme case, when only the fastest agent participates and contributes, AFedPG reduces a single agent sends a gradient for every oracle call. In this setting, AFedPG provably requires at least (( 7/2) communications (Arjevani et al., 2020), resulting in an even larger gap compared to our complexity of O( ?). Moreover, method supports AllReduce, important feature in practical engincering scenarios.
non-distributed stochastic method in which
'For instance, take hıs = h, then it reduces to if /27/ s + 1//e7/3) "330 co. As a concrete example, 8 = 0.0001, the first term a//// /278 already dominates when n = 100. In practice, the number of computational resources n continues to grow toward 10K-100K, causing the complexity to increase with n as well. "since max(n 7/3 nnnn" ' 7/23
52(5 -3)
8

---

Published as a conference paper at ICLR 2026
In Section G, prove lower bound for functions and stochastic gradients satisfying Proposi- tion 2.3. Although we do not establish lower bound under Assumptions 2.1 and 2.2, we believe our result still reflects the fundamental lower bound of the considered task, since all recent state-of-the- art results (Fatkhullin et al., 2023; Lan et al., 2025), including ours, rely solely on Proposition 2.3. Comparing Theorems 4.4 and G.I, one
that there is still gap, for instance, between ke ke-2 and Ke ke-12/7, 12/7, We obtain the latter term by reducing et al. (2021) for (Lg. Ltwiee smooth functions. To the best of our knowledge, it remains an open problem whether the e 112/ rate can be achieved, even in the non-distributed deterministic case.
problem to the lower bound of Carmon
5 TIME COMPLEXITIES IN THE HETEROGENEOUS SETUP
In the heterogencous setup, we consider Algorithm 3 instead Algorithm 2. Algorithm 3 is also asynchronous aggregation scheme of stochastic gradients adapted to the heterogeneous setting. Unlike Algorithm 2, which specialized for the homogeneous setup, Algorithm ensures that the returned vector is unbiased in the heterogeneous setup: 14/n 2im1 8/MM]] 1/n > . J (0) J (0). For Malenia NIGT, we can prove the following result:
Theorem 5.1. Consider the results and assumptions of Theorem 4.1. Additionally, con- sider that Assumption 2.5 holds. Taking Mi max { 1, and M max { + o² //1AA / / NIGT (Algorithms I and 3)
A 1111.. the time required to find an e-stationary point by Malenia
LL 3/2
+ hm (422
AnLA 2/22
+
Σ
h4
nez
o² AVAA ns?
To the best of our knowledge, this result represents the current state-of-the-art complexity for RL problems in the heterogeneous, distributed, and asynchronous setting. Compared to Theorem 4.2, which has harmonic-like dependency, the dependence on {h,) in Theorem 5.1 is mean-like in the small-e regime. This behavior is expected, as the heterogeneous case is more challenging due agents operating with different distributions and environments. However, the term related to the communication time complexity is the same.
SUMMARY OF EXPERIMENTS
AFedRo
ATecPG
AfecPG
(a) Equal times
(b) Heterogeneous times
(c) Increased communication times
Figure 1: Experiments Humanoid-v4 with increasing heterogeneity of times (from left to right).
In this section, we empirically test the performance of Rennala NIGT and compare it with the previous state-of-the-art method by (Lan et al., 2025) and the synchronized version of NIGT (Synchronized NIGT). Following previous works (Lan al., 2025; Fatkhullin et al., 2023), we focus on the MuJoCo tasks (Todorov et al., 2012). We defer details, parameters, and additional experiments to Section H. Figure shows the main results: i) when the computation times are equal, all methods exhibit almost the same performance, which is expected since they reduce to nearly the same algorithm; ii) when the computation times are heterogeneous, Rennala NIGT converges faster than other methods; iii) when the computation times are heterogeneous and the communication times large, Rennala NIGT is the only robust method, and the gap increases even more. These experiments, together with the additional experiments from Section H. support theoretical results.

---

Published as a conference paper at ICLR 2026
7 UNIVERSAL COMPUTATION MODEL
Following (Tyurin, 2025; Maranjyan et al., 2025), for completeness, we can extend the previously derived time complexities to arbitrary computational dynamics.
Assumption 7.1.
We define non-negative and continuous almost everywhere compulation power function Vi R + R+ for all agent i [n]. The number of stochastic policy gradient that agent i can compute between times to and t
Ni (1) == [ (((()dT)
For simplicity, we ignore the communication time.
Using these computational powers, we can formalize the changing computation behaviors of agents, taking into account random fluctuations, different trends, and disconnections in more flexible way. In particular, when (T) = vs R+ is constant, NN((o, = [M; x (t1 - to)] and agent i starts calculating at time to: then it will compute one policy gradient after + 1/e, seconds because (tu, tu + 1/r,) = 1, two after to + 2/v, seconds, and so forth. This example reduces to Assumption 2.5 with h; 1/e.. However, Assumption 7.1 allows computational scenarios (see examples (Tyurin, 2025)).
capture virtually any
Theorem 7.2. Consider the results and assumptions of Theorem 4.1. Additionally, sider that Assumption 7.1 holds. Taking Mii: max { 1 and M .max {[( + o² o'vLnA 6/12
{, the time required to find an E-stationary point by Rennala NIGT (Algorithms I and 2) is fr seconds, where
) L.A (
VLLA and the sequence t 2a1
is defined recursively:
1. min {1: Σ N((1-1,,)2 M
41
(8)
with to min (t: Σl_ (,, 2 Mma)
One can show that this theorem admits an analytical formula and reduces to Theorem 4.2 when {us} are constant functions. general, to find IT, one should solve (8) for each particular choice of 0i, and it is always possible to do numerically. First, find the smallest f 2 O such that EE (0, 2 Miiit where Ei_ (o, f) is the number of gradients that the agents can compute parallel after seconds. Then, repeat the same procedure recursively for (8). We can also extend Theorem 5.1 (ignoring communication times):
Theorem 7.3. Consider the results and assumptions of Theorem 4.1. Additionally, con- sider that Assumption 7.1 holds. Taking Minr max { {[ 1, and M max {[( + / 2712
)( ALLA 5372
)1, the time required to find an e-stationary point by Malenia and the sequence tk ALLA ga/2
NIGT (Algorithms! 1 and 3) is tr seconds, where O Lg is defined recursively:
tu min {t: (+ Nilty 1887
2
M
Vk >
(9)
with to min {t: (-Ei mibeo)
Man
ACKNOWLEDGEMENTS
The work supported by the grant for research centers in the field of Al provided by the Ministry of Economic Development of the Russian Federation in accordance with the agreement 10000C311922SP4F000 and the agreement 133--00-202--03.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Carlo Alfano and Patrick Rebeschini. Linear convergence for natural policy gradient with log-linear policy parametrization. arXiv preprint arXiv:2209. /5382, 2022.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD:
Communication-llfcccent SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pp. 1709-1720, 2017.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sckhari, and Karthik Sridha- ran. Second-order information non-convex stochastic optimization: Power and limitations. In Conference Learning Theory, pp. 242-299. PMLR, 2020.
Yossi Arjovani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185(1):315-355, 2021.
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting dis- tributed synchronous SGD. arXiv preprint /604 0098/, 2016.
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k off off-policy correction for reinforce recommender system. In Proceedings of the twelfth ACM international conference on web search and data mining, pp. 456-464, 2019.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Başar. Communication-effciieell policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems, 9(2):917-929, 2021.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in Neural Information Processing Systems, 30, 2017.
Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances Neural Information Processing Systems, 34: 9024-9035, 2021.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. In International ference on machine learning, pp. 2260-2268. PMLR, 2020.
Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex SGD. In Neural Information Processing Systems, 2019.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Yang, et al. Large scale distributed deep networks. Advances in Neural Information Processing Systems, 25, 2012.
Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum- based policy gradient. In International Conference on Artificial Intelligence and Statistics, pp- 1910-1934. PMLR. 2022.
Xiaofeng Fan, Yining Ma. Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low. Fault-tolerant federated reinforcement learning with theoretical guarantee. Advances in neural information processing systems, 34: 1400 2021.
Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for fisher-non-ded degeeeerrteee policies. International Conference on Machine Learning, pp. 9827-9869. PMLR, 2023.

---

Published as a conference paper at ICLR 2026
Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, (12):3740-3754, 2016.
Swetha Ganesh, Jiayu Chen, Gugan Thoppe, and Vaneet Aggarwal. Global convergence guarantees for federated policy gradient methods with adversaries. arXiv preprint arXiv:2403.09900 049.099900 2024.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet in hour. arXiv preprint arXiv: 706.02677 2017.
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-based policy gradient meth- ods. International Conference on Machine Learning, pp. 4422-4433. PMIR, 2020.
Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis of asynchronous-SCHe algorithms. In International Conference on Artificial Intelligence and Statis- fics, pp. 649-657, PMLR, 2024.
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, 18-37. PMLR, 2022.
Peter Kairouz, 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-211 2021.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, 32(11):1238
2013.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. Advances in Neural Information Pro- cessing Systems, 2022.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492 2016.
Safwan Labbi, Paul Mangold, Daniil Tiapkin, and Eric Moulines. On global convergence rates for federated policy gradient under heterogeneous environment. arXiv preprint arXiv:2505.23459, 2025.
Guangchen Lan, Dong-Jun Han, Abolfazl Hashemi, Vaneet Aggarwal, and Christopher G Brinton. Asynchronous federated reinforcement learning with policy gradient updates: Algorithm design and convergence analysis. In International Conference Learning Representations, 2025.
Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198(1):1059-14 1106, 2023.
Sergey Levine. Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuo- motor policies. Journal of Machine Learning Research, 17(39):1-40, 2016.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. Advances in Neural Information Processing Systems, 28, 2015.
Yujun Lin. Song Han, Huizi Mao. Yu Wang, and William J Dally. Deep gradient compression: Re- ducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887, 2017.
12

---

Published as a conference paper at ICLR 2026
Songtao Lu, Kaiqing Zhang, Tianyi Chen, Tamer Başar, and Lior Horesh. Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 8767-8775, 2021.
Artavazd Maranjyan, Alexander Tyurin, and Peter Richtárik. Ringmaster ASGD: The first asyn- chronous SGD with optimal time complexity. International Conference on Machine Learning. PMLR, 2025.
Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Stochastic second-order methods provably beat sgd for gradient-dominated functions. Advances in Neural Information Processing Systems, 2022.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcienn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1282. PMLR, 2017.
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Systems, 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems, 2019.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24, 2011.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354-35) 2017.
Suvrit Sra, Adams Wei Yu, Mu Li, and Alex Smola. Adadelay: Delay adaptive distributed stochastic optimization. In Artificial Intelligence and Statistics, pp. 957-965. PMLR, 2016.
Sebastian Stich and Sai Praneeth Karimireddy. The error-feedback framework: SGD with delayed gradients. Journal Machine Learning Research, 21(237):1-36, 2020.
Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Alexander Tyurin. Tight time complexities in parallel stochastic optimization with arbitrary compu- tation dynamics. In International Conference Learning Representations, 2025.
Alexander Tyurin and Peter Richtárik. Optimal time complexities of parallel stochastic optimization methods under fixed computation model. Advances Neural Information Processing Systems, 2023.
Alexander Tyurin and Peter Richtárik. On the optimal time complexities in decentralized stochastic asynchronous optimization. Advances in Neural Information Processing Systems, 2024.
Alexander Tyurin, Kaja Gruntkowska, and Peter Richtárik. Freya PAGE: First optimal time com- plexity for large-scale nonconvex finite-sum optimization with heterogeneous asynchronous com- putations. Advances in Neural Information Processing Systems, 2024a.
Alexander Tyurin, Marta Pozzi, Ivan Ilin, and Peter Richtárik. Shadowheart SGD: Distributed asyn- chronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity. Advances in Neural Information Processing Systems, 2024b.
13

---

Published as a conference paper at ICLR 2026
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning, Nature, 575(7782):350-354, 2019.
Ronald J Williams. Simple statistical gradient-folloingg algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256, 1992.
Xuyang Wu, Sindri Magnusson, Hamid Reza Feyzmahdavian, and Mikael Johansson. Delay- adaptive step-sizes for asynchronous learning. In International Conference Machine Learning, 2022.
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. International Conference on Learning Representations, 2020a.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. In Uncertainty in Artificial Intelligence, pp. 541-551. PMLR, 2020b.
Rui Yuan, Robert Gower, and Alessandro Lazaric. general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pp- 3332-3380. PMLR, 2022.
Rui Yuan, Simon S Du, Robert M Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with linelinnar policies. In International Conference Learning Representations, 2023.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6): 3586-3612, 2020.
14

---

Published as a conference paper at ICLR 2026
A GLOBAL CONVERGENCE
Under additional technical Assumptions 2.1 and 4.6 from (Ding al., 2022) about the Fisher infor- mation matrix induced by the policy Te and the initial state distribution, following previous works (Ding et al., 2022; Fatkhullin al., 2023; Lan et al., 2025), we can guarantee global convergence up an v 22' V neighborhood:
Theorem A.1. Let Assumptions 2.1, 2.2, and Assumptions 2.1 and 4.6 from (Ding et al., 2022) hold. Consider Rennala NIGT (Algorithm I and Algorithm in the homogeneous setup, or Malenia NIGT (Algorithms and Algorithm 3) in the heterogeneous setup. Let Mmit vLs
max { {[
_ o² LLn p=² 1. M max {[( (0/4 )((
u (x1 11, =minn
Mus 64 22
Then log (+) global iterations, where Parameter Ebios is an approximation envor and pe is the small- est eigenvalue of the Fisher information matrix induced by the policy no and and the initial state distribution (Ding et al., 2022).
min The "E 1. snyM }. H
max { log, maxx(
vuen
8L, L. V2p'
[ J(Or)] I 8 + f2d after T = O ((22 JLn paie
= pr /enuee M,(1->) and p == 2M2
Hr
In this case, the time complexities of Rennala NIGT and Malenia NIGT follow the same structure in Sections 4.1 and 5:
Theorem A.2. Consider the results and assumptions of Theorem A.I. Additionally, consider that Assumption 2.5 holds. The time required to find an E-solution up /2e' vp neighbor- hood by Rennala NIGT (Algorithms 1 and 2) in the homogeneous setup is
(
Ki
La
+
LLn pol4/e)
I-
min mE/n]
m ha
La
+ μr
LL 13/4
+
mpe?
oF mp774g513
Theorem A.3. Consider the results and assumptions of Theorem A.I. Additionally, consider that Assumption 2.5 holds. The time required to find an e-solution up to /2e' Vp neighbor- hood by Malenia NIGT (Algorithms and 3) in the heterogeneous setup is
Lig
TTh MO/A
T
im
Lu ps
Tom 4O/A
+
hi
o² nuEZ
Th
))
i=
B NOTATIONS
: 21,2,.. ... [n] (1, (1....n); n); ||-|| is the Euclidean norm; (a, v) Eí aay is the standard dot product: ||||| is the standard spectral norm for all A E Rdxd:
O()) there exists C > such that g(z) < C x f()) for all 2 E Z; g = l(f)): : there exists C 0 such that g(2) 2 C x f(z) for all 2 E Z; g = (f)) if O()) and g O(f) ~ h g and h are equal up universal
positive constant; O 02 θ the same O, Ω. θ but up to logarithmic factors.
C USEFUL LEMMAS
The following lemmas provide the time complexities of collecting stochastic gradients in Algo- rithms 2 and
Lemma C.1. Under Assumption 2.5, Algorithms returns the output vector after at most
-1 (M + m)) m) 1) =0 min mE
(1 ( -++1) +1))
Σ his
K + min mE(n)
seconds.
15

---

Published as a conference paper at ICLR 2026
Proof. Let
min mEin
Σ hig
(M + m)
As soon some agent finishes computing stochastic policy gradient, it immediately starts com- puting the next onc. Hence, by time f, the agents together will have processed least
stochastic gradients. Let
(M +m)
m arg min
Σ hi
mE(n)
Using [x] 2 x
for all r 2 0, we obtain
m
m
m
m
(M + m²) (D
mmm M.
h
h4
h4
h4g
h2
Therefore, by time t the algorithm has collected at least M stochastic gradients and exits the inner loop. Returning the output vector then requires single communication//ggrraatinn which by Assumption 2.5 takes at most seconds (via a server or AllReduce for instance). In the centralized setting, broadcasting would also take at most i seconds. Thus, Algorithm 2 returns after at most
t + 2K O minmel)
(EE 1..)
(M + m))
seconds.
Lemma C.2. Under Assumption 2.5, Algorithms returns the output vector after at most
n
M Y2
k hn +
71
i=1
seconds.
Proof. By Assumption 2.5, broadcasting 0 takes at most к seconds. After that, the agents compute in parallel and after h. seconds each agent has completed at least one gradient. Thus, M; 1 for all i E [n] after hn seconds. Let us take
12
M
n
n
For all e [n], after bn + +t seconds, agent i produces Mi(t) gradients, where M,(t) satisfy the inequality
since agent can calculate at least
gradients after t seconds. Using [x] 2 x for all æ E R,
he
h
S 1+
5
M,(1)
[1/ba]]
7.
Summing over i yields
x2
1
1 1
1 Σ
h4
M,(t)
M
and
1 ト
M((t)
1=1
16

---

Published as a conference paper at ICLR 2026
Thus, by time Mi & the while-condition ( E terminates. Returning the output vector then requires most additional seconds. In total, takes
M.
Mr becomes false and the loop
M
Ki + hn +
hi
1=1
seconds.
D PROOF OF THEOREMS
We start with supporting lemmas and then apply them in the proof of the theorem. Lemma D.1. Let Assumption 2.1 and 2.2 hold, {d,) is any sequence vectors from Rd and 0.+1
8, +
de where 8g E IRd and we use the standard convention 0/|ijl| 0. Then [
- - |VV 2a |d VJ((.)) + aga²
(10)
2
for every integer t 2 0.
Proof. Using Proposition 2.3-(1) (or Proposition 2.4-(1)) and the update rule, we get
Lg
-J((++1) S -J(,,) (VJ()))) 02)
|
- -
2
-((,)) a (V.) d,) +
Lg
a
||d,
|
2
[d
-(v)
a
|dell
a (V)(0:) de, de) + Lga?
[d
dell
2
|ddl|| + a || vJ(0,))l + Tyya²
S ((.))
2
where we use the C-S inequality. Using []] < ||del| + +Idd - VJJ(B:)l we have
Lyga
J(( x ((,,) [ (0.))) + 2a 14 - VJ(0.)] +
2
Let E, [ be the conditional expectation condition on all randomness up tt iteration. In the next lemma, we bound ETD Elild JJ (6x))ll
Lemma D.2. Let Assumptions 2.1 and 2.2 hold. Consider Algorithms and assume that
o² Mmnt
E [dg] (0,) and E |Ido - [JHr(0e)11 <
(11)
and
0²
Eg [gd = (..) and E, -J
(12)
M
in Algorithms / for any integer 1. For every 221,
Eilld VJ <
n) v M
σ
+ v
Ln
2a
+
4D AD,
2D
VM
np
n
11
Moreover, for every 2 1,
T-1 Σ VJ JJ
ViTT
2a L.T
4Dg
HT
HT
+
+
VMaan
VM
n
1=
where Dy and Dr, defined in Proposition 2.3.
17

---

Published as a conference paper at ICLR 2026
Proof. Let define
& = dp - (OH(
G = dt VJH (0.),
S. (JH((O-1)) VJ,((,,) V'0(0001 01),
VJ(0,) VJ((--1)
-- 01),
Z = V.)) V)2((0)) + V=)= - B1),
2 = VJ VJ(()) -=)
Using triangle inequality and Proposition 2.3-(2).(3) (or Proposition (.4- we get
|| _ La |10, 0--111 + S. - S. =Laa² +2D " DiT a.
(13)
Similarly,
2z S Ln. (1 =2=
2D Day (1 (1- n)a
(14)
x
7
Applying the update rule for de Algorithm 1:
di (1 11)dd111 nlt
(15)
connecting this with notation for St and Z,, and using 0, 0c + 1- (0, -b,-1), we derive the recursion
((,) (1 (1-1-))0 1 + 19:
VJH (0:)
= (1 7)) + nre + - (1- + 7/
We can rewrite unroll the recursion and get
1-1
é (1- VJn((e))) + (1
()- er41 + (1
r-r-1
S 1
1)
1-7-1
Zr+1.
Now, we estimate the expectation of the norm. Using triangle inequality,
t-1 Σ (1
B|[@e|l] & (1 (1-1)<R[(dd, - VJ (0n))lll1 + tE
11)
1-r-l
ex+1
+
[-1
+ (1- M)
Σ
n) r- S
+ +nB
Σ
(1
17)
(-
Z++1
r=0
11)
1/2
[-1 Σ (1 11 1 1-41
σ Minit
$ (1 1))
C741
+
T=
+
m)
Σ
- +
Σ
(1
--T-1
E 1r+1
7=0
7=0
where we use the Jensen's inequality triangle inequality, and (11); Using (12). for all > j. E. [ee,, eg)) E [E, K(e,, ez)] = E [(T, ey)l 0, and we get
1-1 (1 7)
0²
1/2
&|| < (1 (1-m)²
o
+
20-
+
M
M
7=0
t-1
+ (1-1) 17)
17)
--r E|||S++111 + Σ
(1- 21
7=0
T=0
<(1 (1=n)²
vī VM
+
(1 7) Σ
E
+ Σ
(1
E
7
VMui
-=0
18

---

Published as a conference paper at ICLR 2026
where we use E 2))((-1-1) _ "7 Using (13) and (14),
[||l& S (1 - -))²
Vi
Mint
VM
[-1
+
11)
Σ (1 7)- --1 (I + 222 + ()
T=0
1-1
(1 - a)²
2D + Dny (1 11ax
+
Σ (1 7)²
Ln
n¹²
r=0
$ (1 - 1))²
0
Ln
2a²
+ 2 H +
4Dg
Mini
VM
rp
n
where we use Σ (1 77) - < y
and 0 < 1
It left sum the inequality and use Σt= (1
7)²h s 1 to get
T
2a L,
4D
"T
+ 2aDnn
Ellle
vn
T +
+
Minan
VM
172
Theorem 4.1. Let Assumptions 2.1 and 2.2 hold. Consider Rennala NIGT (Algo- rithm and Algorithmm 2) in the homogeneous setup, or Malenia NIGT (Algorithms Me and Algorithm 3) in the heterogeneous setup. Let n = min 64 2 a = Ö(V(-1)). Let Or be uniformly sampled iterate from (6o. -1-- Then E ||| Lg VLnA 2312
11
min {si,- ' AA/Ls H max (log, (e ..1
after T
VTAA global iterations. MeT13
M Maaes
Proof. We rely on Lemma D.2, which requires du and {gt} to satisfy (11) and (12). For Rennala
NIGT with Algorithm 2, this condition holds because E [g] = M Σソ [gH (Fy, 0)] = VJH (0) for all 0 E R2d where F, ~ p(-(TT) are i.i.d. trajectories sampled by the agents. (For instance, if agent is the first to return a stochastic gradient, then Fn = T1.1- If agent 3 is the next, then F22 = T3.1
agent 1 returns again, then 71,2, and so on.) Moreover,
M
1
E 110
E
9H (T, (0)
M
M
x²
ΣE B 1lg
M J=1
M
for all 0 dd due to the unbiasedness, the i.idd nature of the trajectories, and Proposition 2.3-(4).
In the case of Malenia NIGT with Algorithm 3, (11) and (12) also hold since E | Σ Mi
Me E (I 0)] = Σx (), (0)()), and
1 M.
M.
1
1
E
I.H (T. (0)
=
Σ
D.. 0)
V J.H
M
M
i=1
==1
M.
1
1
E
II (T.) (0)11
o²
M
for all E Rd, where we use E Ig. (Tr,,, 0) V).n(() for E [n].j 2 1, independence, and Proposition 2.4.(4). It left to the exit loop condition of Algorithm which ensure that
19

---

Published as a conference paper at ICLR 2026
(1>E>=11/m 1/a5.)=1
M/n and
o²
E
g (. -) V
M
Using (10) from Lemma D.1 and summing it for I. = O,...,
1
4
- - - (J' - J(06) a7 Σ E(I
+ +a
E [[]d VJ(O.)
t=
Due to - 2 0 and Lemma D.2,
E [[ N aT
Lga
+
20
+ +2
0
4 Ln
+
DDn
4a
T t=
2
In
VM
1p
11
Choosing H = max
log
max (D (Dg,DDn))) ).1) we get
on
8D,7 1
4a 1
and
7
11
[
+
4
20
+ 2
σ
+
4a Ln
E
af
2
MmiiT
VM
1/2
4
Now, we a min
nvE
get
Tv La.
T
<
A
+
2a
+2
0 VM
+
T 1=
aT
MMiin
I'm)
2
0
Me² 1 G402
We choose 77 min
25
A
20
35
E [[I
+
aT
V
Mini Tm
4
t=0
Thus, the method converges after
T
0
M
Lg A
0
2
2
V Sm
4
V
0² VV A
3
g3/2
Me7/2
Vinue
M MMnis
global iterations.
E TIME COMPLEXITY
E. TIME COMPLEXITY OF Rennala NIGT
Theorem 4.2. Consider the results and assumptions of Theorem 4.1. Additionally; consider that
Assumption 2.5 holds with i. (ie., communication free). Taking Min: max {[g" 1,1 and
M max [[ + o² V',A 1. + vILA )1 )1,1} 1,,, the time required to find E-stationary point
27/2
by Rennala NIGT (Algorithms and 2) is
θ
min mE(n|
-
4gA
LLA 2/4
+ me7
AVLA mETrY
(6)
h4
20

---

Published as a conference paper at ICLR 2026
Proof.
With our choice of M and Mint, the number of global iterations to get an stationnary point
Li
VLAA
VvVTAA
==O
62
3/2
M
VMine o² oVVLA
Minis M
A
o²
VLA e3/2
=0
=0
g3/2
M
MET/2
E2
Notice that the time requires to collect stochastic gradients in Algorithm is
(M m))+m) 1)
ΣΣ
min mE(u
h4
with x due to Lemma C.1. At the beginning, the algorithm collects Minit stochastic gradients
that takes O minmmen)] (Em A.. (Miit + -m) seconds. Then, in each iteration the agents
collect M stochastic gradients, which takes O millmme (Σ #t)
(M + m))
m)) seconds.
Thus, after T iterations, the total time to find e-stationary point is
(Miii + m)) ))
m (M + m)
o
Tx min mEIn]
min me [ms]
Σ h4
hgg
-1
1)
m
4
V
o²
0² VVVLAA
min mEIn]
+
771
ha
82
3//2
m
me7/2
-1
)
1 m
a²
+0
min mEin
m
h4
m
1)
m
LgA
o²
o² Lz
=0
min
mE(n]
m
h4
E2
g//2
m
7/7 7/2
It is left substitute h; = h4 H and recall that H Ô to get (6).
Theorem 4.3. Consider the results and assumptions of Theorem 4.1. Additionally, con- sider that computing a single stochastic policy gradient g on agent i in iteration re- quires at most hes x H seconds. Taking Minit = max {|
and M = =max {[ +
63/2 x)AA))) the time required to find an e-stationary point by Rennala NIGT (Algorithms and 2) is 0(111- Et minme(m) [(th Em 1/heme,) (M/m + 1/1-y minme[n] ( ET 3/be,oa.) (Dtafmm + 1)]),, where T (L.0/e2 @ + vInafer2) and Tt is permulation such that be. S... S he.
E712
Proof. The proof is the same as in Theorem 4.2. One should only notice that the total time com- plexity is
M +1
:)
Mini m
min mEnn
+ min mE(m)
hem
he
because Algorithm 2 requires at most minmefn]
M ( m
+ +1)
seconds to col-
lect batch of size M in hh iteration, and min
Σm
(Alut + 1) seconds to
collect batch of size Mmn before the loop. It is left substitute hisj his H.
21

---

Published as a conference paper at ICLR 2026
Theorem 4.4. Consider the results and assumptions of Theorem 4.1. Additionally, consider that -
Assumption 2.5 holds. laking Min = max 11 and M max {[(
( /
+
A )1 13, , the time required find an e-stationary point by Rennala NIGT (Algorithms and 2)
23/2
is
hi
Lga
LLLA 23/2
I-7
min mE
1
R
Ly g
LLL 23/2
me
o" VVLn
me?/3
Proof. The second term in the complexity proved in Theorem 4.2. However, Theorem 4.2 does not take into account the first communication term. Using the same reasoning, after T iterations, the total time to find an e-stationary point is
o TXK+TN
min mE(n)
Σ The
(M + m)
+ min mE(m)
Σ
(Minit + m)
l0g
Tig E2
VTn
1
Lig A 22
VT.AA A
o²
o² o2vI.AA
0
+ min mE(N
g3/2
m
h4
ga/2
me²
m²7/2
It is left substitute h4 = ha H and recall that H Ô
E.2 TIME COMPLEXITY Rennala NIGT UNDER ASSUMPTION 7.1
Theorem 7.2. Consider the results and assumptions of Theorem 4.1. Additionally, consider that 1} and M max {[(g oZVL,
Assumption 7.1 holds. Taking Min max 1
(
8
AL 11.1 11, the time required find an e-stationary point by Rennala NIGT (Algorithms and 2)
by seconds, where T 0 (1ag
and the sequence tt is defined recursively:
2.12
t min {1 Σ N.((x-1, M
Vk 221
with to min (t: Σn No(0,)) 2 Mmn..
Proof. With our choice of M and Muns the number of global iterations get an e-stationary point
T Lig
VTAA
g3/2
At the beginning, the algorithm collects Mini stochastic gradients that takes
to min f+ Σ No(O.t) 2 Mmit
seconds because (0, t) is the number of calculated gradients in agent i and they work in parallel. Then, in each iteration the agents collect M stochastic gradients. The first iteration finishes after at most
41 min t Σ CN((to.t) 2 M
1=1
seconds. Similarly, the ttth iteration finishes after at most
ts = min t Σ M(
seconds. Thus, T iterations finish after most by seconds.
n
22

---

It is left to Published as a conference paper at ICLR 2026
E.3 TIME COMPLEXITY OF Malenia NIGT
Theorem 5.1. Consider the results and assumptions of Theorem 4.1. Additionally, consider that Assumption 2.5 holds. Taking Min max {[ 1 and M max {[( o² dL ) 4 +
A
11, the time required to find an E-stationary point by Malenia NIGT (Algorithms 1 and 3)
ALLA 3372
+
I
hnn (#2A
VLnA 2/2
+
Σ
h:)
ne -
Proof. Similarly to the proof of Theorem 4.2, with our choice of M and Mint.
T= Lg
VIA
e3/2
At the beginning. the algorithm collects Minit stochastic gradients that takes O (x + hn (H h2) Muk) seconds due to Lemma C.2. Then, in each iteration the agents collect M stochastic gradients, which takes (N + hn + (1 Eis h;) a) seconds. Thus, after T iterations, the total time to find e-stationary point is
0
Minit n
M
hn
hi
T x
+ hn
h4
Lgg
A
V
0²
0²
o'VLNA
0
+
(K hm)+
h4
+
Σ h;
E2
e3/2
nE²
nE2
no7/2
i=1
V
0²
0²
0
(k + hn))
hi
E2
g3/2
nE2
T/7
where we substitute our choice of M and Mini, and use T = o
0
4g
23/2
substitute h4 = h4 x H and recall that H δ
E.4 TIME COMPLEXITY Malenia NIGT UNDER ASSUMPTION 7.1
Theorem 7.3, Consider the results and assumptions of Theorem 4.1. Additionally, consider that Assumption 7.1 holds. Taking Min max { 111 and M max { {[(g o² o'vLn
// 4,A
(
+
V. 2/2 11,13, the time required to find an e-stationary point by Malenia NIGT (Algorithms I and 3) by seconds, where T ===0 (Lي
ALLA
and the sequence to is defined recursively:
2/2
to min t: ( E. No(1a-1.15
M
Vk 2 1
(9)
with to min tt: (1 Ei m.o.))
Man
Proof. Similarly to the proof of Theorem 4.2, with our choice of M and Miniss
T=O T
VTA
E3/2
At the beginning, the algorithm collects Mini stochastic gradients. According to Algorithm 3, we wait for the moment when
1
1
Min
M₁
n
1=1
23

---

Published as a conference paper at ICLR 2026
Since M₁ t), the initial phase finishes after at most
to min { [ N.(O.))
(HEMO.))
Minit
n
seconds. Similarly, the hthh iteration finishes after at most
4. = min { b:
{
M
2
Ne((x-1,t)
seconds. Thus, iterations finish after at most by seconds.
F GLOBAL CONVERGENCE
Lemma F.1 (Relaxed weak gradient domination (Ding et al. (2022))). Let Assumption 2.1 and Assumptions 2.1 and 4.6. from (Ding et al., 2022) hold. Then.
E' + ++|V01 2 2u(J - J(0)),
for all 0 IRd, where e'
Eettns and μ = 2M Parameter Etios an approximation error (1(1-9)
and py is the smallest eigenvalue of the Fisher information matrix induced by the policy and and the initial state distribution (Ding et al., 2022).
Typically, the parameter Stios is small (Ding et al., 2022).
Theorem A.1. Let Assumptions 2.1, 2.2, and Assumptions 2.1 and 4.6 from (Ding al., 2022) hold. Consider Rennala NIGT (Algorithm and Algorithm 2) in the homogeneous setup, or Malenia NIGT (Algorithms and Algorithm 3) in the heterogeneous setup. Let Mmit {
2² usz : 1}. M = max {[( +
o² JZ (t/4gb/2) ( + p=iaaE (...,))..1.. =min
= -min Musa 11
max
min Vue WI 1. eny/Mm }.
Juen = max log, (6Tmax Da 13. Then JLn 13/a//
a
8Lg" w/Ln V2p
So
E E J(OT)]
32c'
log (-) global iterations, where Parameter Ebios is an approximation ervor and pe is the small- 2M.
after T T= 0 ((
vp
pe
Peveosis and p. =
the
M2(1-3)
est eigenvalue of the Fisher information matrix induced by the policy no and and the initial state distribution (Ding et al., 2022).
Proof. In the proof of Theorem 4.1, show that (11) and (12) are satisfied, and we use Lemma D.2. Using (10) from Lemma D.I and Lemma D.2:
Lya²
E [J" J(0++1) < E J(e,)] aE ||| (e,) + 2aE I||e - VJ +
2
< E| J(0.)) [
+ 2a (1 (1=n)² Min
σ
2a²
4D, H
11
Lya2
vi
L
2D
VM
7
11
2
Due to Lemma F.I.
E E J(0++1)] < (1-av21) EsJ [(,)] + aee
+ 2a (1 (1-n)²
v VM
Lb
2a²
4D,
2Dz
Ha
m)
Lga²
/ Min
nu
24

---

Published as a conference paper at ICLR 2026
Unrolling the recursion,
E E - -((++1)) (01==(110) (1-a/24) 1+1
B - J(0o]]
2a
Σ
(1- (1-0/2m)) (11 (a--)) (1--))-i
vn VM
+ Ln
2a
4D,r
2D
H1 = e''
L
VMmn
qp
n
"
2
1=
1+1
22/22)
E [J [(0)]
20
Σ
(1 (1- 1)) a
Vini
i=0
2a²
4D, I1
+ 222 11 + e Lg
2a
Σ
1 1- a. 22/2p))))))
V1 VM
Lb
+
1p
i=0
Using Eizo (1 - a//2)) S avvz for all a S
1 and Ei=0(1 - 11) S for all s 1,
V2n
B [J - [(++1)) s
(1-0/221) (1
E [ - [(0o)] + TV Mmni
200
v2
2a²
4Dg H
+ 2D a + Leg
Ln
V
VM
n
It is left to apply our choice of the parameters to get
E[J - J(0r)] (1 alaa//2))
T
V2e'
+
4
v
1et V28'
Vp
after T ittertiion.
F.1 TIME COMPLEXITY OF Rennala NIGT
Theorem A.2. Consider the results and assumptions of Theorem A.1. Additionally, consider that Assumption 2.5 holds. The time required to find an E-solution up to /2E' vP neighborhood by Rennala NIGT (Algorithms I and 2) in the homogeneous setup is
))
Lg
Lh
min mE(n)
Lg As
L 3I
d² mue?
o² ozvLn
I-7
my 74/7/3
Proof. With our choice of M and Mint the number of global iterations is
T= (Le++
VLn 1O3/1
log ()))
(16)
Notice that the time requires to collect M stochastic gradients in Algorithm 2 is
(M + m) )):
o min me [s]
Σ h
due Lemma C.I. Thus, after T iterations, the total communication time is
m
-1
m
-1
T
+ min mE(n)
(M + m)
min [n]
Σ
(Mii + mi)
h3
h
1)
-1
+ +1)])
m
M
MMni
=
T T
min me(n)
+
min mE(m)
h
m
m
hrs
m
25

---

Published as a conference paper at ICLR 2026
Using the choice of Miit and M, and the bound (16), get the time complexity
Lg
Ln
(
L
In
0² VL +
my0148512 )))
16
+ min mEn
Hee
1.3/1
hes
mpe
o²
+
min
mE(m]
his
o² oLVLR m4 ))
= K
La uee
Ln 1///AVE)
m
Lg
vLn
o²
+
+ min mEin]
muuu +
m
h4
ue
13/9Ve
is left to substitute h; = h4 x and recall that H1 = (1
F.2 TIME COMPLEXITY OF Malenia NIGT
Theorem A.3. Consider the results and assumptions of Theorem A.I. Additionally, consider that Assumption 2.5 holds. The time required to find e-solution up /2e / //p neighborkood by Malenia NIGT (Algorithms and 3) in the heterogeneous setup is
1) ripe 11p53
①
hin
L/ us
o² Dige?
a² PT
Vie
1-7
VEE
Proof Sketch. With choice of M and Minis the number of global iterations is
((
Tig uE
vTR /3//
A
T=o
log E
Notice that the time requires to collect M stochastic gradients in Algorithm 3 is
("=
M
o K + Nn +
Σ
hi
n
72
due to Lemma C.2. Thus, after T iterations, the total communication time is
M
n
Minit
o
T x
K + hn +
hi
+ O
K + hip +
-
his
11
n
71
n
i=1
MT
1
Mint
= (KT) + 0 (h +0
h4
+
K K
hn
+
hg
n
n2
i=1
Using the choice of Minit and M, and the bound T, the total communication time Oo
1 Σ
( mnuu +
o2vLnn )+ 1471115/2
o²
o
KT +
h T +
hi
+
h
nuea
i=1
i=1
Lg
v Li
Lg +
VLn
0²
0²
o2
O
+ hn
+
Σ
hi
11/44 Ve
13/4
nque2
ny
1=1
It is left substitute h; = hi H and recall that H = δ
L
G PROOF OF THE LOWER BOUND IN THE HOMOGENEOUS SETUP
In this section, we prove a lower bound for a family of methods that only access unbiased stochastic gradients of an (Lg. -tw-t smooth function F with bounned stochastie variance. We should clarify that our lower bound applies only to methods and proofs that use stochastic gradients (3) as black-box oracle. In other words, our lower bound applies all methods and proofs for which it
26

---

Published as a conference paper at ICLR 2026
is sufficient take Proposition 2.3 as assumption with Lg. Li. and o² being constants. For proof strategy, as well as the previous state-of-the-an strategies (Fatkhullin et al., 2023; Lan et al., 2025), this is the case. Extending the lower bound to methods that fully utilize the structure of J in (1) is an important and challenging problem. Nevertheless, to the best of our knowledge, this the first attempt to provide lower bound for asynchronous and distributed setting.
Theorem G.1. For all A O, Lg. Ln. E > O, and a > 0 such that = ( there exists an twice smooth function F with Lipschitt gradients, L,, Lipschitt Hessians, and F(O) -F* I A, and an oracle that returns unbiased stochastic gradients with a-bounded gradient variance such that any first-order zero-respecting algorithm, where the agents communicate with the server or other agents to update an iterate, requires at least
Li 3/7 2/7 A
me² +1) min
0²
( 52
VI g3/2
Q
K
H min mEnD]
12/7
m
seconds under Assumption 2.5 to output an s-stationary point with high probability.
One particular direction is to extend the result to methods with variance-reduction techniques (Huang et al., 2020: Ding et al., 2022; Xu et al., 2020a;b; Fan et al., 2021), which rely on im- portance sampling (IS). Since the distribution of trajectories is non-stationary, such methods require an additional strong assumption that the IS weights are bounded. Our lower bound applies to all methods that do not require this additional assumption, and extending the lower bound to settings with these extra assumptions is an important direction for future work. Moreover, it would be in- teresting extend the lower bound Hessian-aided PG methods (Fatkhullin al., 2023; Ganesh et al., 2024), which will also require taking into account an extra assumption in the design of lower bounds that the variance of Hessians bounded.
G.1 PROOF OF THEOREM G.1
Proof. We are slightly concise in descriptions since the proof almost repeats the ideas from (Arjevani ct al., 2022; Carmon et al., 2021; Arjevani et al., 2020; Tyurin & Richtárik, 2023; 2024; Tyurin al., 2024b). In particular, Tyurin & Richtárik (2023) provided the proof of the lower bound
m (+ m
m + +1) x 7
min mE(a
h4
for -m-ooho functions F without second-order smoothness, where T = - following (Arjevani et al., 2020) and using the same scaled "worst-case" function as (Carmon al., 2020; Arjevani al., 2020; 2022), we have to take a different dimension
4. (4.2)) However,
@ min {
Lg viv = min
4
LA
})
T T= +
3/2
instead of A,A to ensure that the function has Lm-smooth Hessians (we take T in (84) from (Arjevani et al., 2020)). Thus, the lower bound
(=
+11 min
{
Agg 22
VLAA A 3/2
á min mE(x]
m +
It is left to substitute h; h4 H. We can get the communication term using the deterministic construction from (Carmon et al., 2021), which says that required number call of the first-order oracle is
3/7 1 12/3A
Ω
212/7
3 2//T
Thus, the lower bound for communication Ω
K e/2/7
seconds under the assumption
that the agents communicate with the server other agents after every gradient computation. n
27

---

Published as a conference paper at ICLR 2026
H EXPERIMENTS
In our experiments, we compare the performance of Rennala NIGT with AFedPG by Lan (2025) and with the synchronized version of NIGT (Synchronized NIGT), where all agents compute one stochastic gradient, aggregate them in a synchronized fashion, and perform the standard NIGT step (Fatkhullin et al., 2023). We focus the MuJoCo tasks (Todorov et al.. 2012). We consider the standard setup, where the actions are sample from Gaussian policy. Given a state s, the policy outputs mean (s) and standard deviation de (s) > 0, and samples
Uy no(
(po diag(()(())))
Then, the actions are defined as 0r = a lanh(w.), where a is an appropriate scaling factor (for the most MuJoCo tasks, 1). We take the neural network architecture + Linear(664, 64) - Tanh - (Linear(64, d,) - f4g Linear(64, da) - Softplus - oe). where d, and d, are the dimensions of the state and action spaces, respectively.
Linear(d,, 64) + Tanh
We consider the centralized setting with different computation and communication scenarios, with h; denoting the computation time of agent and K; denoting the communication time for sending one vector from agent i to the server. For instance, if h; = 1 and x; = O. then agent computes one gradient in second and sends it to the server without delay. Unlike Section 2.3, in the experimental part we consider a more general setting where agents have different communication times. However, Assumption 2.5 still holds with max Kig.
sE(n]
We rum every experiment with seeds and report (20%, 80%) confidence intervals. All meth- ods start from the same point, for a fixed seed, and have two parameters: the momentum E We tune both the Humanoid-
{0.001, 0.01, 0.1} and the learning rate {2 12-10,2- .......-11 2-1 v4 task with equal computation speeds and zero communication delays and observe that rj = 0.1 is the best choice for all algorithms. However, is tuned differently for different algorithms. Thus, in the following experiments, we tune a E {2-10 2-9 ,- 2-,,, for every plot and algorithm. Our algorithm Rennala NIGT has the additional parameters M and Minit- We take Minit M which is tuned as M {20, 30, 50}.
The code was written in Python 3 using PyTorch (Paszke et al.. 2019). The distributed environment was emulated on machines with Intel(R) Xeon(R) Gold 6278C CPU @ 2.60GHz and 52 CPUs.
H.1 EXPERIMENTS WITH DIFFERENT ENVIRONMENTS
We start with the experiment Humanoid-v4 from the main part of the paper (see Figure or Figure 2). We consider horizon 512 and n 10 agents with equal computation speeds and zero communication delays: h, 1 and N; 0 for all [n], and observe that the performance of all methods is almost the same, which is expected. Then, we increase the heterogeneity of times by taking h4 = Vi and
vi for all E [n)], and h; = Vi and K; vi x //4 for all E [n], where d the number of parameters. We observe that Rennala NIGT the only robust method, and converges faster than other methods.
129
Perna NCT
Rerna NET Syncrenzed NOT AfcsPo
Syncnizzed
Syncron and NCT ARouPO
AFeePG
(a) Equal times: h 1, K; (similar rates since times are equal) K; vi
(b) Heterogeneous times: h: Vi, (c) Increased communication
times: h, = Vi, Ki
Vi Vix
Figure 2: Experiments Humanoid-v4 with increasing heterogeneity of times (from left to right).
28

---

Published as a conference paper at ICLR 2026
We also consider other environments in Figure 3: Reacher-v4 with horizon 1024, Walker2d-v4 with horizon 1024, and Hopper-v4 with horizon 1024. We observe that our algorithm converges faster on Humanoid-y v4 and Reacher-v4, However, for Walker2d-v4 and Hopper-v4, v4, the gap between the algorithms is less pronounced.
200
Sanrals MET
Sennsia HIST
Sennsis HIST
Syncrsn RAST
Symtzn and NST
Symazo and NIST
Environment: Reacher-v4
(b) Environment: Walker2d-v4
(c) Environment: Hopper-v4
Figure 3: Experiments on MuloCo tasks with h; Vi, K4 vi d/44
H.2 INCREASING NUMBER OF AGENTS AND MORE SCENARIOS
We now verify whether Rennala NIGT performs better as the number of agents increases 100. Moreover, we examine different computation scenarios to validate the robustness of Rennala NIGT. Once again, in the equal-times case shown in Figure 4, all algorithms scale with the number of agents and exhibit similar performance, which is expected.
Next, consider four heterogeneous computation and communication scenarios: In Figure 5, communication is free while computation times are heterogencous. We observe that Rennala NIGT converges faster; ii) In Figure communication times are equal to computation times. Here, Rennala NIGT still achieves the best convergence rate; iii) In Figure 7, we increase the communication time and observe that the performance gap also increases: Rennala NIGT is significantly faster, which aligns with our theoretical results (see Table 1); iv) Finally, in Figure 8, we examine the case where computation times decrease and find that Rennala NIGT remains the fastest method.
500
450
400
Rennala NIGT
39
Rennala NIGT
Syncronized NIGT
Syncrenized NIGT
AFedPG
AfedPG
100
100
200
-310
Time
Time
(a) Environment: Humanoid-v4
(b) Environment: Reacher-v4
Figure 4: Experiments on MuJoCo tasks with h; 1, K; = 0 and = 100 (similar rates since times
are equal).
29

---

Published as a conference paper at ICLR 2026
500
450
Rennala NIGT
Rennala NIGT
Syncronized NIGT AFedPG
Syncronized NIGT
AFedPG
100
-10
Time (4)
Time (n)
(a) Environment: Humanoid-V -44
(b) Environment: Reacher-v4
Figure Experiments on MuJoCo tasks with h; Vi, K; 0 and n 100.
Rennala NIGT
Re Bennala NIGT Syncronized NIGT AFedPG
Syncronized NIGT
AFedPG
100
-35
14030
Time (s)
Time (8)
(a) Environment: Humanoid-vž v4
(b) Environment Reacher-v4
Figure 6: Experiments MuJoCo tasks with h, Vi, R4 vi and 100.
500
-10
-15
350
-20
100
200
Rennala NIGT
Rennala NIGT
150
Syncronized NIGT
Syncronized NIGT
AFedPG
5000
I0000
15000
20000
25000
5000
10000 15030'
20035
25000
30030 35000 40000
(a) Environment: Humanoid-v4
(b) Environment: Reacher-v4
Figure 7: Experiments on MuJoCo tasks with h; = Vi, = Vi x d//4 and n = 100.
30

---

Published as a conference paper at ICLR 2026
500
-10
-15
350
20
200
Rennala NIGT
-10
Rennala NIGT
150
Syncronized NIGT
Syncronized
AFedPG
AFedPG
100g
10000
20000
30000
40000
50000
10000
20005
300m0
a000
500oo
Time
(a) Environment: Humanoid-v4
(b) Environment: Reacher-v4
Figure 8: Experiments on MuJoCo tasks with h4 = 21/4 K6 = vi x d and n = 100.
31

---

Published as a conference paper at ICLR 2026
H.3
HETEROGENEOUS SETTING
400
350
100
Roward
200
Malenia NIGT
150
Syncronized NIGT
AFedPG
100g
10000
20000
20000
40000
50000
Figure 9: Experiments on Humanoid-v4 in the heterogeneous setting.
In this section, we compare Malenia NIGT, a method designed for heterogencous setups. This section repeats the previous experimental setup with one important difference: the agents sample trajectories from different environments. We take two agents, n = 2. The first agent has access to the standard Humanoid-Ve y4 environment from MuloCo. However, the second agent receives inverted states. More formally, when the first worker performs action a,, the Humanoid-v4 environment returns state 8t+1, and instead of immediately receiving it, concatenate the value 0 to 8t+1, and finally redirect (s 0) to the first agent. In the case of the second worker, we redirect (-8++11 1), where we multiply the state by -1 invert it. Thus, the second worker gets inverted states. We concatenate the values 0 and 1 to indicate the type of environment to the agents and to the model. This way, we can compare algorithms and analyze their capability to handle heterogeneous environments. We present the results for n = 2 workers with hn 1, hı 10, and no communication overhead, emulating the scenario where one worker much faster.
In Figure 9, we can see large gap between Malenia NIGT and AFedPG: Malenia NIGT achieves much higher reward, as expected, since provably supports both heterogeneous computations and heterogeneous environments (see Section 5 and Table 2).
32


Reviews:
[{"review_id": "LjW3ukryhO", "reviewer": "Reviewer_Codc", "summary": "This paper introduces two asynchronous distributed policy-gradient algorithms for reinforcement learning:\n\n* Rennala NIGT for the *homogeneous* setting (all agents share the same environment), and\n* Malenia NIGT for the *heterogeneous* setting (each agent may have a different environment).\n\nBoth algorithms combine the NIGT policy gradient update (Fatkhullin et al., 2023) with asynchronous aggregation mechanisms adapted from recent federated SGD literature (Tyurin & Richtárik, 2023). The paper provides wall-clock convergence guarantees (in terms of computation and communication time) to reach an ε-stationary point under standard policy gradient assumptions. A lower bound for twice-smooth stochastic objectives is also presented, and empirical results on MuJoCo tasks illustrate the wall-clock speedups.", "questions": "Please see weaknesses listed.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The problem setting (efficient RL under asynchronous environments even with heterogeneity) is important and highly relevant.\n* The paper is clearly written and the proofs are easy to follow.", "weaknesses": "**Novelty.** Conceptually, I struggle to see what is new here. The algorithm appears to essentially be a direct combination of two known components:\n\n* Rennala/Malenia from federated SGD (Tyurin & Richtárik, 2023), and\n* NIGT-based policy gradient from non-distributed RL (Fatkhullin et al., 2023).\n\nThe analysis likewise seems to be a straightforward combination. In particular, the core convergence argument (Section D, also F) closely follows the standard NIGT analysis, and relies on the fact that Rennala/Malenia provide unbiased policy gradient estimates with bounded variance (∝ 1/M). While it is normal for new work to build on prior components, here it is unclear where the main technical challenge lies (if any). \n\n**Lower bound and Missing Comparisons.** The paper’s main theoretical focus is ε-stationary convergence and also provide a lower bound for this rate (which is assuming access to only stochastic gradient estimates and no other information). The setting for the lower bound feels very artificial especially since there is a substantial body of RL papers that obtain improved ε-stationary rates by exploiting RL-specific structure (see [A],[B],[C] and also Hessian aided PG in (Fatkhullin et al 2023)). It is very odd that these are not even mentioned, let alone discussed or compared against. \n\n\nFinally, although this is less critical, the paper should be better contextualized relative to existing federated PG work. Apart from (Lan et al. 2025), the empirical comparisons focus on non-federated PG methods, which are not the most natural baselines here. There are federated PG methods with ε-stationary guarantees in the synchronous homogeneous case [C], federated PG based on Hessian aided PG in the same regime [D], and heterogeneous PG methods using softmax policies [E]. Including (or at least discussing) such baselines would better position this work within the federated PG literature.\n\n\n\n---\n[A] Xu, Gao, Gu. Sample Efficient Policy Gradient Methods with Recursive Variance Reduction. ICLR 2020.\n\n[B] Xu, Gao, Gu. An Improved Convergence Analysis of Stochastic Variance–Reduced Policy Gradient. UAI 2020.\n\n[C] Fan, Ma, Dai, Jing, Tan. Fault–Tolerant Federated Reinforcement Learning with Theoretical Guarantee. NeurIPS 2021.\n\n[D] Ganesh, Chen, Thoppe, Aggarwal. Global Convergence Guarantees for Federated Policy Gradient Methods with Adversaries. TMLR 2024.\n\n[E] Labbi, Mangold, Tiapkin, Moulines. On Global Convergence Rates for Federated Policy Gradient under Heterogeneous Environment. arXiv 2025.", "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": "GteflYeFxm", "reviewer": "Reviewer_GmQ8", "summary": "This paper investigates distributed policy gradient (PG) methods in asynchronous and parallel reinforcement learning (RL) settings. The authors introduce two new algorithms for homogeneous environments and heterogeneous environments. Both algorithms are based on normalized policy gradient methods and asynchronous aggregation schemes inspired by recent work (e.g. Lan et al. 2025)", "questions": "Please see the Weakness section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* I briefly checked the proofs and they seem correct. This means the paper improves over the communication complexity of existing methods. \n\n* They also show a lower bound for the homogenous setting in the appendix which seems to show there is room for improvement.", "weaknesses": "* There is a lack of novelty in the algorithmic components, while one may argue this particular combination is done for the first time.\n\n* On the theoretical side, the proofs are highly reliant on/similar to existing results in federated RL and stochastic optimization. For instance, Lemma D.2 is a standard result (similar to SGDm with normalization and also a corresponding lemma from Lan et al. 2025). What is a new technical result proposed by the paper?\n\n* I also have a concern about the heterogenous experiments in the Appendix H.3. To test Malenia NIGT in a scenario with environment heterogeneity (different $J_i$), the paper uses $n=2$ agents, where one agent receives state $s$ and the other receives state $-s$. To distinguish these, the paper states, \"we concatenate the value 0 to $s_{t+1}$... In the case of the second worker, we redirect $(-s_{t+1}, 1)$\". In my view, however, this is not a heterogeneous problem. The algorithm is not learning an average policy $\\frac{1}{2}(J_1(\\theta) + J_2(\\theta))$. It is learning a single policy $J'(\\theta)$ for a single environment whose state space is $\\mathcal{S} \\times \\{0, 1\\}$. The policy network can trivially learn to behave differently based on the appended bit.", "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": "jf25HZVLpY", "reviewer": "Reviewer_KcX2", "summary": "This paper studies distributed reinforcement learning (RL) with asynchronous policy gradient methods. The authors propose two new algorithms: Rennala NIGT for homogeneous environments and Malenia NIGT for heterogeneous environments. Both methods extend normalized policy gradient techniques with asynchronous aggregation, achieving improved computational and communication complexity compared to prior work, e.g., AFedPG. The authors also establish a new lower bound and validate the methods on MuJoCo tasks, showing robustness to heterogeneity and communication delays.", "questions": "In Malenia NIGT, the mean-like dependency on agent speeds is less favorable than the harmonic dependency in Rennala NIGT. How does this affect performance in highly heterogeneous environments?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "**Originality.** Proposes new algorithms that generalize normalized gradient techniques to asynchronous distributed RL, with contributions in both homogeneous and heterogeneous settings.\n\n**Quality.** Strong theoretical analysis, including new upper bounds, support for AllReduce, and a new lower bound. Experimental results align with the theory.\n\n**Clarity.** The paper is well-structured, with clear algorithm pseudocode and comparisons.\n\n**Significance.** Distributed RL is critical for scaling up to large systems. The improved communication and computation guarantees, especially with AllReduce support, are practically valuable.", "weaknesses": "**Optimality gap** There remains a gap between the presented upper bounds (κε⁻²) and the lower bound (κε⁻¹²/⁷), leaving open whether the methods are near-optimal.", "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)