On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments
Authors: Muxing Wang
Pengkun Yang
Lili Su
Venue: Accepted by TMLR ()

Abstract: Large-scale multi-agent systems are often deployed across wide geographic areas, where agents interact with heterogeneous environments. There is an emerging interest in understanding the role of heterogeneity in the performance of the federated versions of classic reinforcement learning algorithms. In this paper, we study synchronous federated Q-learning, which aims to learn an optimal Q-function by having $K$ agents average their local Q-estimates per $E$ iterations. We provide a fine-grained characterization of the error evolution, which decays to zero as the number of iterations $T$ increases. When $K(E-1)$ is below a certain threshold, similar to the homogeneous environment settings, there is a linear speed-up concerning $K$. The slow convergence of having $E>1$ turns out to be fundamental rather than an artifact of our analysis. We prove that, for a wide range of stepsizes, the $\ell_{\infty}$ norm of the error cannot decay faster than $\Theta_R (\frac{E}{(1-\gamma)T})$, where $\Theta_R$ only hides numerical constants and the specific choice of reward values. In addition, our experiments demonstrate that the convergence exhibits an interesting two-phase phenomenon. For any given stepsize, there is a sharp phase transition of the convergence: the error decays rapidly in the beginning yet later bounces up and stabilizes.

Published in Transactions on Machine Learning Research (08/2025)
On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments
Leo (Muxing) Wang Northeastern University
wmng.muzinnhhorttesseem..ll
Pengkun Yang Tsinghua University
yanggenngkun@tttsingguuu....
Lili Su Northeastern University
Lan@@hortheasterm.edt
Reviewed on OpenReview: https: // optp//veew.....w....mo. net/ forum? id= EkLAG3gt3g
Abstract
Large-scale multi-agent systems are oflen deployed across wide geographic areas, where agents interact with heterogeneous environments. There is an emerging interest in understanding the role of heterogeneity in the performance of the federated versions of classic reinforcement learning algorithms. In this paper, we study synchronous federated Q-learning, which aims to learn an optimal Q-function by having K agents average their local Qmetes per E iterations. We provide characterization of the error evolution, which decays to zero as the number of iterations increases. We show that when K(E - 1) is below a certain threshold, similar to the homogeneous environment settings, there a linear speed-up concerning K. In sharp contrast, when K(E - 1) above the threshold, heterogencous environments lead to significant performance degradation. In particular, as E increases, the convergence rate deteriorates. The slow convergence of having E > 1 turns out to be fundamental rather than an artifact of our analysis. We prove that, for a wide range of stepsizes, the fx norm of the error cannot decay faster than θд (E/((1 -))),, where θд only hides numerical constants and the specific choice of reward values. In addition, our experiments demonstrate that the convergence exhibits an interesting two-phase phenomenon. For any given stepsize, there is a sharp phase transition of the convergence: the crror decays rapidly in the beginning yet later bounces up and stabilizes.
1 Introduction
Advancements in unmanned capabilities are rapidly transforming industries and national security by enabling fast-paced and versatile operations across domains such as advanced manufacturing (Park et al. 2019), autonomous driving (Kiran et al.] 2021), and battlefields (Möhlenhof et al., 2021). Reinforcement learning (RI.) cornerstone for unmanned capabilities an agent to learn an optimal policy via interacting with its operating environment to solve sequential docision- making problems (Bertsekas Tsitsiklis 1996; [Bertsekas] 2019). However, the ever-increasing complexity of the environment results in high- dimensionn state-action space, often imposing overwhelmingly high sample collection requirements on individual agents. This limited-data challenge becomes a significant hurdle that must be addressed to realize the patential of reinforcement learning.
a powerful machine learning method that aims enable
this paper, we study reinforcement learning within a federated learning framework (also known as Federated Reinforcement Learning (Qi et al. 2021 Jin al., 2022 Woo al.] (202))) ) wherein multiple agents independently collect samples and collaboratively train a common policy under the orchestration of parameter server without disclosing the local data trajectories. A simple illustration be found in Fig. T

---

Published in Transactions on Machine Learning Research (08/2025)
When the environments of all agents are homogeneous, it has been shown that the federated version of classic reinforcement learning algorithms can significantly alleviate the data collection burden on individual agents (Woo et al. 2023 Khodadadian et al. 2022) error bounds derived therein exhibit a linear speedup in terms of the number of agents. Moreover, by tuning the synchronization period E (i.c., the number of iterations between agent synchronization), the communication cost can be significantly reduced compared with E yet without significant performance degradation. However, many large-scale multi-agent systems are often deployed across wide geographic areas, result- ing in agents interacting with heterogeneous envi- ronments, For instance, connected and autonomous vehicles (CAVs) operating in various regions of a metropolitan area encounter diverse conditions such as varying traffic patterns, road infrastructure, and local regulations. Intuitively, the environmental het- erogeneity may lead to misaligned learning signals across agents, potentially hinder the convergence, and degrade the generalization performance of the learned policies. Hence, the clients' federation must. be managed in a way that ensures the learned policy is robust to environmental heterogeneity.
Autonomous car
Autonomous car
Autonomous
Traffic
Road
truck
lights
sensors
Figure 1:
An illustration of a federated learning system.
There is an emerging interest in mathematically understanding the role of heterogencity in the performance of the federated versions of classic reinforcement. learning algorithms (Jin et al., 2022 Woo et. al., 2023 Doan
ct al. 2019 Wang ct al., 2023 Xic & Song, 2023) such as Q-lcarning, policy gradient methods, and temporal difference (TD) methods. In this paper, we study synchronous federated Q-learning (FQL) in the presence of envirommental heterogeneity, which aims to learn an optimal Q-function by averaging local Q-estimates per E (where E 2 1) update iterations on their local data. We leave the exploration of asynchronous Q-lcarning for future work. Federated Q-learning is a natural integration of FedAvg and Q-learning (Jin et al.) 2022 Woo et. al., 2023). The former is the most widely adopted classic federated learning algorithm (Kairouz el al, 2021 McMahan et al., 2017], and the latter is one of the most fundamental model-free reinforcement learning algorithms (Watkins & Dayan 1992). Despite intensive study, the tight sample complexity of Q-learning in the single-agent setting was open until recently (Li el al. 2024 Similarly, the understanding of FedAvg is far from complete; a detailed discussion can be found in Section 2
A concise comparison of our work to the
related work can be found in Table
Contributions. Our contributions can be summarized as follows. All the asymptotic notations, e.g., and O, unless otherwise specified, hide only numerical constants.
We characterize the error cvolution of synchronous Federated Q-lcarning, showing that it decays to zero as the number of iterations T increases. When K(E- -)) 1) is below a threshold of Ô (1ke)-t(1-3)) -)) similar to the homogeneous environment settings, there a linear speed-up concerning and the sample complexity is δ IS||A
K(1 (((1)))02)) matching the homogenous setting (Woo et al. 2023). Here, S and A are the state and action spaces, E 10,1) denotes the discount factor, and K is a scalar characterizing the environment heterogeneity. In sharp contrast, when K K(F - 1) is above the threshold, heterogeneous environments lead to significant performance degradation and results in a unique sample complexity of (1-7)*<) Note that E is also e-dependent. Hence, the sample complexity ő [S][AA(KE)) does not (1-7)3²)
Ō [S] [SII.A)RE))
contradict the lower bound of ((E=2) for the single-agent case.
We prove that the convergence slowing down for F. 1 is fundamental. We show that the to norm of the error cannot decay faster than θR choice of reward values. A practical implication of this impossibility result is that, eventually, having multiple local updates (i.e., E > 1) ends up consuming more samples (i.e., Ex more) than using E to reach a target accuracy.
(1- where 2 only hides numerical constants and the specific
E
Our numerical results illustrate that when the environments are hetcrogencous and > 1, there exists a sharp phase-transition of the error convergence for not too small stepsizes: The error decays rapidly in the beginning yet later bounces up and stabilizes. In addition, provided that the chass-transition time
2

---

Published in Transactions on Machine Learning Research (08/2025)
can be estimated, choosing different stepsizes for the two phases can lead to faster overall convergence for both constant and time-decaying stepsizes. We conjecture that this is because the error in phase 1 is mainly controlled by the initial error with impacting factor decay exponentially in time, and the error in phase 2 is dominated by the collective perturbation caused by environment heterogencity and multiple local updates (i.e.; E 1).
2 Related Work
Federated Learning. Federated learning is a cetpuummiiaaiioeffffieette distributed machine learning approach that enables training global models without sharing raw local data (MeMahan al.
2017 Kairouz et al,,
2021]. Foderated learning has been adopted in commercial applications that involve diverse edge devices
such as autonomous vehicles (Du et al.] 2020 Chen et al. 2021: Zeng et al. 2022 Posner et al.
2021 Peng
et al. 2023), internet of things (Nguyen et al. 2019
Yu et al.) 2020 industrial automation (Liu et al.
2020 healthcare (Yan et al. 2021 Sheller et al. 2019 and natural language processing (Yang et al. 2018
Ramaswamy et al. 2019). , Multiple open-source frameworks and libraries are available such as FATE, Flower,
OpenMinded-PySyft, OpenFI., TensorFlow Foderated, and NVIDIA Clara.
FedAvg was proposed in the seminal work [McMahan et al. 2017], and has been one of the most widely implemented federated learning algorithms. It also has inspired many follow-up algorithms such as FedProx [Li et al. 2020b). FedNova (Wang et al.] 2020). SCAFFOLD (Karimireddy et al., 2020), and adaptive iederated methods (Deng et | 2020). Despite intensive efforts, the theoretical understanding of FedAvg is lar from complete. Most existing theoretical work on FedAAg overlooks the underlying data statistics at the agents, which often leads to misalignment of the pessimistic theoretical predictions and empirical success (Su ctt al.] 2023 Pathak & Wainwright/ 2020 Wang et al.) 2022a bj. This theory and practice gap was studiod in recent work (Su et al.) 2023 in the context of solving general non-parametric regression problems.
Reinforcement Learning. For the single-agent setup, there has been extensive research the convergence guarantecs of reinforeement learning algorithms. A recent surge of work studied non-asymptotic convergence and the corresponding sample complexity. [haadari et. al. (2018) analyzed non-asymptotic Temporal Difference (TD) learning with linear function approximation under a variety of noise conditions, including noiseless, independent noise, and Markovian noise. The results were extended to TD(A) and Q-learning. Li et al. (2020a) investigated the sample complexity of asynchronous Q-learning with different families of learning rates. They also provided an extension of using variance reduction methods inspired by the seminal SVRG algorithm. Li ct al. (2024) shows the sample complexity of Q-lcarning. Recall that A is the set of actions.
When |A| = 1, the sample complexity of synchronous Q-learning is sharp and minimax optimal; however, when [A| 2 2, it was shown that synchronous Q-learning has a lower bound which is not minimax optimal.
Multi-Agent RL. Yu et al. (2022) tested multi-agent Proximal Policy Optimization in four multi-agent lestbeds wherein agents fully share the parameters, and showed its competitive performance. Christianos lt al. (2021) proposed a selective parameter sharing technique, which automatically partitions agents so that they can benefit from the parameter sharing. Zhong et al. (2024) further proposed provably correct heterogeneouu--geet algorithms, which allow agents to have different policy functions. The algorithms showed superior effectiveness and stability in various challenging benchmarks.
Federated Reinforcement Learning. Woo et al. (0023) provided sample complexity guarantees for both synchronous and asynchronous distributed Q-learning, They revealed that, under the same transition probability (i.e., homogencous environment) for all agents, the convergence speed in learning the optimal Q- function can be accelerated linearly in the number of agents. They also uncovered the blessing of heterogeneity in terms of state-action exploration completely different notion of heterogeneity from focus. (Salgia & Chi (225) explored the frontier of sample and communication complexities under homogeneous environments. Via variance reduction and communication quantization, they designed an algorithm that achieves order- optimal sample and communication complexilies. Doan et al. (2019) investigated the distributed TD(0) with linear function approximation for a setting where multiple agents act in a shared environment and each agent has its own reward function. Khodadadian et al. (2022) studied on-policy federated TD learning, off- off-policy foderated TD learning, and federated Q-learning of homogeneous environments and reward with Markovian noises. The sample complexity derived exhibits linear speedup with respect to the number of agents.
3

---

Published in Transactions on Machine Learning Research (08/2025)
RL
Hetero- geneity
Lower bound
Finite- time
Work
Optimality
Sampling
Task
Algorithm TD(0)
Wang et al.
2023
x
X
v
Pred
Pred,
Xie & Song
2023
Policy Gradient
x
x
v
X
Plan
Pred,
Zhang et
2024
SARSA
X
X
V
V
Plan
Khodadadian et al.
TD,
Pred,
x
X
20222)
Q- Learning
Plan
Q- Q-Lernnng,
Pred,
Jin et al.
2022)
X
X
Policy Gradient
Plan
Pred,
Woo et al.
2023
Q- Q-Learning
X
X
V
Plan
Pred,
Zheng et al.
2023
Q-Learning
X
X
Plan
Pred,
Our work
Q-Learning
Plan
Table 1: Comparison of various works in the context of FRI. Pred and Plan stand for prediction (policy evaluation) and planning (policy optimization), respectively.
Heterogeneous environments were considered in Jin al. 2022 Wang al. 2023 Xie & Song (0023
Zhang et al. (2023). Jin et al. (2022) studied fedcrated Q-Icarning and policy gradient methods assuming known transition probabilities. To address heterogeneity in both euvironments and rewards, WWag et al.
(2023) proposed (o) with linear function approximation. They proved that, in a cow-beterogeneity regime, there is a linear convergence speedup in the number of agents. Xie Song (2023) used KI-divergence to penalize the deviation of local update from the global policy, and proved that the local update is beneficial for global convergence. [Zhang et al. (0024) proposed FedSARSA using the classic on-policy RT algorithm SARSA with linear function approximation. They theoretically proved that the algorithm can converge to a ncar-optimal solution. Neither Xic & Song
20233 nor Zhang et al. 2024) characterized sample complexity.
Technical comparisons with Woo et al. (2023) Zhang et al. (2024); Wang et al. (2023).
Zhang et al. (2024) and Wang et al. (2023) examined federated versions of TD learning and SARSA, whereas our paper studied foderated Q-lcarning, which offers distinct thcoretical and practical advantages for optimal policy learning. Specifically, the upper bound in Zhang et al. (2024) and Wang et al. (2023) do not indicate how fundamentally the convergence rates are impacted by the heterogeneity and synchronization period E. In addition, their upper bounds do not decay to 0 T co. Our upper bound converges to T oc. Furthermore, derived lower bound on the convergence rates, showing the fundamental limitation of multiple local updates (i.e., E. > 1) in the presence of environmental heterogeneity. To the best of our knowledge, this is the first result of its kind.
While our analysis of Theorem I builds upon the roadmap established by Woo et al. 2022)) adapting their analysis to our setting introduces significant challenges. In WWo et al. 22023), agents operate in homogeneous environments, i.c., each of the K agents shares the same transition distributions. This homogencity allows the concentration bound the difference between the true transition distribution and sampled estimates to become arbitrarily small as the number of samples increases. However, in our setting, each agent has its own environment with a distinct transition distribution. This heterogeneity introduces a perturbation term in the error upper bound that does not decrease with additional samples. Additionally, when E > 1 and > 0, the term involving x(F-1) in the upper bound becomes the dominant term, resulting in a unique sample complexity. Further technical details and implications of these adjustments are provided in Corollary
3 Preliminary on Q-Learning
Markov decision process. Markov decision process (MDP) is defined by the tuple (S,A,P,y, R), where S represents the set of states, represents the set of actions, the transition probability P 5 -> [0. 1] provides the probability distribution over the next states given a current state s and action a, the reward function R. x A [0, assigns reward value to each state-action pair, and the discount factor (0, models
4

---

Published in Transactions on Machine Learning Research (08/2025)
the preference for immediate rewards over future rewards. It is worth noting that P (P(- a) IeS is collection of |S| |A] probability distributions over S, one for each state-action pair (s. (s.
Policy, value function, Q-function, and optimality. A policy specifies the action-selection strategy and is defined by the mapping я : + (A), where T(a s) denotes the probability of choosing action a when in state 8. For a given policy n, the value function V : - measures the expected total discounted reward starting from state s:
V (*(8)= =
Σ 7f R(si, 80 _):
Vs E.
The Q-function (a.k.a. state-action value function). Q :8 A R, evaluates the expected total discounted reward from taking action in state and then following policy
(s) = ((ss,a + Eaeaa( (
Σ ' R(s) ar) 8u = s, ag = v(s,a) ESx
An optimal policy x² is one that maximizes the value function for every state, that is Vs E S, V VV for any other æ x* Such a policy ensures the highest possible cumulative reward. The optimal value function V (shorthand for V**) and the optimal Q-function Q" (shorthand for QT") are defined under the optimal policy =².
The Bellman optimality equation for the value function and state-value function are:
(*())= max[R(ss a) +
Σ
P(s' s as))
s'ES
(* R(s,a) + + Σ
P(s'ls, a) (s,, a'E
max
e'ES
Q-learning. Q-learning (Watkins & Dayan
1992 is model-free reinforcement learning algorithm that aims to learn the value of actions of all states by updating Q-values through iterative exploration of the environment, ultimately converging to the optimal state-action function. Based on the Bellman optimality equation for the state-action function, the update rule for Q-Learning is formulated as:
Qu+1(s,)) a) (1 x)Qr(s,a) + A[R(s, a) +y Qu(s(,a'), ((s,a)e8xx
where 5' P(: 8, 8, and À is the stepsize.
4 Federated Q-learning
The federated learning system consists of one parameter server (PS) and K agents. The K agents are deployed in possibly heterogeneous yet independent environments. The K agents modeled MDPs with M& A, Ph y, R) for k 1.... K, where pk {P* s. ses is the collection of probability distributions. In the syuchronous setting, each agent k has access to a generative model. At each iteration 4, it generates a new state sample (s) ~ p* a) for each (s,a), i..., P (s = s'} = p*(s' s, a) for all s' S, independently across statc-action pairs (s) For each (s, a), the global environment P(. s,
JJn et al. 2022 is defined as
1 K
P(s' s,a) =
Σ
(s' s,a),
(1)
K
k=1
with the corresponding global MDP defined as Mg = (S, R). Define transition heterogeneily as
sup P(. 8, p*(
(s,,))l = =
(2)
k,s,a
5

---

Published in Transactions on Machine Learning Research (08/2025)
Let Q" denote the optimal Q-function of the global MDP. By the Bellman optimality equation, we have,
(* a( +
Σ P(s (s)) v(s,a)
(3)
s'es
where (8()) A (*, a) is the optimal value function.
The goal of federated Q-learning is to have the K agents collaboratively learn Q'. We consider syn- chronous federated Q-learning, which a natural integration of FedAvg and Q-learning (Woo al. 2023; Jin al.) ) described in Algorithm [ Every agent initializes its local Q* estimate Qo and performs standard synchronous Q-learning based on the locally collected samples sy (s, a). Whenever ++ mod E = O, through the parameter server, the K agents average their local estimate of Q; that is, all agents report their 0 the parameter server, which computes the average and sends back to agents.
Algorithm 1 Synchronous Federated Q-Learning
Inputs: discount factor 7, E, total iteration T, slepsize X, initial estimate Qo
1: for E [K] do
2:
Q Qo
3: end for
for 1= 0 to T do
5:
for k E [K] and (s, S do
6:
litg (8, = (1 - ()Q)(s,a) +
A (R(s, +0000)+mmxpppmp max Q ())(
7:
if (t+1) mod E = 0 then
8:
Q k
Σ -k=1 Q
9:
else
5 Main Results
10:
0 02+ end if
With a little abuse of notation, let the matrix pk E [|SI|AIi|S|| represent the transition kernel of the MDP of agent & with the (s, a)-th row being s,, R the transition probability of the state-action pair as, For ease of exposition, write (= s,a) pK(s, a) the state transition probability at the state-action pair (s, a) when its meaning is clear from the context.
12: end for
13:
end for
14: return QT = R
1 Σ o+
5.1 Main Convergence Results.
Let P E {0, 11SIAA411 denote the local empirical transition matrix at the t-th iteration, defined as
(1 a) 1(s'= = =s
= Denoting PkV' E RISSIA x1 with the (s, a)-th entry as = () Let Q =
Σk Qu From lines 6, 8, and 10 of Algorithm 1 it follows that
1 E (1- -)-x A(R ((R+7P(V+))
Qe+
(4)
K
where (s) A (s) for all S. Define
A == Q" - Q.+1. and - Qo-
(5)
The error iteration A, is captured in the following lemma. Lemma 1 (Error ileration).
For any 2 0,
A (1 1)++1 Do +
2)--1 Σ PPPPP
1 K
+ ?ソ Σ
(1 x) 2)
1-
(V - V.t).
(6)
K
1=0
k=l

---

Published in Transactions on Machine Learning Research (08/2025)
To show the convergence of || we bound each of the three terms in the side of (6) The following lemma is a coarse error upper bound.
Lemma 2. Choosing R(s,a) a) E [0, 1] for each state-action pair (s, a), and choose 0 S Q0(8, S T-7 for any (s,a) E S A, then S Q+ i T (8 a) S T
1
|1Q- - 10 - I- and || Vi S 1- -
1
A 2 0, and & E [K].
With the choice of Qo in Lemma 2 the first term in 6 can be bounded as (1 A) Do (1-A) T-yy In addition, as detailed in the proof of Lemma 4 and Theorem 1 the boundedness in Lemma 2 enables us to bound the second term in (6) via invoking the Hoeffding's inequality. Tt remains to bound the third term in G6. for which we follow the analysis roadmap Woo et al. (0023 by two-step procedure that is described in Lemna 3 and Lemma Let
A =' -Q- Qr and x(t) =t (t mod E),
(8)
i.e., A is the local error of agent k; and x(1) is the most recent synchronization iteration of L.
Lemma 3. I mod E = 0, then
Σx= PV vo) - | Otherwise,
K Σ k=1
(V V/a)
S $11400l 22
|
x(t)
72 1
Σ
(P)(s,a p((,)))()))))
max 6,0
K
#' --x(()
where we use the convention that Σ [x(()-1 =(())
| 1. = 0.
Lemma Choose E. For any 8 E (0, 1), with probability at least (1 8),
37 X(E 1)x +
37
S SKK
| 00 < Axcill
Alog
V TiST,KkEl [K).
1
To bound the foe norm of the third term 6 we first invoke Lemma 3 followed by Lemma Tt is worth noting that directly applying Lemma can also lead to a valid error bound yet the resulting bound will not decay as T increases with proper choice of stepsizes.
Both Lemma. 3 and Lemma 4 are non-trivial adaptations of the approach in Woo et al. 2023 due to the absence of a common optimal action for any given state in heterogencous cnvironments. Morcover, in the homogeneous setting, each agent draws samples from the same true Iransition distribution, allowing concentration inequalities to bound the discrepancy between the true distribution and sampled estimates. However, this line of reasoning docs not go through the presence of environmental heterogeneity. When K > 0, each of the K agents has its own transition distribution, and the discrepancy captured by the environmental heterogeneity parameter
Theorem 1 (Convergence). Choose F - 1 S 1 min 47 } and X b. For any ō (0, }), with probability
at least 1 38, it holds that
14y² (1 - 7)2
16
X
S|
Ao S (1 71
exp { (11
X(E - 1)x
log
(1 - 22
K
The first term of Theorem [ is the standard error bound in the absence of environmental heterogeneity and sampling noises. The second term arises from environmental heterogeneity. is clear that when = 1, the environmental heterogeneity does not negatively impact the convergence. The last term results from the randomness in sampling.
7

---

Published in Transactions on Machine Learning Research (08/2025)
Remark 1 (Eventual zero error). It is common to choose the stepsize À based on the time horizon T. Let X = [T) be a non-increasing function of T, and other parameters be fixed with respect to T. As long À == >T) decay in T' terms 2 and 3 in Theorem [ will go to 0 as T increases. In addition, when A = w(1/T), the first term will decay to O. Conversely, the convergence bounds in Zhang et al. (2024) and Wang et al.
2023 do not decay to 0.
There is tradeoff in the convergence rates of the first term and the remaining terms the slower À decay in T leads to faster decay in the first term but slower in the remaining terms. Forcing these terms to decay around the same speed leads to slow overall convergence. Corollary follows immediately from Theorem via carefully choosing À balance the decay rates of different terms.
1
Corollary 1. Choose (E- 1) S min +1 1 h and X (TK) probability at least 36,
Let T E. For any (0, with 7(1-))
32
log(TK)
SIATK
56 16log (TK) E 8-1
|1 S (1 2TKK (1 (1-7)2.5
log 5
VTK
(1-7)3 T
Remark 2. Intuitively, both terms 1 and 2 decay as if there are TK itcrations. In fact, the decay rate of the sampling noises in Corollary | with respect to TK, is the minimax optimal up to polylog factors (Vershynin 2018). The decay of the third term is controlled by environmental heterogeneity when > In sharp contrast to the homogeneous settings, larger E significantly slows down the convergence of this term. We show in the next subsection that this slow convergence is fundamental.
Remark 3 (Communication cost and convergence). From Corollary 1 by choosing E = =((TT) and other parameters are fixed with respect to T, we can reach the same error bound of ((L/VT) with communcation cost of O ((T)), which is better than Ö(T).
SIAAK log (1))))
Corollary 2. Choose E - 1 x min 1-1 } and X I 1. E and define xn 4096 log
K(1
<(1-))- 31-""""
,22
168x(E-11)) 1)y2 log2( (1-2)*+), ) and x3 1(--7)= log | log" (1-2) (1-7)a
9216
When == or E 1, for any d E (0, })) with probability at least 1 -3,, holds that
A se
when 2 (1))), and X
2304 PIANT, where W-1 is the Lambert W function. The
2(1-))*K
|S|LA resulting sample complerity is Ö (
When and E >>> 1,
log ISILAIK
for any 8 E (0, with probability at least 1 - 35, it holds that (
A Se.
when T2 exp( WW and X 42x(E-1)マ² The sample complecity is δ (MSSILALE)
<(1-))²
(1-7)-
log |SILAIK
K(E -
x for any 8 E (0, } with probability at least 1 - 36, it holds that
| Se.
'K when T2 exp(-W-ii Boo(-WWiit -W-1--1 1) and X 2304 log B The sample complexity is δ |S||A|
[(1-))>2))
Remark 4 (Sample complexity on K and E and conditional linear speedup.). From Corollary we can conclude that when the setting is homogeneous (i.e., к = 0) or the agents communicate every step (i.e., E 1), the sample complexity δ |SILA matches the one in Woo al. (2023). On the other hand, when the setting is heterogeneous (i.e., 0) and F. 1, is evident that il the total computation steps
R(I--)
8

---

Published in Transactions on Machine Learning Research (08/2025)
per synchronization are sufficiently small, i.e., K(E 1) S (( - ?), the sample complexity also matches the one in the homogeneous setting, where there is a linear speedup. Otherwise, the sample
A increases with E, meaning that multiple local rounds only consume more samples complexity Ö (1-7)
(i.c., E-times more) samples without achieving linear speedup.
5.2 On the Fundamentals of Convergence Slowdown for E > in Heterogeneous Environments.
Theorem 2. Let Qo = 0. For any even K 2 2, there crists collection of A(S,A, Pk R,y) k E [K]] where
[r1
-|= = 2, |A| = 1, and :
fized for all MDPs in the collection, such that, for E 2 2 and time-invariant r2
stepsize S
E
| 2 CR
7)T"
when T/E E N and T 2 E-max expl (1+7) exp -W-1 (22++))
4F(y42)
}}
where W-1 is the Lambert W
function, CR = 2 min Intrrll |r ral) when ri # r2 and CR = Instral
otherwise.
2e
Proof Sketch. Below provide the proof sketch of Theorem The full proof is deferred Appendix
The eventual slow rate convergence is due to the heterogeneous environments P regardless of the cardinality of the action space. In particular, we prove the slow rate when the action space is singleton, in which case the Q-function coincides with the V-function. The process is also known as the Markov reward process. According to Algorithm 1 when (t (t+1) 1) mod E + O, we have
Φi+1 = -0-=(11 ((1 ^)T + Xy O + AR.
Following Algorithm 1 let = denote the z-th synchronization round, and obtain the following recursion between two synchronization rounds:
((+1)E A A.E (1I (I + A +...A(E-1)) (1 (1-
(10)
where A A 1 (A and A @ (1- + While the first term the right-hand side of 10
decays rapidly to zero, the second term is non-vanishing due to environment heterogeneity for E 2. Specifically, to ensure the rapid decay of the first term, it is necessary to select stepsize A = ((2)) However, this choice results in the dominating residual error from the second term, which increases linearly with XE = (1122)
Next, we instantiate the analyses by constructing the set. pk over two states and an even number of clients with
[ 0 p2k
O for k E N.
p2k-1
(11)
1
1
Applying the formula of A yields the following sigen-decompositionn
( ar P) BrP,
where P- = $11,, as - H04 + v6), 3e - vg. 1 2 (1 + 7)4, and V2 2 1 (1 7)x. For this
instance of Px. the error evolution (10) reduces to A(2+1E = (a P A + +kglI - P)Q" with
RE A 1-1 ) which further yields the following full error recursion:
A = (a + + 1 1-0
Kg (I PIQ'
ag
Starting from Qo = 0, the error can be decomposed into
A = PQ +
o +
1 a Ki
P1-1)Q-
P)Q'
(12)
9

---

Published in Transactions on Machine Learning Research (08/2025)
The two terms of the error are orthogonal and both non-vanishing. Therefore, it remains to lower bound the maximum magnitude of two coefficients irrespective of the stepsize X.
To this end, analyze two regimes of X separated by a threshold Ào
log(T/E), (1-1)T*
Slow rate due to small stepsize when X S Ao- Since 3E decreases as À increases,
f 2 (1 (1 >)>o)= log =E
2 eT
F
Slow rate due to environment heterogeneity when À 2 Aa
We show that
1- a
E
z + 1 KE
(1-
We conclude that at least one component of the error in Remark 5. The explicit calculations are based on a set p over a pair of states. Nevertheless, the evolution (10 is generally applicable. Similar analyses can be extended to scenarios involving more than two states, provided that the sequence of matrices A()) is simultancously diagonalizable. For instance, the construction of the transition kernels in (11 can be readily extended to multiple states if the set 8 can be partitioned into two different classes. The key insight is the non-vanishing residual on the right-hand side of (10) when E 2 2 due to the environment heterogeneity.
12 must be slower than the rate ((E/TT)
5.3 Discussion on Time-varying Stepsize
Although using time-varying stepsize is common and simple when implementing the algorithm, it is not easy to transfer from current time-invariant stepsize analysis to time-varying stepsize analysis. This is because in the time-invariant stepsize analysis we are dealing with function of one variable, however, in the time-varying case, we are dealing with a function of T variables.
For example, in our lower bound analysis, we picked a threshold Ao and showed that no matter greater or smaller than λo the convergence rate is greater than OR 10//((111)70)) and we can claim we have coverod all the cases. However, for time-varying stepsize, the number of stepsizes is T, and it is not easy to generalize similar result by just considering several cases because each stepsize gives additional dimension. Even if we know the sequence is decaying, without specifying a particular family of stepsizes, it is not possible to divide it into several cases as we did for time-invariant stepsize.
We conjecture that both approaches lead to comparable residual error levels over extended training. For example, the stepsizes used in Figure 4a and Figure 4b are J and V respectively. While the time- decaying stepsize appears to have faster initial convergence due to its larger values, we observe that as increases, the convergence rates of the two strategics seem to align, suggesting a similar asymptotic behavior.
6 Experiments
Description of the setup. In our experiments, we consider K = 20 agents (Jin et al. 2022), each interacting with an independently and randomly generated 5 x 5 maze environment (S,A, Pk R, 7) for & E 21, ... 203. The state set S contains 25 cells that the agent is currently in. The action set contains actions A = (left, up, right, down). Thus, [S] x |A| = 100. We choose y = 0.99. For ease verifying our theory, each entry of the reward E R100 is sampled from Bern(p 0.05), which slightly departs from typical maze environment wherein only two state-action pairs have nonzero rewards. We choose this reward so that | 100 rー which is the coarse upper bound of || for all For each agent k, its state transition probability vectors p are constructed on top of standard state transition probability vectors maze environments incorporated with a drifting probability 0.1 in each non-intentional action as in WindyCliff (Jin et al. 2022 Paul al. 2019). In this way, the environment heterogeneity lies not only in the differences of the non-zero probability values (Jin al. 2022: Paul et al., 2019) but also in the probability supports (i.e., the locations of non-zero entries). Our construction is more challenging: The
10

---

Published in Transactions on Machine Learning Research (08/2025)
environment heterogencity as per (2) of our environment construction was calculated to be 1.2. Yet, the largest environment heterogeneity of the WindyCliff construction in Jin et al. (2022) is about 0.31.
We choose Qo 0 E IR All numerical results are based on 5 independent runs to capture the variability, The dark lines represent the mean of the runs, while the shaded areas around each line illustrate the range obtained by adding and subtracting one standard deviation from the mean. The maximum time duration is T 20, 000 in our experiment since it is sufficient capture the characteristics of the training process.
Convergence behavior and two-phase phenomenon. We demonstrate through numerical simulations that our analysis aligns with the observed behaviors. For algorithms with time-invariant stepsize, convergence requires sufficiently small stepsizes and sufficiently large number of iterations T.
To explore the impact of stepsizes on convergence, we use À E {0.9, 0.5, 0.2, 0.1, 0.05), spanning a range within (o, 1). As shown in Figure 2a] these stepsizes are not sufficiently small, leading to a two-phase phenomenon: the -nom of A, = Q" Qu has a rapid decay the first phase followed by a bounce back in the second phase. This phenomenon is distinctive to heterogeneous settings. Tn contrast, Figure 2b indicates that in homogencous environments, no drastic bounce occurs, irrospective of the stepsize. Note that if multiple plots the same page share the same legend, we display the legend only once for clarity.
1 Figure 4a (light blue curve) demonstrates that with a sufficiently small stepsize, such as X = VT the error continuously decreases, reaching approximately 24 by iteration 20,000.
A useful practice implication of our results is that: While constant stepsizes are often used in reinforcement learning problems because of the great performance in applications as described in Sutton & Barto (0118) they suffer significant performance degradation in the presence of environmental heterogeneity.
stepsize 0.05
constant stopsize - 0.1
constart, stepsize 0.2
80-
80
stepsize
constant stepsize
60
60
20-
20
2500
1000
7500
10000 Time
12500
15000 17500
20000
2500
5000
7500
10000 Time
12500
15000
17500
20000
(a) Heterogeneous environments E 10.
(b) Homogeneous environments E 10.
Figure 2: The too error of different constant stepsizes under the heterogeneous and homogenous settings.
Impacts of the synchronization period E. In homogeneous settings (refer to Figure 5 in Appendix G.I. the synchronization period E has negligible impact, consistent with prior findings in the literature [Woo et al. 2023 Khodadadian et al.] 2022). However, under heterogeneous conditions, larger E' values lead to increased final error across the five constant stepsizes, as depicted in Figure 3 and Figure 2a This = degradation persists even with time-decaying stepsizes X, = v as shown Figure 6 We hypothesize that
larger E values require either smaller or more rapidly decaying stepsizes to mitigate The degradation caused by increased synchronization periods.
Potential utilization of the two-phase phenomenon. As shown Figures 2a and 3 in the presence of environmental heterogeneity, the smaller the stepsizes, the smaller error || can reach and less significant of the error bouncing in the second phase. In our preliminary experiments, we tested small stepsizes À 1/Ta
11

---

Published in Transactions on Machine Learning Research (08/2025)
for 00.,,0.5..-. ... .1), which eventually lead to small errors yet at the cost of being extremely slow. Among these choices, X = 1/vT has the fastest convergence performance yet is still R 24 up to iteration 20,000.
100
100
60
60
40
40
15000 11500
Time
(a) E=1
(b) E-20
100
80-
80-
1-1-
60-
40
20-
20-
2500
5000
7500
10000 Time
12500 15000 17500
20000
2500
5000
7500
10000 Time
125c0
15000
17500
20000
(c) E=40
(d) E=00
Figure 3: Convergence behavior for constant stepsizes (0.05, 0.1, 0.2, 0.5, 0.5, under various synchronization
intervals E' (1,20, 40, oo). In heterogeneous settings, higher E and larger À lead to higher residual errors.
Let to be the iteration at which the error trajectory || llao switchos from phase to phase 2. Provided that lo can be estimated, choosing different stepsizes for the two phases can lead faster overall convergence, compared with using the same stepsize throughout.
Figure 4a illustrates two-phase training with different phase 1 stepsizes and phase 2 stepsize À 1/VT compared with using À = 1/vT throughout. Overall, using = 1/VT throughout leads to the slowest. convergence, highlighting the benefits of the two-phase training strategy. Among all two-phase stepsize choices, the stepsize of 0.05 in the first phase results in longer phase duration (to 5550) but the lowest final error (2.75327), suggesting a better convergence. We further test the convergence performance with respect different target error levels, details can be found in Appendix G.3
We also evaluated the two-phase training strategy using various time-decaying step sizes, including VIFT e+1 Mee F and (e+)),. In all cases, Figure 4 shows the two-phase training has advantage.
We leave the estimation and characterization of to for future work.
12

---

Published in Transactions on Machine Learning Research (08/2025)
Acknowledgments
We thank He Cheng for his valuable assistance on the experiments. P. Yang is supported in part by the National Key R&D Program of China 2024YFA1015800, and Tsinghua University Dushi Program 2025211DSZ001. L. Su is supported in part by NSF CAREER CIF- -344224
References
Dimitri Bertsekas. Reinforcement learning and optimal control, volume 1. Athena Scientific, 2019.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamii programmingg Athena Scientific, 1996.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Jin-Hua Chen, Min-Rong Chen, Guo- Guo-Qiang Zeng, and Jia-Si Weng. Bdft: a byzamtine-fault-tolraaa decen- tralized federated learning method for autonomous vehicle. IEEE Transactions on Vehiculor Technology, (0(9))8639-86522 2021.
Filippos Christianos, Georgios Papoudakis, Muhammad A Rahman, and Stefano V Albrecht. Scaling multi- agent reinforcement learning with selective parameter sharing. In International Conference on Machine Learning, pp. 1989-1998. PMLR, 2021.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint 2Xix:2003.1341,, 2020.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed td (0) with linear function approxination on multi-agent reinforcement learning. In International Conference on Machine Learning, pp.
PMLR, 2019.
Zhaoyang Du, Celimuuee Wu, Tsutomu Yoshinaga, Kok-Lim Alvin Yau, Yusheng Ji, and Jie Li. Federated learning for vchicular internet of things: Recent advances and open issucs. IEEE Open Journal of the Compuler Sociely, 1:45 61, 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, pp. 18-37. PMLR, 2022.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummingss Rafael L. D' D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie Hc, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song. Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Pranceth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1 2):1 210, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Inter- national Conference on Machine Learning, pp. 5132-5143. PMLR, 2020.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference on Machine Learning, pp. 11097-11057. PMLR, 2022.
13

---

Published in Transactions on Machine Learning Research (08/2025)
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: A survey. IEEE Transactions on Intelligent Trunsportation Systems, 23(6):4909 4926, 2021.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. Advances in neural information processing syslems, 14:7031-7044 2020a.
Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejic Chi. Is q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 72(1):222 236, 2024.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia. Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-455 2020b.
Yang Liu, Anbu Huang, Yun Luo, He Huang, Youzhi Liu, Yuanyuan Chen, Lican Feng, Tianjian Chen, Han Yu, and Qiang Yang. Fedvision: An online visual object detection platform powered by federated learning. Tn Proceedings of the AAAT Conference on Artificial Intelligence, volume 34, pp- 13172-1311 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. PMLR, 2017.
Thies Möhlenhof, Norman Jansen, and Wiam Rachid. Reinforcement learning environment. for tactical networks. In 2021 International Conference on Military Communication and Information Systems (ICMCIS), pp. 1 8. IEEE, 2021.
Thien Due Nguyen, Samuel Marchal, Markus Mieltinen, Hossein Fereidooni, N Asokan, and Ahmad-Rens Sadeghi. Diot: federated self-learning anomaly detection system for iot. In 2019 IEEE 39th International conference on distributed computing systems (ICDCS), pp. 756 767. IEEE, 2019.
In-Beom Park, Jaeseok Huh, Joougkyun Kim, and Jonghun Park. A reinforcement learning approach robust scheduling of semiconductor manufacturing facilities. IEEE Transactions on Automation Science and Engineering, 17(3):1420 1431, 2019.
Reese Pathak and Martin J Wainwright. Fedsplit: An algorithmic framework for fast federated optimization. Advances in neurol information processing systems, 33:7057-7066, 2020.
Supratík Paul, Michael A Osborne, and Shimon Whiteson. Fingerprint policy optimisation for robust reinforcement learning. In International Conference on Machine Learning, pp. 5082 5091. PMLR, 2019.
Muzi Peng, Jiangwei Wang, Dongjin Song, Fei Miao, and Lili Su. Privacy-preserving and umcoraainty-wware federated trajectory prediction for connected autonomous vehicles. In 2023 TEFE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2023.10341638.
2023. doi: 10.1109/1RO055550
Jason Posner, Lewis Tseng, Moayad Aloqaily, and Yaser Jararweh. Federated learning in vehicular norks Opportunities and solutions. IEEE Network, 35(2):152-1155 2021.
Jiaju Qi, Qihao Zhou, Loi Lei, and Kan Zheng. Foderated reinforcement learning: techniques, applications, and open challenges. Intelligence & Robotics, 2021. doi: 10.20517/1r:2021. URL httpp:://oii.rgg// 20517/2Fir. 2tt.:/222.1.222..222
Swaroop Ramaswamy, Rajiv Mathews, Kanishka Rao, and Françoise Beaufays. Federated learning for emoji prediction in mobile keyboard. ar preprint arXiv:1906. 04329, 2019.
Sudeep Salgia and Yuejie Chi. The somple-commniiation complexity trade-off in federated qlearning. Advances in Newral Information Processing Systems, 37:39694-39747, 2025.
14

---

Published in Transactions on Machine Learning Research (08/2025)
Micah J Sheller, G Anthony Reina, Brandon Edwards, Jason Martin, and Spyridon Bakas. Multi-institutional deep learning modeling without sharing patient data: A feasibility study on brain tumor segmentation. In Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries: 4th International Workshop, BrainLes 2018, Held in Conjunction with MICCAI 2018, Granada, Spain, September 16, 2018, Revised Selected Papers, Part I 4, pp. 92 104. Springer, 2019.
Lili Su, Jiaming Xu, and Pengkun Yang. A non-parametric view of ledavg and fedprox: Beyond stationary points. Journal of Machine Learning Research, 24(203):1 48, 2023.
Richard S. Sutton and Andrew G. Barto. Chapter 2.5 Tracking a Nonstationary Problem, Reinforcement Learning: An Introduction, chapter 8, pp. 33. The MIT Press, 2018
Roman Vershynin. High-dimensional probability; An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Chunnan Wang, Xiang Chen, Junzhe Wang, and Hongzhi Wang. Atpfl: Automatic trajectory prediction model design under federated learning framework. In Proceedings of the IEEE/CV /CV Conference on Compuler Vision and Pattern Recognition (CVPR), pp. 6563-6572, 6572, June 2022a.
Han Wang, Aritra Mitra, Hamed Hassani, George J Pappas, and James Anderson. Federated temporal difference learning with lincar function approximation under environmental heterogeneity. arXiv preprint Nii:2302.02212, 2023.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33: 7611-7623, 2020.
Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data. arxiv preprint Xrxiv:2006004 0272, 2022b.
Christopher Watkins and Peter Dayan. Q-learning. Machine Learning, 8:279 8:279-292, 1992. URL https:
seapi.semanticccholaar wtw.a//cccccaaaaooroorroorpsaeee 208910339
Jiin Woo, Gauri Joshi, and Yuejie Chi. The blessing of heterogeneity in federated q-learning: Linear speedup and beyond. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (ods.). Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 37157-37216. PMLR, 23-29 Jul 2023. URL https://proceeedingg mlr. ppress/v20/// wow2a....aa.....ooooooooo html
Zhijie Xie and Shenghui Song. FedKL: Tackling Data Heterogeneity in Federated Reinforce- IEEE Journal on Selected Areas in Commu-
ment Learning by Penalizing KL Divergence.
nications, 41(4):1227 April 2023. ISSN 1558-0008. doi: 10.1109//5AC.22223322200
URL
leee. http:///ew.e.eeeeeee///////////a
FsAAAAA
Bingjie Yan, Jun Wang, Jieren Cheng, Yize Zhou, Yixian Zhang, Yifan Yang, Li Liu, Haojiang Zhao, Chunjuan Wang, and Boyi Liu. Experiments of federated learning for covid-19 chest x-ray images. In Advances in Artificial Intelligence and Security: 7th International Conference, ICATS IS 2021, Dublin, Treland, July 19-23, 2021, Proceedings, Part II 7, pp. 41-53. Springer, 2021.
Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXio preprint arXi::1812.022 02200, 2018
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in neural information processing systems, 15:24611-24622 2022.
15

---

Published in Transactions on Machine Learning Research (08/2025)
Tianlong Yu, Tian Li, Yuqiong Sun, Susanta Nanda, Virginia Smith, Vyas Sekar, and Srinivasan Seshan. Learning context-aware policies from multiple smart homes via federated multi-task learning. In 2020 IEEE/ACM Fifth International Conference on onternet-of-Things Design and Implementation (loTDI), pp- 104-115. IEEE, 2020.
Tengchan Zeng, Omid Semiari, Mingzhe Chen, Walid Saad, and Mehdi Bennis. Federated learning the road autonomous contrr design for connected and autonomous vehicles. IEEE Trmnsactions Wireless Communications, 21(12):00407-100 10423,, 2022.
Chenyu Zhang, Han Wang, Aritra Mitra, and James Anderson. Finite-time analysis of on-poliey heterogeneous federated reinforcement learning. arXiv preprint arX1::2/01.1527, 2024.
Shangtong Zhang, Remi Tachet Des Combes, and Romain Laroche. On the convergence of sarsa with linear function approximation. In International Conference on Machine Learning, pp. 41613-41646. PMLR, 2023.
Zhong Zheng, Fengyu Gao, Lingzhou Xue, and Jing Yang. Federated q-learning: Linear regret speedup with low communication cost. arXiv preprint XrX:v:2312. 1....1500 15023, 2023.
Yifan Zhong, Jakub Grudzien Kuba,, Xidong Feng, Siyi Hu, Jiaming Ji, and Yaodong Yang. Hetcrogencous- agent reinforcement learning. Journal of Machine Learning Research, 25(32):1 67, 2024. URL http: 7/jmrr 2tggpapprs/v25/23-0000 0488.00008000 html
16

---

Published in Transactions on Machine Learning Research (08/2025)
Appendices
A Proof of Lemma 1
The evolution of A++1 be decomposed as follows:
A+11
Q" Qu+1
K
(a) 1
Σ (Q" ((1 1JQ5 + +X(+ + 7PA
K
k=1
K
Σ ((1 1)(Q² - -2) + MQ0 - R - -P(P/)
K
k=1
1 K Σ -PV,1
= (1 A)A + 7t K
(P- (P-PLyV' + 7t K
Σ
pk (V - V
K
K
k=l
K
= (1 A) Ao +
(1
A)
P (P-Pk) PK:
K
1=0
k=1
K
Σ
2)--
1
P+ V,+).
K
where equality (a) follows from Eq. 4 equality (b) follows from the Bellman optimality equation in Eq. (3 and the last equality follows from unrolling the updates & 4+1 times and using the fact that Ao = QQ" Q0-
B Proof of Lemma 2
We first show 5 (s, و by inducting on When = 0, this true by the choice of Qu- Suppose that 0 (i-1(s,)) S - for any state-action pair (s,a) and any client k. Let's focus time t. When t is not synchronization iteration (i.c., ++1 1 mod E + 0), we have
(s. = (1 - 2) A + (s,
< + +A(B(s, (
(a)
+ A(1 +
1-7
1-9
A
+ X
1 1-7 1-7
1-
1 where incquality (a) holds because for any 8, V/i = max.e4 (s, S 1-y by the inductive hypothesis, and each element of Pits a) E [0, 1]. Then as, < (s. a)ll || S 1- by Hölder's incquality. Similarly, we can show the case when / is a synchronization ileration.
With the above argument, we can also show that < (s, - + for any state-action pair (s, a). Therefore, have that || -t -
17

---

Published in Transactions on Machine Learning Research (08/2025)
Next, show that bound on ||V 1/
1
max V (s) (s)
SES
max
max Q' (s.
max (((,)a)
#ES
aEA
d'EA
(*) (s,a))
max aEA,
= 11Qe - Qf 11o00
1
x
1-7
C Proof of Lemma 3
When t mod E = 0, i.c., i is synchronization round, Q = Q8 for any pair of agents k. k E [K]. Hence,
1 K
K Σ (s) - -V,)
Pt (0, a)
(V- Vi)
K
k=1
K
Pf (s, a)ll -
K
V
Villo0
s Q|' @111o
a0
(13)
For general 1, we anchor the error term to that of the synchronization round as follows:
K
K
P Vily
P+(V
x(1) + VV
V.lg)
K
K
x(1)
k=1
Pt
V vito
Ps (x(0 - v,t)
+ K
k=1
(a)
1
K
Pk (v x(() Vile)
+
K
K
A x
1
yk
(14)
xit)
where inequality (a) follows from Eq. 13 For any state E S, let at (s) E arg max Qt (s, a) for all t and
k. We have
(²(()) (s)
- (t((s, ((())
-((s, Qi at (s)) + (2, ((
+ + (00 2x (s,
(15)
18

---

Published in Transactions on Machine Learning Research (08/2025)
where inequality (a) holds because O (x0)(s. holds that,
(s, (s). For each t' such that x(t) S t' s st, it (s, a
( -f
= -1- (1- (0)
-
(xQ) -
((s,)))))-(((())))))-))))))))))) PP(c R(s, + (P)()
x >> (P)(s )
as ()) + >> (s)) P(s, (s) - vn)
S 22 Io + + (s) P(s,at v
where equality (a) follows from the Bellman equation Eq. (3] and the last inequality follows from Eq. and that
13
(s, a (s)) v*) s
- Vo s s>lVi V*llo-
Thus, (s( - V/ (s))(s) can be upper bounded
(x) V (+) <
Σ
-
(-x(()
22 Σ
|| +7d
Σ ==x())
P(s)
v.. v
(16)
(=x(t)
Similarly, we have the following lower bound:
(s) 1 (x)
2
- at))
e' (==(())
1-1
1-1
2 2X
Σ (=x(()
A + 7d Σ
(
(0)(())) - a(s, vs.
(17)
f'=((1)
Plugging the bounds Eq.
16 and
Eq. back into Eq.
we get
K Σ
K
K
Pt - v/t)
< || x
+
K
vb
x(t))
V/2
1=1
k=1
1
||
+2
|
K
(()(()
K
7
K
1
max 8,0
Σ
(+) (e((e,))-((ss))VV) V
(=x(t)
proving the lemma.
D Proof of Lemma 4
When mod E = 0, then A = Ax6)). When mod E * 0, we have
Q (1 - + x
(1 -1--A _ (Q'
+R+
19

---

Published in Transactions on Machine Learning Research (08/2025)
So,
4 = 1 + A/ (PV- Pr v=11)
= (1- - 11-)))=-1- + 11PP - 1/-
V +
Pk: / - -
i-1
$ $1 - 1) A x(1) +
Σ (1- 1)= p/
j=x(1)
i-1
+ 7
Σ (1- (1- -V, V
(18)
x=x(1
For any state-action pair a),
- (1- (1- || |
(19)
For the second term, we have
>> Σ (1
(20)
)=
1-1
$ 7r
Σ
(1 (1- ((PP3))' p/
+
7>
Σ
(P)
-P--
(21)
)=
)=x(1)
Σ
i-1
(1-
k k γ
Alog
|KIAT|KT
(22)
5
(=x(1)
$ 1-7
7 X(E - 1)i + 7
Allo
S|ATT 8
(23)
1-71
for all (s. E S x A,i E 1 E [K]. From Eq. 21 to Eq. 22 since for each timestep, each agent independently samples the next state for all state-action pairs to form the sample transition matrix, we can use Hoeffding's incquality by treating \(1 - -P)
V* as the independent random variables with
their absolute values bounded by X(1 - A)- 1V
In addition, we have
1-1
Yr
viJ)
S^ Σ
(1 -1- (1-
1A
(24)
)=x(O)
==
Combining the bounds in Eq.
19
Eq.
20
and Eq.
24 we get
| S
S(1 (1
x)0- | aa +
7
X(E 1)k=
?
V Allo
KT
1-
- 7
8
1-1
+ 7 Σ (1- - || 11
j=x(1)
$ (1 - (1 - 77) x(() xx(0) 1
+ (1 + xx00
1 1
2 X(F 1 - 1)R +
Alog 5
SIIAKT
(25)
1 1-7
where the last. inequality can be shown via inducting on i- xii E (0....,F--
F-11. 1}.
When A E
(1 (1+ x(0 < (1+ E < (1+ 1/E)* F Se53.
20

---

Published in Transactions on Machine Learning Research (08/2025)
We get
| - 4x00 0o +3 1-7
Y A(E 1)x + ?
AAlog |
1-7 V
E Proof of Theorem 1
By Lemma
1
7
K
K
A+11 = (1- 1 Do + Σ
A)
PP
P
+
-1
Σ
P (V* (V* V.E.).
K
K
1=0
1=1
10
k=1
Taking the Lo norm on both sides, we get
A44alo I (1- A)tt1
A
Σ
Σ
(P
PL
(1.1)
(1.2)
K
X) Xy
Ph (V*
(26)
K
==
k=1
(L33
We bound the three terms in the right-hante sidd--e of the above-displayed equation separately.
Bounding (I.1). Since 0 S Qu(s,a) I
1 1-y; the first term can be bounded as
1
(I.1) = (1 - A)*+1 | (1 X)
(27)
1 1-7
Bounding (I.2). To bound the second term (I.2) in Eq. 26
we have
K Σ
I - 1 E(-
PM Σ
(ph-Pt V
pb
2=
k=1
i=0
k=1
K
(1
X)
- S5 PV.V".
K
k=
Let X,,A = -T\(1- ph V* It is easy to see that E (x,,, a)] for all (s, a). By Lemma we have (x,)(s,a))= S <パiー) 7>(1 - X) for all (s,a). Since the sampling across clients and across iterations are independent, via invoking Hoeffding's ' inequality, for any given E (0, with probability at least. - 6,
K [P- PPP-P
S|ATK
(122) = Σ (1 AY
5
K A log
(28)
1
k=1
21

---

Published in Transactions on Machine Learning Research (08/2025)
Bounding (I.3). To bound the third term (I.3) in Eq. (26) following the roadmap of Woo et al. (2023 we divide the summation into two parts as follows. For any BR S L
S T, we have
K
(1.3) Σ - A)'A7
Σ
PV*
Ph.
-
K
1=0
1
(1 - 17 A7
(V - v.41
K k=
i=U
10
X 9E
(1- (1- 17
(V - -V/9
(1 (1- 1)-
_ k=1
1 Σ
PV - V.h))
K
i=
(=x(t)-AR+1
1
K
(1 1)^ x
Σ
11= by
(V* (V-
1-7 1-
K
By Lemma 8
1 K
Σ
(1- i xy
Σ
(V* - Vil)
K A=1
-x
1 K
Σ
(1- (1-))
|Axxoollas
+ +21
Σ
Σ
ا
K
(=x())88++1
k= j=((()
Σ
(s) P(o,a)) -Po,))))(()))) P(o,a))
V-
max
K
5,a
Since (s,, a)'s are independent across time j and across state action pair (s, a), and I-m (from Lemma 2b, with Hoeffding's inequality and union bound, we get for any å E (0, 1), with probability at least 1 --d. 6,
<
S
Σ
(ss P(s.a) V < S(E (E 1) + 7
(E 1-)
(29)
8
(=((1)
for all (s,0) E S A, ke K, and i. By Lemma with probability at least (1 6), we have
1 i-1
Σ
(1- 2721
Σ
Σ
|
K -=
-x(0)-8+1
<212g
Σ
(1- -
Σ Σ
? |Axxoll +3 +3- ? - 1)x +
1-9 /
/Alog
SKKAT
K
1-7
8
-=x())-8E+
A= x(
+ 6-22
SIAATT
22 1)
max Xiis
| 20
+
(E
1)2xx
(E 1) Alog
1-7
1-7
8
22

---

Published in Transactions on Machine Learning Research (08/2025)
Thus, by applying the union bound, we get with probability at least (1 - -2)),
Σ (1-
1 K
Σ Pt
V.t)
i=x(t) -8
6)222
57 7 x(t) ((1)-BRSiS
max
| c0xloo + +2 1)
max (
A + 1-7 11-7 1- 11-
(E
+ 67 X
S|
(E 1) Alog 6
Σ
(1 11 xy (1 7>
(E 1)x + 7d
1 1-7 lggooo 8
log
S/AAT
(1-7
x((1)-88+1
| x(1) 10.00 + 72
= (1 + 2X(F 1)) max
1-7 (6A2(F= -1)2 + +A(E 1))
x(t) BESie
ST
65²2
S||AA|
(E log
(E - 1)
A Alog
8
1
8
Hence, the third term (I.3) in Eq. (66 can be bounded as
1
1 K
(1.3) = Σ (1 (1- ,
Pl (V -vay
vily
K
1=0
72 1 11-
< 1 1-7
KT (1 x)
+ 71 + 11(E-1))
max X(iss
|
+
-1)2 + A(E - -1)xr
1- V (E (E 1)
72x
6₂2x (E - 11 Alog
+ 1 7
(30)
8
5
Combing the bounds of (I.1), (I.2), and (I.3) in Eq. 26
Combing the bounds for terms
27
28
and 30,, we get the following recursion holds for all rounds T with probability at least (1 35):
A4t1ll (11 1)
1 7
Alog
SIATTK
7 (1 - (1- -)
1-7
1 y
K
1
72
+ + + 2X(E - 11)
max -3ESS
|
1-7 (6 11)2 + +(E 1))x
7²1
ST 6₂
|S |AATT
1 1-7 V (F - 11) log
(F 1)y A log
5
2
72
S <11 + 21(E-111)
max
A
Axi1le
+ 1 1-7
(1 -1- 1)-00 + 1-2
(6A2(E + A(E 1))x
x(t) (BESiE
72X
SI|AAK
6922
S S|ATT
1- V
(E - 1) log
(E- - 1)
A Alog
8
8
7
1 Aloo
S|ATK
V
1
K
8
Let
2
72
(1 - -2)8E
(6X2 - 1)2 + X(E 1))R
p 1 7
1 1-7
22x
SIATT
29 ( 1V Alog
S SIAKT
+ 1 1-7 V
(E- - 1)
8
8
7
1 >loo
1
+ 1 1- y
(31)
K
5
23

---

Published in Transactions on Machine Learning Research (08/2025)
With the assumption that A S 1-y the above recursion can be written as
1+
| S
max
| ooo + p.
2
Unrolling the above recursion L times where LBE sts we obtain that
1-1
1 7
max x(1) - L.RSish
Axxill 0
+
+
+ 2
y'p
2
2
1=0
1
1
2
L
+
1 P.
1 7
Choosing B
EV
L
M
t t+1= = T, we get
1 1+7 7
2
2 (1 2)aR + (GA2(E - 1)2 + X(E - 1)) 7
7²
|
5
1 + 1-9 y
2
+
6
E 1 +
7²vZ
V
MME 1og log
SIIAIKT
+
7
>llog |8IAATK
1-7)
5
1 1-7
K
1
$
exp
- (11 - 7)AT
(1- exp { (2 2/v(1 (2(1-7))77 >)AT
27
+ (1 7)2
(6A2(E - 1)2 + +(EE - 1))xz
1
VE 11+ 222VX
27
1
S||AA|TK
+
1 MAEE 1) log
Alog
(1-
(1 - 7/2
(1 71-
5
(1 (1-
K
4
242
$ (1 - 7)² exp
( ([1 7))TT
+ (1-7)² 7)2 (6A2 - 1)2 + +AEE - 1))xc
1472X
V log |K|LAKKT
27
/1
SSAATK
(1-
VF.
(1 (1-
V K
Alog
5
where the second inequality follows from
1 + (1
1-7 yV 1-7
1 7
N
1 V11- 7)
exp
2
2
(1 2)a5 S exp
-Xp
(1 -T]
S Sexp
{ 2 11
1
21
By the assumption that (E - 1) S RX:
the above can be further simplified as
|| S $(1- 7)- exp - [1- )
1472
X(E 1)xc + (1 21
16
X
log
SIIAIK
(1- 71-
K
24

---

Published in Transactions on Machine Learning Research (08/2025)
F Proof of Theorem 2
Let |A| = 1, in which case Q-function coincides with the V-function. According to Algorithm
when
mod E + O, we have
di+1 = ((1-1))1 xyp*) O + AR.
Define A A (1 - A)A + Ayp*, We obtain the following recursion between two synchronization rounds:
U1++1E ( + ((A4)) +... (AR)B-1) xR.
Define
K A
A
(A
(32)
K k=1
Note that Q" is the fixed point under the transition kernel P. we have AR = X(I = since A()) = X(I 10--p4 yP). Furthermore, since Qig...., Qif are identical due to synchronization, we get
Qiot1j 1LEI (T
A (1+ ................................ ........ A(E-11) (T-A1)
Consequently,
(=+1))= = Q' Q(+11)
BB (11 (I A + (..W+..AA... +(...((-11)) (1-AW) qr
(33)
Next, consider |S|= == 2 and even K with
1 0
0 1
p2k-1
p2k
for & E N.
0 1
1 0]
Then P 11 where 1 denotes the all ones vector. For the above transition kernels, we have
k
I, even,
payy
K
P, l odd.
Applying the definition of A in 32
yields that
1 K
A
(
K
1 K
(11 - +
+ Aypbye
K k=1
4 O Σ
Σ
even
odd
= - (111 1
2
Anc
= a P) + 3rP,
which is the eigen-decompositiion A(0) Let
Aι - (1 + 7) X2 A - 7), i 1 X1, 1-
25

---

Published in Transactions on Machine Learning Research (08/2025)
Then
1 0r 2 5 +1))
=e=10 1zg
(34)
Note that 0 S a S 3 < and I P and P are orthogonal projection matrices satisfying (7 - P)P = -0. The matrices for the second lerm of the error on the right-hand side of 33 reduce to
+ A + ....A(6-1) (I (1-A7 -4a))
E-1
E-1
Σ
(1 P)+ + Σ B:P)) ((00-a1)(( a1)(( -P) + (Bo P)
1=0
1=0
E-1
E-1
(1 01)
Σ
aglI p) + -11-81) Σ
3xp²
since ag = :30
R-1
E-1
(1 mn) Σ
ar(I - P) = -1-
3rP
since (I - P) and P are idempotent.
t=0
t=
It follow that
1 1 A(8) (1 + A()
+ +... +... -..1)( (1-A
EE-
E-1
(1 (g) - - (1)
Σ 04
(I- P) + (1-BB) - (1 31)
Σ
p.
i=0
i=0
Ang
=0
Applying 34 yields that
? 11-12 1- v
KE 2 1-7
(35)
1+7
It follows from
33 that the error evolves as
((+1) = (a BxP) A + kx(l PIQ",
which further yields the following full recursion of the error:
A = (a P
Ao +
Σ
-
KE(1 -E(1-P)QQ"
E=
(o) Do +
Σ
(I- - P - P)Q"
1=1
since (oE(T P) P) dg +
3 P.YEEN
1 a kg (I P)Q'
(a - P)+ 9 Ao +
1 ag
a -(0²
- a kg
+ - ag
(I - P)Q' + PQ"
where the last. equality applied the zero initialization condition.
Note that (I - PPQ** and PQ are orthogonal vectors. Since |S| = 2, we have
1 A 2 2 ||a0مl2 min - PJQ' 1|2 PP max |a
1 ax
Kg
35
22
1 ag
26

---

Published in Transactions on Machine Learning Research (08/2025)
ri 12
Let R
since Q" = -1- P)R+ L.R.R we obtain that
r 12
1
ri + r2
(I (I- = (I -I- P)R
PQ 1 1-7
PR
2 r -1
2(1 ((1-
[1 +
V2 2
V2 2(1 7)
||
11 T2
|PQ'
I12 + 12l
When ri = 12, the error AgE reduces to PQ" and | श |ni + r2 18 otherwise, min
P)Q"Il 21. [1P2_ = v2 min(/r: r2l. - t r2l3- remains to analyze the coefficients as functions of A.
2
To this end, introduce the following lemma:
Lemma The following properties hold:
1. Negativity: KE < O; KE T-aR
2. Monotomicity:
is monotonically decreasing for À E (0, )
3. Upper bound: g S - for X E (0, )
4. Lower bound: if (1+ 28 then I-an Ar (E-1)
Proof- We prove the properties separately.
1. Note that v1 < V2, - i1 = (1+ >),, and
1/2 = (1 7)A.
Then it follows from 35 that
xy
E-1
Σ 1=1
(u) v1) < 0.
KE
2
2. For the monotonicity, it suffices to show that
d Rx
< 0. We calculate the derivative
7X I-
(1 + -) - (1-7)12 E-1
KE
dA 2(1-
oF
1 11
- 112
Note that
(1 + 1 B-1
(1 - 7) E-
E-1
E-1
V2
00
1-
1 E 11
o
1 U2 +
E-1
3. For the upper bound, suffices to show the result at X
1
due to the negativity and monotonicity. At
14y
A = , have
2y E
Kg 7
7
<
72
2
22
4. For the lower bound, the case E trivially holds. Next, consider E 2 2. We have
Kg
7
(1 + 7) (1)
11
ag
1 1-92
(1 - u (1 5
イ== (2/g -v()
Æー
=-xy
(1 v
27

---

Published in Transactions on Machine Learning Research (08/2025)
Note that - nx I (1 x)" I 1 Zn for and 0 I 1. Then, for (1 + 7)A
1 2E
have
of (1 (1+ )))) 21 (1 (1+ 1
2
1 = (1 - (1- 8 2 1 - (1-
Moreover, for all x E [2] C [0 and (- 1-13 E E, we have
1
x 1- 2 x ž ルイ スィ こ 2
We obtain that
F-1 (u1 vf) Σes
Lí=1 / c. f. x dx
F-1
E lg(u2 vn)
7:(B - 1).
vf) +(1 -vz
2xE
2xE
The proof is completed.
We consider two regimes of the stepsize separated by A A log < to the small stepsize and the environment heterogeneity, respectively:
1 where the dominating error is due 144
(I-))=R
Slow rate due to small stepsize when X S Au Since 37. monotonically decreases À increases,
B (1- (1 (1-(1- (1- -(1- log =E
11-log2 2 F.
Note that log: (0, 2), applying the fact log(1 - x) + 2 xx² for [0, 2 yields that
log 1
log zE
log
log
2
1
2 E
zE
EE'
Then we get
2F log
3 2
E
62
Slow rate due to environment heterogeneity when A 2 Ag triangle inequality yields that
Recall that X < r Applying the
a
KE
1+
KE OF
a
Kg
a'
1-
For the first term, by the negativity and monotonicity in Lemma
5 it suffices to show the lower bound 1. then ag = 2 ((1 - (1 - -) + - (1+))))+ decreases as À increases. For
at x= = Ag- Since X < 145;
exp - W_ (-
where W-1 is the Lambert W function, such that (1 + 7))o S 2 we apply the lower bound in Lemma 5 and obtain that
2(+
KE aE
20 1).
logs [1
(1-7) E
(F
(E (E-1) 1) llog z
72
4
4
4E
(1 - 7)2
Additionally, applying the upper bound in Lemma yiclds
1++
R
E 12
(1 (1 - {)))==
1
0
<
1
a
7
72
(1 2)
28

---

Published in Transactions on Machine Learning Research (08/2025)
Therefore,
K
KE
00 +
KE
1+
O
O
0
1 O
E 1)
log z
4E
(1-7)=
(1 -2)z
1
((1 (1++7)7 (0g(:)(E 1)
(1 y2)=
1
n log()) -1) 4B/(1 77)
(1 7)2
4E
When 11 r2:
Ir1 + r2
|
(3
2(1 7)
|r] + 12 E
2(1 - 7) cT'
otherwise,
min - 112 1 12)
a Kg
A
max |0
V2
OF
1
a
2 min
[[] T2l
Ir1 + 72
max
| +
2
y
aB
1
1
72 log(()(EE -1) 4E/(1111))
1
2 min
|r r2l,
Ir1 + 12
max
2
1 y
y
(1 7)2
4E
ez
1
E
(>2log(2(E 1) 4E +
E
min
[r] T2/,
|r 72
max
(1 7)T
4E
'T
We can choose log(z) 2
1E(x42)
E' > 2 so that
(2" (E)()>(E-1)-1///
1.
Then the first term inside
(1+7))²(E-1)
41
the max operator is bigger. Then,
1 [r r2l,
E
| 2 min
( + r2
2
'1
(1-
29

---

Published in Transactions on Machine Learning Research (08/2025)
G Additional experiments
100
100
Phase stepsize =0.05
stopsze -0.1
Phans stepsire =0.2
Phase stopize -0.5
60
stepiize
One-shase training
60-
14d-
1dl.
40-
40-
20-
20-
2500
5000
10000
12500
15000
17500 20000
2500
5000
7500
10000
12500
15000
1750c
20000
(a) Phase 2 stepsize À VT
(b) Phase 2 stepsize ) Ve+I
200
100
60-
60-
[N]
[Ad-
40-
40-
17500
12500
15000 17500 20000
Time
Time
(c) Phase 2 stepsize d = c+1
where c 10 (e
(d) Phase 2 stepsize d = 141
100
Mdl-
40-
2500
5000
7500
10000
12500
15000
17500
20000
(e) Phase 2 stepsize Ae (++ 130.7
Figure 4: Choosing different stepsizes for phases 1 and 2 leads to faster overall convergence. E = =00.
30

---

Published in Transactions on Machine Learning Research (08/2025)
G.1 Impacts of E on homogeneous settings.
For the homogeneous settings, in addition to E = 10, we also consider E = {1, (1,20, 40, oo), where E xc means no communication among the agents throughout the entire learning process. Similar to Figure 2b there is no obvious two-phase phenomenon even the extreme case when oo. Also, though there is indeed performance degradation caused by larger E, the overall performance degradation is nearly negligible compared with the heterogeneous settings shown in Figures 2a and 3
stepsize
constant stepsize 0.1
constant stepsize 0.2
80
stepsize
80
stapsize
60-
60
14-1-
20
20-
5000
7500
10000
12500
15000
17500
20000
0
2500
5000
7500
10000
12500
15000
17500
20000
Time
Time
(a) F=1
(b) F=20
60
60
14--
20000
20000
2500
10000 Time
17500
(c) 40
(d) E=
Figure 5: Homogeneons federated Q-learning with varying E.
31

---

Published in Transactions on Machine Learning Research (08/2025)
G.2 Impacts of E on time-decaying stepsize
300
E-10
E=100
E=200
E=300
E-400
20-
Figure 6: Using time-decaying stepsize A V
the overall convergence becomes worse E increases
Final
Real Entr
Erail Crea
10000
12000
34000
18003
18200
22003
Figure 7: Final error versus T. It is clear that when choosing
the final error decays as increases.
VT
G.3 Different target error levels.
In Figure show the error levels that these training strategies can achieve within time horizon = 20, 000. The tolerance levels are 10%, 5%, 3%, and 1% of the initial error || respectively. At a high level, choosing different stepsizes for phases I and 2 can speed convergence.
32

---

Published in Transactions on Machine Learning Research (08/2025)
One-phase training with stepsize + E 10
Phase 1 stepsize 0.9, = -10
10.0% the inttal encr- 10.00
10.0% initta enner -10000 a 16198
5,0% of the initial smor- 5,00
5.0% of the initial error - 5.00
the intaal
3,0% of inttaal
3000
80
1.0% the initial erro- 1.00
80
1.0% of the inkiil error 1.00
60
60
[4
14
20-
20-
2500
5000
7500
10000
12500
15000
17500
20000
0
2500
5000
7500
10000
12500
15000
17500
20000
Time
Time
(a) One common x
vT throughout. | does meet
(b) With a phase stepsize of 0.9, it meets the 10% tolerance level at iteration 16198.
any of the tolerance levels within 20000 iterations
Phase 1 stepsize 0.5. E 10
Phase 1 stepsize 3.2. E 10
00.8% the inital emor- 10.00, 14531
0% the initaa emor- 10.00, 9651 5,0% of the instaal émar - 5.00 al - 19517
5. one of the initial emor- - 5,00
3.0% the inital
3.00
the initial cnor- -
80
7.0% the initial enor 1.00
80
1.0% the initial enorr =.00
60
60
20-
20-
25.00
1000
7500
10000
12500
15000
17500 20000
0
2500
5000
7500
10000
12500
18000
1730E
20000
Time
Time
(c) With phase 1 stepsize of 0.5, meets the 10%
(d) With a phase stepsize of 0.2, it meets the 10% and 5% tolerance level at iterations 9651 and 19517, respectively.
tolerance level at iteration 14531.
Phase 1 stepsize 0.1, E 10
Phase 1 stepsize - 0.05, E 10
100
10.0% the inital enor- 10.00, att 4031 5.00, att 13903
10.0%
crror 5,39, at 4605
5.0% the initial
5.0% of initial eror- 5.00 al 8613
3.0% the inital enor 3.00
3.0% of the initial orer 3.00. at 11998
the initial
80
intial
60
60
40
20-
20
2500
5000
10000 Time
12500
15000
17500 20000
2500
7500
10000 Time
12500
15000
17500 20000
(e) With phase 1 stepsize of 0.1, it meets the 10% and 5% tolerance level at iterations 4031 and 13903, respectively.
(f) With a phase stepsize of 0.05, it meets the 10%, 5%, and 3% tolerance levels at iterations 4605, 8613, and 15998, respectively.
Figure 8: Convergence performance of different tolerance levels of different stepsize choices. The horizontal dashed lines represent the tolerance levels met, while the vertical dashed lines indicate the iterations which the training processes meet. the corresponding tolerance levels.
33


Reviews:
[{"review_id": "Uu2vLdb0Bk", "reviewer": "Reviewer_1Zc6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The set-up, algorithm, and main results are described very well, and with appropriate rigor. \n- Upon checking the proofs (and assuming I have not missed any small details), the main result looks to be correct. \n- The paper provides a numerical simulation which I did not check in detail.\n- I appreciate the lower bounds on the $\\ell_\\infty$ norm of the error. While I have not checked the proof of this, it seems reasonable that there would be a linear (tight) dependence in $E/T$.\n\nWeaknesses \\& Comments:\n- I am sort of concerned with the use of the term \"fine-grained\" in the abstract, contributions, and generally throughout the paper, as the result reads more like a phase-transition characterization. I'd appreciate it if the authors could address whether there is a specific reason to call it fine-grained, and if they'd be open to avoiding the use of \"fine-grained\", which can be potentially misleading?\n- In page 2, in the introduction/contributions section, it would be nice if the authors could mention that they parameterize the environmental heterogeneity by a scalar parameter? It seems a bit vague at the moment.\n- In the contributions section on page 2, it would be nice if the authors clarify whether the algorithm can compute the threshold (if it needs to) and has to do something to realize the speed-up (unless it automatically does), for when K(E-1) is below the threshold. Regarding the computability of the threshold, it would be good if the authors say something about what the threshold depends on, or whether it is even computable.\n- Paragraph 1 of the contributions section uses $\\kappa$ for the sample complexity in page 2. However, $\\kappa$ is also later defined to be the transition heterogeneity on page 5. Can the authors add an explanation in the same paragraph?\n- The authors say in the last paragraph of page 3 that \"no state sampling is considered\". This is false. For instance, [1] does state-sampling in their SUBSAMPLE-MFQ algorithm.\n- Line 6 in page 4: can the authors clarify that $\\kappa$ is scalar?\n- In the introduction, can the authors discuss the difference with [4] which seems to (at least, morally) show a similar result.\n - Lemma 2 appears to be trivial. Is it really a part of the proof roadmap in Woo et. al. (2023), as the authors mention?\n- Equation 20 to 21 in the appendix: can the authors add a justification that the random variables (the inputs to Hoeffding) of $\\lambda(1-\\lambda)^{-j-1}(P_j^k - \\tilde{P}_j^k)V^*$ are independent?\n- Page 29: \"Thus with probability at least $1-2\\delta$\". Can the authors add a justification for why the probability becomes $1-2\\delta$ (by applying the above result twice). For a reader unfamiliar with the proofs in the field, this might not be obvious...\n\nAdditional Questions:\n- In the work on cooperative federated multi-agent RL with _homogeneous_ agents, some recent works on mean-field RL and mean-field sampling enable exponential and super-exponential speedups (respectively) with respect to the number of agents [1,2]. The paper currently refers to a \"linear speed up\" when K(E-1) is below their threshold. I'd be interested in knowing if this linear speed-up should similarly really be polynomial/exponential via the mean-field transformation (which is a natural perspective in scalable MARL).\n- In the last paragraph of page 3, it seems that recent works on heterogeneous agent RL [3] are very relevant (particularly the multi-agent advantage decomposition lemma). Does any of that argument transfer to this problem? Does it say anything interesting? If so, it would be nice if the authors could add such a discussion.\n- Is there no analogous Theorem 2 that holds for odd k?\n- Section F looks at the case where $|\\mathcal{A}|=1$. In the analogous setting where $|\\mathcal{S}|=1$, this recovers the multi-armed bandit setting. In this case, is there an analogous result that can be obtained via the $|\\mathcal{S}|=1$ setting? That would certainly be of tremendous interest to the bandit learning community.\n\nLimitations:\n- The authors mention that the current analysis focuses on synchronous Q-learning, whereas asynchronous Q-learning is left for future exploration. \n- Moreover, the authors mention that they have only identified _one such_ phase transition point; as such, it remains an open problem to estimate other such points.\n\n\n\nReferences:\n1) Mean Field Multi-Agent Reinforcement Learning. Yang et. al. (2018)\n2) Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning. Anand et. al. (2024)\n3) Heterogeneous-Agent Reinforcement Learning. Zhong et. al. (2024)\n4) The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond. Woo et. al. (2023)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies Q-learning in the federated RL setting where the agents (and agent interactions) are heterogeneous. The main contributions of the paper are \"phase-dependent\" error bounds: for instance, when K(E-1) is below a certain (computable) threshold, there is a linear speed-up comparable to homogeneous environments, whereas when it is above a threshold, a different behavior emerges. The paper also shows some unavoidable limitations of multiple local updates (E>1) in heterogeneous agent settings. Finally, the authors corroborate their theoretical findings with numerical simulations on a 20-agent game on a 5x5 maze with drifting transition probabilities.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the strengths \\& weaknesses section.", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zNUaenUaF8", "reviewer": "Reviewer_4S4T", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "After carefully comparing the revised manuscript with the previous version and the comments from the last round, I find that the revisions have significantly improved the clarity, rigor, and completeness of the work. I believe the manuscript is now ready for publication, though a  minor issue still needs to be addressed.\n\nMinor comments:\n1. Page 2, 2nd point of contributions, correct the size of parenthess in $\\Theta$. Same applies to several places such as Remark 4.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Same with prior venue.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Strengths And Weaknesses", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hhLRvkAAJP", "reviewer": "Reviewer_t7mP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors have fixed the issues in the previous version. I will recommend acceptance if other reviewers do not find key issues.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on the synchronous federated Q-Learning algorithm under environmental heterogeneity. It demonstrates performance degradation with regard to the synchronous period $E$, which is validated through a proof, information bound, and numerical experiment. In addition, the authors observed the two-phase phenomenon (where the error first decreases to a minimum point and then rebounds rapidly before stabilizing around a fixed value) in their numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "NA", "broader_impact_concerns": "Do not apply. This is a theoretical work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)