Federated TD Learning with Linear Function Approximation under Environmental Heterogeneity
Authors: Han Wang
Aritra Mitra
Hamed Hassani
George J. Pappas
James Anderson
Venue: Accepted by TMLR ()

Abstract: We initiate the study of federated reinforcement learning under environmental heterogeneity by considering a policy evaluation problem. Our setup involves $N$ agents interacting with environments that share the same state and action space but differ in their reward functions and state transition kernels. Assuming agents can communicate via a central server, we ask: \textit{Does exchanging information expedite the process of evaluating a common policy?} To answer this question, we provide the first comprehensive finite-time analysis of a federated temporal difference (TD) learning algorithm with linear function approximation, while accounting for Markovian sampling, heterogeneity in the agents' environments, and multiple local updates to save communication. Our analysis crucially relies on several novel ingredients: (i) deriving perturbation bounds
on TD fixed points as a function of the heterogeneity in the agents' underlying Markov decision processes (MDPs); (ii) introducing a virtual MDP to closely approximate the dynamics of the federated TD algorithm; and (iii) using the virtual MDP to make explicit connections to federated optimization. Putting these pieces together, we prove that in a low-heterogeneity regime, exchanging model estimates leads to linear convergence speedups in the number of agents. Our theoretical contribution is significant in that it is the first result of its kind in multi-agent/federated reinforcement learning that complements the numerous analogous results in heterogeneous federated optimization.

Published in Transactions on Machine Learning Research (06/2024)
Federated TD Learning with Linear Function Approximation under Environmental Heterogeneity
Han Wang
huu2786@oolumbic.ec
Deportment of Electrical Engineering
Columbia University
Aritra Mitra
amitro2@ncsuu edu
Department of Electricol and Computer Engineering North Carolina State University
Hamed Hassani
hassoni wpwna.. edu
Department of Electricol and Systems Engineering University of Pennsylvania
George J. Pappas
pappasg upenn. edu
Deportment of Electricol and Systems Engineering Universily of Pennsyloania
James Anderson
Department of Electrical Engineering
Columbia University
Reviewed OpenReview:
net/ forum? id= hdhddgggyyFk
Abstract
We initiate the study of federated reinforcement learning under environmental heterogeneity by considering a policy evaluation problem. Our setup involves N agents interacting with environments that share the same state and action space but differ their reward functions and state transition kernels. Assuming agents can communicate via a central server, we ask: Does ezchanging information expedite the process of evaluating a common policy? To answer this question, we provide the first comprehensive finite-time analysis of federated temporal difference (TD) learning algorithm with linear function approximation, while accounting for Markovian sampling, heterogeneity in the agents' environments, and multiple local updates to save communication. Our analysis crucially relies on several novel ingredients: (i) deriving perturbation bounds on TD fixed points as a function of the heterogeneity in the agents' underlying Markov decision processes (MDPs); (ii) introducing virtual MDP closely approximate the dynamics of the federated TD algorithm; and (iii) using the virtual MDP to make explicit connections to federated optimization. Putting these pieces together, we prove that in low- now-heterogeneity regime, exchanging model estimates leads to linear convergence speedups in the number of agents. Our theoretical contribution is significant in that it is the first result of its kind in multi-agent/federree /federated reinforcement learning that complements the numerous analogous results in heterogeneous federated optimization.
1 Introduction
In the popular federated learning (FL) paradigm (Konečný et al., 2016; McMahan et al., 2017), a set of agents aim find common statistical model that explains their collective observations. The motivation to collaborate stems from the fact that if the underlying distributions generating the agents' observations are "similar", then each agent end up learning "better" model than if it otherwise used just its own

---

Published in Transactions on Machine Learning Research (06/2024)
K Local TD Steps
10
0 (3)
MDP
1.
9,
0
6
Virtual MDP
Server
3 .e)
FedTD trajectory during coarse tuning
1 0c+1
B 1x
MDPM
0
Trajectory of TD on Virtual MDP
K Local TD Steps
Fine-tuning for personalization
P:la) = Q0.
Figure 1: (Left) Illustration of how FedTD(O) works. Each agent performs K local TD update steps on its own MDP, and transmits its updated model to a server. The virtual MDP serves to approximate the dynamics of FO).D(O). The global model 0, at the server is used to construct a linearly paramcterized approximation of the value function associated with policy p.. (Right) FedTD(O) helps each agent converge quickly to a ball B(0", .e) centered around the optimal parameter 0* of the virtual MDP. Here, e captures the heterogeneity the agents' MDPs. Using the output 0r of FodTD(O), each agent i can then fine-tune based on its own data to converge eractly to its own optimal paramcter 67.
data. This idea has been formalized by the canonical FL algorithm FedAvg (and its many variants) where agents communicate local models via a central server while keeping their raw data private. To achieve communictiion-cffiiennng
a key consideration in FI the agents perform multiple local model-updates between successive communication rounds. There is a rich literature that analyzes the performance of FedAvg, focusing primarily on the aspect of statistical heterogeneily that originates from differences in the agents' underlying data distributions (Sahu et al., 2018; Khaled et al., 2019; 2020; Li et al,, 2019; Koloskova et al., 2020; Woodworth et al., 2020b; Malinovskiy et al., 2020; Pathak & Wainwright, 2020; Wang et al., 2020; Karimireddy et al., 2020b; Acar et al., 2021; Gorbunov et al., 2021; Mitra et al., 2021; Mishchenko et al., 2022). Notably, the above works focus on supervised learning problems that are modeled within the framework of distributed optimization. However, for sequential decision makinn with multiple agents interacting with potentially different environments, little to nothing is known about the effect of heterogeneity. This is the gap we seek to fill with our work.
The recent survey paper (Qi et al., 2021) describes federated reinforcement learning (FRL) framework which incorporates some of the key ideas from FL into reinforcement learning (RL); applications of FRL in robotics (Liu et al., 2019), autonomous driving (Chen et al., 2015), and edge computing (Wang et al., 2019) are discussed in detail in this paper. As RL algorithms often require many samples to achiove acceptable accuracy, FRI aims to achieve sample-ffieienee by leveraging information from multiple agents interacting with similar environments. Importantly, as in standard FL, the FRL framework requires agents to keep their raw data (c.g., rewards, states, and actions) private, and adhere to stringent communication constraints.
Motivation and Scope of this Work. While FRL is a promising idea, in reality, it will rarely be the case that different agents end up interacting with eaactly the same environment. Unfortunately, this is the running assumption in almost all multi-agent RL (MARL) and FRL works (Doan et al., 2019; Liu & Olshevsky, 2021a; Khodadadian et al., 2022; Shen et al., 2023). Departing from this somewhat unrealistic yet prevalent assumption, the main motivation of this paper is to build a systematic theoretical framework for reasoning about what to expect when one mixes information from non-identical Markov processes. The nature of this question is fundamental, and while we motivate its study from the perspective of FRLL, it can just as casily be connected to stochastic control and estimation problems where one socks to "fuse" data generated from non-identical dynamical systems with noisy inputs (Wang et al., 2022b; Guo et al., 2023; Xin al,, 2023).
Just as statistical heterogeneity a major challenge in Fl., envirommental heterogenesty is identified key open challenge in FRL (Qi al., 2021).
2

---

Published in Transactions on Machine Learning Research (06/2024)
To initiate principled study of heterogeneity in FRL, focus on the simplest RL problem, namely policy evaluation. Our setup involves N agents where each agent interacts with an environment modeled as a MDP. The agents' MDPs share the same state and action space but have different reward functions and state transition kernels, thereby capturing environmental heterogencity. Each agent seeks to compute the discounted cumulative reward (value function) associaled with a common policy μ.. Notably, the value functions induced by i may differ across environments. This leads to the central question we investigate: Can an agent expedite the process of learning its own value function by leveraging information from potentially different MDPs? As explain shortly, this is a non-trivial question to answer even for policy evaluation; hence, our focus on policy evaluation as a starting point. That said, recent works have shown that with minor modifications to the analysis of TD learning for policy evaluation (Srikant & Ying, 2019), one can analyze Q-learning for control (Chen et al., 2019). As such, we envision that the developments in this paper can be suitably extended to control algorithms like Q-learning as well.
A typical application of the above FRL setup is that of an autonomous driving system where vehicles in different geographical locations share local models capluring their learned experiences to train a shared model that benefits from the collective exploration data of all vehicles. The vehicles (agents) essentially have the same operations (e.g., steering, braking, accelerating, etc.), but can be exposed to different environments (e.g., road and weather conditions, routes, driving regulations etc.).
1.1 Our Contributions
We study a federated version of the temporal difference (TD) learning algorithm TD(O) (Sutton, 1988). The structure of this algorithm, which we call FedTD(()), is follows. At cach iteration, cach agent plays an action according to the policy μ,, observes reward, and transitions to a new state based on its own MDP. It then uses TD()) with linear function approximation to update local model that approximates its own value function. To benefit from other agents' data in a communcctioon-efieeee synchronizes with a central server, and performs multiple local model-updates in between as depicted in Figure 1. Notably, as in FL. agents only exchange models but never their personal observations. We perform a comprehensive analysis of FedTD(O) under environmental heterogeneity, and make the following contributions:
manner, each agent periodically
1. Effeet of heterogeneity on TD(O) fixed points. Towards understanding the behavior of FedTD(O), we start by asking: How does heterogeneity in the transition kernels and reward functions of MDPs manifest into differences in the long-term behavior of TD(O) (with linear function approrimation) such MDPs? Theorem 1 provides an answer by characterizing how perturbing a MDP perturbs the TD(O) fixed point. for that MDP. To arrive at this result, we combine results from the perturbation theories of Markov chains and linear equations. Theorem 1 establishes the first perturbation result for TD(O) fixed points, and complements results of a similar flavor in the RL literature, such as the Simulation Lemma due to Kearns & Singh (2002). As such, Theorem 1 can serve as a tool of independent interest. in RT.
2. The Virtual MDP framework. In FL algorithms such FedAvg, the average of the negative gradients of the agents' loss functions drives the iterates of FedAvg towards the minimizer of a global loss function. In our setting, there is no such global loss function. So by averuging TD(O) update directions of different MDPs, where do we end up? To answer this question, we construct a virtual MDP Section 3.1, and characterize several important propertics of this fictitious MDP that aid our subsequent analysis. Along the way, we derive a simple yet key result (Proposition 1) pertaining to convex combinations of Markov matrices associated with aperiodic and irreducible Markov chains. This result appears to be new, and may be of independent interest.
3. Linear Speedup under Markovian Sampling and Hctorocgenity. Our most significant contribution is to provide the first analysis of a fealerated RL algorithm, FedTD(O), that simultaneously accounts for linear function approzimation, Markovian sampling, multiple local updates, and hetero- geneûty. In Thcorem 2, we prove that after T communication rounds with K local model-updating steps per round, (o) guarantees convergence at a rate of ((1/NTT) to a neighborhood of each agent's 's optimal parameter. The size of the neighborhood depends on the level of heterogeneity in the
3

---

Published in Transactions on Machine Learning Research (06/2024)
agents' MDPs. The key implication of this result is that in low-heterrgenccity regime, each agent can enjoy an N-fold linear speed-up in convergence via collaboration, and converye quickly to a vicinily of its own optimal parameter. One can view this as a "coarse tuning phase". As is typically done in FL (Collins et al., 2022), each agent can use the solution of FedTD(O) to then finc-tune (personalize) based on its own data. This is visually illustrated in Figure Theorem significant in that it is the first result in FRL that complements the myriad of federated optimization results that account. for the effects of heterogeneity (Sahu et al., 2018; Khaled et al., 2019; 2020; Li et al., 2019; Koloskova et al., 2020; Woodworth et al., 2020b; Malinovskiy et al., 2020; Pathak & Wainwright, 2020; Wang et al., 2020; Karimireddy et al., 2020b; Acar et al., 2021; Gorbunov et al., 2021; Mitra et al., 2021; Mishchenko et al., 2022).
4. Novel Proof Framework. One might be tempted to think that the proof of Theorem 2 is simple combination of the standard FedAvg analysis with that of TD learning. We briefly explain here why this isn't quite the case, and defer a more elaborate explanation to Section 5.1. First, in the centralized TD analysis (Bhandari et al., 2018; Srikant & Ying, 2019), and in the existing analysis for MARL/FRL (Doan et al., 2019; Liu & Olshevsky, 2021a; Khodadadian et al., 2022) with identical MDPs, the dynamics of the update rules correspond to one single MDP. In our selup, the dynamics of (O) may not correspond to any MDP at all! Thus, we need new tools relative to existing RL analyses. Second, while cxisting FL analyses are esscntially distributed optimization proofs, federaled TD learning does not correspond to minimizing any fixed loss function. Moreover, unlike the ii.d. data model in FL, the data tuples observed by each agent in FedTD(O) are part of a single Markovian trajectory. This creates complex time-correlations that are challenging to deal with even in a singlo-agent setting. Thus, we cannot directly employ FL proofs either. As such, we introduce a new analysis framework where we argue that the dynamics of FedTD(O) can be approximated by that of (D) on virtual MDP, up an error term that captures heterogeneity in the agents' MDPs. Carefully tracking how this crror term propagates over time accounts for the effect of heterogencity; establishing linear speedup under Markovian sampling and local steps requires much more work.
Bias introduced by Heterogeneity. Our convergence result in Theorem features a bias term due to heterogeneity that cannot be eliminated even by making the step-size arbitrarily small. Is such term unavoidable? We explore this question in Theorem 3 by studying "steady-state" deterministic version of FodTD(O). Even for this simple case, we prove that a bias term depending on natural measure of heterogeneity shows up inevitably in the long-term dynamics of FedTD(O). This result sheds further light on the effect of heterogeneity in FRL.
1.2 Related Work
In what follows, we discuss the most relevant threads of literature.
Finite-Time Analysis of TD Learning Algorithms. In their seminal paper, Tiitsiklis & Van Roy (1997) provided an asymptotic convergence analysis of the temporal difference (TD) learning algorithm (Sutton, 1988; Sutton et al., 1998) with value function approximation, using tools from stochastic approximation theory. Several years later, the work by Korda & La (2015) provided finite-time rates for TD learning. However, the authors in Narayanan & Szepesvári (2017) noted some issues with the proofs in Korda & La (2015). Under the i.dd. observation model described in Section 5, Dalal et al. (2018) and Takshminnraaaaaa & Szepesvári (2017) were able to resolve the issues in Korda & La (2015). Even so, non-asymptotic convergence analysis for the challenging Markovian setting (that we consider in this paper) remained elusive till the work by Bhandari et al. (2018). While the authors in Bhandari et al. (2018) made some elegant connections between the dynamics of TD learning and gradient descent, an alternative proof technique using Stein's 's method was developed by Srikant & Ying (2019). Yet another interesting interpretation was provided by Liu & Olshevsky (2021b): they argued that the steady-state temporal difference direction acts as a "gradient-splitting" of an appropriately chosen function. Recently, a short proof of TD learning with linear function approximation and more general nonlinear contractive stochastic approximation schemes was provided by Mitra (2024) based on novel inductive proof technique. While all the
4

---

Published in Transactions on Machine Learning Research (06/2024)
above works provide upper-bounds for the task of policy evaluation, for minimax lower bounds, we refer the reader to the work of Khamaru et al. (2021).
2. Multi-Agent and Federated RL. In Doan et al. (2019) and Liu & Olshevsky (2021a); the authors analyze multi-agent TD learning with linear function approximation over peer-to-peer networks. Neither approach accounts for local steps or Markovian sampling. In Shen et al. (2023), the authors study a parallel version of asynchronous actor-critic algorithms, and establish a linear speedup result- albeit under an i..d. sampling assumption. Very recently, the authors in Khodadadian et al. (2022) and Dal Fabbro et al. (2023) studied the effect of Markovian sampling for federated TD learning. However, all of the above papers consider homogeneous setting with identical MDPs for all agents. In contrast, our work has to lackle the challenge of understanding the long-term effects of miring TD update directions from non-identical MDPs. The only two papers that perform any thcoretical analysis of heterogencity in FRI are Jin et al. (2022) and Xic & Song (2023). However, their analyses are limited to the much simpler tabular setting with no function approximation. In particular, the work of Xie & Song (2023) only comes with asymptotic results, Le., they do not provide finite-time rates. Moreover, unlike us, neither Jin et al. (2022) nor Xie & Song (2023) provide any explicit linear speedup result. In conclusion, we are the first to establish finite-time theory for FRI, under function approximation, environmental heterogeneity, and Markovian sampling. Considering different scttings, Zhang et al. (2024) proposed the FEDSARSA algorithm to solve the on-policy FRL problem and Wang et al. (2023) proposed FedLQR to solve the federated control design problem. A more detailed description of related work on federated learning is relegated to the Appendix.
aware of
2 Model and Problem Formulation
We consider a Markov Decision Process (MDP) (Sutton et al., 1998) defined by the tuple M A, where S is finite state space of size n, AA is a finite action space, P is a set of action-dependent Markov transition kernels, R is reward function, and y E (0, 1) is the discount factor. We consider the problem of evaluating the value function V of given policy μ, where μ. S - A. The policy μ induces Markov reward process (MRP) characterized by a transition matrix PH,, and a reward function Ry Under the action of the policy al an initial state 8, Pa(s, s') is the probability of transitioning from state 8 to state 8', and (s) is the expected instantaneous reward. The discounted expected cumulative reward obtained by playing policy a starting from initial state s is:
vs(() = E
Σ y Ra (5t) =
where st is the state of the Markov chain time From Tsitsiklis & Van Roy (1997), we know that Vn is the fixed point of the policy-specifie Bellman operator Tu R. R." ie., V,VV Vy,, where for any V RR".
(s) = (s) +Y Σ Pa(s, s')''s YsES. S'ES
TD learning with linear function approximation. We consider the setting where the number of states is very large, making it practically infeasible to compute the value function V2 directly. To mitigate the curse of dimensionality, common approach (Sutton et al., 1998) is to consider a low-dimensional linear function approximation of the value function Vy, Let {4 be a set of d linearly independent basis vectors in R", and & E Rxdd be a matrix with these basis vectors as its columns, i.e., the k-th column of $ is dx- A parametric approximation Vo of Vn in the span of {# is then given by v== Φ0, where E Rd is a parameter vector to be learned. Notably, this tractable since d & n. We denote the s-th row of t by d(s) E Rd, and refer to it the fixed feature vector corresponding to state s. We write Vo(s) = ((s) 0 and make the standard assumption (Bhandari et al., 2018) that [|o(s)]l2 < 1, e S.
The objective is to find the best lincar approximation of Vr in the span of {0x More preciscly, we seek a parameter vector 0t that minimizes the distance between Vo and Vp (in suitable sense). When the underlying
5

---

Published in Transactions on Machine Learning Research (06/2024)
MDP is unknown, one of the most popular techniques to achieve this goal is the classical TD(0) algorithm. TD(O) starts from an initial guess 0n E Rd. Subsequently, at the 1-th iteration, upon playing the given policy μ, a new data tuple O = (st, r2 = (st), s(41) comprising of the current state, the instantaneous reward, and the next state is observed. Let us define the TD(O) update direction as (e(O,) - (re + To (8(+1)* 0r - & (8))
TT)Too 0z) $ (8))-
Using a step-size at E (0, 1), the parameter 0, then updated as
0 0, + (g.)
Under some mild technical assumptions, it was shown in Tsitsiklis & Van Roy (1997) that the TD(O) iterates converge asymptotically almost surely to a vector 0", where 0* is the unique solution the projected Bellman oquation T ($6*) ($6*) = $0" Here, D diagonal matrix with entries given by the clements of the stationary distribution π of the Markov matrix Py. Furthermore, [+)() is the projection operator onto the subspace spanned by { with respect to the inner product (s, D..
Objective. We study multi-agent RL problem where agents interact with similar, but non-identical MDPs that share the same state and action space. All agents seek to evaluate the same policy, Our goal is to understand: Can an agent evaluate the value function of its own MDP in a more sample-efficient way by leveraging dala from other agents? Existing FL analyses that study statistical heterogeneily in supervised learning/empii empirical risk minimization fall short of answering this question, since our problem does not involve minimizing a static loss function. As such, the question we have posed above is non-trivial, and requires several new ideas and tools. In the next section, we will start building these tools in systematic manner by accomplishing the following goals.
Goal 1. Formally defining what we mean by model heterogeneity in the agents' MDPs.
Goal 2. Characterizing how such model heterogeneity translates to differences in the fized points of the TD(0) algorithm when run on the agents' MDPs.
Goal 3. Introducing the notion of a virtual MDP that will play a crucial role in reasoning about the long-term behavior of algorithms that combine information from non-identical MDPs.
3 Heterogeneous Federated RL
We consider federated RL setting comprising of N agents that interact with potentially different environments. Agent i's environment is characterized by the following MDP: M = (S, (,()), R()) ()) While all agents share the same state and action space, the reward functions and state transition kernels of their environments can differ. We focus on a policy evaluation problem where all agents seek to evaluate a common policy μ that induces N Markov reward processes characterized by the tuples {P((), .RS.) hE[N].3 Agent i aims to find a linearly parameterized approximation of its own value function V/(0, Trivially, agent can do so without interacting with any other agent by simply running TD(O). However, the key question we ask pertains to the value of side-information: By using data from other agents, can achieve desired level of approzimation with fewer samples relative to when it acts alone? Naturally, the answer to the above question depends on the level of heterogeneity in the agents' MDPs. Accordingly, we introduce the following definitions.
Assumption 1. (Markov Kernel Heterogeneity) There crists an >> 0 such that for all agents i,j E [N), il holds that (x)) p (x, s')l < (( (s, s')), Vs, s' E S. Here, for each i E [N], p(0 8') represents the ('tth element of the matrix p(o)
Assumption 2. (Reward Heterogeneity) There exists an E > 0 such that for all i, E [N], it holds that |R(0 - R <1
Clearly, smaller values of e and e capture more similarity in the agents' MDPs. Suppose all agents can communicate via a central server. Via such communication, the standard FL task is to find one common
WW will use I|D to denote the norm induced by the matrix D, and || || to represent the standard Euclidean norm for vectors and & induced norm for matrices. We will henceforth drop the dependence of p(i) and R(0 on the policy p-
6

---

Published in Transactions on Machine Learning Research (06/2024)
model that "fits" the data of all agents. In similar spirit, our goal is to find common parameter @ such that Vi $0 approximates each Vi"", i E [N]. The role of this common 0 will be to quickly (i.c., by leveraging samples of all agents) provide a coarse model that the agents can then use as a warm-start to fine-tune based on personal data. There is natural tension here. While federation can help converge faster to coarse model, such model may not accurately capture the value function of any agent if the agents' MDPs are very dissimilar. So does more data help or hurt?
Impact of Hotcrogencity on TD fixed points. To answer the above question, we need to carcfully understand how the structural heterogeneity assumptions on the MDPs (namely, Assumptions 1 and 2) manifest into differences in the long-term dynamics of TD()) on these MDPs. Since long-term dynamics are intimately tied to fixed points, we first set out to characterize the "closeness" in TD(O) fixed points across different MDPs. To proceed, we make the following standard assumption.
Assumption 3. For each i E [N], the Markov choin induced by the policy μ, corvesponding to the state transition matrir p(),, is aperiodic and irreducible.
The above assumption implics the existence of unique stationary distribution o( for each i E [NT] let D be a diagonal matrix with the entries of (1) on its diagonal. For each agent i, we then use 0ī to denote the solution of the projected Bellman equation D (007) = Φ0; for agent i. In words, 07 is the best
linear approximation of (8) in the span of [o From Section 2, we know that the iterates of TD(O) agent i's MRP will converge to 0; asymptotically almost surely. Our goal is to bound the gap 10; - as a function of the heterogeneity parameters e and é1 appearing in Assumptions 1 and 2. The key observation we will exploit is that for each i E [N], 0: is the unique solution of the linear equation A,0; = 6,, where and b; = " (((), For an agent j * i, viewing A, and by as perturbed versions
A, = T (0 of A, and b,. we can now appeal to results from the perturbation theory of linear equations (Horn & Johnson, 2012a, 2a, Chapter 5.8) to bound |10-- 07 To that end, we first recall result from the perturbation theory of Markov chains (O'cinneide, 1993) which shows that under Assumption 1, the stationary distributions x(1) and T(5) are close for any pair i,j E [N].
Lemma 1. (Perturbation bound on Stationary Distributions) Suppose Assumption 1 holds. Then, for any pair of agents i,j E [N), the stationary distributions T(() and n()) salisfy:
| 700 S 2(n 1.an-11p1 1)e 0
(1)
We will now use the above result to bound || Á and 1 - by]l- To state our results, we make the standard assumption that for each i E [N], it holds that (s)) I Rmax. Vs E S, i.., the rewards are uniformly boundod. In (Tsitsiklis & Van Roy, 1997), was shown that -A, negative definite matrix; thus, 38, > 0 such that || 2 51, Vi E [N]. We also assume that Edg such that [ ò2, Vi E [N]. In our first technical result, stated below, we provide bound on the perturbation of TD fixed points.
Theorem 1. (Perturbation bounds on TD(O) fixed points) For all i,j E [N], we have:
1. | A,l S A(e) A T/TT (1 + 7) (2(n - 1)e + 0(2))
2. |b6, 6, s E(E, Rmax (2(n - 1)e + 0(2)) + (Ee))
3. Suppose 3H > 0 s.l. 10:1 < H, E [N]. Let k(As) be the condition reumber of A.. Then:
A(AHH
(A(c)
b(e,
100 - 07 $ T(g A max
(E(N] 1- x(A,)
Alc) 81
82
61
Discussion. Theorem reveals how heterogeneity in the rewards and transition kernels of MDPs can be mapped to differences in the limiting behavior of TD(O) on such MDPs from a fixed-point perspective. It formalizes the intuition that if the level of heterogeneity as captured by and 61 is small, then so is the
7

---

Published in Transactions on Machine Learning Research (06/2024)
gap in the (D( limit points of the agents' MDPs. This result is novel, and complements similar perturbation results in the RL. literature such as the Simulation Lemma (Kearns & Singh, 2002). .
In what follows, we will introduce the key concept of a virtual MDP, and build on Theorem 1 to relate properties of this virtual MDP to those of the agents' individual MDPs.
3.1 Virtual Markov Decision Process
In standard FL. setting, the goal is to typically minimize a global loss function ([x)=((/N)) EN fi(x)) composed of the local loss functions of N agents; here, fi(x) is the local loss function of agent In FL, due to helerogeneity in the agents' loss functions, there is a "drift" effect (Charles & Konečný, 2020; Karimireddy et al., 2020b): the local iterates of each agent drift towards the minimizer of fx()). However, when the heterogeneity is moderate, the average of the agents' iterates converges towards the minimizer of f(x). To develop an analogous theory for FRL, we need to first answer: When we average TD(O) update directions from different MDPs, where does the average TD(O) update direction lead us? Tt precisely to answer this question that we introduce the concept of a virtual MDP. To model a virtual environment that captures the "average' of the agents' individual environments, we construct an MDP M (S, R, P,,) 7), where P = (1/N) i= p(9, and R = (1/N) N R(,, Note that the virtual MDP is a fictitious MDP that we construct solely for the purpose of analysis, and may not coincide with any of the agents' MDPs, in general.
Properties of the Virtual MDP. When applied to M, let the policy j that we seek to evaluate induce virtual MRP characterized by the tuple {P, R). It is easy to see that p= (1/N) p((), P(o), and R (1/N) E R00 The following result shows how the virtual MRP inherits certain basic properties from the individual MRPs; the result is quite general and may be of independent interest.
Proposition 1. (Convex combinations of Markov matrices) Let {p()) be a set of Markov matrices associated with Markov chains that share the same states, and are each aperiodic and irreducible. Then, for any set of weights {w; N satisfying w; 2 0, Vi e [N] and ΣiEiN] uh 1, the Markov chain corresponding to the matriæ Σiein w;P( is also aperiodic and irreducible.
The above result immediately tells that the Markov chain corresponding to P is aperiodic and irreducible. Thus, there exists an unique stationary distribution मे of this Markov chain; let D be the corresponding diagonal matrix. As before, let us define À A & -Po), b A + DR, and use 0 to denote the solution to the equation A = b. Our next result a consequence of Theorem 1, and characterizes the gap between 0: and 0*, for each i E [N].
Proposition 2. (Virtual MRP is "close" " to Individual MRPs) Fix any E [N]. Using the same definitions as in Theorem 1, we have ||A - All S A(e), 1b,, - bll s b(e,e1) and 110; - 0 < ((e,
We will later argue that the federated TD algorithm (to be introduced in Section 4) converges to a ball centered around the TD(O) fixed point H of the virtual MRP. Proposition 2 thus particularly important since it tells us that in a low-hetcrogencity regime, by converging close to 8", we also converge close the optimal parameter 0 of each agent i. This justifies studying the convergence behavior of FedTD(O) on the virtual MRP. Define E., A T DΦ. The smallest eigenvalue of this matrix will end up dictating the convergence rate of our proposed algorithm. We end this section with a result showing that this eigenvalue is bounded away from zero.
Proposition 3. For the virtual MRP, it holds that Xmax (Ev) S 1, and 3 @ > 0 s.t. Amia (E.) 2 w.
4 Federated TD Algorithm
In this section, we describe the FodTD(() algorithm (outlined in Algorithm 1). The goal of FedTD is to
generate model 0 such that VU is good approximation of each agent i's value function (i( corresponding
"The simulation lemma tells us that if two MDPs with the same state and action spaces are similar, then so the value functions induced by common policy on these MDPs.
8

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm 1 Description of Fod
(t) Input: Policy 14, local step-size ot, global step-size 0g that depends on communication round / (f)
2: Initialize: 0o = 0g and $0.0 so, Vi E [N]
3: for each round t = ...... T - do
4: for each agent E [N] do
for k = 0.... K - 1 do with initial model 0g00 = 0z
5:
Agent: i plays n m()).)) observes O (8t,k) 1, s1,t1), and updates local model:
(6) (8) (6)
6:
01 0 + alg.(0 where ( & (rik + + To - (s())) TO o(s
7: end for
Agent i sends 4 0 0, back the server
end for
10: Server broadcasts the following global model: 01+1 10, + (N/ (N)NNN EIE(N (00)
11: end for
to the policy μ.. In line with both standard FL algorithms, and also works in MARL/FRL (in homogeneous settings) (Doan et al., 2019; Khodadadian et al., 2022), the agents keep their raw observations (i.e., their rewards, states, and actions) private, and only exchange local models. In each round 6, each agent i E [N] starts from common global model 0, and uses its local data to perform K local updates of the following form: at each local itcration k, agent takes action ((s(,)) and observes a data tuple 0 based on its own MRP, i.e, {P(), ] we note here that observations are independent across agents. Using its data tuple, agent i then updates its own local model ((3) along the direction gi (0())) in line 6. Since each agent seeks lo benefit from the samples acquired by the other agents, there is intermittent communication via the server. a key concern in FL. As
However, such communication needs to be limited as Communication-effiieeee such, the agents upload their local models' difference A, to the server only once every K time-steps. The server averages these model differences and performs a projection to construct a global model 0.+1 that is then broadcast to all agents (line 10). Here, we use (-) to denote the standard Euclidean projection on to a convex compact subset H. C Ed that is assumed to contain each 07, E [.V] and also l*, Such a projection step ensures that the global models do not blow up, and is common in stochastic approximation (Borkar, 2009) and RL (Bhandari al., 2018; Doan et al., 2019). Each agent then resumes its local updating process from this global model.
We note that the structure of FedTD(O) mirrors that of FedAvg (and its many variants) where agents perform multiple local model-updates in isolation using their own data (to save communication), and synchronize periodically via a server. However, there are signíficant differences in the dynamics of standard FI. algorithms and Fo)TD(O), making it quite challenging derive finite-time convergence results for the latter. In the next section where we analyze FedTD(O), we will explain the nature of these challenges, and discuss how we overcome them.
5
Main Result and Analysis
To state our main convergence result. for FedTD(O), we need to introduce a few objects. First, let H denote the radius of the set H. in line 10 of Algorithm 1. Also, define & Rmax + 2H and v ê (1-7)w, where w is as in Proposition 3. In our analysis, we will make use of the geometric mixing property of finito-state, aperiodic, and irreducible Markov chains (Levin & Peres, 2017). Specifically, under Assumption 3, for each E [N], there exists some m, 2 and Pi (0,1), 1), such that for all t and 0 k K-1:
drv (P(5 = -1000 =x))) (0) < mipt IK+ Vs E.
9

---

Published in Transactions on Machine Learning Research (06/2024)
Here, we use drv (P, Q) to denote the total-variation distance between two probability mcasures P and Q. For any 8 > 0, let us define the mixing time for p(t) as (z) _ min (t E No mapf I {J. Finally, let T(E) max (e) represent the mixing time corresponding to the Markov chain that mixes the slowest. As one might expect, and as formalized by our main result below, it is this dowest-mixing Markov chain that dictates cerlain terms in the convergence rate of FedTD(O).
Thcorem (Main Result) There erists a decrensing global step-size sequence {ag"), a fixed local step-size 0n, and set of conver weights, such that a convee combinalion Ör of the global models {0,} salisfies the following for each agent i E [N] after T rounds:
Vor Vo: 12] = ( K2 (quad(T)
(
+ (Un(T) 22NKT a AKT2 + Q(c.a)).
E
K2T2 +
where T [ (a oT Kaja (T), and (quad(T) and (T)(() are quadratic and linear functions in T, respectively. Moreover, E1) H (Vne + 2(n - 1)e + O(2)) + O(e)), e(), is as defined in Theorem 1, and Q(c, Õ B( + ())
The proof of the above result is deferred to Appendix I. We now discuss its impplications.
Discussion. To parse Theorem 2, let us start by noting that the term ((,,G) in Eq. (2) captures the effect of heterogeneity; we will comment on this term later. When T > N, the dominant term among the first three terms in Eq. (2) is Equad (T) To appreciate the tightness of this term, we note that in a centralized setting (i.c., when N = 1), given access to KT samples, the convergence rate of TD(O) is 0(1((r"KT)) (Bhandari et al., 2018). Our analysis thus reveals that by communicating just T times in KT iterations, each agent can achieve a linear speedup w.r.l. the number of agents. In a low-heteeogenneity regime, i.e., when E1) is small, we note that by combining data from different MDPs, FodTD(O) guarantees fast convergence to model that is good approximation of cach agent's 's value function; by fast, we imply N-fold speedup over the rate each agent would have achieved had it not communicated at all. Thus with little communication, FedTD(O) quickly provides each agent with good model that it can then fine-tune for personalization. Theorem 2 is significant in that it is the first result of its kind in MARL/FRL with heterogeneous environments, and complements the numerous analogous results in heterogeneous federated optimization (Sahu et al., 2018; Khaled el al., 2019; 2020; La et al., 2019; Koloskova et al., 2020; Woodworth et al., 2020b; Malinouskiy et al., 2020; Pathak & Wainwright, 2020; Wang et al., 2020; Karimireddy et al., 2020b; Acar el ul., 2021; Gorbunov el ol,, 2021; Milra el al, 2021; Mishchenko et al., 2022).
When all the MDPs are identical, ((c,61)= = 0. But when the MDPs are different, should we expect such a term? To further understand the effect of heterogeneity, it suffices to get rid of all the randomness in our setting. As such, suppose we replace the random TD(O) direction (:(!!)) of each agent i in Algorithm 1 by its steady-state deterministic version (((()) be A. where A; and by are as in Section 3. We call the resulting deterministic algorithm mean-path FodTD(O). For simplicity, we skip the projection step. In our next result, exploit the alfine nature of the steady-state TD(O) directions to characterize the ellect of heterogeneity in the limiting behavior of (0).D(O).
T,k.
Theorem 3. (Heterogeneity Bias) Suppose N = and K = 1. Let the step-size a = agay be chosen such that I I- a is Schur stable, where À = (A1 + A2) /2. Define es, a 0, - 0; E {1, The output of mean-path FeaTD(O) then satisfies:
lim G1 1-000
A
1 A 12 - 05); lim 62 A A 07) _
(3)
Discussion: For the setting described in Theorem 3, the mcan-path FedTD(O) updates follow the determin- istic recursion d,+1 = (I - aA)0, + ab, where b b= (1/2)(b, + b2). This is a discrete-time linear time- invarinaaiann system (LTT). The dynamics of this system are stable if and only if the state transition matrix (I - aA) is Schur stable, justifying the choice of a in Theorem 3. The main message conveyed by this result is that the gap between the limit point of mean-path FedTD(O) and the optimal parameter 0f of either of the two
10

---

Published in Transactions on Machine Learning Research (06/2024)
MRPs bears a dependence on the difference in the optimal parameters of the MRPs natural indicator of helerogeneily between the two MRPs. Furthermore, this term has no dependence on the step-size a, ie.,, the effect of the heterogeneity-indueer bias cannot be eliminated by making a arbitrarily small. Aligning with this observation, notice that (1),c1) in Eq. (2) is also step-size independent. The above discussion sheds some light on the fact that a lerm of the form Q(e, 61) is to be expected in Theorem 2. Notably, the bias term in Eq. (3) persists even when the number of local steps is just one, &.e,, even when the agents communicate with the server at all time steps. This is a key difference with the standard FL setting where the effect of heterogencity manifests itself only when the number of local steps K strictly exceeds 1 (Charles & Konečný, 2021; Karimireddy et al., 2020b; Mitra et al., 2021).
5.1 Main Technical Challenges and Overview of the Novel Ingredients in Our Analysis
Challenges. We summarize the major technical challenges that show up in the analysis of Theorem 2. First, the FedTD(O) update direction may not correspond to the TD(0) update direction of any MDP. This challenge is unique to our setting, and neither shows up in the centralized TD()) analysis (Bhandari et al., 2018; Srikant & Ying, 2019), nor in the existing MARL analyses with homogeneous MDPs (Doan et al., 2019; Khodadadian et al., 2022). Second, unlike standard FL analyses that deal with i.i.d. observations for each agent, our setting is complicated by the fact that each agent's data is generated from a Markov chain. Morcover, for cach agent i, the paramcter sequence ( and the data tuples {o(0} are intricately coupled. Third, the synchronization step in FedTD(O) creates complex statistical dependencies between the local parameter of any given agent and the past observations of all other agents. Fourth, controlling the gradient bias (1/NK) E Σx= (9:(0(.)) o(h) - 9. (0(2) and the gradient norm E[((/KK) E E Ek- 9i (0.2)) I requires a very delicate analysis when one seeks to establish the linear speedup property w.r.t. the number of agents N, i.e., the (as in the centralized analysis (Bhandari et al., 2018)) will not yield the linear speedup property. Finally, we need to control the "client-drift" effect due to environmental heterogeneity under the strong coupling between the different random variables discussed above.
rate. In particular, naively bounding terms using the projection radius
Our first key innovation is to build on the results in Section 3 to show that the mcan-path (stcady-state) FedTD(O) update direction (1/N) N (0) is "close" to the mean-path TD(O) update direction (0)- = b - AO of the virtual MRP we constructed in Section 3.1; here, b, A are as defined in Section 3.1. Formally, we have the following result.
Proof Sketch for Theorem
Lemma 2. (Steady-state Sgeudo-Gradiest Heterogeneity) For each 0 e H. have:
1 N
((0)
Σ
0 S B(G,G),
(4)
N
where B(c, (1) is as in Theorem 2, and g()) is the steady-state TD(O) direction of the virtual MRP.
From Bhandari et al. (2018), we know that 7(0) acts like a pseudo-gradient pointing towards the optimal model 6* of the virtual MRP. Since based on Proposition 2, we know that 0 is close to 8r, Vi E [N], Lemma tells us that at least in the steady-state, the iterates of FedTD(O) will converge to a neighborhood of each agent's optimal model, where the size of the neighborhood depends on the level of heterogencity. While this helps build intuition, all the valuable insights conveyed by Lemma 2 only pertain to the sleady state dynamics of Fe)TD(O), Le., all the statistical challenges we alluded to still need to be resolved. In particular, mentioned earlier, we cannot naively use projection bound of the form E [[1/NKK) EN EK= [(((())) = (G²) from the centralized analysis in Bhandari et al. (2018), since the local models may not belong to the set H. Also, this will obscure the linear speedup effect. We overcome this difficulty by decomposing the random TD direction of each agent i as ((() = b2(0,() t.k)
(t) - A.(0 Since A((O(.)) and b, (O())) only depend on the
randomness from the Markov chain, and GK and 0.5) are independent, we can show that the variances of (L/NK) E ( and (1/N
EN - Σk-O (0(()) get scaled down by NK (up to higher order terms). Furthermore, to account. for the fact that (O and b. (OO differ across agents, we appeal to
11

---

Published in Transactions on Machine Learning Research (06/2024)
Lemma 2. Putting these pieces together in careful manner yields the final rate in Theorem 2. The detailed analysis, along with some simulations, are deferred to the Appendix.
N 20
10'
10a
N
10
2.0
10a
3
100
10a
10"
200
400
600
1000
10a
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
t
(a) Simulations on the effect of the linear speedup
(b) Simulations on the effect of the heterogeneity level
Figure Performance of FedTD(O) under Markovian sampling. (a) Performance of FedTD(O) for varying number of agents N. The MDP M of the first agent randomly generated with a state space of size n 100. The remaining MDPs are perturbations of (1) with the heterogeneity levels 0.05 and 61 0.1. We evaluate the convergence in terms of the rumning error e; 100 011 (b) Performance of FedTD(O) for varying heterogeneity level, with fixed number of agents N = 20. Complying with theory, increasing N reduces the error, and increasing the level of heterogeneity increases the size of the ball to which FedTD(() converges. We choose the number of local steps as K = 10 in both plots.
6 Conclusion
In this work, we have studied the problem of federated reinforcement learning under environmental hetero- geneity and explored the following question: Can an agent expedite the process of learning its own value function by using information from agents interacting with potentially different MDPs? To answer this question, we studied the convergence of federated TD(0) algorithm with linear function approximation, where N agents under different environments collaboratively evaluate common policy. The main differences from the existing works are: (i) proposing new definition of environmental heterogeneity; (ii) characterizing the effect heterogeneity on TD(O) fixed points; (iii) introducing a virtual MDP to analyze the long- term behavior of the FedTD(() algorithm; and (iv) making an explicit connection bet federated reinforcement learning and federated supervised barniing/opimmizatee we proved that if the environmental heterogeneity between agents' environments is small, then FedTD(() can achieve linear speedup under both i.idd and Markovian settings, and with multiple local updates.
by leveraging the virtual MDP. With these elements,
A few interesting extensions to this work are as follows. First, it is natural to study federated variants of other RL algorithms beyond the TD(0) algorithm. Second, it would be interesting to investigate whether the personalization techniques used in the traditional FL optimization literature can applied to solve federated RL problems. Instead of learning a common value imnction/policy can we design personalized value functions/ policies that might perform better in high-heeerogeeneity regimes? We leave the exploration of this interesting question future work.
Acknowledgments
Anderson and Wang are partially supported by the NSF under awards 2144634 & 2231350 from the EPCN program.
12

---

Published in Transactions on Machine Learning Research (06/2024)
Hamed Hassani is supported by The Institute for Learning-enable Optimization at Scale (TILOS), under award number 122-
References
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. arXiv preprint or arXiv:2111.04000 2021.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approxination. In Conference on learning theory, pp. 1691-1692, PMLR, 2018.
Vivek S Borkar. Stochastic approzimation: A dynamical systems viewpoint, volume 48. Springer, 2009.
Zachary Charles and Jakub Konečný. On the outsized importance of learning rates in local update methods. arXiv preprint (xXt::207.00877: 2020.
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. 2575-2588 PMLR, 2021.
Chenyi Chen, Ari Seff, Alain Kornhauser, and Jianxiong Xiao. Deepdriving: Learning affordance for direct perception in autonomous driving. In Proceedings of the IEEE international conference on computer vision, pp. 2722-2730, 2015.
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 arXii:1905 11.9905.1122. 11425, pp. 4, 2019.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. In International Conference on Machine Learning, pp. 2089- 2099. PMLR, 2021.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. FodAvg with fine tuning: Local updates lead representation learning. arXiv preprint arXiv:2205.1360
2022.
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, 2023.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for TD(0) with function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint arXi::2003,1144 2020.
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 Learning, pp. 1626-1635. PMLR, 2019.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta-learning approach. arXiv preprint wxXv:2002.079448 2020.
Georg Frobenius, Ferdinand Georg Frobenius, Ferdinand Georg Frobenius, Ferdinand Georg Frobenius, and Germany Mathematician. Über matrizen aus nicht negativen elementen. 1912.
Avishck Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances in Newral Information Processing Systems, 11195566195999 2020.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556 3564. PMI.R, 2021.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Taosha Guo, Abed AlRahman Al Makdah, Vishaal Krishnan, and Fabio Pasqualetti. Imitation and transfer learning for LQG control. orXiv preprinl ar XiX::333300002, 2023.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arxiv preprinl Xrx 14425, 2019.
Farzin Hadradpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe, Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pp. 11082-11094, 2019.
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárík. Lower bounds and optimal algorithms for personalized federated learning. Advances in Newral Information Processing Systems, 33:2304 2315,
2020.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012a.
Roger A Horn and Charles R Johnson. Matriz anolysis. Cambridge university press, 2012b.
Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated Reinforcement Learning with Environment Heterogeneity. International Conference on Artificial 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- nalional Conference on Machine Learning, pp. 5132 5143. PMLR, 2020a.
Sai Pranceth Karimiroddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Scbastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Inter- national Conference on Machine Learning, pp. 5133-5143. PMLR, 2020b.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine
learning, 49(2))209-233) 2002.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtáríkk First analysis of local GD on heterogeneous data. arXiv preprint arXiv:1909.0 04715, 2019.
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 Wainwright, and Michael Jordan. Is temporal difference learning optimal? An instance-dependent analysis. SIAM Journal on Mathematics of Data Science, 101-1013-10400 2021.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Foderated Reinforcement Learning: Linear Speedup Under Markovian Sampling. In International Conference on Machine Learning, pp. 10997-11057. PMLR, 2022.
Anastasia Koloskova, Nicolas Loizon, Sadra Boreiri, Martin Jaggi, and Sebastian Stich, A unified theory of decentralized SGD with changing topology and local updates. arXiv preprint arXiv:2003. 104,00003...420 10422, 2020.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02227, 2016.
Nathaniel Korda and Prashanth La. On TD( with function approximation: Concentration bounds and a centered variant with exponential convergence. In International conference on machine learning, pp- 626 634. PMLR, 2015.
Yassine Laguel, Krishna Pillutla, Jerôme Malick, and Zaid Harchaoui. A superquantile approach to federated learning with heterogeneous devices. In 2021 55th Annual Conference on Information Sciences and Systems (CISS), pp. 1-6. TEFF, 2021.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Chandrashekar Lakshminarayanan and Csaba Szepesvári. Linear stochastic approximation: Constant step-size and iterate averaging. Xiv preprint arXiv: 1tt:1709.000 7799040733 2017.
David A Levin and Yuval Peres. Morkow chains and mixing times, volume 107. American Mathematical Soc., 2017.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fodavg on non-iid data. Niw preprint arXii:1907.0211 2019.
Boyi Liu, Lujia Wang, and Ming Liu. Lifelong federated reinforcement learning: a. learning architecture for navigation in cloud robotic systems. IEEE Robotics and Automation Letters, 4(4):4555 2019.
Rui Liu and Alex Olshevsky. Distributed TD(0) with almost communication. arXiv preprint
arXiv:2104.07855, 2021a.
Rui Liu and Alex Olshevsky. Temporal difference learning as gradient splitting. In International Conference on Machine Learning, pp. 6905-6999999 6913. PMLR, 2021b.
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.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient lcarning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp- 1273 1282. PMLR, 2017.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. ProxSkip: Yes! Local Gradient Steps Provably Lead to Communcatiio Acceleration! Finally! arXiv preprint ar 00X:::2202.09357, 2022.
Aritra Mitra. simple finite-time analysis of TD learning with linear function approximation. arXiv preprint 0rXiv:2403.02/77 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.
C Narayanan and Csaba Szepesvári. Finite time bounds for temporal difference learning with function approximation: Problems with some "state-of-the-art" results. Technical report, Technical report, 2017.
Colm Art O'cinneide. Entrywise perturbation theory and error analysis for markov chains. Numerische Mathematik, 65(1):109 120, 1993.
Roese Pathak and Martin J Wainwright. FedSplit: An algorithmic framework for fast federated optimization. arXiv preprint orXix:2005.0523 2020.
Hossein Pishro-Nik. Introduction to probability, statistics, and random processes. 2016.
Jiaju Qi, Qihao Zhou, Lei Lei, and Kan Zheng, Federated reinforcement learning: techniques, applications, and open challenges. arXiv preprint arXiv:2108. 2021.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fed- paq: A commuicattion-efiiient federated learning method with periodic averaging and quantization. In International Conference on Artificial Intelligence and Statistics, pp. 2021 2031. PMLR, 2020.
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 arXiv:1812.06123 3, 2018.
15

---

Published in Transactions on Machine Learning Research (06/2024)
Felix Sattler, Klaus-Robers Müller, and Wojeiech Samek. Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints. IEEE transactions on neural networks and learning systems, 32(8):3710 3722, 2020.
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEEE Transactions Signal Processing, 2023.
Artin Spiridonoff, Alex Olshevsky, and Ioannis Ch Paschalidis. Local SGD With a Communication Overhead Depending Only on the Number of Workers. arXiv preprint 2r06 02582,, 2020.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Conference on Learning Theory, pp.
PMLR, 2019.
Sebastian U Stich. Local SGD converges fast and communicates little. ar preprinl arXiv:1805.099 2018.
Lili Su, Jiaming Xu, and Pengkun Yang. Global convergence of federated learning for mixed regression. arXiv preprint Xrv:222006.0 07279, 2022.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3(1):9 44, 1988.
Richard S Sutton, Andrew Barto, et al. Introduction to Reinforcement learning. 1998.
Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33:21394 21405, 2020.
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning. IEEE Transactions on Neural Networks and Learning Systems, 2022.
John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal differeeeeeeeeeeeeeeeeeeeeeeeeee learning with function approxi- mation. In IEEE Transactions on Automatic Control, 1997.
Han Wang, Siddartha Marella, and James Anderson. FedADMM: A federated primal-dual algorithm allowing partial participation. In 2022 IEEE 61st Conference Decision and Control (CDC), pp. 287-294.. IEEE, 2022a.
Han Wang, Leonardo F Toso, and James Anderson. FedSysID: A federated approach to sample-efficint system identification. arXie preprint orXiw:2211.14895 2022b.
Han Wang, Leonardo F Toso, Aritra Mitra, and James Anderson. Model-free learning with heterogeneous dynamical systems: A federated LQR approach. arXiv preprint arXi::2308. 11748, 2023.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communiettion-effieeee SGD algorithms. arXie preprint arXiv:1808.0755 2018.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Newral Information Processing Systems, 33, 2020.
Xiaofei Wang, Yiwen Han, Chenyang Wang, Qiyang Zhao, Xu Chen, and Min Chen. In-Edge AI: Intelligentizing mobile edge computing, caching and communication by federated learning. IEEE Network, 33(5))156-16 2019.
Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMa- han, Ohad Shamir, and Nathan Srebro. Is Local SGD Better than Minibatch SGD? arXiv preprint arXiv:2002.07833, 2020a.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local SGD for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281-622 2020b.
16

---

Published in Transactions on Machine Learning Research (06/2024)
Zhijie Xie and Shenghui Song. Fedkl: Tackling data heterogeneity in federated reinforcement learning by penalizing kl divergence. TEEE Journal on Selected Areas in Communications, 41(4):1227-1242, 2023.
Lei Xin, Lintao Ye, George Chiu, and Shreyas Sundaram. Learning dynamical systems by leveraging data
from similar systems. Xin preprint orXin:2302.44344 04344, 2023.
Chenyu Zhang, Han Wang, Aritra Mitra, and James Anderson. Finite-time analysis of on-policy heterogeneous federated reinforcement learning. International Conference on Learning Representations, 2024.
17

---

Published in Transactions on Machine Learning Research (06/2024)
Contents
Introduction
1
Our Contributions
3
1.2 Related Work
2 Model and Problem Formulation
5
Heterogeneous Federated RL
6
3.1 Virtual Markov Decision Process
8
4
Federated TD Algorithm
8
Main Result and Analysis
9
5.1 Main Technical Challenges and Overview of the Novel Ingredients in Our Analysis
11
6 Conclusion
12
A Additional Literature Survey
20
B Perturbation bounds for TD(O) fixed points
21
B.1 Proof of Theorem 1
21
C Propertics of the Virtual Markov Decision Process
22
C.1 Proof of Proposition
22
C.2 Proof of Proposition 2
................................
22
C.3 Proof of Proposition 3
22
D Pseudo-gradient heterogeneity: Proof of Lemma 2
23
E Auxiliary results used in the L.I.. and Markovian settings
23
F Notation
26
G Warm-up: Analysis of FedTD under i.i.d. sampling
27
G.1 Auxiliary Jemmas for Theorem 4
27
G.1.1 Variance reduction
27
G.1.2 Per Round Progress
28
G.1.3 Drift. Term Analysis
G.1.4 Parameter Selection
32
G.2 Proof of Theorem 4
33
18

---

Published in Transactions on Machine Learning Research (06/2024)
H Heterogeneity bias: Proof of Theorem 3
35
Proof of the Markovian setting
36
I11
Outline
36
1.2
Auxiliary lemmas for Theorem 2
36
I.2.1
Decomposition Form
1.2.2
Variance Reduction.
38
Bounding E [10, 0--11²
1.2.3
40
1,2.4
Drift Term Analysis.
46
I,2.5
Per Round Progress
48
T.2.6
Parameter Selection
56
L.3
Proof of Theorem 2.
58
J
Simulation Results
60
J.1
Simulation results for the I.D. setting
60
J.2 Simulation results for the Markovian setting
61
J.3 Simulation on the effect of the heterogeneity level for the Markovian sctting.
................................
62
19

---

Published in Transactions on Machine Learning Research (06/2024)
A Additional Literature Survey
Federated Learning Algorithms. The literature on algorithmic developments in federated learning is vast; as such, we only cover some of the most relevant/representatiy works here. The most popularly used FL algorithm, FedAvg, was first introduced in McMahan et al. (2017). Several works went on to provide detailed theoretical analysis of FedAvg both the homogeneous case when all clients minimize the same objective function (Stich, 2018; Wang Joshi, 2018; Spiridonoff et al., 2020; Reisizadeh al., 2020; Haddadpour et al., 2019; Woodworth al., 2020a), and also in the more challenging heterogeneous setting (Khaled et al., 2019; 2020; Haddadpour & Mahdavi, 2019; Li et al., 2019; Koloskova et al., 2020). In the latter scenario, it soon realized that FedAvg suffers from a "client-drift" effect that hurts its convergence performance (Charles & Konečný, 2020; 2021; Karimireddy et al., 2020a).
Since then, a lot of effort has gone into improving the convergence guarantecs of FedAvg via a varicty of technical approaches: proximal methods in FedProx (Sahu et al., 2018); operator-splitting in FedSplit (Pathak & Wainwright, 2020); variance-reduucion Scaffold (Karimireddy et al., 2020a) and S-Local-SVRG (Gorbunov al., 2021); gradient-tracking in FedLin (Mitra et al., 2021); dynamic regularization in Acar et al. (2021); and ADMM in FedADMM (Wang et al., 2022a). While these methods improved upon FedAvg in various ways, they all fell short of providing any theoretical justification for performing multiple local updates under arbitrary statistical heterogeneity. Very recently, the authors in Mishchenko et al. (2022) introduced the ProxSkip algorithm, and showed that it can indeod lcad to communication savings via local steps, despite arbitrary heterogeneily.
Some other approaches to tackling heterogeneous statistical distributions in FL include personalization (Deng et al., 2020; Fallah et al., 2020; T Dinh al., 2020; Hanzely et al., 2020; Tan et al., 2022), clustering (Ghosh et al., 2020; Sattler et al., 2020; Su et al., 2022), representation learning (Collins et al., 2021), and the use of quantiles (Laguel et al., 2021).
20

---

Published in Transactions on Machine Learning Research (06/2024)
B Perturbation bounds for TD( fixed points
B.1 Proof of Theorem 1
In this section, we prove the perturbation bounds on TD(0) fixed points shown in Theorem 1. We start by observing that:
IA - A,l
| D ( - 4) - 4 DD) >
S | D (0) 7p(1) x0 D (1) - -pp)) +)+
1 D ( p)())
Db' (Ø- - x>p
$ 9 D
(T Ta
( Φ D x)
( D ( - {p Φ) - Φ D65 ( 7 1>10)
(0) 2 " (it) |9) + + D |I| - -)p(i)||
& Tvne + (1 + 7) 1)c + (())),
(5)
where (a) follows from the triangle inequality. The first term in (b) uses the fact that |0] s 1, | and
| S 1,
|p - |bأ) s v - 1oo ev pl evn.
where we use Assumption 1 in the second incquality. The second term in (b) uses the the facts that || - >P s $14 + 7, [] | < I[ D6'l s [[(() ,(,0|1,, along with Lemma
Next, bound
|
8, - ( (DD())((1))
1 R() - +D ROO + (( Rbi - DD R
| (()) RO + | D() ||| |
Sq + Rmax (2(n= - 1)c + 1)c+ 0(2)).
(6)
where use Assumption in the last inequality and follow the same reasoning used to bound Í - Azll above.
We are now ready to bound the gap between fixed points as:
|10
81 < x((a)) 10
[A Azll
| by
(7)
1 - x(A)) II -A=-A:1 A.ll
||A,||
||bll|
A
Here, we leveraged the perturbation theory of linear equations in Finally, for any || < H, we have
(Horn & Johnson, 2012b) Section 5.8.
A x(A.)
A(E))
b(e,E1)
10- 071 S (((
+
A(e) 1 1 x(A,)
81
82
hy
where we used the fact that 81 and 82 are positive constants that lower bound || and ||bl],, respoctively.
21

---

Published in Transactions on Machine Learning Research (06/2024)
C Properties of the Virtual Markov Decision Process
C.1 Proof of Proposition
Before we prove this proposition, we present the following fact from (Pishro-Nik, 2016): a Morkow matrie P is irreducible and aperiodic if and only if there crists posilive inleger k such that every enlry of the malrix pk is strictly positive, i.e., P > 0, for all s, E S.
For every Markov matrix p(t), we know that there exists such an integer K; according to the above fact and Assumption 3 in the paper. Then we define set J = {i E [M] > 0}. Since Σi=1 Wi = 1, and w; 2 0 holds for all i & [M], we know that J is a non-emply set. If we define k = min and j = arg (i then we have:
(pb)) R
w. p(O) LE[N)
Σ
wy
+
(8)
nonnogative
positive
where each entry of w/ (pD))* k strictly positive while the other matrices in the summation are non-negative. Thus, we can conclude that the Markov chain associated with the Markov matrix EiE[N] w; p(() is also irreducible and aperiodic.
C.2 Proof of Proposition 2
Following similar arguments as in Theorem 1, we bound ||A; - -All
|| All
| T D ( - -p)))) + D( - >Pb)]l
>/ D p()) PI| + |
DII -
Te + (1 + - 1)) 0 = =((e,,
(9)
where inequality (a) follows the same reasoning as (a) in (5), (b) uses the same fact as (b) in (5, and
|[]()) - Pl| S N E |l s cvn and [ D s 2(n 1)c + ((2)).
Based on the above facts: (i) | < + M S Rmaxx (ii) ( - Rll S +
||
R s e
and (iii) || D & 2(n - 1)e + ( we finish the proof by showing that ||b; - bl s b(e, To do so, we
follow the same steps as Eq. (6), and prove the bound on ||0| 0-1 by following the same analysis as Eq. (7).
C.3 Proof of Proposition
Since the virtual MDP is an average of the agents' MDPs, i..., P= 1 E p(), the virtual Markov chain is irreducible and aperiodic from Proposition The maximum eigenvalue of symmetric positive-semidefnniee matrix convex function. Then we have Amax (Φ DΦ) S EsES (m)) (o(s))(s))) E.Es
1.
To show that there exists w > such that Ami (Φ DΦ) 2 w > O, we will establish that & D& is a positive- definite matrix. Since t full-column rank, this amounts showing that D a positive definite matrix. From the definition of D, establishing positive-definiteness of D is equivalent to arguing that every element of the stationary distribution vector म is strictly positive; here, # P म. To that end, from Proposition 1, know that the Markov chain associated with P is aperiodic and irreducible. From the thcorem (Frobenius et al., 1912), we conclude that indced every entry of ă is strictly positive. If we choose w = min.es( > 0, we have Aman (Φ DΦ) 2 w > 0.
22

---

Published in Transactions on Machine Learning Research (06/2024)
D
Eseudo-gradiens heterogeneity: Proof of Lemma 2
For each 0 E H. we have:
|0(0)
1 N
Σ 31(0)
4" D 40)
1
4 T D (
( 20 -00)
N
==1
T"
D(T 20
D0)-
x" (TD())
(T
60- Φ
N
N
D
R
1
Σ
&6 - (T( T0 +0)
+%
N
N
N
j=1
j=1
N
1
D .
Σ
R
+7
1
Σ
pli)
00- $0
D(T OTT $0 +0)
N
5=1
5=1
+ D(T(00000000000000000000
20)-
D
1 40 - +0)
1 N
RGO) +
p0
-D(T 40)
N
+/N
N
j=1
( x0 - $0) - ())) ( か0
N
1 N
R(:)= R000 || +
Σ
p(i) - p(i)
10
j=1
j=1
D D |||| T 00/
RG) R1(0 ||_ +7 N
p() - p(il|(00)
1=1
N
Σ
D D(u ||||| 17:0000000 201|
1=1
El + //re |011 + [2(n - 1)e + 0(63) |000|
< HH| ((e)) vvTn + 2(n - 1)e + + ())
(10)
Inequalities (a) and (c) follow from the triangle inequality, (b) is due to || S 1; (d) is due to the fact that
||D|| < 1; and (c) uses the following facts: (i) || R|| S 61: (ii) [P() p < p(t) p()) loc 2
</]l|P())] I1 evn, which, in turn, follows from the proof of Theorem 1; (in) [ - DDI S 2(m + O
which, in turn, follows from the proof of Theorem 1 or Eq. (5); and (iv) |10]| s H for any 0 E H.
E
Auxiliary results used in the I.I.D. and Markovian settings
We make repeated use throughout the appendix (often without explicitly stating so) of the following inequalities:
Given any two vectors v,y y E RRd, for any 3 > 0, we have
(1+ 1 33 llrl..
|| + 2/1 < (1 + |1= +
(11)
23

---

Published in Transactions on Machine Learning Research (06/2024)
Given any two vectors 2, y R for any 3 0, we have
(a. v) s 9 ||:|| +
1 2 1lvl1
(12)
2
This incquality gocs by the name of Young's inoquality.
Given vectors In t Im E R the following is simple application of Jensen's inequality:
Σ 22
S
1 11
(13)
We prove the following result for the virtual MDP. Lemma 3. For any 01, 02 E R2,
(02 - 01) [g(1)) g(02)l 2 (1 (11-)) 1)/ Ve
(14)
Proof. Consider a stationary sequence states with random initial state s ā and subsoquent state s', which, conditioned on s, is drawn from P(- s). Define - ((s) and ø' a & (s'). Define X1 - (eg - Vo, (s)
(02 01) and X2 Vo, (8') Vo, (s') = (02 - 01) Φ. By stationarity, X1 and X2 are two correlated
random variables with the same same marginal distribution. By definition, E xx E [x3l since s are drawn from म. And we have,
| Vo,
- g(01) g(02) = O -1) - (0) 10--b) 02) = B - -x2)]-
Therefore,
(02 01) (5(01) 5(02)] [xx (x1 Tx2)l
E [xil ->IE [xIx2]
2 (1 7) [xil
(1 >) |loe voll1
where we use the Cauchy-Schwartz inequality to conclude E [x S EE E
Lemma 4. For any 01,05 O2 E Idd, we have
llg(01) - g((2)) s2
<2||Te. Vo. veelb:
(15)
Proof. Following the analysis of Lemma 3, have
(lg(0,) g(02)l | (x 7x2)ll
S [ E (x1 - 7xa)
E
E 12
= =1+ E Exill.
24

---

Published in Transactions on Machine Learning Research (06/2024)
where the second inequality is due to ||o]| Σ and the final equality is due to E [xi] =E [x3] We finish the
proof by using the fact that E [x]] = Voo voll l| and 1 22
With this Lemma, we next show that the stcady-state TD(O) update direction 9 and Ti are 2-Lipschitz. Lemma 5. (2-Lipschitmeess of steady-state TD(0) update direction) For any 01, 02 Rd we have
| - x(02)11 s 110 0211
(16)
And for each agent i [N], we have
(0)) - g.(02)1l 2 10 021l.
(17)
Proof. From Lemma 4, easily conclude that the steady-state TD(O) update direction for the vitual MDP is 2-pischiitz, i.e.
(lx(1)) - g(02)ll - 2 ||0] 82ll.
(18)
based on the fact that Amax (TT DΦ) & 1. We can follow the same reasoning to prove Eq. (17) since (lā:(1:) (02) 2 Vo. Vog D.
holds for each E [N] from Bhandari et al. (2018).
Next, we prove an analog of the Lipschitz property in Lemma for the random TD(0) update direction of each agent Lemma 6. (2-Lipschitemess of random TD(O) updote direction) For any 8,, 02 E Rd and E [N], we have
1g (0i) - gi (02) s 1|0 - 021l-
Proof. In this proof, we will use the fact that the random TD(O) update direction of agent al the 4-th communication round and k-th local update is an affine function of the parameter In particular, we have 9: (0) (O(.)) A:(O Thus, we have t,k)0 0, where A.(O(()) (( (o (8t 7 ( (b(k+1)) and (.(0 r (6
(s
(t)
Ig: (0,) - gs (02)l
= A:(0 (0, - 02)
(((O()) (ik) |10 - 0211
<
(1lo (st )l + 11 (st |1ø (s (st 110, 021
< 2 100 0zll,
where used that [|o(s)] 1, E S in the last step.
25

---

Published in Transactions on Machine Learning Research (06/2024)
F
Notation
For our subsoquent analysis, we will use F to denote the filtration that captures all the randomness up to the k-th local step in round L. We will also use F² to represent the filtration capturing all the randomness up to the end of round t 1-1. 1. With a slight abuse of notation, F=1 is to be interpreted as F Based on the description of FedTD(O), it should be apparent that for each [N], 0 is -eessuaareee and 0, is Fl-moasurable. Furthermore, we use E, to represent the expectation conditioned on all the randomness up to the end of round 1.
For simplicity, we define 6, = NK EE EK-1 0 0. and A. NK Ei Σk=o 0
The latter term is referred to as the drift term. Note that (o.)² A. holds for all & via Jensen's inequality. Unless specified otherwise, || denotes the Euclidean norm.
Throughout the paper, encounter three kinds of step-sizes: local step-size oy; global step-size ag. and the effective step-size Some of our results will rely effective step-sizes that decay function of the commuication round t; we will use }ar} to represent such decaying effective step-size sequence. While the local step-size will always be held constant, the decay in the effective step-size will be achieved by making the global step-size at the server decay with the communication round. Accordingly, we will use { to represent the decaying global step-size sequence at the server. In what follows, unless specified in the subscript, all the step-sizes appearing in the proofs refer to the effective step-size.
Step-size:
26

---

Published in Transactions on Machine Learning Research (06/2024)
G wprm-up: Analysis of FedTD under i.i.d. sampling
To isolate the effect of heterogeneity and provide key insights regarding our main proof ideas, we will analyze a simpler i..d. setting in this section. Specifically, we assume that for each agent i E [M,, the data tuples {0[)) are sampled i..d. from the stationary distribution x(6) of the Markov matrix p(),, Such assumption is common in the finite-time analysis of RL algorithms (Dalal et al., 2018; Bhandari et al., 2018; Doan et al., 2019). To proceed, for fixed and for each i E [M], let us define gi(0) - Bot [g:(0)] as the
iid
expected TD( update direction at itcrate A when the Markov tuple 0 hits its stationary distribution T(), We make the following standard bounded variance assumption (Bhandari et al., 2018); similar assumptions are also made FL analyses.
Assumption 4. (0) 9.(0)112 o² holds for all agents [N], in each round t and local update k, and vO.
Let H denote the radius of the set H. Also, define G - Rmax + 2H and -= (1 - y) where w is as in Proposition 3. Our convergence result for FedTD(O) in the i.i.d. setting is as follows.
Theorem 4. (I..DD. Setting) There exists decreasing global slep-size sequence {a²"), fixed local step-size on; and set of conver wrights, such that a conveex combination OT of the global models {0.} satisfies the following for each E [N] after T rounds:
E Vor - -o: 10:10 < <0
G
o²
A AKT +Q(E,Ei)):
(19)
K2T2
NNNT
and r(e, is as In what follows, we provide detailed convergence analysis of the above result.
where (1,,(1) = Ö Blean) + ((),,)))), B(e, = H (Vie + 2(n - 1)s 0(2)) defined in Theorem 1.
G.1 Auxiliary lemmas for Theorem
G.1.1 Variance reduction
Lemma 7. (Variance reduction in the i.d.d setting). In the iid. selling, under Assumplion 4, at each N E
k=0 (0(()(2)) 0:
]| s d NK-
round t, we have E
3.(0(.)) Since (0.0) is drawn ii.d. over time from its stationary distribution 700, we have (| |
Proof. Define Y.k (0
(9) Lk )
[[01 0. As we mentioned before, for cach i E [N], o()) 1,6
1,6
is measurale.... If we condition on Ft-1 know that o02 and 0g deterministic and the only randomness in y-(t) and y-(i) come from 0 and o which are independent. Therefore, y-(i) and y-0) are independent conditioncd on Fk-1-
For every * j E [N], we have
E (r y!? E |IE
[ (y 4. Xx,
(()
[
12) EE (EIY
[(lnn)]] 0,
(20)
where (a) follows from the fact that 2 and x((i) t,k
are independent conditioned on F For every < and
i E [N],
E
( 1.
E
(6)
y(())
Fh ]] E EYY Filll = 0.
[(x
(21)
t.l
Then,
N
K
E
Σ
NK
27

---

Published in Transactions on Machine Learning Research (06/2024)
N
K-1
E
1
Σ
Y
NK
N K-1
K-
EI
B
B x(y L.
N2K
t.k
N2K K2
k=0
N
(8)
+
N
1,6
w==
0²
NK
where the second equality is due to Eq. (20)) and Eq. (21) and the last inequality is due to Assumption 4. 0
G.1.2 Per Round Progress
First,, characterize the error decrease at each iteration in the following lemma.
Lemma 8. (Per Round Progress). If the local step-size og satisfies as S with any global step-size Oy satisfy
(1-7)0 48K then the updates of Fod
B110++1- 1 S (1 G) 0. 0-122 + 22 0. 00) + 6a ((oi))
4a²
S1 +6 +
1
20"0²
NK 2a + oa (G,
(22)
where Ci is any posilive constant, and a is the effective step-size, i.e., a Kantig Proof.
B100++1 - 1-11
K-1
(:(0! 0r) )( (updating rule)
12,71 =1
E
0
Σ
Σ
0r)
NK-
N K-1
$
E
+
(
g-
(projection non-expansive)
NK
1,k)
k=
N K-1
K
E||
0"
+
2E
( O2 0-) +
(0(+)) 2
NK
NK
k=
K-1
E
0.
8-
20
((
- 0r 8*)
NK
==
N K-1
N K-1
NK Σ
20
Σ
- 0*)
+E
NK ΣΣ
9 (0(00) 2
N K-1
N Ā-1
E 0 8-1
+
2x
(l ()) 0, 0r)
Σ
9 !
NK
NK
1=1
k=0
1=1
k=0
<B
<BB6
0" 1|
2x
Elg (0.0)) -0)
NK
N K-1
a N
+ 2E
a Σ
Σ
(0.(0!1)) - g. (B()))
|| + 2E
Σ
gs (,6)
|
(Young's incquality (12))
NK
NK
0=0
28

---

Published in Transactions on Machine Learning Research (06/2024)
(a)
0
0
2
N
K-
((g t,k,, 0, -00- +
20² NK
+ 2E
N
Je
(0()
NK
NK
1.k
k=0
i=1
K-1
2a
E
0
0
+
((a (.(0.) + 9.,)) g(0,) + g(0,), 0. - 07)
NK
N
K-1
20
α
2F
De
NK
2,1c
NK
0=
N K-1
N
0: 11
+
20
E L ( - (.(())) 0: - -8") +
2a
(gg g(0.), 6, 0-)
NK
N
i=1 km
1=1
0110 ||" 2020²
+ +2aB(g(O,)), 0. -0) + 2E
NK
NK
K=
$ 51+ 0, - 0r| ||
1 E
N
K-1
9. (0 - -gi(0.) I|
+ E))
C1
NK
+ +2.R(g(O.),, 02 - 0-) + 2F
a
N
K-1
3000 ||
20202
(Eq (12) and Lemma 2)
NK
NK
k=
S S1+ (1) 0. 8-1 2
4a
E E110/2
0.1"
+ +a)
LNNK
+ +2aE(g(0.), 01 8*) + 2E
a Σ
N K-1
Σ
0:(0(11) ||
+
2a²0² NK
(2-Lipschitz of g. in Lemma 5)
NK Am K=0
(1+G)BB 0. 10-000 001
4a
20
B[A.] +
+ +2aB(e,E1)G
21
NK
K-1
+ +2.B(7(0.), 02 0-) + 2F
a
( - + (0.) x(O.) + [00.) ||
NK
K=
<11+ ()) 0-| 12
4a
20
B[A.]
+ NK
+ +20B(E,E1)G
K-1
2a..gg(.), 0. 0-) 6E
(:(0(11)) Jz (0.1))
NK
K=0
N N
(..). g(0,)] 1|
+ 6E (a(B)) ||
+E
(Eq (12) and Lemma 2)
< (1 [ (1) 0. 8- 12
2 4a
2a
E[A.] + NK + +2BB(e,e)
+ +2aB(g(0i), 0 0*) + +2aa2
(2-Lipschitz of gi)
+ 6a2 (c,
+ 6a 23 ((0))
(Eq (12))
0. 8- +2 0. 8*) + 6a 2 g(0) ?
(1+(1)E)
(z +6 E[A.] +
20 + 2aB(e, - 2a B² (e,
+ 4a²
(23)
NK
where (a) is due to Lemina 7. Furthermore, the reason why Ci = 0 is as follows:
N K-1
C =
Σ Σ
E(g (,( 0, 8r)
0=0
29

---

Published in Transactions on Machine Learning Research (06/2024)
N K- 2
(0())) 3. - - (gg 1,k)
k=
(9 (K-1) - 1 0*)
K-
Egg (0())
0.(0(())0 -8-+
0=
N
Σ
E
(0: x - -11,0000,--00 [
==1
(g (0
2,(0 - -0)
K=
g: g:(0 (: 1
E
0, 0", E
i=1
N K 2
ΣΣ
Σ
(gg (0(2)
3.(6(1)) 8¹).
We can keep repeating this procedure by iteratively conditioning on Fk-2.".. Fi,
G.1.3 Drift Term Analysis
We now turn to bounding the drift term A.
Lemma 9. (Bounded Client Drift) The drift term D. at the t-th round can be bounded
N K-1
00 - 0.1' s 27 + (e,e)) + 2KG
a²
E E
(24)
NK
Koy
provided the fixed local step-size ay satisfies og S min (1-7)
48K
Proof.
((0) 0.1
E8
1.
E 000 + (0 (0 - 0.l2 (updating rule)
E
0 1 + ag (0 ))- - 0. + a (n:0((1))) F. (0
(6--1) ) 2
(1-1)
E ((0 1--- + aig (0 - - a.l' + 1. 1) ( 16112-1111 1>1
E (9x(0 D: (0.2 1), 010 x + ang (0.2 - O, F [b
+ 20, E
C==0
(4)
< (1 (2) 1012 + a - 0.1
2
JajE g00021)))))))))))0))) - T. (0
+ (1 +
+ +afE (0() (0(1))) (0(+)) (1) |
(1+ + |E 102h + cn (1) - 02 - (0)
30

---

Published in Transactions on Machine Learning Research (06/2024)
+(1+ (2+ 1
33
+(1 1
JapE 1 - g(())) - -((.) - Bi(()) + +g.(0)) - -. 1,6-11) ||
+ ajjo
(1+ + [3)
( - 0 - -aig(t))
+ (1 (1( 5o Ja o(b)) 2
+3(11 + _
Jof B
(1) GK-
/0011| -
+3(1-
| (..0))
"
+3(1 + 8 (0)) - 30000 | || 2 - aaf²
3
(4)
x (1+ + (s) [1 - (2ar(1 - 7) - 4af) EE (,k-1 - 0/ ||?
1
- )ap ((..) ||
+1+ (1) +
2,
+ +12(1
1
Jaf (00
0.11
+ +311 + C.2 Jaj (E
1
+ +12(1+ +
aaf
0 12211 - 0.1
+ tajo²
24(1+ + ) (1+ (2)
E8 0000000 1 0.1 ||
(1+ +1++s)) (s))
1 (2ar(1 - 7) 4a² +
(1 + (1 + 3. JatB b(0i)| ||
1 B2, e1) + afj0²
+ +3(1 +
G3
where we used the incquality in Eq (11) with any positive constant C2 for (a); for (b), we used Assumption 4 and the same reasoning as Eq (11) with any positive constant Ca; for (c), we used the inequality in Eq (13) to bound the third term; and for (d), we used Lemma and Lemma 4 to bound the first term, the 2-Lipschitz property of 9. P. (i.c., Lemma 5) in the third term and the fifth term, and the gradicnt heterogeneity bound
3x(++g)oo 1 - (20n(1 7) -aa)) + (1+30)1((3)
from Lemma. 2 in the fourth term. If we define C4 A + (2)(1) +1) Ca)
and define Dj as above, we have that
B 11002 0.1" s 0 - 0.l'² + +DI. Di.
(25)
Next, we set C2 = S3 = R-., K 2 2, and choose the local step-size aç to satisfy
on (1 (1
2 4afa & ar(1-7)8
24 + 2 )af (1+
2
2
so that 1- (2ar(1 - 7) 4a p + (I+c))(+<a)
S a1(1 - 7)) These inequalities hold when or S
min
(l-))w 48k
Then, Eq (25) becomes
E (
8.
1| S (1+
((() t, - 0.|2 + +D, K K-1 )1 a, - (1 [
3
If we unroll this recurrence above, using g(6) = fr, we have that
S A-1
E
2 Di
0.
Σ
1--1 (1 +
j=o+1 K - (1 a(1 - ->)0ā}
t.k
0f2 + 3K (E, +2 KE + ((00))
31

---

Published in Transactions on Machine Learning Research (06/2024)
3
11 k-
j=s+1 (1 +
K K-1 [11 an(1 7
ai0² 2 + 3a K KB (c, (1) + 20 KTE ((0:) 1|/
==0
3 k b [1 a1(1 - 7001
(1 +
K K-1
3 |3 > of x 1 a(1 ]
< 27(o² + +3KB (e,
+ 2KE
((O.)
==0
S1
227 +3K k2KG2)
(constant local step-size)
where we used the fact that (2) + ) s 2K for (e) and (1 + ==1 S 27 for (f). we finish the proof by substituting a Kag
If we incorporate Eq (24) into Eq (22), we have that
E 0++1 -0- 0-1
(26)
0, -012 + 2a - -0) + 6 ((
$ (1 + (1)
a²
|0² + ((,)) + 20²0²
+ 108
(6 + 21
NK + +ab((e, 6a (E, (3)
(27)
Kag
G.1.4 Parameter Selection
Lemma 10. Define 2 (1- If we choose any effective slep-size a Kugon < (1-7)=
any local
96
step-size an S min ا and choose the constant Si av, the updates of FedTD(O) satisfy 1SK
2
1 - -E)E 0. 0r 0-|² - B 1 S (
0-1|²=
2002
nB
Vo.
Vo-
+
D
NK Ola')
1080a²
(02 + 333BB((, + 2KG + 2B((, E1)G (c,
(28)
Kazu
heterogeneity term
Ola2)
where vi = 4 [1-7)0 1
Proof. From Eq (26) and Ci = au, we know
B 0..1 - 1012
< (1 + (1)))e( 00- -000-011' 00112 + +2.B(((00)).0 0-0 0-) + + g(0.)| ||
108 at
(6 1002
1
+ (x)+((
2020²
+
+2aB(c, + 6a B2(c, ())
Ka² "i
NK
0. 0r|
+ 240 16. - Vy- ||
2a²a²
< (1 + av
- 2
(Lemmaa 3 and 4)
NK
108 at
1
(6 +
102
+ 3KB² (c, (1) + 2KG2) + 2xx 2r ( + 6ax (c,
Ka
< (1 av E 0. 0-1²
av E 0, 0-1
+ 24a 2B
Vo.
Vo- 1/rl²² +
20202
2
2
D NK
32

---

Published in Transactions on Machine Learning Research (06/2024)
at
+ 108
+ [0²
(cB) + 6
Kay
av
(a)
0: 11 E Vg V/. 1
E
-Vo I
20²0²
S (1 2 J
NK
+ 108
+ [02 + +3KB (1) + 2KG + 2aB(c, + ba (c,,,))
Kaz av
where (a) comes from A ( < 1 and 24a² v 24a شررلاا = -. Moving E Vo. Vo- vo-11²
(on the
96
right-hand side of (a)) to the left hand side of the above inequality yields:
Bc+1 - 0+1 011 + 2a20² E
E Vo,
Vo-
P S
2 1B
NK
a
+ 108(
+
102 + (3K + 2KG + Ba 6a (e,
Kay
Kazy
Dividing by on both sides of the inequality above and changing into 11, have:
B
Vi, - Vo-
1
1n 10100
0g
0-1
0-
1
0
0r1[²
2002
NK
a
6a
4a2
+ 108(
102
+ 3K B² (c,6)) + 2KG + 2B(G,)) +
Ka²
Kazen
u
v1 )b|
0g 0-
1 R
01+1 - 0=1/²=
2002
NK
O(a!)
1080a²
(02 3K 3KB (c, + 2KG 2B(c, 6a
K
heterogeneity term
((a²)
where we used the fact that a < 1 in the last inequality.
7
With these lemmas, we are now ready to prove Theorem 4, which we restate for clarity.
G.2 Proof of Theorem 4
Given fixed local step-size ag
1 (1->)/
48K decreasing effective step-sizes as vla+t+1)
(1-7)0(0+44))
decreasing global step-sizes 0ig Kay
(4) ai and weights we (a 1), we have that
1
2 Ô G
d²
a² B(c,e1)G + (T(())))
E Vor Vo:
KTT + PNK
(29)
K2T2
holds for any agent E [N].
2 Proof. We take the effective step-size 04 v(ati+1) v((att+1) for 0. In addition, we define weights w/ = (a t) and define
8
T
0r
Σ
w=Or.
W
where W ET wi 2 1 *T(+TT) By convexity of positive definite quadratic forms (Amin "T DΦ) 2 σ > >0,
we have that
Var - Vo- l v1
33

---

Published in Transactions on Machine Learning Research (06/2024)
11 T
Vo. Vo- l
a + 1)
t=1
(28)
(a + 1) =2
2(a + t)a 0²
2W
W
NK
1=1
1
1080(a + t)at
+ (o² + +3KB (e, +2KG2)
Kazu
(a + t) [2 6a, (a,
W
(a + +)(a + 2)G²
20
T
(a + t)ot
2W
NKW
1080(0² + 3KBB(G, + 2KG
(a + 1)ag + 2)( (c,))
T
Σ
aa + t)ar
KozuW W
W
t=1
t=1
(a 1)(a + 2)
4
T
2W 4320(0² + +3K B² (1) + 2KG
WNWW
(1 + log(a + T)) + 2B(c, () + 12 61)
T,
K
WW
|Vo0
Ve- 1 s G2. Dividing by vs on both sides, changing Vi into v, and using W T(a+T)
where used
have:
2 | 20
G
o²
d²
B(e
E Vør
Vo.
K2T2
AKT
T2NKT
1
We finish the proof by using the following inequality: E Vor in tandem with the third point in Theorem 1.
Vo= l' D
2E
Văn Vo-
vo-112+
+2E
V0:
Vo-
34

---

Published in Transactions on Machine Learning Research (06/2024)
H
Heterogeneity bias: Proof of Theorem 3
In this section, we prove Theorem 3.
Proof of Theorem 3. As 0f and 0j are the TD(0) fixed points of agents and 2, respectively, we have 0r = A by and 0 = Ar'by The output of mean-path FedTD(O) with and a = agaz satisfics:
D+t1 0. a(- A0- bb)
0(+1 07 = 0, of + a( a(-A(0, 04 + 01) + +8)
-1,--1 (1 aA)e1, aAOi ab
A1 + A2
b + bz
= = (1 a A)e1 -
Ar
+
2
2
A2 b
b2 2
-1,1111 (I aA)e1,1
+
aA2
-1 = (I a.)
(Ai
b
An b2)
2
aA₂
-1,-1 [I aA
C
(0
0T)
(30)
2
Let us now note that 61,+11 = A + y can be viewed as discrete-time linear time-invariant (LTI) system where a is chosen s.t. A is Schur stable, i.e,, Amax((A) < 1. At the t-th iteration, we have:
612 A' + Σ A
k=0
As > 00, the small gain theorem tells us that because p(A) < 1 (where p(-) denotes the spectral radius),
Σ A exists and is given by (I (I-A) A)-1. We can then conclude that
lim e1,t = (1 (1- Ā)- 600
(aA) -1 aA2 (0 0
- 1 Ag (0) - 03)
(31)
The limiting expression for 62 follows the same analysis.
35

---

Published in Transactions on Machine Learning Research (06/2024)
Proof of the Markovian setting
We now turn our attention to proving the main result of the paper, namely, Theorem
1.1 Outline
As mentioned in the main body, one of the main obstacles to overcome in the analysis is that in general, [[(1/N) E (g.(0)) 0(1)) - gi (0(2)) # O. In order to show that a lincar speedup achievable, we first decompose the random TD direction of each agent i as gi (0 = b,(0%,)) - A o in subsection 1.2.1 and show that the variances of (1/NK) E -K-1 A,(O(.) and (1/NK) E Ik= (,( get scaled down by N in subsection I.2.2. To decouple the randomness between the parameter 0 and the observations 0 f.k using the method called information theorelic control of coupling in Bhandari et al. (2018), we need to bound E | 0-- in subsection T.2.3. As the analysis in the i.i.d setting and traditional FI., we characterize the drift term, per-iteration error decrease, and parameter selection in subsections I.2.4, I.2.5 and T.2.6, respectively. Finally, we prove Theorem 2 in subsection I.3.
Additional Notation: Under Assumption 3, for each MDP there exists some 2 and some P; E (0, 1), such that for all t 2 0 and 0 < K it holds that
drv P
(
(2) = 86,k | 1..0
=,)==()))) ,1())) I m=ppK** vs E S.
Furthermore, we define p = max m = max:EINN(mG
1.2
Auxiliary lemmas for Theorem 2
1.2.1
Decomposition Form
The first step in our proof of Theorem 2 is to rewrite agent i's update direction of FedTD(O) as:
9:(0(.1) - A. + +.
where A,(o = (0 (+(1) go (s and (O() = r( ((s Note that the steady-state
value of (O is not equal to O. For convenience, we apply appropriate centering to rewrite gi as:
(010 - A.00 - 01) b(OO A(00
(32)
Define 21( & b,(0
A As g:(0) A E ~ [0), we have:
((
(,(((()) t,k 07).
(33)
where A, D p). Note that B ~0() definitions above, we establish the following lemmas:
[z,( equals to 0. Taking into account the
Lemma 11. (Uniform norm bound) There exist some constants C1, C2, c3 2 such that | (O(2) | Sq :=
1 1+7, A <e = 1==++1 and
Zi (0 1.k
||
S C3 = Rmax + ei H holds for all i E [N].
36

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. Based on the definition and the fact that ||Ø(s)] I 1, we have
A -
[6 (s - 76 T (5 (8) (s) |o - | o (+())) T0
s1+%
Similarly, making use of the fact that r(s) S Rmax for any E S, we apply the same reasoning to conclude that
| S 11 & 2 (0%)
||
- Rmax + c
Lemma 12. There erist some constants L1, L2 2 0 such that
A; E A (0!0) (6)
| S
A Ex,
A (o!0))
)
S L1pp
12,
E Z (2.kiz)
|
Er, Zi
(0)))
S Li
t2.
hold for any E [N], 0 S hi, k2 S K 1 and 12 2 1 2 0.
Proof. We have:
| 2: (0.
(0/g.ka) ) 1
E Zi (O
|
-Bog
E
Zi
(0.00)
(0()))))) Fr
(i)
t2.kk)
i2.ta (
(5
(
)
88 (
12
1
822222
A2g A247
- 12.0g
(1)
= [, P(( 1,
(1)
(
(((,kz)))) (2(0(()
(2.2) )
$
Σ
x (60 (t)
(s/22t))) - (( = 1 ) (
1
1/2
( (3/2.h22) - P(.l0d = 1 =110(( (Rmax + c1 H)
(1)
(4) F12 Ar
2 [mmax + Cq Hdd (P
(10 = s/ s2i ( =s) xz())
< 2( (Rmaxx + ca H)mp,, (1)
where (a) is due to Lemma 11 and the last step follows from Assumption 3. We finish the proof by choosing L2 A ( Rmax + ci H):m = 20gm. And we follow the same analysis to bound:
|| | -E
E [A (0.1) (0t))ts) ) Fb:
I As
(0.0) (000.ta)
[ (0 12
k2.
-x(e)
(1(0)
(2)
(3) )((
11 12 1.2g11
-( =
(2)
) (2)
1g 11 1 ((()tt))) )) A: (1)
$ Σ
(s (s(())ao) - (() = =1((() (1( t2
12.42
37

---

Published in Transactions on Machine Learning Research (06/2024)
(6)
x 2c1drV (P (Staks
(
- ks k =s) xx
(t2- (12-t1 -ko--
- 20 mip
We finish the proof by choosing L, - maxie[N] (2c1m) = m2. We employ the same reasoning to prove the remaining three inequalities.
]
1.2.2 Variance Reduction
We are now ready to present the variance reduction Lemma in the Markov setting. The following Lemmaa estab- lishes an analog of the variance reduction Lemma 7 in the i..d. setting. Based on the assumption that trajecto- ries are independent across agents, it is casy to understand that the variance of (1/NK) Σ EK= A,(0)) and (I/NK) En (O((()) can be scaled by the number of agents N. However, is not obvious that the variances can be scaled by K (the number of local itcrations), since the observations of each agent O and ((1) are correlated at different local steps k, k2 Due to the geometric mixing property of the Markov t,kg
t,k2 chain, the correlation between 1,k2 and (6) will geometrically decay after the mixing time. Based on
this fact, we show that the variances of (1/NK) EN E A,(O)) and (1/NK) E EK= b,(O 1.6) get scaled down by NK with an additional additive, higher order term dependent on the mixing time T, which is formally stated as follows:
Lemma 13. (Variance reduction in the Markovian setting) For any 0 < < there erists d1, d2 > 0 such thot:
K
d1 VNK
E
A((O
A.
5
+
+211p
(34)
NK
K=
S di
E
AMO A.
+
+L,
and
(35)
NK
NK
km
I
K-1 Σ [(00
d2 VNK 2T22p=
(36)
NK
K=0
dc
E
NK 4L22p 2TK
(37)
NK
where di A V (cI c2) + 2(e toglhip and d2 A V +
20gh2g
I-p
I-p
Proof.
E T
1
9 (k
NK
K-1
K-1
Ee-r
Σ
NK
NK
N K-1
)
(
N
K-1
<
E
M
((O
Σ
Σ
((1
NK
NK
0=0
1=1
0=
(concavity of square root and Jensen's inequality)
38

---

Published in Transactions on Machine Learning Research (06/2024)
K-1
Eg -7
21(0 ZZ( +
N (
2
N2K²
T1
2 K-
+
2
ΣΣ
E2(0 22,002
(38)
N2K2
N2K²
i<g kel
where Ti can be further bounded by:
N
B E
2
Z(00!)
N2K²
i=1 k<!
N
(10 TE (2 Fil]
EE-T
N2K2
1.6)
1=1 k<c
2
[(0 B [200 [i]]
E
N2K²
(Cauchy Schwarz inequality)
N
< E
(aLzp((-R)
Lemma 11 and 12)
N2K
2
1=1 k<
N K-1 0
S Eq-T
C3 c2
N2K2
k=0
L2
P
L2g
N2K²
p
NK(1 - p)
And T2 can be bounded by:
K- 1
[((0
E.- [2,1 (0 and 0f are independent)
E, E
T2l
Be-
N2K
K2
k=0
K-1
2
(Lemma 12)
N2K2
K3
K=0
2
22p2.k
2
K
Meanwhile, T3 can be bounded by:
2
E.- [((O
E,- [2,(0[1]] (0() and 0 are independent)
[T- =
N
Kjj kel
2
2- -k+1
(Lemma 12)
N
icj
kel
$
2
Substituting the upper bound of Ti, T2 and T3 into Ey (38), we have:
N K-1
E, E
Σ Σ (1)
(8)
NK
(.k)
0=0
39

---

Published in Transactions on Machine Learning Research (06/2024)
N R-1
B B [2(0
2cgL2p 2 + NK(1 p)
+ 12 + +212,2r K
N2K²
1=1 k=0
NK
20zLp
+ L302Tk + 2L3P2TK
N2K2 3 + NK(1 pp)
K
20gbap
c 1
AL30RTK (K21)
NK
c3 +
2esTep
+ VALL02TK
NK c5 20sT2p 2L22=*
NK
I 1-p
p
2 (0..) ||
where (a) used the fact that follows the same reasoning.
< Cg mentioned in Lemma 11. The proof of other inequalities
1.2.3 Bounding E [10, 8 -117
Lemma 14. (Bounding |10, 01--112) Consider T (aa) and choose the effective step-size
(a+))
a S min 30ca(T + 1) 96c3r
where C1 301. For any 2 2T, we have the following bound:
Ex_2r [100 0,_ 12] < 8a' 8 22 [10, 1100-0" 00 11] + 14x²
d2
52L3a-T
NK
1 p2
+ 40 2
E Σ
Er [ + 3200a 3200a"cfee7 $ (e, + 2
(39)
Proof. For any 12 2T, we have
0 - 0.
N K-1
= ||11..4 0 +
α
9: (0
-0,1"
NK
i=1
k=0
K-1
< 0 + NK
(0
01
N K-1
Σ
Al(o (0. + 2 |
NKK
K-1
[ A (012 -0 -0 +Z(0
< 2a
NK
k=0
K-1
(0'
2a
NK
(a)
Σ K-1
(1( (0 -8r) + [,(0 | +
< 2a²
NK
0=0
40

---

Published in Transactions on Machine Learning Research (06/2024)
N
R-1
N K-1 Σ Σ
= =
1,10(1 (012 - -81]| + +6o²
A.10
(0: - 8-) )1
NK
NK
k=
1= k=0
K-1
6a?
1
(((0 ||
+ (f,
NK
i=1
k=0
10c2 ai1)
S .a
NK
==1 h==
+ Ga
- 0-11
+ 6a²
1
Σ
K-1
Σ k=
( || + (1,
(40)
NK
where (a) comes from the upper bound of fixed points distance in Theorem and the fact that (0 sa in Lemma 11. Taking square root on both sides of the inequality above, we get:
0+1 - 0:
$
a
C1
N
K-1
0 all)
+ +3/ a²c - 801|
NK
k
1
||
+3
a
+ (22
NK
N K-1
30c
0
öi|
+3ac
0. 0r
+ 3a
[(0 + +(,,))((,,...
(41)
NK
NK
k=0
| - 80| s 8: 8- 8-|1 +
[[+1 0.11
By using the fact that
have:
N
0(1
00|
$ (1 + 3aci)
-00
+
30c
10 8.1
NK
(42)
N K -
(0( (2) ||
30
+ 20c ele,
NK
1=1 h=0
For simplicity, we define & 3c1 and 6, Eq (42), we have:
1
Σ
EK= K-
0112 81||
Taking the square on both sides of
NK
@141 - 8r) |
K-1
$ (1+ + acc)
+ a² c²c207 + 2
1
Z, (1) ||
+ 4a 1 (1)
NK
k=0
N K
+ 6a(1 + +cc4)
01 0-
7x(0
(8)
20c4 + acs))
0 - 0- 61
NK
1,k
1=1
k=0
H1
11
N
K-1
+ 662 caai
Σ
Σ
+ +4a (10)
(1) (.k)
NK
1= k=0
H4
41

---

Published in Transactions on Machine Learning Research (06/2024)
N
K-1
+ 4ac (1 + aca) TT([(1,))+
+ +1202
1
(43)
NK
1=
k=0
Hs
We can further bound H1 as:
1 K-1
H1 6a(1 + aci)
0.
Σ Σ
2
NK
i=1 k=0
K-1
= =2/3a(1 + aras)
01 0.1
33a(1 (1 + accs)
NK
N
K-1
x 3a((1 + +aci)
0- 11
+ +aa(1 + aciil
(0
(8)
||
1,k
NK
1=1
k=0
$ 6a| 6a||8 8: 0r|l²
6a
Σ Σ (1
(44)
NK
where we use the fact 1 + ac₁ S in the last inequality. Similary, we can bound H2 as:
H2 20c, + aci)|
0/10: = 2a/ - 00l + 2ac
(45)
And we bound H3 as:
N K-1
1 N K-1
H3 6a
1
Σ Σ
2:0 s 3302
Σ Σ
2(00 (1)
1.k
||+ + 230
(46)
NK
NK
i=1 k=0
x=1 k=0
For HA, Hs, H6, have:
H4 = 4 20² + (c,
H3 = 4ac (1 + aci) (1 1 [(E,es) s 4a| - + (e,
N K-1
N K-1
Hs 12a²c
1
Σ
6a?
1
Σ
Σ
(1(0
|| +6a (6
NK
NK
k=
Substituting the upper bound of H1 Hy,... Ho into Eq (43) and noting that (1 + acz)² S 1 +0c because ac4 I 1, we have:
0141 - -00l 0-1
0 - 1=(2 (6a² 22)
$ (1 a(3c + 12))
K-1
+ +18a² + 6a)
1
(,(
(.6)
||
2
+ (12a² + (e,
NK
k=
(1 (1+ -
0012
+ 8ac + 24a
1
K-1
2, ( || + 16acTT
(47)
NK
im
k=0
where we denote h 3c4 + 12 for simplicity. For any 1 5 l < 1, conditioning F.-2r on both sides of the above inequality, we have;
E. Oc+1 - 0r
42

---

Published in Transactions on Machine Learning Research (06/2024)
N K-1
S (1 + (h1) E2 -2
01 -0rl 0-1|"
+ 24 27
1
Σ
Z (0
2
NK
i=
k=0
+ Bac 27
[9]
+ aNM3(E,E))
< (1 aa1))
Ex 27
0: 0- 11 24a
dP
+ 41220(1
(Lemma 13)
NK
+ _ [o0]
+a
10)
S (1+ + ahi) 27 01 - 0-|
NK + 2L 20-)))))
dp
+ +4a
+ 8ac 2- [of] + +aMs(c,
< (1+ 22 01 0. 0²1"²
+ (lc((l) + Ee [o0] + aM
(48)
where we denote 61) (e, and ce(l) =
d
+ 4Lza² ( for simplicity. Inequality
NK
(a) due to 2 S a4 S oz. Tn the following steps, we try to map E 0141 - 0²2 to B 0 | 0- for any
7 tt. By applying Eq (48) recursively, we have:
E 2r Oi+1 - 0-1
< (1 + ahi) 1 B, O.r - 0012 ta Σ (1 (-ah))"-*(ar (c((k) + M2(cg))
k=t-r
+ E
Σ A
(1 (1+ahg) ahz) ahz) oz
(6)
T+1 Ex-2r 11022100- - 0012 - +a Σ (1 (c Ma(e,))
I (1+al1)
R=1-T
11.
+ S
Σ k
(1 + ahi ah1)"= o%
(49)
Hg
where (b) is due tl1l1. For H7, we have:
H7 <
(1 + ah1) 1-k (k((k) + Ms(c,e))) (t
k=
(1+ah)) (c,(K' +t + Ma(c,c1)
P=0
( (hanging index into ke with E' = k + -
& + AT 2 K + Ma(e,)1)
< 24
(1 +da))
NK -
==0
(Substituting the definition of ce(k)) inside)
dg
Ma(erei) (1 ah1) -
D2k
+ 4L2aa² (1 + ahh))"
NK
ah1
1 1 ahny
k==0
NK + MM(cca)
d2
(1 (1+ ah1 + +4I3a² (1 + +hh))
Σ 22n
< 24
(1 + ah1 2 1)
ah1
43

---

Published in Transactions on Machine Learning Research (06/2024)
(
s 24
L NK
+ Ma(c,ai)
(1 + ahi) -1 + 4T2aa² (1 + ahh)""
1
ah1
p2
Here follow the analysis in (Khodadadian et al., 2022). Notice that for 1og2
we have (1 (1+x) v
+ 2x(T + 1). If a I 1h17 I log2 and a I 2/+()+1) we have (1+ + ahl) T+1
1 + 20da (r 1) S and
hit
(1 a11) $ 1+ 2ah17 < 1 + $/252 2. Hence, we have
[Nxx + Msle.a)) 1) 8I.302
H7 s 24
1 1-p² p²
We apply the similar analysis to bound Hg as:
Hg Σ (1 + ah1)) 82 (1 + a01)) 02
Σ + T) 02 S $2Σ 8i
km0
Substituting the upper bound of Hy and Hg into Eq (49), we have:
1|
0 0-|
+ 24a [
d3
Male.ci) 2(r 2(T++ 1) 1)+ 8L3a²
E,-27 2r 01+1 8-|
s 2E, 27
NK
p²
16ac
Σ
E4g 27 11--2-08-11 [87-
k=0
0| - 10-0% 00ll as:
Then it is straightforward to bound E,-2r
E 01 - 0012
1² S 2 0,, 0012 24a
( NK
dz
+ Molese))
8L2a²
4T
1 p²
7 16ac
Bo- 18
(50)
Furthermore, based on the triangle inequality, have:
2
0. 0
0.+1 - 0. 0.1) [1)==
1-1
<T Σ
D.t1 0g
6=1-r
8-1-
[-1
1 K-1
<T
a² a²c2 0, - -0-1(
+ aa² G00 + oa.
Σ
Σ
+ 2a ((,
NK
where the last inequality is due to Eq (40) with c4 = 3eg- we take the expectation on both sides, we have:
E, 2r 0g 0--7
i-1
ST Σ
a 222g Er
0. -01e + &a
Amt-r
6a2 27
(((
2 || + 222
NK
1-1
< Ta² 2 cj
Σ
2 27
0-- - 0-l
4=1-7
44

---

Published in Transactions on Machine Learning Research (06/2024)
+24 24a
(
d2
Ms((,e1)
4T +
8L3a²
+ 16ac Σ
B2 27 [88
x1]
(Eq (50))
p2
k=0
t-1 Σ
d2
+ T
+
NK
1-1
+ &d
E1-
[6 + 2a 2
(Lemma 13)
8=1-T
(a)
I 72222 2T
1 8-
0
-01 +96
d3 NK
Q5 + 2Iza3
)
] 6
[NK T +
d3
4Lza²
1- p2
1- 1-
+ a² ccceT(11 + 16aTe)
Σ
Ee- Er 188 + 96a 227 3 MM((E, +2a +2a2e77 T (E,,1))
2r
(M)
S 2+ 22
01 -0
0-|
2² (96ate) + +6)+ 12L3a"T dP
(16aeiT + 2)
NK
1-
+ a² etT 1 + 16aTe))
Σ
+ 96a 22r E)(E + 2
(51)
==0
where we used the fact that p²rk S a² for (a) and (b), and that 8, S A, (via Jensens' incquality) for all 2 0 in the last inequality. Let us choose a such that 96are + S 7, 16adir + S and 1 1+ 16aTC] s 2, this holds when
a S min 16TC7 96 16re 1
Based on the fact that 10,_, 1- < 2 0.r 2| + 21 0" 1|2 and the requirement on a, we have
202 2 2 110 1/ < 4a 4
0. 8 - 4a 2 E 1 - 1
< 0.5E. 27 10, - - 1|2 + 22
10, - 0112 24a2 S 0.5)
(2)
7
2 + 13
< 0 E 0 0,-,- 0r
2NK
(1 (1-
+ a² GeT Σ
Er_2r A . + 48a 2
+ + Ma(e,))
(e
0
4a 2 Br 10, 1-
(52)
where (a) is due to Eq (51) and the choice of a. Putting the term r²a2cEE 0.r - 00l2 together by rearranging the terms, have:
7cl
13L3a*T
a² a²72 E. 10,- 0-122 S
22 +
2NK
(1 p2)
a² 227T Σ
Er A + 48a 22
4a 2 22 E 11 - 0¹11
(53)
The proof is completed by substituting this incquality into Eq (51) and the definition of Ms(e, (). Note that require the effective step-size
< min {
14h,T' 2h (T + 1) 96037* }
in this proof, which holds when a S min 30al 96657 ; 1) since C4 = 3c1 2 1.
1
45

---

Published in Transactions on Machine Learning Research (06/2024)
1.2.4 Drift Term Analysis.
Now we bound the drift term as follows:
Lemma 15. (Bounded Client Drift) If as S 2/2c1(K-1)'
the drift term satisfies
E[A|]
K-1
B
((1) 2,k
02
2
S
4a
c
20IL2
+ Sck - 11)1?
(54)
NK
Ka²
1 1-p p
R=
g
Proof.
N K-1
N K-1
8.
1
ΣΣ
Ei 0.
E
E
0. + 01
NK
NK
i=1 k=0
==1 0=0
A,(0 (0 0:) +2(0 ||
aj
NK
N K-1
A,(0 (02 - -0:)l + 20f + NK
N K-1
S 20
NK
k=0
K-1
K-1k-1
1
[A(O)) (02=-00 1/
2
E
+2a 2
E
Z,(0
NK
NK
K=
(=1
k=
8=0
N
K-1 A-1
+ 20
Σ
Σ 2()
NK
k=0
3,
5 <2a
k
E
0000
0:1]²
2aa
1
Σ
kcg
(Lemma 11)
NK
NK
K=U
N K k-1
+ 2a
Σ
Σ
Σ
E
B
Fi]
NK
1=1
k=0 5,
spfa"
< 2 2
1
N K-1
Σ
kep
Σ
k-1
E
0::"
2a²
1 N K
Σ
kcz
NK
NK
f=1
k=
2=0
1=1 K=0
N
K-1 k-1
+ 20
1
E (2210
E
(10 ) > Fi! }}
NK
1=1
k=0
=0
sph's'
< 20 2
N K-1
Σ
kep
Σ
k-1
(
0:1""
+ 20 2
ΣΣ k
N Ā-1
NK
NK
[=] 0=
i=1 k=
N
K-1
4aj
1
Σ E
E
(+)
Fz
NK
1=1
k=0 =0
s<c''
< 4
Σ
N
Σ
K-1
ko
k-1
Σ
( 0.1"²
+ 4a
Σ
N K-1
Σ
ke
Σ
1-
B
0.
8:1
2
(Eq (11))
NK
NK
0=
0=0
1=1 k=
0=0
46

---

Published in Transactions on Machine Learning Research (06/2024)
N
K-1
N
K-1 1 R-
+
2a
kcg
4a
Σ
caLap" -s (Lemma 12)
NK
NK
1=1
k=
k=0 8,8 SCs'
K-1
k-1
N K-1
4
2
1
Σ
koj
E
B.ll
+ dai
Σ
Σ
4kcj (K 1)/
NK
NK
k=0
N K
N K-1
+ 20
kgz
4ai
ΣΣ
Σ
ea Calpp'''
(55)
NK
NK
k=0
k=0
=,00=0
8C8'
where we used the property that 0, 87 E H in the last incquality, ic.,, ||0|l| S H² and ||0 I H², We now bound Mi as:
k-1 k-1
c3L2 Σ p-p pp= S C3L2 1-p 1-p
k-1
pk
caLيp"
czL2
Σ
Σ
(56)
8,6
s'=st
0, 2 and note that Rx is monotonically increasing in K. With this
Define Rx A E Ek
t.k
definition, if we plug in the upper bound of Mi into Eq (55), we have;
N K-1
K-1
RR S 40²
kej
0.
4
4koq(K - H1
1=1
R=0
==0
1=1 k=0
K-1
N K-1
+ 2a
koz + 4a
Σ
C3L2
pk
P
1=1
20gL2p
S 20 (K 1)NK
+ 8 (K- - 11) 1)
033 +
1-p
K-1 N k-1
( 0.1 1
+ +4afe 1)
K-1
20gL2p 1-p
=2af(K - -K
+ - (
+ +4,22 1)
Σ
Rr
(57)
k=1
By the monotonicity of R2. we have
20gL2p + 8c2(K 1)H2 +
RK S 20 (1-1)KK
2g + 1-p
Let us choose aj such that 4a2o7(K 1)2 < 1, i.e, ai S 2 the following recursion holds:
Rx S / R + 2a (K- 1)NK o/ + 203L2p + +cq - 1)HH²
(58)
1-p p
for all k E [K]. Next, we unroll the recurrence, go back K - 1 steps and use the fact that R₁ = 0, we have:
2 203Lap + (c)(K-
Rx <
20 -1NK
23 + 1 1-p p
2
20gL2p + Scf(K - 1)H12 1-p
= 4K - 1)NK
(59)
We finish the proof by dividing NK on both sides and substituting ai Kag"
47

---

Published in Transactions on Machine Learning Research (06/2024)
1.2.5 Per Round Progress
Lemma 16. (Per Round Progress). If the local step-size ai 2x and the effective step-size a = Kajag satisfies:
1
&
1, (1 + +2)
1
S min{
24(c1 + 02)² 245 16 2L1 + 87 30c + 1) 96 X),
where
X = (Ea(E, + 24(c: + +
and choose T -uii (a 1, then we have,
Er 20 - 8-112
(1+320Ei (c1 + 02)) Br 27 O. - o¹1|² + 2aB, 27 (p(0,), 0-) + 2 27 ((0.)) 1
Expected progress for the virtual MDP
28r2
108T
NK a 2 +a3 36L2 1 1 L2 + 42, + 2L
Linear spenduu
High
O(a²)
3
14
203 T2p
( (4;:)(a + 02)
og
4e (K 12H
Ka² g f1
p
drift term
+ AaB(e, + (c + (c,e))
(60)
keterogeneity term
where & is any universal positive constant.
Proof. According the updating rule and the fact that the projection operator is non-expansive, have:
E,-r 0 00+1
0-12
K-1
-,,r
112,71
0,
96
(0(0) 1,6%
0-
NK
N K-1
< EE-7
0: +
((
g-
NK
0m
N K-1
E
0, 011
+ +2E,
(0 0, -0-)
00)
NK
K=0
28, NK
9 (
(8
-0r)
Thhis requirement is very easy satisfy the denominator X is composed the heterogeneity terms, which quite small and therehy makes large. Overall, the feasible step-sizes is not empty.
48

---

Published in Transactions on Machine Learning Research (06/2024)
N K-1 1
( 2
+ a
E
Di
NK
i=1 k=0
N
E
0,
0
2
((())) 01 - 00) + 2
a
9. g. - (..). 0-)
NK
i=1
B1
K
K-1
3. (0
0-)
+a Ex
9 (
(61)
NK
NK
B2
We now begin to bound the gradient bias term B2 by decomposing this term into three terms:
( -0000000))0)) 0²)
NK
k=
N
K-1
( - (.(0 0, DrT))
NK
B21
N K-1
(i(0( g:(0 - (0(( + 2.0 -8)
8-)
NK
i=1
N K
(1 - _ O.r - -07)
(62)
NK
1=1
k=
Next, bound E
K
[0.00(1)))((000)) -0 -0ar)
E
NK
k= 0
Σ K
E
((((())
0.(0!.2) 1100))11000000 -8
NK
N K-1
(a)
(-A,(0 + A0 -0,) + 2: 1|0, 0. o, 0,-,)
E,
E
(A,(
A0 001 1 -6--11
NK
N K-1
1110,1101 - ||
Σ
NN
0=
N K-1
(A(0
AN 07) |||||00
0 - 0 6 |]
E
NK
1=1 k=0
N K-1
|1 0. 27
Σ
Σ
E E
2
NK
2a
(b) (a + +2)
Σ
N K-1
E, E
0:|1|a
0:
0.
8--7
NK
k=
49

---

Published in Transactions on Machine Learning Research (06/2024)
N K-1
a
||²
R
2,6
+ 2a
8
2
NK
i=
k=0
5i
+
C2)
N K-1
000
0:1
(cr + c2)
K-1
E
+
E
0.
0 --
2NK
N
1=
k=
(Young's inequality (12) with constant E1
N
K-1
a -
1
Σ
1|
+ 2a
E
0.
81_
2
2
NK 1=1
k=
② [cl + c22
K-1
[0(0 1.
0. 111²
+ 361(c1 + 02)
N K
E
0,
0"
2NK
2NK
k=
K- k=0
361(c1 02)
K-1
B 0" 0:1
(c1 + 02)
2
0.
8
2NK
N
k=0
a
E
N K-1 1
+
E
02
8,_ 2
2
NK
2a
i=1 k=0
(c) + +22
N K-1
E
((1) 1.6
-0g
0 2
1
(c + c2)
E
02 0- 2
2NK
k=
(61(c1 + 02)
(c)
(CI + 02)
Bi-r -0-
0
2
251
K-1
a
R
1
1,6)
(8)
||
2
+
1
E
00. 0
2
2
NNK-
2a
1=1
K=0
(
(9 + 02)
N K-1
E B--7
0.1"
+
361 + C2)
Fe-r| 0, 00
2NK
1,k
k=
361(1 + 02)
(e()))) +
Ci 4
02
E,
|0, 0PT
2
2
25
a
dz
+
4L222=k
2
+
1
Ee
0,
0,-
|²
2
2
NK
2a
(c1 + 02)
N K
Ex_
(000
0:
2
(c1 + 02)
E,
0, 0r
|
2NK
t,k
2
k=0
+ 62)
2 (E, +
(1 (1
+
1
E, -7
0,
0,
2 α
+ 2
d2
+
4L202rK
201
(63)
2
26
20
NK
E41300
A. 03) + (1)) (b) is due to Lemma 12 (the upper bound of where (a) is due to gi (0 = -
((( and Ad), (c) is due to Eq (13) and (d) is due to Lemma 13.
And we bound B22 as:
N K-1
B2n
Σ
- - + (1
B 0r)
NK
1
(((((()) 9.(0( ((((( + g. 10 - 10---0)
NK
1=1 K=
(Cauchy-Schwarz inequality)
50

---

Published in Transactions on Machine Learning Research (06/2024)
N R-1 1 2: (-T. /| (1(2 - I. r-r, w>1l | - 0-1
Σ
(0010020 -
NK
21102 / + 2 1010 - 0 7_ |] 1| - - 0-1
+2
NK
N K-1
Σ
Σ
|0 6,6 - 0.11 + al10. 01- + 4 0 0 ||
|
0 - 0-1
NK
1=1 0=
(Triangle incquality)
< 46 0,-r---- - 00 + 4
= 0, 0--
1o-1|| 1 0-1
+ +48,_ 0 0-
D.+
+
2
- + (252 + 452) 0or - 0/1
+
2
0. 0,-7
|
22
&2
E2
(Young's inequality (12) with constants &2 and o - A.)
2
A + 1 0. 0-11" + (12E2 +
2 )
0c 0: - |
_ A
+
(Eq 13)
(64)
22
2
2
where (a) is due to the 2- 2-Lipschitz property of steady-state I (i.e., Lemma 5) and random direction gi (i.e.,
Lemma 6), 6, = N Σn Ek
|002 0.| and A. a NE En Eko B 0.02 0, ||
2k=0
Now, we bound B23 as:
E, [Baa]
N K-1
E, E - - -6. )
NK
N K
P 8-
E, 7 10.00! - -6 [ ||
(Cauchy-Schwanl incquality)
NK
0 0-|
E2 7 | A - 03) + 2,(0!)) + (, 003] ||
- 00 {|] (1 -,100fT---0)1
- -0>)| + + | [2]10[))]] ||
Σ
|
0-| 0
k ( - -0:1 + k <
NK
0 0-1|
NK
i=l K=
x LIp K+* *+*
[1 1 0 0--1 + |0_ - 00| + |or - -0:1] k+b }
5 21 0 0,- - 0-1
1
5 + a² 1² 10..-
- 0ul 2 + + + a²InG
5 12 - 0²1
+ +a - + a² 0r. 1
0r 1'= + a² [T
_/ 2a² 2 L22 + a² LLLG + a² LL + a2 aLLT
(65)
where (a) is due to Lemma 12, (b) is due to the fact that 0--,,0- 0* E H. which radius is H S G and
2
loR, 103,(03) | (i.e., pTt S a²) and (c) is due to the fact that 0- 0" E H. Then, the term B2 can be
51

---

Published in Transactions on Machine Learning Research (06/2024)
bounded as:
F,
1B211 + B22 + B23)
351 + 02)
+ 3C1 + ②2)
Et- 0: 00| +
361(01 + +02) (c))gg)
E E |
2
2
2
+
C1 02 02
+
1
0, 02
2 +
a
d3
+ 4L3g2 2n
25
20
2
NK
2
2
0:- 001
2
0, 0 2
Ey EE [1,]
+
B ( + 12
E
+ +1222 +
|E,
E2
52
52
+ 2a L G2 + Lz
a² 2LL E,
L, - 1
a² LTGGGG
(9 + +02)
+ 126
B 0. 0²1
+
ci +1
+ 2a
+
1252
+
2
Br-r|00 0--
2
261
E2
+
351 (c1 + 02)
+
Ee-r/d1]+ +
(2 +abl1) D +
a
d2
+ 4L2a²
2
32
E2
2
NK
3619 + +22)
+ 20 2 L2 + aa L22
T2 (2) + a² (G
(66)
2
Next, we bound B3 as:
E
N K-1
= =E
(0 -.(0 + - -
+ +0(00) g(o.) + [ |
NK
1=
(n:0 -1 1| 4R,
1
(0(0012) =i(00)) l|²
4E
NK
NK
N
N
K-
Σ
Σ
(g.(0)) - g(o)) 1| + 4
g(
(Eq 13)
NK
NK
k=0
4E,
1
Σ
Σ
[4. A:(O())) (0 0;) + [[(O ||
+ +4E, +4B,-~11000 1100000000
NK
0=
(g.(0(.)) - -3((0)) 11 + + (0)(0))- - -((0)) 12
+ 4E
NK
Lemma 2
(a)
N
(A, - A (0 - -0:3|² +
N K
SE
SE
NK i=1 k=0
NK
i=1
k=
N K
16
Σ
Σ
E, Ex_ 0000 o1|" +AB*(c,c1) + -
NK
N K-1 1
N K-1 Σ =!(0
8
Ex A - A(O
|/10000
10 1000-0:1 -0:1² + &K, 7
NK 1=1 k=0
NK
1=1 k=0
+ 16E,- +14 + (B,((, + 4B, |((0)) 1
8(a + )2
N K-1
E + (0(0) - 8, 2
||
+ 8E
Σ Σ
N K-1
NK k=
NK
1=1 k=
+ 16E,, [AA)] + 4B² (e, e1) + 4B,_, [3(00)1 1
52

---

Published in Transactions on Machine Learning Research (06/2024)
24(c1 + 02)
Σ
N K
B B
8.1²
+ 24(01 + +z2)
N K-
Eg
0.
0-
||
NK
1.
NK
1=1 k=0
k=0
24(c1 + c2)
K-1
1
N K-1
E
00 0rr
+ SIE
NK
NK
k=
k=
+ 16 [ + 4 (c, + 18, -
=24(c1 + 02) 02))"E--,111) + 24(c1 + E 8- 2
1|
+ +24(c + (c,)))((c
N K
(,6, || 2 + +16 + +4B² (c,
(rB((r - -4B,- |10.)|
+ 8E,
NK
1=1 k=0
(6)
dB
+ +423p= +2((c1 B. 01
I (24(c1 + 02)2 + 16) | + +8(
NK
$AL3a²
+ - |10001 +B + 24(c + 02) (2)
(67)
where (a) is due to 2-Lipschitz of g. (i.e., Lemma 5) and the gradient heterogeneity (i.e., Lemma 2) and (b) is due to Lemma 13.
Next, bound B1 as:
E,- [B,]
-B--- 0 10-00 -000 001 + +2B
D: (0.), 0. 0*)
N
N K
+ 2F,
a
(0(0 t.kk
De
D. (0.), 02 - 0*)
NK
i=1
k=0
< E
0 0²1
+2aE,
<
1
Σ (0,) g(0.). 8¹) + (0(0)))
0, - 0-)
N
K-1
9i (0())) g.(O.). 0 0r)
+ 20
NK
N
$ 1B--1100
+ +2
N Σ (0)) - g(0.)| |0. 0
00|| + +2aF - 0: 8.)
K-1
(.(0 (0,) || + a 00 0-1
+
33
NK
K=
(Young's inequality Eq (12) with constant {3)
(0)
Ee-r
0.
0r
BaB(G, + 20E (8(8),, - 0r)
N
K-1
-((0)))((00))) // + 1 a -1000-0001 0-( 0012 0=
+
E,
NK
(6)
$ E,
E,_
0 0r
|2
+aaB(e, 2aB, (9(0)) 0. - 0r)
4a
+ aEsE 0.
+ E,
E-
(68)
E3
where (a) is due the fact that 0, 0* E H and the gradient heterogeneity; (b) is due to 2-Lipschitz property of function ÿ in Lemma 5.
53

---

Published in Transactions on Machine Learning Research (06/2024)
Incorporating the upper of B1 from Eq (68), Bg from Eq (66) and By from Eq (67) into Eq (61), we have:
E 0c+1 8-| 2
| s F 0. 0r) 1| + ( 0. 8*) + E p- [(0,)
+ (aSa + ((33i((c + 02) + 24{2) + 24a² (c) + 02) B,- 0. 0-)
1 4
+ - + + 22 E 0, 0r-7
|
+
61
9dB
(Aa
+ NK
a² + +3623a 4 + 4a & I, G² + 20 T2 +
+ t220t1 A
+ + 02) + + (24(c) + +1)) Ei-r
+ a
E3
+ 2aB(c, + 4a B² + 24a (a + 02) (c,
+ 3ati(a
[ + 2a (1)
(69)
Conditioned on Fi-2r 2r and using Lemma 14 to give upper bound of B. B2-27 0, 0,-7
we have:
2 2r 0.+1 0+
S R 2r 0: - 0²1² + 2a 25 g(0.). - 0r) + + 2r ((0.)
+ (afs + aa33i(c (c1 + 02) 248x) + 24a2 (c1 c2) E2-27 01 0-1 11
&
Ci 02
1
4
88 8a 27 [10. 1001 14a2 d3 52I30'
+a
+
245 +
$1
a
&
NK
1 1-p² p²
&
+4a
2 CTT
E A |
32000222f22 +a (177717)
==0
9d3
4a
a +36L2a 44 + 20
+ +202L1 Ee Br
NK
E2
4
4 &
+a
+ (c +02)+ + + + (24(c) + +z2) 2122rAdd
33
Ea
2aB((, + 4a B² (1) + 24a (aI + (c,6))
+ (a(i(a + 02) 12 (c, + 20 ' [(,GG)
(70)
If we choose step-size a such that a& = 99t + + + 4 < 2, E = E2 = Es, E, = acs +
(3E1(cc + + + 2462) + 24a + 02) < 28afi(c1 + +c2) 24 + 22)) < (0 + ce) (c1. > 1) and
& a/4 + (c + (2) + E + a² (24(c) + +22 + 16) < { ( + + (2), ie.
1
A + 24 E1
+
4
(a + 02 + 24 4)
a ك min
&
1,
24(c + 02) + 16 }.
6
+ 5C, (a: + +22)
12(c + 02)
which is sufficient to hold when a S min
+213=333111 1}. then we have:
El
E, 27 |0+z1 - 0-| 1
54

---

Published in Transactions on Machine Learning Research (06/2024)
E, E, 0. -001 0=1 22 (2
[(0,)), 02
8-) Ta |(00))
+ 30 Rx 2r 0, 00
+2 f 8a 2 27 |10: - 11] 14a
d2 52L3a'T
NK
p-
+4a² c2r Σ E1-2:1A1-) 32 4a 4a"dr
9d2 a +-3622a + 40 + 20 20 L2
4a 22 (
NK
E2
4 +3 +2) + a (24(c) + 02))² + 16) 20
4
+a
+ 2aB(c, - 4a² (B + 24a (a + 02) (c,
+ safi(c + 02) [2 (1) 2a L[GGGG
E. E1-27 0. - 0r + 2xE, 2- [(0)) 02 0r) + 4a 27 [(00)
(300gi + (2) + 16a 7 c1) E 27 0 0-1
+ 2872
a² a²dy +36 +36
1+ [ 1- (1+1-13
3r
Liat 4a L, 2a
NK
4a + 21 B + a 9 (6)(( t22) + 8a²c2r Σ F1-2r(Ard))
+
==0
2a 2aB(e, + 4a (22 + 24a + 02) (()6))
+ (a + (2 2a L
+ 6400a2ef F
Sa G
(71)
if we choose the step-size a such that the high order Oaa?) terms are dominanted by the first order terms O(a), i.e., B² e)) (o2 2a 3aEi + (e) i.e.
2 + +c)
a 2 minf 4B²(c, 2 2221"( 340033AAAAAA-PP0000-//////01---0 6400()497(4)) (6FTT3((,,)))) 1},
we have:
E2 27 0.1 8+] 2
E,-27 0, - 0r
+ 2aE, (g())), (g(0))
0, 80)
+ + E,,E2,2 -2 ((00) ?
0 - 1¹
+ +300g (c) + (2) + 7 E,-27 27
+ 2872
a&d +36 1+ 1+-
3r
Lza 1 + 44 L2 + 20
NK
1-
+ 4a
+ 2
E. E + of
+ ( + +2) + 802eTT Σ
Fr- Fx- (Ars)
E
s=0
+ 44B((, - 6cti(c1 + (c.
(72)
With Lemma (15), we have the upper bound of E, Pa-22((A (r),,,, 1e-2r(Ar and Σ. Fx- (A]-s). Then we have:
Er-2r 27 | 0-1
55

---

Published in Transactions on Machine Learning Research (06/2024)
2 27 0: - -011 + +2. (2(00),, 02 8-) +4a 27 [(0.)
+ (3005) (c1 + 02) + 16 (g)) BB Be-27 27 0, 0r
E4
+ 2872
108T
+
a²d3 + 366.2 +
1.2 + GT, + +
NK
1- p²
4a²
4a
9
20ITep
+2a L1 + a(
+ (c + 02) + +8a'e7"
c3
+ +4c2(K - -K)H²
Kag
1
+ 4ar((e, + bagi (al + (e)
(73)
If we choose step-size such that E₁ 30afi (ci 02) 16a I 32afi 02) and &g 5
2a L1 +
al 2 + +tt1)(c + 02) + Ba²e]r² s a + 14f1)(c1 + c2), i.e.,
(( 02)
1, (5 + til(e + +22)
S min 87
},
2L1 + 8c2
which is sufficient to hold when te(c)tes) 2L,+8r'
then have:
E, Ei-2r 2r Bc+1
0-|
S E.-22 27
0, 80|
+ +2aB, 2 ((())), 0r) + 4a2 222
+ #33052 (c1 + E2
0 14-001 8'
9 + 28r²
108T
a²d a
36L3 +
L3 + 4L, + +2L2G)
NK
1- 12
4a 14
c/3 + 20gL28
+ 14 +02)
+ 8 - 11)H²
Kaz 51
1-p
+ 4aB(c, 6aEi + (c,)))
(74)
1.2.6 Parameter Selection
With Lemma 16, we have:
E,-rr 0.t1 - 8-1
< (1+320 (1+32a5 + +02) (02))R,220 R,-27 0. - 0-1 + 2al.
(p(0.), 0, +-
0²) 2F, 27 g(0.)
9 2872
1087
a' + a 3662 + 1 1- p²
L3 + G2 + +2L2G)
NK
4a3 3
14
c3 + 20zL20
+ 141 + 02)
+ S 1)113
Kay
1-p
4a Aa + 6o9i (c) (2)
(75)
Proposition 4. If a satisfies the requirement as Lemma 16, choose E1
(1-7)² 32(c1+oo))
and T min (a
have:
2 11 14-27 Vi, - -Vo-
0, 0r 2
1
0 0 - 0-11² + + 2872
- -V))
E,
ad
D a
NK
56

---

Published in Transactions on Machine Learning Research (06/2024)
+ a²
36L2 +
1 p² L2 + G2, + +2l2G)
108T
66
1 L2
+ 8 - -1)r2) + +
+
(76)
K
where V/ = == = (1-7)w and C6
-
4 14
+ 14 + c2).
(1
Proof. Incorporating & = 32(()+(2))
(1-7)@
C6
-
4 (14 oz Ei
+ 1451)(c1 + 02) and 651(c1 + 02) S v into Eq (75), we have
2r
0 - 0-
2
S 1B--22 2r
0: - 0"
+ 2a 25 (0(0,), 02 0r) + 4a B, ((0.)
-0"1 |
a(1 - ))
9 + 2872
a a²dB + 3
(6622 +
108r
L3 + AL, + +2[2G)
NK
1 1 p²
a'cs
20gL2
2 1-p + + 1)H?²
K
+ + (c,
(4)
B: - 8'| - -2a(1 - -))
02 -00 -0 001 + +6a B2-27
1|2
2
I E2-27
Vo. - Vo-
0:-0" 0r 1
a(1 - 7) 27
9+ 2872
a²db- +
3 36I2 + 1 p²
108T
I + GL, + +2I2G)
NK
acc
20g
+ +oc((K - 1)H?
C3 + 1
K
4aB((,
+ tan (c,
-E-22 0. - 001
a(1 - 7))
E4-27
02 0r 0-1
a(1 - 77)
R, R4-27 0: 0r 1
2
2
16a 2x Vo.- V/-
2 9+ 287
a²
36L2
108T
L3 G2 2L22)
D
NK
02
a²co
+ 20zT2p + +oc7(K 1)H²
K
1-p
+ 4cBB(e,6)) + avg ( (e, 61)
- 00 1= a(1 - 70
01 0-|| 0-12=
a(1 - (1)
E, 27 Vo, - -Vo- 1
E1
E
2
2
D
2 9+ 282
108T
+ 1 2-
Ve. -Vo.
Vo-
+
a
d' +a3
36T22 +
12
+ 4T, 02 + +2
5
NK
1 p2
a'co
20gL2p + sc2(K 1)11?
2 1 1-p
K
+
(6)
0r - 0r| I|
a(1 - -7)
2 0, - 0012
a(1 - 7)
2 V/. - Vo-
I E,-27
Ex-27 27
2
4
+
2872
+o²
36122 + 1- p²
108T
12z + AL, + +L22G)
NK
a'co
203L2P
2
+ &of 1)H²
+
K
1 1-p
AaB(e, + au (c,
57

---

Published in Transactions on Machine Learning Research (06/2024)
| B
9 28r
$ (1 2004 Ex 8: - 8t - B1
V/. V/--
+
a²
NK
36L2 + 108T
3
13 + 4L1 + +L22
p-p²
a²
c²co
( +
1 + 867(K - 1)H?
+ 4AaB(e, + ou, (c,
(77)
K
where (a) is due to Lemma and the selection of parameter; (b) is due to 16a s a(l-2)a terms and using the fact 1 - 2av1 I 1 aV1, have:
Rearranging the
ov, av Vlo. Vo- vo-10- S <1 (1-ar)) (. 27 0 0'1 21-2r |1+1 - 0-)
9 2
a add
NK
108T
+ a²
361.2 + 1 p2
12 + O2 + 2L22
3 cB
203 L2p
+
bg +
+ 8c7 - 1)H2 + +4aB(c (G
(78)
K
- p
Then we finish the proof by dividing on both sides.
With these Lemmas, we are now ready to prove Theorem 2.
1.3
Proof of Theorem 2.
Given fixed local step-size aq 4K2c((KTT)
decrcasing effective step-sizes o₁ v(a+++1)
(1-7)a(at++1))
decreasing global step-sizes 0igg Ko: and weights w; = (a 1), we have:
G²2
(q) (T)
(T)
B(G +r*(e))))
E
V&r
Vo: Ô
(79)
K272
PNT AKT
Proof. We take the step-size a4 v(att+1) vl(att+1) for > In addition, we define weights w; (a + t) and define
w.O,
where W - ui T(a TT) By convexity of positive definite quadratic forms (Amin ( DΦ) 2 w >0), have
Via 2
EE
Vir
5
T
1
(a + 1)E
Vo, - -Vo-
W
1=1
2r-1
(a 1)B
Vo. - Vo-
2
+
(a + 1)E
Vo. Vo- 1
W
W
2
(2r () 27 - 1)
11
Σ
(a + ولاا|
Vo. 1358|1Vo
Vo- 1|3
< 1
W
W
2=
(76)
(2r () 2r - 1)G2
Vi + (a + + 1)G²
$ V/
+
W
2W
58

---

Published in Transactions on Machine Learning Research (06/2024)
T
(9 + 28
(a + t) + +a+ 33112 +
1- p² 1 + 4L, + +2InG)
108T
NK
(a + t)a²cs
20gL2p 1/7
+ -8ci(K - 1)H2
W
K
1
2=
[4(a + ()B(ee)) (a (a+ 1) (e)
(80)
27
where
Vo.. Vo- 1|
G We know that W Et Ei=2((+ S W Ei=i(a+ 17latess (a+1) S
8log(a+7) o9
and that
Et (a + t)at I nT
Plugging in these inequalities into Eq (80), we have:
w
1
4 E V/ Ve-
D
3v (a + (a
2T + 1)G²
4 28
+
2W
KT
8 Slog(a +T)
108T
36L2 + 1-
L3 + 4L, G² + 2L2G
1212
8cs log(a + T)
20gL20
8c2 1)11?
u9T2K
4B((,, 21 (c,G))
(a + (a + 2T + 1)G2
+ 4(9 + 28
2W
KT
8 8log(a +T)
K
36L2 + 108T
L2 + G2 + +LL20 + (+++ p²
20gL2p
8c7(K 1)
17
1-p
(mn(7)
+ +4B(c,a)G
(81)
where Equad(T (T) = (d + 2). Dividing on the both sides, changing in into v (v = (1 - 7))) and noting
that Co
11
+ (c1 + 02) = O+t,, we have:
" E1
V Vo- 2 < G22
+ Cquad(T) + (T)(T)
B(G,
+ +r9(a)))
(82)
K2T2
N2KT
AKT2
We finish the proof by using the inequality, E/|Vor Vo: 10 - 2B combining with the third point in Theorem 1.
Vor 12
12
V2r
+
2E
Vo;
Vo-
and
5
5
59

---

Published in Transactions on Machine Learning Research (06/2024)
J Simulation Results
J.1 Simulation results for the I.I.D. setting
In this subsection, we provide numerical results for FodTD(O) under the i..d. sampling setting to verify the theoretical results of Theorem 4. In particular, the MDP M of the first agent is randomly generated with a state space of size n = 100. The remaining MDPs are perturbations of M with the heterogeneity levels 0.1 and 6 = 0.1. The number of local steps is chosen as K 20. We evaluate the convergence terms of the rumning error Et |0 01l.2. Each experiment is run 10 times. We plot the mean and standard deviation across the 10 runs in Figure
102
N = 1
N 10
N
20
N 40
100
et
10-2
10
100
200
300
400
500
t
Figure 3: Performance of FedTD(O) with i.i.d. sampling with varying number of agents N. Solid lines denote the mean and shaded regions indicate the standard deviation over ten runs.
As shown in Fig 3, FedTD(O) converges for all choices of N. Larger values of N decreases the error, which is consistent with our theoretical analysis in Theorem 4.
60

---

Published in Transactions on Machine Learning Research (06/2024)
J.2 Simulation results for the Markovian setting
In this subsection, provide numerical results for FedTD(O) under the Markovian sampling setling to verify the theoretical results of Theorem 2. Here we generate all MDPs in the same way as the ii.d setting and choose the number of local steps as K = 20. All the remaining parameters are kept the same as those in the subsection J.1.
10a
N N=1 1
N 10
N 20
N 40
et
10
10-2
100
200
300
400
500
t
Figure 4: Performance FodTD(() with the Markovian sampling with varying number of agents N. Solid lines denote the mean and shaded regions indicate the standard deviation over ten runs.
As shown in Fig 4, FO) converges for all choices of N. Larger values of N decreases the error, which is consistent with theoretical analysis in Theorem 2.
61

---

Published in Transactions on Machine Learning Research (06/2024)
J.3
Simulation the effect of the heterogeneity level for the Markovian setting.
10'
750
1080
1550
1010
3500
300
100
18
1558
(a) Effect of the heterogeneity with different reward and Markov kernel heterogeneity.
(b) Effect of the heterogeneity with a fixed reward heterogeneity 6, and different reward heterogeneity 6.
20
N
N 10. 5.0
20.c 5.0
40.c 5.11
1340
1550
1800
2503
300
3083
2000
3008
2001
18/M
1968
2003
2000
(c) Effect of the heterogeneity with fixed Markov kernel heterogeneity and different reward heterogeneity
As shown in Fig (a) (c), conclude that increasing the level of heterogencity level will increase the size of the ball to which FedTD(() converge, which is completely consistent with our theoretical analysis in Theorem 2.
62


Reviews:
[{"review_id": "Aex4UWfsAH", "reviewer": "Reviewer_By6e", "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": "Starting with the strengths, though the math is fairly involved due to the mixing/long-term nature of the MDPs, the idea itself is reasonably straightforward and nicely built up from a perturbation analysis of stationary distributions and linear systems.  The algorithm structure itself is also intuitive and operationally it is a very simple extension of TD(0).\n\nThe paper has a number of weaknesses, but I hope that most of them can be mitigated with textual changes.\n\nFirst, in my opinion the paper does over claim and misrepresent some of its contributions.  An example of this is the statement \"Theorem 2 is significant in that it is the first result of its kind in MARL/FRL with heterogeneous environments...\".  I do not view this setting as multi-agent RL as an agent's actions has no effect the others' rewards.  In a sense, the agents in this setting do not even act as the shared policy is predetermined, and all must update and communicate their state-value parameters exactly as prescribed by the algorithm.  Additionally, the analysis of the algorithm implies that its performance only trends favorably when scaling the number of agents in the population stays relatively homogeneous.  Another example, it is also not totally clear how to apply FedTD(0) to actually perform RL.  Where as in the single-agent setting state-value estimation is a critical component of learning good policies, the agents in this setting cannot independently adjust their policy if they wish to continue participating in the shared policy evaluation.\n\nSecond, though the relative error bound on the probability transitions and norm-bound on the corresponding MRPs' rewards are easy to describe mathematically, it is hard to imagine situations where multiple agents will act in the exact same state/action-space where these components differ slightly.  Some concrete examples of applications would be helpful.\n\nThird, related to the most recent point, it is also difficult to follow exactly how the error bounds are related to the assumed probability/reward bounds.  In particular, the Eigenvalue/condition numbers of the matrices corresponding to the MDPs relate to non-intuitive structural aspects, and exactly how these combine when analyzing the \"average\" MDP is hard to imagine.\n\nFourth, the algorithm as stated is to some extent unimplementable in that the step-size parameters are, as far as I can tell, a function of the steady-state distribution of the average MDP.  i.e., it seems that the agents' would need to perform a non-trivial collaborative computation to first agree on the step-sizes.\n\nFinally, if my understanding is correct it is rather detrimental that the performance of the agents as a whole is only guaranteed to be as good as that of the two most dissimilar agents.  i.e., if there are N-1 agents acting in the same MDP and one acting in a very dissimilar MDP then all agents might be better off acting alone.", "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 introduces and analyzes FedTD(0)--an algorithm for federated policy evaluation.  Under the proposed framework, $N$ agents each take actions in individual MDPs according to a common policy $\\mu$.  The MDPs share the same finite state and action structure, but may have different rewards and transition probabilities.  The goal of an agent is to evaluate its own policy, i.e., estimate its own state-value function.\n\nWhen employing FedTD(0), each agent perform $K$ steps of TD(0) with linear function approximation starting with the same state-value parameters.  After $K$ steps, each agent broadcasts the difference between their current state-value parameters and the common starting parameters.  Then the agents derive new common state-value parameters by averaging the differences and begin a new round.\n\nThe paper proves that so long as the individual MDPs are similar enough that FedTD(0) can in expectation achieve a linear speedup with respect to the number of agents.  This result in and of itself is not surprising, e.g., if all the agents act in the same MDP then they effectively all perform $(N-1)*K$ additional updates per round.  What is much more nuanced though is the analysis of how the performance of FedTD(0) degrades as the MDPs start to differ.\n\nMore concretely, the paper assumes that each MDP has long-term dynamics that result in a unique steady-state distribution.  First, it shows that so long as the transition probabilities are relatively within $\\varepsilon$ for all pairs of agents and pairs of states that the L1-norm of the difference in steady-state distributions is bounded by $O(n\\varepsilon)$.\n\nSecond, it shows so long as the L2-norm of the difference between any two agents' MRP reward vectors is bounded by $\\varepsilon_1$, then the L2-norm of the difference between their optimal state-value function parameters is also bounded.\n\nThis leads to the development of FedTD(0), which can be roughly thought of as having the agents' collaboratively estimating the state-value function in the \"average\" MDP until the very last round where each individual estimates its own state-value function from a common starting point.  So long as the individual MDPs are pair-wise close, then they will be close to the average and this strategy can be advantageous.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Though it may appear by the relative length of my strengths and weaknesses lists that I am not in favor of accepting this paper, I do believe that it can be dramatically improved with appropriate textual additions.\n\nSpecifically, the addition of concrete examples of what constitutes settings that are favorable for FedTD(0) and what settings are not and why.  e.g., what constitutes a good heterogeneous population of agents for different structures of MDPs, and how quickly the performance of FedTD(0) degrade.  This is empirically explored to an extent in Section 5.1., but that can be complemented greatly by exploring how agent populations and MDP structures effect the terms in the bound and how well the bound predicts the performance in practice.\n\nAnother particular point of interest is discussing how should a group of agents decide to participate in FedTD(0), what step-sizes that they should use, how to combine the weights into a solution for each agent, or in what situations can an agent identify that it is not advantageous for them to continue cooperating in the FedTD(0) process.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VODqRs2eTA", "reviewer": "Reviewer_N4hB", "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": "Overall the paper is well written, organized and easy to follow. The explanation of technical contributions is clear and intuitive. However, some implications of the results are not immediately clear to me, and it would be much appreciated if the authors can provide some further discussions on them:\n\n1. What would be a reasonable choice of the number of local updates $K$, given that the total number of iterates $KT$ is fixed? The ideal choice of $K$ should be as large as possible without significantly worsening the error bound, so as to promote communication efficiency.\n\n2. The bias term from environmental heterogeneity appears to scale quite pessimistically with $\\epsilon$ and $\\epsilon_1$, and involves some terms that are hard to interpret (e.g., the conditional number of $\\bar{A}_i$). Would it be possible to derive the bound with terms such as $\\\\|V\\_{\\theta_i^\\star} - V\\_{\\theta_j^\\star}\\\\|$ instead?\n\n3. The first experiment investigates the effect of linear speedup with different number of agents. It is mentioned that the first MDP is randomly generated and the remaining MDPs are perturbations of the first one. If they are generated in an i.i.d. random way, then the improvement may actually results from the benign statistics property that the virtual MDP is converging to the first MDP.", "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 work focuses on federated RL, in particular the TD learning task with linear function approximation. The setting involves $N$ agents, each with its own environment (with heterogeneous transition kernels and rewards) to interact, and seek to evaluate a shared policy by communicating with a central server. The main results establishes an upper bound of the estimation error, that involves (i) a non-vanishing bias term due to environmental heterogeneity and (ii) vanishing terms that features a linear speedup with the number of agents. Numerical results are provided to verify the findings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Strengths And Weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gfwP5f8FtM", "reviewer": "Reviewer_nkSm", "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": "All in all, I really love the topic of the paper- a multiagent view on analyzing environments and policies that have some similarities and some differences. I think the model proposed by the authors is quite natural. Nonetheless, I think it could be better motivated in the paper. It’d be good for example to list down multiple possible domains where this could occur, and provide an example or two per each domain, possibly in the form of a table. For instance I can easily think of some domains (e..g supply chains, where customer demands and stock item transfers are held fixed, but the probabilities / quantities of demand or supply have different probability distribution, or traffic networks where the graph topology is fixed, but the travel times come from a different distribution).\n\nThe proposed method combines several building blocks in a creative  way: perturbation bounds on TD fixed points depending on the differences in the underlying MDPs, using a “virtual” MDP to approximate the dynamics of the federated algorithm, and using the “virtual” MDP to connect to federated optimization. A key result in the paper is that for low-heterogeneity regimes, exchanging model estimates leads to linear convergence speedups in the number of agents.\n\nAll in all, a very interesting paper on an important topic. Presentation could be improved a bit, but the paper is readable and clear (with a lot of details left in the later sections, which I think is a good call).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers federated reinforcement learning under environmental heterogeneity, looking into the policy evaluation problem. The authors consider a model where N agents interact with environments sharing the same state and action space, but with different reward functions and state transition probabilities. In the model, the agents may communicate through a central server. The key question studied is whether exchanging information can speed up the process of evaluating a common policy. The authors hence provide a finite-time analysis of a (federated) temporal difference learning algorithms, applying linear function approximation. The method accounts for the sampling and heterogeneity in the agents’ environments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please first see abpve regarding better / more detailed presentation of the motivation behind the paper (and possible domains). \n\nSecond, in terms of the exposition, I’ve found Figure 1 very helpful. I suggest extending that description. Additionally, the list of contributions of the paper is very clear. However, I would have appreciated a more details introduction to the topic of Federated Learning and RL. Readers are likely to come from all sorts of backgrounds, and it would be great to give more details on this topic. In particular, I’d also suggest exploring some connections to multitask learning in more detail; I realize this is about federated RL, but you base model is having MDPs that are similar in state and action spaces, and the theme of using what is known about the setting to speed-up learning has been explored in a broader context.", "broader_impact_concerns": "No concerns on my part.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall two reviewers recommended an accept and one reviewer recommended a reject. The primary reasoning for the reviewer recommending a reject is that the paper does not provide enough practical scenarios where the development in the paper will be useful. While this is true, I believe the paper still meets the criteria of TMLR in terms of correctness of results and there being some folks in the community who would be interested in the paper. The reviewers all seem to agree on this criteria.
Decision: Accept (poster)