The Sample-Communication Complexity Trade-off in Federated Q-Learning

Authors: sudeep  salgia
yuejie  chi
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:20:32

Abstract: We consider the problem of Federated Q-learning, where $M$ agents aim to collaboratively learn the optimal Q-function of an unknown infinite horizon Markov Decision Process with finite state and action spaces. We investigate the trade-off between sample and communication complexity for the widely used class of intermittent communication algorithms. We first establish the converse result, where we show that any Federated Q-learning that offers a linear speedup with respect to number of agents in sample complexity needs to incur a communication cost of at least $\Omega(\frac{1}{1-\gamma})$, where $\gamma$ is the discount factor. We also propose a new Federated Q-learning algorithm, called Fed-DVR-Q, which is the first Federated Q-learning algorithm to simultaneously achieve order-optimal sample and communication complexities. Thus, together these results provide a complete characterization of the sample-communication complexity trade-off in Federated Q-learning.

Main paper: 
 introduction: 
 Reinforcement Learning (RL) [Sutton and Barton, 2018] refers to an online sequential decision making paradigm where the learning agent aims to learn an optimal policy, i.e., a policy that maximizes the long-term reward, through repeated interactions with an unknown environment. RL finds applications across a diverse array of fields including, but not limited to, autonomous driving, games, recommendation systems, robotics and Internet of Things (IoT) [Kober et al., 2013 , Yurtsever et al., 2020 , Silver et al., 2016 , Lim et al., 2020] .The primary hurdle in RL applications is often the high-dimensional nature of the decision space that necessitates the learning agent to have to access to an enormous amount of data in order to have any hope of learning the optimal policy. Moreover, the sequential collection of such an enormous amount of data through a single agent is extremely time-consuming and often infeasible in practice. Consequently, practical implementations of RL involve deploying multiple agents to collect data in parallel. This decentralized approach to data collection has fueled the design and development of distributed or federated RL algorithms that can collaboratively learn the optimal policy without actually transferring the collected data to a centralized server. Such a federated approach to RL, which does not require the transfer of local data, is gaining interest due to lower bandwidth requirements and lower security and privacy risks. In this work, we focus on federated variants of Q-learning algorithms where the agents collaborate to directly learn the optimal Q-function without forming an estimate of the underlying unknown environment.A particularly important aspect of designing Federated RL algorithms, including Federated Q-learning algorithms, is to address the natural tension between sample and communication complexity. At one end of the spectrum lies the naïve approach of running a centralized algorithm with optimal sample complexity after transferring and combining all the collected data at a central facility/server. Such an approach trivially achieves the optimal sample complexity while suffering from a very high and infeasible communication complexity. On the other hand, several recently proposed algorithms [Khodadadian et al., 2022 , Woo et al., 2023] operate in more practical regimes, offering significantly lower communication complexities as compared to the naïve approach at the cost of sub-optimal sample complexities. These results suggest the existence of underlying trade-off between sample and communication complexities of Federated RL algorithms. The primary goal of this work is to better understand this trade-off in context of Federated Q-learning by investigating these following fundamental questions:• Fundamental limit of communication: What is the minimum amount of communication required by a federated Q-learning algorithm to achieve any statistical benefit of collaboration?• Optimal algorithm design: How does one design a federated Q-Learning algorithm that simultaneously offers optimal order sample and communication complexity guarantees i.e., operates on the optimal frontier of sample-communication complexity trade-off?We consider a setup where M distributed agents collaborate to learn the optimal Q-function of an infinite horizon Markov Decision Process which is defined over a finite state space S and a finite action set A, and has a discount factor of γ ∈ (0, 1). We consider a commonly considered setup in federated learning called the intermittent communication setting, where the clients intermittently share information among themselves with the help of a central server. In this work, we provide a complete characterization of the trade-off between sample and communication complexity under the aforementioned setting by providing answers to both the questions. The main result of this work is twofold and is summarized below.• Fundamental bounds on communication complexity of Federated Q-learning: We establish lower bounds on the communication complexity of Federated Q-learning, both in terms of number of communication rounds and the overall number of bits that need to be transmitted in order to achieve any speed up in convergence with respect to the number of agents. Specifically, we show that in order for an intermittent communication algorithm to obtain any benefit of collaboration, i.e., any order of speed up w.r.t. the number of agents, the number of communication rounds must be least Ω( 1(1-γ) log 2 N ) and the number of bits sent by each agent to the server must be least Ω( |S||A| (1-γ) log 2 N ), where N denotes the number of samples taken by the algorithm for each state-action pair.• Achieving the optimal sample-communication complexity trade-off : We propose a new Federated Q-Learning algorithm called Federated Doubly Variance Reduced Q Learning, Fed-DVR-Q for short, that simultaneously achieves optimal order of sample complexity and the minimal order of communication as dictated by the lower bound. We show that Fed-DVR-Q learns an ε-optimal Q-function in the ℓ ∞ sense with Õ |S||A| M ε 2 (1-γ) 3 i.i.d. samples from the generative model at each agent while incurring a total communication cost of Õ |S||A|(1-γ) bits per agent across Õ 1 (1-γ) rounds of communication. Thus, Fed-DVR-Q not only improves upon both the sample and communication complexities of existing algorithms, but also is the first algorithm to achieve both order-optimal sample and communication complexities (See Table 1 for a comparison).Single agent Q-Learning. Q-Learning has been extensively studied in the single-agent setting in terms of both its asymptotic convergence [Jaakkola et al., 1993 , Tsitsiklis, 1994 , Szepesvári, 1997 , Borkar and Meyn, 2000] and its finite-time sample complexity in both synchronous [Even-Dar and Mansour, 2004 , Beck and Srikant, 2012 , Wainwright, 2019a , Chen et al., 2020 , Li et al., 2023] and asynchronous settings [Chen et al., 2021b , Li et al., 2023 , 2021 , Qu and Wierman, 2020] .Distributed RL. There has also been a considerable effort towards developing distributed and federated RL algorithms. The distributed variants of the classical TD learning algorithm have been investigated in a series of studies [Chen et al., 2021c , Doan et al., 2019 , 2021 , Sun et al., 2020 , Wai, 2020 , Wang et al., 2020 , Zeng et al., 2021b] . The impact of environmental heterogeneity in federated TD learning was studied in Wang et al. [2023] . A distributed version of actor-critic Table 1 : Comparison of sample and communication complexity of various single-agent and Federated Q-learning algorithms for learning an ε-optimal Q-function under the synchronous setting. We hide logarithmic factors and burn-in costs for all results for simplicity of presentation. In the above table, S and A represent state and action spaces respectively and γ denotes the discount factor. We report the communication complexity only in terms of number of rounds as other algorithms assume transmission of real numbers and hence do not report bit level costs. For the lower bound, Azar et al. [2013] and this work establish the bound for sample and communication complexity respectively. algorithms was studied by Shen et al. [2023] where the authors established convergence of their algorithm and demonstrated a linear speed up in the number of agents in their sample complexity bound. Chen et al. [2022] proposed a new distributed actor-critic algorithm which improved the dependence of sample complexity on the error ε and incurs a communication cost of Õ(ε -1 ). Chen et al. [2021a] have proposed a communication efficient distributed policy gradient algorithm and have analyzed its convergence and established a communication complexity of O(1/(M ε)). Xie and Song [2023] adopts a distributed policy optimization perspective, which is different from the Q-learning paradigm considered in this work. Moreover, the algorithm in Xie and Song [2023] obtains a linear communication cost, which is worse than that obtained in our work. Similarly, Zhang et al. [2024] focuses on on-policy learning and incurs a communication cost that depends polynomially on the required error ε. Several other studies [Yang et al., 2023 , Zeng et al., 2021a , Lan et al., 2024] have also developed and analyzed other distributed/federated variants of the classical natural policy gradient method [Kakade, 2001] . Assran et al. [2019] , Espeholt et al. [2018] , Mnih et al. [2016] have developed distributed algorithms to train deep RL networks more efficiently.Distributed Q-learning. Federated Q-learning has been explored relatively recently. Khodadadian et al. [2022] proposed and analyzed a federated Q-learning algorithm in the asynchronous setting with a sample complexity of Õ |S| 2 M µ 5 min (1-γ) 9 ε 2 , where µ min is the minimum entry of the stationary state-action occupancy distribution of the sample trajectories over all agents. Jin et al. [2022] study the impact of environmental heterogeneity across clients in Federated Q-learning. They propose an algorithm where the local environments are different at each client but each client knows their local environment. Under this setting, they propose an algorithm that achieves a sample and communication complexity of O( 1(1-γ) 3 ε ) and O( 1 (1-γ) 3 ε ) rounds respectively. Woo et al. [2023] proposed new algorithms with improved analysis for Federated Q-learning under both synchronous and asynchronous settings. Their proposed algorithm achieves a sample complexity and communication complexity of Õ( |S||A| M (1-γ) 5 ε 2 ) and Õ( M |S||A| 1-γ ) real numbers respectively under the synchronous setting and that of Õ( 1M µavg(1-γ) 5 ε 2 ) and Õ M |S||A| 1-γ real numbers respectively under the asynchronous setting. Here, µ avg denotes the minimum entry of the average stationary state-action occupancy distribution of all agents. In a follow up work, Woo et al. [2024] propose a Federated Qlearning for offline RL in finite horizon setting and establish a sample and communication complexity of Õ( Accuracy-Communication Trade-off in Federated Learning. The trade-off between communication complexity and accuracy (equivalently, sample complexity) has been studied in various federated and distributed learning problems, including stochastic approximation algorithms for convex optimization. Duchi et al. [2014] , Braverman et al. [2016] establish the celebrated inverse linear relationship between the error and the communication cost the problem of distributed mean estimation. Similar trade-off for distributed stochastic optimization, multi-armed bandits and linear bandits has been studied and established across numerous studies [Woodworth et al., 2018 , 2021 , Tsitsiklis and Luo, 1987 , Shi and Shen, 2021 , Salgia and Zhao, 2023] .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: In the abstract and introduction, we describe that we study the samplecommunication complexity trade-off in Federated Q-learning and derive both converse and achievability results. In Sec. 3 we derive the lower bound on communication complexity and in Sec. 4 we outline the algorithm that matches the lower bound derived earlier.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
problem formulation and preliminaries: 
 In this section, we provide a brief background of Markov Decision Processes, outline the performance measures for Federated Q-learning algorithms and describe the class of intermittent communication algorithms considered in this work.In this work, we focus on an infinite-horizon Markov Decision Process (MDP), denoted by M, over a state space S and an action space A and with a discount factor γ ∈ (0, 1). Both the state and action spaces are assumed to be finite sets. In an MDP, the state s evolves dynamically under the influence of actions based on a probability transition kernel, P : (S × A) × S → [0, 1]. The entry P (s ′ |s, a) denotes the probability of moving to state s ′ when an action a is taken in the state s. An MDP is also associated with a deterministic reward function r : S × A → [0, 1], where r(s, a) denotes the immediate reward obtained for taking the action a in the state s. Thus, the transition kernel P along with the reward function r completely characterize an MDP. In this work, we consider the synchronous setting, where each agent has access to an independent generative model or simulator from which they can draw independent samples from the unknown underlying distribution P (•|s, a) for each state-action pair (s, a) [Kearns and Singh, 1998] .A policy π : S → ∆(A) is a rule for selecting actions across different states, where ∆(A) denotes the simplex over A and π(a|s) denotes the probability of choosing action a in a state s. Each policy π is associated with a state value function and a state-action value function, or the Q-function, denoted by V π and Q π respectively. V π and Q π measure the expected discounted cumulative reward attained by π starting from a particular state s and state-action pair (s, a) respectively. Mathematically, V π and Q π are given asV π (s) := E ∞ t=0 γ t r(s t , a t ) s 0 = s ; Q π (s, a) := E ∞ t=0 γ t r(s t , a t ) s 0 = s, a 0 = a , (1)where a t ∼ π(•|s t ) and s t+1 ∼ P ( • |s t , a t ) for all t ≥ 0. The expectation is taken w.r.t. the randomness in the trajectory {s t , a t } ∞ t=1 . Since the rewards lie in [0, 1], it follows immediately that both the value function and Q-function lie in the range [0, 1 1-γ ]. An optimal policy π ⋆ is a policy that maximizes the value function uniformly over all the states and it has been shown that such an optimal policy π ⋆ always exists [Puterman, 2014] . The optimal value and Q-functions are those corresponding to that of an optimal policy π ⋆ are denoted asV ⋆ := V π ⋆ and Q ⋆ := Q π ⋆respectively. The optimal Q-function, Q ⋆ , is also the unique fixed point of the Bellman operator T : S × A → S × A, given by(T Q)(s, a) = r(s, a) + γ • E s ′ ∼P (•|s,a) max a ′ ∈A Q(s ′ , a ′ ) .(2) Q-learning [Watkins and Dayan, 1992] aims to learn the optimal policy by first learning Q ⋆ as the solution to the fixed point equation T Q = Q and then obtain a deterministic optimal policy via the maximization π ⋆ (s) = arg max a Q ⋆ (s, a).Let Z ∈ S |S||A| be a random vector whose (s, a) th coordinate is drawn from the distribution P (•|s, a), independently of all other coordinates. We define the random operator T Z : (S × A) → (S × A) asEQUATIONwhere V (s ′ ) = max a ′ ∈A Q(s ′ , a ′ ). The operator T Z can be interpreted as the sample Bellman Operator, where we have the relationT Q = E Z [T Z Q] for all Q-functions.Lastly, the federated learning setup considered in this work consists of M agents, where all the agents face a common, unknown MDP, i.e., the transition kernel and the reward functions are the same across agents, which is popularly known as the homogeneous setting. For a given value of ε ∈ (0, 1 1-γ ), the objective of agents is to collaboratively learn an ε-optimal estimate (in the ℓ ∞ sense) of the optimal Q-function of the unknown MDP.We measure the performance of a Federated Q-learning algorithm A using two metrics -sample complexity and communication complexity. For a given MDP M, let Q M (A , N, M ) denote the estimate of Q ⋆ M , the optimal Q-function of the MDP M, returned by an algorithm A , when given access to N i.i.d. samples from the generative model for each (s, a) pair at all the M agents. The minimax error rate of the algorithm A , denoted by ER(A ; N, M ), is defined asEQUATIONwhere the expectation is taken over the samples and any randomness in the algorithm. Given a value of ε > 0, the sample complexity of A , denoted by SC(A ; ε, M ) is given asEQUATIONSimilarly, we can also define a high-probability version for any δ ∈ (0, 1) as follows:SC(A ; ε, M, δ) := |S||A| • min{N ∈ N : Pr(sup M ∥ Q M (A , N, M ) -Q ⋆ M ∥ ∞ ≤ ε) ≥ 1 -δ}.We measure the communication complexity of any federated learning algorithm both in terms of frequency of information exchange and total number of bits uploaded by the agents. For each agent m, let C m round (A ; N ) and C m bit (A ; N ) respectively denote the number of times agent m sends a message to the server and the total number of bits uploaded by agent m to the server when an algorithm A is run with N i.i.d. samples from the generative model for each (s, a) pair at each agent. The communication complexity of A , when measured in terms of frequency of communication and total number of bits exchanged, is given byEQUATIONrespectively. Similarly, for a given value of ε ∈ (0, 1 1-γ ), we can also define CC round (A ; ε) and CC bit (A ; ε) based on when A is run to guarantee a minimax error of at most ε.Algorithm 1: A generic algorithm A end for 8: end for 9: return Q T In this work, we consider a popular class of federated learning algorithms referred to as algorithms with intermittent communication. The intermittent communication setting provides a natural framework to extend single agent Qlearning algorithms to the distributed setting. As the name suggests, under this setting, the agents intermittently communicate with each other, sharing their updated beliefs about Q ⋆ . Between two communication rounds, each agent updates their belief about Q ⋆ using stochastic fixed point iteration based on the locally available data, similar to a single agent setup. Such intermittent communication algorithms have been extensively studied and used to establish lower bounds on communication complexity of distributed stochastic convex optimization [Woodworth et al., 2018 [Woodworth et al., , 2021]] .1: Input : T, R, {η t } T t=1 , C = {t r } R r=1 , B 2: Set Q m 0 ← 0 for all agents m 3: for t = 1, 2, . . . , T do 4: for m = 1, 2, . . . , M do 5: Compute Q m t-A generic Federated Q-learning algorithm with intermittent communication is outlined in Algorithm 1. It is characterized by the following five parameters: (i) total number of updates T ; (ii) the number of communication rounds R; (iii) a step size schedule{η t } T t=1 ; (iv) a communication schedule {t r } R r=1 ; (v) batch size B. During the t th iteration, each agent m computes { T Z b (Q m t-1 )} B b=1, a minibatch of sample Bellman operators at the current estimate Q m t-1 , using B samples from the generative model for each (s, a) pair, and obtains an intermediate local estimate using the Q-learning update as follows:EQUATIONHere η t ∈ (0, 1] is the step-size chosen corresponding to the t th time step. The intermediate estimates are averaged based on a communication schedule C = {t r } R r=1 consisting of R rounds, i.e.,EQUATION)In the above equation, the averaging step can also be replaced with any distributed mean estimation routine that includes compression to control the bit level costs. Without loss of generality, we assume that Q m 0 = 0 for all agents m and t R = T , i.e., the last iterates are always averaged. It is straightforward to note that the number of samples taken by an intermittent communication algorithm is BT , i.e, N = BT and the communication complexity CC round = R.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We consider an infinite horizon MDP in the tabular setting and derive the results for the class of intermittent communication algorithms. We acknowledge that these assumptions might be restrictive for a certain class of applications and extension to more general settings is discussed as a future direction in Sec. 5. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
lower bound: 
 In this section, we investigate the first of the two questions regarding the lower bound on communication complexity. The following theorem establishes a lower bound on the communication complexity of a Federated Q-learning algorithm with intermittent communication. Theorem 1. Assume that γ ∈ [5/6, 1) and the state and action spaces satisfy |S| ≥ 4 and |A| ≥ 2. Let A be a Federated Q-learning algorithm with intermittent communication that is run for T ≥ max{16, 1 1-γ } steps with a step size schedule of either η t :=1 1+cη(1-γ)t or η t := η for all 1 ≤ t ≤ T . If R = CC round (A ; N ) ≤ c 0 (1 -γ) log 2 N ; or CC bit (A ; N ) ≤ c 1 |S||A| (1 -γ) log 2 Nfor some universal constants c 0 , c 1 > 0 then, for all choices of communication schedule, batch size B, c η > 0 and η ∈ (0, 1), the minimax error of A satisfiesER(A ; N, M ) ≥ C γ log 3 N √ N ,for all M ≥ 2 and N = BT . Here C γ > 0 is a constant that depends only on γ.The above theorem states that in order for an intermittent communication algorithm to obtain any benefit of collaboration, i.e., for the error rate ER(A ; N, M ) to decrease w.r.t. number of agents, the number of communication rounds must be least Ω(1 (1-γ) log 2 N). This implies that any Federated Q-learning algorithm that offers order optimal sample complexity, and thereby also a linear speed up with respect to the number of agents, must have at least Ω( 1 (1-γ) log 2 N ) rounds of communication and transmit Ω( |S||A| (1-γ) log 2 N ) bits of information per agent. This characterizes the converse relation for the sample-communication tradeoff in Federated Q-learning. We would like to point out that our lower bound extends to the asynchronous setting as the assumption of i.i.d. noise corresponding to a generative model is a special case of Markovian noise observed in asynchronous setting.The lower bound on the communication complexity of Federated Q-learning is a consequence of the bias-variance trade-off that governs the convergence of the algorithm. While a careful choice of step-sizes alone is sufficient to balance this trade-off in the centralized setting, the choice of communication schedule also plays an important role in balancing this trade-off in the federated setting. The local steps between two communication rounds induce a positive estimation bias that depends on the standard deviation of the iterates and is a well-documented issue of "over-estimation" in Q-learning [Hasselt, 2010] . Since such a bias is driven by local updates, it does not reflect any benefit of collaboration. During a communication round, the averaging of iterates across agents allows the algorithm an opportunity to counter this bias by reducing the effective variance of the updates through averaging. In our analysis, we show that if the communication is infrequent, the local bias becomes the dominant term and averaging of iterates is insufficient to counter the impact of the positive bias induced by the local steps. As a result, we do not observe any statistical gains when the communication is infrequent. The analysis is inspired the analysis of Q-learning by Li et al. [2023] and is based on analyzing the convergence of an intermittent communication algorithm on a specifically chosen "hard" instance of MDP. Please refer to Appendix B for a detailed proof. Remark 1 (Communication complexity of policy evaluation). Several recent studies [Liu and Olshevsky, 2023, Tian et al., 2024] established that a single round of communication is sufficient to achieve linear speedup of TD learning for policy evaluation, which do not contradict with our results focusing on Q-learning for policy learning. The latter is more involved due to the nonlinearity of the Bellman optimality operator. Specifically, if the operator whose fixed point is to be found is linear in the decision variable (e.g., the value function in TD learning) then the fixed point update only induces a variance term corresponding to the noise. However, if the operator is non-linear, then in addition to the variance term, we also obtain a bias term in the fixed point update. While the variance term can be controlled with one-shot averaging, more frequent communication is necessary to ensure that the bias term is small enough. Remark 2 (Extension to asynchronous Q-learning). We would like to point out that our lower bound extends to the asynchronous setting [Li et al., 2023] as the assumption of i.i.d. noise corresponding to a generative model is a special case of Markovian noise observed in the asynchronous setting. 
the fed-dvr-q algorithm: 
 Having characterized the lower bound on the communication complexity of Federated Q-learning, we explore our second question of interest -designing a federated Q-learning algorithm that achieves this lower bound while simultaneously offering an optimal order of sample complexity.We propose a new Federated Q-learning algorithm, Fed-DVR-Q, that achieves not only a communication complexity of CC round = Õ( 1 1-γ ) and CC bit = Õ( |S||A| 1-γ ) but also the optimal order of sample complexity (upto logarithmic factors), thereby providing a tight characterization of the achievability frontier that matches with the converse result derived in the previous section.Algorithm 2: Fed-DVR-Q 1: Input : Error bound ε > 0, failure probability δ > 0 2: k ← 1, Q (0) ← 0 3: // Set parameters as described in Sec. 4.1.3 4: for k = 1, 2, . . . , K do 5:Q (k) ← REFINEESTIMATE(Q (k-1) , B, I, L k , D k , J) 6: k ← k + 1 7: end for 8: return Q (K)Fed-DVR-Q proceeds in epochs. During an epoch k ≥ 1, the agents collaboratively update Q (k-1) , the estimate of Q ⋆ obtained at the end of previous epoch, to a new estimate Q (k) , with the aid of the sub-routine called REFINEESTIMATE. The sub-routine REFINEESTIMATE is designed to ensure that the suboptimality gap, ∥Q (k) -Q ⋆ ∥ ∞ , reduces by a factor of 2 at the end of every epoch. Thus, at the end of K = O(log(1/ε)) epochs, Fed-DVR-Q obtains a ε-optimal estimate of Q ⋆ , which is then set to be the output of the algorithm. Please refer to Alg. 2 for a pseudocode.The REFINEESTIMATE sub-routine REFINEESTIMATE, starting from Q, an initial estimate of Q ⋆ , uses variance reduced Q-learning updates to obtain an improved estimate of Q ⋆ . It is characterized by four parameters -the initial estimate Q, the number of local iterations I, the recentering sample size L and the batch size B, which can be appropriately tuned to control the quality of the returned estimate. Additionally, it also takes input two parameters D and J required by the compressor.The first step in REFINEESTIMATE is to collaboratively approximate T Q for the variance reduced updates. To this effect, each agent m builds an approximation of T Q as follows:EQUATIONwhere{Z (m) 1 , Z (m) 2 , . . . , Z (m) ⌈L/M ⌉ } are ⌈L/M ⌉ i.i.d. samples with Z (m) 1 ∼ Z. Each agent sends C T (m) L (Q) -Q; D, J , a compressed version of the difference T (m) L(Q) -Q, to the server, which collects all the estimates from the agents and constructs the estimateEQUATIONand sends it back to the agents for the variance reduced updates. We defer the description of the compression routine to the end of this section. Equipped with the estimate T L (Q), REFINEESTIMATE constructs a sequence {Q i } I i=1 using the following iterative update scheme initialized with Q 0 = Q. During the i th iteration, each agent m carries out the following update:EQUATIONIn the above equation, η ∈ (0, 1) is the step size andT (m) i Q := 1 B z∈Z (m) i T z Q, where Z (m) iis the minibatch of B i.i.d. random variables drawn according to Z, independently at each agent m for all iterations i. Each agent then sends a compressed version of the update, i.e., C Qm i-1 2 -Q i-1 ; D, J ,to the server, which uses them to compute the next iterateEQUATIONand broadcast it to the clients. After I such updates, the obtained iterate Q I is returned by the routine.A pseudocode of the REFINEESTIMATE routine is given in Algorithm 3 in Appendix A.The compressor, C (•; D, J), used in the proposed algorithm Fed-DVR-Q is based on the popular stochastic quantization scheme. In addition to the input vector Q to be quantized, the quantizer C takes two input parameters D and J. D corresponds to an upper bound on ℓ ∞ norm of Q, i.e., ∥Q∥ ∞ ≤ D. J corresponds to the resolution of the compressor, i.e., number of bits used by the compressor to represent each coordinate of the output vector.The compressor first splits the interval [0, D] into 2 J -1 intervals of equal length where0 = d 1 < d 2 , • • • < d 2 J = D correspondto end points of the intervals. Each coordinate of Q is then separately quantized as follows. The value of the n th coordinate, C (Q) [n] , is set to be d jn-1 with probabilitydj n -Q[n] dj n -dj n-1and to d jn with the remaining probability, where j n := min{j :d j < Q[i] ≤ d j+1 }.It is straightforward to note that each coordinate of C (Q) can be represented using J bits.The desired convergence of the iterates {Q (k) } is obtained by carefully choosing the parameters of the sub-routine REFINEESTIMATE and the compression operator C . For all epochs k ≥ 1, we set the number of iterations I and the batch size B of REFINEESTIMATE and the number of bits J of the compressor C to be ⌈EQUATION))⌉ respectively. The total number of epochs is set toK = ⌈ 1 2 log 2 ( 1 1-γ )⌉ + ⌈ 1 2 log 2 ( 1 (1-γ)ε 2 )⌉.The recentering sample sizes L k and bounds D k are set to be the following functions of epoch index k:EQUATION)whereK 0 = ⌈ 1 2 log 2 ( 1 1-γ )⌉.The piecewise definition of L k is crucial to obtain the optimal dependence with respect to 1 1-γ , similar to the two-step procedure outlined in Wainwright [2019b] .The following theorem characterizes the sample and communication complexity of Fed-DVR-Q.Theorem 2. Consider any δ ∈ (0, 1) and ε ∈ (0, 1]. Under the federated learning setup described in Section 2.1, the sample and communication complexities of the Fed-DVR-Q algorithm, when run with the choice of parameters described in Sec. 4.1.3 and a learning rate η ∈ (0, 1), satisfy the following relations for some universal constant C 1 > 0:SC(Fed-DVR-Q; ε, M, δ) ≤ C 1 ηM (1 -γ) 3 ε 2 log 2 1 (1 -γ)ε log 8KI|S||A| δ , CC round (Fed-DVR-Q; ε, δ) ≤ 16 η(1 -γ) log 2 1 (1 -γ)ε , CC bit (Fed-DVR-Q; ε, δ) ≤ 32|S|A| η(1 -γ) log 2 1 (1 -γ)ε log 2 70 η(1 -γ) 2 M log 8KI|S||A| δ .A proof of Theorem 2 can be found in Appendix C. A few implications of the theorem are in order.Optimal Sample-Communication complexity trade-off. As shown by the above theorem, Fed-DVR-Q offers a linear speed up in the sample complexity with respect to the number of agents while simultaneously achieving the same order of communication complexity as dictated by the lower bound derived in Theorem 1, both in terms of frequency and bit level complexity. Moreover, Fed-DVR-Q is the first Federated Q-Learning algorithm that achieves a sample complexity with optimal dependence on all the salient parameters, i.e., |S|, |A| and 1 1-γ , in addition to linear speedup w.r.t. to number of agents and thereby bridges the existing gap between upper and lower bounds on sample complexity for Federated Q-learning. Thus, Theorem 1 and 2 together provide a characterization of optimal operating point of the sample-communication complexity trade-off in Federated Q-learning.Role of Minibatching. The commonly adopted approach in intermittent communication algorithm is to use a local update scheme that takes multiple small (i.e., B = O(1)), noisy updates between communication rounds, as evident from the algorithm design in Khodadadian et al. [2022] , Woo et al. [2023] and even numerous FL algorithms for stochastic optimization McMahan et al. [2017] , Haddadpour et al. [2019] , Khaled et al. [2020] . In Fed-DVR-Q, we replace the local update scheme of taking multiple small, noisy updates by a single, large update with smaller variance, obtained by averaging the noisy updates over a minibatch of samples. The use of updates with smaller variance in variance reduced Q-learning yields the algorithm its name. While both the approaches result in similar sample complexity guarantees, the local update scheme requires more frequent averaging across clients to ensure that the bias of the estimate, also commonly referred to as "client drift", is not too large. On the other hand, the minibatching approach does not encounter the problem of bias accumulation from local updates and hence can afford more infrequent averaging allowing Fed-DVR-Q to achieve optimal order of communication complexity.Compression. Fed-DVR-Q is the first algorithm in Federated Q-Learning to analyze and establish communication complexity at the bit level. All existing studies on Federated RL focus only on the frequency of communication and assume transmission of real numbers with infinite bit precision. On the other hand, the our analysis provides a more holistic view point of communication complexity and provides bounds at the bit level, which is of great practical significance. While some recent other studies [Wang et al., 2023] also consider quantization in Federated RL, their objective is to understand the impact of message size on convergence with no constraint on the frequency of communication, unlike the holistic viewpoint adopted in this work. 
conclusion and future directions: 
 We presented a complete characterization of the sample-communication trade-off for Federated Q-learning algorithms with intermittent communication. We showed that no Federated Q-learning algorithm with intermittent communication can achieve a linear speedup with respect to the number of agents if its number of communication rounds are sublinear in 1 1-γ . We also proposed a new Federated Q-learning algorithm called Fed-DVR-Q that uses variance reduction along with minibatching to achieve optimal-order sample and communication complexities. In particular, we showed that Fed-DVR-Q has a sample complexity of Õ( |S||A| M (1-γ) 3 ε 2 ), which is order-optimal in all salient problem parameters, and a communication complexity of Õ( 11-γ ) rounds and Õ( |S||A| 1-γ ) bits. The results in this work raise several interesting questions that are worth exploring. While we focus on the tabular setting in this work, it is of great interest to investigate to the trade-off in other settings where we use function approximation to model the Q ⋆ and V ⋆ functions. Moreover, it is interesting to explore the trade-off in the finite horizon setting, where there is no discount factor. Furthermore, it is also worthwhile to explore if the communication complexity can be further reduced by going beyond the class of intermittent communication algorithms. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The empirical studies require no specific compute resources can be easily completed on a regular laptop.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The paper is concerned with foundational research and is theoretical in nature with no direct societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper is theoretical is nature and does not involve release of data or code and hence poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: The paper does not use any existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We outline below the pseudocode of the REFINEESTIMATE routine described in Sec. 4.1.1. Send C ( T (m) L (Q) -Q; D, J) to the server 6: Receive 1 M M m=1 C ( T (m) L (Q) -Q; D, J)Compute Q m i-1 2 according to Eqn. (11) 14: Send C (Q m i-1 2 -Q i-1 ; D, J) to the server 15: Receive 1 M M m=1 C (Q m i -Q i-1 ; D, J)from the server and compute Q i according to Eqn. ( 12) 16:end for 17: end for 18: return Q IIn this section, we prove the main result of the paper, the lower bound on the communication complexity of federated Q-learning algorithms. At a high level, the proof consists of the following three steps.Introducing the "hard" MDP instance. The proof builds upon analyzing the behavior of a generic algorithm A outlined in Algorithm 1 over a particular instance of MDP. The particular choice of MDP is inspired by, and borrowed from, other lower bound proofs in the single-agent setting [Li et al., 2023] and helps highlight core issues that lie at the heart of the sample-communication complexity trade-off. Following Li et al. [2023] , the construction is first over a small state-action space that allows us to focus on a simpler problem before generalizing it to larger state-action spaces.Establishing the performance of intermittent communication algorithms. In the second step, we analyze the error of the iterates generated by an intermittent communication algorithm A . The analysis is inspired by the single-agent analysis in Li et al. [2023] , which highlights the underlying bias-variance trade-off. Through careful analysis of the algorithm dynamics in the federated setting, we uncover the impact of communication on the bias-variance trade-off and the resulting error of the iterates to obtain the lower bound on the communication complexity.Generalization to larger MDPs. As the last step, we generalize our construction of the "hard" instance to more general state-action space and extend our insights to obtain the statement of the theorem.We first introduce an MDP instance M h that we will use throughout the proof to establish the result. Note that this MDP is identical to the one considered in Li et al. [2023] to establish the lower bounds on the performance of single-agent Q-learning algorithm. It consists of four states S = {0, 1, 2, 3}. Let A s denote the action set associated with the state s. The probability transition kernel and the reward function of M h is given as follows:EQUATIONwhere the parameter p = 4γ -1 3γ . We have the following results about the optimal Q and V functions of this hard MDP instance. Lemma 1 ( [Li et al., 2023, Lemma 3] ). Consider the MDP M h constructed in Eqn. (14). We have,V ⋆ (0) = Q ⋆ (0, 1) = 0 V ⋆ (1) = Q ⋆ (1, 1) = Q ⋆ (1, 2) = V ⋆ (2) = Q ⋆ (2, 1) = 1 1 -γp = 3 4(1 -γ) V ⋆ (3) = Q ⋆ (3, 1) = 1 1 -γ .Throughout the next section of the proof, we focus on this MDP with four states and two actions. In Appendix B.4, we generalize the proof to larger state-action spaces.For convenience, we first define some notation that will be used throughout the proof.Useful relations of the learning rates. We consider two kinds of step size sequences that are commonly used in Q-learning -the constant step size schedule, i.e., η t = η for all t ∈ {1, 2, . . . , T } and the rescaled linear step size schedule, i.e., η t = 1 1+cη(1-γ)t , where c η > 0 is a universal constant that is independent of the problem parameters.We define the following quantities:EQUATIONwhere we take η 0 = 1 and use the convention throughout the proof that if a product operation does not have a valid index, we take the value of that product to be 1. For any integer 0 ≤ τ < t, we have the following relation, which will be proved at the end of this subsection for completeness:EQUATIONSimilarly, we also define,EQUATIONwhich satisfies the relationEQUATION)for any integer 0 ≤ τ < t. The claim follows immediately by plugging p = 0 in (16). Note that for constant step size, the sequence η(t)k is clearly increasing. For the rescaled linear step size, we have,EQUATIONk is an increasing sequence as long asEQUATIONk is also clearly increasing for the constant step size schedule. For the rescaled linear step size schedule, we have,η (t) k-1 η (t) k = η k η k-1 (1 -η k (1 -γp)) ≤ η k η k-1 (1 -η k ) ≤ 1, whenever c η ≤ 1 1-γ .The last bound follows from Eqn. ( 19).Proof of (16). We can show the claim using backward induction. For the base case, note that,(1 -γp)η (t) t + (1 -γp)η (t) t-1 = (1 -γp)η t + (1 -γp)η t-1 (1 -(1 -γp)η t ) = 1 -(1 -η t (1 -γp))(1 -η t-1 (1 -γp)) = 1 - t k=t-1 (1 -η k (1 -γp)),as required. Assume ( 16) is true for some τ . We have,(1 -γp) t k=τ η (t) k = (1 -γp)η t τ + (1 -γp) t k=τ +1 η (t) k = (1 -γp)η τ t k=τ +1 (1 -η k (1 -γp)) + 1 - t k=τ +1 (1 -η k (1 -γp)) = 1 - t k=τ (1 -η k (1 -γp)),thus completing the induction step. EQUATIONwhereP m t,b (s ′ |s, a) = 1{Z m t,b (s, a) = s ′ } for s ′ ∈ S.Preliminary relations of the iterates. We state some preliminary relations regarding the evolution of the Q-function and the value function across different agents that will be helpful for the analysis later.We begin with the state 0, where we have Q m t (0, 1) = V m t (0) = 0 for all agents m ∈ [M ] and t ∈ [T ]. This follows almost immediately from the fact that state 0 is an absorbing state with zero reward. Note thatEQUATION0) = 0 for all clients for some time instant t -1, by induction, we have,Q m t-1/2 (0, 1) = (1 -η t )Q m t-1 (0, 1) + η t (γV m t-1 (0)) = 0. Consequently, Q mt (0, 1) = 0 and V m t (0) = 0, for all agents m, irrespective of whether there is averaging.For state 3, the iterates satisfy the following relation:Q m t-1/2 (3, 1) = (1 -η t )Q m t-1 (3, 1) + η t (1 + γV m t-1 (3)) = (1 -η t )Q m t-1 (3, 1) + η t (1 + γQ m t-1 (3, 1)) = (1 -η t (1 -γ))Q m t-1 (3, 1) + η t ,where the second step follows by noting V m t (3) = Q m t (3, 1). Once again, one can note that averaging step does not affect the update rule implying that the following holds for all m ∈ [M ] and t ∈ [T ]:EQUATIONwhere the last step follows from Eqn. ( 16) with p = 1.Similarly, for state 1 and 2, we have,EQUATIONEQUATIONEQUATION)Since the averaging makes a difference in the update rule, we further analyze the update as required in later proofs.We first focus on establishing a bound on the number of communication rounds, i.e., CC round (A ) (where we drop the dependency with other parameters for notational simplicity), and then use this lower bound to establish the bound on the bit level communication complexity CC bit (A ).To establish the lower bound on CC round (A ) for any intermittent communication algorithm A , we analyze the convergence behavior of A on the MDP M h . We assume that the averaging step in line 6 of Algorithm 1 is carried out exactly. Since the use of compression only makes the problem harder, it is sufficient for us to consider the case where there is no loss of information in the averaging step for establishing a lower bound. Lastly, throughout the proof, without loss of generality we assume thatEQUATIONotherwise, the lower bound in Theorem 1 reduces to the trivial lower bound.We divide the proof into following three parts based on the choice of learning rates and batch sizes:1. Small learning rates: For constant learning rates, 0 ≤ η < 1 (1-γ)T and for rescaled linear learning rates, the constant c η satisfies c η ≥ log T .2. Large learning rates with small η T /(BM ): For constant learning rates, η ≥ 1 (1-γ)T and for rescaled linear learning rates, the constant c η satisfies 0 ≤ c η ≤ log T ≤ 1 1-γ (c.f. ( 25)). Additionally, the ratio η T BM satisfies η T BM ≤ 1-γ 100 . 3. Large learning rates with large η T /(BM ): We have the same condition on the learning rates as above. However, in this case the ratio η T BM satisfies η T BM > 1-γ 100 .We consider each of the cases separately in the following three subsections.In this subsection, we prove the lower bound for small learning rates, which follow from similar arguments in Li et al. [2023] .For this case, we focus on the dynamics of state 2. We claim that the same relation established in Li et al. [2023] continues to hold, which will be established momentarily:EQUATIONConsequently, for all m ∈ [M ], we haveEQUATION)To obtain lower bound onV ⋆ (2) -E[V m T (2)],we need to obtain a lower bound on η (T ) 0 , which from [Li et al., 2023, Eqn. (120) ] we have log(η(T ) 0 ) ≥ -1.5 T t=1 η(1 -γp) ≥ -2 T t=1 1 t log T ≥ -2 =⇒ η (T ) 0 ≥ e -2when T ≥ 16 for both choices of learning rates. On plugging this bound in ( 27), we obtain,EQUATIONholds for all m ∈ [M ], N ≥ 1 and M ≥ 2. Thus, it can be noted that the error rate ER(A ; N, M ) is bounded away from a constant value irrespective of the number of agents and the number of communication rounds. Thus, even with CC round = Ω(T ), we will not observe any collaborative gain if the step size is too small.Proof of (26). Recall that from (24), we have,Q m t-1/2 (2, 1) = (1 -η t )V m t-1 (2) + η t (1 + γ P m t (2|2, 1)V m t-1 (2)).Here, Q m t-1 (2, 1) = V m t-1 (2) as the second state has only a single action.• When t is not an averaging instant, we have,EQUATION)On taking expectation on both sides of the equation, we obtain,EQUATIONIn the second step, we used the fact thatEQUATIONOnce again, upon taking expectation we obtain,EQUATIONEqns. ( 30) and ( 32) together imply that for all t ∈ [T ],1EQUATIONOn unrolling the above recursion with V m 0 = 0 for all m ∈ [M ], we obtain the desired claim (26).B.3.2 Large learning rates with small η TIn this subsection, we prove the lower bound for case of large learning rates when the ratio η T BM is small. For the analysis in this part, we focus on the dynamics of state 1. Unless otherwise specified, throughout the section we implicitly assume that the state is 1.We further define a key parameter that will play a key role in the analysis:EQUATION)It can be noted that for constant step size sequence τ = 1 and for rescaled linear stepsize τ = T /3.Step 1: introducing an auxiliary sequence. We define an auxiliary sequence Q m t (a) for a ∈ {1, 2} and all t = 1, 2, . . . , T to aid our analysis, where we drop the dependency with state s = 1 for simplicity. The evolution of the sequenceQ m t is defined in Algorithm 4, where V m t = max a∈{1,2} Q m t (a).In other words, the iterates { Q m t } evolve exactly as the iterates of Algorithm 1 except for the fact that sequence { Q m t } is initialized at the optimal Q-function of the MDP. We would like to point out that we assume that the underlying stochasticity is also identical in the sense that the evolution of both Q m t and Q m t is governed by the same P m t matrices. The following lemma controls the error between the iterates Q m t and Q m t , allowing us to focus only on Q m t .Algorithm 4: Evolution of Q 1: Input : T, R, {η t } T t=1 , C = {t r } R r=1 , B 2: Set Q m 0 (a) ← Q ⋆ (1,Q m t (1, a) -Q m t (a) ≥ - 1 1 -γ t i=1 (1 -η i (1 -γ)).By Lemma 2, bounding the error of the sequence Q m t allows us to obtain a bound on the error of Q m t . To that effect, we define the following terms for any t ≤ T and all m ∈ [M ]:∆ m t (a) := Q m t (a) -Q ⋆ (1, a); a = 1, 2; ∆ m t,max = max a∈{1,2}∆ m t (a).In addition, we use ∆ t =1 M M m=1 ∆ m t to denote the error of the averaged iterate 1 , and similarly,EQUATIONWe first derive a basic recursion regarding ∆ m t (a). From the iterative update rule in Algorithm 4, we have,∆ m t (a) = (1 -η t )∆ m t-1 (a) + η t (1 + γ P m t (1|1, a) V m t-1 -Q ⋆ (1, a)) = (1 -η t )∆ m t-1 (a) + η t γ( P m t (1|1, a) V m t-1 -pV ⋆ (1)) = (1 -η t )∆ m t-1 (a) + η t γ(p( V m t-1 -V ⋆ (1)) + ( P m t (1|1, a) -p) V t-1 ) = (1 -η t )∆ m t-1 (a) + η t γ(p∆ m t-1,max + ( P m t (1|1, a) -p) V m t-1). Here in the last line, we used the following relation:∆ m t,max = max a∈{1,2} ( Q m t (a) -Q ⋆ (1, a)) = max a∈{1,2} Q m t (a) -V ⋆ (1) = V m t-1 -V ⋆ (1), as Q ⋆ (1, 1) = Q ⋆ (1, 2) = V ⋆ (1).Recursively unrolling the above expression, and using the expression (17), we obtain the following relation: for any t ′ < t when there is no averaging during the interval (t ′ , t)EQUATION)For any t ′ , t with t ′ < t, we define the notationEQUATIONEQUATIONEQUATIONNote that by definition, E[ξ m t ′ ,t (a)] = 0 for a ∈ {1, 2} and all m, t ′ and t. Plugging them into the previous expression leads to the simplified expression∆ m t (a) = φ t ′ ,t ∆ m t ′ (a) + t k=t ′ +1 η (t) k γp∆ m k-1,max + ξ m t ′ ,t (a).We specifically choose t ′ and t to be the consecutive averaging instants to analyze the behaviour of ∆ m t across two averaging instants. Consequently, we can rewrite the above equation asEQUATIONFurthermore, after averaging, we obtain,EQUATIONStep 2: deriving a recursive bound for E[∆ t,max ]. Bounding (40), we obtain,EQUATIONwhere in the first step we used the fact thatEQUATION)On taking expectation, we obtain,EQUATIONEQUATIONSimilarly, using ( 41) and ( 43) we can write,EQUATION)On combining (44b) and (45b), we obtain,EQUATION)In order to simplify (46), we make use of the following lemmas. Lemma 3. Let t ′ < t be two consecutive averaging instants. Then for all m ∈ [M ],E[∆ m t,max ] -E[ξ m t ′ ,t,max ] ≥ t k=t ′ +1 (1 -η k (1 -γp)) E[∆ t ′ ,max ] + E[ξ m t ′ ,t,max ] t k=t ′ +1 η (t) k -1 + -φ t ′ ,t E[|∆ t ′ (1) -∆ t ′ (2)|],where [x] + = max{x, 0}. Lemma 4. For all consecutive averaging instants t ′ , t satisfying t -max{t ′ , τ } ≥ 1/η τ and all m ∈ [M ], we have,E[ξ m t ′ ,t,max ] ≥ 1 240 log 180B η T (1-γ) • ν ν + 1 , E max 1 M M m=1 ξ m t ′ ,t (1), 1 M M m=1 ξ m t ′ ,t (2) ≥ 1 240 log 180BM η T (1-γ) • ν ν + √ M ,where ν := 20η T B(1γ) .Lemma 5. For all t ∈ {t r } R r=1 , we haveE[|∆ t (1) -∆ t (2)|] ≤ 8η T 3BM (1 -γ).Thus, on combining the results from Lemmas 3, 4, and 5 and plugging them into (46), we obtain the following relation for t, t ′ ≥ τ :EQUATIONEQUATIONwhere we used the relation φ t ′ ,t ≤ (1η T ) t-t ′ , as well as the value of ν as defined in Lemma 4 along with the factEQUATIONfor all t, t ′ ≥ τ such that tt ′ ≥ 8/η τ .Proof of (48). We have,EQUATION)To show (48), it is sufficient to show thatEQUATION)Since γ ≥ 5/6, 1γp ≤ 2/9. For x ≤ 2/9, the function f (x) = 1-e -8x 3x ≥ 8/7, proving the claim.Step 3: lower bounding E[∆ T,max ]. We are now interested in evaluating E[∆ T,max ] based on the recursion (47). To this effect, we introduce some notation to simplify the presentation. LetEQUATIONFor r = R τ , . . . , R, we define the following terms:x r := E[∆ tr,max ], α r := (1 -η τ (1 -γp)) tr-tr-1 , β r := (1 -η T ) tr-tr-1 , I r := {r ≥ r ′ > R τ : t r ′ -t r ′ -1 ≥ 8/η τ }, C 1 := 1 5760 log 180B η T (1-γ) (1 -γp) • ν ν + 1 , C 2 := 32η T 3BM (1 -γ) , C 3 := 1 240 log 180BM η T (1-γ) • ν ν + √ M .With these notations in place, the recursion in (47) can be rewritten asEQUATIONfor all r ≥ R τ . We claim that x r satisfies the following relation for all r ≥ R τ + 1 (whose proof is deferred to the end of this step):EQUATIONwhere we recall that if there is no valid index for a product, its value is taken to be 1.Invoking (53) for r = R and using the relation x Rτ -1 ≥ 0, we obtain,EQUATIONwhere we used the factEQUATION)Consequently,EQUATION)Note that T 1 satisfies the following boundEQUATION)We split the remainder of the analysis based on the step size schedule.• For the constant step size schedule, i.e., η t = η ≥ 1(1-γ)T , we have, R τ = 0, with τ = 0 and t 0 = 0 (as all agents start at the same point). If R ≤ 1 96000(1-γ) log( 180B η(1-γ) ), then, ( 55), ( 56) and ( 57) yield the following relations:T 1 ≤ 8R η ≤ T 12000 log(180N ) , i / ∈I R α i ≥ 1 -η(1 -γp) • T 1 ≥ 1 - 32R(1 -γ) 3 ≥ 1 - 1 9000 log(180N ) , 1 - i∈I R α i ≥ 1 -exp (-η(1 -γp) (T -T 1 )) ≥ 1 -exp - 4 3 1 - 1 9000 log(180N ).On plugging the above relations into (54), we obtainEQUATIONwhere recall that ν := 20η 3B(1γ). Consider the function fEQUATIONThe proof of the above claim is deferred to the end of the section. In light of the above claim, we have,EQUATIONwhere we used the fact that M ≥ 2,√ x log(1/x) is an increasing function and the relation ν M = 20η 3BM (1 -γ) ≤ 1 15 ≤ 1.• Next, we consider the rescaled linear step size schedule, where τ = T /3 (cf. ( 34)). To begin, we assume t Rτ ≤ max{ 3T 4 , T -1 6ητ (1-γp) }. It is straightforward to note that max 3T 4 , T - 1 6η τ (1 -γp) = 3T 4 if c η ≥ 3 T - 1 6ητ (1-γp) if c η < 3. If R ≤ 1 384000(1-γ) log 180B η T (1-γ) •(5+cη)then, ( 55), ( 56) and ( 57) yield the following relations:T 1 ≤ 8R η τ , i / ∈I R α i ≥ 1 -η τ (1 -γp) • T 1 ≥ 1 - 32R(1 -γ) 3 ≥ 1 - 1 36000.For c η ≥ 3, we have,1 - i∈I R α i ≥ 1 -exp (-η τ (1 -γp) (T -t Rτ -T 1 )) ≥ 1 -exp - (1 -γ)T (3 + c η (1 -γ)T ) + 32R(1 -γ) 3 ≥ 1 2(3 + c η ),where we used T ≥ 1 1-γ in the second step. Similarly, for c η < 3, we have,1 - i∈I R α i ≥ 1 -exp (-η τ (1 -γp) (T -t Rτ -T 1 )) ≥ 1 -exp - 1 6 + 32R(1 -γ) 3 ≥ 1 10 .On plugging the above relations into (54), we obtainEQUATIONwhere we again used the facts that M ≥ 2, c η ≤ log N ,√ x log(1/x) is an increasing function and the relation ν M = 20η T 3BM (1 -γ) ≤ 1.• Last but not least, let us consider the rescaled linear step size schedule case when t Rτ > max{ 3T 4 , T -1 6ητ (1-γp) }. The condition implies that the time between the communication rounds R τ -1 and R τ is at leastEQUATIONUsing the above relation along with (53), we can conclude thatEQUATION)In the above relation, we used the trivial bounds C 1 , C 3 ≥ 0 and a crude bound on the term corresponding to C 2 , similar to (54). Let us first consider the case of c η ≥ 3. We have,1 -(1 -η τ (1 -γp)) T0 ≥ 1 -exp (-η τ (1 -γp)5T /12) ≥ 1 -exp - 5(1 -γ)T 3(3 + c η (1 -γ)T ) ≥ 1 3 + c η , (1 -η τ (1 -γp)) T -t Rτ ≥ 1 -η τ (1 -γp) T 4 ≥ 1 - (1 -γ)T (3 + c η (1 -γ)T ) ≥ 1 - 1 c η ≥ 2 3 .Similarly, for c η < 3, we have,1 -(1 -η τ (1 -γp)) T0 ≥ 1 -exp -η τ (1 -γp) 2T 3 + 1 6 ≥ 1 -exp - 8(1 -γ)T 3(3 + c η (1 -γ)T ) + 1 6 ≥ 1 -e -5/18 , (1 -η τ (1 -γp)) T -t Rτ ≥ 1 - η τ (1 -γp) 6η τ (1 -γp) ≥ 5 6 .The above relations implies that (1-η τ (1 -γp)) T -t Rτ (1 -(1 -η τ (1 -γp)) T0 ) ≥ cfor some constant c, which only depends on c η . On plugging this into (63), we obtain a relation that is identical to that in (54) up to leading constants. Thus, by using a similar sequence of argument as used to obtain (61), we arrive at the same conclusion as for the case of t Rτ ≤ max{ 3T 4 , T -1 6ητ (1-γp) }.Step 4: finishing up the proof. Thus, ( 60), ( 61) along with the above conclusion together imply that there exists a numerical constant c 0 > 0 such thatEQUATIONThe above equation along with Lemma 2 impliesE[|V m T -V ⋆ (1)|] ≥ c 0 log 3 N • min 1 1 -γ , 1 (1 -γ) 4 N - 1 1 -γ T i=1 (1 -η i (1 -γ)). (65)On the other hand, from (21) we know thatEQUATIONHence,EQUATIONwhere the third step follows from ( 65) and ( 66) and the fourth step uses max{a, b} ≥ (a + b)/2.Thus, from ( 28) and ( 67) we can conclude that wheneverCC round = O 1 (1-γ) log 2 N , ER(A ; N, M ) = Ω 1 log 3 N √ Nfor all values of M ≥ 2. In other words, for any algorithm to achieve any collaborative gain, its communication complexity should satisfy CC round = Ω 1 (1-γ) log 2 N , as required.Proof of (53). We now return to establish (53) using induction. For the base case, (52) yieldsx Rτ +1 ≥ α Rτ +1 x Rτ -β Rτ +1 C 2 + C 3 1{R τ + 1 ∈ I Rτ +1 } + (1 -α Rτ +1 )C 1 1{R τ + 1 ∈ I Rτ +1 }.(68) Note that this is identical to the expression in (53) for r = R τ + 1 as  i / ∈I Rτ +1 α i     1 - i∈I Rτ +1 α i   = (1 -α Rτ +1 )1{R τ + 1 ∈ I Rτ +1 }based on the adopted convention for products with no valid indices. For the induction step, assume (53) holds for some r ≥ R τ + 1. On combining ( 52) and ( 53), we obtain,EQUATIONEQUATIONOn the other hand, if (r + 1) ∈ I r+1 , then i /∈Ir α i = i /∈Ir+1 α i . Consequently, we have,EQUATIONCombining ( 69), ( 70) and ( 71) proves the claim.Proof of (59). To establish this result, we separately consider the cases x ≤ 1 and x ≥ 1.• When x ≤ 1, we haveEQUATIONwhere in the last step, we used the relation M ≥ 2.• Let us now consider the case x ≥ 1. The second derivative of f is given by f ′′ (x) = -1 2(x+1) 3 . Clearly, for all x ≥ 1, f ′′ < 0 implying that f is a concave function. It is well-known that a continuous, bounded, concave function achieves its minimum values over a compact interval at the end points of the interval (Bauer's minimum principle). For all M ≥ 2, we have,f (1) = 1 2 - 1 5 √ M ≥ 7 20 ; f ( √ M ) = √ M √ M + 1 - 1 5 ≥ 7 20 .Consequently, we can conclude that for allEQUATIONCombining ( 72) and ( 73) proves the claim.In order to bound the error in this scenario, note that η T BM controls the variance of the stochastic updates in the fixed point iteration. Thus, when η T BM is large, the variance of the iterates is large, resulting in a large error. To demonstrate this effect, we focus on the dynamics of state 2. This part of the proof is similar to the large learning rate case of Li et al. [2023] . For all t ∈ [T ], define:EQUATIONThus, from (33), we know that E[V t (2)] obeys the following recursion:E[V t (2)] = (1 -η t (1 -γp))E[V t-1 (2)] + η t .Upon unrolling the recursion, we obtain,E[V T (2)] = T k=t+1 (1 -η k (1 -γp)) E[V t (2)] + T k=t+1 η (T ) k .Thus, the above relation along with ( 16) and the value of V ⋆ (2) yields us,EQUATIONSimilar to Li et al. [2023] , we defineEQUATION) Similarly, if E[(V T -1 ) 2 ] < 1 4(1-γ) 2 , it implies E[V T -1 ] < 1 2(1-γ). Using (33), we have,E[V T (2)] = (1 -η T (1 -γp))E[V T -1 (2)] + η T ≤ E[V T -1 (2)] + 1 < 1 2(1 -γ) + 1 6(1 -γ) = 2 3(1 -γ) .Consequently,EQUATION)For the case when τ ′ exists, we divide the proof into two cases.• We first consider the case when the learning rates satisfy:EQUATION)The analysis for this case is identical to that considered in Li et al. [2023] . We explicitly write the steps for completeness. Specifically,EQUATIONwhere the first line follows from (75), the second line from the condition on step sizes and the third line from the definition of τ ′ . • We now consider the other case where,EQUATION)Using [Li et al., 2023, Eqn.(134) ], for any t ′ < t and all agents m, we have the relationV m t (2) = 1 1 -γp - t k=t ′ +1 (1 -η k (1 -γp)) 1 1 -γp -V m t ′ (2) + k=t ′ +1 η (t) k γ( P m k (2|2) -p)V m k-1 (2).The above equation is directly obtained by unrolling the recursion in (24) along with noting that Q t (2, 1) = V t (2) for all t. Consequently, we have,EQUATION) Let {F t } T t=0 be a filtration such that F t is the σ-algebra corre- sponding to {{ P m s (2|2)} M m=1 } t s=1 . It is straightforward to note that 1 M M m=1 η (T ) k γ( P m k (2|2) -p)V m k-1 (2)k is a martingale sequence adapted to the filtration F k . Thus, using the result from [Li et al., 2023, Eqn.(139) ], we can conclude thatEQUATION)We have,EQUATION)where the first line follows from that fact that variance of sum of i.i.d. random variables is the sum of their variances, the second line from variance of Binomial random variable and the third line from Jensen's inequality. Thus, ( 82) and ( 83) together yield,EQUATION)where the second line follows from the definition of τ ′ . We focus on bounding the third term in the above relation. We have,EQUATION)where the second line follows from monotonicity of η t and the numerical constant c ′ in the fifth step is given by the following claim whose proof is deferred to the end of the section:1 -(1 -η τ (1 -γp)) 2(T -max{τ ′ ,τ }-1) ≥ 1 -e -8/9for constant step sizes,1 -exp - 8 3 max{1,cη}for linearly rescaled step sizes .(86) Thus, ( 84) and ( 85) together implyEQUATION)where the last inequality follows from the bound on η T BM .Thus, for all N ≥ 1, we have,E[(V ⋆ (2) -V T (2)) 2 ] = E[(V ⋆ (2) -E[V T (2)]) 2 ] + Var(V T (2)) ≥ c ′′ (1 -γ)N ,for some numerical constant c ′′ . Similar to the small learning rate case, the error rate is bounded away from a constant value irrespective of the number of agents and the number of communication rounds. Thus, even with CC round = Ω(T ), we will not observe any collaborative gain in this scenario.Proof of (86). To establish the claim, we consider two cases:• τ ′ ≥ τ : Under this case, we have,EQUATION)where the last inequality follows from (80).• τ ≥ τ ′ : For this case, we haveEQUATION)For the constant stepsize schedule, we have,EQUATION)For linearly rescaled stepsize schedule, we have,exp - 2T η τ (1 -γp) 3 ≤ exp - 2T 3 • 1 1 + c η (1 -γ)T /3 • 4(1 -γ) 3 = exp - 8 3 max{1, c η } (91)On combining ( 88), ( 89), ( 90) and ( 91), we arrive at the claim.We now elaborate on how we can extend the result to general state-action spaces along with the obtaining the lower bound on the bit level communication complexity. For the general case, we instead consider the following MDP. For the first four states {0, 1, 2, 3}, the probability transition kernel and reward function are given as follows.A 0 = {1} P (0|0, 1) = 1 r(0, 1) = 0, (92a)EQUATIONwhere the parameter p = 4γ -1 3γ . The overall MDP is obtained by creating |S|/4 copies of the above MDP for all sets of the form {4r, 4r +1, 4r +2, 4r +3} for r ≤ |S|/4-1. It is straightforward to note that the lower bound on the number of communication rounds immediately transfers to the general case as well. Moreover, note that the bound on CC round implies the boundCC bit = Ω 1 (1-γ) log 2 Nas every communication entails sending Ω(1) bits.To obtain the general lower bound on bit level communication complexity, note that we can carry out the analysis in the previous section for all |A|/2 pairs of actions in state 1 corresponding to the set of states {0, 1, 2, 3}. Moreover, the algorithm A , needs to ensure that the error is low across all the |A|/2 pairs. Since the errors are independent across all these pairs, each of them require Ω 1 (1-γ) log 2 N bits of information to be transmitted during the learning horizon leading to a lower bound of Ω(1-γ) log 2 N . Note that since we require a low ℓ ∞ error, A needs to ensure that the error is low across all the pairs, resulting in a communication cost linearly growing with |A|. Upon repeating the argument across all |S|/4 copies of the MDP, we arrive at the lower bound ofCC bit = Ω |S||A| (1-γ) log 2 N .Note that a similar relationship is also derived in Li et al. [2023] , but needing to take care of the averaging over multiple agents, we present the entire arguments for completeness. We prove the claim using an induction over t. It is straightforward to note that the claim is true for t = 0 and all agents m ∈ {1, 2, . . . , M }. For the inductive step, we assume that the claim holds for t -1 for all clients. Using the induction hypothesis, we have the following relation between V m t-1 (1) and V m t-1 :EQUATION)For t ∈ {t r } R r=1 and a ∈ {1, 2}, we have,EQUATION)where the last step follows using the same set of arguments as used in (94). The inductive step follows from ( 94) and (95).In order to bound the term E[∆ m t,max ] -E[ξ m t ′ ,t,max ], we make use of the relation in ( 44a), which we recallE[∆ m t,max ] ≥ φ t ′ ,t E[∆ t ′ ,max ] + t k=t ′ +1 η (t) k γpE[∆ m k-1,max ] + E[ξ m t ′ ,t,max ] -φ t ′ ,t E[|∆ t ′ (1) -∆ t ′ (2)|].• To aid the analysis, we consider the following recursive relation for any fixed agent m:EQUATION)Upon unrolling the recursion, we obtain,EQUATION)Initializing 97) and plugging this into (44a), we havey t ′ = E[∆ t ′ ,max ] in (E[∆ m t,max ] ≥ y t -φ t ′ ,t E[|∆ t ′ (1) -∆ t ′ (2)|],where we usedt k=t ′ +1 η (t)k ≤ 1 (cf. ( 18)). We now further simply the expression of y t . By rewriting (96) asy t = (1 -η t (1 -γp))y t-1 + η t E[ξ m t ′ ,t,max ],it is straight forward to note that y t is given asEQUATION)Consequently, we have,EQUATION• We can consider a slightly different recursive sequence defined asEQUATION)Using a similar sequence of arguments as outlined in ( 96)-( 98), we can conclude that ifEQUATIONOn combining ( 99) and ( 101), we arrive at the claim.We begin with bounding the first term E[ξ m t ′ ,t,max ]; the second bound follows in an almost identical derivation.Step 1: applying Freedman's inequality. Using the relation max{a, b} = a+b+|a-b| 2 , we can rewrite E[ξ m t ′ ,t,max ] asEQUATIONwhere we used the definition in ( 38) and the fact thatEQUATIONEQUATIONwhere for all1 ≤ l ≤ L z l := γ B (P m k(l),b(l) (1|1, 1) -P m k(l),b(l) (1|1, 2)) V m k(l)-1 with k(l) := ⌊l/B⌋ + t ′ + 1; b(l) = ((l -1) mod B) + 1; L = (t -t ′ )B. Let {F l } L l=1 be a filtration such that F l is the σ-algebra corresponding to {P m k(j),b(j) (1|1, 1), P m k(j),b(j) (1|1, 2)} l j=1 .It is straightforward to note that {z l } L l=1 is a martingale sequence adapted to the filtration {F } L l=1 . We will use the Freedman's inequality [Freedman, 1975 , Li et al., 2023] to obtain a high probability bound on |ζ m t ′ ,t |.• To that effect, note thatEQUATIONwhere the second step follows from the boundsEQUATIONUsing the above bounds ( 104) and ( 105) along with Freedman's inequality yield thatEQUATIONSettingδ 0 = (1-γ) 2 2 • E[|ζ m t ′ ,t | 2 ], with probability at least 1δ 0 , it holdsEQUATIONConsequently, plugging this back to (102), we obtainEQUATIONHere, the penultimate step used the fact that|ζ m t ′ ,t | ≤ t k=t ′ +1 η (t) k (1 -γ) ≤ 1 (1 -γ), and the last step used the definition of δ 0 . Thus, it is sufficient to obtain a lower bound onE[|ζ m t ′ ,t | 2 ] in order obtain a lower bound for E[ξ m t ′ ,t,max ].Step 2: lower boundingE[|ζ m t ′ ,t | 2 ].To proceed, we introduce the following lemma pertaining to lower bounding V m t that will be useful later. Lemma 6. For all time instants t ∈ [T ] and all agent m ∈ [M ]:E V m t 2 ≥ 1 2(1 -γ) 2 .We have,EQUATIONwhere the third line follows from Lemma 6 and the fourth line uses γ ≥ 5/6.Step 3: finishing up. We finish up the proof by boundingEQUATIONwhere (i) follows from the monotonicity of η k . Plugging (110) into the expressions of D (cf. ( 107)) we haveD = 8 log(2/δ 0 ) 3B(1 -γ) t k=t ′ +1 η (t) k 2 + 4η t log(2/δ 0 ) 3B(1 -γ) ≤ 9 2 E[|ζ m t ′ ,t | 2 ] • 8 log(2/δ 0 ) 3 1 B(1 -γ) t k=t ′ +1 η (t) k 2 -1/2 + 60 • E[|ζ m t ′ ,t | 2 ] • log(2/δ 0 ) ≤ 3E[|ζ m t ′ ,t | 2 ] • log(2/δ 0 ) 60B(1 -γ) η t + 20 ≤ 60E[|ζ m t ′ ,t | 2 ] • log(2/δ 0 ) 3B(1 -γ) 20η T + 1 ,where the second line follows from ( 109) and ( 110), and the third line follows from (110). On combining the above bound with (108), we obtain,EQUATIONwhere ν := 20η T 3B(1γ). Note that we have,δ 0 = (1 -γ) 2 2 • E[|ζ m t ′ ,t | 2 ] ≥ (1 -γ) 9B • t k=t ′ +1 η (t) k 2 ≥ η T (1 -γ) 90B .Combining the above bound with (111) yields us the required bound.Step 4: repeating the argument for the second claim. We note that second claim in the theorem, i.e., the lower bound onEQUATION) follows through an identical series of arguments where the bounds in Eqns. ( 104) and ( 105) contain an additional factor of M in the denominator (effectively replacing B with BM ), which is carried through in all the following steps.Using Eqns. ( 41) and (38), we can write∆ t (1) -∆ t (2) = t k=t ′ +1 (1 -η k ) (∆ t ′ (1) -∆ t ′ (2)) + 1 M M m=1 t k=t ′ +1 η k t i=k+1 (1 -η i ) γ( P m k (1|1, 1) -P m k (1|1, 2)) V m k-1 .Upon unrolling the recursion, we obtain,∆ t (1) -∆ t (2) = t k=1 M m=1 η k t i=k+1 (1 -η i ) γ M ( P m k (1|1, 1) -P m k (1|1, 2)) V m k-1 .If we define a filtration F k as the σ-algebra corresponding to { P 1 l (1|1, 1), P 1 l (1|1, 2), . . . , P M l (1|1, 1), P M l (1|1, 2)} k l=1 , then it is straightforward to note that {∆ t (1) -∆ t (2)} t is a martingale sequence adapted to the filtration {F t } t . Using Jensen's inequality, we know that if {Z t } t is a martingale adapted to a filtration {G t } t , then for a convex functionEQUATION)We use the following observation about a martingale sequence {X i } t i=1 adapted to a filtration {G i } t i=1 to evaluate the above expression. We have,EQUATIONwhere the third step uses the facts that t-1 i=1 X i is G t-1 measure and E[X t |G t-1 ] = 0 and fourth step is obtained by recursively applying second and third steps. Using the relation in Eqn. (113) in Eqn. (112), we obtain,EQUATION)Let us focus on the term involving the step sizes. We separately consider the scenario for constant step sizes and linearly rescaled step sizes. For constant step sizes, we have,T k=1 η (T ) k 2 = T k=1 η k T i=k+1 (1 -η i ) 2 = T k=1 η 2 (1 -η) 2(T -k) ≤ η 2 1 -(1 -η) 2 ≤ η. (115)Similarly, for linearly rescaled step sizes, we have,EQUATIONwhere the second step uses c η ≤ log N ≤ 1 1-γ and the fact that η(T ) kis increasing in k in this regime. (See Eqn. ( 19)) and fifth step uses xe -4x/3 ≤ 3/4e. On plugging results from Eqns. ( 115) and ( 116) into Eqn. ( 114) along with the value of p, we obtain,EQUATIONas required.For the proof, we fix an agent m. In order to obtain the required lower bound on V m t , we define an auxiliary sequence Q m t that evolves as described in Algorithm 5. Essentially, Q m t evolves in a manner almost identical to Q m t except for the fact that there is only one action and hence there is no maximization step in the update rule.Algorithm 5: Evolution of Q1: r ← 1, Q m 0 = Q ⋆ (1, 1) for all m ∈ {1, 2, . . . , M } 2: for t = 1, 2, . . . , T do 3:for m = 1, 2, . . . , M do 4:Q m t-1/2 ← (1 -η t )Q m t-1 (a) + η t (1 + P m t (1|1, 1)Q m t-1 ) 5:Compute Q m t according to Eqn. (8) 6:end for 7: end forIt is straightforward to note that Q m t (1) ≥ Q m t, which can be shown using induction. From the initialization, it follows that Q m 0 (1) ≥ Q m 0 . Assuming the relation holds for t -1, we have,Q m t-1/2 (1) = (1 -η t ) Q m t-1 (1) + η t (1 + γ P m t (1|1, 1) V m t-1 ) ≥ (1 -η t ) Q m t-1 (1) + η t (1 + γ P m t (1|1, 1) Q m t-1 (1)) ≥ (1 -η t )Q m t-1 + η t (1 + γ P m t (1|1, 1)Q m t-1 ) = Q m t-1/2 . Since Q m t and Q m tfollow the same averaging schedule, it immediately follows from the above relation thatQ m t (1) ≥ Q m t . Since V m t ≥ Q m t (1) ≥ Q m t, we will use the sequence Q m t to establish the required lower bound on V m t . We claim that for all time instants t and all agents m,EQUATIONAssuming ( 118) holds, we haveE[( V m t ) 2 ] ≥ E[ V m t ] 2 ≥ E[Q m t ] 2 ≥ 1 1 -γp 2 ≥ 1 2(1 -γ) 2 ,as required. In the above expression, the first inequality follows from Jensen's inequality, the second from the relation V m t ≥ Q m t ≥ 0 and the third from (118). We now move now to prove the claim (118) using induction. For the base case, E[Qm 0 ] = 1 1-γp holds by choice of initialization. Assume that E[Q m t-1 ] = 11-γp holds for some t -1 for all m.• If t is not an averaging instant, then for any client m,EQUATION)The third line follows from the independence of P m t (1|1, 1) and Q m t-1 and the fourth line uses the inductive hypothesis. • If t is an averaging instant, then for all clients m,Q m t = (1 -η t ) M M j=1 Q j t-1 + η t 1 M M j=1(1 + γ P j t (1|1, 1)EQUATIONwhere we again make use of independence and the inductive hypothesis.Thus, ( 119) and ( 120) taken together complete the inductive step.In this section, we prove Theorem 2 that outlines the performance guarantees of Fed-DVR-Q. There are two main parts of the proof. The first part deals with establishing that for the given choice of parameters described in Section 4.1.3, the output of the algorithm is an ε-optimal estimate of Q ⋆ with probability 1δ. The second part deals with deriving the bounds on the sample and communication complexity based on the choice of prescribed parameters. We begin with the second part, which is easier of the two.Establishing the communication complexity. We begin with bounding CC round . From the description of Fed-DVR-Q, it is straightforward to note that each epoch, i.e., each call to the REFINEES-TIMATE routine, involves I + 1 rounds of communication, one for estimating T Q and the remaining ones during the iterative updates of the Q-function. Since there are a total of K epochs,CC round (Fed-DVR-Q; ε, M, δ) ≤ (I + 1)K ≤ 16 η(1 -γ) log 2 1 (1 -γ)ε ,where the second bound follows from the prescribed choice of parameters in Sec. 4.1.3. Similarly, since the quantization step is designed to compress each coordinate into J bits, each message transmitted by an agent has a size of no more than J • |S||A| bits. Consequently,CC bit (Fed-DVR-Q; ε, M, δ) ≤ J • |S||A| • CC round (Fed-DVR-Q; ε, M, δ) ≤ 32|S|A| η(1 -γ) log 2 1 (1 -γ)ε log 2 70 η(1 -γ) 4 M log 8KI|S||A| δ ,where once again in the second step we plugged in the choice of J from Sec. 4.1.3.Lemma 7. Let δ ∈ (0, 1). Consider the REFINEESTIMATE routine described in Algorithm 3 and let Q ⋆ H denote the fixed point of the operator H defined in (122) for some fixed Q. Then the iterates generated by REFINEESTIMATE Q I satisfy∥Q I -Q ⋆ H ∥ ∞ ≤ 1 6 ∥Q -Q ⋆ ∥ ∞ + ∥Q ⋆ -Q ⋆ H ∥ ∞ + D 70with probability 1 -δ 2K . Lemma 8. Consider the REFINEESTIMATE routine described in Alg. 3 and let Q ⋆ H denote the fixed point of the operator H defined in Eqn. (122) for a fixed Q. The following relation holds with probability 1 -δ 2K :∥Q ⋆ H -Q ⋆ ∥ ∞ ≤ ∥Q -Q ⋆ ∥ ∞ • 16κ ′ L(1 -γ) 2 + 64κ ′ L(1 -γ) 3 + 2κ ′ √ 2 3L(1 -γ) 2 + D 70 , whenever L ≥ 32κ ′ , where κ ′ = log 12K|S||A| δ .Step 2: establishing the linear contraction. We now leverage the above lemmas to establish the desired contraction in (121). Instantiating the operator (122) at each k-th epoch by setting -1) and L := L k , we defineQ := Q (kEQUATIONwhose fixed point is denoted as Q ⋆ H k . Using the results from Lemmas 7 and 8 with D := D k and H = H k , we obtainEQUATIONholds with probability 1 -δ K . Here, we invoke Lemma 7 in the second step and Lemma 8 in the fourth step corresponding to the REFINEESTIMATE routine during the k-th epoch. In the last step, we used the fact thatL k (1-γ) 2 κ ′ ≥ 1.We now use induction along with the recursive relation in (125) to establish the required claim (121). Let us first consider the case 0 ≤ k ≤ K 0 . The base case, ∥Q (0) -Q ⋆ ∥ ∞ ≤ 1 1-γ , holds by definition. Let us assume the relation holds for k -1. Then, from (125) and choice of L k (Sec. 4.1.3), we haveEQUATION)Now we move to the second case, for k > K 0 . From (125) and of L k (Sec. 4.1.3), we haveEQUATION)By a union bound argument, we can conclude that the relation∥Q (k) -Q ⋆ ∥ ∞ ≤ 2 -k1-γ holds for all k ≤ K with probability at least 1δ.Step 3: confirm the compressor bound. The only thing left to verify is that the inputs to the compressor are always bounded by D k during the k-th epoch, for all 1 ≤ k ≤ K. The following lemma provides a bound on the input to the compressor during any run of the REFINEESTIMATE routine. Lemma 9. Consider the REFINEESTIMATE routine described in Algorithm 3 with some for some fixed Q. For all i ≤ I and all agents m, the following bound holds with probability 1 -δ 2K :∥Q m i-1 2 -Q i-1 ∥ ∞ ≤ η∥Q -Q ⋆ H ∥ ∞ 7 6 • (1 + γ) + 2γ + ηD(1 + γ) 70 .For the k-th epoch, it follows thatη∥Q (k-1) -Q ⋆ H k ∥ ∞ 7 6 • (1 + γ) + 2γ + ηD k (1 + γ) 70 ≤ 13 3 ∥Q (k-1) -Q ⋆ ∥ ∞ + ∥Q ⋆ -Q ⋆ H k ∥ ∞ + D k (1 + γ) 70 ≤ 13 3 • 15 14 • ∥Q (k-1) -Q ⋆ ∥ ∞ + 2D k 70 ≤ 195 42 + 16 70 • 2 -(k-1) 1 -γ ≤ 8 • 2 -(k-1) 1 -γ := D k .In the third step, we used the same sequence of arguments as used in ( 126) and ( 127) and, in the fourth step, we used the bound on Let us begin with analyzing the evolution of the sequence {Q i } I i=1 during a run of the REFINEESTI-MATE routine. The sequence {Q i } I i=1 satisfies the following recursion:EQUATIONEQUATION)In the above expression, ζ m i denotes the quantization noise introduced at agent m in the i-th update. Subtracting Q ⋆ H from both sides of (128), we obtainQ i -Q ⋆ H = (1 -η)(Q i-1 -Q ⋆ H ) + η M M m=1 H (m) i (Q i-1 ) -Q ⋆ H + ζ i = (1 -η)(Q i-1 -Q ⋆ H ) + η M M m=1 H (m) i (Q i-1 ) -H (m) i (Q ⋆ H ) + η M M m=1 H (m) i (Q ⋆ H ) -H(Q ⋆ H ) + ζ i . (129)Consequently,EQUATIONwhich we shall proceed to bound each term separately.• Regarding the second term, it follows thatEQUATIONwhich holds for all Q since T (m) i is a γ-contractive operator. • Regarding the third term, notice thatEQUATIONThus, each of its coordinate is a (2γ∥Q -Q ⋆ H ∥ ∞ ) 2 -sub-Gaussian vector. Applying the tail bounds for a maximum of sub-Gaussian random variables [Vershynin, 2018] , we obtain thatEQUATIONholds with probability at least 1 -δ 4KI . • Turning to the last term, by the construction of the compression routine described in Section 4.1.2, it is straightforward to note that ζ m i is a zero-mean random vector whose coordinates are independent, D 2 • 4 -J -sub-Gaussian random variables. Thus, ζ i is also a zero-mean random vector whose coordinates are independent, D 2 M •4 J -sub-Gaussian random variables. Hence, we can similarly conclude thatEQUATIONholds with probability at least 1 -δ 4KI .Combining the above bounds into (130), and introducing the short-hand notation κ := log 8KI|S||A| δ , we obtain with probability at least 1 -δ 2KI ,∥Q i -Q ⋆ H ∥ ∞ ≤ (1 -η(1 -γ))∥Q i-1 -Q ⋆ H ∥ ∞ + 2ηγ∥Q -Q ⋆ H ∥ ∞ • 2κ M B + D • 2 -J • 2κ M .Unrolling the above recursion over i = 1, . . . , I yields the following relation, which holds with probability at least 1 -δ 2K :EQUATIONHere, the fourth step is obtained by plugging in the prescribed values of B, I and J in Sec. 4.1.3.Intuitively, the error∥Q ⋆ H -Q ⋆ ∥ ∞ depends on the error term T L (Q) -T (Q).If the latter is small, then H(Q) is close to T (Q) and consequently so are Q ⋆ H and Q ⋆ . Thus, we begin with bounding the term T L (Q) -T (Q). We have,EQUATIONwhere once again ζ(m)L := T (m) L (Q) -Q -C T (m) L(Q) -Q denotes the quantization error at agent m. Similar to the arguments of ( 133) and ( 134), we can conclude that each of the following relations hold with probability at least 1 -δ 6K :EQUATIONEQUATIONFor the third term, we can rewrite it as1 M M m=1 T (m) L (Q ⋆ ) -T (Q ⋆ ) = 1 M ⌈L/M ⌉ M m=1 ⌈L/M ⌉ l=1 T Z (m) l (Q ⋆ ) -T (Q ⋆ ) .We will use Bernstein inequality element wise to bound the above term. Let σ ⋆ ∈ R |S|×|A| be such that [σ ⋆ (s, a)] 2 = Var(T Z (Q ⋆ )(s, a)), i.e., (s, a)-th element of σ denotes the standard deviation of the random variable TEQUATIONholds simultaneously for all (s, a) ∈ S × A with probability at least 1 -δ 6K . On combining (137), ( 138), ( 139) and ( 140), we obtain thatEQUATIONholds simultaneously for all (s, a) ∈ S × with probability at least 1 -δ 2K , where κ ′ = log 12K|S||A| δ . We use this bound in ( 141) to obtain a bound on ∥Q ⋆ H -Q ⋆ ∥ ∞ using the following lemma. Lemma 10 (Wainwright [2019b] ). Let π ⋆ and π ⋆ H respectively denote the optimal policies w.r.t.Q ⋆ and Q ⋆ H . Then, ∥Q ⋆ H -Q ⋆ ∥ ∞ ≤ max (I -γP π ⋆ ) -1 T L (Q) -T (Q) , (I -γP π ⋆ H ) -1 T L (Q) -T (Q) .Here, for any deterministic policy π, P π ∈ R |S||A|×|S||A| is given by (EQUATIONfor some z 0 , z 1 , z 2 ≥ 0 with z 1 < 1, then the bound in Lemma 10 can be simplified toEQUATIONOn comparing, (141) with (142), we obtainz 0 ≡ 8κ ′ L ; z 1 ≡ 2κ ′ L ; z 2 ≡ 2κ ′ 3L(1 -γ) + D • 2 -J • 2κ ′ M .Moreover, the condition L ≥ 32κ ′ implies that z 1 < 1 and 1 1-z1 ≤ √ 2. Thus, on plugging in the above values in (143), we can conclude thatEQUATIONwhere once again we use the value of J in the last step.From the iterative update rule in (123), for any agent m we have,Q m i-1 2 -Q i-1 = η( H (m) i-1 (Q i-1 ) -Q i-1 ) = η( H (m) i-1 (Q i-1 ) -H (m) i-1 (Q ⋆ H ) + H (m) i-1 (Q ⋆ H ) -H(Q ⋆ H ) + Q ⋆ H -Q i-1 ). Thus, ∥Q m i-1 2 -Q i-1 ∥ ∞ ≤ η ∥ H (m) i-1 (Q i-1 ) -H (m) i-1 (Q ⋆ H )∥ ∞ + ∥ H (m) i-1 (Q ⋆ H ) -H(Q ⋆ H )∥ ∞ + ∥Q ⋆ H -Q i-1 ∥ ∞ ≤ η γ∥Q i-1 -Q ⋆ H ∥ ∞ + 2γ∥Q -Q ⋆ H ∥ ∞ + ∥Q ⋆ H -Q i-1 ∥ ∞ = η (1 + γ)∥Q i-1 -Q ⋆ H ∥ ∞ + 2γ∥Q -Q ⋆ H ∥ ∞ ≤ η∥Q -Q ⋆ H ∥ ∞ 7 6 • (1 + γ) + 2γ + ηD(1 + γ) 70 ,holds with probability 1 -δ 2KI . Here, the second inequality follows from ( 131) and ( 132), The last step in the above relation follows from (135) evaluated at a general value of i and the prescribed value of J. By a union bound argument, the above relation holds for all i with probability at least 1 -δ 2K .In this section, we corroborate our theoretical results through simulations. For the simulations, we consider an MDP with 3 states and two actions, i.e., S = {0, 1, 2} and A = {0, 1}. The discount parameter is set to γ = 0.9. The reward and transition kernel of the MDP is based on the hard instance constructed in Appendix B. Specifically, the reward and transition kernel of state 0 is given by the expression in Eqn. (14a). Similarly, the reward and transition kernel corresponding to state 1 and 2 are identical and given by Eqns. ( 14b) and (14c) with p = 0.8. We perform three empirical studies. In the first study, we compare the proposed algorithm Fed-DVR-Q to the Fed-SynQ algorithm proposed in Woo et al. [2023] . We consider a Federated Q-learning setting with 5 agents. The parameters for both the algorithms were set to the suggested values in the respective papers. Both the algorithms were run with 10 7 samples at each agent. For the communication cost of Fed-SynQ we assume that each real number is expressed using 32 bits.In Fig 1a , we plot the error rate of the algorithm as a function of the number of samples used. In Fig. 1b we plot the corresponding communication complexities. As evident from Fig 1a, Fed-DVR-Q achieves a smaller error than Fed-SynQ under the same sample budget. Similarly, as suggested by Fig. 1b , Fed-DVR-Q also requires much less communication (measured in terms of the number of bits transmitted) than Fed-SynQ, demonstrating the effectiveness of the proposed approach and corroborating our theoretical results.In the second study, we examine the effect of the number of agents on the sample and communication complexity of Fed-DVR-Q. We vary the number of agents from 5 to 25 in multiples of 5 and record the sample and communication complexity to achieve an error rate of ε = 0.03. The sample and communication complexities as a function of number of agents are plotted in Figs. 2a and 2b respectively. The sample complexity decreases as 1/M while the communication complexity is independent of the number of agents. This corroborates the linear speedup phenomenon suggested by our theoretical results and the independence between communication complexity and the number of agents.In the last study, we compare the communication complexity of Fed-DVR-Q as function of the discount parameter γ. We consider the same setup as in the first study and vary the values of γ from 0.7 to 0.9 in steps of 0.05. We run the algorithm to achieve an accuracy of ε = 0.1 with parameter choices prescribed in Sec. 4.1.3. We plot the communication cost of Fed-DVR-Q against the effective horizon, i.e., 1 1-γ in Fig. 3 . As evident from the figure, the communication scales linearly with the effective horizon, which matches the theoretical claim in Theorem 2.We use this different notation in appendix as opposed to the half-time indices used in the main text to improve readability of the proof. 


Decision: The paper explores the trade-off between sample complexity and communication complexity in federated Q-learning. The authors focus on a specific yet intuitive class of algorithms characterized by intermittent communication, where each agent independently runs the Q-learning algorithm and engages in scheduled communication rounds to exchange their estimated Q-functions. These algorithms are defined by their step-sizes and communication schedules. For this class, the authors derive a lower bound on communication complexity necessary to achieve a given speed-up in sample complexity (Theorem 1). They also introduce an algorithm that achieves a sample complexity speed-up by a factor of $M$ (the number of agents), with a communication complexity of $\tilde{O}(1/(1-\gamma))$. Notably, these performance guarantees align with the established lower bound.

The reviewers unanimously recognize the significance and depth of the results. They have also provided several suggestions to enhance the clarity and depth of the paper through additional discussions. Please consider these suggestions when preparing the camera-ready version of your paper. Congratulations on this very nice paper.

Reviews: review: paper_summary: paper_summary: This paper investigates the sample and communication complexities of federated Q-learning with intermittent central aggregation of the Q-value function.
The authors demonstrate that to achieve any speedup in sample complexity through federated collaboration, the communication complexity must be at least $\Omega(1 /(1-\gamma ))$.
Additionally, the paper introduces a novel federated Q-learning algorithm incorporating variance reduction and minibatching techniques, achieving order-optimal sample and communication complexities.
strength_weakness: strength_weakness: - Several papers report that a _one-shot_ average is sufficient to achieve linear speedups in federated reinforcement learning (FedRL) [1,2]. This seems to contrast starkly with the authors' claim that infrequent communication does not speed up sample complexity. Could the authors clarify this discrepancy and discuss how their work relates to these results?
- The related work section on Distributed RL is generally comprehensive; however, it omits some recent works on heterogeneous FedRL [3,4].
- There is a lack of discussion on the technical difficulties and novelties of the proposed approach. The authors mentioned that Theorem 1 is inspired **by** the analysis of single-agent Q-learning [5] and Theorem 2 is based on the analysis of variance-reduced Q-learning [6]. The authors should elaborate on how their analysis differs from the single-agent case, what new challenges arise in the federated setting, and what novel techniques are employed to overcome these challenges. Additionally, can these techniques be generalized to other settings?
- In Eq. (7), should $\widehat{\mathcal{T}}$  be $\mathcal{T}$? Otherwise it is not defined.

Overall, I am satisfied with the paper, with the first point being my primary concern. I would be happy to raise my score if the authors provide satisfactory clarifications on the above points.

### References

[1] Liu, R., & Olshevsky, A. (2023). Distributed TD (0) with almost no communication. _IEEE Control Systems Letters_, _7_, 2892-2897.  
[2] Tian, H., Paschalidis, I. C., & Olshevsky, A. (2024). One-Shot Averaging for Distributed TD (λ) Under Markov Sampling. _IEEE Control Systems Letters_.  
[3] Xie, Z., & Song, S. (2023). FedKL: Tackling data heterogeneity in federated reinforcement learning by penalizing KL divergence. _IEEE Journal on Selected Areas in Communications_, _41_(4), 1227-1242.  
[4] Zhang, C., Wang, H., Mitra, A., & Anderson, J. (2024). Finite-time analysis of on-policy heterogeneous federated reinforcement learning. In _International Conference on Learning Representations_. PMLR.  
[5] Li, G., Cai, C., Chen, Y., Wei, Y., & Chi, Y. (2024). Is Q-learning minimax optimal? a tight sample complexity analysis. _Operations Research_, _72_(1), 222-236.
[6] Wainwright, M. J. (2019). Variance-reduced $ Q $-learning is minimax optimal. _arXiv preprint arXiv:1906.04697_.
questions: questions: - While I understand that the authors focus on homogeneous i.i.d. data to highlight the main ideas, could the authors comment on the difficulty of generalizing their results to the asynchronous sampling setting? Specifically, the authors mention that the lower bound applies to the asynchronous setting. A similar remark on Theorem 2 would be helpful.

Please see Section Weaknesses for other questions.
limitations: limitations: Limitations and open problems are adequately discussed.
paper_summary: paper_summary: This paper discusses the sample and communication complexity of federated tabular Q-learning. The main contributions can be summarized as follows. First, the paper provides a lower bound on the communication 
cost to guarantee a linear speed-up with respect to the number of agents. Then, it proposes a novel  Federated Q-learning algorithm, called Fed-DVR-Q, which simultaneously achieves optimal order sample and communication complexities.
strength_weakness: strength_weakness: W1. Both the lower and upper bounds only apply to the case of synchronous Q-learning with IID samples of the $(s_k, a_k, r_k, s_{k + 1})$ sequence at each agent. Moreover, it only applies to the tabular setup.
questions: questions: Q1. Can you quantify the benefit of variance reduction in the upper bound? That is, what would the sample complexity be if we looked at a variant of your algorithm without the variance reduction part of the update rule? Doesn't the variance reduction technique typically lead to an improvement in terms of the constants in the sample complexity? I am a bit surprised to see that variance reduction is needed even to guarantee **order** optimal sample and communication complexities.

Q2. Typically, to get convergence to an $\epsilon$-neighbourhood, the stepsize $\eta$ should be chosen depending on $\epsilon.$ For example, see Theorem 2 (a) in [BRS18]. However, in your Theorem 2, it appears $\eta$ can be any number in $(0, 1).$ This seems a bit surprising. Can you elaborate on why that is the case? Am I overlooking something?

[BRS18]: Bhandari, J., Russo, D. and Singal, R., 2021. A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation. Operations Research, 69(3), pp.950-973.

Q3. Also, it is unclear to me why you claim that your upper bound matches the lower bound. The lower bound is in terms of $N,$ while the upper bound is in terms of $\epsilon?$ Can you formally show that the two orders match?

Q4. Finally, assuming your lower and upper bounds match, can you explain whether the proposed Fed-DVR-Q is a parameter-free algorithm? That is, does it need any knowledge of the unknown parameters of the underlying MDP to achieve order-optimal sample complexity?

I would be happy to increase my score based on your response to my above question.
limitations: limitations: Yes, the authors have discussed the limitations of their work.
paper_summary: paper_summary: This paper addresses the challenge of Federated Q-learning, focusing on the trade-off between sample complexity and communication complexity. Federated Q-learning involves multiple agents collaboratively learning the optimal Q-function for an infinite horizon Markov Decision Process (MDP) with finite state and action spaces.

The paper proves the lower bound result on the number of rounds, which shows that linear speedup in sample complexity with respect to the number of agents requires at least $\Omega(\frac{1}{1-\gamma})$ rounds of communication.

The second contribution is the algorithm that shows that this bound is tight.
strength_weakness: strength_weakness: While the main focus of this work is theoretical, the paper could benefit from the experimental evaluation of the algorithm.
questions: questions: There are also studies on distributed multi-armed bandits, such as 'Parallel Best Arm Identification in Heterogeneous Environments' and 'Communication-efficient Collaborative Best Arm Identification,' which are relevant to Q-learning and RL problems. Could you elaborate on the main differences in techniques used in these studies?
limitations: limitations: N/A

Comments: title: Response to Reviewer
Response to Reviewer
Response to Reviewer
Rebuttal by Authors contd.
Rebuttal by Authors contd.
comment: Thank you for the response.  Yes, it is satisfactory.
I thank the authors for the comprehensive rebuttal and am content with the clarifications, discussions, and promised revisions. I have raised my score and will support the acceptance of this work.
Thank you once again for taking out time to review our paper. We hope that our rebuttal satisfactorily addressed all your concerns. If you have any additional or follow-up questions based on the rebuttal, we would be happy to answer them!
Thank you once again for taking out time to review our paper. We hope that our rebuttal satisfactorily addressed all your concerns. If you have any additional or follow-up questions based on the rebuttal, we would be happy to answer them!
Thank you once again for taking out time to review our paper. We hope that our rebuttal satisfactorily addressed all your concerns. If you have any additional or follow-up questions based on the rebuttal, we would be happy to answer them!
- _While I understand that the authors focus on homogeneous i.i.d. data to highlight the main ideas, could the authors comment on the difficulty of generalizing their results to the asynchronous sampling setting? Specifically, the authors mention that the lower bound applies to the asynchronous setting. A similar remark on Theorem 2 would be helpful._

It is reasonably straightforward to extend the results to the asynchronous sampling setting. At a high level, note that after a burn-in period depending on the mixing time of the behaviour policy, the state visitation distribution will be close to the true stationary distribution. From hereon, we can run the algorithm almost as is with a different choice of mini-batch sizes and recentering sample size parameters. Note that the only difference in the asynchronous setting as compared to the generative model will be that the number of samples for each state-action pair will depend on the behaviour policy. By an appropriate choice of mini-batch sizes and recentering sample sizes, we can ensure that the error still decreases by a factor of 2 every epoch. Consequently, similar conclusions on the sample and communication complexity will also hold for the asynchronous setting. We would also like to point out that the sample complexity will be inversely proportional to the minimum *average* state-action visitation probability, similar to (Woo et al, 2023). As shown in that work, that is the best one can hope for and does not require each agent to cover all state-action pairs. 

Thank you for you helpful question. We will also add a discussion on this in the final paper.
- _There is a lack of discussion on the technical difficulties and novelties of the proposed approach. The authors mentioned that Theorem 1 is inspired by the analysis of single-agent Q-learning [5] and Theorem 2 is based on the analysis of variance-reduced Q-learning [6]. The authors should elaborate on how their analysis differs from the single-agent case, what new challenges arise in the federated setting, and what novel techniques are employed to overcome these challenges. Additionally, can these techniques be generalized to other settings?_

One of the challenges in federated setting over the results in [5] and [6] is the design of the communication schedule and its interplay with the convergence of the algorithm to the optimal Q-function. We mention that our analysis is inspired by [5] as we use the same hard instance used in that work and the authors in [5] also use bias-variance trade-off to establish sub-optimality of sample complexity of Q-learning. However, in terms of establishing our lower bound, none of the lemmas from the analysis of single agent Q-learning in [5] can be trivially adopted for the federated learning scenario considered in our work as behaviour of all agents affects that of the others. This requires us to establish all technical results from scratch. Moreover, the communication schedule directly affects the bias-variance trade-off in the federated setting which needs to be carefully analyzed and balanced. Establishing the impact of communication on this trade-off is central to establishing the lower bound in our work. In our analysis, we establish how the time interval between two communication rounds affects the bias and the variance terms. This allows us to show that infrequent communication results in a higher bias term preventing linear speed-up with the number of agents. This analyses and conclusions are completely novel compared to the single-agent analysis in [5] especially because there is no communication involved in single-agent setting and the focus of their analysis is on establishing the sample complexity. Furthermore, the interplay of communication and bias-variance trade-off can be used to conclude communication bounds for more general problems of distributed stochastic fixed point iteration, specifically with non-linear operators. For example, a similar analysis yields that distributed optimization of strongly convex functions using SGD requires a communication cost proportional to the condition number of the function. Thus, the proposed techniques in this work have implications beyond RL.

A direct extension of the algorithm in [6] to the federated setting results in a sub-optimal sample and communication complexities similar to (Woo et al, 2023). The novelty in our work to show that using minibatching as opposed local updates helps manage the bias-variance trade-off (referred to the in lower bound) much better enabling us to achieve optimal sample and communication complexities. As mentioned earlier, this observation carries forward to other distributed stochastic fixed point iteration problems, thereby providing a template to design algorithms that operate at the optimal point in sample-communication complexity trade-off curve. Since our algorithm design is different from that in [6], we need to derive newer results to establish Theorem 2. Lastly, the impact of communication and quantization prevents us from directly adopting the results in [6] and requires a more careful and novel analysis to ensure the optimal convergence rates.

Thank you for pointing this out. We will add a discussion based on these lines in the final version of this paper.


- _In Eq. (7), $\hat{\mathcal{T}}$ should be $\mathcal{T}$? Otherwise it is not defined_.

That is correct. Thank you pointing it out. We will fix the typo.