Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning
Authors: Chenyu Zhang
Han Wang
Aritra Mitra
James Anderson
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning
federated learning
temporal difference learning
Primary area: reinforcement learning

Abstract: Federated reinforcement learning (FRL) has emerged as a promising paradigm for reducing the sample complexity of reinforcement learning tasks by exploiting information from different agents. However, when each agent interacts with a potentially different environment, little to nothing is known theoretically about the non-asymptotic performance of FRL algorithms. The lack of such results can be attributed to various technical challenges and their intricate interplay: Markovian sampling, linear function approximation, multiple local updates to save communication, heterogeneity in the reward functions and transition kernels of the agents' MDPs, and continuous state-action spaces.  Moreover, in the on-policy setting, the behavior policies vary with time, further complicating the analysis. In response, we introduce FedSARSA, a novel federated on-policy reinforcement learning scheme, equipped with linear function approximation, to address these challenges and provide a comprehensive finite-time error analysis. Notably, we establish that FedSARSA converges to a policy that is near-optimal for all agents, with the extent of near-optimality proportional to the level of heterogeneity. Furthermore, we prove that FedSARSA leverages agent collaboration to enable linear speedups as the number of agents increases, which holds for both fixed and adaptive step-size configurations.

Published as a conference paper at ICLR 2024
FINITE-TIME ANALYSIS OF ON-POLICY HETEROGE- NEOUS FEDERATED REINFORCEMENT LEARNING
Chenyu Zhang
Han Wang
Data Science Institute Columbia University New York, NY 10025, USA cz2736 www.@oowwmmmbiimccmm edu
Department Electrical Engineering Columbia University
New York, NY 10025, USA hw2 7 8 60columbia......mmmmo edu
Aritra Mitra
James Anderson
Department of Electrical and Computer Engineering NC State University Raleigh, NC 27695, USA mmitra@@ncsus edu
Department of Electrical Engineering Columbia University New York, NY 10025, USA j james. andersone co co wmbia.....m edu
ABSTRACT
Federated reinforcement learning (FRL) has emerged promising paradigm for reducing the sample complexity of reinforcement learning tasks by exploiting information from different agents. However, when each agent interacts with a po- tentially different environment, little to nothing is known theoretically about the non-asymptotic performance FRL algorithms. The lack of such results can be attributed to various technical challenges and their intricate interplay: Markovian sampling, linear function approximation, multiple local updates to save communi- cation, heterogeneity in the reward functions and transition kernels of the agents' MDPs, and continuous state-action spaces. Moreover, in the on-policy setting, the behavior policies vary with time, further complicating the analysis. In response, we introduce FedSARSA, a novel federated on-policy reinforcement learning scheme, equipped with linear function approximation, address these challenges and provide a comprehensive finite-time error analysis. Notably, we establish that FedSARSA converges policy that is near-optimal for all agents, with the tent of near-optimality proportional to the level of heterogeneity. Furthermore, we prove that FedSARSA leverages agent collaboration enable linear speedups as the number of agents increases, which holds for both fixed and adaptive step-size configurations.
INTRODUCTION
Federated reinforcement learning (FRL) (Qi et al., 2021; Nadiger et al., 2019; Zhuo et al., 2019), distributed learning framework that unites the principles of reinforcement learning (RL) (Sutton & Barto, 2018) 8) and federated learning (FL) (McMahan et al., 2017), is rapidly gaining prominence such edge computing (Wang al.,
for its wide range of real-world applications, spanning 2019), robot autonomous navigation (Liu et al., 2019), and Internet of Things (Lim et al., 2020). This paper poses an FRL problem, where multiple agents independently explore their own envi- ronments and collaborate to find near-optimal universal policy accounting for their differing en- vironmental models. FRI. leverages the collaborative nature of FL to address the data efficiency and exploration challenges of RL. Specifically, we expect linear speedups in the convergence rate and increased overall exploration ability due to federated collaboration. We use FRL autonomous driving (Liang et al., 2022) simple example to demonstrate our motivations and associated the- oretical challenges. In this scenario, the objective is to determine a strategy (policy) that minimizes collision probability. In contrast the single-agent setting, where policy is found by letting one vehicle interact with its environment, the federating setting coordinates multiple vehicles to inter- with their distinct pwvironments-compiee different cities and traffic patterns. Despite their

---

Published as a conference paper at ICLR 2024
aligned objectives, the environmental heterogeneity will produce distinct optimal strategies for each vehicle. Our goal is to find a universal robust strategy that performs well across all environments.
Tailored for such tasks, we propose novel algorithm, FedSARSA, integrating SARSA, classic on-policy temporal difference (TD) control algorithm (Rummery & Niranjan, 1994; Singh & Sut- ton, 1996), into federated learning framework. On one hand, want to leverage the power of federated collaboration to collect more comprehensive information and expedite the learning pro- cess. On the other hand, we want to utilize the robustness and adaptability of on-policy methods. To elaborate, within off-policy methods, such as Q-learning, agents select their actions according to fixed behavior policy while seeking the optimal policy. In contrast, on-policy methods, such as SARSA, employ learned policies as behavior policies and constantly update them. By doing so, on- policy methods tend to learn safer policies, as they collect feedback through interaction following learned policies, and are more robust to environmental changes compared to off-policy methods (see Sutton& & Barto (2018, Chapter 6)). Additionally, when equipped with different policy improvement operators, on-policy SARSA is more versatile and can learn broader range of goals than off off-policy Q-learning (see Section 4 and Appendix C). Formally analyzing our federated learning algorithm poses several multi-faceted challenges. We outline the most significant below.
Time-varying behavior policies. In off ooflpo FRL with Markovian sampling (Woo et al., 2023; Khodadadian et al., 2022; Wang et al., 2023a), agents' observations are not i.i.d.; they are gen- erated from fime-homogeneouu ergodic Markov chain as agents follow a fixed behavior policy. Such an ergodic Markov chain converges rapidly to steady-state distribution, enabling off-policy methods to inherit the theoretical guarantees for i.i.d. and mean-path cases (Bhandari al., 2018; Wang et al., 2023a). In contrast, on-policy methods update agents' behavior policies dynamically, rendering their trajectories nonstationary. Therefore, previous analyses for off off-policy methods, whether involving Markovian sampling or not, do not apply to our setting. Specifically, it remains unknown if the trajectories generated by on-policy FRL methods converge, and if they do, how this nonstationarity affects the convergence performance.
Environmental heterogeneity in on-policy planning. In an FRL instance, it is impractical to as- sume that all agents share the same environment (Khodadadian et al., 2022: Woo et al., 2023). In planning task, this heterogeneity results in agents having distinct optimal policies. Thus, to affirm the advantages of federated collaboration, it is crucial to precisely characterize the dispari- ties in optimality. Only two FRI. papers have considered heterogeneity: Jin et al. (2022) explored heterogeneity in transition dynamics without linear speedup, and Wang et al. (2023a) considered heterogeneity in prediction task (policy evaluation). Beyond these studies, other research has addressed heterogeneity primarily within the domains of control design (Wang et al., 2023c) and system identification (Wang et al., 2023b). Unfortunately, neither the characterizations nor anal- yses of heterogeneity from the previous work apply to on-policy FRI. Specifically, heterogeneity in agents' optimal policies implies heterogeneity in the behavior policies, which could lead to drastically different local updates across agents, negating the benefits of collaboration.
Multiple local updates and client drift. In the federated learning framework, agents communicate with central server periodically to reduce communication cost, and conduct local updates be- tween communication rounds. However, these local updates push agents to local solutions at the expense of the overall federated performance, phenomenon known client drift (Karimireddy et al., 2020). Uniquely within our setting, client drift and nonstationarity amplify each other.
Continuous state-action spaces and linear function approximation. To better model real-world scenarios, consider continuous state-action spaces and employ linear approximation for the value function. Unfortunately, RL methods with linear function approximation (LFA) are known to exhibit less stable convergence when compared to tabular methods (Sutton & Barto, 2018; Gordon, 1996). Besides, the parameters associated with value function approximation no longer maintain an implicit magnitude bound. This concern is particularly relevant in on-policy FRL, where the client drift and the bias from nonstationarity both scale with the parameter magnitude.
Given these motivations and challenges, we ask
Can an agent expedite the process of learning its own near-optimal policy by leveraging information from other agents with potentially different environments?
'Considered i..dd and Markovian sampling, but only established linear speedup result for the i.i.d. case.
2

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of finite-time analysis for value-based FRL methods. LSP and LFA represent linear speedup and linear function approximation under the Markovian sampling setting; Pred and Plan represent prediction (policy evaluation) and planning (policy optimization) tasks, respectively.
Hetero- geneity
Markovian Sampling
Behavior Policy
Work
LSP
LFA
Task
Doan et al. (2019)
x
X
X
Pred
Fixed
Jin et al. (2022)
X
X
X
Plan
Fixed
Khodadadian al. (2022)
X
Pred & Plan
Fixed
Shen et al. (2023)
Plan
Adaptive
Wang et al. (2023a)
Pred
Fixed
Woo et al. (2023)
Plan
Fixed
Our work
Pred Plan
Adaptive
We provide complete non-asymptotic analysis of FedSARSA, resulting in the first positive answer to the above question. We situate our work with respect to prior work in Table 1. A summary of our contributions is provided below:
Heterogeneity in FRL optimal policies. We formulate practical FRL planning problem in which agents operate in heterogeneous environments, leading to heterogeneity in their optimal policies as agents pursue different goals. We provide an explicit bound this heterogeneity in optimality, validating the benefits of collaboration (Theorem 1).
Federated SARSA and its finite-sample complexity. We introduce the FedSARSA algorithm for the proposed FRL planning problem and establish a finite-time error bound achieving a state-of- the-art sample complexity (Theorem 2). At the time of writing, FedSARSA is the first provably sample-efficien on-policy algorithm for FRL problems.
Convergence region characterization and linear speedups via collaboration. We demonstrate that when constant step-size is used, federated learning enables FedSARSA to exponentially verge to a small region containing agents' optimal policies, whose radius tightens as the number of agents grows (Corollary 2.1). For linearly decaying step-size, the learning process enjoys linear speedups through federated collaboration: the finite-time error reduces as the number of agents increases (Corollary 2.2). We validate these findings via numerical simulations.
RELATED WORK
Federated reinforcement learning. A comprehensive review of FRL techniques and open prob- lems was recently provided by Qi et al. (2021). FRL planning algorithms can be broadly catego- rized into two groups: policy- and value-based methods. In the first category, Jin et al. (2022); Xie & Song (2023) considered tabular methods but did not demonstrate any linear speedup. Fan et al. (2021) considered homogeneous environments and showed a sublinear speedup property. In the second category, Khodadadian al. (2022); Woo al. (2023) investigated federated Q-learning and demonstrated linear speedup under Markovian sampling. However, these studies did not examine the impact of environmental heterogeneity, pivotal aspect in FRI. To bridge this gap, Wang et al. (2023a) presented finite time analysis of federated TD(0) that can handle environmental hetero- geneity. To take advantage of both policy- and value-based methods, Shen et al. (2023) analyzed distributed actor-critic algorithms, but only established the linear speedup result under i.i.d. sam- pling. Table summarizes the key features of these value- methods, including our work. There also some works developed for studying the distributed version of RL algorithms: Doan et al. (2019) and Liu & Olshevsky (2023) provided a finite-time analysis of distributed variants of TD(0); however, their analysis is limited to the i.i.d sampling model.
SARSA with linear function approximation. aggele SARSA is on-policy TD control algorithm proposed by Rummery& & Niranjan (1994) and Singh & Sutton (1996). To accommo- date large even continuous state-action spaces, Rummery & Niranjan (1994) proposed function
3

---

Published as a conference paper at ICLR 2024
approximation. We refer to SARSA with and without LFA linear SARSA and tabular SARSA respectively The asymptotic convergence result of tabular SARSA was first demonstrated by Singh et al. (2000). However, linear SARSA may suffer from chattering behavior within region (Gordon, 1996; 2000; Bertsekas & Tsitsiklis, 1996). With a smooth policy improvement strategy, Perkins & Precup (2002) and Melo al. (2008) established the asymptotic convergence guarantee for linear SARSA. Recently, the finite-time analysis for linear SARSA was provided by Zou et al. (2019).
3 PRELIMINARIES
3.1 FEDERATED LEARNING
Federated Learning (FL. is distributed machine learning framework designed to train models using data from multiple clients while preserving privacy, reducing communication costs, and accommo- dating data heterogeneity. We adopt the server-elient model with periodic aggregation, akin well- known algorithms like FedAvg (McMahan et al., 2017) and FedProx (Sahu al., 2018). Agents (clients) perform multiple local updates (iterations of a learning algorithm) between communication rounds with the central server. During communication round, agents synchronize their local pa- rameters with those aggregated by the server. However, this procedure introduces client-drift issues (Karimireddy et al., 2020; Charles & Konečný, 2021), which can hinder the efficacy of federated training. This problem is particularly pronounced in our on-policy FRL setting, where client drift is amplified due to the interplay with other factors.
3.2 MARKOV DECISION PROCESS AND ENVIRONMENTAL HETEROGENEITY
We consider N agents that explore within the same state-action space but with potentially different environment models. Specifically, agent i's environment model characterized by Markov deci- sion process (MDP) denoted by ()) (S,A. A,) ((), p()),))))))))))))))))) Here, S denotes the state space, A is the action space, (() : S x A + [o, R] is a bounded reward function, E (0, is the discount factor, and p() is the Markov transition kernel such that (s,s') is the probability of agent i's transition from state 8 to following action a. While all agents share the same state-action space, their reward functions and state transition kernels differ. Agents select actions based their policies. A policy π maps state to a distribution over actions, (aas) denotes the probability of an agent taking action state s.
Assumption 1 (Uniform ergodicity). For each E [N]. the Markov chain induced by any policy and state transition kernel p() is ergodic with uniform mixing rate. In other words, for any MDP M and candidate policy æ, there exists steady-state distribution n/ as well as constants m, 2 and p E (0, 1). such that
Pa (S
=
SQ ((1) =s)
-1/ 1ly S <mpti.
sup sup SES
where || ||TV the total variation distance.
Assumption 1 is standard assumption in the RL literature needed provide finite-time bounds under Markovian sampling (Bhandari et al., 2018; Zou et al., 2019; Srikant & Ying, 2019).
Agents operate in their own environments and may have their own goals. We collectively refer to the differences in the transition kernels and rewards as environmental heterogeneity. Intuitively, collaboration among agents is advantageous when the heterogeneity is small, but can become coun- terproductive when the heterogeneity is large. We now provide two natural definitions for measuring environmental heterogeneity.
Definition (Transition kernel heterogeneity). We capture the transition kernel heterogeneity using the total variation induced norm: max [JE[N]
p00 pb) TV
We use the functional-anale definition of the total variation, which is twice the quantity suP lp(A)) for any signed measure p on
4

---

Published as a conference paper at ICLR 2024
where with slight abuse of notation, define
PP|TT = sup 1IqP/TTV= (EP(SxA) rvl
sup (EP(SxA) gglrv=1
(ss,
dddda
SxA
where P(S A) is the of probability measures S x A. By the triangle inequality and the uniform bound on rewards, R, we have Ep S 2.
Definition (Reward heterogencity). We capture the reward heterogeneity using the infinity norm:
||:0) r()
max [JE[N]
where ||r sups,aExA (r(s, a)). By the triangle inequality, we have Er S 2.
3.3
VALUE FUNCTION AND SARSA
An RL planning task aims to maximize the expected return, defined as the accumulated reward of trajectory. For a given policy v, the expected return a state-action pair (s, a) is captured by the Q-value function:
gx(s, a) = 15 Σ ai) s, A, a = as) + 7IE, (S,, A1) = Ao a).
Ta (x.a)
where the expectation is taken with respect to a transition kernel that follows the policy æ (except for the initial action, which fixed to a). For any MDP, there exists an optimal policy æ. such that On (s, a) 2 (=(s,a) for any other policy and state-action pair (8, a). This puper focuses FRI FRI. problem where all agents aim find a universal policy that is near-optimal for all MDPs under low-heterogeneity regime.
To find such an optimal policy for a single agent, SARSA updates the estimated Q-value function based on (1) by sampling and bootstrapping. With the updated estimation of the value function, SARSA improves the policy via policy improvement operator. By alternating policy evaluation and policy improvement, SARSA finds the optimal policy within the policy space. The tabular SARSA for a single agent can be described by the following update rules:
Q (st,aa) {
+ Qs1, +a (r(ss, ad) + +QQ ($t+1, a(41) Q (z),
+ I+(((s441,
where is the estimated Q-value function, is the learning step-size, and I' is the policy improve- ment operator. We provide further discussion on the policy improvement operator Section 4.
3.4 LINEAR FUNCTION APPROXIMATION AND NONLINEAR PROJECTED BELLMAN EQUATION
When the state-action space is large or continuous, tabular methods are intractable. Therefore, we employ linear approximation for the Q-value function (Rummery Niranjan, 1994). For a given feature extractor
S A + Rd we approximate the Q-value function as Qu(s, a) Φ(s, a)T where 0 E θ C d is parameter vector to be learned. Without loss of generality, we assume that [lo(s, a2 < 1 for every state-action pair (s, a). Linear function approximation translate the task of finding the optimal policy to that identifying the optimal parameter that solves the nonlinear projected Bellman equation:
Qo -I,
(3)
where T, the Bellman operator defined by the right-hand side of (I), and 1l, is the orthog- onal projection onto the linear subspace spanned by the range of the & using the inner product (ar, y) = (ssyy) [=(S, A)" y(S. A)). Equation (3) reduces to the linear Bellman equation used policy evaluation when the policy π is fixed (Tsitsiklis & Van Roy, 1996; Bhandari et al., 2018), and to the Bellman optimality equation used Q-learning when the policy improvement operator is the greedy selector (Watkins & Dayan, 1992; Melo al., 2008).
5

---

Published as a conference paper at ICLR 2024
4 ALGORITHM
We now develop FedSARSA; a federated version of linear SARSA. In FedSARSA, each agent explores its own environment and improves its policy using its observations, which refer as local updating. Periodically, agents send the parameter progress to the central server, where the parameters get aggregated and sent back each agent. We present FedSARSA in Algorithm I.
Local update. Locally, agent updates its parameter using the SARSA update rule. With linear function approximation, the Q-value function update in (2) becomes
0 = 0 + +aght (3) (0
where at is the step-size and 9r (
is defined
Pi (0: = o(s a)r (s, tols a) -((ss" s'~P((((s,)) d' N o'
(4) We refer to 9t as a semi semi-gradien as it resembles a stochastic gradient but does not represent the true gradient of any static loss function (Barnard, 1993). Also, we introduce a subscript to the semi-gradient to indicate that it depends on the policy Tof0) at time step I.
Policy improvement. We assume that all agents use the same policy improvement operator T, which returns a policy π for any Q-value function. Since we consider linearly approximated Q- value functions, we can view the policy improvement operator acting on the parameter space: We denote the policy resulting from the parameter 6 as = r(f). To ensure
I 0 + the convergence of the algorithm, we need the following assumption on the policy improvement operator's smoothness.
Assumption (Lipschitz continuous policy improvement operator). The policy improvement oper- ator is Lipschitz continuous in TV distance with constant L:
[T, (-Is) - To, (+Is)]l I L| 82112. V01,02 E O, s S.
Furthermore, S w/ (Ho), where H, a, and w are problem constants to be defined in Appendix.
When the action space is of finite measure, Assumption 2 is equivalent that in Zou et al. (2019). This assumption is standard for linear SARSA (Zou et al., 2019; Perkins & Precup, 2002; Melo al., 2008). As shown in (De Farias & Van Roy, 2000; Perkins & Pendrith, 2002: Zhang et al., 2022), linear SARSA with noncontinuous policy improvement may diverge.
An example policy improvement operator satisfying Assumption is the softmax function with suitable temperature parameter (Gao & Pavel, 2017). In contrast, the deterministic greedy policy improvement employed in Q-learning an illustrative case where Assumption does not hold. Additionally, when the policy improvement operator maps to a fixed point æ, SARSA reduces to TD learning, which evaluates the policy æ. Generally, SARSA searches the optimal policy within the policy space I' I'()) determined by the policy improvement operator and the parameter space.
Server side aggregation. FedSARSA adds an additional aggregation step to parallelize lincar SARSA. During this step, agents communicate with central server by sending their parameters or parameter progress over given period. The central server then aggregates these local parameters and returns the updated parameters the agents. Intuitively, if the agents' MDPs are similar, i.e., the level of heterogeneity is low, then exchanging information via the server should benefit each agent. This is precisely the rationale behind the server-aggregattin step. In general, K is selected to strike a balance between the communication cost and the accuracy in FL.
Besides averaging, we add a projection step ensure stability of the parameter sequence. This technique is commonly used in the literature on stochastic approximation and RL (Zou et al., 2019; Bhandari al., 2018; Qiu al., 2021; Wang et al., 2023a). In practice, it is anticipated that an implicit bound on the parameters exists without requiring explicit projection.
For case of presentation, we assume all agents share the same step-size. Our analysis handles agents using their own step-size schedule, long as each agent's 's step-size falls within the specified range.

---

Published as a conference paper at ICLR 2024
Algorithm 1: FedSARSA
input Initial parameter 80) 8g
for 1 , do
for each agent = ,,...,N N do in parallel [
// policy improvement Sample observation (st ar 2411, (411) following policy n, (8)
(1)
(2)
off =05² + ange where 9r is defined in (4)
// local update
if + 1 =0 0 (mod K) then
// every K iterations
0++ He E 0411
// federated aggregation
Set 0221 oc+1 for each agent i [N]
5 ANALYSIS
We begin our analysis of FedSARSA by establishing perturbation bound on the solution (3), which captures the near-optimality of the solution under reward and transition heterogeneity. We then provide a finite-time error bound of FedSARSA, which enjoys the linear speedup achieved by the federated collaboration. Building this, we discuss the parameter selection of our algorithm.
5.1 NEAR OPTIMALITY UNDER HETEROGENEITY
We consider an FRL task where all agents collaborate to find universal policy. However, due to environmental heterogeneity, each agent has potentially different optimal policy. Therefore, it is essential to determine the convergence region of our algorithm, and how relates to the optimal parameters of the agents. To show that find a near-optimal parameter for all agents, to characterize the difference between the optimal parameters of agents. Given the operator r, we denote by g(9) the unique solution to (3) for MDP M The next theorem bounds the distance between agents' optimal parameters as a function of reward- and transition kernel heterogeneity.
need
Theorem (Perturbation bounds on SARSA fixed points). There exist positive problem dependent constants w, H, and a such that
max -1000-0011 [JE[N]
[1]] Re, + Haep ((pp:
w
where Ep and e, are the perturbation bounds environmental models defined in Definitions I and 2.
We explicitly define the constants in Theorem 1 and show that w= in Appendix I. In the next subsection, we demonstrate that there exists parameter 6x such that |]e.0) -050-A.0
-10(0)___ -0 S A(ep. ww. and Algorithm converges to a neighborhood of é, whose radius is also of (A G, (1-7)). Since ((p,,r) 6r) O(G + G,). when the environmental heterogeneity is small, these results guarantee that 0, near-optimal for all agents.
Theorem 1 is the first perturbation bound on nonlinear projected Bellman fixed points. Wang et al. (2023a) established similar perturbation bounds for linear projected Bellman fixed points using perturbation theory of linear equations. However, it is crucial to note that their approach does not extend to our setting where (3) is nonlinear.
5.2 -INITE- TIME ERROR AND LINEAR SPEEDUP
We now provide the main theorem of the paper, which bounds the mean squared error of Algorithm recursively, and directly gives several finite-time error bounds.
Theorem 2 (One-step progress). Let { be the parameters returned by Algorithm 1 and
Nx N e( Then, there exist positive problem dependent constants w, C1, Cz, Cs, Ca. and parameter 0,, such that max ||0.0) 0.1l < A(cp,t)) ///p,,)//w /w, and for any t N, it holds that
E. 0 0.1 < a. E 00 0 CaCCTA((pp:)) + a,Oo/N of of 04C4. (5)
7

---

Published as a conference paper at ICLR 2024
Explicit definitions of the constants are provided in Appendix J.
On the hight-hand side of (5), the first term a contractive term that inherits its contractivity from the projected Bellman operator; the second term accounts for heterogeneity; the third term captures the effect of noise where the variance gets scaled down by a factor of N (linear speedup) due to collaboration among agents; the last two terms represent higher-order terms, which are negligible, compared to other terms. In the following two corollaries, we study the effects of using constant and decaying step-sizes in the above bound.
Corollary 2.1 (Finite-time error bound for constant step-size). With a constant step-size at = ao S w/(20002K + 8 In(m/ (pw))) ()) for any T E N. we have
E 0r -000 < 4e Loow
!
2
nouT |00 - 0
++-
1 w
((+++))
ao (e))) -
C2 N
+agO's ag
Corollary 2.2 (Finite-time error bound for decaying step-size). With a linearly decaying step-size 0t = 41( + ++ a)), where > is to guarantee that og S min(1/(8K), w/64), there exists convex combination 0r of (0: (0+)2-o such that
112 E - - (1->)²
O
1² T (1- NT
A?(ene)))
112 (1-7)3
① NT
1
+
(e H²
We now discuss the implications of the above theoretical guarantees.
Convergence region. From Corollary 2.1, with a constant step-size a, FedSARSA exponentially converges to ball around the optimal parameter 8 of each agent. The radius of this ball is governed by two objects: (i) the level of environmental heterogeneity; (ii) the inherent noise in our model. In the absence of heterogeneity, the above guarantee is precisely what one obtains for stochastic ap- proximation algorithms with a constant step-size (Zou et al., 2019; Srikant & Ying, 2019; Bhandari et al., 2018). The presence of heterogeneity manifests itself the O(A /1 (1-7)) = (Eppte,)
term in the convergence region radius. Since the optimal parameters of the agents may not be iden- tical (under hetcrogeneity), such a term is generally unavoidable.
Linear speedup. Turning our attention to Corollary 2.2 (where we use a decaying step-size), let us first consider the homogeneous case where E, = E, = When T 2 N, the (LL((NT) rate we obtain in this case is the best one can hope for statistically: with T data samples per agent and N agents, one can reduce the variance of our noise model by at most NT. Thus, for a homogeneous setting, our rate is optimal, and clearly demonstrates an Nolddd linear speedup over the single-agent sample-complexity of O(1/T) in Zou et al. (2019). In this context, our work provides the first such bound for a federated on-policy RL algorithm, and complements results of a similar flavor for the off-policy setting in Khodadadian et al. (2022). When the agents' MDPs differ, via collaboration, each agent is still able to converge at the expedited rate of (1/NN) around the optimal parameter of each agent. The implication of this result is simple: by participating in federation, each agent can quickly (i.e., with Nfoodd speedup) find OOpp + 6 aappproxiiaeee solution of its optimal parameter: using such an approximate solution as an initial condition, the agent can then fine-tune (personalize) based on its own data converge to its own optimal parameter exactly (in mean-squared sense). This is the first result of its kind for federated planning, and complements the plethora of analogous results in federated optimization (Sahu al., 2018; Khaled et al., 2019; Li et al., 2019; Koloskova et al., 2020; Woodworth et al., 2020; Pathak & Wainwright, 2020; Wang et al., 2020: Mitra al., 2021; Mishchenko et al., 2022). Arriving the above result, however, poses significant challenges relative to prior art. We now provide insights into these challenges and our strategies to overcome them.
ball of radius O(ep + cx)
5.3 PROOF SKETCH: ERROR DECOMPOSITION
Our main approach of proving Theorem 2 is to leverage the contraction property of the Bellman equation (3) to identify a primary "descent direction." " Algorithm then updates the parameters along this direction with multi-sourced stochastic bias. We provide an informal mean squared error decomposition (formalized in Appendix I.1 to illustrate this idea:
EE 00+1 0-11² < recursion + descent direction gradient heterogeneity + client drift + gradient progress + mixing + backtracking + gradient variance.
8

---

Published as a conference paper at ICLR 2024
Some of these terms commonly appears in an FRL analysis: the descent direction is given by the contraction property the Bellman equation (3) when the policy improvement operator suffi- ciently smooth (Appendix I.2): the client drift represents the deviation of agents' local parameters from the central parameter, which controlled by the step-size and synchronization period (Ap- pendix 1.4); the mixing property (Assumption 1) allows stationary trajectory rapidly reach to steady distribution (Appendix 16). We highlight some unique terms in our analysis.
Gradient heterogeneity. This accounts for the local update heterogeneity, which scales with the environmental heterogeneity. The effect of time-varying policies coupled with multiple local updates accentuates the effect of such heterogeneity. Thus, particular care is needed to ensure that the bias introduced by heterogeneity does not compound over iterations (Appendix I.3).
Backtracking. FedSARSA possesses nonstationary transition kernels. To deal with this challenge and use the mixing property of stationary MDPs, we virtually backtrack period т: starting at time step I-T, fix the policy r(0 for agent and consider subsequent virtual trajectory following this fixed policy. The divergence between the updates computed on real and virtual observations is controlled by the step-size a and backtracking period 7 (Appendix I.7).
Gradient progress. Note that the steady distribution in the mixing term corresponds to an old policy. Since the backtracking period small, the discrepancy (progress) between this old policy and the current one is small (Appendix I.5).
Gradient variance. While one can directly use the projection radius bound the semi-gradiens vari- ance, such an approach would fall short of establishing the desired linear speedup effect. To achieve the latter, we need a more refined argument that shows how one can obtain a "variance-reductioon effect by combining data generated from non-identical time-varying Markov chains (Appendix 1.8).
SIMULATIONS
We create finite state space of size |S| 100, action space of |A| = 100, feature space of dimension = 25, and set y = 0.2 and = 10. The actions determine the transition matrices by shifting the columns of reference matrix. The synchronization period is step-size of oz = 0.01. For the full experiment setup, please refer to Appendix C. In Figure 1, we plot the mean squared error averaged over runs for different heterogeneity levels and numbers of agents. The simulation results are consistent with Corollary 2.1 and demonstrate the robustness of our method towards environmental heterogeneity. Additional simulations, including federated TD(0) and on-policy federated Q-learning covered by our algorithm, can be found in Appendix C.
K 10, and the
1000
MSS
(a) Ep E
(b)
Ep
(c) Ep
Cy
Figure 1: Performance of FedSARSA under Markovian sampling.
7 CONCLUSION
We proposed straightforward yet powerful on-policy federated reinforcement learning method: FedSARSA. Our finite-time analysis of FedSARSA provides the first theoretically conformation of the statement: an agent can expedite the process of learning its own near-optimal policy by leveraging information from other agents with potentially different environments.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
JA is partially supported by Columbia Data Science Institute and NSF grants ECCS 2144634 & 1350.
REFERENCES
Etienne Barnard. Temporal-difference methods and Markov models. IEEE Transactions on Systems, Man, and Cybernetics, 23(2):357-365, 1993.
Dimitri Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. finite time analysis of temporal difference learning with linear function approximation. In Conference Learning Theory, pp. 1691-1692. PMLR, 2018.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-311, 2018.
Zachary Charles and Jakub Konečný. Convergence and accuracy trade-off's in federated learning and meta-learning. In International Conference on Artificial Intelligence and Statistics, pp. 2575- 2583. PMLR, 2021.
Daniela Pueci De Farias and Benjamin Van Roy. On the existence of fixed points for approximate value iteration and temporal-different learning. Journal of Optimization theory and Applica- tions, 105:589-608, 2000.
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.
Xiaofeng Fan, Yining Ma. Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low. Fault-tolerant federated reinforcement learning with theoretical guarantee. Advances in Neural Information Processing Systems, 14:1001-1 2021.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv: 1XXi::1744000003 2017.
Geoffrey J. Gordon. Chattering in SARSA(A). CMU Learning Lab Technical Report, 1996.
Geoffrey J. Gordon. Reinforcement learning with function approximation converges region.
Advances in neural information processing systems, 13, 2000.
Hao Jin, Yang Peng. Wenhao Yang. Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 18-37. PMLR, 2022.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143, PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárík. First analysis of local GD on hetero- geneous data. arXiv preprint 9xXiv:/90.004715, 2019.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under Markovian sampling. In International Conference on Machine Learning, pp. 10997-11057. PMLR, 2022.
Anastasia Koloskova, Nicolas Loizou, Sadra Borciri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381-5393. PMLR, 2020.
Xiang Li. Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg non-iid data. arXiv preprint 190: 2019.
10

---

Published as a conference paper at ICLR 2024
Xinle Liang, Yang Liu, Tianjian Chen, Ming Liu, and Qiang Yang. Federated transfer reinforcement learning for autonomous driving. In Federated and Transfer Learning, pp. 357-371. Springer, 2022.
Hyun-Kyo Lim, Ju-Bong Kim, Joo-Seong Heo, and Youn-Hee Han. Federated reinforcement learn- ing for training control policies on multiple IoT devices. Sensors, 20(5):1359, 2020.
Boyi Liu, Lujia Wang, and Ming Liu. Lifelong federated reinforcement learning: A learning ar- chitecture for navigation cloud robotic systems. IEEE Robotics and Automation Letters, 4(4); 4555-4562, 2019.
Rui Liu and Alex Olshevsky. Distributed TD(0) with almost communication. IEEE Control Systems Letters, 2023.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson. and Blaise Aguera y Arcas. Communication-eficien learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Francisco S Melo, Sean Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on Machine learning, pp. 664 671, 2008.
Sean Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Con- ference Machine Learning, pp. 15750-15769. PMLR, 2022.
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, 14:14606-146111 2021.
Yu Mitrophanov. Sensitivity and convergence of uniformly ergodic markov chains. Journal of Applied P Probability, 42(4):1003-1014, 2005.
Chetan Nadiger, Anil Kumar, and Sherine Abdelhak. Federated reinforcement learning for fast personalization. In 2019 IEEE Second International Conference on Artificial Intelligence and Knowledge Engineering (AIKE), pp. 123-127. IEEE, 2019.
Reese Pathak and Martin Wainwright. FedSplit: An algorithmic framework for fast federated optimization. arXiv preprint arXiv:2005.05238, 2020.
Theodore Perkins and Doina Precup. A convergent form of approximate policy iteration. Advances in neural information processing systems, 15, 2002.
Theodore Perkins and Mark D Pendrith. On the existence of fixed points for Q-learning and SARSA in partially observable domains. In ICML. pp. 490-497, 2002.
Jijju Qi. Qihao Zhou, Lei Lei, and Kan Zheng. Federated reinforcement learning: Techniques, applications, and open challenges. arXiv preprint 10Xiv:2 2021.
Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor-
critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652-666) 2021.
Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Conference on Learning Theory, pp. 3185-3205. PMLR, 2020.
Gavin Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems, vol- ume 37. University of Cambridge, Department of Engineering Cambridge, UK, 1994.
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. On the convergence of federated optimization in heterogeneous networks. arXiv preprint arXiv: 1el..8112.00210 2018.
11

---

Published as a conference paper at ICLR 2024
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEEE Transactions on Signal Processing, 2023.
Satinder Singh, Tommi Jaakkola, Michael Littman, and Csaba Szepesvári. Convergence results for single-step on-policy reinforeementtleariing algorithms. Machine learning, 38:287-308, 2000.
Satinder P Singh and Richard S Sutton. Reinforcement learning with replacing eligibility traces. Machine learning, 22(1):123-111 1996.
Rayadurgam Srikant and Lei Ying. Finite-time enror bounds for linear stochastic approximation andtd learning. In Conference Learning Theory, pp. 2803-2830, PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
John Tsitsiklis and Benjamin Van Roy. Analysis of approximation. Advances in neural information processing systems, 9, 1996.
diffference learning with function
Han Wang, Aritra Mitra, Hamed Hassani, George J Pappas, and James Anderson. Federated tem-
poral difference learning with linear function approximation under environmental heterogeneity. arXiv preprint arXiv:2302.0222 12. 2023a.
Han Wang, Leonardo F Toso, and James Anderson. FedSysIID: A federated approach to sample- efficient system identification. In Learning for Dynamics and Control Conference, pp. 1308- 1320. PMLR, 2023b.
Han Wang, Leonardo F Toso, Aritra Mitra, and James Anderson. Model-free learning with het- erogeneous dynamical systems: A federated LQR approach. arXiv preprint arXiv:2308. /743, 2023c.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural 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. leee Network, 33(5):156-165, 2019.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279-292, 1992.
Jiin Woo, Gauri Joshi, and Yuejie Chi. The blessing of heterogeneity in federated q-learning: Lin- ear speedup and beyond. In International Conference on Machine Learning, pp. 37157-37216. PMLR, 2023.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local SGD for heteroge- neous distributed learning. Advances in Neural Information Processing Systems, 33:6281-6297 2020.
Zhijie Xie and Shenghui Song. FedKL: Tackling data heterogeneity federated reinforcement learning by penalizing KL divergence. IEEE Journal Selected Areas in Communications, 41 14):1227-1242, 2023.
Fuzhen Zhang. Matrix Theory: Basic Results and Techniques. Springer, 2011.
Shangtong Zhang, Remi Tachet, and Romain Laroche. On the chattering of SARSA with linear function approximation. arXiv preprint arXiv:2202.0688 262222222.0282 2022.
Hankz Hankui Zhuo, Wenfeng Feng, Yufeng Lin, Qian Xu, and Qiang Yang. Federated deep rein- forcement learning. arXiv preprint
2019.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019.
12

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Organization of Appendix
14
B Finite-Time Results Comparison
14
Additional Simulations
Additional Simulations FedSARSA
C.2 Simulations for Federated TD(0)
................................
C33 Simulations for On-Policy Federated Q-Learning
16
D Central MDP
17
E Notation
19
F Constants
20
G Preliminary Lemmas
21
H Proof of Theorem 1
24
Key Lemmas
26
1.1
Error Decomposition
26
1.2
Descent Direction
26
1.3
Gradient Heterogeneity
27
1.4
Client Drift
28
1.5
Gradient Progress
29
1.6
Mixing
32
I.7
Backtracking...
33
1.8
Gradient Variance
35
Proof Theorem
38
K Proof of Corrolaries 2.1 and 2.2
41
L Constant Dependencies
42
M Tabular FedSARSA
44
13

---

Published as a conference paper at ICLR 2024
A ORGANIZATION OF APPENDIX
The appendix is organized as follows. First, we present an additional comparison of our results with other finite-time results in Appendix B, and additional simulation results in Appendix C. In Appendices D and E, we introduce the concept of central MDP and some notation that will assist our analysis. In Appendix F, aid readability, for readers' convenience. In Appendix G, we provide several preliminary lemmas that will be used throughout the analysis. Before presenting lemmas for Theorem 2, we first prove Theorem in Ap- pendix H, for it will be used by later lemmas. In Appendix I, we first decompose the mean squared emorr and then present seven lemmas, each bounding one term in the decomposition. Then, we provide the proof of Theorem 2 and Corollaries 2.1 and 2.2 in Appendix J and Appendix K, respec- tively. To provide insights into our results, we discuss the dependencies of constants in Appendix L. Finally, we reduce FedSARSA to the tabular case in Appendix M, demonstrating the flexibility and efficiency of our algorithm.
list all the constants that appear in the paper
B FINITE-TIME RESULTS COMPARISON
comparison of finite-time results on temporal difference methods is provided Table
Table Comparison of finite-time time results. Results with green background are first provided by our work; results with blue background are covered by our work. "Linear" indicates the usage of linear function approximation, and "Hetero" indicates the presence of environmental heterogeneity. All constants are defined in Section 5 and Appendix I. We show the squared & error for linear settings and squared loo error for tabular settings. Asymptotic notations are omitted for simplicity.
Federated
Single-Agent
Lincar
Tabular
Linear
Tabular
Hetero
Homog
Hetero
Homog
TD Learning
[1- NT
21a
+ [1-7)
(1 1->)'T NT
H2
X² NT
NT (- 71
x 1'
(1-7)*7
H²
X' (1
Q-Learning
H2
A² + (I-7)²
S
H2
SA
PNT
[--y)o7
X0(I~>)NT
(1-
X(1->)>7
SARSA
PT +
A
H
SA + X
A²
SA
H
SA
(1-7)a
(1
(1-7)²T
X²(1-7)43
(Wang et al., 2023a) (Khodadadian et al., 2022)
(Jin et al., 2022)
(Bhandari et al., 2018)
(Qu & Wierman, 2020)
(Zou et al., 2019) Corollary
2.2
Appendix M
C ADDITIONAL SIMULATIONS
C. ADDITIONAL SIMULATIONS FOR FEDSARSA
We first restate the simulation setup in more detail. We index finite state space by S = [100] and an action space by A = [100]. where the actions determine the transition matrices by shifting the columns of reference matrix Po:
Pa = circ.shift(Pp, columns = a);
where circ.shift denotes circular shift operator. We construct the feature extractor
((s, a) = e(s mod d,) da mod dg E Bd Xd2
where e; the indicator vector with the i-th entry being 1 and the rest being We set dj = 5 and
d2 = 5. For the policy improvement operator, we employ the softmax function with temperature of 100:
exp( 0(s, a)/100)
To (a(s)) En'es E. exp (T 6(s, a a')/100)
Other parameters are set as follows: the reward cap 10, the discount factor = 0.2, the synchronization period K 10, and the step-size og 0.01.
14

---

Published as a conference paper at ICLR 2024
To construct heterogeneous MDPs, first generate nominal MDP M₁ and obtain the remaining MDPs by adding the perturbations to M₁. Unlike in FedTD (Wang et al., 2023a), where the optimal parameters be obtained by solving the linear projected Bellman equation directly, here get a reference parameter ( by running a single-agent linear SARSA on M, with decaying step- size. As suggested in Corollary 2.2, the reference parameter converges to the optimal parameter corresponding to _M1- Then, we calculate the mean squared error with respect to the reference
parameter: | ( All of our simulations are averaged over ten runs and all graphs are plotted with 95% confidence region.
In Figure 1, both kernel heterogeneity and reward heterogeneity set at the same level. In Fig- ure 2, we fix the kernel heterogeneity as 1.0 and vary the reward heterogeneity. In contrast, we fix the reward heterogeneity affirm the robustness of our method towards environmental heterogeneity. Furthermore, they seem- ingly suggest that the algorithm is more sensitive reward heterogeneity than kernel heterogeneity. However, it is important to note that Cp and 6, represent upper bounds and may be much larger than the actual heterogeneity level.
zero and vary the kernel heterogeneity in Figure 3. Again, these results
Further exploring the effect of heterogeneity on federated collaboration, Figures 4 and 5 illustrate the effect of different reward and kernel heterogeneity levels on the performance of FedSARSA respectively. Generally, higher levels of heterogeneity result in larger mean squared error, which aligns with our theoretical results Section 5.
X000
XGDE
(a) 6
(b) 6
0.1
(c) 6r 0.2
X000
3.55
(d) 6, 0.5
(c)
(f) Ey
Figure 2: Performance of FedSARSA under Markovian sampling for varying reward heterogeneity and numbers of agents with fixed kernel heterogeneity (cp 1).
C.2 SIMULATIONS FOR FEDERATED TD(0)
As discussed in Section 4, FedSARSA reduces to federated TD(0) (Wang et al., 2023a) when the policy improvement operator maps any parameter to a fixed policy æ. This corresponds to a fixed transition kemel. Therefore, conduct simulations for federated TD(0) to demonstrate the adaptability of FedSARSA. We inherit the simulation setup from the previous subsection (Ap- pendix C. which matches the setup in Wang et al. (2023a). We fix the behavior policy by fix the transition matrix as the reference matrix P,- The results are presented in Figure 6, which are similar to the results in Section 6, again validating our theoretical results.
15

---

Published as a conference paper at ICLR 2024
3030
3458
309E
(a) Ep
(b) Ep
0.1
(c) Ep 0.2
1050
AGSE:
(d)
0.5
(e) Ep
(1) Ep 2
Figure 3: Performance of FedSARSA under Markovian sampling for varying kernel heterogeneity and numbers of agents with fixed reward heterogeneity (c, = 1).
X Tuly 141
N Rhg 1
N Mi., 1D
MS55
M855
MASE
(a)
5, Ep
N 10,6p 6p 1.0
(c)N 20, Ep
N-10-20
N-
ASSB
84
66
11
14
03
08
15
(d)
N 5,
Ep
2.0
(c) N 10,
22.0
(1
N
20,
6p
2.0
Figure 4: Effect of the reward heterogeneity on the performance of FedSARSA
C.3 SIMULATIONS FOR ON- ON-POLICY FEDERATED Q-LEARNING
When equipped with greedy policy improvement operator, FedSARSA reduces to on-policy fed- erated Q-Learning. Specifically, we employ greedy policy improvement operator:
(a)s)) = 1 1{a argmax 6 o(s,a')}
a'EA
where 1 is the indicator function. For the other part of the simulation setup, inherit the setup from the previous subsection (Appendix C. The results are presented in Figure 7, which resemble the results in Section 6 and Appendix C.2.
16

---

Published as a conference paper at ICLR 2024
MSS
(a) N 5,
1.0
(b) N 10, Ep
1.0
(C) 6p 0.2
W=66-80
X -90
No 20,6 20
NGSB
(d) N 20, Ey
1.0
N
2.0
N 10, 2.0
Figure 5: Effect of the kernel heterogeneity on the performance of FedSARSA.
JUSE:
XODE
Ep
Ep
67
0.1
Ep
0.2
XSS
XSR
417
(d) 6p
0.5
(e) Cp 6,
(1) Cp
2
Figure 6: Performance of FedSARSA with fixed-point policy improvement operator, covering federated TD(0).
D CENTRAL MDP
To facilitate our analysis, introduce a virtual MDP: M EN M Specifically, M (S, A. F, P, 7), where F = N/2 M (() P = \ EN P(0, We refer to this virtual MDP as the central MDP, The following proposition shows that M is indistinguishable from the collection of actual MDPs and also satisfies Assumption
Proposition 1. If MDPs {MO) are ergodic (aperiodic and irreducible) under a fixed policy n, the central MDP M is also ergodic under n.
17

---

Published as a conference paper at ICLR 2024
1000
MB5
204
150
190
(a) Ep
(b) Ep 64
0.1
(c) 0.2
1256
6p 6y 0.5
(c) Ep 6
(f) 6p Gy 2
Figure 7: Performance of FedSARSA with greedy policy improvement operator, covering on- policy federated Q-learning.
Proof. Suppose is given. We first show that M is also aperiodic. If not, by the definition of aperiodicity (Meyn & Tweedie, 2012, Page 121), there exists E S such that
d(s) gnd(n: ("(ss 8) 0}>1,
where ged returns the greatest common divisor and we omit the subseript v of Pa since we consider a fixed policy. The above inequality indicates that, for any n E N {kd(s)]keN. holds that
N
0 0= ss)
1
Σ p(i
(8,8)
1 Nu
(plo)) (s, E
(6)
Now since M is aperiodic, (s) gedfn (P())) > 0} 1. Thus there exists N LKeN such that (P())) s) 0 (otherwise (s) > d(s)), which contradicts to (6). Therefore, we conclude that d(s) = 1 for any s E S, and thus M is aperiodic. We now show that M is irreducible given {M are irreducible (Meyn & Tweedie, 2012, Page 93). For any B(S) with positive measure, where B(S) is the Borel o-fiedd on S, we have min(n
(s A) 0} < +o0 for any E and i [N]. Then again by (6), get
1 min(n: (s, A) 0) < min min (": Na sE[N]
"s, (p(t))((s,A of to0.
Therefore, M irreducible.
When the state-action space is finite, Proposition I covers Wang et al. (2023a, Proposition I).
By Proposition we can confidently regard M as the MDP of virtual agent, which does
exhibit any distinctive properties in comparison the actual agents. Therefore, we denote () = M and define the extended number set [N] = [N] U (0) (0, 1,... N). When we drop the superscript (6), it should be clear from the context if are talking about the central MDP M an arbitrary MDP ( Clearly, the extended MDP (MO) )ej still satisfies Assumption and Definitions and and thus Theorem 1. Now
specify the special parameter 8, in Theorem is the unique solution to (3) for M. other words, Theorem asserts that the algorithm converges the central optimal parameter.
18

---

Published as a conference paper at ICLR 2024
E NOTATION
Before presenting lemmas and proofs of our main theorems, we introduce some notation that will aid in our analysis. We introduce notation for the unprojected central parameter:
N
0.+1
1 N
0 angge") when / + = (mod K).
Then, 0f41 = 0.+1 = 1lo(0++1) when 1+1 = 0 (mod K). It's easy to verify that for any ||O|| - G, have
110 011 - 10 O|1-
Then we define some notations on the MDPs. Note that all these definitions apply to the extended (M(N)) that includes the central MDP.
MDP set (M() NE(N)
Definition 3 (Steady distributions). Assumption guarrnntees the existence of steady state distri- bution for any MDP and policy π. We denote Ti
(2) the steady state distribution with respect to
MDP ( and policy na, i.e.,
No (8) = lim
t-000 Rg ( = =sS00 - so).
Additionally, given policy Ty. the steady acaton distribution is defined as
( (s, a) = 1a (s) To(als)
Then, the two-step steady distribution is defined
9p (s, a, ",a,s',a') = ( (s, (s. (s, sf s')xo(d'|ss))
For local parameter o(() we simplify the above notations as follows:
14
Pt
We now ready provide the precise definitions of the semi-gradients discussed in Section Definition 4 (Semi-gradiente As indicated by (4), semi-gradient is function of both the param- eter & and the observation tuple O (s, a, a,)), while the observation tuple is dependent on the local Markovian trajectory. Therefore, the general form of a semi-gradient is
(0:0(0) (1) = Φ
(1(0)
+ +00" (st2). (121
8
where 0 = indicates that the trajectory after time step t- 7 follows fixed policy म. Tg i...
(411 is the observation of agent i at time step t, and the subscript
T0
When т = 0, the semi aami-gradient corresponds to an actual SARSA trajectory, and we omit the sub- script and the observation argument, i.e.,
0 gi (i) (B:0.)).
When 5 0, the semi- -raieeradient corresponds virtual trajectory, and we use Ô, in place of O to indicate it is virtual observation at the current time step.
We add bar to denote the mean- mean-path semi- semi-gradients i.e..
E 1
-i- (0, (0,0)] E ()) (s, + 70" (s',a') o² (s,
where the expectation is taken over the two-step observation steady distribution:
0 = (s, a' a') -p- 4 (1)
(8)
19

---

Published as a conference paper at ICLR 2024
For mnean-path semi-gradient the randomness of the observation is eliminated, and the parameter the only argument, and we can substitute the subscript t-7 with a general parameter 8"; then we define
Dor (0) = ca Por
()t,,)(()) (8, + 16" "0" (d, of (s. a)))
We omit the superscript (i) when referring the central MDP M. For instance,
--- (0) = E [d(s, (F(s (1. a) + no (s', a d')0 o² (s. a)0)
Finally, for notational simplicity, we use bold symbols to denote the average semi-gradients, c.g.,
N
(0,r = N
92
(0)
0
The above notations will be used in combination, e.g..
g(O))
1
(
0 1
9t
(4) (0())
N
We can further decompose semi cemi-gradients into TD operators.
Definition 5 (TD operators). A semi-gradient 9 (, (1,) can be decomposed into the following
two two operators:
(0,0(") - (0()) + 6 (o!²). 91
where
(of))
( (1)
(70²
(1)
0²
(st (0) ((%)a("))
88 ai
( (
.441
10
(+)
Φ
(i)
(8)
Similar to Definition 4, can define other TD operators for each semi- gradiinddddnnt e.g., the mean-path TD operators:
A (
E ca (A0 (O)),
bg
E
(e) [b0) (O)).
We summarize the notations defined in this section and other notations used in our analysis in Ta- ble 3.
F CONSTANTS
We first introduce two important constants that as base constants throughout the paper. The first one is the upper bound of the norm of the central parameter, denoted by G > ||@|| For this
bound to hold, we require the projection radius G to be large enough such that ( S G for i E [N]. The explicit expression for G will be given in Corollary 1.5.3. Then, we define
R (1+
(8)
The constant H can be viewed as the scale of the problem, analogous to [S]].A] for the tabular setting that will be discussed in Appendix M. For local parameters, define similar function h(0) = R + (1 + +)]l
We summarized the constants that appear in analysis in Table 4. Notice that 7, Cu, and a in Table refer to the constants in the case with a linearly decaying step-size. For the case with a constant size, these constants fixed and specified in Corollary 2.1.
20

---

Published as a conference paper at ICLR 2024
Table 3: Notation
Notation
Definition
[V] [N]
The set of numbers and the set N + numbers including Markov decision processes
M .M
A,
State space, action space, and parameter space
0
P(,
P
Reward functions and transition kernels
$ U 0
Agent i's state, action, and observation random variable at time step t Instances of the state, action, and observation policy and the policy improvement operator Total variation distance and its induced norm for transition kernels
8,0,0
a,r
II ||tv q, Q 6,0
True Q-value function and estimated Q-value function
Feature map and feature weight (parameter)
11 1l
Orthogonal projection operator
T
Bellman operator
T
((0)
Optimal policies and optimal parameters
(4)
(8)
11
Mg
P9
Steady distributions
g
Semi-gradient
A, b, Z
Temporal difference operators
h(0) = R (1 + 7) [0]]
Client drift
Ft
Filtration containing all randomness prior to time step t
G PRELIMINARY LEMMAS
In this section, we present two preliminary lemmas that will be used throughout the analysis.
Lemma G.1 (Steady distribution differences). For the same MDP, the TV distance between the steady distributions with regard to two different policies is bounded follows:
|17,
192 TV S Lo' 110 02112
|
100 TV I TL1 + d') 02112
||ypo, -P02llTy I L(2 + a) |10 -021121
where L is the Lipschitz constant of the policy improvement operator specified in Assumption 2 and o' a constant determined by m and p specified in Assumption 1. Letting o == o' + 2, all three TV distances above are bounded by Lo LoIl61 02112- Next, for fixed parameter 0, the TV distance between the steady distributions with regard to two MDPs is bounded as follows:
(4)
(3)
< S
11 11
TV
(4)
(
< d'
198 48
Tv
1P 48
(8)
(
S (o' + 1)ep-
TV
By the above inequalities, for different MDPs and different parameters, we have
(1)
TV So'ep
T. (1ا) I|2-
Proof. For the same MDP, by (Mitrophanov, 2005, Corollary 3.1), we get
||,, -00 -021lr S a'll Po. Po, llv
21

---

Published as a conference paper at ICLR 2024
Table 4: Constants
Notation
Meaning
Reference
Range Order
N
Number of agents
Section 3.2
N
R
Reward cap
Section 3.2
(0, +o0)
8, A
Measures of the state space and action space Discount factor
Section 3.2
(0, +00
Section 3.2
(0,
m4,
Markov chain mixing constant
Assumption 1
(1,+00)
and Lemma G.1 Assumption and Lemma G.1
PisP
Markov chain mixing rate
(0,
o,a'
Steady distribution perturba- tion constant
Lemma G.1
O(log m/ (1 p))
G
Algorithm projection radius Parameter norm upper bound Problem scale
Algorithm
(0, +00)
G
Corollary I.5.3
O + R)
H
Equation (8)
O + R)
T.
Lipschitz constant for the pol- icy improvement operator Local update period Environmental heterogeneity ratio
Assumption
[0, (Ho))
K
Section
Eps Er
Definitions and 2
[0,2]
A
Environmental heterogeneity
Theorem 1
OH +
A x
Exploration constant
Equation (18)
(0,1)
ws w
Convergence constant
Equation (19)
[(1 - 7)2/2, 1/2)
Backtracking period
Lemma I.1
O T)
og
Initial step-size
Section 4
(0, min min (1/8K, w/64]]
General step-size
Section 4
(
Carint
Client drift constant
Lemma I.4
O(KH)
prog
Parameter progress constant
Lemma I.5
O(HT)
Chack
Backtracking constant
Lemma 1.7
0(72w)
Gvar
Gradient variance constant
Lemma 1.8
(HH
B
Young's inequality constant
Appendix
w0,w/7)
Harift Ca
Another drift constant
Appendix
O(H)
Step-size constant
Appendix
0(1)
C
First-order constant
Equation (50)
O(1 (1)
C2
Second-order constant
Equation (50)
O(H²T)
C3
Third-order constant
Equation (50)
2(H2
CA
Fourth-order constant
Equation (50)
w(H2
Square the convergence re- gion radius for constant step- size
Corollary 2.1
see Corollary 2.1
where Po(s,s')= = SA Pa(s, (')olalsdda and ||
11 q(s)) [
sup |vl|
||
sup
TV
And the constant o' is defined by
mp
o'
where = log, m '1, m == maXiE[N] m, and == maXig[N] P: with m,, P; specified As- sumption Note that the above inequalities, we actually should use of defined by m, and pæ but of is bounded by o' for all [N], this possibly looser bound for notational simplicity.
22

---

Published as a conference paper at ICLR 2024
Then, by Assumption 2, we have
/ sup I s l/5
Po.
Po, lIv
(s, s')ss' ds sup / ((s)(Pa(s,)') (a|s) Pa(s, s') ds
I 8xA
sup [a(s) (a s') |T, (als) no, (als) dads'ds ds
Ilallv==1 S2XA
sup
[g(s)] Te, (als) - (als) dads
1 SxA
sup
| (+ss Toz l| ds
sup / (a(s) ds lollav=1
L| 02 l|
L 02 12.
Therefore, we get
|170 no, lla S Lo'1101 02112.
Next, for the state-action distribution, we have
1 |no, (s)TT, (als) n0, (s) (a|s) dsda
lime, poollrv
SxA
< / 110 (s) (T, (als) - Tuz (als) dsda -f SSX
Ino, (s) (s)] ne, (als)dads
A
< L|10 02112 + Il -oall
I L(1 + o') 02112.
Similarly, we have
l1p0, - po ll S L(2 1(2+0')100 02l12.
Also by (Mitrophanov, 2005, Corollary 3.1), we get
(4) 100 TV
I o' d'(l pb") || S d''ep,
where is defined in Definition 1. Then, for the state-action distribution, we have
|0000 1000
(1)
(3) 116
(z)
-6=0 lv S L
lrv
m
1/8
And similarly, have
(
(3)
90
90
TV
( (saa(((s))))))
pg (sa (oo(al)s)) dsds'
Mo
<
M8
(s
(
11 (s, (a (s') dads'dada'
12
+
M4
(
(s, (Tooaas - (s.0)) s' (a'ls") dsds' 'ada'
(1)
1660 | + +|(p(0 pl1) ||V
<
118
<(o' + 1)e, gep
Finally, by the triangle inequality, we get
|
(8)
1000 lr S + - p00) 112
(i)
23

---

Published as a conference paper at ICLR 2024
Similarly, bound the differences between TD operators defined in Definition 5. Lemma G.2 (TD operator differences). For the same MDP, the difference between the mean-path TD operators with regard different parameters is bounded follows:
{ |o. Ao.ll
$ {) |0] 101--2
llbe. - be_
RLoo 10 02112-
Next, for a fixed parameter the difference between the mean-path TD operators with regard to different MDPs is bounded follows:
A/ - 1
{1 {1
1 - -b00
I R(e, + ocp).
Then, by the triangle inequality, we get
A - 86))
1 (1 7)0 (L (2| - o6:011 112 + +c))
1369 p(a)
(06 BG))
I R(e, + oep) + RLo |100) - 010)122
Proof. For the same MDP, by Definition 5, we have
| (ss, (1)0" ())rr)"('''a))) - (a (d)po) 8',, dops (s,
|| - Aoz
52x
I + l1,o, - PoalITV
(11 + 7) Lo |10, - B2ll2
where the last inequality comes from Lemma G.I. Similarly, we have
1/ SxA oss a)r(s, a) (s,a) - duo (s)
|,00 - bozll
<R || Hea - Moo llTv
< RLo |10 82ll2-
Then for the same parameter have
A - 1300
|/50000 sxx (o, - o ()) (s, -
- (8, s',"")
5(1 + 7) (060) - 066 l
TV
(11 + 7pp
where the last inequality comes from Lemma G.I. Similarly, we have
B(0)
/ SxA
a) as) (s, ,.0 (s(6s)))))
(s) (s. dug (1) (s, If (3, |ay (s, ( - -p
(0) (s))
SSX
SxA
SRE, + Ro'ep
where the last inequality comes from Definition and Lemma G.I.
H PROOF OF THEOREM
Theorem 1. For any i,j E [N], we have
( 0000
1 1-==00 (Re, + HoEe)) S A(cp.cr)
_(RR,
wj
where minte(N) way w; is defined in Lemma 1.2 and M(pp 67) defined in Lemma 1.3.
24

---

Published as a conference paper at ICLR 2024
Proof. First, formulate the Bellman optimal equation in terms of TD operators defined in Defi- nition 5:
A 0 + b. 0,
for any i [N], where
A
7(0)
5 ((1) 0!
6.9
Then for any i,j E [N], we have
( A( -!00 A( (B())
-00) ) = 550h 866)
By Tsitsiklis Van Roy (1996, Theorem 2), A!d) is negative definite Therefore, A is non-singular, and we get
|0.T)
/
(42)
[ -A 00.0 + (BL)) - 654 1.
And we have
[ (At)) -1
=m (A()))
(10)
1
(11)
Amax Ab55)
(12)
RAmax
(A(5)
(13)
A((1)
Amax
88ym
(14)
2wy
where (10) uses the spectrum norm equality and m returns the smallest singular value of matrix; (11) and (12) use the fact that A( is negative definite; (13) is by (Zhang, 2011, Theorem 10.28); and lastly, (14) is the definition of wy (see Lemma I.2).
Therefore, letting G be large enough to contain {0!*) hE(NN we get
(o0)) -000
1
(|
| G - ( b50)l)
2w0
By Lemma G.2, we get
(0(0)
//0/11
0000
112
S S (1++))0G) (pp + I - 1/011/) -110)))) + R(er + +acp) + RLo 10.0) - -050 0,011))
2w;
RR, + Hoc, + LHo |0!00 ا591 ())
$ 2w,
We require that LHo S wy (the same restriction (20) in Lemma I.2); then we get
|001- 1 -p0-0
05.111
(Re, + Hoep) Wi
S 2w,
2w;
2
which gives
(550 0500 0501/2
< 1
A(ep.
(Re, + HHTe,) -
Wi
w
where w := minse(M] wi and A(ep, ex) = Re, + Hoep (the same definition in Lemma I.3).
25

---

Published as a conference paper at ICLR 2024
I KEY LEMMAS
In this section, we first decompose the mean squared enror and then present seven lemmas, each bounding one term the decomposition.
1.1 ERROR DECOMPOSITION
Lemma I.1 (Error decomposition). The one-step mean squared error can be decomposed recur- sively as follows:
E | 0.112 S Bl 0.11² =Bl 0.11
+ BB,B B (0.
- -..9 (1)) 9 (0+))
(descent direction)
200
E 0. 0.0 g (0.) (0.))
(gradient heterogeneity)
N
N
20:
00, 0. ( (8()) - g(dh (8.)
(client drift)
N
N
20
(0. 0., - (0.0) (00) (0:0)
E
(gradient progress)
N
200
Σ
E (0. 0., -
(1) (0)0) 0000)
-i-r (o!.)
(1)
(mixing)
N
N
20
00. - 0.. gt
(1)
(00
-
(0)
(0.0) ((00)
(backtracking)
N
N
+ a
Σ
Dt
(5)
(0(3))
(gradient variance)
One can verify the above decomposition given g(O.) 0.
1.2 DESCENT DIRECTION
Lemma 1.2 (Descent direction). There exist positive constants (wiheem such that any ||0|| < G, we have
(0- 00 go) < -w; 2590)
Vi [N].
Proof. We drop the subscript (i) in this lemma since the following derivation holds for all MDPs. We first denote AO = 0 0.. Then, we have
0 - 0z, (0)) - g(O.)) =AAT ((A0 + b0) (Ao, 0_ + +b.))
-AOT Ag. AO + ~O (Λo Ao.) - ~0 (bg bg.)
<AOT Ao. A0 ||0 || Ao_ll |10|| || bbg bo.1l
<AOT Ao. A0 (1 + 7) Lo100111A0) + RLo |
(15)
AOT (Ao. + Lo + (1=
<AOT (Ao. + LoH 1) AO
(16)
NT Āo.A0. 20,
where (15) uses Lemma G.2, and (16) uses the fact that ||0| < G and H = R1 By
(Tsitsiklis & Van Roy, 1996, Theorem 2), Ao, is negative definite in the sense that x² Ax <
26

---

Published as a conference paper at ICLR 2024
for any vector R. Specifically, for any nonzero E R denote x² xT)(SSA) and x (("",A) Then, for any x + O, by Definition 5, we have
x² Agı Eupo Irun' u²) =Eluul] Elu²]
? (E(u²) Biu"1) - E(u²] 17-1) 0, 2
(17)
where we use the fact that B|u E (0(S, A)o" (S, A)] O. We define
[|[ under steady distribution.
Let 466
A
Amiu
(5) o5
x= min A
(18)
sE[M]
By (17), we have
1
1m (1(1
Wi =
2 Amax
sym
5 (
(19)
2
where (Am = (A + A") maps general matrices to Hermitian matrices. Due to the positive
definiteness of 4 (1) 06 We know we > O for any E [N]. By Zhang (2011, Theorem 10.21) and the
linearity of the sym function, we know
Amax sym
(10) 0.0) ) Amax (sym AA 0500
)
(sym(Lo I)) 2ww; LoH.
Let = m [we). Then, we can choose L to be small enough such that
L S oH
(20)
which gives
(yy (T(6) ))
wc 2 Amax
Therefore, for any E [N], we have
0 0 g (0) - g (0!)))
s Amax
8ym
A00) (
)) 10 0- 000 5
-w; |
0001
(21)
Remark (Convergence constant). Equation (21) mirrors the result of stochastic gradient descent (SGD) (Bottou et al., 2018), with w being analogous to the Lipschitz constant of function's 's gradi- ent. Therefore, similar SGD, controls the convergence rate of our algorithm.
Remark 2 (Exploration constant). The value of w depends on A, constant that reflects the explo- ration difficulty of the environment. We can see this by considering simple tabular setting, where the feature map simply the indicator function (see Appendix M for detailed definitions). Then lo(S, (,(,SAA)) A)ø" (S, A)] reduces to diagí a)) (s In this case, the minimal eigenvalue of is aa (ss, a). i.e., the probability of visiting the least probable state-action pair under the steady distribution.
(S,
We say an environment is hard to explore if some state-action pairs have a very small probability of being visited under the steady distribution, then small. Conversely, À is large when the environment is easy to explore. Intuitively, an environment that is hard to explore requires more samples to learn an optimal policy.
In the context of LFA, the value of X, and consequently w. is determined by the conditions of both the MDPs and the feature map Φ. the environments the feature space are easy explore under the MDPs, X and w will take on larger values, and the algorithm converges faster.
I.3 GRADIENT HETEROGENEITY
Lemma I.3 (Gradient heterogeneity). For ||0|| S G. we have
1 N N Σ (0)
g(0)
< Hopp + Re, = A(cp:
27

---

Published as a conference paper at ICLR 2024
Proof. Directly applying the decomposition in Definition 5 and Lemma G.2 gives
g(0)
Σ (0)
(0)
(Ag0 + bu)
1 N
Σ (Ag 0 (//))
1 N
b5- | + || Al A1'111011)
N i=1
c
R
+ (1+ 7)11811 + Re
1.4 CLIENT DRIFT
Before bounding the gradient progress, we first bound the client drift.
Lemma L.4 (Client drift). If |1 & G holds for all E N, then
1
Σ
g of (1+ OLH) Cann:
N
where k is the smallest integer such that k = 0 (mod K), and
C H²
Proof. Similar (15) in the proof of Lemma 1.2, we have
0 ( nd (0>) s (1+ La (1++00011)))
1000 -o1
(22)
Then, since ||0,|| S G. we have
N
N N
1
(0())
gl)(o +
1
((()) 0.1"
(23)
N
0 - 8.1.. We then need to bound Q. First, if 0 (mod K). have Q = O. Now suppose # 0 (mod K). Let k be the smallest integer such that t - k
Let Ω4 = Σ
1=1
(mod K). Then we know that there no aggregation step between time step and and
8,11 = 1/N EN ((9) for 0 < k. Therefore, we have
1 0 Ea-1 (3) - 2
(010) - 0.1²
k
< ka Σ
-
where gi(0))
1 Σm= 9t (0(0)) ), and we choose a to be non-increasing. Since for random
vector X, Var(X) < x1 ? we have
2 < ko 2
Σ
N
1=1
b
< ska? 2
Σ
Σ
N
1=1
-(,00~1
(0) (0=)))))))))))) ||00000+|+||000000--00
< ka?
2
N
28

---

Published as a conference paper at ICLR 2024
where also used Jensen's inequality. By the definition of the Markovian semi-gradients (see Definition 4), they are linear and Lipschitz continuous with the Lipschitz constant bounded by ||4اا|| ll < y However, it is worth emphasizing that the mean-path semi-gradients non-linear and non-L.pschitz continuous (unless ||0+|| is bounded; (22)). Given the Lipschitz continuity, Lipschitz.continiity have
2 * Sh 1 2ka,
(L (1+
10 - 86-1| +112)
1=1
(=1
=2k
1-H2 + (1 7)² Σ 22-1
(24)
Recursively applying (24) gives
+1 Q 52ka, k111 + (1+ +
Σ
+ 2kka 7)2 -2kk 1)ak
kkll + (1+7)²
Σ
(0q-1)
1=2
1=2
52ko - 1))
1H2 + +1++))
Σ 84-1
<2ka *k II (1+ 8(k - -)aa( 2kH2 + +11+1111111 (1++)) 71
j=1
<2kai= (1+ 8ka kH?²
where we use the fact that Ω = O. To continue, we impose a constraint on the initial step-size by requiring 4Kao S which gives 1 a <
Then, have
8k²a2
(1 + 8ka 11+)
Σ 1=1
k (Ska <1 + 1 8h20
< 1 11+16K
2
0 2.
(25)
Therefore, we get
2 S H2 (1 + 16k oZ
2 0 S 0 Carfte
(26)
Plugging (26) back into (23) gives the final result.
Corollary I.4.1 For future reference, we extract two bounds on the client drift from the proof of Lemma 1.4:
94 S az Parito
wt S aq & Carint.
where We == N Σ. |10 - 0ell
1.5 GRADIENT PROGRESS
To bound the gradient progress, we first need bound the parameter progress. Instead of directly bounding the client parameter progress, we bound the central parameter progress, which then gives the client parameter progress combining Lemma 1.4.
Lemma 1.5 (Central parameter progress). If |1
G for any I S t, then have
||0, 1kk-0--a - < a (T)
where s is the largest integer such that sK < t and
Cprog(T) = 2(T + 2K) + 200 = 0(r).
Proof. Bounding the central parameter progress is harder than bounding the client parameter progress since
|10, 0.-1ll & a (R + (1 11,
29

---

Published as a conference paper at ICLR 2024
Therefore need to introduce the client drift, and then bound the parameter progress using Lemma 1.4. First, for any t, we have
|0+||| S ||&el|
8 +
--
91-1
0
(--1)
10)
N
i=1
P
0t-1
(1())
(0 0e- A00) (o.2)) (0 Bb-1) ((0)
(o
N
(1 + 1 + 1))011111 + ar-1 1R- 2w1-1);
(27)
where - defined in Corollary 1.4.1 Let k be the smallest positive integer such that & (mod K) (if L = 0 (mod K), then k = K). Recursively applying (27) gives
2-1
||+||| s II
(1+ 20x) |10--111 Σ 200-; a 2w1-1)
1=f-k
<(1 + 2x) |0 + ar (R 20x 2 (1 + 2010 -1
(28)
201-k
<1 + 4km 1) 0 + 2k0, x + 20v (CCrit)
(29)
<2 + 2ka; + 20 Cdrttt))
(30)
where (28) uses Corollary 1.4.1 and require to be non-increasing; and in (29) and (30), we require that 40 < 1, which gives (1 + 20 < 1 4ka4-k with the similar reasoning in (25).
Now ready to bound any central parameter progress between two aggregation steps. Since t (mod K), we have [0,- I G. Then by (7), we get
110, - 0-- S <100 0-- 5 k=t-k
100++ 0:11
(27)
1-1
Σ
an (R+ (1 ||111 + 2wr)
k
(30)
k R + 211 7) 0. +11 + 4ka, + CCritt) 20, (.Crittrrtt)) <kka- k (R (1 + 7) 0 +11 2aInn
(31)
where we use the fact that
and 4ka, 5 1.
Finally, we need to bound the central parameter progress for general time period т. For any / > 1, let s be the largest integer such that sk < And let s' be the largest integer such that s'K < f. Then we have
110 0.-
10++) - 0(04)-1)K11 100, 0+ + 110,_ 0.Kll
(31)
2(T + 2K)ask (R 2ask 2arit
+1 + 7)
K (1000++-)))]11 (t-5)(K)1000 (1 (1- -1-7-sk sK)110xx(1| (1---ssk]00xx]]
<20. + (R 20.x Cani)) + 2T + +7)G
<20s + (T2ok(++2K)) (R + (1+ 7) 20. Cavin))
Sask
(32)
where Cprog (T) = 2(T + 2H) + Cagin)) = O(T).
30

---

Published as a conference paper at ICLR 2024
Corollary 1.5.1 (Client parameter progress). If 0:|| S G holds for all I I t, we also have
1 0 S a.k (rog()))
where s is the largest integer such that sK - -T.
Proof. Ift 0 (mod K) and t - 0 (mod K). then 0!" = 0r and o 0._.. and the result directly follows Lemma I.5. Without loss of generality, we assume o 0 (mod K) and f r * (mod K). Let be the largest integer such that sK < <t- - And let s' be the largest integer such
that 8' K < t. Similar to (32), we have
| < <1002x 0xxl1+ + 11000 - -0xx + 11102 0xx
By Lemma I.5, have
||0xx- 0skl| S a.k Grog(s' sK -2K),
where we subtract 2K to offset the addition of 2K Lemma 1.5 for general / and T.
Then to bound the client parameter progress after synchronization, we first notice that when / # 0 (mod K), we have
008)) 0121
|0(0
$ 20
+ +a-1Rh
Similar to (27)-330), we have
|
<(1 + 201-1) |0.01 ta--
1-1
II (1+ + 20r) |||x||| +
>
Pa-----
j
<2 (110- Il + RR),
where le is the smallest integer such that - k: = (mod K). Then, we get
10.0
0 || $
0/00 0f:0
t=
1-1
0n (1 (1+ + 7) | ||/0| + R)
k
<kark k (2(1 7) (110)~11 + Roo RR) + R)
22kar (R + (1+ (1+))100-*11)
where we use the fact that 4ka, $ 1. Therefore, we have
0s < 2(t 5 s'K)askll S 20,k KH,
( 0,k
2 sK)ask H I 20, KH.
Putting all together gives
0. 0(0)
S ask (Cprog (6'K - -KK -KK) + +KKH) S OskK Oprug()))
With the above corollary, we are ready to bound the gradient progress. Corollary 1.5.2 (Graident progress). If @ I G holds for all S t, then for any have
oL22. (0) 5 (0) < Lah(O)a, Oprog(T)
where is the largest integer such that sK
31

---

,it1 (+1) the observation of this virtual MDP at Published as a conference paper at ICLR 2024
Proof. c (0) - Dt (0) = (1 - 1/") 0 02
|
0 0 -
- Lo (R + (1 + +)1001
|
0
where the inequality uses Lemma G.2, Then we get the desired result by plugging in Corollary 1.5.1.
The third corollary of Lemma 1.5 is the expression of G. which was stated as an assumption in previous lemmas.
Corollary 1.5.3 (Parameter bound). Given the explicit projection l6 for any & N, have ||0,|| S == 2(2 + R)
2(2G R)
I
160g K2n
1 1-7
Proof. For any E N, by (30) in Lemma L.5, we have
| s 2 (G Koo R 200 2omDCrrin)).
Plugging the expression of Canin in Lemma 1.4 into the above inequality gives the recursive defini- tion:
G = 2G + om K + 200 2K + (1 + 7))))
Note that we require 4Koo < in Lemma I.5. Thus, we have
G s 2G R+ 80 (1 + Y)
which gives
2(2 + R) G < 1 - 16 K2ng
Therefore, we let G = 2(26 + R1 - 16a 37);; and then, we have
||0.] < 20 + R 80 K2 7)G DGG... G.
1.6 MIXING
Unlike stationary MDPs in TD(0) and off-policy Q-learning, the mixing process in our algorithm is virtual process. After backtracking, fixed the policy r(o("), which then introduces virtual stationary MDP. We denote 0 (S (()) 2(8) ((()) time step t.
Lemma L6 (Mixing). Let Fi-r denote the filtration containing all preceding randomness up to time step - r. For any deterministic A conditioned on Ft-r- such as a constant parameter or parameter determined by Fr we have
9 (0,0 06) F1-7]
S m.p (0)
Proof. We define
TD operator:
2.2n (0.019) 1i2 (0,0(0) - (0).
Then, we have
()))
F(_T] ||
E
Ji-r (0,0(²)
[r-r]] 1 (0
E
(1(0 + x (s',a')0 0= (x,a)))) (Pl (0 o Fi_.)) -2(_(0)) no
52x (s
<(R + (1 + [101) (5(() = F(-)) 1/- TV
(2)
Smap7 (R (1 77) [01))
where the last inequality is by Assumption 1.
32

---

Published as a conference paper at ICLR 2024
1.7 BACKTRACKING
Lemma 1.7 (Backtracking). !f [0il| S G all S L, then for any deterministic 0 conditioned on Fi-r, we have
E
( (0,0 9t
1
9. (0,0 F
ask ( (0),
where
Cback (7) = T TT.Croog (7) = 0(+2).
Proof. First, have
12 (0, (() (R + (1 (101))
B oh
1 (0, Fr-
p( (0 F - pl) (0(0) = F 0
For specific client, for notation simplicity, we omit the superscript (i) and denote Po. by Pt. Let O = (s, a, s', a');; then we have
P, = =
Pa(S, -, a, S U,+1 = d' 0,0, 01
Pi(S, = sFF=-) P:(0,-1 = 0
62
P(U, = -; =, = 8)
Pf(S,-1 = s F S: = 8, 1 0, 0g = a)
P((0: Ft St 8, 8,0,-1 0,U, a. S1+1 = 8')
-P( a' F S: s, 0,0,-1 0.U, a, S.41 s', 0; 0 d')dd
P((S,
St-)) P(
= 5) TT (a(a
e2
Pa(s,8') P. = -0, St 0-- 0, = 8, U. a) To (a )deae'
where we use that fact that Ug is dependent on 9 instead of 6;; and when f,- determined, A, not dependent on S,+1. Notice that for any (s, a) 5² x A, we have
/ Pi(00-1 = 0FF S. = 5) Pi(, =
= S, = =. a)dodo' = =1.
Thus, for P we have similar expression:
92 P5- = 8, Ü; = o, 5,411 = = U,, d((FF-.) P( -
=
P.( = F 0, = s, U₁ = a)dddd'
Pa-r (S, 5555=s(0--- =,0,,,,, ne. (a|s) Pa (a To. (d'ls')
Pi(0--1 110,,,,m_m St = =) (0 0 St.,, 0c- = =. = =s, a)dddo
Therefore, we decompose the observation distribution discrepancy as follows:
(2-00)---))----0)1-)-)-))))) < / (0000-0000.---000000000--0000000
sAxA2
where
Qi(0)= = 00a
Pt- s/0,-,, To._. (a|s) Pa(s, (a'ls')
-P1(0-11 0/0--. St.r, St = 5) Pi(O: = 0' 0, p. S, 01-1 = 0,
01S: =
-,,5=sU U, = a)d0do'.
33

---

Published as a conference paper at ICLR 2024
For S1, we have
(S- = 8/0 ST (ss)))P((s 7,
0,0,- r, St =8)
82X
P.(0, -1000- 02-1 S. s, U, a) T6. (a'|s') (ap (s'{ ")/d00000"
(s:
Si- (T., , (a s') (0 S1- s)
x2XXX62
P.(0, Srr 0, O.
s, U, a) TB._. (-15') To (-15') Il dads' daaddd'.
By the Lipschitzness of the policy improvement operator (see Assumption 2), we know
|| TO._. (-18') - no (+1)'')) S 16,-- - EE
sup
Then for any 0' θ for which P0, (( has non-zero density, meaning that 0' is reachable at time step L, Corollary 1.5.1 implies
[0(0)
0/| S ask Cprog (T);
where s is the largest integer such that sk <t Therefore, we have
J (o, - do s ask LC prog (T).
0.(0))
For S2, we have
A -
P:(Oi-1 = S1 = =6'10, 0100,-, = Ur a, 01-1-11 = (a'ls')
82x
P. (S 5/00-1, S To, (als) P.(S, = St. dOd0do'
Po(0i-1 = 0 1 St =
AxAx
(S. =000 S To, (als) Pt(S, = s10, (7((((ll) dsdad0
<
Pí(0,-1 = 0 01- ST-,, =)
SxAx0
(Pirr(S; (8: 8 3/0,-. S, )TB (a|s) P (3: s/0, St (rl(ass)
+ (5_ s/0, S P.(S, = s s/0,.. )T dodado
| Te( 1)) s)\llv + PL_ :(F Ps = -1, |TV
< sup SES
LC - 1) + ( P. (F
Substituting S1 and S2 with the above bounds gives
P((O. -O---) < (S. P.(S. -..5=))F-rr))) (F(-))
took L
Σ
Opro
1=7-1
(33)
34

---

Published as a conference paper at ICLR 2024
Applying similar decomposition as S1 and S2, we can obtain analogous bound to (33) for the state distribution discrepancy:
Pt Pt- = ( Pi = 1/
Pl - - TV + a,k LC progg 2)
P (S._ (F(+)) (S 1F
Σ 0 I.C prog
TV
5(r-2)ask L
Putting this bound back into (33) gives
(:(Oo]]e_>)) (1,--))--- STa
(T)
Finally, we get
Fr
gb
Stack (C (R+ (1 + 7) [0]]).
1.8 GRADIENT VARIANCE
Lemma L8 (Gradient variance).
(e Cra + 4m 4m2 H2 + 2T
32H2
E [l.)( 64
E 0 0.112+
w²
N
where
(T) = 4 (4(3 + 22 4 prog (T) + H2C back (a)c)))))
Similar to Lemma 1.1, we first decompose the gradient variance and establish the linear speedups for the backtracking and mixing terms.
Proof.
lg (0.) (g.) 0(.)
(34)
(..(0.) (0., O.) + g. (O., Ot) (0., O.)
(0,- Ô.) g: (0. + 9: (0.) - g(..)
(35)
4
(1)
(
(
( )|
N Mi
gt
-1-
2ml
G2, gradient progress
2
+ gt (0., O.)
gi-r 0,, O.
+4
ge-r 0., Ô. gr (0.)
Gg. backtracking
Ga. mixing
where (34) uses the fact that g(O.)
2 g(()
(050)
0: and in (35), we denote
Ii- Ii-- (0. E gi- 0,(0) and the same notation applies to other semi-gradients.
By the Lipschitzness of semi semi-gradient g² G1 is bounded by
9: (4)
(0..)
(((
)|²
<4 ( o 2
96
$12
(1000 00000
0e e
+ 10
0.112+ |0000 - 0.11²)
35

---

Published as a conference paper at ICLR 2024
By Lemma G.1, G2 is bounded by
- (0.*) (0.²) || 2 - (R (1 +1> 100) || |4_ - m1 )
2
LH2LL' | -
L4H2L'O? (1022 8/_. + +1
B8|l² +111 - -0.11
1 85.) 13
Now we are left with G3 and G4- However, we only have the bound of their first moment by Lemma 1.7 and 1.6. We first note that for a set of functions {9;) ) such that l|gilloc I a and independent
random variables { Jiy such that [B:ga b, have
[gg =E
9 (x
1 N
Σ s((z))
N
E
(2,)
g
(g (x,))
N
N²
N
N
N2
6².
(36)
N
By (36) and Lemma 1.7, the expectation of G3 is bounded by
E g. (0., O.) gi-r (0.. (0. 0. 0.)1 [ s
4H²
o Baak 112
(37)
N
By (36) and Lemma 1.6, the expectation of G4 is bounded by
E gt-r (0..0.)
-0) -0. Fe-r E
Z 0. o.) 0.)||²
2 Fe-
4H² N
+ m 2 p² H2.
Combining all together with Lemma I.4, I.5, and Theorem we get
A Ar(
E [[l. (0.) (00111 <4 (4(3 H²
E [| 0-|1² 1F[]]
+ a²x Carin +
w²
8H²
+ a
a
02
prog N
(a2x + m² mm?22)) H²
(3(()
32H
<64 E
[[0 6. 0.11² |F [F,-7]
+ a² C.xKvva Cvar 4m 222 H²
w²
where we use the fact that T.Ho < < required by (20), and
OproR + +12 H12CRack)) Ovar = (4(3 + 1 1 0² Carin + 122 2
Finally, we get
+a Ovar Crar+Am? 2 p² 112 s 64 [E100, - 0-112 + (2(())(r) w
32H2
(0.)11 = E
N
Recall that Lemma 1.5 bounds the central parameter progress, which gives naive bound of the mean square central parameter progress El 9.-r12 < a Cprog(7) for any T S t, where is the largest integer such that sk < t However, with the help of Lemma L8, we can derive a tighter bound of the mean square central parameter progress, which is essential for proving Theorem 2 later.
36

---

Published as a conference paper at ICLR 2024
Corollary 1.8.1 (Mean square central parameter progress). For any T S l, we huve
E 01 - 0--r 4 + 3K)a (64E |0,x - 0.11 + v(T)).
where s the largest integer such that sK St and
(e))
+ a. (T) + 4m p2 2T H22 + 32H2²
V(r)
w²
N
part of the gradient variance bound Lemma 1.8.
Proof. Recall in Lemma 1.5, we utilize a naive bound of [g (0)) by (R+ (1++1--) (1+) 2wr); the key difference in this proof that we will bound Ellg: (0:)ll using Lemma 1.8. Therefore, similar to (32), let and s' be the largest integer such that sk S T and s K S respectively, Then we have
Ell0, 01-112 S(s' 2)
El10: 1s
EE 0 0(0+j-1)K11 BB|0,- Os 112
<(8' - 8 +)
Bl10, 0xx
Σ Bll0( - 000+)-1))11 +BBI0, Osx 112
<2(s' 5 2)K
Σ g0
t=sk
<2(T + 3K)a
Ellgi (0))
By Lemma 1.8, we get
E El00 - 01 1100-61-711
2(T 3K (64E)0--0 0-11 V( - -sK)).
(38)
1=
Then, similar to (30), we want bound E100 1- by Bl|0.K 0.112 for sK < <1st-1 We have
E
0
1.112
s 6 0.
|| - 0, + 01 01-191-1 (0:-1){² 2|2
El - 0, 1|a 20 E (0-1 - 0,, 9.- (01-1)) + a2 gi-1 (0:-((0011)) ||?
(1 (1-1) )) E 1 - 0.11² + 01 + 01 || (0-1))1
(39)
$ (1 11-1 (1 + 64az E|) - 0-1 + 0+11 (1 + V(l - - sK), (40)
where (39) uses Young's inequality and (40) uses Lemma 1.8. We require 64a5k S 1, which gives (1 + (1 64a.-1) S (1 66a;-1). Recursively applying (40) gives
1-1-8
E 01 la1l² < (1 6
1- E 0. 0.11 + ask (1 + (sk)
Σ
1=
where we the fact that V is monotonically increasing. We further requires that 132(T+ K 1. Then, similar to (25), we get
(T+TT) S
E 0: 0.112 S 2Bll0.x 0-112 + 2a.k +1+ (T
(41)
37

---

Published as a conference paper at ICLR 2024
Combining (38) and (41) gives
B| 01--11 =2(T + 3K)a
(128E]|&<k 0-112 + 1280,K (1 + a,k) (T KTV(T) + +(r))
<2(T + 3K)aa
128E - 0.112 +
128
133
+1) V(T)
(42)
132
132
I=
<T(T + (T + 3K)a (64E 10x - 1.12 + V(T)),
where (42) uses our requirement that ac-r I (T + K)ack S 1/132.
J PROOF OF THEOREM 2
Theorem 2. If [:] S G holds for all S t, then
2 E B100+11 - 0. s (1 ).w) B 0. 0.1 1|2 + at C + + + + a
N
where C1, C2 C3, C4 are constants defined (50).
Proof. We need pre-process the results from Lemmas 1.3 to 1.7 before plugging them back into Lemma L.1. Throughout this proof, let s and s' be the largest integers such that sk I t 7 and
K S t. First, for Lemma I.3, by Young's inequality ab 1 (3a² + 2,6)). for any positive B, we have
2E
0
1 1 0., N
Σ
(.)) (0.)
2 (0.)
S 3T3 11,, 0.11 (p))
(43)
B
Similarly, for Lemma 1.4 and 1.5.2, we have
N 0.
2E
0n, N Σ (8( g(.) 53B 0.112
(1 Caiit
B
(44)
21E
0.112 + 0, 02, (3) (0()) (0(0) 23E
1
aas prog ProggL' L (0.),
C2
N
1=1
(45)
where 1², = 2/2 EN 112 (0(0) and
ER² (0.) = 212 + 2(1 + 7) [2,]] s 2H² 80 Ca S Haain
where we define Harift == 22H2 + 80 Carit
Then, for Lemma I.6, we have
E B(0. 00, (1) (0!0) ((0) (0())
1 N
01 1--00--
0.-r.
gt
( (1(0)
- (0.0) (0.)))
+
Σ
EE (0._
0., gr. (0.0) - -/" (0!00)
N
N
1=1
N
E
Gr 0
0.-r.
-
(1)
(0(0)
5 (0()) [
N
H.
N
+ E
0
8.11
E
(1) gi-
(0(0)
-r-
(i0)
F
N
38

---

Published as a conference paper at ICLR 2024
For H1, since both -i-7 and -i-7 are independent of og conditioned Fe-r. Lemma 1.5 and 1.6 give
(
(
H1
=E
E(o, P.-r F,
gi-r (0()) 9. (o!*) F(-1))
(
N
N
<
Σ
E|0
+e- Fi-11l
B - (8(0) F(-1)]
N
Sask Drog mp" (.) Saskmp" Grrog Harift-
(46)
Similarly, for H2, we have
H₂ =E | - 0.1l N 1=1
Σ
gi-r (0.²)
ge-r (0.0)
F Fe-r]]
<I (mpp Ehh (0,) (110- 0ell + 1101,-0.
-0, 0+ 0+1l)]
2mp Harin (1 0-11 + 0'.K Cprox)
1 2 BE 00: 01 + mm² mm p² Harinn
askmpp' Opro Harift.
Substituting H1 and H2 with the above bounds gives
N
2B G. 0. -..ge- (0()) -
-(_ (08
1i-mpHHari BE 10, 0x 00 Harift (2mp² Harin + 4a Cpoos
N
(47)
For Lemma 1.7, the trick we applied in (46) is no longer valid because 9e and o are correlated. Notice that o("), is deterministic given Ft-r, we first apply the following decomposition:
2E 0. 0., 91
0..9r
(8) (0) ( - (0 ,(0)))
21
0,
0y,
g6 10
10.00
o6 (0 -(0)) (0 (0 -0,0000000
H3
0er gr.g. (0 (0
62 ( 0.01 0
2E
H1
2E
Br 0....
( (e (2
g6 (0 0.0)) 0000
H5
By the Lipschitzness semiigradient gb and - and Corollary 1.5.1, we have
N
H1 S Σ
2E |10. - 0.11 0.11 -.11-4108" 000h < 3Ellō, 0.11 2 +
B Jask (prog(T)
4
02
i=1
By Lemma 1.7, we have
H4
0. Σ E -100-1-0.111
(0 -
(1)
|
< IE 00,
0
1
Chack 2- + 20 Gprog Che
(h(Orr)
B
39

---

Published as a conference paper at ICLR 2024
Finally, for Hs. by Young's inequality, we have
Hs S T 2K 0sKK (T + KT + 3K)
Elj0, 01-
0sk (T + (T 3k)
W 11g((0 -9---0000-- Fr-1] [|]]]=
T 2K
Since 0,- deterministic given Fi-ri can apply a similar argument (37) here, which gives
H3 ask (T + [T + 3K)
(T + 2K)
Bll6, 01--11 + +K)
(
[4/
a Chack Chack(T) (T)
By Corollary 1.8.1 and Lemma 1.5, we get
4H² Hs ST + 2K) 256E 10 - 0-112 + (V
N + a C Backk (T)
Sask(T + 2K)
(256(1 + 1/32)L 110, - -0.11 2-26 + 32)1B 00 - 0/11
++((r) + 4H12
a sk Paack (T)
N
4H²
S0.k(T +
264B |00 0. 8448o .k prog (T) + (V(()) +
+ o. Back (T)
H2
N
We further require that 1320,x (T + 2K) - 3. Then, plugging Ha, H4, H5, and V(T) back gives
N
02 - 0., 0z.gr 10) (0 0.00 - 2.2 -00000000000))
2E
N
1=1
1
2,322
<4
11 +
Boo (40 prog + 2.3 buuck Herift + Clack Harin) +
2
B
w.
132H
+ ta.k (T + 2K)
(84480 C + 40 Crar + 16m² p²1 H² + 0 Phack H²
N
(48)
Putting Equations (43) to (45), (47) and (48) and Lemmas 1.2 and 1.8 back into Lemma I.1, we get
E 00 - 0 < E
01+1 - 0g
<(1 -)aaw
10c 16--8. 0-12 80, 31E 110, 601-1111 1=l
(x)
Ex) 2,A
1 B gark (1 + (1+7++ (o+ Gan +
+ ai
+
3 3aak Opougl? 12H22 Harite
02
3
w
+ mpp Harife
Hann + 4ask 4a
+ 2 (4C prog + prCck Harin. + Boac (eeit))
Crack
132H12
+ a.kk( (T + 2K)
"844802x +402gCras + 16m 2T H2 + o² Ca Chack H2 +
32H² N
A?((p1(r) w²
+ at 64
11,10,-0.11" 0.112=
+ OZ Ovar + 4m 25 H2 +
N
Note that is a virtual time range that we backtrack, and we have not determined yet. Now require it to be large enough such that mp- I at. We also do not want 7 to be too large. Thus, we fix
T [llog a m)/ log p1 log o, We also require that the decay rate of a, is non-increasing and > a: = +00. Then, there exists
(49)
Ti > 0 such that for any 2 Tı. it holds that
log a₁ log m
$ K 2 1 - =
2
log
40

---

Published as a conference paper at ICLR 2024
The requirement the step-size also gives lim sup 01/2/01 to0. Then, there exists C. C. > O such that for any / 2 O, we have
01/2 Ca.
Ca
lim sup
sup
02
t1000 at
Thus, after some rearrangement, we get B 0.41 1
<(1 - w + 80g + 64a2) 0. - 0.11²= + (33Ca 2K) - 8) H² N
+ C2 (1 ((1+ +11+
+ Grog 1?2 oa + Haain + 4C prog + 2,3 Cback Harin + Bback Haritt)
+ 4Cprog Harift)
+ CaTa + +2K)(84480pp))) + 4Cvar + 16H + Back H²) + Ovar + 4H2)
23 + 6404
+ 0x
^? (em, 6r)
w²
Now we let B and on small enough such that
83 + 64x0 S w.
Then get the final form
C2 B B1 0.1 s (1 - a. 0.11 (xciA + +
+ + + a N
where
C =B-1 + (23 + 64cm) ) =
C2 4(33Ca (T 2K) + 8)H2
C3 ca (1+ + Oprog 1.2 H.rin + Harn 50 50pr 20acckHaatt Haritt (50)
4Cprog Harits
C4 ( (8448C) prog 40var + 16H Ch Hbacit + Cvar 4H
K PROOF OF CORROLARIES 2. AND 2.2
In this section, we provide the proofs of Corollaries 2.1 and 2.2. Combining with the constant dependencies discussed in Appendix L, we get the final results presented in Section 5. Corollary 2.1. With a constant step-size a, s w/(2200(K + 8 + In(m/(pw)))) for any N, we have
E OT - 038 S 4E woow 00 10- 1
+ B,
where B is the squared convergence region radius defined by
C2 B= = w ((++ w) () A²((p, (,) + 00 N + agCss + ajCs
1
Proof. Let be the central optimal parameter. By Theorem 2, for any N, we have
6A2 T
6A2
0 0.12 (1 (0)))))) EE 0_
B
agw) Se aown 110 -0.00.11++00
w
202
where the last inequality uses the fact that (1 - agw) S e ag ang and E1 - anw) = ((oow) Then by Theorem get
0 0(00)
2 | < 2EI1 0.112 + 2 S 4e- aoot - 0
6A w
6A2
E
wn
41

---

Published as a conference paper at ICLR 2024
Corollary 2.2. With linearty decaying step-size or 4/(w(1 + t +a)), where a is to guarantee that ao I min(1//8K), w/ w//4], there exists convex combination Or of {8:] such that
E 0r - 1/ = 0
C1 w
Czlog +
C2 wNT
(cp)(
+
w2T2
Proof.
Let ce = a + and C Et= ct 2 (T -T+11)2/2 We define
T Σ
0r C
G02s
t=0
which is a convex combination of {0r
1==
Then, by Jensen's inequality, we have
T
E 0 0,
||
Σ
GI 0 0-1
(51)
t=0
Let O, be the central optimal parameter. By Theorem 2, we have
1 R 00 0.11² S (1) 1 ay 2
E 1 - 0.1
R 0 - -0.11= + B(at), a2W
1
where B(a) = (C,A²+ + aC2/N + a² + a²Ca)/w. Recall our choice of the step-size at = 4/(w(( t + 1)); then have 1/(aww) (a t + 1)/4. Plugging this back into (51) gives
T
0r
02
2
a
aat-1- 1
0,
0_1 ||
a+t+1
E
0 1+1 0.11² +2B(aa)
2
2
1=0
T
Σ
(a t 1)(a
+ t)E 0b - 0.11 - (a + (a + + 1)E | - 0- 0211²)
2C
1=0
+ A0
8C2
T
a+1
32Ca T
a a+1 1
128Ca
T
a + L
+
CNw
a+t+1
Cws
(a t 1)22
Ow t=0
(a + t 1)3
1=
1=0
(ala- - 1) 110 - 0.112
(a + (a T
1) |T++ - 0. 11))
2C
A0
(T2(T+1)
32C₂
T
1
128Ca
T Σ
+
+
CNw +
+
Cw t=0
t+1
1
Owt
(t 1)2
(=0
a²
100
0.11
20₁A²
802
32C₂
Ollog(T) 256CA
+
T2
w
w2
NT
3T3
wAT2
a
C4
CologT
C2
C₁A²)
T2
w472
W3T2
N2NT
w
Then by Theorem 1 and the fact that 1/w S C1 (see Appendix L) and a S K/ww, we get
0
0r
2 s 2E
ØT 0.
|
+
2
2
0
[K++C, C1
C3 CologT
C2
C1A2
w
w1T2
w372
NT
w
L
L CONSTANT DEPENDENCIES
In this section, establish explicit dependencies between the constants. We begin by introducing
problem constants that are independent of other parameters: the reward cap R > 0, discount factor
y E (0, 1), projection radius G 0," local update period K, and kerne--related constants, m >
1.p (0, 1), and À min (0) E (0, Throughout this paper, we asymptotic notation
42

---

Published as a conference paper at ICLR 2024
R, G,K,K m + and P.P 1. We also the nonasymptotic notation a x and 2 to indicate that there exists C 2 such that a I Cbb, and a x indicate that both a S b and 2 hold.
We first give the dependencies of o' defined in (9). By its definition, we have o' 2 0, and
o' v log m
+ 1
log m + 1
log m 1-pp
log p
1-p
where the asymptotic notation holds as + and m + xc. We also get = o'+2 = (0oog (1- p)). We will now w is an important MDP constant and plays critical role in the convergence rate. By its defini- tion (19), we get w S 1/2 and
base constant.
min w/ 2
1-7 7
min (
2 X,
ME|M]
2
1E[M]
which gives
w -1== 1-(==((1-7))) ())
We then consider G and H. By Corollary 1.5.3, we get
2(2 + R) G 1 - 16a
G 1-7
When y is near 1, the above bound is undesirable. Thus, when y is large, we can further require 4agK v0.5, which gives G V 4(2G + R). Without loss of generality, we have
GzG+R
And by the definition of H, we get
R - (1+))
We now use H as a base constant and replace G + R with H for simplicity. H can be viewed as the scale of the problem. If we choose G according to (Zou et al., 2019), then H O(R((1 -)))
By (20), we get the dependencies the policy improvement operator's Lipschitz constant L:
L S oH
We now address the constants in Appendix By Lemma 1.4, we directly have
Caria (KH).
We now consider ag- There are two requirements on oo throughout the proof: 4Kog < in Lemmas 1.4 and I.5, and 64cg S w in Appendix J. Combining these conditions gives
00 S min
w
S min {K-,,w) ww]
4KK
64
Therefore, Oprog in Lemma 1.5 has the following dependencies:
Oprog = O((r + K)(H + K-1 K O(T K)H).
And Cback in Lemma 1.7 has the following dependencies:
Cback = 0 O(F
Then, Ovar in Lemma 1.8 is controlled by
Cyar OC wp²Groog + T22Cackk O(H?(K? w²74)).
OOne can choose G R/w suggested in Zou al. (2019). Here, we make it pre-defined algorithm constant.
43

---

Published as a conference paper at ICLR 2024
Next, give the dependencies of constants in Appendix J. By definition, have
Harift O(H + Carin))) O(H).
By the requirement of B, we have And we have C. = O(1). Therefore, we get
B x w.
C O(w O(11 - -))
C2 (T K)),
C 0 (H +?)) wTT)),
C4 = (T K)( + K2 + w²
Finally, we give the dependencies of constants in Corollaries 2.1 and 2.2. In Corollary 2.1, we choose constant step-size a = ag. There are two requirements on a, throughout the proof: 132(T K)ask S in Corollary 1.8.1 and 1320 (T + 2K) S 3 in Appendix J. concrete Furthermore, if we choose a small enough initial step size such that dg T ž max {K, w-, then C2, Cs. and C4 becomes
condition satisfying these requirements is (2120 (2K' + In (n(2120m)/(pw))
C2 === = Ō(1)), C3 = O(I2p=')== Ō(1) C4 Ol1 Ö(H?2w)), (52)
where Ô omits the logarithmic dependencies on т. Then the convergence region radius in Corol- lary 2.1 becomes
B B= 0 a H2
(1 - 7)2 (1- ) =ō - az +
A
agl? A2
+
N(1 7)
N(1 (1 7)-
With the linearly decaying step-size in Corollary 2.2, (49) gives
x log T
as the total number of iterations T + C0. And the requirements on ag in previous discussion automatically hold for large enough t. Omitting the logarithmic dependencies on T, C2, Ca, and C4 in this case are the same as (52). Therefore, the finite-time error bound in Corollary 2.2 becomes
E 6 0.1|
2
0
A Ex) H²
H (1 (1-7)²
δ
1 NT
A? H²
(1 (1-7)2
T2
NT
M TABULAR FEDSARSA
In this section, reduce algorithm and analysis to the tabular setting, Recall that S and A are the measures of the state space S and action space A, respectively. For the tabular setting, S and A the numbers of states and actions. Then, choose the feature map to be indicator vector function, i.c.,
S A-
[d(s, (((,,))(rr,a) + 1[(5 (s)
where we treat ((s, as a vector and use wwo-dimensional index such that [Ø(s, a)l(or,a)) is the (s', a')-th element of o(s, a); 1 is the indicator function. Using this feature map, the parameter is indeed the estimated value function table:
Qo(s,a) (s a)0 (0)..a)
Therefore, the local update rule in Algorithm 1 reduces the tabular SARSA update rule (2).
We now show natural bound G for ||0|] without an explicit projection. First, the true value function (1) is bounded by
Ia (s, a)l <
Σ
1- =: Goo-
t=0
44

---

Published as a conference paper at ICLR 2024
Suppose current estimated value function satisfies that Qr(s, Go for any state-action pair, then we have
(Q4+1(s,a) - aar(s, + - Qs,a)l
=|(1 a a)Qr(s, + t ar(s,,
<(1 x) G +aR
R
=(1 a - 0n)
+ a
R Gx
1-7
Therefore, if the bound holds for the initial estimated value fuunction, it holds for all sequential, local or central, estimated value functions. However, Go is a upper bound for |[0]| For 2-norm, we have
VSAR 1-7
|001| S V/AA1000 S
G,
which further gives
VSAR
==O
1 1-7
Also, for tabular FedSARSA, Remark 2 tells us that
1 =1 A(1 (x
is the probability of visiting the least probable acatin pair under the steady distribution the optimal policy across all agents. Then, Corollary 2.2 can be translated into the following corollary. Corollary 2.3 (Finite-time error bound for tabular FedSARSA with decaying step-size). With linearly decaying step-size at 4/(w(1 + 1 + a)); where >> is to guarantee that oo S min[1/(88] w/643, there exists a convex combination ÖT of {0,)T- such that
01 0 FP(1-)) Ō
SAR?
(1 (1-7)²a NT + A² (cpss (cp. (.)
SAR2
7T
where the asymptotic notation suppresses the logarithmic factors. Since 101|o0 S |101|2, we also get the finite-time error bound under the infinity norm.
45


Reviews:
[{"review_id": "4c2NRfAAHA", "reviewer": "Reviewer_rA2b", "summary": "This paper studies the problem of on-policy federated RL with agents interacting with potentially different environments. A new algorithm FedSARSA is proposed, and shown to converge to a near-optima policy for all gents. Convergence speed analysis is also provided.", "questions": "- It would be helpful if the authors could provide more intuition about where the speed up comes from. Specifically, what in the problem formulation/assumptions enable this speedup? Intuitively, this would be possible only when things are homogeneous (or close to that). \n- Is it possible to comment on the optimality of the finite-time error? Right now only upper bounds are provided.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written. The formulation and ideas are explained clearly.", "weaknesses": "- It would be helpful if the authors could provide more intuition about where the speed up comes from. Specifically, what in the problem formulation/assumptions enable this speedup? Intuitively, this would be possible only when things are homogeneous (or close to that). \n- Is it possible to comment on the optimality of the finite-time error? Right now only upper bounds are provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oVEQlnaJ6N", "reviewer": "Reviewer_qewk", "summary": "This paper studies federated on-policy reinforcement learning with linear function approximation. It proposes FedSARSA that is a federated version of SARSA. It proves that FedSARSA converges to the neighborhood of the optimal parameter with a linear speed up.", "questions": "- The motivation is unclear to me -- why do we want to learn a single universal policy? Each agent may interact with his/her own environment and learn a personalized policy for that environment. Isn't that better to be deployed on that environment than the single averaged policy across all environments?\n- I don't see the linear speedup in the simulation results?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "+ FedSARSA is intuitive and reasonable.\n+ The theoretical result that proves linear speedup is interesting.", "weaknesses": "- The theoretical results do not have the impact of periodic updating. \n- The authors do not specify the communication cost and how it trades off with the convergence.\n- The FedSARSA is a straightforward of single-agent SARSA -- the only difference is to aggregate the parameter estimation from all agents, which is a straightforward average.\n- The authors talked about how heterogeneity is captured in the convergence, but this relationship is not well articulated. In FL, one would first need to define the heterogeneity metric and then express the convergence bound as a function of this metric. Furthermore, such heterogeneity should be defined on the data, not the underlying distribution.\n- Paper writing needs some work. It is strange to not have a Conclusion section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iVQFRSC94m", "reviewer": "Reviewer_uJdU", "summary": "This work performs theoretical studies on federated reinforcement learning with clients facing heterogeneous environments. In particular, the classical SARSA algorithm is extended to the federated version. Theoretical analyses are established to demonstrate the finite-sample convergence of the proposed FedSARSA under linear function approximation. In particular, linear speedups are reported with the established results.", "questions": "Please see the weakness section.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work follows the interesting line of work of extending federated learning to the domain of decision-making under environmental heterogeneity. This setting is well-motivated and has wide practical implications.\n\n- The established results are solid and novel based on my reading. In particular, no similar results have been reported on FRL with heterogeneous clients in the planning task with both linear function approximation and linear speedup.\n\n- Despite the theoretical nature, the overall presentation is clear and the key intuitions are provided. The listed sketch of the proof especially facilitates the readability.", "weaknesses": "- I am overall satisfied with this work. There is just one minor question I have for the authors. As mentioned at the end of page 8, the obtained results from federated RL can be leveraged as initialization points for finetuning with just local data. I imagine the analyses would not be different given existing works, and wonder whether it would be possible to state the finetuning results, which may better highlight the impact of cooperation on accelerating individual learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LvZaY3SfuP", "reviewer": "Reviewer_pmTu", "summary": "The paper proposes the federated version of SARSA algorithm and analyses its convergent performance with the existence of heterogeneity in both transition dynamics and reward functions.\nDifferent from classical settings of federated reinforcement learning, the paper does not assume that agents have to share the same transition dynamics and reward functions.\nThe paper demonstrates that its proposed algorithm achieves a linear speedup for the convergence to the optimal answer in each local environment both theoretically and empirically.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper considers heterogeneity in both transition dynamics and reward functions. Moreover, it quantifies the degree of these heterogeneities and discusses their effect in the final convergence of FedSARSA.\n2. The paper discusses the convergence region and linear speedup of FedSARSA. It is claimed that smaller learning rates and a larger number of participating agents will help tighten the convergence region, which matches the intuition.\n3. The numerical experiment is carried out in settings with different degrees of heterogeneity.", "weaknesses": "1. What does MSE in the numerical experiments stand for? Does it mean the averaged MSE of current parameter to optimal parameters in different environments?\n2. The explanation of numerical experiments is not enough. For example, why the MSE of FedSARSA with a large number of $N$ ($N=40$) increase along the training process when $\\epsilon_p>0,\\epsilon_r>0$? And where is the confidence bound for the numerical experiments?\n3. The convergence MSE of FedSARSA with different number of agents are different from each other. What makes that difference?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)