The Sample-Communication Complexity Trade-off in Federated Q-Learning
Authors: Sudeep Salgia
Yuejie Chi
Venue: NeurIPS 2024 oral (2024)
Keywords: Federated Q learning; Communication Efficiency;
Primary area: reinforcement_learning
TL;DR: Characterization of Sample-Communication Trade-off in Federated Q-learning with both converse and achievability results

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.

The Sample-Communication Complee Trade-off in Federated Q-Learning
Sudeep Salgia Carnegie Mellon University ssalgia@andrew cmu. edu
Yuejie Chi Carnegie Mellon University yuejiechi@cmu edu
Abstract
We consider the problem of Federated Q-learning, where M agents aim to col- laboratively 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 inter- mittent 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 incur communication cost of at least Q (-)) where is the discount factor. We also propose new Federated Q-learning algorithm, called Fed-DVR-Q, which is the first Federated Q-learning algorithm to simultancously achieve order-optimal sample and communication complexities. Thus, together these results provide complete characterization of the sample-communication complexity trade-off in Federated Q-learning.
Introduction
Reinforcement Learning (RL) (Sutton and Barton 2018 refers online sequential decision making paradigm where the learning agent aims to learn an optimal policy, i.c., 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 2013 Yurtsever
et al. 2020 Silver et al,, 2016 Lim et al., 2020].
The primary hurdle in RL applications is often the nigh-dimensional nature of the decision space that necessitates the learning agent to have to access to an enormous amount of data order to have any hope of learning the optimal policy. Moreover, the sequential collection of such 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, gaining interest due 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 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 central facility/server. Such approach trivially achieves the optimal sample complexity while suffering from a very high and infeasible communication complexity. On the other hand, several recently proposed
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

algorithms [Khodadadian et al. 2022 Woo et al. 2023 operate in more practical regimes, offering significantly lower communication complexities as compared the naive approach the cost of sub-optimal sample complexities. These results suggest the existence of underlying trade-off between sample and communication complexities of Federated RI. 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 benefis of collaboration?
Optimal algorithm design: How does one design a federated Q-Learning algorithm that simultane- ously offers optimal order sample and communication complexity guarantees i.e. operates on the optimal frontier of cample-communicot complexity trade-off?
1.1
Main Results
We consider setup where M distributed agents collaborate 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 discount factor of (0, 1). We consider commonly considered setup in federated learning called the intermittent communication setting, where the clients intermittently share information among themselves with the help of central server. In this work, provide 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 transmitted in order to achieve any speed up in convergence with respect the number of agents. Specifically, we show that in order for an intermittent communication algorithm to obtain any benefit collaboration, i.e., any order of speed up w.r.t. the number of agents, the number of communication rounds must be least Q log² N and the number of bits sent by each agent to the server must be
least Q [S||-]] lo- N). where N denotes the number of samples taken by the algorithm for each
state-action pair.
Federated Q-Learning algorithm called Federated Doubly Variance Reduced Q Learning. Fed-DVR-O 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-O learns an e-optimal
Achieving the optimal cumple-commuiccatiio complexity trade-off': We propose
Q-function in the foo sense with δ |S||A|| i.i.d. samples from the generative model each [ee(1-))3
agent while incurring a total communication cost of Ō rounds of communication. Thus. Fed-DVR- 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 Tfor a comparison).
SS [SLA)] bits per agent across ① (1-))
(1-7)
1.2
Related Work
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 complexiin
both synchronous EEen- Dar and
Mansour [2004] Beck and Srikant 2012,, Wainwright 2019a aa Chen et al. 2020 Li et al. 2023 and
asynchronous settings [Chen al. 2021b Li al. 2023 202 Qu and Wierman 2020
Distributed RL. There has also been considerable effort towards developing distributed and federated RL algorithms. The distributed variants of the classical TD learning algorithm have been investigated in series of studies [Chen et al.] 2021c Doan et al. 2019 202 Sun et al.) 2020 Wail 2020, Wang et al.] 20200 Zeng et al. [02Tb]. in federated TD learning was studied in Wang et al. 2023 A distributed version of actor-critic
The impact of environmental heterogeneity

---

Number of Agents
Sample Complexity
Communication Complexity
Algoritmm/Reference
|
Q-lcaming [Li et al.
2023
1
N/A
(1 7)
|
Variance Reduced Q-learning Wainwright
2019b
1
N/A
(1 - 7)
||||A
M
Fed-SynQ
[Woo et al.
2023
M
M(1 7)
1
|S||_A]
1
Fed-DVR-Q (This work)
M
(1 7)
||||
1
Lower bound ( (Aza et al. 2013), This work)
M
M(1 77)
Table I: Comparison of sample and communication complexity of various single-agent and Federated Q-learning algorithms for learning an e-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, and A represent state and action spaces respectively and y 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 al. 2022 proposed new distributed actor-critic algorithm which improved the
dependence of sample complexity on the error and incurs a communication cost of Ö(E-)). Chen itt al. [2021a] have proposed communication efficient distributed policy gradient algorithm and have analyzed its convergence and established communication complexity of (M)((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 [003) obtains linear
(Chen
communication cost, which is worse than that obtained in our work. Similarly, Zhang et al. [2024]
focuses on on- on-policy learning and incurs 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 distributeddfeddertted variants of the classical natural policy
gradient method [Kakade| 22001] 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 al. [2022] proposed and analyzed a federated Q-learning algorithm in the asynchronous setting
with sample complexity of Ô M (
[S)
where Mmin 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 Qeleaniing 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( ((T-))²)) and O (TT-))=)) 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 sample complexity and [SIAA|
communication complexity of Ó M(1-7) and Ö( S| real numbers respectively under the
1-y
(M(SILA) real numbers respectively under synchronous setting and that of Ö( "Pay(1 and ò ( (M
the asynchronous setting. Here, Mavg denotes the minimum entry of the average stationary state-action occupancy distribution of all agents. learning for offline RL in finite horizon setting and establish sample and communication complexity of Ö single-policg concentrability cocfficient of all agents.
follow up work. Woo al. (2024) propose Federated Q-
M (S and Ö(H), where H denotes the length of the horizon and Cavy denotes the average
3

---

Trade-off in Federated Learning. The trade-off between commu- nication complexity and accuracy (equivalently, sample complexity) has been studied in various federated and distributed learning problems, including stochastic approximation algorithms for con- vex 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 202 Salgia and Zhao 2023
2 Problem Formulation and Preliminaries
In this section, we provide a brief background of Markov Decision Processes, outline the performance measures for Federated Q Q-learning algorithms and describe the class of intermittent communication algorithms considered in this work.
2.1 Markov Decision Processes
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 y E (0, 1). Both the state and action spaces are assumed to be finite sets. In an MDP, the state evolves dynamically under the influence of actions based on a probability transition kernel, P (S A) x S + [0, 1]. The entry P(s"|s, a) denotes the probability of moving to state s' when an action is taken in the state An MDP also associated with deterministic reward function r : S x A -> [0, 1], where r(s, a) denotes the immediate reward obtained for taking the action in the state 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 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
policy π S > (AA) is a rule for selecting actions across different states, where A(AA denotes the simplex over A and x (als) denotes the probability of choosing action a in state s. Each policy π associated with 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 as
1
(3) = E
Σ Ex((s)))))) 0
(²( = E
Σ 0=
(rr(s), az) 80 8,000
(1)
where a2 (-1ss) and St+1 P( (st,aa) az) for all t > 0. The expectation is taken w.n.t. the randomness in the trajectory {s,, a, j Since the rewards lie in [0, 1], it follows immediately that both the value function and Q-function lie in the range [0, 1-
An optimal policy " is policy that maximizes the value function uniformly over all the states and it has been shown that such an optimal policy x' always exists [Puterman] [014]. The optimal value and Q-fucttions are those corresponding to that of an optimal policy a are denoted as V == v** and Q* == Q*" respectively. The optimal Q-function, Q*, is also the unique fixed point of the Bellman operator T S x A + S x A, given by
(TQ) r r(s,)) + +y Ea-P((aaa)
max Q(s', a's',a') a'EA
(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 TQ = Q and then obtain a deterministic optimal policy via the maximization π (s) = arg max, (*(ssa) a).
Let Z E S|S|AAA 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 Tz (S x A) + (S x A) as
(TzQ) r(s. a) + +))
(3)

---

where (s*) a EA Q(s', d'). The operator Tz can be interpreted as the sample Bellman Operator, where we have the relation TQ = Ez [7> for all Q-functions.
Lastly, the federated learning setup considered in this work consists M agents, where all the agents face 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 E E (0, r-y), ) the objective of agents is to collaboratively learn an e-optimal estimate (in the &o sense) of the optimal Q-function of the unknown MDP.
2.2 Performance Measures
We measure the performance Federated Q-learning algorithm af using two metrics - sample complexity and communication complexity. For given MDP M, let Qm(at, Me(a,,,, N.) denote the estimate of QM. the optimal Q-function of the MDP MM, returned by an algorithm st 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 s/ denoted by ER(a/; N, M),, is defined as
ER(a/;
sup E (IQ, Qmll=> M=(P,r)
(4)
where the expectation is taken over the samples and any randomness in the algorithm. Given a value of >> 0, the sample complexity of s denoted by SC (o;;; M) is given as
SC(ddE M) == ||S|AA min E N: ER( N, M) E)).
(5)
Similarly, we can also define a high-probabiiltyy version for any 5 E (0, 1) as follows:
S M, 8) = |S||_]] min{ E N Pr(sup ((Q N, M) QMll 56) 63.
MM
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 Croun (o/; ; N) and Chil (#/; .N) respectively denote the number of times agent m sends a message to the server and the total number of bits uploaded by agent to the server when an algorithm of is run with N i.i.d. samples from the generative model for each (s, a) pair at each agent. The communication complexity of s when measured in terms of frequency of communication and total number bits exchanged, is given by
M
M Σ (ad;
Σ CC ( Nz = M m==1
Cround N); CC N)
(6)
M
m==
respectively. Similarly, for given value of E (0, r we can also define (a) and (Con((e/E)) based on when of is run to guarantee minimax error of at most E.
2.3 Intermittent Communication Algorithms
In this work, consider popular class of federated learning algorithms referred to as al- gorithms with intermittent communication. The
Algorithm 1: A generic algorithm st
intermittent communication setting provides a natural framework to extend single agent Q- learning algorithms to the distributed setting. As the name suggests, under this setting, the agents intermittenlly communicate with each other, sharing their updated beliefs about Q*. Between two communication rounds, each agent updates their belief about Q* using stochas- tic 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 (Woodworhh al., 2018 2021
1: Input: : T, R. {m 1T VT C {t,) B
2: Set QT" + for all agents m
3: for t = 1,2, ... do
4:
for m = 1, 2,
do Compute Q according to Eqn.
5:
6: Compute Q according to Eqn.
7: end for
8: end for
9: return QT
5

---

A generic Federated Q-learning algorithm with intermittent communication is outlined in Algorithm 1 is characterized by the following five parameters: total number of updates T: (ii) the number of communication rounds R: (iii) step size schedule {m ) (iv) communication schedule {4,) ) (v) batch size B. During the tt iteration, each agent computes (Tz, (Q7",) ) minibatch of sample Bellman operators at the current estimate Q using B samples from the generative model for each (s, a) pair, and obtains intermediate local estimate using the Q-learning update follows:
(1- +
T B
Σ b=1
Tz (Q
Here 77, E (0, 1] is the step-size chosen corresponding to the tt time step. The intermediate estimates are averaged based on a communication schedule = [tr)r= consisting R. rounds, i.c.,
M プド=
O iftEC
Qr
(8)
otherwise.
In the above equation, the averaging step 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 = 0 for all agents and & = 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, Le, N BT and the communication complexity CCround R.
3 Lower Bound
In this section, we investigate the first of the two questions regarding the lower bound on communica- tion complexity. The following theorem establishes a lower bound on the communication complexity of Federated Q Q-learning algorithm with intermittent communication.
Theorem 1. Assume that Y E [5/6,] 1) and the state and action spaces satisfy |S] 2 4 and |A] 2 2. Let s be Federated Q-learning algorithm with intermiltent communication that is run for T 2 max [16, I steps with a step size schedule of either = I+e,(1-73{ or le == 7) for all I
1st 14111 T. If
ci C|
R = CCrondd N) S (1 7 71 log N or CCarl N)
(1 (1- log
for some universal constants co, then, for all choices of communication schedule, batch size B, on > and 17 E 1), the minimax error of satisfies
C
ER( (N log" NVN'
for all M 2 and BT. Here C, > 0 is constant that depends only on 7/-
The above theorem states that in order for intermittent communication algorithm obtain any benefit of collaboration, i.e., for the error rate N M) to decrease w.r.t. number of agents, the number of communication rounds must be least Q (1(1117)) (1-7) log" N )- This implies that any Federated Q-learning algorithm that offers order optimal sample complexity, and thereby also linear speed up with respect to the number of agents, must have at least O (1=7) rounds of communication
and transmit Q (1-3) log N bits of information per agent. This characterizes the converse relation tradcoff Federated Q-learning. We would like to point out that our
[SAA
for the sumple-communicattee lower bound extends to the asynchronous setting the assumption of i.i.d. noise corresponding to generative model a special case of Markovian noise observed in asynchronous setting.
The lower bound on the communication complexity of Federated Q-leariigg is consequence of the bias-variance trade-off that governs the convergence 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 balancing this trade-off in the federated setting. The local steps between two communication rounds induce positive estimation bias that

---

depends on the standard deviation of the iterates and is well-documented issue of "over-estimatte 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 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 intermittent communication algorithm specifically chosen "hard" instance of MDP. Please refer to Appendix B for a detailed proof.
Remark (Communication complexity of policy evaluation). Several recent studies (Liu and OH shevsky 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 more involved due to the nonlinearity 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 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 ensure that the bias term is small enough.
Remark 2 (Extension to asynchronous Q Q-learning). We would like to point out that lower bound extends to the asynchronous setting et ct al. 2023) as the assumption of i.id. noise corresponding to generative model is special case of Markovian noise observed in the asynchronous setting.
4 The Fed-DVR-Q algorithm
Having characterized the lower bound the communication complexity of Federated Q-learning, explore our second question of interest - designing a federated Q-learning algorithm that achieves this lower bound while simultaneously offering optimal order of sample complexity.
We propose a new Federated Q-learning algorithm, Fed-DVR-C. that achieves not only a communica- tion complexity of CCround = Ō } and CC = Ō ( but also the optimal order of sample complexity (upto logarithmic factors), thereby providing tight characterization of the achievability frontier that matches with the converse result derived in the previous section.
4.1 Algorithm Description
Fed-DVR-Q proceeds in epochs. Dur- ing an epoch 2 1, the agents collab- oratively update Q(k-1), the estimate of Q" obtained at the end of previous epoch, to a new estimate Qik), with the aid of the sub-routine called REFINEESTIMATTE The sub-routine REFINEESTIMATTE is de- signed to ensure that the suboptimality gap. [[Q(k) - @²' reduces by a factor of 2 the end of every epoch. Thus, at the end of K Olog(1/E)) epochs, Fed-DVR obtains e-optimal estimate of Q", which then to be the output of the algorithm. Please refer to Alg. forr a pseudocode.
Algorithm 2: Fed-DVR-Q
1: Input: Error bound > 0, failure probability
> 0
2: k -- 1, 110(0)) +
3: // Set parameters as described in
Sec. 4.1.3
4: for k = 1,2, do
5: Q(R)
REFINEESTTMATTE(II- B, La, Dx, J)
6: k <- k+1
7: end for return Q(K)
4.1.1 The REFINEESTIMATE sub-routine
REFINEESTIMATE, starting from Ø, an initial estimate of Q", uses variance reduced Q-learning updates 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,
7

---

which can be appropriately tuned to control the quality of the returned estimate. Additionally, it also takes ippu two parameters D and J required by the compressor.
The first step in REFINEESTIMATE is collaboratively approximate TQ for the variance reduced updates. To this effect, each agent m builds an approximation of TQ as follows:
[L/M]
m.
Σ
T T2(m)(())
[L/M]
where { _mmm
[(m) [L/M]
are [L/M] i..d. samples with 2/T) Z. Each agent sends
& T (m) Q Q: D. a compressed version of the difference T/," (Q) Q2 to the server, which
collects all the estimates from the agents and constructs the estimate
M Σ
Tz(Q) - M m=1
6 T
Q - Q; D,J,J)
(10)
and sends back 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 (Q)). REFINEESTIMATE
constructs a sequence {Q:Y/z using the following iterative update scheme initialized with Qo Q. During the :th iteration, each agent m carries out the following update:
QT (1-n)QQ-1 +
7, (m) Qi-1 7:10) Q+ TQ(
(11)
In the above equation, 1) (0, 1) is the step size and 7. Q = B E.Ez(")) T2Q, where 2 is the minibatch B i...d. random variables drawn according to Z, independently at each agent m for all iterations Each agent then sends a compressed version of the update, i.e., 8 to the server, which uses them to compute the next iterate
(QTTh D,,1;
1 M Σ E
Qi
(12)
and broadcast it to the clients. After / such updates, the obtained iterate Q₁ is returned by the routine. pseudocode of the REFINEESTIMATE routine is given in Algorithm 3 in Appendix A
4.1.2 The Compression Operator
The compressor, (,; used in the proposed algorithm F is based on the popular stochastic quantization scheme. In addition to the input vector to be quantized, the quantizer '6 takes two input parameters D and J. D corresponds to an upper bound on for norm Q, i.e., [1 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' intervals of equal length where 0= di < d2, < d2. = D correspond to end points of the intervals. Each coordinate of Q is then separately quantized follows. The value of the thth coordinate, '6 [n)) is set to be d,, with probability din -i,-d,,-
4, Q[m] and to dj, with the remaining probability, where jn := min(j d, < Q S ds+1}. It is straightforward to note that each coordinate of ((Q) can be represented using J bits.
4.1.3 Setting the parameters
The desired convergence of the iterates {Q(#) is obtained by carefully choosing the parameters of the sub-routine REFINEESTIMAN and the compression operator 66 For all epochs k: 2 1, we set the number of iterations and the batch size B REFNEESTIMATE and the number bits J of the com-
pressor 6 to be . 1.
M
[T-7]]
12t )² log( (K1])SL ) and [log2( 7(1
70
re- loga( (1-7) )1 The
log( &K//S
spectively. The total number of epochs is set to K = [ log, 1
recentering sample sizes LE and bounds D; are set to be the following functions of epoch index k:
Ly (1 11-7) 72 log [KI[S||AA
19600
if < Ko if Ko
2
DE 16
(13)
Koo
1 1-
8

---

where Ku [ log2( (-))1 The piecewise definition of L is crucial to obtain the optimal depen-
dence with respect to similar to the two-step procedure outlined Wainwright 2019b].
4.2 Performance Guarantees
The following theorem characterizes the sample and communication complexity of Fed-DVR-Q.
Theorem 2. Consider any å E 10 and = E (0, 1]. Under the federated learning setup described in Section 2.7 the sample and communication complexities of the Fed-DVR-O algorithm, when run with the choice of parameters described in Sec. 4.1.3 and a learning rate E (0, satisfy the following relations for some universal constant C1
O:
C1
8KT|S|IA
S. S
log2
log
11(11 - 3)
(1-7)8)
16
CCround (Fad-DDFFDDV
log2
17(1 7)
(1 7)=
3 log2
1
70
2
(8I[S||AA
CC (Fed-DVV--
log2
log
11 7)
(1 - 7)c
111
7)
M
8
proof of Theorem 2 can be found in Appendix C A few implications of the theorem are order.
Optimal Sample-Communicattee 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 simultameously achieving the same order of communication complexity as dictated by the lower bound derived in Theorem [] both in terms of frequency and bit level complexity. Moreover, Fed-DVR-Q the first Federated Q-Learning algorithm that achieves sample complexity with optimal dependence on all the salient parameters, i.e., [S), |A] and 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 T and 2 together provide a characterization of optimal operating point of the compule-commuiictioon complexity trade-off in Federated Q-learning.
1-7'
Role of Minibatching. The commonly adopted approach in intermittent communication algorithm to use a local update scheme that takes multiple small (i.e., (1)), noisy updates between
communication rounds, as evident from the algorithm design in Khodadadian et al. [2022] Woo
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 single, large update with smaller variance, obtained by averaging the noisy updates over 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- to achieve optimal order of communication complexity.
Compression. F the first algorithm in Federated Q-Learning 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 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 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 linear speedup with respect to the number of agents if its number of communication rounds are sublinear in r We also proposed new Federated Q-learning algorithm called Fed-DVR-Q that uses variance reduction along with minibatching to achieve optimal-orde sample and communication complexities. In particular, we showed that Fed-
DVR-Q has sample complexity of O
([1-7)) ) which is order-optimal in all salient problem IS [.A]
parameters, and communication complexity of Ö rounds and Ō ( bits.
The results in this work raise several interesting questions that are worth exploring. While focus on the tabular setting in this work, is of great interest to investigate to the trade-off in other settings where we use function approximation to explore the trade-off in the finite horizon setting, where there is no discount factor. Furthermore, it is also worthwhile explore if the communication complexity can be further reduced by going beyond the class of intermittent communication algorithms.
model the Q* and V functions. Moreover, it is interesting
Acknowledgement
We would like to thank the anonymous reviewers for their constructive feedback. This work is supported in part by the grants NSF CCF-2007911, CCF-2106778, CNS-2148212, ECCS-231844 ONR N00014-19-1-2404 and AFRL FA8750-20-2-0504 and in part by funds from federal agency and industry partners as specified in the Resilient & Intelligent NextG Systems (RINGS) program.
References
M. Assran, J. Romoff, N. Ballas, J. Pineau, and M. Rabbat. Gossip-based actor-learner architectures for deep reinforcement learning. In Proceedings of the 33rd Annual Conference Neural Information Processing Systems, volume 32, 2019.
M. G. Azar, R. Munos, and H. J. Kappen. Minimax PAC bounds the sample complexity of reinforcement learning with a generative model. Machine Learning, 91(3):22--39, 2013.
C. Beck and R. Srikant. Error bounds for constant step-size q-learning, Systems & Control Letters, 61012):1203-1208 2012. ISSN 0167-6911.
V. S. Borkar and S. P. Meyn. The o.d.e. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469, 2000. doi: 10.1 10.11377/0066331199933336
M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. Woodruff. Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pages 101 101100020, 2016.
T. Chen, K. Zhang, G. B. Giannakis, and T. Başar. Communication-effccinn policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems, 9(2): 917-929, 2021a.
Z. Chen, S. T. Maguluri, Shakkottai, and Shanmugam. Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, volume 33, pages 8223-8223333 2020.
Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam. A Iyapunov theory for finite-sample guarantees of asynchronous q-learning and td-learning variants, 2021b.
Z. Chen, Y. Zhou, and R. Chen. Multi-agent off-policy tde with opar-oltimal sample and commu- nication complexity. In Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers, pages 504-508, 2021c.
10

---

Z. Chen, Y. Zhou, R.-R. Chen, and S. Zou. Sample and communication-Co critic algorithms with finite-time analysis. In Proceedings of the 39th International Conference on Machine Learning, pages 3794-3834. PMIR, 2022.
-eaffficatto-fffiienttt efficient decentralized actor-
T. Doan, S. Maguluri, and J. Romberg. Finite-time analysis of distributed td (0) with linear function approximation on multi multi-agent reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, pages 1626-1635, PMLR, 2019.
T. T. Doan, S. T. Maguluri, and J. Romberg. Finite-time performance of distributed temporal- difference learning with linear function approximation. SIAM Journal on Mathematics of Data Science, ((1))2988333)) 2021.
J. C. Duchi, M. I. Jordan, M. J. Wainwright, and Y. Zhang. Optimality guarantees for distributed statistical estimation, 2014. /tttp:////axx org/obgg /eeee/140...0 0782
L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In Proceedings of the 35th International conference machine learning, pages 1407-1416. PMLR, 2018.
E. Even-Dar and Y. Mansour. Learning rates for q-learning. Journal of Machine Learning Research, 5, 2004. ISSN 1532-4435.
D. A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100-118, 1975.
Haddadpour, M. M. Kamani, M. Mahdavi, and V. R. Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems, volume 32, 2019.
H. v. Hasselt, Double q-learning. Proceedings of the 23rd International Conference on Neural Information Processing Systems, page 2613-2621. Curran Associates Inc., 2010.
T. Jaakkola, M. Jordan, and S. Singh. Convergence of stochastic iterative dynamic programming algorithms. In Proceedings of the 7th Annual Conference on Neural Information Processing Systems, volume 6, 1993.
H. Jin, Y. Peng, W. Yang, S. Wang, and Z. Zhang. Federated reinforcement learning with environment heterogeneity. In Proceedings of the 25th International Conference on Artificial Intelligncee and Statistics, pages 18-37. PMLR, 2022.
S. M. Kakade. A natural policy gradient. Proceedings of the 15th Annual Conference on Neural Information Processing Systems, 14, 2001.
M. Kearns and S. Singh. Finite-sample convergence rates for q-learning and indirect algorithms. In Proceedings of the 12th Annual Conference on Neural Information Processing Systems, 1998.
A. Khaled, K. Mishchenko, and P. Richtárik. Tighter Theory for Local SGD on Identical and Heterogeneous Data. In Proceedings of the 22nd International Conference Artificial Intelligence and Statisties, AISTATS, pages 4519-4529, PMLR, 2020. httthhttp///aeeee org/ hlsgg/bb//// 1909 04746
S. Khodadadian, P. Sharma, G. Joshi, and S. T. Maguluri. Federated reinforcement learning: Linear speedup under markovian sampling. In Proceedings of the 39th International Conference on Machine Learning, pages 10997-110577 PMLR, 2022.
J. Kober, J. A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11): 1274, 2013.
G. Lan, D.-J. Han, A. Hashemi, V. Aggarwal, and C. G. Brinton. Asynchronous federated rein- forcement learning with policy gradient updates: Algorithm design and convergence analysis, 2024.
G. Li, Y. Wei, Chi, Y. Gu, and Y. Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. IEEE Transactions on Information Theory, 68(1):448-477 2021.
11

---

G. Li, C. Cai, Y. Chen, Y. Wei, and Y. Chi. Is q-learning minimax optimal? tight sample complexity analysis. Operations Research, 2023.
H.-K. Lim, J.-B. Kim, J.-S. Heo, and Y.-H. Han. Federated reinforcement learning for training control policies on multiple iot devices. Sensors, 20(5), 2020. ISSN 1424-8220. doi: 10.3390/s20051355,
R. Liu and Olshevsky. Distributed TD(0) with almost no communication. IEEE Control Systems Letters, 7:2892-2888 22997, 2023.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication-effce learning of deep networks from decentralized data. In Proceedings of the 20th International Conference Artificial Intelligence and Statistics, AISTATS, pages 1273 1282. PMLR, 2017.
V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillierap. T. Harley, D. Silver, and K. Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning, pages 1928-1993 PMLR, 2016.
M. Puterman. Markov decision processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
G. Qu and Wierman. Finite-time analysis of asynchronous stochastic approximation and q-learning. In Proceedings of the 33rd Conference on Learning Theory, pages 3185-3 3205, PMLR, 2020.
S. Salgia and Q. Zhao. Distributed linear bandits under communication constraints. In Proceedings of the 40th International Conference on Machine Learning. ICML, pages 2023.
PMLR,
H. Shen, K. Zhang, M. Hong, and Chen. Towards understanding asynchronous advantage actor- critic: Convergence and linear speedup. IEEE Transactions on Signal Processing, 2023.
C. Shi and C. Shen. Federated Multi-Armed Bandits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 9603-9611 2021. httthttp///xiii org/ abs/ tabs/2101, 2101. 12204
org/abs/a/
D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, Antonoglou, V. Panneershalvam, M. Lanetot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484 489, 2016.
J. Sun, G. Wang, G. B. Giannakis, Q. Yang, and Z. Yang. Finite-time analysis of decentralized temporal-difference learning with linear function approximation. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 4485 4495. PMLR, 2020.
R. Sutton and A. Barton. Reinforcement learning: An introduction. MIT Press, 2018.
C. Szepesvári. The asymptotic convergence-rate of q-learning. Proceedings of the 11th Annual Conference on Neural Information Processing Systems, 10. 1997.
H. Tian, I. C. Paschalidis. and A. Olshevsky. One-shot averaging for distributed TD (X) under Markov sampling. IEEE Control Systems Letters, 2024.
N. Tsitsiklis. Asynchronous stochastic approximation and q-learning. Machine learning, 16: 185-202 1994.
J. N. Tsitsiklis and Z. Q. Luo. Communication complexity of convex optimization. Journal of Complexity, 3(3):231-243, 1987. ISSN 10902708. doi: 00.00160885--0644()79900000
R. Vershynin. Hiihh-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
H.-T. Wai. On the convergence of consensus algorithms with markovian noise and gradient bias. In Proceedings of 59th IEEE Conference on Decision and Control, pages 4897-4902. IEEE, 2020.
M. Wainwright. Stochastic approximation with cone-contractive operators: Sharp l-infinity-bounds for q -learning, 2019a
12

---

M. Wainwright. Variance-reduced q-learning is minimax optimal, 2019b.
G. Wang, S. Lu, G. Giannakis, G. Tesauro, and J. Sun. Decentralized td tracking with linear function approximation and its finite-time analysis. Proceedings of the 34th Annual Conference on Neural Information Processing Systems, 1111162221777. 2020.
H. Wang, A. Mitra, H. Hassani, G. J. Pappas, and J. Anderson. Federated temporal difference learning with linear function approximation under environmental heterogeneity, 2023.
C. J. Watkins and P. Dayan. Q-learning. Machine learning, 8:279-292, 1992.
J. Woo, G. Joshi, and Y. Chi. The blessing of heterogeneity in federated q-learning: Linear speedup and beyond. In Proceedings of the 40th International Conference on Machine Learning, page 37157-37216, 2023.
J. Woo, L. Shi, G. Joshi, and Y. Chi. Federated offline reinforcement learning: Collaborative single-policy coverage suffices, 2024.
B. Woodworth, J. Wang, A. Smith, B. McMahan, and N. Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Proceedings of the 32nd Annual Conference Neural Information Processing Systems, volume 31, 2018.
B. Woodworth, B. Bullins, O. Shamir, and N. Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Proceedings of the 34th Conference on Learning Theory, COLT, pages 4386-4437. PMLR, 2021.
7. Xie and S. Song. Fedkl: Tackling data heterogeneity in federated reinforcement learning by penalizing kl divergence. IEEE Journal on Selected Areas Communications, 4124):1227-1222, 2023.
T. Yang, S. Cen, Y. Wei, Y. Chen, and Y. Chi. Federated natural policy gradient methods for multi-task reinforcement learning, 2023.
E. Yurtsever, J. Lambert, A. Carballo, and K. Takeda. A survey of autonomous driving: Common practices and emerging technologies. IEEE access, 8:58443-58469, 2020.
S. Zeng, M. A. Anwar, T. T. Doan, A. Raychowdhury, and Romberg. A decentralized policy gradient approach to multi-task reinforcement learning. In Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence, UAI, pages 1002-1012. PMLR, 2021a.
Zeng, T. Doan, and Romberg. Finite-time analysis of decentralized stochastic approxima- tion with applications in multi-agent and multi-task learning. In Proceedings of the 60th IEEE Conference on Decision and Control, pages 2641-2646. IEEE, 202
C. Zhang, H. Wang. A. Mitra, and J. Anderson. Finite-time analysis of on-policy heterogencous federated reinforcement learning, 2024.
13

---

A
Additional details about REFINEESTIMATE
We outline below the pseudocode of the REFINEESTIMATE routine described in Sec. 4.1.1
Algorithm 3: REFINEESTIMATEE B,,,I,
Input: Initial estimate Q, batch size B. Number of iterations recentering sample size L, quantization bound D, message size .J
2: // Build an approximation for TQ which is to be used for variance reduced updates
3: for m = 1, 1.2..... .M do
4: Draw [L/M] i..d. samples from the generative model for each (s, a) pair and evaluate
Timm) (Q) according to Eqn. (9)
5: Send (T m) Q D.) to the server
6: Receive 1 17 m== 6 (T,, (Q) Q; J) from the server and compute (Q) according to
Eqn. 1O]
7: end for
8: Qo +QQ
9: // Variance reduced updates with minibatching
10: for ior1=1 1.,,...... do
11: for m = 1.2...... ........ M do
12:
Draw B i.i.d samples from the from the generative model for each (s, a) pair
Compute Q according to Eqn. (11)
14:
Send (( Qi-1i D, J) to the server
15: Receive 17 Em=1 ((QTT - Qi-1; D) from the server and compute Q, according to
M
Eqn. 12
16:
end for
17:
end for
18:
return Q1
B Proof of Theorem I
In 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 generic algorithm e outlined in Algorithm I 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 the heart of the sample-communicet trade-off. Following Li et al. [2023), the construction is first over small state-action space that allows us focus on a simpler problem before generalizing to larger state-action spaces.
complexity
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 off. Through careful analysis of the algorithm dynamics in the federated setting, we uncover the impact of communication the bias-variane variance trade-off and the resulting error of the iterates to obtain the lower bound on 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 thcorem.
14

---

B.1 Introducing the "hard" instance
We first introduce an MDP instance Ma that will use throughout the proof 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, denote the action set associated with the state The probability transition kernel and the reward function of Mr given follows:
Ao (1)
P(OJ0,
r(0, = 0,
(14a)
A1 (1,
P(1 = p
1(0 1 -p r(1,1) 1,
(14b)
P(1[1,2)
P(0 = - (1,2) = 1,
(14c)
A (1)
P(2 =
P(0 1-- r(2.1) 1) = 1,
(14d)
A3 (1)
P(3 1) =
r(3. = 1, (14e)
where the parameter 47
We have following results about the optimal Q and functions
37
of this hard MDP instance.
Lemma
[Li et al. 2023 Lemma 3J). Consider the MDP M₁ constructed in Eqn.
14 We have,
(*(0) Q" (0, 1) = 0
3 (1) 1 PP 4(1 - 7)
V*(1) =
V*(3) = (3, 1-
Throughout the next section the proof, we focus this MDP with four states and actions. In Appendix B.4, we generalize the proof to larger state-action spaces.
B.2 Notation and preliminary results
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 and the rescaled linear step size schedule, i.e., I+c,(1-9)}* where Gy > 0 a universal constant that is independent of the problem parameters.
the constant step size schedule, i.e, 7)t r for all t E 21,
We define the following quantities:
( 1
II 1=++1
(1- (1))))
77,1%
for all 0 0 k
(15)
where we take = 1 and use the convention throughout the proof that if a product operation does have valid index, we take the value of that product to be 1. For any integer 0 S r < t, we have the following relation, which will be proved at the end of this subsection for completeness:
II (1- (1-ma(1 - Yp)) + (1 7p) kmT+1
Σ Am++1
= 1.
(16)
Similarly, we also define.
1 4h
1
II (1 (1-n) -%)
for all 0 k: St
(17)
i=k+1
which satisfies the relation
II (1 mp) +
1
100
1.
(18)
k=T+1
k=r+1
15

---

for any integer 0 S r < t. The claim follows immediately by plugging p 0 in 16 Note that for constant step size, the sequence Th clearly increasing. For the rescaled linear step size, we have,
(1)
(1 - C.y (1 cny 7)%
(19)
%
(t)
Th Th-1
m1)
(t) whenever Cn - 1-7" Thus, 7 is an increasing sequence as long as Cyj S 1- Similarly, Mi is also clearly increasing for the constant step size schedule. For the rescaled linear step size schedule, we have,
(1)
1/6
1jk
S 1
1/3
T
17
7p)
176-1
whenever Cy S 1-7"
The last bound follows from Eqn. (99)
Proof of (16). We can show the claim using backward induction. For the base case, note that,
- 7p)m) (8) (1 mp)m (1 7p) + 7p) - -xp)mm
=1 ne(( 7P)) 7- <p)
II (1 m. -Tp)), k=t-1
required. Assume (16 is true for some We have,
(1 - pp)
n = (1 wp)nt + (1 - (p)
Σ k=++1
(0)
k=
(1 >p))
II
(1 n) -pD) +1
II k=T+1
m 7p)
k=7+1
7k - -p));
k=y
thus completing the induction step.
Sample transition matrix. Recall Z E S!SIIA1 is random vector whose (s, a)-th coordinate is drawn from the distribution P(-|s,a) a). We use Prt denote the sample transition time and agent m obtained by averaging B i.i.d. samples from the generative model. Specifically let (2,3) 18 denote collection of B i.i.d. copies of Z collected at time t at agent m. Then, for all a, s',
B
(s'1ss a) =
(s'sss)),
(20)
B
where P. a) =
(0:00)=112220 112[)(s,a) = 5'} for E.
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 (0, = Von(()) = for all agents m E [M] and t [T]. This follows almost immediately from the fact that state 0 is absorbing state with zero reward. Note that Q (0, 1) = V (0) = holds for all clients m E [M]. Assuming that Q (0. ViT (0) for all clients for some time instant - 1, by induction, we have,
Q f 10, 1) (1 n 2 (0, 1) + ne (M = 0.
Consequently, QTh 1) = 0 and 1/2h (0) 0, for all agents m, irrespective of whether there is averaging.
16

---

For state 3. the iterates satisfy the following relation:
Q 1/2(3, = (1 - 7) (1)0 (3, + n1(1 + (V=
= [1 -1:)Q[-1(3311 + 7o 1
= [1 - 7/ -)) (3.
+ +3
where the second step follows by noting (3( Q1"" (3, 1). Once again, one can note that averaging step does not affect the update rule implying that the following holds for all m E [M] and E (T]:
ViTH (3,
E 1=1
[I v=+++
a (1-mm(11-
7))) (1-m((1-)))
-
1
II
(1 n - -
m
(21)
where the last step follows from Eqn.
16 with p 1.
Similarly, for state 1 and 2, we have,
(2,12(111) = (1-7)]Q(1(0 +
(1)) p1 (11,)))))))
(22)
1 = (
+ + (1)1, (1))
(23)
12, (101)))(11mm11100 =1--m) + (1 (1 (2,,, (
(24)
Since the averaging makes a difference in the update rule, we further analyze the update as required in later proofs.
B.3
Main analysis
We first focus on establishing a bound on the number of communication rounds, i.e., CCrauna (of) (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 CCbi(
To establish the lower bound on CCrouna for any intermittent communication algorithm st analyze the convergence behavior of of on the MDP MM, We assume that the averaging step in line 6 of Algorithm is carried out exactly. Since the of compression only makes the problem harder, it sufficient for us to consider the case where there is no loss of information in the averaging step for establishing lower bound. Lastly, throughout the proof, without loss of generality we assume that
1
log N S 1 1-7²
(25)
otherwise, the lower bound in Theorem I 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-y] and for rescaled linear learning rates, the constant Gn satisfies Gy 2 log
2. Large learning rates with small yr (BM): For constant learning rates, 1) 2 [1->] and for rescaled linear learning rates, the constant G, satisfies 0 Gr I log T < 1 (c.f. 25 Additionally, the ratio yr BM satisfies
1-7
WT < 1-7
BM
100
3. Large learning rates with large /r/ (BBM We have the same condition on the learning rates as above. However, in this case the ratio
or satisfies BM
1-x
BM
We consider each of the cases separately in the following three subsections.
B.3.1 Small learning rates
In this subsection, we prove the lower bound for small learning rates, which follow from similar arguments in Li et al. 2023
17

---

For this case, we focus on the dynamics of state 2. We claim that the same relation established in al. [023] continues hold, which will be established momentarily:
Li
(T)
E[V
M Σ
B[V
(0)
1 - 7
(26)
1 -p
Consequently, for all E [M], we have
(T)
1
(22)
(27)
--
To obtain lower bound on (2) [ (2)), we need to obtain lower bound on T
(T)
which from
Li et al. 2023 Eqn. (120)) we have
T
T
log(1))) (2))
2 1.5
Σ
nl - 7p) -
2
-2
2 e
log T
t=1
[=1
when T> 16 for both choices of learning rates. On plugging this bound (7 we obtain,
3
BIIQT @*11oo) (2) QT (*) E (2))
(28)
4c VVNN
holds for all m E [M. N 1 and M 2 2. Thus, can be noted that the error rate ER( N, M) is bounded away from constant value irrespective of the number of agents and the number of communication rounds. Thus, even with CCround = Q(T), we will not observe any collaborative gain if the step size is too small.
Proof of 26 Recall that from
24 we have,
QThh 1/1 = (2 " (212
Here, QTh 1) (2) as the second state has only a single action.
When / is averaging instant, have, (2, On taking expectation on both sides equation, we obtain,
(2) = (2, = (1 n) ne(1 +
(29)
E|V.'T (1 -->>) (2)] + nh
(1 V (2)] + 7 1 (P, 1V
(1 nh TvV [2) + nh + [y]]
(1 (1 EVT (2)) 1)t-
(30)
In the second step, we used the fact that P. (2 1) is independent of (2).
Similarly, is an averaging instant, we have,
M
= (2) = M j=1
(211/2(2,1)
M
(1 T
(2) (2)+ +
Σ
ne mm1++7/022.1)__000
(31)
M
M
J=1
Once again, upon taking expectation we obtain.
1 M
E| = (1 - m²) M
Σ
(2)
+
Σ
m( 2
M
j=1
18

---

1 M
M
= (1 (1-mh) 71))
Σ
BLV
+
1
Σ
nh
M
M
j=1
j=1
1 M
= (1 - ne (p))
B[V2-1 (2))
+ +1.-
(32)
M
Eqns.
30 and
32
together imply that for all & E [2],
1
EIV"
(1 10-mm(1-- 7p)) (p)))
1
=IV=((211
+ nm-
(33)
.
M
m=1
On unrolling the above recursion with Vi0h for all m [M], we obtain the desired claim (26)
B.3.2 Large learning rates with small
Tr BM
In this subsection, we prove the lower bound for case of large learning rates when the ratio BM is small. For the analysis in this part, focus the dynamics of state Unless otherwise specified, throughout the section we implicitly assume that the state is 1.
We further define key parameter that will play key role in the analysis:
== min (k N: V 2 k, n 7 S 3m)).
(34)
It can be noted that for constant step size sequence T and for rescaled linear stepsize T = 7/33
Step 1: introducing an auxiliary sequence. We define an auxiliary sequence (Tr(() for {1,2) and all t = 1, T to aid our analysis, where we drop the dependency with state s I for simplicity. The evolution of the sequence Qin is defined in Algorithm 4 where V maxae (a). In other words, the iterates (Ộ'") evolve exactly the iterates of Algorithm except for the fact that sequence {QiT) } is initialized at the optimal Q-function of the MDP. We would like point that assume that the underlying stochasticity is also identical in the sense that the evolution of both Q and QIe is governed by the same Par matrices. The following lemma controls the eтror between the iterates Q!" and Q allowing us to focus only on Q
Algorithm 4: Evolution of Q
1: Input: T, R. (m)) {tr 1 B
2: Set Q (a) - Q' (1, a) for [1,2) and all agents m
// Different
initialization
3: for = 1,2...., do
4: for = 1, ...,, M do
5: Compute QThh according to Eqn.
6: Compute T according to Eqn. 8
7: end for
8:
end for
Lemma 2. The following relation holds for all agents m E [M], all E [T] and E (1,2]:
2 I - m. 7)).
(1, -
By Lemma 2 bounding the error of the sequence T allows us to obtain a bound on the error of Q To that effect, we define the following terms for any < and all E [M]:
(a) = Ô.h (a) (1, 1,2;
19

---

A maax
max (a). aE{1,2)
In addition, we use 4 Em= to denote the error of the averaged iterate and similarly,
A mmax = max (a).)
(355
ae (1.2)
We first derive basic recursion regarding (T) From the iterative update rule in Algorithm have,
(a) (1 n) (1)44(((00) + (1 -
= (1 - 77) A (a) + n (11, - -P
[1 7h m A - VV (PTT - V-1))
(1 - 7: 1- (a) + 7/ (p4 + (P (1]1, - vm)
Here in the last line, we used the following relation:
A n
max (ÔTh (a) Q" (1. max (²"(aa) V* D. V*)),, (E(1,2)
Lmax
aE(1.2)
as (+(2))-v(()
Recursively unrolling the above expression, and using the expression relation: for any t' t when there no averaging during the interval
obtain the following
II - mh) )
(a)
(a)+
Σ
Mk Yp
Imax + (Pr (1 vm) (36)
AA=1/41
k=t'+1
For any t,, with t' < we define the notation
1 fp = II (1 nk),
(37)
k=t'11
(a) =
The
(t))
(1
a 1,2;
(38)
+1+1
em mmax == max em (a).
(39)
(1(1
Note that by definition, E[gr (a)) for a E {1,2) and all m, t' and t. Plugging them into the previous expression leads to the simplified expression
(r(a)=)r.AApa))
Σ
(1) T
ypA
k 1.mxx
em (a).
Lk=++1
We specifically choose t' and t to be the consecutive averaging instants to analyze the behaviour of A y across two averaging instants. Consequently, we can rewrite the above equation as
(a) Ar +
Σ
The Ap maax
(a),
(40)
Furthermore, after averaging, we obtain,
M
M +
A, = Pr.
1
Σ
Σ
(2) 7
ApA
Σ
(a).
(41)
M
maxx
M
m=1
Lk Am
m=1
'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.
20

---

Step 2: deriving a recursive bound for E m, Bounding 40
we obtain,
T2 maxx 2 P SH +
Σ
(1)
cm m,,ax
sr. (rr((A((1) - (e(2),, (42a)
I.max
L==+++
A 1,max "p
Bv max
Σ
(1)
yp
k
I.axx
(42b)
L=#++1
where in the first step we used the fact that max + , 02 ba) 2 minfaj, a²} max(b], b2) max(ar, 02] + max (b1, |aj 02)
(43)
On taking expectation, obtain,
E T2 I max
2 per
max] +
(1)) Ti
TpE maxx
+ E
em Stt mm..
Tr (2))..
A=1++1
(44a)
B Lmax
S S B Av max] +
(1) The
yp
A k- max
+
E max
(44b)
R=1+1
Similarly, using (41 and 43
we can write,
A t,aax Sr Ar max +
I M
Σ
Σ
Th
(11)
yp m
1,max
Ar (2)
Lk=''+1
M
M
+ max
1
EP (1),
M Σ (7,(())
(45a)
M
m=1
m=1
A Drr.BB.
maxl
+
(1) Th yplE A x 1
PP
EE
Ar (1) (2)1]
M
Lk=!'
M
M
}
+ E
max
(1)
2T St
(2)
(45b)
M
M
m=1
m==
On combining 44b and 45bb.. obtain,
A [rmax]
M
E
m
max
Blen
[.max]]
BBI (1) - (2))
m=1
M
1 M
+
E
(1),
SP (2)
(46)
M
m=1
In order simplify (46), make of the following lemmas.
Lemma 3. Let < t be two consecutive averaging instants. Then all m [M],
E Elem m.ax) >
II (1 ma -(p) max
St maxd
Σ
T
10
-1
A=P+1
k=
Bl - (2)]]
where [z]+ = max 0}.
Lemma 4. For all consecutive averaging instants t', satisfying max 2 1/n, and all E [M], we have,
E Lma.
240 log
180
1/
(r((1~)
21

---

MM
M
spee( (2) }
E
max
Σ m=1
EP (1),
Σ
M
M
240 200 log
180BM
m=1
201rr
where V
B(1
7)
Lemma 5. For all t [tr we have
8U1
(1) - (2)1 <
3BM (1 7)
Thus, on combining the results from Lemmas 3 and 3 and plugging them into following relation for t, t' 2 T:
46
we obtain the
B[Ar,max 2
II (1 (1-1((1- - -p))) E Ar max] + E k=1+1
Σ
10
k=
M
(F,(()) (2) |
1
B Ac
De (1) De (2) +
max
ST
M
M
m=1
m=1
2 -1--10 (1-77(1 - -xp)) (1)))
18 Ar maxl +
1- (1 - 17, -xp))(-
V
1
1st
t-t
8
5760
1808 (r((-
(1 (1-1p)
v+1
7/-
2(1 - -1r)²-
8T1
+
V
t
2
8
(BM(1-7) -
240 log
180 To (1-7)
4 M
T/
(47)
where we used the relation fea S (1 --rrr+++ as well as the value of defined in Lemma along with the fact
- -12 1- (1 - 77 (1-1-770 (1p
Σ
(t)
(48)
24(1 - 7p
k=1++1
for all 1,6' 2 r such that - l' 2 8/1/.
Proof of 48
We have,
1k
(1 - n1 (11)-
-1
k=
k=t'+ +1
i=k+1
t
(1 1/ (1 - -TD))
h= +1
i=++1
(1 7/ (1 - 7p)) -
1/1
k=+++
1 (1 - 17 (1 - 7p))
1/t
1/ (1 - -p))
1 (1 17 - )pp)
1.
(49)
3(1 7p))
1 (1 17, (1 --p)
To show (48). it is sufficient to show that
>
for t 2/2 8/n.. Thus,
3(1 - (p))
7
for 1' > 8/n, have,
(1 7/ (1 (pp
exp(-1771 - <p) (1 (d-1") 1'))
3(1 111-7p) 7P)
3(1 7p)
22

---

- exp(-8(11 (-8(1 7p))
(50)
3(1 -7p)
Since y 2 5/6, pp - 2/9. For x S 2/9, the function f(z)
1-e
2 8/7, proving the claim.
32
Step 3: lower bounding E max)- We are now interested in evaluating max] based on the recursion 47.. To this effect, we introduce some notation simplify the presentation. Let
R, = min tr 2 7}
(51)
For r R R. we define the following terms:
I, == E A m,,,ax]
a, == (1 77 (1 7p))
3, == (1 ./ -
I, = {r 2 r' > Rr tp - tr-1 2 8/1rr
C1 =
5760 log
180B
(1 -0-770 7p) V 1
(1((1-)
321/T
C₂ =
3BM(1 77
C3 240 log
180BM (1-3)
= VM
With these notations in place, the recursion in 47 can be rewritten as
Iy 0, 3,C₂ + C3l(fr I,) (1 (
(52)
for r 2 Ry, We claim that x, satisfies the following relation for r 2 Rr + (whose proof is deferred to the end of this step):
r
Zr 2
II R,
04
IR.
Σ
Be
II ai lik+1
C2 + Σ
II
a,
1 E Ix)Css
k=
R=R,
+1
W=
+
II
ai
(53)
IEI,
iEI,
where we recall that if there is no valid index for product, its value is taken to be 1.
Invoking 53
for r R and using the relation 2R,-1 2 0. we obtain,
R
R
R
2
Σ
II ai
C2
Σ
II Lisk+1
as
Colfke
II i
II iT
k= R,
Ni=k41
km
R.
2 RC2 + Ci
II ai
Oi
IRIR
iEIR
2 -R \
32mF
II as IEIn
a;
V F 1
(1
iETR
5760 log
180 (-(1->) (1
-pp)
(54)
where we used the fact Be [ a:)
< 1 and that Cg 2 0. Consider the expression
II a. II (1
(1 2 - n (1 yp) Σ
(t:
f
(55)
RR
TT
TT
T
23

---

Consequently,
1 II 04 =1 (11
(1-))())
(p)) 2 cxp (- 7P) (T - -T)). (56)
IETA
Note that 7i satisfies the following bound
8
8R
T : Σ (t: - 1--111) (R [Ta])
S
(57)
7
ig
We split the remainder of the analysis based the step size schedule.
For the constant step size schedule, i.e., 1/: = 1j 2 (1 (1-7)7- we have, R = 0. with and
to 0 (as all agents start at the same point). If R S 96000 log( m(1-))
then, (55 (6
and (77 yield the following relations:
8R Ti
T
12000 log (88NN)
32R(1 7)
II
2 1 111 (1-))) Ti 2
21
3
9000 log 1og(180N))
1 II as
2 1 exp
(T 21 exp
9000 log (og.(1800))) (180N)
SEIn
On plugging the above relations into
54 we obtain
400
2R
(58)
96000 log
180
(1 (1-7)
v++1
5VM
n1
20n
where recall that v/
Consider the function f(x) 2+1
We
3B(1
7)
5/M
claim that for i E (M. and all M
2M2 2,
7
( 2 min (1r, 1)-
(59)
20
The proof of the above claim is deferred the end of the section. In light of the above claim, we have,
40
7
2017
ER 2
min
1,
96000 log
180B (((
(1
7)
20
3B(1
7)
40
7
20
min
(60)
96000 log (180N)
20
1 1-
3(1
where we used the fact that M 2 2,
log(1/2) an increasing function and the relation
Va
U
20n <
15 1
M
3BM(1 -
Next, we consider the rescaled linear step size schedule, where 7 = T/3 (cf. (34). To begin, we assume tR, S max
6n- (1 7p) }. It is straightforward to note that
3T
1 61,, (1 -p)pppp))))
3T
if c, 2 3 if Cn <
max
T
T
Gn- (1-2p)
If <
then,
(55
56
and
57 yield the following rela-
384000(1 -n) log
(5+t..)
tions:
T S
8R
II iRTR
1 21 1- 11 - 7p) - 7 32R(1 (1 -2)
1 36000
nr
24

---

For Cyj 2 3, we have,
1 II ai
2 1 exp
(-1) (1-111110 -pp) (T - -RR, Ti))
iEIA
(73 Gy(1 - -7)7)
(1 -) +
32R(1 - 7)
2 1 - exp
expp
3
1
2(3 + cn))
where we used 7 2
1. in the second step. Similarly, for Cop < 3, we have,
I-y
1 - II Oi
1 - exp (- vP) (T- LR, - -Ti))
iEIn
32R(1 -7)
2 1 - exp
3
10
On plugging the above relations into
54 we obtain
18vI.6
JR
180. 384000 log
(1 () c,)
v+1
18VM
[r(1 (1-))
18vI.6
min {
201T
1 (1.V
384000 log
180
(1 (5 + cn))
20
3B(1- -7)
1r (1-
18v1.6
7
1
20TT
min
384000 log
180
(5 + cn))
20
7
V
3B(1 733
|rr(1 (1
18vI.6
20
min
384000 log (180N + log N)) (5 log N) 20
3B(1 log NV 7)a
(61)
where we again used the facts that M 2 2, on v log N, log(1/2) is an increasing function and the relation
V/
20mr
1
M 3BM(1
Last but not least, let us consider the rescaled linear step size schedule case when fR. max 3T T T
61 (1-1pp J. The condition implies that the time between the communication
rounds R, and R2 is at least To == max
5T (n-(1--p)) Thus, (47 yields that
12
E D(A 2
1 (1 (1 TD))
V 2(1 -mT))
8HT
5760 log
180
(1 7p)
1+1
3BM - 7)
Byr
(62)
Using the above relation along with (53). we can conclude that
RR 2 (1 - 1/, 11 (1-7p)) -tx 1- 17, (1
To
5760 log
180
(1 7p)
8ip
- - To. (1 1n (((11-p))) -
RRC,.
(63)
3BM (1-7)
25

---

In the above relation, we used the trivial bounds C1, C3 2 0 and crude bound on the term corresponding C22 similar to (54). Let us first consider the case of cn 2 We have,
5(1 7)T
2 1
- - 1/- (1 ->p)) 2 exp (-1/r - -1015/122 2 exp
3(3 + c7(1 - ->)
3 + Cp
T
(1-
2 1 -2 2
(1 - (1-111111))) (1-p)= (R 21 - 17 (1 - 7p)
2
4
(3 cn - ))
3
Similarly, for on < 3, we have,
-7/ - 7P) + /
27'
1-(1- 1-11-1 7/ (1 - (1-7p)) To 2 - exp
3
6
8(1 7)T
1
2 1 - exp
2 1 21- 5/18
3(3 + Cy 7)T)
6
17 (1 - (p)
5
(1-7)(1-7p)) T
1
6// (1 - -
6
The above relations implies that (1- 17 (1 - 7p)) (1- 77 (1=(1= (1-2))))2)) 2 c
for some constant c, which only depends on Cyy On plugging this into (63). we obtain
relation that is identical to that in (54) up to leading constants. Thus, by using similar
sequence of argument as used obtain (61). we arrive at the same conclusion as for the case of tR. < max 37 T
6n. (1-)))
Step 4: finishing up the proof. Thus, (60). (61) along with the above conclusion together imply that there exists a numerical constant co >> 0 such that
BiVE (1) - (+)I 2 E max
CD
min
1
(64)
log
3
N
1- V (1-
The above equation along with Lemma 2 implies
B(|VT V
(LIl
Co
min
1
1
7o (1 7)). (65)
log 3
N
1-
(1
7)aN
On the other hand, from
21 know that
1
E| - [3)] -
II
17(1 - 7)).
(66)
Hence,
B||[T - Q- [|x]] 2 E
mmax (|v7((3) (3)
max { |17 (3) V (17 (1))
max
m 7)) min
1- V (1-
1
1
n -111 711
min
(67)
2
1->'V (1 (1-7)*N
where the third step follows from (65) and (66) and the fourth step uses max(a, aa, b) 2 (a + 6)/2.
28 and 67 we can conclude that whenever CCround (a-vilog' n)
Thus, from
CR( Ω log NVN for all values of M 2. In other words, for any algo- rithm to achieve any collaborative gain, its communication complexity should satisfy CCround = 1 [og")]og" N. as required.
Ω
26

---

Proof of (53) We now return to establish 533 using induction. For the base case, 52 yields
TR,+1 2 +RRR C + C3l(R, + +1,+1} + (1 aR, -1-- + IR,41}. (68)
Note that this is identical to the expression in (53) for R, +
(1-
II ai
1
II
at = (1 an ar, + E
+R,+1)
based on the adopted convention for products with no valid indices. For the induction step, assume (53) holds for some 2 R, + 1. On combining (52) and (53). obtain,
1y+1 2 a,+1I, Br+1 C2 + Cg1((r + +) E I+t + (1
+1EI++1
r
2 ar+1
II ai
RR. - ap-1
Σ
II a4 1=++1
C2 + ar+1
Σ
II as
Colsh Ix}
i= f2,
k=
k=
li=k+1
+ ar+1Ci
II
ai
1 II
Bp41
C2 +
E +)
(1
(1-+))+(((+) I,+13
iEZ,
RR.
Σ
Bk
II 03
C2 +
Σ
Il at Cgl(ke
R1+1
km R.
Nink+1
k R,
Wmk+1
1 1
+ ar+1Ci
II ai ieI,
II
ai
+ (1 - ((--o)))G((0++)))
(69)
VEI,
If (r + 1) & I,41, then (Il 0:)
(1 Iliez a:)
-I-E,, oi) and artl (Tlgg ai) =
Consequently,
art1Ci
II ai
(1-
1- II ai +(1
)000=++ - + 1)
as
a4
I
EE
I
T
(70)
On the other hand, if (r + 1) E Ir+1, then (IIizz, os) (Ilszzes) ai). Consequently, we have,
(1 1
art1Ci
II i
a1 ai
ai
+ (11- II+11
VEI,
Cr++1Ci
II ai
1
II a + -ar+1)
(EI.11
iEI,
ai
ar+1
1
II ai iET,
+ (1 ax41)
> C1
II 04
1
0
(71)
iEZ
Combining 669
70
and
proves the claim.
Proof of 59
To establish this result, we separately consider the cases x < and x 2 1.
When < 1, we have
7
f
2 x
>
(72)
T +1
5
2 5 M
20
where in the last step, used the relation M
> 2.
27

---

Let us now consider the case a 2 1. The second derivative of f is given by f=(x) 2[++1ys Clearly, for all z 2 1, fr implying that f is a concave function. It is well kooln that a continuous, bounded, concave function achieves its minimum values over compact interval the end points of the interval (Bauer's minimum principle). For all M 2 2, we have,
VM
f(1) = 2 5VM 2
20
S(VM)
2
VM
1
5
20
Consequently, we can conclude that for all E [1, MM.
((x) 7
(73)
20
Combining
72 and 73 proves the claim.
B.3.3 Large learning rates with large
Or BM
In order to bound the error in this scenario, note that nr updates in the fixed point iteration. Thus, when dr BM controls the variance of the stochastic BW is large, the variance of the iterates 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 al. [2023). For all E [?']. define:
M
V2 = Σ (2).
(74)
Thus, from
33 we know that IE[V obeys the following recursion:
E (2)) = (1-mm11 (V + me.
Upon unrolling the recursion, we obtain,
T II
T
VV
(1 m1 -D)) E (2)+
Σ
Tl
(T)
kmt+l
Thus, the above relation along with (66) and the value of (2 yields us,
(2())) = II
(1 - ne(1 - -D))
1- (T----IVVVV
(75)
k=++1
Similar to Li ct al. 2023), we define
7' min 0 f'st'sTa <T-2
E[(V))²
4(1 7)2 for all a +1
such a 7' does not exist, implies that either BE((T)?] -パ-ン:p or B[(V+-1)* < |---プ the former is true, then,
(*(2) E (2) = 3
E(( >
(76)
4(1 ((1~))
4(1 71
Similarly, if if 1- 4(1 4(1-7)2 it implies E V 11
Using 33
have,
2(1 2(1-
2
E(V (1- 1T (11p) + 7 < E (2))
2(1 - 7)
6(1 -1)))
3(1 - 7)
Consequently,
3
V*(2) -
(77)
4(1 - 7) 3(1 y) 12(1 - 7)
For the case when r' exists, we divide the proof into two cases.
28

---

We first consider the case when the learning rates satisfy:
T
II
(1-1(1ppp 2 2
(78)
A=r'+1
The analysis for this case is identical that considered in Li et al. [023]. We explicitly write the steps for completeness. Specifically,
II (1 (1-ma(1- (a(1-)901)
(1- E[V , (2))
(2(2) [2)]
1-
k=r/+1
2 2 4(1 ((1
[E((V, (2))
2 4(1
(79)
2(1 (1-7)
8(1 71
where the first line follows from the third line from the definition of
75). the second line from the condition step sizes and
We now consider the other case where,
T
0 S II
(1
me yp) 2
(80)
k=r4+1
Using
[Li et al.
2023
(134), for any t' < t and all agents m, we have the relation
(2)
1
II (1
TA - 7p)) (1p)))
1 (1-1--10 V2T
PP
km0+1
Σ A=1'+1
(0) The
7 (2 - v3-
The above equation is directly obtained by unrolling the recursion in 24 along with noting that (2, 1) = V2(2) for all I. Consequently, we have,
T
Vr(2)
II
(1
na -7P)
1
V..
p
11-pp
k=P+1
Σ
Σ
(T)
(PT (2(2) p) v
(81)
M
k=1'41
Let (Fi)T be filtration such that F. the o-algebra corre- sponding to {IPmT (2
is straightforward to note that a martingale sequence adapted the filtration Fg. Thus, using the result from LL al. 2023 (139)] can conclude that
M EM Th (Pp (2(2) {
(2)
M
p) [0-1]] (82)
Var Var(V,(2)) E
Var
(
M
A==
m=1
We have.
Var
1
Σ
The
x (P (2(2) p3 F
M
m=1
M Σ
Var
(1) ( (2 V2m F
(TT (T)
M
BM 7 pp - p)
M Σ (V)2(
m=1
29

---

(47 - 1), (1h (m (V (2))
(83)
9BM
where the first line follows from that fact that variance of sum of i.id. random variables is the sum of their variances, the second line from variance of Binomial random variable and the third line from Jensen's incquality. Thus, (82) and (83) together yield,
(1 (1-7)(47 1)
Var Var(V[(2 (2))
Σ
(M
(T)
9BM
k=7442
(4 -1)
T
Σ
1)
(84)
9BM
4(1 7)
k=max{
where the second line follows from the definition of r'. term in the above relation. We have,
We focus on bounding the third
Σ
Σ
II (1 (x (111-)p))
1k
?]k
k==aax ++2
m=max
(=++1
(1 1r (1 -yD))
1T
i=++1
Σ
(1 - 1/r(1 - -1pp))
1/T
k=maxfr',
1 (1 - 177 (2))) -mxx-=ax -maxtr' ()1-))111)
2 1/7 -1 - 17 (1 - -pp)
2 I/T 4(1
c'.
(85)
where the second line follows from monotonicity of f) 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:
8/9
for constant step sizes,
1 (1 Tr (1 7p)) 2
max ( 111)) 2 exp (-3 (33ax(L.cn)) for linearly rescaled step sizes
(86)
Thus,
and
85
together imply
Var (T(()) 2
(47 1)
(1 m)y
36BM 7))
k= +2
c
1/2
c(4 -
1
(87)
144(1-7)
BM
144(1 -
100'
@r where the last inequality follows from the bound on BM
Thus, for all N 2 1. we have,
- - -(V))))))))((()--VVVVV----------
(ar(2)(2)) >
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 CCround I(T). we will not observe any collaborative gain in this scenario.
Proof of
86
To establish the claim, consider two cases:
30

---

7' N Under this case, we have,
7- ( -77 -7: -pp)) (
$ (1 7/ pp)) x
II
(1-mm(1- 7D)) -
k=
(88)
where the last inequality follows from 80
T 2 r': For this case, we have
(1 ( 2 max () (1 17; 7p)))((-~-11
2I'n, (1 YP)
$ 77 (1 -p)) exp
(89)
For the constant stepsize schedule, we have,
(T (- -yp) -111pp
27 1
4(1 (11~7) ) exp
8
exp
exp
(-9)
(90)
3
(1- 7)T
For linearly rescaled stepsize schedule, we have,
2Tn, (1 yp)
2T
1
4(1 - -
8
exp
3
S exp
(33
3 1 - 7)-33
3
exp
3 max (91)
On combining
888
89
90
and
91
arrive at the claim.
B.4
Generalizing to larger state action spaces
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, instead consider the following MDP. For the first four states 2,2,3,, the probability transition kernel and reward function are given as follows.
Ao {1}
P(O 1)
r(0, 1) 0,
(92a)
A1 f1,2, [A]
P(1[1,a) = P(0)1,a) = 1 r(1, = 1, L E A
(92b)
A [1}
P(2 =p
P(0 = 11- r(2, 1) I,
(92c)
As = {1}
P) =1
r(3, 1) =
(92d)
47 The overall MDP is obtained by creating S copies of the above
where the parameter
3y
MDP for all sets of the form (4r, 4r+1, 4r 2, +r++3 for S S1/4-1. It 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 CCround implies the bound CC.it = as every communication entails sending 12(1) bits.
log
To obtain the general lower bound on bit level communication complexity, note that we can carry the analysis in the previous section for all |A// pairs of actions state 1 corresponding set of states {0. 1, 2, 3}. Moreover, the algorithm L needs to ensure that the error is low across all the [Al/2 pairs. Since the errors are independent across all these pairs, each of them require bits of information to be transmitted during the learning horizon leading to lower (1 log"
the
Ω
Note that since we require low for eιror, of needs ensure that the error is low across all the pairs, resulting in communication linearly growing with [A]. Upon repeating the argument across all |SI/4 copies of the MDP, we arrive at the lower bound of
bound of Ω
LA
(1->) (1->) log"
CC = Q
[A)LA
log
31

---

B.5
Proofs of auxiliary lemmas
B.5.1 Proof Lemma
Note that similar relationship also derived in Li et al. 2023]. but needing 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 straightforward to note that the claim is true for = 0 and all agents m {1, 2, ..... M. For the inductive step, we assume that the claim holds for 1 for all clients. Using the induction hypothesis, we have the following relation between (1) and 1i=
V (1) max Qthh (1, 2 max (a) 1 aEf1.2)
II
m1 7)) 1-1
1
7) 7)).
aE(1.2)
(93)
For & & (tr M and E (,, we have,
0 (1. (a) = Q[ ()) - 1/-1/2(()
= =11 - 2= ( (1
+
(1 m: (Q (1|1, - (0) nn PMMH (1l (V] 1
2 (1 m)
t-1
1-1
(1 - 7)) P.
71 - 7))
-
==1
t-1
t-1
m))
11(11 -7)) 7K
2
Tue -)))
2
7i(1 7)))
(94)
Fort E [t and E [1,2], we have,
M
M
QT" - (a) = Σ
1
Q (1,
Σ 1/((a)
M
M
m=1
m=1
M
1
(1
(1,
M
m=1
M
M Σ (11 (1
1
(1 ne) (0
(1,
vm
M
[ n.(1 7)),
(95)
where the last step follows using the same set of arguments as used in 94 The inductive step follows
from (44 and (95
B.5.2 Proof of Lemma
In order to bound the term E t recall
B ).me we make use of the relation in 44ah. which we
B[er
Imaxx
E[Am
Prr Avr max] +
Σ
mh APEAAA max]
(1))
+ E Elem m...mll
1=141
32

---

To aid the analysis, we consider the following recursive relation for any fixed agent m. y (1 1/t 3 + (7pP99--1 El d,max))).
(96)
Upon unrolling the recursion, we obtain,
1
yt =
II (1 - mc)
yu +
Σ
7
II (1 mh)) k=++1
YPUk-1
R=8++
1=0++1
Σ
II (1 mi)
k=t++
k=++1
(t))
= Pur +
ypyk
+
m.md
(97)
k=1++1
k=1+1
Initializing yr-
EE| Dr max in 97 and plugging this into
44a have
m E|
mmax
where used By rewriting (96 as
Mk
(t)
S (cf. (8
We now further simply the expression of yr.
Vt
(1 T/ >p))) + (E
it is straight forward to note that is given as
yt II (1 m= - ye + R max
Σ
M/
(t)
(98)
k=#+++
k=
Consequently, we have,
E A
[.max]
E St....m
E A .max] II ne(1 7p)) k=t'+1
t
Σ
(t)
- (v, (1)
(2)].
k=+'+1
(99)
We can consider slightly different recursive sequence defined as
Wt (1 1/ )))))) Wt- 1): +) (7pw:-1).
(100)
Using similar sequence of arguments as outlined 96
98
we can conclude that
wy = [ then [[ 2 we + E[ maxx consequently,
Pe Ag (1) (2) and
E m [max]
N
II (1 -1- m1 - 7p))
E A max] + EEST"...mm. Ar,,B (2))
(101)
On combining (99) and 1011. we arrive at the claim.
B.5.3
Proof of Lemma
We begin with bounding the first term [ maae): the second bound follows in an almost identical derivation.
33

---

Step 1: applying Freedman's 's inequality.
Using the relation max(a, b}
a+btta-b we can
rewrite [S as
(1) + (2)
Sr - (2)
E St Lmax
E
E
2
St (1) - 5 (2)
2
E
(t))
(Pk
7
PT
(1
P (111,
(102)
2
kmd++1
where we used the definition in and the fact that [[5F),(1)) = E(srT, = 0. Decompose CY,
38
B
L
Se
Th
(P - PR (1), =:
Σ 21
(103)
B
km
b=1
where for all L
21
pm k()).0)) (1)11)
Pr (()
21),, k()-1
with
A(1) = + b(1) = ((1 1) mod B) +1; L-
Let {
a filtration such that F1 the o-algebra corresponding to (PMG) kG))6O) (1|1, 1). RG)), (1|1, 2) It is straightforward to note that { is mar- tingale sequence adapted to the filtration ( We will use the Freedman's inequality [Freedman) 1975
Li et al. 2023 to obtain a high probability bound on (r
To that effect, note that
sup |2 S sup
(()) (u(l)
(PR (111,1) - MC (111,2)) V
B
(()
7
< Ms(())
B(1 7)
1}t
$ B(1 77)
(104)
where the second step follows from the bounds [(PK()
k()),0)) (1 pm k())0())) 60) (1 <
1 and the fact that ` is increasing in and pm k()) < - and the third step uses S 1-
k in this regime. (cf. 19
Similarly,
2 22
Var (1 $
[i(l))
((t)
fm (()))=)²
Pm Var M().o)() (1/1, 1) -PRO (1)1,2)
B
7.2
(t)
2p(11 - p)
B - 2)²
(t)
2
2
1k(1)
(105)
3B2 7)
Using the above bounds 104 and (05) along with Freedman's 's inequality yield that
8208(2/8) 31 7)
Σ
2
41p. 1og()
Pr
>
$
(106)
3B(1 -7)
1=1
34

---

Setting 60 [1-2)² 2
BllsT" 11]), with probability at least
8p. it holds
8log(2/60)
4n log(2/0o)
Thk
(1)
D.
(107)
3B(1 77
3B(1 - -7)
1=
Consequently, plugging this back to
102 we obtain
El
2
FlIST 1I (1577 S DH
2
1
Ells??, 121 (1 S DH]
2D
1
(E(157,,
||- Bl|s7, ( (157 DH]
2D
1
Pr > D)
1
12]
ス
TE 117,711
(108)
2D
(1 - 7)2
4D
(t)
Here, the penultimate step used the fact that |5P
Σ
and the last step
k=1+1
used the definition of dg. Thus, it sufficient to obtain a lower bound on E|| [2] lower bound for B mmxx]
order obtain a
Step 2: lower bounding 11 To proceed, we introduce the following lemma pertaining to lower bounding V.Th that will be useful later.
Lemma 6. For all time instants t E [T] and all agent m E [M]:
1
E
2
2(1 - 7)22
We have,
E 2
E
Var ((11)
E Σ E [=1]
((tt)
92
2p(1 - -p) E. (vZz)) 27
(1(1))
B
y2
Uk(()
B2
2p(1 - p)
2(1 - 7-
2
(11)
71
(109)
9B(1
Je k==ax(( (+
where the third line follows from Lemma 6 and the fourth line uses 7 5/6.
(1))
Step 3: finishing up. We finish up the proof by bounding Σ El=max(t
1
for t
max (1'+7} 2 1/1,- We have
2
2
II (1 m:)
k=max(( ( m1)11
k=max
i=++1
35

---

1ht II (1 (1-m+) (n)-)))
k=maxff (r+
(1 - 1// 11/) 2((-kk
k=max +1
1 (1 17-
) ( (7))
2 7/
17: 17-
1 1 exp(-2)
1/1
1/
1/
(110)
6
10'
where follows from the monotonicity of nk- Plugging (110) into the expressions of D (cf. (107) we have
8 (20((2))))
4n log(2/00)
D
Σ
1
3B(1 - 77
3B(1 -7)
k=#+1
-1/2
9
8log(2/00
(1) 2 1k
60
E1 [ log(2/5o)
2
B(1 7)
k=1+1
60B(1 7)
s 3E ST 11 1og(2/60)
+ 20
3B(1 7)
$ 60011577, [12] 1og(2/60)
+
20Tr
where the second line follows from (09p and (TO)), and the third line follows from combining the above bound with (108). we obtain,
1T0 On
V
E M.xx
(111)
240 (2/60)
+
20HT
where
Note that have,
V (B(11 - -7)
50 (1 7)-
(1-7)
Σ
2
Tr - 7)
1k
>
2
9B
90B
k=1+1
Combining the above bound with 1111 yields us the required bound.
Step 4: repeating the argument for the second claim. We note that second claim in the theorem, follows through an identi-
i.e. the lower bound on E max cal series of arguments where the bounds in Eqns. (104) and (105) contain additional factor of M the denominator (effectively replacing B with BM), which carried through in all the following steps.
1 M
Em= em (P),(1), A8 ΣM SP,,
B.5.4
Proof of Lemma
Using Eqns.
41 and
388 we can write
A, (11))
II (1 md)
- (r()
k=
M
(1 mi) (PP - PE (1,, im
Σ
Σ
1ik
m=
k=
i=++1
36

---

Upon unrolling the recursion, we obtain,
(1 - (2
II (1 nk) 1mm++
2 T (1[1,1) - P (111, M
T/k
1 m==1
as the o-algebra corresponding to PM (111,2) then it is straightforward to note that ( h is a martingale sequence adapted to the filtration {5i) Using Jensen's inequality, we know that if {Zi) is martingale adapted to a filtration {%)). then for convex function f such that f(Z)) is integrable for all t, [f(2)) is a sub-martingale adapted to (Sh Since f(x) = |x]] is a convex function, (1) (2)l), is a submartingale adapted to the filtration (F.) As result,
If we define a filtration (1/11,, 1); (). (11(1)11),,
sup E (1) (2)l (1) Ar())] S (r)))))))) I5:ST
-
(112)
We use the following observation about a martingale sequence {X,) to evaluate the above expression. We have,
adapted to a filtration {8))
E
Xi
E
E
Σ
Xi
9--1
1=1
1=1
1-1
E
E
x? + 2X,
Σ
+
Σ
Xi
8--1
1=1
1=1
E
[
+E
Σx X₁
E [
(113)
where the third step uses the facts that (E X, is 9--1 measure and B[X, (--1 = and fourth step is obtained by recursively applying second and third steps. Using the relation in Eqn. 113 in
Eqn. 112). we obtain,
sup BIIA(1)) (2)1 S (1 1/2
KEST
)1)
1/2
T
M
E
(PE - Pm
Vrn k-
M
1=1
m=1
T
(T))
2
2 p(1 p)
Σ
M
(vm=)) )
1/2
1hx
BM
m=1
T
2
27 27 1p2p(117) - p)
1/2
VA
(114)
B1 7)
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
(L-
Σ k=1
(1 1)2 n. (115)
1)2
k=
i=++1
Similarly, for linearly rescaled step sizes, we have.
m
II (1
77:)
R=1
k=
i=k+1
37

---

I
+
me(11 - mTr) (((T
k=++1
- (1 - 'TT) 2(7 -T)
T + n/=-
1/r(2 - 177)
4m'm
< 3t/ 11 exxp
+ 3//
9
1/r 37T
4e
2 4mp,
(116)
((2) where the second step Cy S log N S 1- and the fact that 7l
is increasing in k in this regime.
(See Eqn. (99) and fifth step uses de - 1z/3 < 3/4e. On plugging results from Eqns. 115) and (166
into Eqn. 114) along with the value of p. we obtain,
SiP 3BM(1-7))
sup EIJ -2)( ISET
(117)
required.
B.5.5
Proof of Lemma 6
For the proof, we fix agent m. In order to obtain the required lower bound on V.T define an auxiliary sequence Q, that evolves as described Algorithm 5 Essentially, Q, evolves in manner almost identical to QTe 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 Q
< 1, 1 (1, 1) for all m (1,2....,M)
2:
for = 1,2 T do
3: for m 1,2, ..... do
4:
Q.-1//2 (1 QT (a) + m1 P171,,
m2
5: Compute Q, according Eqn. (
6: end for
7:
end for
straightforward to note that (1) 2 Ct", which can be shown using induction. From the
initialization, it follows that Q (1) 2 Q Assuming the relation holds for t - 1, we have,
1/2 (1) (1 Tt T1 (1) + (1
> (1 1/: ))) (1) + n/ (1+
+ 2 (1 n)) m 0) m
(111,))))))
1/21
Since T.n and Q follow the same averaging schedule, it immediately follows from the above t
relation that Q 2 D," Since V.m Q (1) 2 Q, we will use the sequence Q," to establish the required lower bound on t.T..
We claim that for all time instants / and all agents m,
E
(118)
1 7-7p"
Assuming (188) holds, we have
E [( 2
[ 2
2
2
2
2
1
7p
2(1
7)
38

---

as required. In the above expression, the first inequality follows from Jensen's 's inequality, the second from the relation V 2 Qi 0 and the third from (118
We now move now to prove the claim 118 using induction. For the base case, E[Q²" I- holds
by choice of initialization. Assume that E[ 1-7p holds for some - 1 for all m.
1
If t is not an averaging instant, then for any client m,
02- 1--))_--111- + (1 + + 7 (1
E(Q,1 (1 m.) - No 7E
(P 1)Q2-11)
= (1 71 nn) 7e yp
(1 - m1)
+ (1 (1+ T YP
7p
(119)
1 7p
7P
The third line follows from the independence of P.m (1 and Qi and the fourth line uses the inductive hypothesis.
If is an averaging instant, then for all clients m,
Q₂
(1
170
T
1
Σ
M
(1
(1+
M
M
j=1
==1
(1 17:)
1
M
E[Q,
EQQ
|
Tl
(1 + B(P
(1 1)Q(-11)
M
M
j=1
j=1
M
M
(1 176)
+ 111 M
1
Σ
PP
1
(120)
M
7
Yp
J=1
where we again make use of independence and the inductive hypothesis.
Thus, 119 and 120
taken together complete the inductive step.
C Analysis of Fed-DVR-Q
In this section, we prove Theorem 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 1.3 the output of the algorithm is an c-optimal estimate of Q* with probability 1 8. The second part deals with deriving the bounds the sample and communication complexity based on the choice of prescribed parameters. We begin with the second part, which is easier of the two.
C.1 Establishing the sample and communication complexity bounds
Establishing the communication complexity. We begin with bounding CCround- From the de- scription Fed-DVR-Q, it is straightforward to note that each epach, i.e., each call to the REFINEES- TIMATE routine, involves / + rounds of communication, one for estimating TQ and the remaining ones during the iterative updates of the Q-function. Since there are total of K epochs,
16
1
(Crdun((Fed-DVR-QQ M, s + IIK <
71-7) loga
7)
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 M, J | CCround (edd-FVFDVF Mood-DVR-Q;,. M,
32 32|S|A| 1 - 7)
70
(8K(S/|A4) 1
loga
loga
log
(1 - 7)E
17(1 - 7)
M
8
where once again in the second step plugged in the choice of J from Sec.
4.1.3
39

---

Establishing the sample complexity. In order to establish the bound on the sample complexity. note that during epoch each agent takes total of [ + B samples, where the first term corresponds to approximating Tr (Q(R-1)) and the second term corresponds to the samples taken during the iterative update scheme. Thus, the total sample complexity is obtained by summing up over all the K epochs. We have,
K
Lk M
S
+I.B
SI.B.K
Lx + K.
k=1
To continue, notice that
39200
8KI|S|A
Ko
K
LR
log
k= Ko+1 k
kk- Ko
M
211
5
39200
log
SKISI|AA
(4 + +4" Kk)
3M - --
8 8KISIAA
156800
(1-1+
log
3M(1 (1 7)2
8
7)2
where the first line follows from the choice of L in Sec. 4.1.3 and the last line follows from
Ko = [ loga( (1-)] Plugging this relation and the choices of I and B (cf. Sec. 4.1.3) into the
previous bound yields
4608
SKI|S|IA
SC(Fed-DVR-Q:s,,.pp 1 (1 7)3 log2
log
+ K
(1 - 7)E
156800
8K 8KISS|IA
1
31 - 7 log
+
5
(1 - 7)
313600
SKIS|AA
M (1 - 73 log2
log
+ K.
(1 7)=
Plugging in the choice of K finishes the proof.
C.2 Establishing the error guarantees
In this section, show that the Q-function estimate returned by the Fed-DVR-Q algorithm is e-optimal with probability at least - 6. We claim that the estimates the Q-function generated by the algorithm across different epochs satisfy the following relation for all ls K with probability
1 1- 8:
2-
- 12 S 1-7
(121)
The required bound on [[Q(K) - Q* b1 immediately follows by plugging in the value of K. Thus, for the remainder of the section, we focus on establishing the above claim.
Step 1:
fixed-point contraction of REANEESTIMATE. Firstly, note that the variance-reduced update scheme carried out during the REFINEESTIMATE routine resembles that of the classic Q- learning scheme, i.e., fixed-point iteration, with a different operator defined as follows:
H(Q) == T(Q) - T + (Q), for some fixed Q
(122)
Thus, the update scheme step in 11I then be written as
Q = (1 1)Qi))1i+t
(Qi-1), (Q..))
(123)
where Hg (Q) (((m((2) - (( m) 2 + (Q) is a stochastic, unbiased estimate of the operator
H. similar to 7((m) (Q). Let Qi denote the fixed point of H. Then the update scheme in (123) Qi further, as long as ||Q 1Q*-Qilllas is small, the required error I|Q, - Q'I Ioooo can also controlled. The following lemmas formalize these ideas and pave the path
drives the sequence 1Qth)120
to establish the claim in [21 The proofs are deferred to Appendix C.3
40

---

Lemma 7. Let Ô E (0, Consider the REFINEESTIMATE routine described in Algorithm and let Q7 denote the fixed point of the operator H. defined in (22 for some fixed Q Then the iterates generated by REFINEESTIMATE Q satisfy
D
- - (IQQ - 2= + l|Q Qullos)
70
with probability 1
2K'
Lemma 8. Consider the REFINEESTIMATE routine described in Alg. and let Qh denote the fixed 122 for fixed Q. The following relation holds with
point of the operator H. defined in Eqn. probability zk:
16x
64k!
2n' 2n'v2
D
1Q 1' S IQ - Q"1
V
L(L 7)2
+
V
713
3L
7)3 70'
+
whenever L 32k', where K¹' loo
|22|(||AA
Step 2: establishing the linear contraction. We now leverage the above lemmas to establish the desired contraction (I2I). Instantiating the operator (22) at each k-th epoch by setting Q (k--1) and L Lg. define
H2(Q) = - T(Q(t-1) + + (Q(k-1)), (
(124)
whose fixed point is denoted as Qite Using the results from Lemmas 7 and 8 with D = D2 and H = He. we obtain
[1Q(k) - 10 < (1Q(6) - Qi, 1o00 + 110 QHa 1l0o
s 6 (1Q( 1x + 1|Q" Qieeelll 1l00))))
1
De
+ 11Qu. - QQ'1lss 1100
- 70
1
(1Q(R-1) Q'1 100 + 7
DE
Qit 100)
+ 70
6
< 110 - 1o0
7
6
V
Lx 7)2
16k
+ 6
(V
La - 7)3 +
64k'
3Lx - 7)2
2V2n'
+
13Dx
420
< [1Q - 120
7
16k
7
100k'
13Dr
+
+
6
Lx(1
7)2
6
L1
420
(125)
holds with probability K- Here, we invoke Lemma 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 that L. (1-2)
x² 2
We now use induction along with the recursive relation in 125
to establish the required claim 121) Q S - holds by defimition. and choice of La (Sec. 4.1.3). 3, we have
Let us first consider the case 0 < < Kg. The base case, Q
Let us assume the relation holds for A: - 1. Then, from 125
[[Q(k) - 10 < (1Q(k-1)-
- -Q1 1lc0
7
16k
7
100k'
+ 13Dx
6
V
Lx
7)
6
Lb
7)3
420
2 1k-
7
8
7
50
104
2 (1--1))
+ 2- k
+ 2
k
+
1-7 7
6
19600
6
19600(1
-7)
420
1-7
2 2- (k
7
91
1
+
1 1-7
39200
4
2 2
(126)
1-9
41

---

Now we move to the second case, for l > Ko. From (25) and choice of L₁ (Sec.
4.1.3
we have
[|Q(h) 20 - 110
-101--)- -Q
7
16k
7
100k'
13D
6
Lx
7)2
Lx
7)3
420
1-
1-9
2- (k- Ko)
V
19600
+ 2
Ka)
V 19600(1
50
-
420
104
2-
1 1-
2 (k()-
1
1
1-n
196
4
2 2-
(127)
1-7
By a union bound argument, we can conclude that the relation [[Q()] - -Q0 S - holds for all
k < K with probability at least - 8.
Step 3: confirm the compressor bound. The only thing left to verify is that the inputs to the compressor always bounded by D& during the k-th epoch, for all 1 I k S K. The following lemma provides a bound on the input to the compressor during any run the REFINEESTIMATE routine.
Lemma 9. Consider the REFINEESTIMATE routine described in Algorithm 3 with some for some 5
fixed Q. For all i S and all agents m. the following bound holds with probability 1
2K'
7 (1++7)++ (1+1))))+
+ D +
10 Qi-ills S 1 Qh
70
For the k-thh epoch, it follows that
(1 1oalloo ( (1+ +.7)
7
11Dx(1 (1+(+++))) +7)
70
$
13
- + -1Q" - -oe.illee (1ox)
-Q'lls
+
D& + 7)
3
13
15
2D
11Q(==))
-Q( +
3
14
70
195
16
2 (k-
+
42
70
1 1-7
2-
(b-1) 1)
8
1-7 D
In the third step, used the same sequence of arguments as used in 126) and 127 and, in the fourth step, we used the bound on [[Q(k-1) - Q" |l from (121) and the prescribed value of D
C.3 Proof of auxiliary lemmas
C.3.1 Proof of Lemma 7
Let us begin with analyzing the evolution of the sequence (Q.H= during run of the REFINEESTI- MATE routine. The sequence (Q:) satisfies the following recursion:
M
Q Q-1 M
Σ
E
@0Th
-.-1;:
M
Q 1 +
Q Qi-1 -
M
m=1
42

---

M
M
M M
M O + (i") = = (1-n)) +
Σ m=
7
Σ m=1
H.
( (Q:-1) +
S
(128)
M
In the above expression, 5:Th denotes the quantization noise introduced at agent m in the i-th update. Subtracting Qi from both sides of 128
we obtain
Q: QH = (1- QH+ +
H (m)
(Qi-)) Q74)
Cr
M
M
(1 (1-1)(00 (1-n) + 1
Hn (Qi-1) - Fm) (Q7t1)
M
m=1
M
1
{m (QH) H((Q1)) + G. (129)
+
M m
Consequently,
IQ - Q7ello 51 (11-1)) 1
1 1xe +
Σ
(m)) H (Qi-1) - (Q7)
M
m=l
Σ
(m) (Qx) H(Q71)
+ +1Gilloo
(130)
which we shall proceed to bound each term separately.
Regarding the second term, it follows that
( (Q) (m) (Q++
T/ (Q) 7.m)
Sr1Q - Qill (131)
which holds for all Q since 7:(m) is c-oottrcctvve operator.
Regarding the third term, notice that
M
M
1
H (m) (Qx) +((25))
Σ
(T.(HH) - - -(0) +T())
M
MB
m=1
m= 2E z(m)
Note that T((2)) - Tx(2) -((})) T(Q) is zero-mean random vector satisfying
-
+ lo s 2
(132)
Thus, each of its coordinate is a (2>l1Q- - 1o --s-)------sssssss Gaussian vector. Applying the tail bounds for maximum of aub-Gaussian random variables [Vershynin] 2018), we obtain that
M Σ m=1
(7 (QT) - P((O%)
log 8KTSSIA
2 Qullox
MM
V
MB
(133)
holds with probability least 487
Turning to the last term, by the construction of the compression routine described in Section 4.1.2 it is straightforward to note that <Th a zero-mean random vector whose coordinates are independent, D --ssuuaaass random variables. Thus, Ç is also zero-mean random vector whose coordinates are independent, M-47 sub-Gaussian random variables. Hence, we can similarly conclude that
DD
2 M
8KISS|AA
1KGiloo S DD.2
log
(134)
8
holds with probability least 1
IKT
43

---

Combining the above bounds into (300) and introducing the short-hand notation K log 8KTS| we obtain with probability at least 2KI
2x MB
2x
||Q; - Qi S 5 (1- - Qill= 00 + 2 - Vulla
DD.2-J
2- V M
V
Unrolling the above recursion over i = 1..... yields the following relation, which holds with probability at least 1
8
2k
||Q lx s (1
(11 7))' (0))'114, 110o Qieloo
V
2K
2m
Q
Qie + +D.2-1)
Σ (1 11-n(1 7))=
M
VB
$ (1 - 71(1 7))' 11Q - QHll +
1
2k
20/7
1Q - Q7ello +D.2
V
7/11
7)
M
VB
< 110 17l
(1 - n1 - -7))² + (1-7)
27
2x
+
D D-2
V
2Kk
M (135)
MB
11(1 7)
Q Q7 loc
D
D
(IQQ - Q" 11x 1Q" - lxel
(136)
70
Here, the fourth step is obtained by plugging in the prescribed values of B, and in Sec. 4.1.3
C.3.2 Proof of Lemma g
Intuitively, the error ||Q Q' Ie depends on the error term TQ.(Q) T().. If the latter is small, then H(Q) is close T (Q) and consequently Q and Q* Thus, we begin with bounding the term (Q) - TQQ). We have,
T T(Q)
1 M
Q
M Σ 6
[
mL) (Q)
1 M
(m) TL
(Q) + 2 7(m))
-T(Q)
M m=1
M
M
M
2 (m) (Q) -T( (Q") (Q")-
7(m)
Σ
T (m) (Q") (Q")-((Q')) T(Q)).
+
M
M
M m=1
m=1
m=11
(137)
where once again 7 - (m)
(2) Q '6
T
denotes the quantization error at 134 we can conclude that each of the following
(m) Q2) - 2)
agent m. Similar to the arguments of (I33 and relations hold with probability least
6k
1 M
m
T (m) -
-()
2 Q*1b>
V
L
2
log
12K IA
(138)
M Σ mm)
2
|2K|S||AA
M
$ D
V M
log
m=
(139)
For the third term, we can rewrite as
M
M [L/M]
Σ T (m) (Q")
-TQQ))
Σ
Σ
(T (Q") (TQ0)
M 1==1
M
L/M
m=1
1=1
44

---

We will use Bernstein inequality element wise to bound the above term. Let o R|SI be such that |o (s, a)I² Var(Tz (s. a)), ie.. (s, a)-th element of denotes the standard deviation of the random variable Tz(Q") (8, a). Since (Q') 'TQ I1x I I- a.s., Bernstein inequality gives that
M Σ (196))
2 log
(K||S|AA1) 8
2
6K|S| |.A]
so L
log (140)
3L -7)
8
holds simultaneously for all (8, E S x A with probability at least 137.
8 6k
On combining
(138). (139) and 140). we obtain that
Sn o (s.)
2Rd
2n'
2x²
(s, - TT()) = =IQ 10
L
L
3L(1
7)
+
+D.2
V (141)
M
holds simultaneously for all (s,a) E S x A with probability at least
8 where k²
2k*
log 12x151_A)) ) We this bound in (141 to obtain bound on l|Qu Q" loc using the fol-
lowing lemma.
Lemma 10 Wainwright 2019b]). ) Let nt" and मे respectively denote the optimal policies w.r. Q and Qix Then,
)-1 110 - Q0 max {(1 7 TT(Q)- (((Q)-((Q)) -P -10
Here, for any deterministic policy pr E IR AIxISIIA is given by (PTQ)(s,a) = Eves (()(s ( =Ts')).
Furthermore, it was shown in Wainwright 2019b ((Q) a)l satisfies
Proof of Lemma 4] that if the error (Q)
(z(Q))s a) T(Q))ss a) s so ||Q - Q0 + + (s,a) +
(142)
for some 21, 82 2 0 with 21 < 1, then the bound in Lemma 10 can be simplified to
||Qx - Q- 11.0 < 1
1
20
Q
1o + (1 (1-7)3/2
21 + 22
(143)
1--7
1 1-7)
On comparing,
141 with
142). we obtain
8k
2x
2n'
2n
20
21
22
D. 10.2-J_ J-J..
.
3L(1 - 7)
M
Moreover, the condition L 2 32k' implies that < 1 and above values in (143), we can conclude that
1
< V2. Thus, on plugging in the
1-21
16x'
64k'
2n' V2
D.2-1
4K'
11Q4 1bo < QQ 1'
V
7)
L(1 11)3
7)3
+ 3I(11 7)
+
(1
7)
M
8K
32k'
2v/2n'
D
< | Q- |0
V
T(1
72
V
T.(1 7/3
+
3T - 7)²
40'
(144)
where once again we use the value of J in the last step.
C.3.3 Proof of Lemma 9
From the iterative update rule in 123 for any agent have,
2 - Qi-1 n (m)) (Q.-1) - Qi-1)
(77
45

---

- + Qi-1).
Thus,
- -Qi-11o 5 (+:
+ +100 H(
Qi Qi-
S <1 0Hl1 + 201 Qh + 1107 Qi-1llac
1) ((1 +7)1Q:-1111 Qx 2 Qxello)
s m/|Q - Vieloo ( - (1+ +27) 1D(1+ +
70
holds with probability 2KT step the above relation follows from (135) evaluated at general value of and the prescribed value of J. By a union bound argument, the above relation holds for all with probability at least 2K
5 Here, the second inequality follows from 131 and [122 The last
D Numerical Experiments
In this section, corroborate theoretical results through simulations. For the simulations, consider an MDP with 3 states and two actions, i.c., S {0. 1, 2 and = {0, 1]. The discount parameter is set to y 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 given by the expression in Eqn. (4a)). Similarly, the reward and transition kernel corresponding state 1 and are identical and given by Eqns. (14b) and (14c) with 0.8.
Error vs Samples Takm
Commuomication Coet Samples
Ro--VR-
Fwi-Syn-Q
Fed-Syn-43
20000
10-1
15000
10000
5000
0.0
10
X10
(a) Sample Complexity
(b) Communication Complexity
Figure 1: Comparison between sample and communication complexities of Fed-DVR-Q and the algorithm Fed-SynQ from Woo et al. [2023]
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 the suggested values in the respective papers. Both the algorithms were run with 10" samples at each agent. For the communication cost of Fed-Sp red-SynQ we assume that each real number is expressed using 32 bits. Ta we plot the error rate of the algorithm
In Fig
function of the number of samples used. In Fig. lb we plot the corresponding communication complexities. As evident from Fig La Fed-DVR- achieves smaller error than Fed-SynQ under the same sample budget. Similarly,
suggested by Fig. lb Fed-DVR-Q also requires much less communication (measured 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 agents from to 25 in multiples of and record the sample and communication complexity to achieve error rate of 0.03. The sample
46

---

Sample Complesity vs Number Agynnss
Bed-DVE-Q
Commmmnication Complexity vs Number of Agenta
11300
0.5-
11000
10600
10000
0.4
0.3
10
20
(a) Sample Complexity
(b) Communication Complexity
Figure 2: Dependence of sample and communication complexities of Fed-DVR-Q on the number of agents.
Communication Complexity ve Ellective borison
Fwi-TVV--Q
7000
5000
5
10
1 Figure 3: Communication complexity of Fed-DVR-O as a function of effective horizon, i.e., 1-7
and communication complexities as function of number of agents are plotted in Figs. 2a and 2b respectively. The sample complexity decreases as 1/M while the communication complexity 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, compare the communication complexity of Fed-DVR-O as function of the discount parameter y. We consider the same setup as in the first study and vary the values of from 0.7 0.9 in steps of 0.05. We run the algorithm 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., - in Fig. 3 evident from the figure, the communication scales linearly with the effective horizon, which matches the theoretical claim in Theorem
I-
47

---

NeurIPS Paper Checklist
1. Claims
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 study the sample- communication complexity trade-off in Federated Q-learnin and derive both converse and achievability results. In Sec. 3ec. we derive the lower bound communication complexity and in Sec. 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 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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We consider an infinite horizon MDP the tabular setting and derive the results for the class of intermittent communication algorithms. We acknowledge that these assumptions might be restrictive for certain class applications and extension more general settings is discussed as future direction in Sec.
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 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 vell-specifiiattio, 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 few datasets with 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
48

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Both Theorem | and 2 clearly state all assumptions used in the statement of main result. The proofs for both the theorems can be found in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have section with numerical experiments in Appendix D The section contains all relevant details of our implementation to reproduce the results.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
49

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
The paper does not have associated code or data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://niis.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 //nips. /twpps.ccppublli/ httpcc/pccccccceeeeeeeeeeeeeeeee wwtpc//guiies/e/eee htt.//dd/ee/ooeeuuiiiiieeee
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The relevant details can be found in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[NA]
Justification:
The error bars associated with the plots small and hence omit them.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
50

---

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 the standard error of the mean.
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 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 range (e.g. negative error rates).
If error bars 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The empirical studies require no specific compute resources be easily completed on a regular laptop.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have read the NeurIPS Code of Ethics and the paper conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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:
51

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 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 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
52

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve any crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
53

---

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.
54


Reviews:
[{"review_id": "1mjN6vrF6G", "reviewer": "Reviewer_UVy4", "summary": "This paper investigates the sample and communication complexities of federated Q-learning with intermittent central aggregation of the Q-value function.\nThe authors demonstrate that to achieve any speedup in sample complexity through federated collaboration, the communication complexity must be at least $\\Omega(1 /(1-\\gamma ))$.\nAdditionally, the paper introduces a novel federated Q-learning algorithm incorporating variance reduction and minibatching techniques, achieving order-optimal sample and communication complexities.", "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.\n\nPlease see Section Weaknesses for other questions.", "limitations": "Limitations and open problems are adequately discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper considers the important trade-off problem between sample complexity speedup and communication cost in federated reinforcement learning. It provides a complete characterization of this trade-off in federated Q-learning, including the communication cost in bits.\n- Not only do the authors provide a complete characterization of the sample-communication trade-off and design a novel federated Q-learning algorithm that achieves order-optimal sample and communication complexities, but they also provide insights and intuitions into how infrequent communication fails to speed up sample complexity, and how their algorithm balances this trade-off.", "weaknesses": "- 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?\n- The related work section on Distributed RL is generally comprehensive; however, it omits some recent works on heterogeneous FedRL [3,4].\n- 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?\n- In Eq. (7), should $\\widehat{\\mathcal{T}}$  be $\\mathcal{T}$? Otherwise it is not defined.\n\nOverall, 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.\n\n### References\n\n[1] Liu, R., & Olshevsky, A. (2023). Distributed TD (0) with almost no communication. _IEEE Control Systems Letters_, _7_, 2892-2897.  \n[2] Tian, H., Paschalidis, I. C., & Olshevsky, A. (2024). One-Shot Averaging for Distributed TD (λ) Under Markov Sampling. _IEEE Control Systems Letters_.  \n[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.  \n[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.  \n[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.\n[6] Wainwright, M. J. (2019). Variance-reduced $ Q $-learning is minimax optimal. _arXiv preprint arXiv:1906.04697_.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and your constructive feedback. We appreciate the time and effort you spent on our paper and the helpful comments you provided. Please find our itemized responses to your questions below.\n\n- _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?_\n\nOur result does not violate the results obtained in the existing studies on federated TD learning [1,2]. The key difference here is that the results in [1,2] consider TD learning to learn the value function directly instead of Q-function. If TD-learning is used to learn the value function directly, then the resultant algorithm aims to learn the fixed point of the operator $\\mathcal{T}\\_{TD} : \\mathbb{R}^{|\\mathcal{S}|} \\to \\mathbb{R}^{|\\mathcal{S}|}$ given as $\\mathcal{T}\\_{TD}(V)(s) := r(s) + \\sum_{s'} P(s,s')V(s')$, where $r$ and $P$ are reward and probability transition matrices respectively. Note that this is a **linear** function of $V$. On the other hand, our work focuses on learning the optimal Q-function via Q-learning. Specifically, we learn the fixed point of the operator $\\mathcal{T}\\_{QL} : \\mathbb{R}^{|\\mathcal{S}| |\\mathcal{A}|} \\to \\mathbb{R}^{|\\mathcal{S}| |\\mathcal{A}|}$ given by $\\mathcal{T}\\_{QL}(Q)(s,a) := r(s,a) + \\sum_{s'} P(s'|s,a) [\\max\\_{a'} Q(s',a')]$. Note that this function is a **non-linear** function of $Q$. \n\nThe difference in the communication requirement stems from the fact that the linearity of the Bellman operator in terms of the value allows one-shot averaging to be sufficient to achieve optimal error rates. On the other hand, the non-linearity of Bellman operator with respect to the Q-function results in one-shot averaging to be no longer sufficient to achieve optimal error rates. \n\nIf 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. A discussion regarding this difference between TD learning and Q-learning can also be found in [5] (from your comment) where the authors show that TD learning achieves the optimal sample complexity but Q-learning (without variance reduction) is necessarily sub-optimal in terms on dependence on $\\gamma$.\n\nThank you for highlighting this interesting point. We will add this discussion in the revised version of the paper.\n\n- _The related work section on Distributed RL is generally comprehensive; however, it omits some recent works on heterogeneous FedRL [3,4]._\n\nThank you for pointing out the additional papers. We will add them in the related work section. [3] adopts a policy optimization perspective, which is different from the Q-learning paradigm considered in this work. Moreover, the algorithm in [3] obtains a linear communication cost, which is worse than that obtained in our work. Similarly, [4] focuses on on-policy learning and incurs a communication cost that depends polynomially on the required error $\\varepsilon$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8qk8YUSRjf", "reviewer": "Reviewer_buwU", "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 \ncost 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.", "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.\n\nQ2. 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?\n\n[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.\n\nQ3. 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?\n\nQ4. 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?\n\nI would be happy to increase my score based on your response to my above question.", "limitations": "Yes, the authors have discussed the limitations of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "S1. The paper provides a lower bound in terms of communication complexity. This would be helpful to the community.\n\nS2. The work provides a novel algorithm that incorporates the variance reduction technique. It is shown that this algorithm has optimal order from both the sample complexity and communication complexity perspectives and achieves a linear speedup in terms of the number of agents.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and your constructive feedback. We appreciate the time and effort you spent on our paper and the helpful comments you provided. Please find our itemized responses to your questions below.\n\nQ1. 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.\n\nA1. For Q-learning, it is well-known that some form of variance reduction presents in all existing algorithm designs that achieve the optimal sample complexity with respect to $\\gamma$. In [LCCWC23], the authors demonstrated that vanilla Q-learning, i.e., without variance reduction, has a sample complexity that is necessarily sub-optimal by a factor of $1/(1-\\gamma)$. Thus, some form of variance reduction is crucial to achieve the optimal sample complexity. In absence of variance reduction, our algorithm will achieve a sample complexity that is greater than the current one by a factor of $1/(1-\\gamma)$ (along with logarithmic factors).\n\nQ2. 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?\n\nA2. The Theorem 2(a) in [BRS18] is true when the learner updates the Q-function (or the parameter $\\theta$ in their case) after *each* data point/observation from the environment. In other words, the mini-batch size is $1$. On the other hand, our algorithm takes a mini-batch ($\\gg 1$) of samples, collates the information and then updates the Q-function. In both the approaches, the fundamental motivation is to ensure that the variance of stochastic updates is small. In [BRS18], the authors use an update with a large variance and balance it by choosing a small step size. In our work, we allow larger step sizes but require updates with smaller variance (obtained through mini-batching) to ensure updates with low variance.\n\nThe dependence of $\\varepsilon$ is directly through the number of epochs $K$ and indirectly through the choice of $B$ and $J$, as they depend on the parameter $K$.\n\nQ3. 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?\n\nA3. The variable $N$ in Theorem 1 is the sample complexity of the algorithm and its relation with the error $\\varepsilon$ can be obtained through equations (4) and (5). Our Theorem 1 states that if the number of communication rounds in algorithm is $\\mathcal{O}(\\frac{1}{1-\\gamma})$ (upto logarithmic factors), then the error of the final output is $\\Omega(1/\\sqrt{N})$, where $N$ is the number of samples taken for each state-action pair at each agent. In other words, in order to obtain $\\varepsilon$-optimal Q-function, each agent needs to take at least $\\Omega(1/\\varepsilon^2)$ samples, i.e., the algorithm offers no linear speed up w.r.t. the number of agents. This is equivalent to saying that if any algorithm is designed such that it only takes $\\mathcal{O}(1/M\\varepsilon^2)$ samples per agent (or offers _any_ speed-up w.r.t. number of agents), then it must have at least $\\Omega(\\frac{1}{1-\\gamma})$ rounds of communication. \n\nOur Theorem 2 states that our proposed algorithm Fed-DVR-Q is such that it takes $\\mathcal{O}(1/M\\varepsilon^2)$ samples per state-action pair at each agents and has $\\mathcal{O}(\\frac{1}{1-\\gamma})$ rounds of communication. Note that this order matches that in the statement of the lower bound, thereby establishing the optimality of communication complexity. The optimality of the sample complexity follows immediately from the lower bound in (Azar et al. 2013). \n\nQ4. 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?\n\nA4. Our algorithm Fed-DVR-Q is parameter-free in the sense that it does not require any knowledge of the parameters of underlying MDP. Our algorithm, however, does have several parameters, whose values have been specified in Sec. 4.1.3. of the paper. We also use a hyperparameter $\\eta \\in (0,1)$ corresponding to the step size of the updates. As evident from the bounds in Theorem 2, it is preferable to have values of $\\eta$ close to $1$.\n\n[LCCWC23]: G. Li, C. Cai, Y. Chen, Y. Wei, and Y. Chi. Is q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pIHcl7qdx2", "reviewer": "Reviewer_YcCi", "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.\n\nThe 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.\n\nThe second contribution is the algorithm that shows that this bound is tight.", "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": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The authors consider the problem interesting and well-motivated. The findings establish a good understanding of tradeoffs in Federated Q-learning. The results are well-presented, and the theoretical part of the lower and upper bound looks solid.", "weaknesses": "While the main focus of this work is theoretical, the paper could benefit from the experimental evaluation of the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and your constructive feedback. We appreciate the time and effort you spent on our paper and the helpful comments you provided. Please find our itemized responses to your questions below.\n\n- _While the main focus of this work is theoretical, the paper could benefit from the experimental evaluation of the algorithm._\n\nBased on your suggestion, we performed some empirical studies and have included the results in the rebuttal. We consider a MDP with 3 states, namely $\\{0,1,2\\}$ and 2 actions, where the reward and transition kernel of states $0$ and $1$ are identical to those in the MDP outlined in Appendix B.1 in the paper. The reward and transition kernel for state $2$ is identical to that of state $1$. The values of $\\gamma$ and $p$ are set to $0.9$ and $0.8$ respectively. We perform two 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. The parameters for both the algorithms were set to the suggested values in the respective papers. As evident from Fig 1, Fed-DVR-Q achieves a smaller error than Fed-SynQ in the same sample budget. Similarly, Fed-DVR-Q also requires much lesser communication (measured in number of bits transmitted) than Fed-SynQ demonstrating the effectiveness of the proposed approach and corroborating our theoretical results. In the second experiment, we study the effect of the number of agents on the sample and communication complexity of Fed-DVR-Q. The sample complexity decreases as $1/M$ demonstrating the linear speed-up while the communication complexity is independent of the number of agents. Both these results confirm our theoretical findings. \n\nThank you for your suggestion. We will add the empirical results in the final version of our paper.\n\n- _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?_\n\nThank you for pointing this additional related work. Both the studies mentioned by the reviewer focus on best-arm identification in bandits, which is different problem from learning the optimal Q-function in RL using Q-learning due the markovian structure of the responses and the different objective functions. As a result, both the algorithmic design and analysis are quite different in these papers from those in our work. The lower bound in [1] is established using the heterogeneity across clients. On the other hand, the lower bound in our work is based on the bias-variance trade-off of Q-learning. Similarly, the algorithm design in both [1] and [2] are based on arm-elimination approaches which is different from the variance reduced stochastic fixed point iteration used in our work. We will add a discussion on this in the final version of the paper.\n\n[1] Nikolai Karpov and Qin Zhang, \"Parallel Best Arm Identification in Heterogeneous Environments\"\n\n[2] Nikolai Karpov and Qin Zhang, \"Communication-efficient Collaborative Best Arm Identification\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Based on the suggestion by Reviewer YcCi, we have performed two empirical studies and included their results in the attached PDF. We refer the reader to the response to Reviewer YcCi for additional details about the experiments and a discussion of the results.

Meta-review: 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.
Decision: Accept (oral)