Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling
Authors: Feng Zhu
Aritra Mitra
Robert W. Heath
Venue: Accepted by TMLR ()

Abstract: Motivated by collaborative reinforcement learning (RL) and optimization with time-correlated data, we study a generic federated stochastic approximation problem involving $M$ agents, where each agent is characterized by an agent-specific (potentially nonlinear) local operator. The goal is for the agents to communicate intermittently via a server to find the root of the average of the agents' local operators. The generality of our setting stems from allowing for (i) Markovian data at each agent and (ii) heterogeneity in the roots of the agents' local operators. The limited recent work that has accounted for both these features in a federated setting fails to guarantee convergence to the desired point or to show any benefit of collaboration; furthermore, they rely on projection steps in their algorithms to guarantee bounded iterates. Our work overcomes each of these limitations. We develop a novel algorithm called \texttt{FedHSA}, and prove that it guarantees convergence to the correct point, while enjoying an $M$-fold linear speedup in sample-complexity due to collaboration. To our knowledge, \emph{this is the first finite-time result of its kind}, and establishing it (without relying on a projection step) entails a fairly intricate argument that accounts for the interplay between complex temporal correlations due to Markovian sampling, multiple local steps to save communication, and the drift-effects induced by heterogeneous local operators. Our results have implications for a broad class of heterogeneous federated RL problems (e.g., policy evaluation and control) with function approximation, where the agents' Markov decision processes can differ in their probability transition kernels and reward functions.

Published in Transactions on Machine Learning Research (01/2026)
Achieving Tighter erated Stochastic Approximation under Markovian Sampling
Rates for Heterogeneous Fed-
Feng Zhu
fihu5@@nsu.edu
Deportment of Electrical and Computer Engineering North Carolina State University
Aritra Mitra
amitro2@ncsu.c edu
Department of Electricol and Computer Engineering North Carolina State University
Robert W. Heath Jr.
rwheathhjr@ucsd. edu
Department of Electricol and Computer Engineering University of Colifornia, San Diego
Reviewed on OpenReview: https: openrevieww net/ forum? id- IaRG4ECacS
Abstract
Motivated by collaborative reinforcement learning (RL) and optimization with time-correlated data, we study generic federated stochastic approximation problem involving M agents, where each agent is characterized by an agent-specific (potentially nonlinear) local operator. The goal for the agents to communicate intermittently via a server to find the root of the average of the agents' local operators. The generality of our setting stems from allowing for (i) Markovian data at each agent and (ii) heterogeneity the roots of the agents' local operators. The limited recent work that has accounted for both these features in federated sctting fails to guarantee convergence to the desired point to show any benefit of collaboration furthermore, they rely on projection steps in their algorithms to guarantee bounded iterates. Our work overcomes each of these limitations. We develop a novel algorithu called FedHSA, and prove that it guarantees convergence to the correct point, while enjoying an Af-old linear speedup in sample-complexity due to collaboration. To our knowledge, this is the first finite-time result of its kind, and establishing it (without relying on projection step) entails fairly intricale argument that accounts for the interplay between complex temporal correlations due to Markovian sampling, multiple local steps to save communication, and the drift-offects induced by heterogencous local operators. Our results have implications for a broad class of heterogeneous federated RL problems (e.g., policy evaluation and control) with function approximation, where the agents' Markov decision processes can differ their probability transition kernels and reward functions.
1 Introduction
In the classical stochastic approximation (SA) formulation (Robbins & Monro, 1951; Borkar, 2009; Borkar
& Meyn, 2000; Meyn, 2023), the goal is to solve for parameter 0* Ød such that G(0*) 0, where G: .d. + Rd is a potentially nonlincar operator satisfying G(.) = Eowp [G(,,))]. Here, G Rd x X' + Rd is the noisy version of the true operator G, and is an observation random variable drawn with some unknown distribution μ from a sample space X. The agent (learner) tasked with finding 6* only has access to the operator G via noisy samples (G(,,o,), where {or} is a stochastic obscrvation process that typically assumed to converge in distribution p (Borkar, 2009). Interestingly, the SA formulation described above captures large class of problems arising in stochastic optimization, control, and reinforcement learning

---

Published in Transactions on Machine Learning Research (01/2026)
(RL). For instance, popular iterative algorithms like stochastic gradient descent (SGD) in optimization, and temporal difference (TD) learning, Q-learning in RL turn out to be specifie instances of SA.
Federated learning (FL) has also made extensive use of SA. The general idea of FL is to leverage data collected from multiple agents to train accurate statistical models for downstream prediction (Konečný et al., 2016; Bonawitz al., 2019; McMahan et al., 2017). SA has primarily been used FI. to solve stochastic optimization problems that arise in the context of empirical risk minimization (ERM), under assumptions like offiine data collection and i..d. (independent and identically distributed) data at each agent. In contrast, when the data arrives sequentially and exhibits strong temporal correlations is the case in multi-agent multi-agget/ffddrraeed /federated RI very little is understood about non-asymptotic/ haatmmtttc///iiiittiine /finite-tineeeeeeee performance. This is particularly the case when the agents' baata-geeraatig processes are potentially non-identical. In our paper, we develop convergence and sample-complerit results for a general class of federated SA methods that signifienntly improve upon eristing bounds, and provide deeper understanding of the interplay between hata-hhetroogenetty and temporal corvelations FL.
Our Federated SA Setup. We aim to develop unified framework that can accommodate broad class of distributed SA problems. To that end, we consider setup involving M agents that can exchange information via a central server, as is typical in an FL setting. Each agent i E [M] has its own true and noisy operators G Rd + Rdd and G; : Rd x X; + Rdd, respectively, where G,(-) = Eorn, [G.(;,) o)]. Here, X, is the sample space of agent i, and the observation random variable o is drawn from an agent-speciffe unknown distribution p4. The information available locally at an agent comprises a sequence of noisy samples (-,,),,,))) To capture temporal correlations, we assume that the observation sequence {or,e} is generated from an ergodic Markov chain M, with stationary distribution 14- Given this setup, the collective objective is to find the root 0* E Rd of the "average" operator G; this objective can be succinctly stated as
M
Find 0* s.t. G(0)) 0, where G G= 1 M
(1)
Note that to achieve the above objective, communication via the server is necessory. In a typical FL scenario, communication takes place over low-bandwidth channels, and can hence be costly and slow. To mitigate the communication bottleneck, we will adhere to the standard intermåttent communication protocol in FL, where an exchange of information with the server takes places only once in every H > 1 time-steps, where H is some predefined synchronization time-period. To summarize, there are three main features in our formulation: (1) Heterogeneity: The local operators {G:} al the agents can be non-identical and, such, have different roots; (2) Markovian Sampling: The agents' observation sequences are generated in a Markovian mannor; and (3) Sparse Communication: Agents need to perform local computations in isolation between communication rounds. Additionally, complying with the FL paradigm, the agents are required to solve the problem in (1) without ever exchanging their raw observations.
1.1 Motivation and Related Work
When one considers the challenging setting that involves all of the above features, there are significant gaps in the understanding of the problem in (1). We now explain these gaps by considering several motivating applications of (1). Along the way, we also review relevant. literature.
1. Motivation 1: Federated Optimization in Dynamic Environments.
L.L.. Data. When G is the gradient of local loss function at agent and G4 noisy stochastic version thereof, the problem in (1) reduces to the standard FL sctting that has been extensively studied under the assumption that the observation process (o.,)} at each agent i is generated in an i.i.d. manner from 14 (McMahan et al., 2017). Under this i.id. data regime, a large body of work has studied the heterogencous federated optimization problem (Li et al., 2019; Khaled et al., 2020; Karimireddy et al., 2020; Mitra et al., 2021; Gorbunov et al., 2021; Mishchenko et al., 2022).
2

---

Published in Transactions on Machine Learning Research (01/2026)
Markovian Data. Our formulation substantially generalizes the standard FL setting by allowing the observation process at each agent i to be generated from ergodic Markov chain that converges in distribution to p4. As explained in detail in Sun et al. (2018) and Duchi et al. (2012), there is ample reason to consider such Markovian data streams. Morcover, temporally correlated Markovian data arises naturally in several real-world applications: dynamic environments such as non-stationary wireless systems where the channel statistics drift over time following Gauss- Markovian processes, linear dynamical systems in control with input noise, and distributed sensor networks with correlated measurements. With these reasons in mind, considerable recent attention has been given to the study of Markovian gradient descent. in the single-agent setting (Sun et al., 2018; Doan, 2022; Even, 2023; Beznosikov et al., 2024).
Rescarch Gap: Counterparts of the results in the above papers remain open in FL, i.c., we are unaware of any fonile-imme results for federaled optimizalion under Markov dala.
2. Motivation 2: Heterogeneous Fixed Point Problems. Our work is particularly inspired by that of Malinovskiy et al. (2020), where the general problem of finding the fixed point of an average of local operators considered, exactly like we do in (1). As detailed in Malinovskiy et al. (2020), in addition to optimization, heterogeneous fixed-point problems find applications in many other settings such as alternating minimization methods, nonlinear inverse problems, variational incqualitics, and Nash equilibria compulation.
The main gap, however, is that Malinovskiy et al. (2020) consider a "noise- less" setting, where each agent can access their true local operator directly, i.c., there is no aspect of i.i.d. or Markovian sampling in their work.
Research Gap:
3. Motivation 3: Collaborative Multi-Agent RL. In RI, an agent interacts sequentially with an environment modeled as a Markov decision process (MDP). At each time-step, the agent plays an action according to some policy, observes a reward, and transitions to a new state. The goal is for the agent to play a sequence of actions that maximizes some long-term cumulative utility referred to as the aalue-function, without a priori knowledge of the reward functions and the probability transition kernels of the MDP. It turns out that the problem of estimating the value-function corresponding to given policy (policy evaluation), and that of finding the optimal policy (control), can be both cast as instances of SA (Meyn, 2023). In this context, the sample-complexities of SA-based RL algorithms like TD learning and Q-learning have been studied recently by Bhandari et al. (2018); Srikant & Ying (2019); Khamaru et al. (2020); Wainwright (2019); Guannan Qu (2020); Li et al. (2024); Mitra (2024). This line of work has collectively revealed that for contemporary RL problems with large state and action-spaces, several samples are typically needed to achieve a desired performance accuracy. A natural way to overcome the sample-complexity barrier via parallel data collection from multiple environments. This has led to new paradigm called federated reinforcement learning (FRL) (Qi el al., 2021), where the idea is to use information from multiple enviromments (MDPs) to learn a policy that performs "well" on average in all MDPs. Compared to FL, the theoretical aspects of FRL remain poorly understood. To explain the gaps in this context, we broadly categorize SA problems in FRL into two main groups as follows; for a quick comparative summary, see Table 1.
Homogeneous Environments. In this case, agents share identical MDPs and local operators. The works of Doan et al. (2019) and Liu & Olshevsky (2023) both examine federated TD algorithms under restrictive i.i.d. sampling assumption. While Shen et al. (2023) analyze federated actor-critic algorithms under both i.dd. and Markov data, they establish a linear speedup in sample-complexity (w.r.t. the number of agents) only under ii.d. data. To our knowledge, the first paper to establish a lincar speedup in sample-complexity under Markovian sampling for contractive SA problems was (Khodadadian et al., 2022), followed by (Woo et al., 2023) for tabular Q-learning. Follow-up works have focused on the minimum amount of communication nceded to achiove lincar speedups (Tian et al., 2024; Salgia & Chi, 2024) in comple-complexity, and also the effect of imperfect communication channels (Dal Fabbro et al., 2023; Mitra et al., 2024; Beikmohammadi et al., 2024; Dal Fabbro et al., 2025).
3

---

Published in Transactions on Machine Learning Research (01/2026)
Table 1: Comparison of finite-tine analysis for FRL papers that study stochastic approximation problems.
Work
Hetergencity
Vo beterogmellty bis
Linow speedip
Mariowinn sampling
(Doan et al., 2019)
(Lin & Olshersky, 2023, Shen al., 2021)
(Khodaladian al., 2022; Woo al., 2023; Solgia & Chi, 2024; Tian et al., 2024)
(Jin al., 2022)
X
X
(Wang ol., 2024b; Zhang al., 2024)
This work
Heterogeneous Environments. In practice, it is unreasonable to expect that the agents' environments are eractly the same. Thus, it makes more sense to consider setting where agents interact with potentially distinct MDPs, leading to distinct local operators. This setting has received much less attention. The convergence of federated Q-learning algorithms is analyzed in Jin et al. (2022), but no linear speedup is established. The results in Wang et al. (2024b) for federated TD learning, and Zhang et al. (2024) for foderated SARSA, do exhibit a lincar specdup in the noise variance term, but their bounds also feature an additive helerogeneity-indurer bias term that grows with the discrepancy in the agents' envirouments; such a bias term also appears in Jin et al. (2022), and its presence prechudes possible gains from collaboration.
Research Gap: To sum up, in the context of general heterogeneous stochastic approximation problems in FRL under Markov noise, it remains an open problem to establish a linear collaborative speedup that is not affected by any cnterogencity-indneee
bias term.
Now that we have elaborated on the motivation for our work and the research gaps in the literature, let us turn our attention to the main questions investigated in this paper.
Key Questions. Having motivated the rationale behind studying the problem in (1), can now state more precisely the key questions of interest to us. To do so, we start by presenting the convergence rates of SA in the single-agent case as benchmark. Accordingly, consider the SA scheme of Robbins & Monro (1951):
g((+1) = g( + a,G((())
(2)
for 6= O,.,, 1. Here, T denotes the total number of ilerations, 0(0) E Rd is the parameter estimate at time-step f, and {ar] is the step-size sequence. Asymptotic convergence results for the SA rule in (2) were derived in the seminal works of Tsitsiklis & Van Roy (1997) and Borkar & Meyn (2000). Finite-time rates under Markovian observations were more recently established in Bhandari et al. (2018); Srikant & Ying (2019); Chen et al. (2022); Mitra (2024), where it was shown that under certain mild technical assumptions (which will be detailed later in Section 2), running T iterations of the rule in (2) with the same step-size
og leads to the following error bound:
dr S S exeep exeeppoook (-aC2T) + aCzo²
bias
variance
where de == 1E 11 10 denotes the MSE at time-step t, C1,C2, C3 are problem-specific constants, and o² characterizes the variance of the noise model. The MSE bound consists of two components: (i) a bias term that decays exponentially fast and (ii) a variance term that captures the effect of noise. Thus, the rule in (2) ensures linear convergence to a ball of radius O (ao?) centered around 8*. By choosing an a on the order of O (log(T)/T), one can then achieve exact convergence to H*. Now consider the fed- erated SA setup with heterogeneous local operators, Markovian data, and intermittent communication. We ask:
Is it possible to converge exactly (i.e., without any bias) in the mean-square sense to the root 0* of the average operator G Moreover, can one achieve a linear M M-fold reduction in the variance term, copturing the benefit of collaboration!
Contributions. As far as we are aware, no prior work has been able to establish both exact con- vergence and linear sample-cone complerity speedups FL under Markovian sampling and heterogeneity of local operators. We close this significant gap via. the following contributions.
4

---

Published in Transactions on Machine Learning Research (01/2026)
Motivation for New Algorithm. In Section 2.2, we study the performance of existing FRL algorithms (Jin et al., 2022; Khodadadian et al., 2022; Wang et al., 2024b; Zhang et al., 2024), where each agent performs multiple local parameter updates using just its own operator. Proposition reveals that in a heterogeneous setting, such algorithms fail to match the single-agent SA convergence rate in (3). In particular, when run with a constant non-diminishing step size a, such algorithms do not converge exactly to the root 0", even in the absence of noisc.
Novel Algorithm. Motivated by the findings from Section 2.2, we develop new local SA procedure called FedHSA in Section 3. The core idea in FedHSA is to modify the local update rule to ensure convergence to the correct point H* We emphasize that while drift-mitigation techniques to combat heterogencity have been studied before in federated optimization ( (Karimireddy et al., 2020; Gorbunov et al., 2021; Mitra et al., 2021), FedHSA is not limited to optimization. Instead, FedHSA applies much more broadly to general nonlinear SA problems, including those RL.
Matching Centralized Rates and Linear Speedup. In Theorem 2 of Section 4, we prove that FedHSA matches the centralized rate in (3), and, uilkke the results in Jin et al. (2022); Wang et al. (2024b); Zhang et al. (2024), there is no heterogeneity-innde indducdd bias in our final bound. Furthermore, with a linearly decaying step-size, we prove that FedHSA achieves an optimal sample-complexire bound of ((1(MHTT) after T communication rounds, with H local steps in each round (Corollary 1). This result is significant because it is the first to establish a collaborative M -fflld linear speedup for heterogenemus federated SA problems under Markovian sumpling, with no additional bias term to negale the benefit of collaboration.
Analysis Technique. Even in the single-agent SA setting, finite-time analysis under Markovian data is quite non-trivial. Our FL setting is further complicated by complex statistical correlations that arisc from combining data generated by distinct Markov chains, drift effects due to heterogeneous local operators, and multiple local steps. The only other recent papers (Wang et al., 2024b; Zhang et al., 2024) that consider similar settings rely on a projection step in the algorithm to ensure uniform boundedness of iterates. Furthermore, they build on a "virtual MDP framework" for their analysis. Our proof neither requires a projection step nor a virtual MDP. Tn particular, the lack of a projection step entails a much more involved analysis. We elaborate on the main technical challenges in Section 5.
Although our work is primarily theoretical, corroborate our main theoretical findings via numerical simulations, covering both optimization and RT, in Section D.
More Related Work. Since the focus of this paper is on federated stochastic approximation, we have only reviewed SA-based approaches in FRL. We note that policy mandient-based approaches for FRL have also recently been explored in Xie & Song (2023); Fan et al. (2021); Tan et al. (2023); Wang et al. (2024a); Zhu et al. (2024). In particular, the approaches developed in Wang et al. (2024a) and Zhu et al. (2024) manage to achieve collaborative speedups without incurring additive bias terms due to heterogeneity. That said, even in the single-agent setting, the dynamics of policy gradient methods and SA schemes in RL are considerably different, and entail separate treatments. For instance, the aspect of Markovian sampling does not show up at all in volicy-gradient methods.
At the time of preparing this paper, we became aware of a very recent piece of work by Mangold et al. (2024) that looks at federated linear stochastic approximation (LSA). In this work, the authors provide a detailed and refined analysis of local update rules- of the form of FedAvg under both i.i.d. and Markov sampling. Furthermore, they develop bias-corrected algorithm for federated LSA, and show that it simultaneously achieves a linear speedup and no heterogeneity-innuuee bias. Although the flavor of the results in Mangold et al. (2024) is similar to that of our work, there are significant differences in scope, algorithms, and proof techniques that we outline below. First,, the results in Mangold et al. (2024) are limited to linear stochastic approximation (LSA). In contrast, we consider general nonlinear operators throughout this work. An inspection of the refined analysis in Mangold et al. (2024) seems to suggest that the recurrence relations exploited in Mangold al. (2024) rely heavily on the linearity of the underlying operator. More precisely, the approach in Mangold et al. (2024) is based on the framework in Durmus et al. (2025) which relies on expressing the error dynamics as a linear time-varying system that involves a product of random matrices. Such an error recursion does not arise in our analysis which involves non-linear operators, thereby requiring a different proof approach right from the first step. Second, the results under Markov sampling in Mangold et al.
5

---

Published in Transactions on Machine Learning Research (01/2026)
(2024) are provided only for the vanilla federated LSA schemes, not for the bias-corrected one. Thus, even in light of the contributions made in Mangold et al. (2024), our work is the first to establish linear speedup result without heterogeneity bias for general (nonlinear) contractive SA under Markov sampling. Third, the authors in Mangold et al. (2024) use the "blocking technique" " to handle temporal correlations under Markov sampling- This requires modifying the original algorithm so that only operates on a sub-sampled data sequence, where the sub-sampling gap is informed by the mixing time of the underlying Markov chain. In contrast, our proof technique is more direct, does not go through the blocking apparatus, and, as such, requires modification to the algorithm for Markov data.
2
Setting and Motivation
2.1 Setting
We consider mulli-agent heterogeneous SA problem involving M agents, where each agent i [M] has its own local true operator Gj Since the true operators are generally hard to evaluate exactly, each agent can access G; only through sequence of noisy samples [Gi(-, o(.))) The observation oi, made at time-step by agent i is sequentially sampled from an underlying agent-specisic time-homogeneous Markov chain M: with stationary distribution p;, We further have G.(-) = Exnn, [Gi(-, o)]. We consider the case where the agents' Markov chains {M.} share a common finite state space S, but have potentially different probability transition matrices. The collaborative goal is to solve the root-finding problem described in (1) within a federated framework, where the agents communicate intermitietly via central server only once in every H time-steps, while keeping their raw observation sequences {or,e} private.
Working Assumptions. We now make certain standard assumptions on the agents' operators and stochastic observation processes for our subsequent analysis.
Assumption 1 (Lipschitzness). The local noisy operator G, for each agent i [M] is L-Lipschitz, i.e., there erists constant L 2 1 such that given any observation o, for all 01, O2 E Rd, we have
[[C((0,, -G((02, 0)112 L 110 02l12-
(4)
Furthermore, there erists o, 2 1 for each i E [M] such that for any given 0 o, the following holds
||G((,,))] o)l22 S E[100]2 + tz).
(5)
Assumption 2 (1-point strong monotonicity). The average true operator G is 1-point strongly monotone w.r.t. 0+, i.e., there erists some constant μ E (0, 1] such that for any 0 E Rd, we have
(0 (0- 0" ã - G(O))) < p 110 0 0" 1-
(6)
In the context of optimization, Assumption corresponds to smoothness assumption typical in the analysis of Markovian gradient descent (Doan, 2022), and Assumption 2 corresponds to strong-convexitty As for RL, Assumptions and both hold for TD learning with linear function approximation (LFA) (Bhandari et al., 2018; Srikant & Ying, 2019; Khamaru et al., 2020; Tsitsiklis Van Roy, 1997; Doan et al., 2019; Liu & Olshevsky, 2023; Khodadadian al., 2022: Tian et al., 2024; Wang et al., 2024b), and certain variants of Q-learning with LFA (Chen et al., 2022; Zeng et al., 2022), where G; and G, correspond to the non-noisy and noisy versions, respectively, of the TD TD/Q-learnig update rules. Assumptions 1 and 2 suffice to guarantee the MSE bound in (3) in the centralized case, i.e., when M = 1. Since our objective is to obtain such a bound for the multi-agent heterogeneous setting, it is natural for us to work under the same assumptions.
The next assumption on the agents' Markov chains helps control the effect of temporal correlations in the data, and appears in almost all finite-time analysis papers for both single-agent (Bhandari et al., 2018; Srikant & Ying, 2019; Chen et al., 2022; Adibi et al., 2024; Guannan Qu, 2020; Li et al., 2024) and multi-agent RL (Khodadadian et al., 2022; Zeng et al., 2022; Wang et al., 2024b; Woo et al., 2023; Tian et al., 2024; Zhang et al., 2024; Dal Fabbro et al., 2023).
Assumption 3. For each agent: E [M], the state space of the underlying Markov chain M, is finite, and the Markov chain M, is aperiodic and irreducible.
6

---

Published in Transactions on Machine Learning Research (01/2026)
A key implication of Assumption 3 is that it implies geometric mixing of each of the agents' Markov chains (Levin & Peres, 2017). More precisely, for each i E [M] there exists some 2 1 and some Pi E 10, such that the following is true for any state 8 E S:
dTv (P(o. = 10,0 = s) S capl. Vt 0,
(7)
where (Pv Q) is the total variation distance between two probability measures P and Q, o denotes the state of agent i at the t-th time-step, and μi is the stationary distribution of M,. In words, Assumption 3 implies that each agent i's Markov chain converges to its stationary distribution b4 exponentially fast.
We now define the concept of a mixing time that plays a key role in our analysis. Intuitively, the mixing time of a Markoy chain measures how long it takes for the chain to "forget' its starting state and become close to its stationary distribution. For any & E> O, we define the mixing time of the Markov chain M, (at. precision level E) as (e) := minst= E No : csp S E). We define r(e) == [ax (e(s) as the mixing time corresponding to the slowest-mixing Markov chain.
Our final assumption concerns statistical independence between the data across different agents. Such an assumption is needed to establish "lincar speedups" in performance, and has appeared in prior FRL work (Khodadadian et al., 2022; Woo el al., 2023; Wang et al., 2024b; Zhang et al., 2024). Assumption 4. For every pair of agents + j E [M), the observation processes {or,e and {oga} are stotistically independent.
With the above assumptions in place, we are in a position to describe and analyze our proposed algorithm. Before doing so, however, it is natural to ask What is the need for a new federated SA algorithm? We provide concrete answer in the next section.
2.2 Motivation for a new Federated SA Algorithm
To explain the motivation for developing our algorithm, it suffices to focus on the class of linear stochastic approximation (LSA) problems, where for each agent i e [M], G, = A, - b,, and (,(0,,,,) = (o,
b((o),)) i.c., the operators are affine in the parameter 0. Furthermore, to isolate the effect of heterogeneity, we will consider a simplified "noiseless" setting where each agent can directly access its true operator (O). Our goal is to formally establish that even for this simplified scenario, if one employs the existing algorithms in Jin et al. (2022); Khodadadian et al. (2022); Wang et al. (2024b); Zhang et al. (2024), then it might be impossible to match the convergence rates in the single-agent setting. To see this, we first note that the algorithms in these papers operate in rounds L == =0,1,... 0.1....,7? T-1 1, where within each round 1, each agent performs H 2 1 local model-update steps of the following form:
of0 = 000 + (00)), HI
(8)
where 0/2 is agent i's parameter estimate in local step & of communication round t, and n E (0, is a step-size. For each i E [M], o
is initialized from a common global parameter T At the end of the t-th round, each agent i transmits o to the server; the server then broadcasts the next global parameter g(++1 = (1/M) EvETan o to all the agents. We will analyze local SA rules of the form in (8) under the standard assumptions made to derive finite-time rates for linear SA in the single-agent case (Srikant & Ying, 2019): for all i E [M], (i) (Lipschitzness) the 2-norms of A, and b, are bounded, and (ii) (strong-monotoniictyy all the cigenvalues of A; have strictly negative real parts, i.c., A; is Hurwitz. When M 1, i.c., there is only one agent, and H = 1, i.e., communication occurs every time-step, the rule in (8) ensures exponentially fast convergence to the root of the underlying operator (Srikant & Ying. 2019). Our next result reveals that this no longer the case when M > and H > 1. To state this result, we define A == (1/M) Eie[M) As, b = (1/M) EiELM bi, and A' (1/M) EiE A?.
Proposition 1. Suppose M > and H = 2. Consider the local SA update rule in (8), and suppose the step- size v) is chosen such that the matris (I + 2 + 172 A') is Schur-stabled Then, we have: lim 011) 0" = 1jU,
A square matrix Schur-stable its eigenvalues all lie within the open unit disk the complex plane, L.e. the magnitude of each of its eigenvalues is strictly smaller than one.
7

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm 1 FedHSA
1: Input: Local siep 7) global step-size ag, initial parameter (()), initial noisy operator G(
for & ...... T do
for = ...., M do
4: Agent initializes its local parameter 0 = g(t) for = 0, .....
do Agent i observes o, generated from its Markov chain M,, and updates 0 as per (10).
6:
7: end for
8: Agent transmits |,1 ( 7l9) to server.
end for
10: Server broadcasts ((++1) computed in (11).
11:
for == = M do
12: Agent. transmits (,(+++)), 0 )) to server.
13: end for
14: Server broadcasts average operator G(G(t+!)).
15:
end for
where (1/M) + n -A' AR - -8)) 07 A,'be is the root of the local operator G., and 8* = b bbbbaa is the root of the global operator G.
The main takeaway from Proposition is that even with just 2 local steps (i.e., H = 2) and no noise, in the limit, there is non-vanishing eтror qe that depends on how much each local root 07 differs from the global root 8" To climinate this crror, the step-size must be diminished with time, i.c., one cannot afford to use a conslant step-size like in the single-agent case. Note, however, if diminishing slep-size sequence is used, although convergence to the desired point 6* guaranteed, this will come at the cost of slower, sublinear convergence rate. few crucial comments are in order about this result.
1.
The phenomenon observed in Proposition has nothing to do with noise at all, i.e., whether the noise is i.idd or Markovian is immaterial as far as the main message of Proposition is concerned.
The key issue at play in Proposition 1 is that the agents' operators have distinct roots, creating the "client-drift" effect under intermittent communication.
3. Heterogeneous federated optimization is a special case of Proposition 1 In particular, Proposition stated for linear stochastic approximation (LSA) algorithms, and quadratic optimization is a special case of LSA. An immediate corollary of this point that even in federated optimization (without noise), if one uses a vanilla local update algorithm (with no bias-correction), then a constant. step-size will lead convergence to an incorrect fixed point, i.e, the client-drift effect connot be eliminated. For optimization, this message has already been conveyed by Charles & Konečný (2021). Proposition simply generalizes this observation to more general SA schemes.
Thus, there is a gop between the bounds in the single-agent case and those achievable with algorithms of the form in (8) in the heterogeneous federated SA setting. We now procoed to develop FedHSA that will not only close this gap, but also achieve an optimal M-fold sample-complexity reduction due collaboration.
3 Proposed Algorithm: FedHSA
In this section, we will develop our proposed algorithm titled Federated Heterogeneous Stochastic Approximation (FedHSA), designed carefully to account for heterogeneous local operators and intermit communication. We now elaborate on the steps of FedHSA, outlined in Algorithm 1. FedHSA adheres the standard intermittent communication model in FL, where communication takes place rounds 0, 1,.... At the beginning of each round t, central server broadcasts the global parameter g(t) all the agents, who then perform H steps of local updates; will describe the local update process shortly.
8

---

Published in Transactions on Machine Learning Research (01/2026)
We denote the local parameter of agent i at the 8-th local step of the I-th communication round as 0,2 with o/e initialized from Ø0) In each local step l of round t, agent i interacts with its own environment and observes ofr from its Markov chain M₁ Using this observation, agent computes the noisy operator G. (.)) Note here that we define each local step as a time-step, and thus 0f can be equivalently denoted as 01,
(t)
The Core Idea. The core technique involves the local update rule at each agent. As revealed in Section 2.2, if each agent makes local updates by simply laking steps along its own operator, then it can be impossible to converge to 0", while maintaining the same convergence rates as in the centralized setting, However, this is prociscly what is done in the existing FRL litcrature (Jin et al., 2022; Khodadadian et al., 2022; Woo et al., 2023; Wang et al., 2024b; Zhang et al., 2024), where the local update rule lakes the form
(0) 311 0 + nG.i (0) 1, o..)
99)
with 1) > O being the local step-size. When cach agent i follows the update rule in (9) for several local steps, it tends to naturally drift lowards the root 0j of its own local operator G3 As such, the reason why update rules of the form in (9) fail to achieve the desired MSE bound in (3) can be attributed to the following simple observation: in the heterogeneous setting, the root O of the global operator G may not coincide with the average (1/M) E 8 of the roots of the agents' local openators.
We now develop a drift-mitigaionn technique that overcomes this issue. To start with, we observe that if each agent had the luxury of talking to the server at every time-step, the ideal update rule of the global parameter would be g(++1) = g(t) + (g())) where G(B())= == (1/M) Eielan G,(((+), o..)). Under the intermittent communication model, however, this is not feasible since an agent & does not have access to the information from the other agents in [M] \ {i} during cach local stop. Accordingly, our algorithm exploits the memory of the global operator G(0()) from the beginning of communicattin round I lo guide the local updates of each agent during round t. Here, G(B(*)) == (1/M) Ee G((B(t), ,o,)), and the initial global parameter Φ(0) can be arbitrary. To be conerete, at each local step E of round t, agent í adds the correction term G(Ø())- (,(0)), o()) to its local update direction (, o.0) to account for drift-effects, leading to the update rule for FedHSA:
0 1 004 + n (G:1002.000 + +((0)) - G -,0 ,0(0)
(10)
To gain further intuition about the above rule, suppose for a moment that every agent can access the noiseless versions of their local operators. In this case, the noiseless version of FedHSA would take the form: 1.4+1 = 0 +n (G,(o!)) + G(Ø())) ())))) Now suppose the global parameter g(t) is 0*. Since 000 = (()) and G(0r) 0 by definition, observe that all subsequent iterates of the agents remain at 0*, Said differently, if one initializes FedHSA at 8*, the iterates never evolve any further, exactly as desired, i.c., the root 0* of the operator G is a stable equilibrium point of FedHSA. After H local steps, each agent i transmits their local parameter change (t) := =00² g(t) to the central server, and the global parameter 0(t) is updated as follows with global step-size 0g:
g(++1) = -(()) + ag
Σ
( I
(11)
M
iE[M]
This completes the description of FedHSA. Remark 1.
We note that in the federated optimization literature, variety of techniques have been proposed to account for heterogeneity, e.g., prozimal methods in Sahu et al. (2018); Pathak 8 Wainwright (2020); Mishchenko el al. (2022), and gradienl-truckingg tintentttruuckig//wue hwnp:l/-tuuuiiiinuarrreeieti /tt//aaccereeuaattiii in Karimireddy el al. (2020); Milra el al. (2021); Gorbunov et al. (2021). While the update rule of FedHSA might bear a cosmetic simélarity with those these papers, we note that if one considers SA problems other than optimization, such a similarity ceases to erist. For instance, if one considers TD or Q-learning with linear function approzimation, then the corresponding FedHSA rule would be one that has not been analyzed before in FL. or FRI.
9

---

Published in Transactions on Machine Learning Research (01/2026)
4 Main Results and Discussion
As warm-up to our main convergence result for FedHSA, we first consider a simpler setting where the observation (2) dig made by each agent E [M] at local iteration l and round & is drawn i..dd from the stationary
distribution #4 of its underlying Markov chain Mi. With dN := E [1000 - 0- 011]] we have the following result for this setting.
Theorem 1. Suppose Assumplions 1 to 4 hold, and consider the i..d. sampling model described above.
Define Hijyy as the effective stepsize, and == (os 110% Then, there exists universal constant C, such that with ag and 11 i 1 FedHSA guarantees the following VT 2 0:
(- |0000 - -01 +0
(ot HMM
02. )
a²Lt) 122
dr S exp eep
+
Next, we present our main convergence result under Markovian sampling. Theorem 2 (Main Result). Suppose Assumptions 1 to 4 hold. Define 7 T T(a2) and p p= max4e[M] Pi-
Then, there erists universal constant C' 2 1, such that by selecting ag = 1, S L/(C"=L21t) the following holds for FedHSA for any T 2 2
dr S exp ( (do + +
0
FaL?
+ 112
a²L*
0².
(12)
(MH(1 - p)
The next result is an immediate corollary of Theorem 2.
Corollary 1 (Linear Speedup). Suppose all the conditions in Theorem 2 hold. Then, by choosing = 4log( ( (uHH), and T 2 (4I.2og (og(MHT)//² max following for any T 2 2F:
- - FedHSA guarantees the
(( do - MHT
FL20²
dr 2
)
(13)
We provide detailed convergence proofs of Theorems 1 and 2 in Appendices B and C, respectively. We will provide a proof sketch for Theorem shortly in Section Before doing so, several comments are in order.
Discussion. Comparing our bounds for the i.i.d. (Theorem 1) and Markov settings (Theorem 2), we note that the only difference comes from the fact that the noise variance term o² in the Markov case gets inflated by an additional factor 7/(1- ([1--) p) capturing the rate at which the slowest mixing Markov chain approaches its stationary distribution. Such an inflation by the mixing time is typical for problems with Markov data (Nagaraj et al., 2020).
Matching Centralized Rates of Convergence. Theorem 2 reveals that FedHSA guarantees exponentially fast. convergence to ball around 0*. In particular, comparing (12) with (3), we conclude that FedHSA recovers the known finite-time bounds for single-agent SA in Bhandari et al. (2018); Srikant & Ying (2019); Chen
et al. (2019; 2022); Mitra (2024).
Linear Speedup Effect. From (12), notice that the radius of the ball of convergence around 0* is the sum of two terms: an O(aFo3 ()M (())) term that gets scaled down by the number of agents M, and a higher-order O (a²a²) term that can be made much smaller relative to the first term by making a sufficiently small, iee., the dominant noise term cxhibits a "varianccereduccioon" effect. To further highlight this effect, Corollary reveals that with a decaying step-size, the sample-complexity of FedHSA is (TH)( this is essentially the best rate one can hope for since after H local steps in T communication rounds, the total number of data samples collected across M agents is preciscly MTT The M-fold reduction in sample-complexity makes it explicit that even in a heterogeneous federated SA setting with time-correlated data, one can achieve linear speedups by collaborating using our proposed algorilhmm FedHSA This is the first. result of its kind and significantly generalizes similar bounds for homogeneous FRL (Khodadadian et al., 2022; Woo et al., 2023).
Communication Complerity. First, should be clear that the notion of communication complexity makes sense unless we associate it with desired performance. For instance, our algorithm can involve zero
10

---

Published in Transactions on Machine Learning Research (01/2026)
communication, but then the performance guarantees would be vacuous. Keeping this in mind, recall that for the single-agent centralized setting, given R samples, the standard SA scheme achieves mean-square error (MSE) on the order of (l) Now, say each of the M agents in our setup has access to precisely R samples. A natural question then is: How much communication is needed to achieve an MSE rate on the order of ()), exhibiling the desired linear speeduu effect? We answer this question below.
In our notation, recall that T' is the number of communication rounds, and I/ the gap between communication rounds. As such, have R TH. Now note that Theorem 2 of our paper presents the following result:
dr - exp exp (-" Odo + +0
FaL?
+
O².
pMH - p) p.a
(+)
(+*)
This is essentially saying that the MSE after T communication rounds is upper-bounded by an exponentially decaying term (+) plus a term (**) scaled down by the number of agents M, and another term (+ * *) that is
higher-order in a, but not scaled down by M. In order to achieve linear speedup, it is then straightforward that the term (* * +) should be dominated by (**), imposing the following requirement on the maximum allowable gap H between communication rounds (to preserve the linear speedup effect):
H [T - p))-
Substituting the choice of a Hox = 4 4log(MHH))/(T))) in Corollary 1, we then have
TT
H 4L p) log (og(MHT)
Finally, using T R//H in the above display yields the requirement:
H 1 2L M(1 - p) (M))
FR
(14)
which is essentially R/M). Concretely, given M and R, one can then set to be
FR H 2L M(1 p) (R)
With H as above, the communication overhead is T' R/H, which is on the order of VMR. A key message conveyed by the above discussion is follows: to achieve the desired lincar speedup, the gap H between communccaiin rounds cannot be arbitrarily large; instead, it needs to satisfy the constraint imposed in (14).
No Heterogeneity Bias. In Proposition 1, we saw that if one employs the algorithms in Jin et al. (2022); Wang et al. (2024b); Zhang et al. (2024) in the heterogeneous setting, then there is heterogeneitt-innduee bias term in the final bound that can potentially negate the benefits of collaboration. FedHSA effectively eliminates such a bias term without making any assumptions whatsoever on the level of heterogeneity. To see this, it suffices to note from (12) that in the noiseless case when o² 0, FedHSA guarantees exponentially fast convergence to 0", opposed to ball of radius O(1)) around 0* like in Proposition 1.
Remark on Constant Constant/Diminise Diiiiiisiing Step-sizes. As one might expect, constant step-size (adopted in this paper) admits a much cleaner analysis than a diminishing step-size, which is exactly why we adopt it, to avoid distraction from the main message that we are trying to convey, i.e., we are able to fill the gap of achieving linear speedup with no heterogeneity bias under Markovian data.
Next, we note that non- con-dimnnishing constant step-sizes are used readily in the literature on SA/RL. even in simpler single-agent settings, precisely with the same motivation (as us) of providing simple, clean analysis;
11

---

Published in Transactions on Machine Learning Research (01/2026)
see, for instance, Bhandari et al. (2018); Srikant & Ying (2019). In fact, note that in Theorem 2 (part (a)) of Bhandari et al. (2018), the constant step-size requires knowledge of the horizon R= HT, much like us. Other than picking up some additional log factors, this causes no degradation in the overall learning rate.
Having explained why we chose constant step-sizes, and the fact that such a choice is common in SA/RI, we now mention two pathways for getting rid of the knowledge of R. One direct option to use a diminishing step-size schedule. For this setting, we can borrow well understood proof techniques: for instance, the one used to prove item (c) in Theorem 2 of Bhandari et al. (2018). The other-perhan the "doubling trick" in the online learning literature. The basic idea is as follows. We first set the horizon length to say R', decide the step-size as per R' (like in our paper), and run the algorithm for R' - 1 iterations. Then, we set R' + 2|',, reset the step-size, and repeat. This degrades the performance of the algorithm by at most a constant factor. To see why, note that due to doubling, the k-th epoch is of duration 2*, if R' = 1. Suppose the true unknown horizon length R. Let J be the last epoch before the horizon length is exceeded, i.c., 2'-1 R, implying 2 > R/2. But since the duration of the last epoch is preciscly 2", we conclude that the last epoch contains al least half the lotal number of samples R. Consequently, long story short, the price of not knowing Re priori is a degradation by a constant factor that is no worse than 2.
casier to adapt technique-
To corroborate our developed theory, we provide various simulations in Appendix D.
5 Challenges and Proof Sketch
Although the analysis of Markovian sampling has appeared in prior SA/RL work, arriving at our main result in Theorem is highly non-trivial, and requires overcoming several technical challenges arising from the interplay between complex statistical correlations, drift effects due helerogeneity, and multiple local update steps. In what follows, we elaborate on these challenges by explaining why existing proof techniques are inadequate for our specific setting.
Comparison with homogeneous federaled RL/SA papers. The first paper to analyze the effects of Markov sampling in FRL was Khodadadian et al. (2022), followed by Woo et al. (2023). In Khodadadian et al. (2022), the authors consider a homogeneous setting, where all agents' operators have the same root, and as a result, a standard FedAvg-style local update rule suffices. Even so, the analysis in this paper is quite involved and proceeds by using the concept of Generalized Moreau Envelopes. It is not at all apparent whether such a proof technique could be extended to handle the bias-correctod local update scheme in our paper, subject to additional drift effects introduced by helerogeneily in agents' operators. Our proof, in contrast, does not require going through the framework of Generalized Moreau Envelopes, and analyzes different local update scheme altogether (relative to that in Khodadadian et al. (2022) and Woo et al. (2023)).
While the analysis in Woo el al. (2023) sharpens some of the bounds in Khodadadian el al. (2022), the results are derived only for tabular Q-learning without any function opprozimation. Even in a single-agent sctting, it is well understood that extension from the tabular sctting to the function-approximatton sctting is highly non-trie triviarvial, and several papers have focused precisely on this extension. In particular, for the tabular setting, relatively straightforward argument (requiring no more than a couple of lines) suffices to establish that the Q-table iterates remain uniformly bounded throughout the course of the algorithm; see, for instance, Guannan Qu (2020). This fact is leveraged throughout the analysis. Unfortunately, under function approximation, it is no longer the case (in general) that the iterates are uniformly bounded deterministically (with a non-vacuous upper bound). This complicates the analysis significantly since cach of the terms in the R.H.S. of our main recursion in Lemma are dlerale-dependen and cannot just be replaced by uniformly bounded perturbations (as is possible in a tabular setting).
Comparison with heterogeneous federated RL/SA papers. The only two papers we know of that consider finite-time analysis of heterogeneous FRL algorithms under function approximation are Zhang et al. (2024) and Wang et al. (2024b). Our analysis departs from both these papers in two main ways. First, as we explained carlier in our paper, Zhang et al. (2024) and Wang et al. (2024b) study FedAvg-style algorithms where each agent uses just its own local operator to update model parameters between communication rounds. As we show in Proposition 1, such algorithms converge to incorrect fixed points. In contrast, we study
12

---

Published in Transactions on Machine Learning Research (01/2026)
(1)
0
1
Agent
(0)
(0)
(0)
(1)
20
2.H-1
0,0
(
Agent 2
020
10
2.81
0,
2.1
(0)
000
M
1600
Agent M
M
[00
(1)
M.0
(1
Figure 1: Illustration of the different statistical correlations in our heterogeneous lederated SA setting.
different algorithm altogether, the dynamics of which are not the same as the ones in Zhang et al. (2024) and Wang et al. (2024b).
On more technical note, both Zhang al. (2024) and Wang et al. (2024b) consider a projection step in their algorithm to ensure that the iterates remain uniformly bounded. This considerably simplifies the analysis since the Markovian bias term is seraate-dppnddnnt and projection ensures that such a term is essentially a uniformly bounded perturbation. In sharp contrast, we make no such assumption of a projection step, and, as such, we do not have the luxury of a uniformly bounded Markovian bias. Thus, a much finer analysis relative to Zhang et al. (2024) and Wang et al. (2024b) is needed to control each of the iterate-dependent "error" terms on the R.H.S. of our main one-step recursion in Lemma 4 (established in Appendix C). In addition, our proof also requires establishing that no heterogeneity-induese bias shows up in our final bound (unlike Zhang et al. (2024) and Wang et al. (2024b)).
Comparison with single-agent RL/SA papers. Although Markovian sampling has been studied in single-agent RL/SA, there are considerable challenges in extending such results to our specific setting. As illustrated in Figure 1, our analysis has to account for two types of data correlations: (i) temporal correlations in the data for any given agent, and (ii) correlations induced by exchanging data across agents. For each agent i, the (t) observation oiee is statistically dependent on all prior observations for itself since they are all part of single Markovian trajectory. Such an issue does not arise in the standard FL setting where one assumes i.i.d. data over time. Additionally, the local parameter 0f2 is jointly influenced by all the parameters of all agents up to the beginning of round t, due to communication. Finally, all such parameters inherit randomness from prior Markovian observations. In short, combining information generated by heterogeneous Markov chains creates complez spatial and temporal correlations.
Moreover, relative to single-agent RL papers, we need to establish a finer result involving the linear speedup effect. To achieve this, we need to show that the Markovian bias term can be upper-bounded by terms that are either higher-order in the step-size or scaled down by the number of agents. This is the hardest part of our analysis, and to our knowledge, other paper in FRL has been able to establish such a result without making simplifying assumptions of projection steps.
Comparison with Mangold et al. (2024). In our discussion on more related work in Section 1, we have already explained why the nonlincarity of operators in our setting prechudes the approach pursued in the work of Mangold et al. (2024). There is one other crucial difference with this work. In Mangold et al. (2024), the bias-corrected algorithm used for lincar SA is studied only under i..d. sampling: thus, our work is the first to analyze the effects of control variates under Markov sampling. For vanilla SA, the approach in Mangold et al. (2024) to control Markov sampling is the "blocking technique", where one simply discards several data points by sub-sampling. By coupling argument, the analysis then boils down to that for i.dd. sampling. In sharp contrast, our approach does not discard any data points, making the Markovian analysis significantly more challenging since the samples used to generate iterates are temporally correlated.
Summary. To sum up, our discussion above highlights that no prior analysis is enough to subsume the specific challenges that arise in our setting from a combination of function approximation, nonlinear operators with heterogeneous roots, the lack of projection steps, and the need to establish linear speedup
13

---

Published in Transactions on Machine Learning Research (01/2026)
effect despite complex correlations. As such, we believe that the analysis framework developed in our paper can serve as template for reasoning about more involved complex SA/RI, schemes in the future.
Note. For notational simplicity, we omit the observation variable in the operator in subsequent analysis when the time-index of the observation matches with that of the parameter, i.c., we use the shorthand G.( i,:: (.) == C,(((2). The observation variable is made explicit only when its time-index differs from that of the associated parameter.
Proof Sketch. We now provide a high-level technical overview of our analysis; the details are deferred to Appendix C. Our first step is to establish a one-step recursion that captures the progress made by FedHSA in each communication round (Lemmna 4 in Appendix C). Up a higher order term in a, the R.H.S. of this recursion comprises four terms: "good" term that leads to contraction in the mean-square error, "noise variance" term that gets scaled down by M, "drift" term due to heterogeneity, and a bias term due to Markov sampling. The challenging part of this result is showing the variance-reduction effect under Markov sampling; to do so, we carefully exploit the geometric mixing properties of the agents' Markov chains and Assumption 4.
Next, to control the drift effect due to heterogencity, we show in Lemma (in Appendix A) that n S 1/(H), then the following is true deterministicaall::
0+ |002 - = -010) +02 (
To build intuition, notice that when there no noise, i.e., 0 a= 0, if ((0) 0", meaning the iterate at the start of the round is at the desired value, there would be client-drift at all, precisely desired. The most challenging part of our analysis pertains to controlling Markovian bias term of the following form:
Thias =: E [((000
-
0r,
20
Σ
M H-1 Σ 2=
((l0)))-((0)) ))
MH
that arises due to temporal correlations in data. Such a term vanishes in the standard FI. setting where one assumes i.idd. data, In the heterogeneous FRL setting in Wang et al. (2024b) and Zhang et al. (2024), such a term is simplified by assuming a projection step. Since we do not assume a projection step FedHSA, we cannot benefit from such simplifications. Nonetheless, we establish the following key result.
Claim (Informal). (Markovian Bias Control). Under the conditions of Theorem 2, we have:
ap +0 +0(TL'd (LL'a+ + Lta3)
P )) E 800 0 0112] +0 ( (L' FL'o2a?
Thias
+ MH(1-
11
A formal version of this claim appears as Lemma 6 in Appendix C. For the Markovian sampling result to closely resemble the i.i.d. case, we need to crucially ensure that (i) the iterate-dependent term in the bias can be dominated by the contractive "good" term, and (ii) the noise terms are either O(a²), or O(2//M, i.e. the noise terms need to be either higher-order in a or exhibit an inverse scaling with Ad, to preserve the linear speedup effect. In the single-agent case (Bhandari et al., 2018; Srikant & Ying, 2019), one need not worry about linear speedups, and, as such, the corresponding analysis is much less involved. In summary, to arrive at our desired bounds, we need to significantly generalize known analysis techniques for both single- and multi-agent SA under Markov sampling.
6 Conclusion
We studied a general lederated stochastic approximation problem subject to heterogeneily in the agents' local operators, and temporally correlated Markovian data at each agent. For this setting, we first showed that standard local SA algorithms may fail to converge to the right point. Based on this observation, we developod a new class of heterogeneity-awann federated SA algorithms that simultancously (i) guarantee convergence the right point while matching centralized rates, and (ii) enjoy linear speedups in sample-complexity that.
14

---

Published in Transactions on Machine Learning Research (01/2026)
are not degraded by the presence of an additive eeterogeneityy-ndueee bias term. Our results subsume the standard federated optimization setting and have implications for a broad class of SA-based RL algorithms. There are various interesting questions that we plan to explore in the future:
One natural question is to ask how much communication is necessarily needed to achieve optimal speedups sample-complextty?
2. At the moment, our bounds scale with the mixing time of the slowest mixing Markov chain among the agents. Can this bound be further refined?
3. Can the techniques developed in this paper be employed for more complex SA-based RL algorithms with nonlinear function approximators? The extension to two-time-scale algorithms is also of interest.
In our analysis, we leveraged the "strong- monotonicity' condition in Assumption to obtain con- tractive terms that led to overall progress towards the desired point in cach iteration. However, in the context of say stochastic non-convex optimization, such an assumption may not hold. It is an interesting direction (even in the single-agent) case to explore the relaxation of Assumption 2 under Markov sampling, without making further simplifying assumptions such a PL condition projection steps or bounded gradients.
References
Arman Adibi, Nicolò Dal Fabbro, Luca Schenato, Sanjeev Kulkarni, H Vincent Poor, George J Pappas, Hamed Hassani, and Aritra Mitra. Stochastic approximation with delayed updates: Finite-time rates under markovian sampling. In International Conference on Artificial Intelligence and Statistics, pp. 2746-2754. PMLR, 2024.
Ali Beikmohammadii Sarit Khirirat, and Sindri Magnússon. Compressed federated reinforcement learning with a generative model. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 20-37. Springer, 2024.
Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. In Advances in Neural Information Processing Systems, volume 36, 2024.
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
Keith Bonawitz, Hubert Eichner, Wollgang Grieskamp, Damitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arxiv preprint 192.0000, 2019.
Vivek S Borkar. Stochastic approrimation: dynamical systems viewpoint, volume 48. Springer, 2009.
Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447 469, 2000.
Zachary Charles and Jakub Konečný. Convergence and accuracy trade-offs in federated learning and meta- learning. In International Conference on Artificial Intelligence and Statistics, pp. 2583. PMLR, 2021.
Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke. Performance of Q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprint 1725 pp. 4, 2019. Lemma 3.1.
Zaiwei Chen, Sheng Zhang, Thinh T Doan, John-Paul Clarke, and Siva Thoja Maguluri. Finito-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning. Automatica, 146:1 10623,, 2022.
15

---

Published in Transactions on Machine Learning Research (01/2026)
Nicolò Dal Fabbro, Aritra Mitra, and George J Pappas. Federated TD learning over finite-rate erasure channels: Linear speedup under markovian sampling. IEEE Control Systems Letters, 7:2461 24666, 2023.
Nicolò Dal Fabbro, Aritra Mitra, Robert W Heath, Luca Schenato, and George J Pappas. Finite-time analysis of over-the-air federated td learning. IEEE Transactions on Wireless Communications, 2025.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine PMTR, 2019.
Learning, pp.
Thinh T Doan. Finite-time analysis of markov gradient descent. IEEE Transoctions Automatic Control, 2022.
Thinh T Doan. Finite-time convergence rates of distributed local stochastic approximation. Automatico, 158: 111294, 2023.
John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael Jordan. Ergodic mirror descent. STAM Journal on Optimization, 22(4):1549 1578, 2012.
Alain Durmus, Eric Moulines, Alexcy Naumov, and Sergey Samsonov. Finito-time high-probability bounds for polyak-ruppers averaged iterates of linear stochastic approximation. Mathemotics of Operations Research, 50(2):935-966 964, 2025.
Mathieu Even. Stochastic gradient descent under markovian sampling schemes. In International Conference on Machine Learning, pp. 9412-9439. PMLR, 2023.
Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low. Fault- tolerant federated reinforcement learning with theoretical guarantee. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 1007 1021. Curran Associates, Inc., 2021.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Inlelligence and Statistics, pp. 3556 3564. PMLR, 2021.
Adam Wierman Guannan Qu. Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Proceedings of Machine Learning Research, volume 125, pp. 1 21. Kluwer Academic Publisher, 2020.
Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with enviromment heterogeneity. In International Conference on Arlificiol Intelligence and Statistics, pp. 18 37. PMLR, 2022.
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. 5182-5143. PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519 4529. PMLR, 2020.
Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J Wainwright, and Michael I Jordan. Is temporal difference learning optimal? an instance-dependen analysis. Xiv preprint ar arXin:2003.07333 07337, 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. 10997 11057. PMLR, 2022.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Foderated optimization: Distributed machine learning for on-device intelligence. ar Xiu preprint ar 161iv:1600.00 0.02277, 2016.
16

---

Published in Transactions on Machine Learning Research (01/2026)
Guangchen Lan, Han Wang, James Anderson, Christopher Brinton, and Vaneet Aggarwal. Improved communication efficiency in federated natural policy gradient via ADMM-based gradient updates. arXiv preprint Xie:23300. 19807, 2023.
David A Levin and Yuval Peres Morkow chains and mixing times, volume 107. American Mathematical Soc., 2017.
Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejie Chi. Is Q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 72(1):222-2366 2024.
Xiang Li, Kaixnan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. orXiv preprinl 107::097,,0219,, 2019.
Rui Liu and Alex Olshevsky. Distributed TD (0) with almost communication. IEEE Control Systems Lellers, 7:2892 -2289222897, 2023.
Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local SGD to local fixed-point methods for federated learning. In International Conference on Machine Learning, pp. 6692-6701. PMLR, 2020.
Paul Mangold, Sergey Samsonov, Safwan Labbi, Ilya Levin, Reda Alami, Alexcy Naumov, and Eric Moulines. Scafflsa: Taming heterogeneity federated linear stochastic approximation and td learning. Advances in Neural Information Processing Systems, 2024.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicttion efficient. learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp- 1273 1282. PMLR, 2017.
Sean Meyn. Stability of Q-lcarning through design and optimism. arXiv preprint arXim:2307.02633 2023.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárík. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference on Machine Learning, pp. 15750-15769. PMLR, 2022.
Aritra Mitra. A simple finito-time analysis of td learning with linear function approximation. 1EEE Transactions on Aulomalic Control, 2024.
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34: 14606-14619, 2021.
Aritra Mitra, George J Pappas, and Hamed Hassani. Temporal difference learning with compressed updates: Error-feedback meets reinforcement learning. Transactions on Machine Learning Research, 2024.
Dhecraj Nagaraj, Xian Wu, Guy Bresler, Pratock Jain, and Pranccth Netrapalli. Least squares regression with markovian data: Fundamental limits and algorithms. In Advances in Neural Information Processing Systems, volume 33, pp. 16666-16676, 2020.
Reese Pathak and Martin Wainwright. Fedsplit: An algorithmic framework for fast federated optimization. arXiv preprint Xrx::2000. 05238, 2020.
Jijju Qi, Qihao Zhou, Lei Lei, and Kan Zheng, Federated reinforcement learning: techniques, applications, and open challenges. arXiv preprint arXiv:2108. 11887, 2021.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pp. 400 407, 1951
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheor, Amoct Talwalkar, and Virginia Smith. On the convergence of federated optimization in heterogencous networks. arXiv preprint arXhv:1812.06123 3, 2018.
17

---

Published in Transactions on Machine Learning Research (01/2026)
Sudeep Salgia and Yuejie Chi. The sumpl-communication complexity trade-off in federated q-learning. In Advances in Newral Information Processing Systems, 2024.
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEFE Transactions Signal Processing, 2023.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Conference on Learning Theory, pp. 2803 2830. PMLR, 2019.
Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. In Advances in Newral Information Processing Systems, volume 31, 2018.
Haoxing Tian, loannis Ch Paschalidis, and Alex Olshevsky, One-shot averaging for distributed TD (A) under markov sampling. IEEE Control Systems Letters, 2024.
John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approxi- mation. In JEEE Transactions on Aulomatic Coutrol, 1997.
Stephen Tu and Benjamin Recht. Least-squares temporal difference learning for the linear quadratic regulator. PMLR, 2018.
International Conference on Machine Learning, pp.
Martin J Wainwright. Stochastic approsimation with cono-contractive operators: Sharp loo -ounds for Q
-learning. arXiv preprint ar Kkt::195500266, 2019.
Han Wang, Sihong He, Zhili Zhang, Fei Miao, and James Anderson. Momentum for the win: Collaborative federated reinforcement learning across heterogeneous environments, In International Conference on Machine Learning. PMLR, 2024a.
Han Wang, Aritra Mitra, Hamed Hassani, George J Pappas, and James Anderson. Federated temporal difference learning with linear function approximation under environmental heterogeneity. Transactions on Machine Learning Research, 2024b.
Jiin Woo, Gauri Joshi, and Yuejie Chi. The blessing of heterogeneity in federated Q-learning: Linear speedup and beyond. In International Conference on Machine Learning, pp. 37157-37216 PMLR, 2023.
Zhijie Xie and Shenghui Song. Fedkl: Tackling data heterogeneity in federated reinforcement learning by penalizing kl divergence. IEEE Journal on Selected Areas in Communications, 41(4):1227-1222, 2023.
Sihan Zeng, Thinh Doan, and Justin Romberg. Finite-time convergence rates of decentralized stochastic approximation with applications in multi-agent and multi-task learning. JEEE Transactions on Automatic Control, 2022.
Chenyu Zhang, Han Wang, Aritra Mitra, and James Auderson. Finite-time aualysis of ou-policy heterogeneous federated reinforcement learning. In International Conference on Learning Representations, 2024.
Feng Zhu, Robert W Heath, and Aritra Mitra. Towards fast rates for federated and multi-task reinforcement learning. In 2024 IEEE 63rd Conference on Decision and Control (CDC), pp. 2658 2663. IEEE, 2024.
18

---

Published in Transactions on Machine Learning Research (01/2026)
A
Basic Results
In this section, will compile some known facts and derive certain preliminary results that will play key role in our subsequent analysis of FedHSA. Before proceed, for the reader's 8 convenience, assemble all relevant notation in Table 2.
Table 2: Notation
Notation
Definition
[N]
The set of N numbers from to N
M,
Markov chain of agent
S,
Rd
Common finite stale space of agents' Markov chains, and d-dimensional real space Instance of state
s
Or ii
(0)
Observation of agent i at time-step and observation of agent i in local iteration & of round t
P4
stationary distribution of M,
drv
Total variation distance Global parameter at round and local parameter of agent in local iteration & of round
g0, 8
G G
Noisy and true local operators of agent i Noisy and true global operators
G,G
800
Root of global operator G(0), and root of local operator (,(0) of agent i Parameters capturing the effect of noise, with = max aas)
0,.
PaP
Parameters capturing the mixing-time time property, with p = max(p1. ,Pa) Lipschitz constant and strong-monotonicity constant
L
7, a a
Local step-size, global step-size, and effective step-size
O,0
Big-O notation hiding universal constants, and big-O notation hiding poly-logarithmic terms
T.
Functions capturing the mixing time and the slowest mixing time defined as F == r(a?)
F(0
Filtration containing all randomness prior to round t and local iteration across all agents
Given m vectors (-i,--. 3m) Rd Rd, the following holds true by simple application of Jensen's inequality:
Σ X2
< m
(15)
Given m vectors (#1,"",,0 Rm) E Rd x ... x Rd. the following is generalization of the triangle inequality:
|xl|22
(16)
1=1
Given any two vectors (x, y) E IRdd x Red, the following holds for any & > 0:
(x, v)
|
(17)
2
Proof of Proposition 1 We first provide the proof Proposition 1. Before we start, recall from Section that the local update formula
((0) 000 (0 E= 0, H 1,
(18)
19

---

Published in Transactions on Machine Learning Research (01/2026)
where G:(0) A,0 - b, and H = 2. Also recall that the aggregation formula at the server is
0(++1
Σ
0
(19)
M
M
Proof. By definition of G;, we can write
o(0) i,841 = 0 + 11 (A.0 b,)
(I nAi) 0 ni;
(20)
= (I + nA,)) (0!1) 0-) + + + 17 (A,0' - -b:),
which yields
( 1.41 0" = (T + nA.) (0.0) 0+) + +1 (A,00" -b.)
(21)
Tterating Eq- (21) for H = 2 steps, we obtain
0 - = (1+ ( - 8*) + (I (I + nAi)) (A,0* - -b.).
(22)
Therefore, by Eq. (19) and the fact that 0 g(t) we have
g(++1) -0" 1
(I nA,) (B (0))
0r) +
1 M
Σ
(2I nAi) (A,0* - -bi) 5.))
(23)
M
M
i=1
E=1
Using the fact that Ao b= and b. A,0;, we have
M
" M
(T + n1) (A,00 - b.) =
Σ (A² (0) -;))
(24)
M
M
A Also, we have
(T (T+1A))2
M Σ
1
(T (T+ 2n + +
M
(25)
i=1
= 24 1
where recall that A = (1/M) Eie(M] A, and A'= -1/M) Σ ΣiE[M] A?. Now, defining e g()) 8", and combining Eq. (23) Eq. (25), we obtain
et+1 Fe, + 8, Vt 0,
(26)
where F= T= T 2 + 2 and ū= (1//M)> (A) (0 - 0;)). We then conclude that Eq. (26) represents a linear dynamical system in discrete time with state transition matrix
For stability, we need be Schur-stable, Suppose n is chosen ensure that F Schur-stable. Now, applying (26) iteratively yields
e, = Fteo
Σ pk B.
(27)
Taking limits on both sides and using the fact that F is Schur-stable, we obtain
H
lim F' cv = 0,
lim t-000
Σ
Fb = (I
-I-F)-+ (2A + nA7
(28)
(-000
k=0
20

---

Published in Transactions on Machine Learning Research (01/2026)
Therefore,
M Σ
lim e, 400
71 (2A (2A+nA)) -1
(4) (0; 8*))
(29)
M
We have thus proved that the error e, is non-vanishing.
The following corollary will come in handy at several points in our analysis.
Corollary 2. Given Assumption 1, for any given 8, o, the following holds for all e [M]:
GG((0, - G < o (L) (10- 0- +
|G:(0,0)]22 5 0 (L) (10- -0 +o) ||0(00]]2 0 (L) (10- - 0- +o)
(30)
Proof.
(G)(0,))-G(((]]] < [0, o)||2 + ||):
- 2T (1001 +
(31)
= 2L (110 - 8'112 + 11 + o)
s 2L (110 (10-- + 22)
Here, the second inequality follows from (5), and the last inequality uses the definition of a. The rest two bounds can be obtained similarly.
We also state upfront the following lemma that bounds the drift term |0 8(0) holds deterministically, i.e., applies to both i.ddd and Markovian sampling. Lemma 1. Suppose Assumptions and 9 hold. By selecting n s 1|LHH, the following is true for FedHSA:
| 12" Notably, this result
|0.00 - 0001
-0000001 =0] 21P (100) - 0r 0²( + +0²
(32)
Proof of Lemma 1.
Proof. A high-level intuition for proving this lemma is to use the update rule of FedHSA in tandem with
Corollary 2 to obtain a recursion for the term |0 Ø(0 || With that aim in mind, from (10) we can write
|0.2 g())
|002
Φ(0) + (. +((0)))GGG))))))) C,(6 |
1002
g()
+ n (
(B (1)) + (7)((((t) + 1,000 -y, 100
00 000
+ 1 (c.(0()) (27 (010,
/1 + (01111 + t 0 G G
2
1002
0011
+ Tz. lo!2 - g())
2 + +1|1c0000 || + /|00,1000 1.9011 + (0 0.0
2
(1 mD)
800|, +O(LL) (11000 (1100- 00|1 +o)
-
(33)
where the in the second last inequality used Assumption 1, and the last inequality follows from Corollary 2. Applying (33) iteratively, we obtain
8-1
|0.0 500 < <1 + nD) 1000 - 0001/
+ Σ
(1 + (L)) (1 - 001/111 + +o)
-0000
1=
H(1 (L)))
(1
0- +0)
(34)
< O(nhH) (1/00) 0+
+ +o)
21

---

Published in Transactions on Machine Learning Research (01/2026)
Here, the second inequality holds because 0g00 g(0) and L S H. The last one follows by choosing 1/ S (LH), and thus (11 + n1) ((()) & (1 + 1/H1" O (TLH) v (nLH),, where in the last inequality we used (1 + 1/x)* s e, Vo > Squaring both sides of (34) yields the final form of Lemma
Lemma 1 states that if we select 0g and Hog? we then bound the drift term | ((+) in the form of the squared norm of the distance of the global iterate to the global root plus the effect of noise, damped by the factor a².
22

---

Published in Transactions on Machine Learning Research (01/2026)
B Analysis of FedHSA under I.I.D. Sampling
We begin analysis of the FedHSA algorithm's convergence by examining its performance in simplified L..dd scenario. Specifically, we assume that for each agent i E [M], its observation Oir at time step & is drawn in an i.id. manner from its stationary distribution μ4, Our analysis of the i..d. setting will provide a foundational understanding the finite-time behavior of FedHSA. In turn, will offer a smoother transition to the more complex case of Markovian sampling.
For our subsequent analysis, we remind the reader again of the shorthand G:(0 6,87 (.. = G:( used whenever the observation variable and the parameter share the same time-index.
We start by introducing the following lemma, which provides a recursion for the progress towards #* made by FedHSA in each communication round.
Lemma 2. Suppose Assumption 3 and 4 hold. Also, suppose the data samples of each agent i [M] are drawn i.idd from the stationary distribution hr of its underbying Markou chain M,. Then, the following holds for FedHSA Vt 2 0:
E pott
10 -0-1
1 <(1 op + O (x) E
7 0=1 + O
1222202 MH
2
(35)
+ 40
al? a²
M H-1
|1000 - 0cc3 1/
E
pMH
MH
:=1 2=
Proof. From the update rule of FedHSA in Eq. (11) and the definition of G(O(t)), we obtain
M
H-1
((++) g(t)
ag
(,((0()) - G,(0'() -C(00))) (000 + G(O
M
(36)
M H-1
Σ (0
M
Using the definition of the elfective step-size = Hioogg we can then write the squared norm of the distance of the global iterate to the optimum 8* as
M H-1
| - 0-|²- 2
g(t) +
a MH
Σ Σ
G((
1=1 1=
T
T2
(37)
M
Ø-1
= =1|00) 0011?
g(t) 8+,
2a
G.(0!!) 1.0
Σ
MH
MH
i=1
t=
2
23

---

Published in Transactions on Machine Learning Research (01/2026)
To bound this equation in expectation, it then boils down to bounding the expectations of the terms T₃ and T2 separately. We proceed to do this next.
M
H-I
C.(0! )
E 71
(a)
20B
0r, ((0)
1
MH
2aL
((0) 0
1
(G.(0 -,(0())) -
2aB
git) ((it- 0",
MH Σ Σ C,(0 )
1 H-1
MH
M #-1
2aE
O 0r
(: - G:(0(0)) -c.(0))))))))))))
+ 2aBB (000) - 0" G(
MH
20
H-1
E [000 - 0-, G.() {.(0(0))]] -2aulE
(0:0-0'1 0+ -0000-0011
10-00-001
MH
H-1
Σ
|
p(1) 8+
0x| + (0(0)) - G,(010)11
20qulB
|10ce 8+1
MH
M H-
Σ
E
[000)
0+
||
+
L2
(00))
i,
00011- - 2ahB
|1000- 1010--0112 00-1/2]
MH
1
i=1
t=
=apll
|00
0r
$120
+
aL?
E
(0())
g(0)
1
HMH
(38)
where (b) follows from Assumption 2; (c) result of Assumption 1. Before we proceed, we define
F(())
as the r-algebra capturing all the randomness up to the f-th local iteration of round Building on this definition, we reason about (a) separately as follows:
M
H-1
B 2&E
(10) 0",
1
Σ
Σ
MH
i=1
M
H-2 ()
)
M
2aE
g(0) 0"
Σ
Σ
+ 2aE
g(0) 0"
Σ
(
MH
MH
1=1
0=
i=1
R-2
G((0 )
20F
((0) 0+
MH Σ
Σ
+ 2aEE
E g
0
F
MH
M
H-2
M
(a2)
2n
g 0*
Σ
Σ
G.
+ 2nE
g(0) 0+
G.(((() ( |
MH
MH
1=1
i=1
M H-2
)
M
(a3)
20F
T10)
0-
Σ
Σ
G.O0
+ 2
gOL) 0*
Σ
MH
MH 1=1
1=1
E=0
(39)
Here, (al) follows from the tower property of expectations; (a2) holds from the fact that ((t) is deterministic conditioned f(()) H- and (a3) is a result of the i.i.d. assumption in tandem with the fact that 0(00)
11 is
deterministic conditioned on FH-2 We can repeat this process by iteratively conditioning on FH-3..... z(0) and arrive at. (a), where F(() all the randomness up round t before any local steps are taken.
24

---

Published in Transactions on Machine Learning Research (01/2026)
We now move on to bound the expectation of T2.
M 8-1
M H-1
T E E
(: C:(O!))) + MH
G
MH
t=
M H-1
M H Σ
< 2F
Σ
(G(0 - -.(0
+ 2
1
G (00)
MH
MH
i=1 2=
1=1
8=
(a)
S 2F
1
M
H
(.00%) C.(0!!))
M
t=1 8=
M H-1
Ø-1
+ 2
(2,(0 C,(0()))
1
ΣV Σ
(00))
MH t=
MH
1=1 t=
(6)
M H-1
(109) - 8-
M Ø-1
2B
Σ
(
+ 02)
+ 4a
Σ
(,(0!!) - -,(010)
2
MH
8=
2=
M Ø-1 Σ
[]
+ "
Σ
(00)))
MH i=1 t=
2O.FR
Σ
M H-1
Σ
0113) (1022-01011 - -010
+ | 0-11 + o²
M 1=1
t=0
4a²
H-1 Σ
E
-C,(01))
+ 4a2E
||aT !
MH
2a²
Σ
M H
E
[1002 - 8000
+ |0100 00112 + 022)
2,2
ΣΣ
M Ø-1
| 0000
M
-
MH
1=1 1=
i=
F=
L + 4a
||000
0
a²I.
a²I22
M
E |1000 - 000
+0 0a00200 222
a²
E [100)-0111
(
L22
00
+0
M2
MH
MH
MH
0
a21?
ΣΣ
M 1-1
E
00
100 [|3
g00)
|lw
0+ 2
2 +
TTT222
MH
MH
(40)
where (b) uses Corollary 2, and (c) is result of Assumption
1. We provide the rationale behind (a) as follows.
25

---

Published in Transactions on Machine Learning Research (01/2026)
The second term in incquality (a) is direct result of add-and-subbract. To inspect the first term, note that
M H-1
E
E
M H
G( -G
!
Σ
M
Σ
(G -G Gy( -
j=1 mcn
H-1
(m)) 6, (o
Gn (o km)
jKh
Σ
E
(c
(mm C,(0g,m) , Gx((
JKh m<n
M #-1
M
E
Σ
+ +2 (. 11
Σ j=lm<n m<n
E E
-5 -1:0 - |
G, ()
G,(0 GN Gn((
(m(( )) | m- ]]
jek
( C,(0 Gx( (=(( |
E
E
jck m
M H
--(0 G.(0
= E
(41)
where the first equality holds from unrolling the squared norm, and the second equality follows from the tower property of expectation. We analyze the terms separately in the last equality.
For the first cross-term, we can write
M
Σ
[
[ -100))) (
E
(G,
j=1 mnn
M
(42)
Σ
-G,10))
()((((h) -
jmm
i=1
mcn
0.
The first inequality holds from the definition of F(") The second one holds because g is deterministic j.n conditioned on r(t) and the only randomness comes from ofth Gy Due to the i.id. sampling assumption, we readily know that E [_,( C,(ofh)) for a fixed e(t) inn and the cross-term then equals 0.
For the second cross-lerm, we can write
#-
- GA (A Gn(( [= ]]
2
E
E
j.m
k 0==0
(
21 1 Σ
E
E
J.m m-
[1(
] E
kk m- |>]
(e) [(()
(43)
j< mm 0
18)
0,
where we define (1) - conditioned on F(t)_ So, due to Assumption 4, j and (t) used the i.i.d. sampling assumption.
-((
For (i), we used the fact that of and o are deterministic
km are conditionally independent. For (it), we
26

---

Published in Transactions on Machine Learning Research (01/2026)
The third cross-term can be proved to be 0 similarly as for the second one.
Taking expectation on both sides of (37), and plugging in the bounds from (38) and (40), we obtain:
E 0l0+)) - 0. 11] 1 (1 ap + 10 La2
000 0* 1
E
DRIPT
(44)
aL?
d²L² +
M
H
2
a²'L'²²
000) -B())
+
E
+0
HMH
MH
MH
1=1 8=0
The proof of Lemma 2 is then complete.
Lemma 2 breaks the bounding of the recursion E -010 into three parts: (i) the "good term"
(1 (1-ap a-a (z)) E [|00 0* 01]] where we can select small enough such that O (a2t.3) can be absorbed by the iveative term aa,, ensuring that the distance to the optimum 0* decreases; (ii) the effect of noise O (a² (MMH)) which demonstrates the benefit of collaboration (since it gets scaled down by M), and (iii) the drift term DRIFT that accounts for the client drift caused by environmental heterogeneity and local steps. We can further bound this term by plugging in Lemma 1, and arrive the following result of Theorem 1.
Proof of Theorem 1.
Proof. Plugging the bound from Lemma into the bound from Lemma 2, we obtain:
E p
001?]] < (1 11-aut+ -appp+000 000 E
g(t) or
+ 0
a T2200
2
MH
+0 (
al? a²L?)
MHa?1?
(F.
( 0+
[2]
+
WMH
MH
(a²T.t)
)) E
ap + 10 (2² + +0(''(') +0
((0)
8+
(45)
( (aoL'2
MH + a L02 +a"
+0
Q²1,
a3T
$ (a E
[(0) gr
+
+
02.
MH
P
Here, the first inequality follows from the definition of a = Hnog The last one is a result of the fact that a S m/L2, 2 1, μ S 1, such that L S a²LL, a La μ < L², and a LA2 S L
Applying Eq. (45) iteratively T times yields
E | 10m-00'1
1-10 19 < (1-
0r
ap T
[00]-
0"
+ 0
a
T-1
2
MH
P
2
1=0
Q2L2
L 20
atl T
|0000 0"
(46)
S exp
0
2
MH
11
01p1
aT?
a 02.
$ exp
(0(0)
0r
0
PMH
n²
Here, the first incquality holds since a S (2CC) where C' is the dominant constant in O (a²1z), and thus Ca²L² < 22.22. The second inequality holds from the fact that 1 - x S exp (-+). The proof then complete.
Thus far, we have demonstratod that by selecting a small enough so that the term a² L /p² is subsumed by aT. H), Theorem 1 mirrors the result of the single-agent case in Eq. (3) under i.i.d.
27

---

Published in Transactions on Machine Learning Research (01/2026)
sampling. Additionally, it is important to highlight that a linear speedup is achieved, i.., the variance term, ar.202/(uMMT) is reduced in proportion to the number of agents M, further underscoring the benefits of collaboration in a multi-agent setting.
28

---

Published in Transactions on Machine Learning Research (01/2026)
C Analysis of FedHSA under Markovian Sampling
Now, we shift our focus to the central result of our analysis: the convergence of the FedHSA algorithm under Markovian sampling. In this scenario, the observations (or,) for each agent i E [M] are temporally correlated, as opposed to being statistically independent. This introduces additional complexity to the analysis, as we must account for the intricate interactions between observations across different time steps and among various agents.
Building upon the geometric mixing time property, we present the following corollary to deal with time- correlation in observations.
Corollary 3. For each agent E [M], any given E Rd, and any non-negative integers T, satisfyying r s k the following holds:
E (0, o1,k) - S (LP)) (110 0 o))
(47)
where 0i, is the obsercalion made by agent at the k-th lime-slep.
We refer the reader to Lemma 3.1 of (Chen et al., 2019) for proof.
Corollary 3 states that given fixed parameter 8, the difference in the Enclidean norm ||-1|2 between the true operator and the expectation of the noisy operator, conditioned on the observation from 7 time-steps before, decays exponentially fast, where the ||0 0 ll term captures the influence of 0. Corollary 3 is particularly useful for addressing the temporal correlation between observations. Specifically, when observations are sampled i.i.d. from the distribution p4a the left-hand side of (47) equals zero, recovering the relationship between G; and G.-
Before delving into the details of the proofs, we first introduce the following lemma that bounds the variance reduction term in the Markovian sampling scenario.
Lemma 3. Suppose Assumptions 1 to 4 hold. Then the following holds for FedHSA Vt 2 7, where 7 = =(a2).
V Ratarkov
M Ø-1
Σ
(G(00()- ( -c,00))
5
12222
H Σ
M
E
10.0 g(t) [2]
MH
MH
2
E=
1=
(48)
||000 -011
0 (I'a²)
E
+ +0
L2a302
+
MH(1
Proof. Note here that we can no longer bound it we did in the i.i.d. case due to the presence of Markovian sampling, where data samples for each agent are temporally correlated rather than independent. To handle this, we take advantage of Corollary 3 to address the time correlation. We thus bound V RMMako as follows.
M H-1
V RMMrrov = 2
G (:000-0)--01000--0000--000000000
-,(0- -000)
MH
A
A2
8-1
Ø-1
< $
1
G. (.0 (000))(()))
+ +
1
(,00% - -.(00))
MH
MH
1=1 t=
t=
M 1
+ 66 2E
(,(0(()) (20) G (1)
MH
t
(49)
29

---

Published in Transactions on Machine Learning Research (01/2026)
We proceed to bound A₂
17
M
H-1
A2
0000
Σ 1=
E
10 0- 0-12
MH
L?a?
Ø-1 1F
1099 -
L
M H
0+ 1-1
0
+0
E
(50)
MH
MH
M #-1 Σ
E
(0 800)
+ +0(L'a²) E
(L'a²)
g(t) - 1-1
MH
where we used Assumption 1. We can obtain the same bound for A3 with the same reasoning.
Now we continue to bound the term A1. With a slight overload of notation, denote e, = G,(0r,00) G,( and we obtain
a²
H-1
=
A1
E
C
M2
B;
Ba
a
M
H1
a²
=0
E
|levell]
+0
E Kere, e,,e
(51)
H2
M2H2
E f1
Bs
a²
a² M2
+
Beee ex+)+
Σ
Σ
E leeiers ejaa)).
M2
1
8=
Ex
We then bound the four terms separately. For the term B1, we have
Bi 500
a²
E
G: 0
+|
+|G,(00))
M2
(52)
1222022
< 0
MH
where we used Corollary 2.
30

---

Published in Transactions on Machine Learning Research (01/2026)
For the term B2, we have
B2
(a)
a
Σ
M
Σ
E
E (eser cxed (.02) ]]
M
H
i=1
f f1
a²
M
IR (eiss TE [(csslof2]) ]
0
M
0
a²
M
I |lese lla
B [ersslo22
M
E Eigll2
La²
M H-1
Σ
p² 10
o1 [llera 1121
M
t=1 E
(53)
La²
M H
Σ
OF
oF
c|, ;0( (2) 1/ + +|[G((0)]])]
M
1=1 01
12a22
H-1
Σ
02
2200 M
L'aF02
M H-1
00
ΣΣ
(1+ p +2...... +...)
M2H2
i=1 4=
L2'2002
0
MH(1-p))
where we used the tower property of expectation in (a), Corollary 3 in (b), and Corollary 2 in (c).
For the term B3, we have
(a)
a²
H
B3
O
(E [ec,e,, E [eg,e])
M2
a²
H
<
|| [es,ell [e
M2
a²
| [E [e, [B,ee,oo,..ttt-ll [EBle
M2
(54)
a²
H-1
E [[B[ecnloouu4+++=]]]]] (1
M2
iイj t=
L'a²
H 1 Σ
Σ
2 0²
2
igj
12 H
where (a) is result of Assumption 4, (b) uses the tower property of expectation, (c) uses the fact that ||B [x]]]|| < E 2||= (d) is the application of Corollary 3, and (e) uses the definition that p² saa Note here that we are allowed to condition on 7 time-steps before because t 2 F.
Similarly, we can achiove the bound for B1 as
B4 5 00
(55)
31

---

Published in Transactions on Machine Learning Research (01/2026)
Further plugging the bounds for B1 to B1 into (51) yields
A 5 L2a00
MH(1-1 MH(L-p) )
I²a20²
+0 [
+0
+ +
MH
H
(56)
L20202
0 50
MH(1
-
Finally, plugging the bounds for A to A3 into (49) yields
L2
M
H-1
2 g0
000 00 (
L'a20² MH -
V VaMarkov 0O
+0 (L
MH
(57)
The proof is then complete.
With the upper-bound for the variance reduction term under Markovian sampling, we now introduce the following lemma, which bounds the one-step recursion of the distance the optimal parameter 0* in the Markovian sampling setting. This lemma lays the foundation for understanding the impact of time correlations on the convergence behavior of FedHSA.
Lemma 4. Suppose Assumptions to 4 hold. Then the following holds for FedHSA Vt P T:
E
0r 1- < (1 ap 0 (1203) 10000 -0-1
00133]
+0
L²
La
ΣΣ
M
E
10000 (00)
[-]
2
MH
pMH
+ +
1.20202
+
{ g(() 0",
2a
M
H-1
-
)
MH(1-p)
MH
(58)
Proof. As in the i.idd case, we first write the error update rule as follows:
[oitt1) 0r11 -00l+ |
0011² @(t)
0+h
2x
ΣΣ
H-1
+o²
M
G
(59)
MH
MH
t=
We proceed to bound the term U2 using Jensen's inequality. By taking expectation, we obtain:
Un
U2a
H
B S 2E
1 MH
Σ
(G(0
+
2
1 MH
(60)
Note here that the term U22 only involves the true operators, and thus do not need consider the effect of Markovian sampling. Therefore, it be upper-bounded exactly as the term TV in the i.i.d. case, i.e.:
U22 s
L'aa
Σ
M
H
10 - g 1 + E
100
001
(61)
MH
The term U21 is exactly the variance reduction term we bounded in Lemma 3. Plugging the bounds for U2i and U22 into (60) yields
EU 50
L MH
ΣΣ
00|
+0 (1)22) E
| | 00l2 +0 (
L2a202 MH(1 - -p)
32

---

Published in Transactions on Machine Learning Research (01/2026)
For the term E|U1], we can decompose it into two parts:
C1
C2
M
H-1
M
H
B = IE ((0) -0,- 0-,
2a MH
+ E
0(0) - 0r
2a
c.(0(())
MH
t=
8=0
(63)
Note that the second part C2 can be bounded similarly as the term Ti in the i.i.d. case:
C2 S aapB 8 8-
aL
M
H
(00))
g(4) 1
+
E
(64)
HMH
t=
Plugging (64) into (63), together with (62) into (59) and taking expectation on both sides, obtain
E
glt+1) -8¹ 11 $ (1 ou + 0
[(0)
+0
II'a²
Li
Σ
M H-1
E
10(0 g(0)
MH
μMH
2
Tyjus
+ E
g(t) 0-,
20
M 1-1
(,(0 -.,00)))(1)))))))
to + +0
+0
(
MH p)
12
M
(65)
Comparing Lemma with Lemma 2, we observe that the one-step bound for the i.i.d. case can be recovered in Lemma 4 if data are iid., i.e., p O. The only term that impedes further bounding in Lemma 4 is the one Toias capturing the bias caused by Markovian sampling. which equals zero in the i.i.d. case proved in Eq. (39). The next lemma then focuses on bounding this distinct bias term in the Markovian case.
C.1 Bounding of the Markovian Bias
It worth noting that the goal of bounding the bias term ensure that the term E [ 0' on the R.H.S. has scaling factor no larger than ap, along with constant term scaled by an order of a that is either higher than equal to 3, or an order of 2 but scaled down by the number of agents M, thus demonstrating the benefits of collaboration. Unfortunately, directly applying Eq. (17) cannot yield the desired result. Instcad, by applying Corollary 3 to account for the time correlation in data samples, we condition on parameter at least 7 time-steps earlier in time. Specifically, since in the bias term, the parameter 044 is from the f-th round and ε-th local step with 2 F, we condition on g(t-F), which is at least F time-steps earlier. For this reason, we first provide an upper-bound for the term E [10000 [1 which comes in handy in subsequent proofs.
Lemma 5. Suppose all the conditions in Lemma 4 hold. Then there exist a universal constant C 2 1 such that by selecting n $ 1/(FCHL2) and ag = 1, the following is true for FecHSA for all t 2 27:
g(t) - g(t (() < E (00
0-1("]
+ +0 10TFT..0000
F2L'2002
(66)
MH -
33

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. Observe that
M H-1
1 H-1
g(++1) 8r 0- 000) 1-| 2a
g(0) 0r, MH
Σ
Σ
G(((
G.
MH
M R-1
H-
((0) 8+
|+
+ a²
Σ Σ
(i
a
MH
MH
t=
t=
M #-1
e-12
$ (1
+ a)
((0)
+ 2a
MH
(67)
where we used the fact that a S 1, and 2 (a. b) < ||all2 + |لل| for all (a, E TRd x Rd. Taking expectation of both sides and plugging in the bound for 2EUUg]/ a in Eq. (62) yields
E pot1 - -
S (1 a)
(00) - 0r 12
+ +0
I.a
ΣΣ E
M H-1
|100 - 00113] + +0 (L2a) (L'a) E
0 -0
MH
i=1
L2oo²
+0(L'a
M MH
(1+
| | - 0r
27
+ +0 +0(L'a²)
- 0r 1011 +02) + +0 (L2a) +0(Laa) E
[E
0 - -
2
L'ao²
+ +
MH(1
$ (1+a+0(L'' + L'a)) E
@00 - -0113)
+ +0
1,200
MMI(1-0)
+0(L'000))
- (MPA00-))
L'ao²
s (1+0(()))
+ + +0
(68)
where in the second incquality used Lemma 1 and we selected 7 large enough such that p² a² and in the last inequlaity we used the fact that aL < 1.
Therefore, for any t' E [t F, f), we can write
E g(e) 0-133] 5 (1+0 B -1 Σ
L2ao² MH(1 - p)
1.'0002
<0(1 E | - o-113) + 10 [
L'ao²
MH(1
(69)
where we selected a s 1/((I277) where C 2 the dominant. constant in O (T?a), such that (1 (I+0 < 1/7) ee.
34

---

Published in Transactions on Machine Learning Research (01/2026)
Next, observe that
g(m) 27
E
g(t)
g(c-r)
@lm+l)
m==
M H-1
f
a²
G (m))
MH
n=m--
1= 00
|
0* 2 2
I²a20²
0
+ L 1
MH -p)
m=iー
=F - 0013]]
FL'a'0²2
L''0'0
Σ
0
12-OEE
LL'
MH(1 p)
MH( -
[-1 Σ
|
8r !?2]
+ L44002
MH(1 - p)
1720002
m=|-F
((tー +) 0r 1 27
FL''200"
<O(PDaa) B
+ +
72 FL
MH(1 p)
sO(PL'a E
[1ot-=)) g00)
+0
+0 E |000 - 0r
=2
+0 (PL'''O'+
MH(1-P)
(70)
where in (a) we used the bound for [[UU and plugged in Lemma 1, i.e.,
0 0. 2 + ( +o MH(1 -
I²a2002
B|US] (
(71)
Note here that we are allowed to use the bound for B[Ug] because require 2 27, and thus m 2 F
in (b) used the result in Eq. (69), and in (c) we selected S 1/((77) such that 5 < TAa'02 and
FL < 222
Suppose that the dominating constant in O (F²L3a² E - 000
is C We can then write
(1 (1-OPL33
0 - 16 (O(PL''a))
|000 - -01,3 +0 2O(P''at0- M (72)
By selecting a such that 0-2120² < 1/2, i.e. a 1/(11/12))) 1/(V2CFL) we oblain
2 | sO(F)Pa)) B |1000- 1-1 o (PIA00O0
72L2a202 MH( p)
(73)
The proof is then complete.
With Lemma 5 at hand, we can arrive at the following lemma that bounds the Markovian bias: Lemma 6. Suppose all the conditions in Lemma 5 hold. Then the following is true for FedHSA for all t 2 2F:
E
g())_ g^
20
(G(0(()) 0, -.(00))))
-
+0
FI'02
I/a2)
IAa3)
)) E (0()) 0¹
MH
0=0
rI?o2a2 [.oo'a3
+
MH(1 - )
(74)
35

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. Observe that
D
>)
M
E
((0) 8*
20
(((0))))) -((0)))-((00))))
= E
(lt) g
2a
MH H
MH
t=
Da
M
- )
((- -0,
2x
E
MH
(75)
We then continue to bound the terms D1 and D2 separately. For the term D1, we have
M H-1
1 E D1
|000 -((0))(())))
ta 2
-
MH
i=1
<0(FI' E
| 0"
+ +
FIL'a00²+
7I20202
P))
MH(1
(76)
+0 E
( 0"
+O
+
MH(1 - pp)
g00 gr 2
7T20202
{O(FFa)) E
+0
MH(1 -
where we use Lemma 5 and Lemma 3 with the bound from Lemma plugged in. Clearly the bound for D₃ is eligible for our goal.
For the term D2, again, directly bounding will suffice. Therefore, we introduce intermediate terms G, (0(1) and G,(00),, (.)).
E
( (bl-.)- 0r,
2a
M
H
(, - -
D2
MH
E2
#-1
[|L-3]- 0r, 2a
(G.00 (1)) .0(9)
+
MH
Ea
H-1
g(r-)) 0-
2a
(G.(0))) -((0))((000))
+ E
MH
We then bound these three terms separately.
36

---

Published in Transactions on Machine Learning Research (01/2026)
For the term E2, have
F2g
E
a - 0r
(((->)
0B3
1
G. 10 (.)) Gi
3
MH
E=
(a) 20
E
(((--F) 8(1)
27
+
20
(0())
8
2
+ aB
Σ Σ L'
M H-1
0/0
g(e)
8
B
2
MH
2/
i=1 t=
0 (
E
[(()
2
+
0
F2""0000" +
72 2
+
20 3
E
|1000
8r 11
B
MH p)
+ (BL'
E
[000 0r
+
2
20 (20 +0 3
72 (
0r 0-|13]
LL
7LL20203 MH p) + +BL
+ BL 3
E
(10)
+0
3
(78)
where we use Assumption 1 in (a), Corollary 2 and the bound from Lemma 5 in (b). We can achieve identical bound for Eg with the same reasoning. With a proper choice of the parameter B (which will be made later), the bounds for Eg and Eg also comply with the requirement.
For the term E1, further decompose it into three terms:
F
E1 E ( (((-+) 0+,
2a
(,(0(t-F), .00) - G.((((
MH
F2
E
O((-F)
0-
2x
(G,(0(() .0(h) (010 (0)
(79)
MH
8=
Ps
H-1
g(c-t) 8r
20
(G,(0(t-t)) (G((0(-))-CC((000)) -.(0(1)) -C,((())))))()))
+ E
MH
8=
For the term F2, we have
F2 s E
2 (((-F)
001/ -
g -(())
FLa (((-F) - 0+) 1|3 +
[((--)) g(t) 12
S aLE
FLa
2
SaLo
E
FLa
(t-F)
g(0)
2
+ FLa
(0()) 0-112
+
FLa
1
[((- - 800) 1
(80)
(((=F) 0(()) 1²8)
S al.
R
FLa
x(t))
0r
+
FLa
8- [(:)
=T.20202 MH(1 p)
0 (FI'
E
g
+
FFL'a'02
FII
where we use Assumption 1, the fact that a S 1, and the bound from Lemma Similarly, we can obtain the same bound for Fg. The bounds for F2, Fg satisfy the requirement well.
37

---

Published in Transactions on Machine Learning Research (01/2026)
Finally, for the term Fi, we have
M
H
F =
E
E
0
0-
20
G ( - -,(0(-1)))
MH
M
(0)
E
(((-
2a 0',
E
(1)
((((() 5)
(,(l-=)))
MH
M H-1
18
2a
((t-)) 0- | E
(1)
F( 7)
(,(0(-)))
MH
1=1
(6)
I (Lp a) E
0 0111
0
0r 2
+ [a]]
(Lp' a) E
((C- 0-11"
0 (L' ao) E || | 0-
|
$ (O(L))) E
@(t-+) 8r
+ 20 (((--) -0"
+ ao2
2
(81)
27
- (Ia))) E
00
+ Vad
| 0+ 2
2 0 (T.)))) E
+ 202
0 LO
g F) 8-
+ La
| 000
(000)-0l("" Toat22)
Lo 2E
T
(4)
2 0
72 La
(000) 0r
MH(1 - p) + LLaEE
7²
|1000- 0. 0-16]] + Lat
2
2 0 (La?)
E
11 (100
0-
|
+ -
+
[La'o²+
11,20002
MH(1-
Here, in (a) we used the fact that Ø(t-F) is deterministic conditioned on FLT") (b) is a result of Corollary 3 and Assumption 4, (c) used the fact that p² a²² (d) used previous bounds for E [|000] g(t [|]] and (e) used the fact that a S 1/(FL?), and hence f2 < La
We now plug in the bounds recursively to arrive at the final bound for the Markovian bias term. First, plugging in the bounds for En with Eg Fi + F2 + F's yields
+ +0 -010
P2L3a0o2
F ( E.
+0
MH(1 - p)
E | 001(2) + +0 1OFL'a''''
712
(FL''a)
(82)
MH(1 pp)
{O(FL'a?)
|000 1013]] + +
FL2
MH(1-p) p)
where we use the fact that L 2 1, 7 2 1 and 0² 1/(TT).
38

---

Published in Transactions on Machine Learning Research (01/2026)
Second, with D2 E1 + E2 + Es, obtain
((0) 0 01 +0
D2 1000
E
+0
MH(1 p)
+ 4a
+0
(ALPa)
+BL
B
[00 -
+
7
MHB(1 1 +
3
2
4a
+0
FL'a²
PLPa33
BL'aa)
E
((0)
0r
|?]
3
2
L
7L202a2
+
+
B
MH3(1-P)
MH(1-1 -
(83)
Finally, using C1 = Dj + D2 yields
|000- - -0113] +0 FFL'''0
FL'a0002
Ci S ( E
MH(1 p)
4a 0
FI.202 71203
+ (3.T00
R
(00) -0"
PLO'
FI200a2
+3L'0a0
+
(84)
MH3(1
MH(1 - p)
4a
B + +BI ))
|000 0=|
$
+0
2T
+
3
22
MH(1-P )
FI.20a02
+0
MH3(1-P) - p) + +BL +
B
By selecting 4a/3 = a/1/2, i..,, 3 = 8/u, we obtain
ajl 2
FL"a² + 1222 + L'a²)) E
10000 8(0) (0|12)
C1 <
+0
PLL2
MH(1-1 + Loo2a3
FL?o2a2
+0
?2 L2
+TL +
(85)
MH p)
< <(7 +0 FLL2a²+
aj
L'a3) 11a))
E 0000 - 0r
+0 L'00aa"
TL2o2a0
MH(1-p)
where we use the fact that μ S and S 1/7.
Lemma 7. Suppose all the conditions in Lemma 5 hold. Then the following holds for FedHSA for any t > 27:
E 10tt)100 - 8r < <11-10111 ap +F(22a²) E |000
0z 00
+0
F22
a²
02
(86)
MI1 p)
4
39

---

Published in Transactions on Machine Learning Research (01/2026)
Proof of Lemma 7.
Proof. Plugging Lemma and Lemma 1 into Lemma 4, obtain
-
(aa3))
La
1
L'oaa
L2a²00
E
0r
5 1
a1aa++ +0
E
0r
+0
+0
1
1
MH(1-) -
+
aji
O
(T.202 + L'ad*
T..
|00
0r
27
+
L'00a"
71200a22
p))
+ +0 +1(1..000)
2
1
1
MH(1
04
+0 FiL'a² +
I,a a3 ))
1
LiP2a3
+
MH(1 - p)
1
op
2 + o (FI?0?) E ((t)) 0- |
- 0
L'o'a"
FL2a20²
1
MH(1 -
(87)
where we used the fact that a < Fp/ L
Proof of Theorem 2.
Proof. Applying Lemma 7 recursively, we obtain
E (CT)
< 00100]
0r
aj
T-27
(((E)) - -001
+ +0
Fa?
L
T-25-1
Σ
(1-4)
(1-94
--
aw
4
MH(1
1=0
oxp
T-27
E
((er) 0.12
+0
7a
+
02
4
WMH(1
112
(88)
where the first inequality holds because we select a < H/(AFL2("), where C' greater than or equal to the dominant constant O (FI.2a2) such that O (FI2a²) ap/4.
We proceed to bound the term E [|002F) 001]] From the update rule of FedHSA in Eq. (10) and Eq. (11),
obtain
M #-1
((+1) 8-- - g(t) 8"
a
Σ Σ
G
(89)
MH
40

---

Published in Transactions on Machine Learning Research (01/2026)
where we subtracted 0 on both sides. Taking norm on both sides and applying triangle inequality yields
M
H-1
| - 0r
(
0"
MH
M
H-1
a
G:(
1.E) 1
MH
M
H-1
(
0
+
aL
00 +0)
MH
(0
aL
(1 800) + g(0) 0- + 0- 2
+ o)
MH
(90)
(00)
(11010 - 800 1|_ + [00) -
+ 1100|12 + o)
MH
M Σ
[000 8-
+ aL
Σ
La (((0) - 8/), + Lao
(0(1) 80 + +20
MH i=1 1=)
(00) 00
+ aL (2/ [00)) 0-)
||,
+ +30)
2
(1 + 20l)
(00) 0011 + +3aLo,
where (a) holds due to Assumption 1, and (b) is a result of Lemma 1. Therefore, applying Eq. (90) recursively yields
11
g(2F)) 8+ 11, S (1+ 2aL)
27
|000
+ 3aLo
(1 + 2aL)
1
2F
2F
1
2F
5
+
2F
(10) - 0r
2
+ Lo
Σ
+
27
(91)
S e g(0)
0-)
2
+ 2ea
o (11000)
0r
+a).
where we selected a S 1/(4FL), and used the fact that (1+1/x)² S e, e, > 0. Plugging Eq. (91) into Eq. (88) yields
E TT)) - 0/113] - (1 8(1- 4
ap
T-2F
o
01000
- -0
to a
+
1uMH(1 p) +
FaL?
a²L*
2
12
S exp
1 (T
27)
(x(0)
0"
2
+ 0
+
FaL? 2²
0²
2
(MHH(1 - p) 112
(92)
exp
aT)
exp
uTa
0
[1())
0+
2
+o
+
FaL?
o²
2
WMH
112
S exp
(T)))) 0
((0)
0+
+ 0
+ 0
FaL2
+ 12
a²L4
o²
WMH(1
(1
where we used the fact that 1 - exp
(-x), a < 1/7, and S 1 such that exp(uta < 01).
41

---

Published in Transactions on Machine Learning Research (01/2026)
D Experimental Results
In this section, we present numerical results for three heterogeneous federated SA tasks subject to Markovian noise, which provide empirical support for our thcoretical framework. In our experiments, we aim to convey two key messages: (i) Our FedHSA algorithm eliminates the heterogeneity bias and (ii) FedHSA achieves lincar speedup w.r.t. the number of agents. The experimental sctups are described in detail in the sequel.
D.1 Federated Quadratic Loss Minimization Problem
Consider the classical FI, framework involving M agents:
M min ((0) = M Σ 11())- 8E3
(93)
1=1
Here,
1 f((0) -00 A.0 - Ci.
[
(94)
where A, E Rdxd is a positive definite matrix, 6; E Rd is a d-dimensional vector, and oj E R is a scalar for - 1, ,M. Since [fil/= are quadratic functions with positive definite A,ss, the gradients are given by Vi((0)= = A,0 b,, for == 1..........
Problem (93) is a good fit for our federated SA framework. Specifically, the true local operator G.()) corresponds to the true negative gradient f-) for each i E [M]. At time step t, each agent E [M] has access only to an estimator G,(+) of the true operator, which is corrupted by additive Markovian noise:
G,(0(t) = (0()) + ct9)
Ei [M]
(95)
where the noise samples (5!") J220 are drawn from discrete-time continous-state Markov chain.
We now explain how the Markovian noise is generated. For each agent i, we maintain a state vector E Rdd, initialized to zero, which evolves as
(t-1) (-11= =iz! + +
(96)
Here, Q E dddd is Schur-stoble matriz, ensuring that all eigenvalues of Q, lie within the unit ball. This
guarantecs that z/ does not diverge. The noise ( is a zero-mean Gaussian noise with variance o² and
covariance matrix given by I, ie.,, &0 *~(00,0 The Markovian noise e(()) is directly taken from the state vector:
=
(97)
It can be shown that this noise is Markovian (Tu & Recht, 2018), and mixes geometrically fast (as needed by our thcory).
To validate (i), we consider Problem (93) and solve it using the conventional FL framework, where each agent performs local steps. We compare FedHSA with the existing local SGD approach, which does not include a correction term during local updates as shown in (9) (referred to as the "Local SA approach" in what follows). These two approaches are evaluated under both noiseless conditions and with the presence of additive Markovian noise. The experimental configurations are as follows: M 20 agents, each agent performs H 10 local steps, the learning rate is 17 0.001, the parameter dimension is d 10, and the performance is measured by F, : ||000 8- ||=
As shown in Figure 2(a), even in the noiseless case where each agent has access to the true operator G the Local SA approach fails to converge to the optimal point 0* due to the heterogeneity bias, as explained in Proposition 1. In contrast, FedHSA demonstrates linear convergence towards 0*. This result aligns with the theoretical prediction in (12), where the algorithm converges exponentially fast to 0r in expectation when o² (noiseless case).
In Figure 2(b), we introduce additive Markovian noise with of 0.01 into the local operators G,'s. In this noisy setting, we observe that the FedHSA method exhibits lower error floor compared to Local SA. This is
42

---

Published in Transactions on Machine Learning Research (01/2026)
10
10a
Local SA
10
FedHSA
10
10a
10 10-10
10
10-14
Local
10
FedHSA
10
200
400
600
800
1000
500
1000
1500
2000
t
t
(a) Noiseless sctting
(b) Additive Markovian noise sctting
Figure 2: Comparison between Local SA and FedHSA
10
agent
10
agents
agents
10
100 agents
10
10
10
0
200
400
600
800
1000
t
Figure 3: Comparison between different numbers of agents for the FedHSA algorithm.
because FedHSA effectively eliminates the heterogeneity bias, with the resulting error being solely attributed to the Markovian noise. Additionally, the impact of this noise is mitigated by factor of M, owing to the linear speedup of the FedHSA algorithm.
further verify the linear speedup effect (ii), we compare the results FedHSA with different numbers of agents. We consider the same problem (93) equipped with the FedHSA algorithm for M 1,5, 20, 100. The other configurations remain the same.
Figure 3 demonstrates lower error floor with an increasing number of agents for our FedHSA algorithm. This is exactly what we expect, since Corollary 1 clearly states that with proper choice of the step-size Y, the expected error floor dr is upper-bounded by ((H(MMHT)) which is inversely proportional to the number of agents M.
We also present results in scenarios where Assumption does not hold, meaning each A; for E [M] is symmetric but necessarily positive definite. Consequently, the objective function fi becomes nonconvex. Removing this assumption significantly expands the applicability of our algorithms. As demonstrated in Figures 4 and 5, the observed results remain consistent with those obtained under strongly convex objectives.
D.2 Federated TD Learning with Linear Function Approximation
We proceed to explore the application of FedHSA to FRL via focusing on the setting of federated TD learning with LFA. We begin by providing a detailed explanation of the problem formulation.
Consider total of M agents, cach agent intcracting with its individual environment equipped with a fixed policy μ4 which can be modeled as Markov reward process (MRP). Suppose that all the MRPs have identical finite state and action spaces, though not necessarily the same transition matrices, reward functions,
43

---

Published in Transactions on Machine Learning Research (01/2026)
Local SA
-
FedHSAA
10²
-
10 10
10a
10
Local
10
10-18
FedHSA
200
400
600
800
1000
500
1000
1500
2000
t
t
(a) Noiseless sctting
(b) Additive Markovian noise sctting
Figure 4: Comparison between Local SA and FedHSA with nonconvex objectives
103
agent
agents
10
20 agents
100 agents
10
10
10
1000
2000
3000
4000
t
Figure 5: Comparison between different numbers of agents for the FedHSA algorithm with nonconvex objectives.
discount factors. Specifically, the MRP of the i-th agent is denoted as M; (S,A,P,, R, n)), where S is the state space with cardinality S; A is the action space with cardinality A; P, is the transition kernel dictated by the local policy μ4 R2 is the reward function; and ?/ is the discount factor with < 7/2 < 1. We denote r!!) as the reward observed by agent i at time-step l.
For self-containedness,, we reiterate some basic concepts. For agent and the underlying MRP M., the associated policy is P4s and the value-function V, defined as:
Vi(8) = E
(0) = 9,
(98)
(6) is the state of agent at time-step l. where 8,
In many RL applications, the state and action spaces can be extremely large, making it impractical to store the value-function for each state s. To address this, feature matrices are often used to approximate the value-function. One common approach the LFA framework:
V &,0,
(99)
where V44 the approximated value-function for agent i in vector form, o e g dd is the feature matrix specific agent i, consisting of d lincarly independent feature vectors ( and E Rd is the nominal parameter. Here, we make the general assumption that all M agents do necessarily use the same set of feature vectors (Doan, 2023).
44

---

Published in Transactions on Machine Learning Research (01/2026)
The goal in this problem is for the agents to collectively find a parameter 6* such that it best approximates the value-functions across all agents, i.e.,
40
V₁
(100)
where == 1. M - 4.-
To this end, each agent updates its parameters by taking the direction of the negative gradient of the sample Bellman error B BE, al observation 0i,t == {o( 1 88 ((+1) w.r.t. parameter g(0) at time-step I, obtained via interacting with its own environment MM.
BE, 1 (1)
(
(1) + Yo +o (000)) of (5(9))88())
(101)
g The server then collects the local parameters for where (s(")) is the feature vector agent i for state aggregation, exactly the FL framework.
The negative gradient step of (101) is given by:
gi (000) or,t) = (1)0 + 707 (5) (00 o5 -0 (o("))00))) )e(o!9).
(102)
Note that in (102), the gradient (0(),, or,() is implicitly integrated with Markovian noise since the states are sampled from the underlying Markov chain.
Local SA
10
10
FedHSA
10-5 5
100
10-2
10-13
10-17
Local SA
10
10 21 21
FedHSA
500
1000
1500
2000
500
1000
1500
2000
t
t
Noiseless setting
(b) Additive Markovian noise setting
Figure 6: Comparison between Local SA and FedHSA
We also provide the expression for the expected negative gradient step, which one interpret the noiseless gradient:
(.(0))) x.. ( v,0(1),
(103)
where D, = Diag(n,), m, is the stationary distribution of P,, and Tj the Bellman operator for agent i. We refer the reader to (Bhandari et al., 2018) for more details.
Our federated SA setup (1) precisely captures this setting. Specifically, G, corresponds to the noiseless gradient operator D: for agent [M], and G; corresponds to the noisy operator 9i incorporated with Markovian noise.
To validate message (i), we compare our FedHSA algorithm with Local SA where there is no correction term in the local update of each agent. We consider foderated TD learning sctting with LFA involving M 200 agents, with each agent performing H 10 local steps. Each MRP M, has S 100 states, and the rank of each feature matrix t; is d = 50.
45

---

2000 Published in Transactions on Machine Learning Research (01/2026)
10a
agent
agents
10
20 agents
100 agents
10
10
10-2
500
1000
1500
2000
t
Figure 7: Comparison between different numbers of agents for the FedHSA algorithm with the federated TD setting
Figure clearly demonstrates that FedHSA converges exponentially fast to 0* in the noiseless case and consistently outperforms Local both in the noiscless case and the one with Markovian noisc
We validate message (fi) by comparing FedHSA for different numbers of agents M 1,5, 20, 100. Figure 7 shows improved error bounds with an increase in the number of agents, substantiating the linear speedup effect.
D.3
Federated Finite-Sum Minimization Problem with Quadratic Loss
102
Local SA FedHSA
10
10
10
10
10
10
10-16
10
Local SA
10-21
FedHSA
10-3
100
200
300
400
500
100
200
300
400
500
t
(a) Noiscless setting
(b) Additive Markovian noise sctting
Figure 8: Comparison between Local SA and FedHSA
101
agent
agents
10-1
20 agents
100 agents
10
10-5
0
1000
3000
4000
t
Figure Comparison between different numbers of agents for the FedHSA algorithm with the finite-sum setting
46

---

Published in Transactions on Machine Learning Research (01/2026)
In section D.1, Markovian noise was introduced by directly adding noise to the true local operator. Here, we adopt alternative approach to incorporating Markovian noise: sampling data points from a Markov chain in a fimite-sum setting. The detailed problem formulation is presented as follows.
We consider the same federated minimization problem as in (93), but with a different structure for the local loss functions fi's. Specifically, for each i [M], we have
N (0) (0)
N Σ 3=1
1 f:(0) = N ==1
- b ois)
(104)
N
Here, A E Rddd is a positive definite matrix, brg E Idd is d-dimmensional vector, and Ci2j scalar for 1, .N. In essence, each local loss function is the average of N quadratic loss functions, giving rise the name "finite-sum setting.'
We now describe the incorporation of Markovian noise. For intuition, consider the case where the noise is i..d., meaning each agent i E [M] selects one quadratic loss function fú, uniformly at random and computes its gradient to determine the descent direction. Under Markovian noise, however, instead of selecting data samples uniformly at random, agent i selects fú, based on a discrete Markov chain M,, The states of the Markov chain M, correspond to the indices [N] of the loss functions {fi,) and its stationary distribution Pa is the uniform distribution over [AV] This ensures that in the limit, G, is an unbiased estimator of the true operator G., G.(-) Eo-ns (G((:)) o)] holds only when μ is uniform over [N].
We set up the experiment with M = 200, N = 2, d = 200 and 0.01. Figure 8 validates message (i) exactly as in the previous experiments. Figure 9 compares the performance of FediSA under varying numbers of agents, specifically M = 5, 20, 100, with N = 10. Consistent with the observations from the previous experiments, the error floor decreases as the number participating agents increases. This empirically validates our thcorctical result that dr S ((1/(MHT)) demonstrating the benefits of collaborative speedup in reducing error.
47


Reviews:
[{"review_id": "MPuPeae2rY", "reviewer": "Reviewer_kPGF", "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": "", "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 aims to provide an enhanced finite-time convergence analysis for heterogeneous federated stochastic approximation where the data and observations of each client are generated from an ergodic Markov chain rather than independent and identically distributed (i.i.d.) from a stationary distribution. This captures broader interesting problems in dynamic environments like wireless systems with channels changing over time.  However, this also induces some additional challenges in analysis, e.g., leading to additional bias terms such as the one on page 11. The authors provide the first finite-time convergence results for federated optimization under such Markov data, particularly without relying on any projection step or restrictive assumptions.  \n\nThe developed method considers a general SA setup. Therefore, the method could be applied to broader problems such as multi-agent RL problems. In this setup, there have been quite a few works focusing on developing finite-time results for federated algorithms under different data or setups. In particular, the authors clearly compare their results to these results. For example, their results allow for heterogeneous MDPs across different clients, and compared to existing results such as those in Zhang et al., 2024, their results suffer from a heterogeneity-induced bias term. In addition, a linear speedup result is shown as well. Table 1 is a good summary for readers to quickly compare different related works. \n\nSome methods turn out to be interesting, if more details are given. For example, the authors first show that only the local updates with multiple agents and periodic communication can induce non-vanishing error terms proportional to the constant stepsize. The authors propose to add a correction term relying on the stored aggregation at the beginning of each communication round. It would be even better if the authors can clarify if this is a widely used approach in i.i.d. data case, or it is specially designed under the Markovian data.", "claims_and_evidence_yn": "Yes", "claims_explanation": "This paper is very well written and clearly discuss all relevant works along this direction. I like the comparison to existing results in the introduction, providing readers with sufficient evidence to understand the main contributions and the theoretical advantages over existing literature. In addition, Proposition 1 motivates the algorithmic designs and the proof sketch part helps me to understand the main technical contributions.", "audience_yn": "Yes", "audience_explanation": "This paper provides the first finite-time convergence results for heterogenous federated optimization under Markovian data, without any projection step, while achieving a linear speedup result. It contributes new result in this setup. The analysis can be of interest to multi-agent and federated RL communities.", "requested_changes": "1.\tProposition 1 shows that the error is proportional to the stepsize \\eta. I am wondering if this stepsize decreases with time, will it lead to a  worse rates or without linear speedup? The authors may want to provide a formal comparison. In addition, typically, for federated optimization with i.i.d. data, with proper aggregation and stepsizes (not necessarily decreasing with time, i.e., can be small constants), that client drift will not happen. I am wonder if this is the special challenge of SA or Markovian data case? \n\n2.\tAssumption 2 seems a little bit strong as it corresponds to the strong-convexity in optimization perspective. This assumption seems quite necessary when proving the Claim on page 11, where the authors show that the bias can be resolved without any projection step. I am wondering if the results also hold for general nonconvex case? If not, what is the challenge?\n\n3.\tSince the authors propose new algorithms, I believe some validation experiments are needed. For example, it would be good to validate the results such as linear speedup, the correction term, convergence rate etc.", "broader_impact_concerns": "This is a theoretical paper and there are no broader impact concerns.", "additional_comments": "RL experiments should be provided.", "extra_scores": {}, "extra_text": {}}, {"review_id": "G1CLVtDiMY", "reviewer": "Reviewer_uWrU", "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": "", "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 presents FedHSA, a novel federated stochastic approximation (FSA) algorithm designed to address heterogeneous federated learning problems under Markovian data. FedHSA incorporates a drift correction term in local updates to handle heterogeneity in agents' local operators. The paper establishes finite-time convergence guarantees showing convergence to the correct global optimum without heterogeneity-induced bias, achieving linear speedup with regard to the number of agents.\n\nStrengths\n1. The work develops and analyzes FSA under more generalized setting (Marokvian sampling and non-linear operators) compared to the previous work [1] mainly considering linear operators and providing limited analysis on Markovian sampling.\n\nWeaknesses\n1. Core algorithm design/analysis overlaps with the previous work [1]: [1] studied FSA under heterogeneity and proposed a similar bias-corrected (scaffold-style) algorithm that removes heterogeneity-induced bias and achieves linear speedup. \n2. Although the paper differentiates its contribution from [1] by claiming to consider more general non-linear operators, it is unclear how technically challenging or novel this extension is.\n3. Similarly, analysis of federated SA under Markovian sampling is common in the federated RL/SA literature, and it is unclear how challenging or novel it is to additionally consider Markovian sampling in this problem.\n4. Communication analysis is not that informative. Many federated RL algorithm [2,3] provides communication sample complexity in terms of problem specific parameters (horizon length or discount factors, state-action size, stationary distribution). However, this work does not characterize the communication overhead clearly and present it mainly in terms of H (local updates), R (total samples), which seems superficial.\n\n[1] Paul Mangold, Sergey Samsonov, Safwan Labbi, Ilya Levin, Reda Alami, Alexey Naumov, and Eric Moulines. Scafflsa: Taming heterogeneity in federated linear stochastic approximation and td learning. Advances in Neural Information Processing Systems, 2024.\n[2] Sudeep Salgia and Yuejie Chi. The sample-communication complexity trade-off in federated q-learning. In Advances in Neural Information Processing Systems, 2024.\n[3] 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. 10997–11057. PMLR, 2022.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper provides theoretical analysis with detailed proofs establishing convergence rates.", "audience_yn": "Yes", "audience_explanation": "The paper provides a principled design and analysis of federated stochastic approximation under heterogeneity for a realistic setup (nonlinear operators and Markovian noise), offering broad applicability and theoretical advancement.", "requested_changes": "I suggest the authors to address the following points, which are critical for clarifying the paper's precise technical contributions and novelty.\n\n1. Clarify the technical challenge and novelty of non-linear operators: The paper differentiates its contribution from [1] by claiming the more general consideration of non-linear operators. However, it is currently unclear how technically challenging or novel this extension is. The authors must explicitly detail the specific technical hurdles introduced by moving from linear to non-linear operators and clearly articulate how their analytical techniques overcome these challenges in a novel way.\n\n2. Justify the contribution regarding Markovian sampling: The analysis of federated SA under Markovian sampling is relatively common in the federated RL/SA literature. The paper would be significantly strengthened if the authors could more clearly explain the novelty of their analysis in this context. Please clarify what unique challenges arise from additionally considering Markovian sampling in this specific problem (e.g., in combination with heterogeneous non-linear operators) and how the proposed analysis advances beyond existing work in the federated RL/SA domain.\n\n3. Provide clarifications on why the extension to no-linear operators is important.\n\n4. Provide more detailed characterization of communication complexity in terms of problem specific parameters.", "broader_impact_concerns": "No significant concerns. The work mainly focuses on theoretical aspects of the problem.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "T5OE32yv4s", "reviewer": "Reviewer_Vbyh", "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": "", "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 makes the following contributions to the problem of federated stochastic approximation:\n\n1. **Primary contribution:** This work proposes a novel algorithm that provably achieves both *exact convergence* and *linear sample-complexity speedup* under both *Markovian noise* and local *heterogeneity* for federated SA under *sparse communication constraints*. This provides a framework that could be adapted to both stochastic approximation and reinforcement learning.\n\n2. **Technical contribution:** The proof of the main theorem (Theorem 2) is established through handling complex statistical correlations and drift terms caused by Markovian sampling, communication between agent and central algorithm and heterogeneity across agents. Notably, the authors avoids relying on a projection step (which ensures boundedness of the iterates) in the algorithm, and therefore have to deal with much harder bias control.\n\n3. **Motivation and connection to various fields:** This work presents a thorough discussion of motivations from different existing fields, and provides a detailed discussion of related works, and provides numerical simulations of the proposed algorithm on those application domains. The authors provide a simple yet illustrative example of linear SA problem in which the naive local-update global-aggregation rule is biased under sparsity of communication, necessitating the design of a new algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors provide detailed proofs for their theoretical results and use numerical simulations to illustrate the effectiveness of their algorithm.\n\nTo make the entire proof of main result easier to understand, the authors first provide the proof of Theorem 1 in Appendix B through error decomposition and techniques from stochastic approximation. The authors provide intermediate results in Lemmas 1 and 2 to clarify the essential steps of the proof.\n\nBuilding upon the previous part, the authors provide a detailed proof of the main result (Theorem 2) using a proof with similar outline to that of Theorem 1, but carefully deals with the noise dependence induced by Markovian sampling, which makes the proof much more complicated. The authors provide bounds for various different Markovian sampling errors in Lemmas 3, 5 and 6, which are clear and easy to follow.\n\nAll theorem and lemma statements look reasonable. I checked most of the proofs and didn't find obvious errors.", "audience_yn": "Yes", "audience_explanation": "This paper studies the problem of federated stochastic approximation, which may be of interest for researchers in federated learning, stochastic approximation, optimization and RL.", "requested_changes": "I do not find any critical need to change the paper, however, there are a few changes that I would recommend:\n\n1. In the statement of Proposition 1, Schur-stable is not defined throughout the paper, and the symbol $e_t$ is not defined until later. These should be clearly stated within or before the statement. Also, the update rule in equation (8) does not explicitly state how $\\theta_{i,0}^{(t)}$ is set, which should be made clear.\n\n2. Both theorems take $\\alpha_g=1$ by default and define $\\alpha$ (the effective step size) to be dependent on $\\alpha_g$. This would make it harder to interpret how the bound depends on different algorithm parameters. For example, the statement in (12) looks like the larger $H$ is (the less frequent agents communicate), the better bounds we have, which is clearly wrong. I would present the theorem without defining $\\alpha$ and without the choice of $\\alpha_g=1$. It's also beneficial to discuss the communication overhead directly for Theorems 1 and 2, instead of only for the linear speedup.", "broader_impact_concerns": "I do not identify any broader impact concerns beyond the standard scope of theoretical research.", "additional_comments": "Comments and questions:\n1. Try not to use $\\mathcal{O}$ notations when proving the intermediate results. This can sometimes hide problem-dependent parameters.\n\n2. Omitting $o$ in $G$ terms can sometimes be confusing. For example, does $G_i(\\bar{\\theta}^{(t)})$ refer to $G_i(\\bar{\\theta}^{(t)},o_{i,\\ell}^{(t)})$ or $G_i(\\bar{\\theta}^{(t)},o_{i,0}^{(t)})$?\n\n3. In the linear speedup (Corollary 1), the choice of step size requires knowing $T$ in advance. Do the results generalize to using diminishing step sizes? For example, using $\\alpha_t=\\frac{\\alpha_0}{t}$?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)