Gap-Dependent Bounds for Federated $Q$-Learning
Authors: Haochen Zhang
Zhong Zheng
Lingzhou Xue
Venue: ICML 2025 poster (2025)
Keywords: Federated learning
Reinforcement learning
Regret
Communication cost
Primary area: reinforcement_learning
TL;DR: We present the first gap-dependent analysis of regret and communication cost for on-policy federated Q-Learning in tabular episodic finite-horizon Markov decision processes.

Abstract: We present the first gap-dependent analysis of regret and communication cost for on-policy federated $Q$-Learning in tabular episodic finite-horizon Markov decision processes (MDPs). Existing FRL methods focus on worst-case scenarios, leading to $\sqrt{T}$-type regret bounds and communication cost bounds with a $\log T$ term scaling with the number of agents $M$, states $S$, and actions $A$, where $T$ is the average total number of steps per agent. In contrast, our novel framework leverages the benign structures of MDPs, such as a strictly positive suboptimality gap, to achieve a $\log T$-type regret bound and a refined communication cost bound that disentangles exploration and exploitation. Our gap-dependent regret bound reveals a distinct multi-agent speedup pattern, and our gap-dependent communication cost bound removes the dependence on $MSA$ from the $\log T$ term. Notably, our gap-dependent communication cost bound also yields a better global switching cost when $M=1$, removing $SA$ from the $\log T$ term.

Gap-Dependent Bounds for Federated Q-Learning
Haochen Zhang" Zhong Zheng' Lingzhou Xue
Abstract
approach accelerates the learning process with low commu- nication costs. In this paper, focus on the online FRL tailored for episodic tabular MDPs with inhomogeneous transition kernels. Specifically, we assume the presence of a central server and M local agents in the system. Each agent interacts independently with an episodic MDP consisting of S states, A actions, and H steps per episode.
We present the first gap-dependent analysis of regret and communication cost for online feder- ated Q-Learning in tabular episodic finite-horizon Markov decision processes (MDPs). Existing fed- erated reinforcement learning (FRI.) methods fo- cus on worst-case scenarios, leading to -type regret bounds and communication cost bounds with log I' term scaling with the number of agents M, states S, and actions A, where T is the average total number of steps per agent. In contrast, our novel framework leverages the be- nign structures of MDPs, such as a strictly pos- itive suboptimality gap, to achieve a log Tyyy regret bound and refined communication cost bound that disentangles exploration and exploita- tion. Our sap-dependent regret bound reveals a distinct multi-agent speedup pattern, and our gap- dependent communication cost bound removes the dependence on MSA from the log I' term. Notably, our gap-dependent communication cost bound also yields better global switching cost when M 1, removing SA from the log I" term.
Multiple recent works studied the online FRI. for tabu- lar MDPs. Zheng et al. (2024) proposed model-free al- gorithms FedQ-Hofffding and FedQ-Bernstein that show the regret bounds Ó(v M SATT) and D(VMH*SAL respectively under O(MH SA T) rounds of commu- nications. Here, T is the average total number of steps for each agent, and Ô hides logarithmic factors. Zheng et al. (2025a) proposed FedQ-Advantage that improved the regret O(VMH2SAT) under reduced munication rounds of AHlloog Hog T) where fM E {1,M} reflects the optional forced synchroniza- tion scheme. Chen et al. (2022) and Labbi et al. (2024) proposed model-based algorithms that extend the single- agent algorithm UCBVI (Azar et al., 2017). Byzan- VI (Chen al., 2022) reaches regret O(V AT) under HSM log T) rounds of communications, Ved-UCBVI (Labbi et al., 2024) reaches the regret O(VMH'SAT) un- der O(HSA log T MHSS A log log rounds of commu- nications. Here, model-based methods require estimating the transition kernel so that their memory requirements scale quadratically with the number of states S. Model-free meth- ods, which are also called Q-Learning methods (Watkins, 1989), directly learn the action-valt value function, and their memory requirements only scale linearly with The re- gret Õ(VM H2S reached by both FedQ-Advantage and Fed- UCd-UCCVII is almost optimal compared to the regret lower bound O(VM (Jin et al., 2018; Domingues et al., 2021). In summary, all the works above provided worst-case guarantees for all possible MDPs and proved VT-type regret bounds and communication cost bounds that linearly depend on MSA A log T S log T. The re- sults of these works are also summarized in Table 1.
1. Introduction
Federated reinforcement learning (FRL) is a distributed learning framework that combines the principles of rein- forcement learning (RL) (Sutton & Barto, 2018) and fed- erated learning (FL) (McMahan et al., 2017). Focusing on sequential decision makiing FRL aims to learn an optimal policy through parallel explorations by multiple agents un- der the coordination of a central server. Often modeled as Markov decision process (MDP), multiple agents inde- pendently interact with an initially unknown environment and collaboratively train their decision-making models with limited information exchange between the agents. This
Equal contribution 'Deparmment of Statistics, The Pennsylva- nia State University, University Park, PA 16802, USA. Correspon- dence to: Lingzhou Xue <lzxue @ eoxuue@ps.edu... psu.edu>.
In practice, RL algorithms often perform better than their worst-case guarantees, as they can be significantly improved under MDPs with benign structures (Zanette & Brunskill, 2019). This motivates the problem-dependent analysis ex- ploiting benign MDPs (Wagenmaker et al., 2022a; Zhou
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Cap-Dependent Bounds for Federated Q-Learning
Table I. Comparison of online FRL algorithms
Algorithm Byzan-UCBVI (Chen et al., 2022)
Gap-dependent
Regret
Number of rounds
x
O(VMHPS2AT)
O T) O(MH'SAlog7)
FedQ-Hoeffding (Zheng et al., 2024)
X
S(TM
FeddQ-Bernstein (Zheng et al., 2024)
X
O(VMHSSAT)
O(MH'SA
FedQ-Advantage (Zheng al., 2025a)
X
O(VMI'SAT)
Off H) log
Fed-UCBVI (Labbi et al., 2024)
X
O(MMIPSAT)
O (HHSAlog
Our work
Or
H MSAT)
O'H
Amis
In this table, hides logarithmic factors and O hides logarithmic lower-order terms, such as log log I' and Vlog T, as well as constants. Parameter far E {1, M) indicates the optional forced synchronization scheme.
al., 2023; Zhang et al., 2024b). One of the benign struc- tures is based on the dependency on the positive subop- timality gap: for every state, the best actions outperform others by a margin. It is important because nearly all non- degenerate environments with finite action sets satisfy some sub-optimality gap conditions (Yang et al., 2021). For single- agent algorithms, Simchowitz & Jamieson (2019); Dann al. (2021) analyzed gap-dependent regret for model-based methods, and Yang et al. (2021); Xu et al. (2021); Zheng et al. (2025b) analyzed model-free methods. Here, Yang et al. (2021) focused on UCB-Hoeffding proposed by Jin et al. (2018), while Xu et al. (2021) proposed an algorithm that did not use upper confidence bounds (UCB). Zheng al. (2025b) analyzed UCB-Advantage (Zhang al., 2020) and (-EartySettled-AAvaaee Advanttge (Li et al., 2021), which used variance reduction techniques. All of these works reached regrets that logarithmically depend on T, which is much better than the worst-case vT-type regrets. However, no literature works on the gap-dependent regret for online FRL. This motivates the following open question:
gaps can be arbitrarily close 0 (see Section 5.1 for more explanations). This leads to the dependence M, S, and A for the log T term, which motivates the following open question:
Is it possible to establish gap-dependent communication cost upper bounds for online FRL algorithms that disentangle exploration and exploitation and remove the
dependence on M.S the log T term?
A closely related evaluation criterion for online RL the global switching cost, which is defined the times for policy switching. It is important in applications with restric- tions on policy switching, such as compiler optimization (Ashouri et al., 2018), hardware placements (Mirhoseini et al., 2017), database optimization (Krishnan et al., 2018), and material discovery (Nguyen et al., 2019). Next, we review related literature on single-agent model-free RL al- gorithms. Under the worst-case MDPs, Bai al. (2019) modified the algorithms in Jin et al. (2018), achieving switching cost of S log T), and UCB-Advantage (Zhang et al., 2020) reached an improved switching cost of O A log T), with both algorithms depending on
Is it possible to establish gup-dependent regret bounds for online FRL algorithms that are logarithmic in T?
SAlog T. In gap-dependent analysis, Zheng et al. (2025b) proved that Advantage enjoyed a switching cost that linearly depends on S log T. Whether single-agent model- free RL algorithms can avoid the dependence SA for the log T term remains an open question.
Meanwhile, recent works have proposed FRL algorithms for tabular episodic MDPs in various settings, such the offline setting (Woo et al., 2024) and scenarios where simulator is available (Woo et al., 2023; Salgia & Chi, 2024). Differ- ent from the online methods, state-of ofethh-art algorithms for these settings do not update the implemented behavior poli- cies (exploration) and reach A-ffee logarithmic bounds on communication rounds, whereas the worst-case com- munication cost bounds for online FRL methods require the dependence on M, S, and A in the log T term (e.g., D(MH35 log 7') in Zheng et al. (2024)). While increased communication for exploration is reasonable, existing on- line FRL methods cannot quantify the communication cost paid for exploring non non-optimal actions or exploiting optimal policies under the worst-case MDPs since the suboptimality
In addition, multiple technical challenges exist when trying to establish gap-dependent bounds and improve the exist- ing worst-case ones. First, gap-dependent regret analysis often relies on controlling the error the value function es- timations. However, the techniques for model-free methods (Yang al., 2021; Xu et al., 2021; Zheng et al., 2025b) can only adapt to instant policy updates in single-agent methods, while FRL often uses delayed policy updates for low com- munication cost. Second, proving low communication costs for FRL algorithms often requires actively estimating the number of visits to each satte-action-seey triple (see, e.g..
2

---

Cap-Dependent Bounds for Federated Q-Learning
Woo et al. (2023)). However, this is challenging for on- line algorithms because the implemented policy is actively updated, and a universal stationary visiting probability is unavailable. Existing online FRL methods reached loga- rithmic communication costs by controlling the visit and synchronization with the event-triggered synchronization conditions. These conditions guaranteed a sufficient in- crease in the number of visits to one state-action-step triple between synchronizations. However, this analysis is insuffi cient for the estimation of visiting numbers and results in the dependence on SA for the log T term.
policies, and to log( M MS///p). Since the communica- tion cost of each round is ((MHS), the total communica- tion cost is (2) multiplied by M
Compared to the existing worst-case communication rounds that depend on MS A log T (Zheng et al., 2024; 2025a; Qiao et al., 2022) or SA log T (Zheng et al., 2025a; Labbi et al., 2024), the first three terms in (2) only logarithmically de- pend on 1/Dmin and log and the last term removes the dependence on MSA from the log T term. This improve- ment is significant since M represents the number of col- laborating agents, and SA represents the complexity of the state-action space that is often the bottleneck of RL methods (Jin et al., 2018). Compared to the SA-free communication rounds for FRI. methods that do not update policies, (2) quantifies the cost of multiple components in online FRL: the first two terms represent the cost for exploration, and the last two terms show the cost of implementing the optimal policy (exploitation). Further technical details are provided in Section 3.3 and Section 5. Our numerical experiments, presented in Appendix B.2, demonstrate that the log T term in the communication cost is independent of M, S, and A.
Summary of Our Contributions. We give an affirmative answer to these important open questions by proving the first gap-dependent bounds on both regret and communication cost for online FRL in the literature. We focus on FedQ- Hoeffding (Zheng al., 2024), online FRL algorithm designed for tabular episodic finite-horizon MDPs. Our contributions are summarized as follows.
Gap-Dependen Regret (Theorem 3.1). Denote Amin as the minimum nonzero suboptimality gap for all the state- action-stey triples. We prove that sadQ-Hoefdiing guaran- tees a gap-dependent expected regret of
When M 1, FedQ-Hoeffding becomes single-agent al- gorithm with low global switching cost shown in (2) (Corol- lary 3.4). It removes the dependence on SA from the log T term compared to existing model-free methods (Bai et al., 2019; Zhang et al., 2020; Zheng et al., 2025b).
o 11 (MTSATT
+ +0,)
(L)
Amin
where C = MV MV (oo.//lo((MSA)T + M SA pro- vides the gap-free part. This bound is logarithmic in T and better than the worst-case -Tpttype regret discussed above when T' is large enough. When M = 1. (1) reduces to the single-agent gap-dependent regret upper bound established in Yang al. (2021) for CoefHfng (Jin et al., 2018), which is the single-agent counterpart of Feef--oof When T is large enough and Amin is small enough, (1) shows a better multi-agent speedup in terms of the average regret per episode, compared to the -tyt worst-case regrets shown in Zheng et al. (2024). We will present the theoretical details in Section 3.2 and Section 4. Our nu- merical experiments in Appendix B.1 also demonstrate the log T patteen of the regret for any given MDP.
Technical Novelty and Contributions. We develop a new theoretical framework for the gap-dependens analysis of on- line FRL with delayed policy updates. It provides two fea- tures simultaneously: controlling the error in the estimated value functions (Lemma 4.1) and estimating the number of visits (Lemma 5.2). The first feature helps prove the gap- dependent regret (1), and the second is key to proving the bound (2) for communication rounds. Here, to overcome the difficulty of estimating visiting numbers, we develop a new technical tool: concentrations on visiting numbers under varying policies. We establish concentration inequalities for visits with the stationary visiting probability of the opti- mal policies via error recursion on episode steps. This step relies on the logarithmic number of visits with suboptimal actions instead of the algorithm settling on the same policy. It provides better estimations of visiting numbers.
Gap-Dependent Communication Cost (Theorem 3.3). We prove that under some general uniqueness of optimal policies, for any p& E (0, 1), with probability at least - p. both the number of communication rounds and the num- ber of different implemented policies required by FedQ- Hoeffding are upper bounded by
We also establish the following techniques with the tool and nonzero minimum suboptimality gap: (a) Lemma 5.1: Ex- ploring visiting discrepancies between optimal actions and suboptimal actions. This validates the concentrations above. (b) Lemma 5.3: Showing agent-wiss simultaneous sufficient increase of visits. This helps remove the linear dependency on M in the last three terms of (2). (c) Lemma 5.4: Show- ing state-wise simultaneous sufficient increase of visits for states with unique optimal actions. This helps remove the linear dependence on SAA from the last term in (2).
HSSA
M
+ 11 log
A A
(MH + H2 log
T HSA
+ S3
2
min Cst
Here, Cae E (0, represents the minimum of the nonzero visiting probabilities to all state-step pairs under optimal
3

---

Gap-Dependent Bounds for Federated Q-Learning
To the best of our knowledge, these techniques are new to
and the Bellman optimality equation can be expressed
the literature for online model-free FRL, methods. They will be of independent interest in the gap-dependent analy- sis of other online RL and FRL methods in controlling or estimating the number of visits.
(s) - Eg (1))
(](s, = rn a) + B B...B. (-1s,)) (5')
VH+1(s) = 0, V(s a, h) E x Ax [H],
(3)
(g)(s) = maaxare (s,
(8, =- =ra(s,a) + Ber V (+') ( = O, V(s,,, a, h) E S A (H)
2. Background and Problem Formulation
2.1. Preliminaries
Suboptimality Gap. For any given MDP, we can provide the following formal definition of the suboptimality gap.
We begin by introducing the mathematical framework of Markov decision processes. In this paper, we assume that 0/0 = 0. For any C' E N, we use [C] to denote the set (1.2....C)) ... We use [[x]] to denote the indicator function, which equals 1 when the event x is true and O otherwise.
Definition 2.1. For any (s, a, h) E x A x [H], the sub- optimality gap is defined as
as) = (s) (h a).
Tabular Episodic Markov Decision Process (MDP). A tabular episodic MDP is denoted as M :=
P.),, where S is the set of states with [8] S,A is the set of actions with |A| A, H is the number of steps in each episode, IP = 1 ) A=1 is the transition kernel so that (. a) characterizes the distribution over the next state given the state action pair (s, a) at step h. and r == (rA, ) collection of reward functions. We assume that (x, a) E [0, is deterministic function of (s, a), while the results can be easily extended the case when rh random.
(3) implies that for any (s, a, h). (s, a) 2 0. Then, it is natural to define the minimum gap, which is the minimum non-zero suboptimality gap.
Definition 2.2. We define the minimum gap as
is the
Amin : inf (A)(s,a) An(s, > 0, v(s,a,))).
We remark that if
(s, An(s,o) > (s,a,, S Ax [M]] 0,
In each episode, an initial state $1 is selected arbitrarily by an adversary. Then, at each step h E [H] an agent observes a state 84 E S, picks an action aA E A, receives the reward Th = (sn, an) and then transits to the next state 81+11 The episode ends when an absorbing state 8H+1 is reached.
then all policies are optimal, leading to a degenerate MDP. Therefore, we assume that the set is nonempty and Amin > O in the rest of this paper. Definitions 2.1 and 2.2 and the non- degeneration are standard in the literature of gap-dependent analysis (Simchowitz & Jamieson, 2019; Yang et al., 2021; Xu et al., 2020).
Policies and Value functions. A policy π is collection of H functions { S A hIEHT] where A is the set of probability distributions over A. A policy is deterministic if for any E S, Ti (s) concentrates all the probability mass on an action Ví S R and Q7 S x A- - R denote the state value function and the state-action value function at step h under policy т. Mathematically, for any (s, h) E S x A x [H],
Global Switching Cost. We provide the following defini- tion for any algorithm with U > 1 episodes, which is also used in Bai et al. (2019) and Qiao et al. (2022).
A. In this case, denote n (s)
Let
Definition 2.3. The global switching cost for any learning algorithm with U episodes is defined as
U-1
Newitch
Σ
1( 1
4 n-)
V (oo (r 18h = s]
Here, n² is the policy implemented in the u-th episode.
and
2.2. The Federated RL Framework
(7(s,)) = r((saa))++
We consider an FRL setting with a central server and M agents, each interacting with an independent copy of M. The agents communicate with the server periodically: after receiving local information, the central server aggregates it and broadcasts certain information to the agents to coordi- nate their exploration.
Σ E( ar) (sh, an) = (s, a).. 1=1+1
Since the state and action spaces and the horizon are all fi- nite, there exists an optimal policy xt that achieves the optimal value (s) = sup, (s) = V (s) for all (s, h) E [H] (Azar et al., 2017). The Bellman equation
For agent m, let Um be the number of generated episodes, m, be the policy in the u-th episode of agent m, and xi
m,a
4

---

Cap-Dependent Bounds for Federated Q-Learning
be the corresponding initial state. The regret of M agents over π = HH) Em Um total steps is
At the end of round k, each agent sends
mik (r (s, (x)) m.kk (s)))(()) 1b41 (s, n (()(s)) s,
Um
(Tg =
Σ
- V/" ())))
to the central server for aggregation.
m MEIM] ==1
Updates of Estimated Value Functions. The central server a) for all triples. While letting Q a) = Q% (s,a) a) for triples such that n (s, a) = 0, it updates the estimated value functions for each triple with positive n (s. a) as follows.
Here, T' := T/M is the average total steps for M agents.
calculates ne (s, v (s,
We also define the communication cost of an algorithm as the number of scalars (integers or real numbers) communi- cated between the server and agents.
Case I: N (8, a) < 2M+(H+1)) =: in. This case implies that each client can visit each (s. a) pair at step h at most once. Let Q (s, a). Then the server iteratively update
3. Performance Guarantees
3.1. FedO-Hootldiing Algorithm
Q using the following assignment:
In this subsection, we briefly review FedO-Hoeffding. De- tails are provided in Algorithm 1 and Algorithm 2 in Ap- pendix C.I. FedQ-Hoeffding proceeds in rounds, indexed by k E ] Round A: consists of nz episodes for agent m, where the specific value of mm will be determined later.
t= Q _ nh (Th + h+1 + b, 1k--Q -Q). t= NR + 1, I,...,NNY N
and then assign 1 (s, a) with Q. Here, The NK. N/ are abbreviations for their respective values at (s, a), The E (0, 1] is the learning rate, b, > 0 is a bonus, and V repre- sents the (t - (C-N))-a )-th nonzero value in {o (s, a)) m-
For the j-th (j E (n) episode for agent m in the k-th round, we use {(s k. .at. k.J.m ,hh R...m) 1
Notations.
J==1 to m.k (s, a) as the number of times that (s, a, h)) has been visited by agent M n/
denote the corresponding trajectory. Denote nh
Case 2: Nº (s. a) 2 in- In this case, the central server calcu- lates the global estimate of the expected return v/ (8. a)
m in round k n (s, a) == Em=1 ni "s, a) as the total number of visits in round A for all agents, and (s, as the total number of visits to (s, a, h) among all agents before the start of round k. We also use (V*= S + - R and {Q%= S x A + R) to denote the global estimates of the state value function and state-action value function at the beginning of round k. Before the first round, both estimates are initialized as H.
DM wi (s. (n/////... (s, a) and updates the Qesstimate as
2h41 -1-1// Qh + n/t (rn + 2h+11) + 2
Here, Thi Qh, Q -h+ are abbreviations for their respec- tive values at (s,a), Te,a E [0, is the learning rate and Bh S > 0 represents the bonus.
h.k
After updating the estimated Q-function, the central server updates the estimated V V-function and the policy as
Coordinated Exploration. At the beginning of round k. the server decides a deterministic policy ~² = ( and then broadcasts it along with (N, +x)) )., and (s))a, to agents. Here, 7 can be chosen arbitrarily. Then, the agents execute π and start collecting trajectories. During the exploration in round k; every agent m will moni- tor its number of visits to each (s, a, h). For any agent m, at the end of each episode, if any (s, a, h) has been visited by
V*+1(s) = min { H, max Q (s. d'EA
and
k+ (s) = arg max Q Q++1 (s, a'). Th
d'EAA Such update implies that Feef--igg is an optimism- based method. It then proceeds to round k + 1.
(Ess a) max {1.
MH(H [ }
(s) a)
(4)
In
agents only send local estimates instead of original trajectories to the central server. This guaran- tees a low communication cost for each round, which is (M HS). In addition. the -riggeriggeere termination con- dition with the threshold (4) limits the number of new visits in each round, with which Zheng et al. (2024) proved the linear regret speedup under worst-case MDPs. Moreover, it guarantees that the number of visits to the triple that sat- isfies the trigger condition sufficiently increases after this round. This is the key to proving the worst-case logarithmic communication cost in Zheng et al. (2024).
times by agent m, the agent will send a signal to the server, which will then abort all agents' exploration. Here, we say that (s, a, h) satisfies the trigger condition in round k. During the exploration, for all (s, a, h). agent m adaptively calculates ni (s, a) and the local estimate for the next-step return xx (s, a) by
mi,k
mmkk
Vhh ( (5 (s k.j.m a c... = (s, as)
5

---

Cap-Dependent Bounds for Federated Q-Learning
3.2. Gap-Dependent Regret
Compared to requiring unique optimal policy, G-MDPs allow the optimal actions vary outside the support under optimal policies, i.e., the state-step pairs with P = 0.
Next, we provide a new gap-dependent regret upper bound for
algorithm.
Theorem 3.1. Let 11 log(MSAT)) For FedQ- Hoeffding (Algorithms/ 1 and 2). E (Regret(T)) can be bounded by
For a G-MDP, we define C.e = min I s S, E [H], P > 0}. Thus, 0 < Cst S reflects the minimum visiting probability on the support of optimal policies. Next, we provide gap-dependent upper bound for the number com- munication rounds and communication costs.
( 11 SA4 + SAVIISAVT++ET
(5)
Amin
Theorem 3.3. For any P E (0, 1), define to log( MSAT) Then under the full synchronization and random initializa- tion assumptions, with probubility at least 1 p. FedQ- Hoeffding (Algorithm I and Algorithm 2) satisfies the fol- lowing relationship for any given G-MDP:
The proof is provided in Appendix F. Theorem 3.1 shows that the regret is logarithmic in T for MDPs with positive minimum gap Amin- When T is sufficiently large, it is better than the v -Typpe worst-case regrets in the literature.
When M = 1, the bound reduces to
SA 2
o (
lo5AlogSAAT
K KSO o SA
+ SH
A
Amin
min
(MH
SAL
T
which matches the result in Yang et al. (2021) for the single- agent counterpart, Hoe-Hooffding algorithm. Therefore, when T is sufficiently large, for the average regret per episode defined as (Mg)) the ratio between Fedf-Hoeffding and UCe-Hoeffding O11MM), which serves as our error reduction rate. As a comparison, it is better than the rates under worst-case MDPs for online FRL methods in the literature, which are ((//VM) because of their linear dependency on VMT. We will also demon- strate this ((1/) pattern in the numerical experiments in Appendix B.I.
+ S
A
min Cst
+ H2
log
)
HSA
(6)
We can get the upper bound of total communication cost by multiplying the upper bound in (6) and O(MHS), the com- munication cost of each round in FedQ-Hooffdinng We will highlight the key technical tools for proving Theorem 3.3 in Section 5.1, provide a sketch of proof in Section 5.2, and give a complete proof in Appendix G.
Compared to existing worst-case costs that depend on SA (Zheng et al., 2025a; Labbi et al., 2024) or MSA (Zheng et al., 2024: 2025a; Qiao et al., 2022) for log T, (6) is better when T is sufficiently large since the first three terms only logarithmically depend on 1/ 1/Amin and log T, and the last term that is logarithmic in removes the dependency on MSA SA. Moreover, (6) highlights the cost for different proce- dures in FedQ-Hoeffding: the first two terms represent the cost for exploration, and the last two terms show the cost when exploiting the optimal policies. We will provide more theoretical explanations in Section 5. Our numerical experi- ments in Appendix B.2 also demonstrate that the log T term in the communication cost is independent of M, S, and A.
3.3. Gap-Dependent Communication Cost
We first introduce two additional assumptions:
(I) Full synchronization. Similar to Zheng et al. (2024), we assume that there no latency during the communications, and the agents and server are fully synchronized (MeMahan et al., 2017). This means nT = n² for each agent m. (II) Random initialization. We assume that the initial states {s k. Jkj.m are randomly generated following some dis- tribution on S, and the generation is not affected by any result in the learning process.
Since FedQ-Hoeffding implements a fixed policy in each round, when M 1, the algorithm reduces to single-agent algorithm with a low global switching cost. The result is formally shown in Corollary 3.4.
Next, we introduce new concept: G-MDPs. Definition 3.2. A G-MDP satisfies two conditions:
(a) The stationary visiting probabilities under optimal poli- cies are unique: if both nrd and 2 are optimal policies, then we have P (s), = =s/x = P (sp- = +27+ =; P
Corollary 3.4. For any E (0, 1), define = log( SAT P Then under the random initialization assumption, for any given G-MDP, with probability at least 1 1- p. the global switching cost for FedQ- Hoeffdii algorithm (Algorithm I and Algorithm 2 with M 1) can be bounded by
arg max (7, a')}. For any (s, h) E S [H] if TPm 0. then [s,[)) = 1, which means that the optimal action is unique.
(b) Let (3(s) = {a|
H1 SA12A12
o S'
+ H S
G-MDPs represent MDPs with generally unique optimal policies. (a) and (b) above characterize the general unique- ness, and an MDP with a unique optimal policy is G-MDP.
A2
Cea
T
+ H
HSA
6

---

Gap-Dependent Bounds for Federated Q-Learning
Given that the switching costs of existing single-agent model-free algorithms depend on SA (Bai et al., 2019; Zhang et al., 2020) or S (Zheng et al., 2025b) for log T", our log T -eeeeddenccy is better by removing the factor SA.
Next, Lemma 4.2 characterizes the relationship between the expected regret and the total error (Q) (s,
Lemma 4.2. For Feef--Hoffdiing (Algorithm and Algo-
rithm 2), the expected regret EE ((Regret((T) is bounded by
At the end of this section, we briefly discuss RedQ-Bernstein another online FRL algorithm in Zheng et al. (2024). Com- uses different bonuses (be and ( that incorporate variance estimators. Although FedQ-Bernstein achieves a vH factor improve- ment in worst-case regret while maintaining identical worst- case communication costs (Zheng et al., 2024), our analysis in Appendix and Appendix shows both algorithms share the same gap-dependent bounds ((5), (6)). Whether FedQ- Bernstein can achieve tighter gap-dependent regret bounds remains an open question.
E
Σ A= k.j.a
k.im clipl(Qh (%00 ,a (.ddm) Amin]
pared to RedQ-Hoefftdine
The proof of Lemma 4.2 is provided in Appendix F.3. By combining Equation (8) in Lemma 4.1 and Lemma 4.2 and using the definition of expectation, we can bound the expected regret and finish the proof of Theorem 3.1. Further details can be found in Appendix F.4.
5. Bounding the Communication Cost with (6)
4. Bounding the Regret with (5)
5.1. Bounding the Number of Visits
In this section, we bound the gap-dependent regret by con- trolling the error in value function estimations. Define clipfær w]] = x [[ 2 w]. Let e log( 2SAHT) where ō E 10 and Ti < 2T + MHSA is an known upper bound of the total steps T as defined in (e) of Lemma E. We provide Lemma 4. to control the total error in the value function estimations (Qh. (s,
In this subsection, we introduce the new technical tool for estimating visiting numbers. We first provide Lemma 5.1 that quantifies the frequency and the probability of imple- menting non-optimal actions.
Lemma 5.1. For any 5 E (0, 1) and any given deterministic optimal policy n,, with probability at least 1 - 36, we have
Lemma 4.1. For FedQ- -Hoeffding (Algorithm I and Algo- rithm 2). for any E (0, 1), with probability at least 8, the following two conclusions hold for any e HO;
Σ
Σ
k.j. o
& Ah (t. S C'in
(9)
h=1 J.
PP
ah
k.jm
+ t (o
mM S 40min, 4h E [H].
H
I(Oh - (5) k..m k.d.
2 2 S Ce- (7)
k.j.on
(10)
R=1 R.J.m
Here Cmin equals C. in Lemma 4.1 with Amin-
H
For each of keam & (o the optimism of FedQ- Hoeffding ensures that
Σ
Σ
dipl(Ch - (o) oh ( [e] S SeCr. (8)
1= k.j.a
(ot - 27) (s k.m. ,ah (.s.m) 2 Amin
Here
SA
MH MALH+MMHSSAA
with high probability. Therefore, by taking e = Amio in (7), we can bound
CC=
k.m a
& Ah
where > O is sufficiently large constant.
The proof of Lemma 4.1 l is in Appendix F.2. Both bounds depend on log T when c is fixed. Compared to the methods for single-agents algorithms (see, e.g., Yang et al. (2021)), Lemma 4.1 also accommodates the delayed policy updates, and its dependency on M reflects the cost of collaborating multiple agents. We will let Amin later.
in (9) and its conditional expectation in (10). See Ap- pendix G.2 for details of the proof.
Since Cmin scales logarithmically with T, (9) shows that the frequency of non-optimal action selections becomes negli- gible compared to T asymptotically. This means that most states in the learning process are generated under optimal actions and reveals the visiting discrepancy between optimal and non-optimal actions in the gap-dependent analysis.
II the literature, these bounds are for local switching cost that counts the state-step pairs where the policy switches. The local switching cost is greater than equal to the global switching cost, but these works didn't find tighter bounds for the global switching cost. We refer readers to Bai et (2019) for more information.
Such discrepancy helps us quantify the communication cost paid for exploring non-optimal actions. The threshold of
7

---

Cap-Dependent Bounds for Federated Q-Learning
the synchronization condition (4) implies that the number of visits the triple (s, a, ht) that satisfies the trigger condi- tion increases by at least 1/(2M (H + 1)) times. Conse- quently, the logarithmic upper bound for non-optimal visits, as provided in (9), implies a log -tyype communica- tion cost for exploration, which is reflected in the first two terms of (6). These two terms depend on SA because FedQ- Hoeffding only ensures a sufficient increase in the number of visits for one triple in a round. We remove the depen- dency on M from the second term by proving agent-wise simultaneous sufficient increase of visits (Lemma 5.3), lever- aging the stationary visiting probability under their common policy in a round.
P(sk, )²). However, the varying policies employed by Fedf-Hoeffding across different rounds prevent direct alignment between the executed policy x and the optimal policy 'τ. To overcome this challenge, our proof establishes a relationship between P(sk, = 8 | x²) and the optimal stationary visiting probabilities IP through error recur- sion over the step h. This analysis exploits the discrepancy in visit counts between optimal and non-optimal actions, which is a distinctive feature enabled by the gap-dependent structure. Especially, we prove that for any h' E [f]].
Σ
P P( R.j. = = = P
Next, we bound the number of visits to the optimal visits. For any W' E [K], let Rx = -== -k Ej.m 1 be the number of episodes in the first k' rounds. Lemma 5.2 quantifies the difference between the number of visits to any (s, a, h) with a E AA, (8) in the first k' rounds and the expected number of visits Rg.P,, a under the optimal policy.
11-1
$ 2
Σ h=1
P
k.j. # t ( | art)
which is further bounded by (10) in Lemma 5.1 and helps complete the proof of Lemma 5.2. See Appendix G.3 for more details of the proof.
Lemma 5.2. For any d E (0, 1), with probability at least 1 - 56, the following conclusion holds simultaneously for any (s, h, k') E S
5.2. Proof Sketch of Theorem 3.3
x
[M] x [K]:
With the tools introduced Section 5.1, we outline the key steps in proving the gap-dependent bound (6) for the number of communication rounds.
I
AT) k.j. s, on k.j.a E P2
k=1 J.m
Let d' = log ( (2MSAHT, ), i1 200M + +))'', is 6500HH&Cmin/ee /Ctt and C = IH + 1)). In this subsec- tion, for any (s, h) E S x [H] such that s >> 0, we use TT (s) to denote its unique optimal action.
< /v
Re.IP 5, + 32HCCin
Lemma 5.2 establishes that the average number of visits to (s, a, h) with (s) per episode will converge to the stationary visiting probability P under the optimal policies. Furthermore, it implies that for any (8, a h k) such that IP > O and xs)(),
Lemma 5.3 shows agent-wise simultaneous sufficient in- crease of visits for the triple (s, a, h) that satisfies the trigger condition in round k when N/, a) > i1.
Lemma 5.3. For any d E (0, 1), with probability at least 1- 8,
NA+1 (s, RAP,,, 5v R&P.t " -320-32HCm 32HCmin:
(s,o) 2 (1+ + (1+0/3)N
R.P. t. + 5 RR 32HCmin
holds simultaneously for any (8,a, a, h k) E S 1 AX (H) x [K] such that N (s, a) > in and the triple (8, a h) satisfies the trigger condition (4) in round k.
Therefore, when (s, a) is sufficiently large (ensuring that both Ra-1 P and RrP are sufficiently large), the ratio N/ (s, a)/ /N/ (s, a) approximates R2/ R Since Re/ Ra-1 is independent of (s, fi), the number of visits to each optimal (s, (s. h) (IP A > O and a is the optimal action) increases at similar speed. This explains why the communication cost for exploiting the unique optimal action after sufficient visits (the last term of (6)) does not depend on the factor SA. The dependence on M is also removed due to the agent-wiss wise simultaneous sufficient increase. Ad- ditionally, we remark that the third term of (6) accounts for cost with insufficient visit counts.
The proof of Lemma 5.3 can be found in Appendix G.4.
Lemma 5.4 shows the state-wise simultaneous sufficient increase of visits for states with unique optimal actions, which is proved based on Lemma 5.2.
Lemma 5.4. For any i E (0, 1), with probability at least 55, the following events hold simultaneously for any E [K]: If there exists (so, on, ho) E S x A x [H], such that it satisfies the trigger condition (4) in round k and NE. (so, ao) > i + iz. then ag E Arn (so).
Finally, we provide the intuition for the proof of Lemma 5.2. Standard concentration incqualities typically relate the num- ber of visits of (s. h) to the policy-dependent probability
Furthermore, if the state atate-action-ste triple (su. ao ho) also satisfies that TP* so > O, then for any ,h) E S x (H)
8

---

Cap-Dependent Bounds for Federated Q-Learning
such that P st,be O, we have
When such a trigger occurs, we have N (s, a) > i1. and Lemma 5.3 implies that the number of visits the triple (s, a, h) increases by at least C/3 times. Therefore, the maximum number of Type- triggers for any such triple is
NW (s 2 (1+ (())
The complete proof of Lemma 5.4 is in Appendix G.5.
o (ig( ) (H(Hlogg(e))
We now analyze the number of rounds in which the trigger condition is satisfied, categorized according to the four cases corresponding to the terms in (6). A detailed discussion can be found in Appendix G.6.
log(1+0/33
Then the number of rounds with Type-Ill triggers is no more than O S log(12)).
Type-I Trigger: It occurs when triple (s, a, h) satisfies the trigger condition in round & with N (s, a) $ i1.
Type-IV Trigger: It occurs when a triple (s, a, h) satisfies the trigger condition in round & with (s, a) in + ig.
For each time the trigger condition is met by triple (s, a, h), the number of visits to it increases by at least C/2M times. Therefore, the maximum number of Type-I triggers for any triple (8, a, h)) is
In this case, whenever the trigger condition is satisfied by (s, a, h) in round k. we have N (s,a) > i2 > 32 and a E (s) by Lemma 5.4. Furthermore, since Lemma 5.2 establish an upper bound of 32 on the number of visits triples (s', a', where P 0. we can conclude that with high probability, F > 0 and T (s) holds.
log( log(1 + C/(2M)) = (MHH
Thus, the number of rounds with Type-I triggers is no more (f1)).
By Lemma 5.4, for any state-step pair (s', h) E (H) such that P2 >> O, the number of visits to (8', (s),, simultaneously increases by at least C/6 times. Therefore, the maximum number of rounds with Type-IV triggers is
than O (MH'
Type-II Trigger:
It occurs when a triple (s,a, (9,aah) h) satisfies the trigger condition in round & with i < (s,a) S d + 22 and either & (s) or a E (s) and P 3,4 0.
By Lemma 5.3, which establishes the agent-wise simulta- neous sufficient increase, the number of visits to the triple (s, a, h) increases by at least C/3 times each time the trigger condition satisfied.
log(TT((n + +2)) log(1 + C/6)
<0(P2 log
[H
H2
)) (HSA)
T HSA
By aggregating the bounds on the number of communication rounds across all four cases, we derive the gap-dependent upper bound presented in (6).
Furthermore, as shown in (9) of Lemma 5.1 and Lemma 5.2 with P 0, for state-action-step triple (s, a, h) where & (s) or E (s)s) and P2,, O, the total number of visits is bounded by 32HCmin with high probability. Conse- quently, the maximum number of Type-Il triggers for any such triple is
6. Conclusion
In this paper, we establish the first gap-dependent bounds on regret and communication cost for online federated Q- Learning in tabular episodic finite-horizon MDPs, address- ing two important open questions in the literature. While existing FRI methods focus on worst-case MDPs, show that when MDPs exhibit benign structures, such strictly positive suboptimality gap, the worst-case bounds can be significantly improved. Specifically, we prove that both Feef-Hoeffding and FedQ-Bernstein can achieve logarith- mic regret. Additionally, we derive gap-dependent com- munication cost upper bound that disentangles exploration and exploitation, with the log I" term the bound being independent of M, S, and A. This makes work the first result in the online FRI. literature to achieve such a low communication cost. When M = 1, our gap-dependent communication cost upper bound also yields a tighter global switching cost upper bound, removing the dependence on S SA from the log T term.
o log (10g(32FFCmm))) mnin/ii))) log(1 + C/3)
(HSAA) A min
S
[H log
H2
2
Then the upper bound for the number of rounds with Type-II triggers is
HOSAY )) 2 min
o H SAlog
Type-III Trigger: It occurs when triple (s, a, h) satisfies the trigger condition in round k with i (s, x i + i2, a E AA7 (8) and I+ 5, > 0.
For any triple (s, a, h) that satisfies Type-III triggers, condi- tion (b) of Definition 3.2 ensures that a is the unique optimal action T7 (s). Therefore, at most HS different triples can satisfy Type-Ill trigger conditions.

---

Doan, T., Maguluri, S., and Romberg, J. Finite-time analysis of distributed td (0) with linear function approximation on Cap-Dependent Bounds for Federated Q-Learning
Acknowledgment
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21, 2008
The work of H. Zhang, Z. Zheng, and L. Xue was supported by the U.S. National Science Foundation under the grants DMS-1953189 and CCF-2007823 and by the U.S. National Institutes of Health under the grant GR128825
Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International Con- ference on Machine Learning, pp. 263-272. PMLR, 2017.
Impact Statement
Bai, Y., Xie, T., Jiang, N., and Wang. Y.-.. Provably ef- ficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
This work significantly advances federated reinforcement learning (FRL. by improving regret and communication efficiency. Federated reinforcement learning has privacy- preserving properties by design, as it enables agents learn collaboratively without sharing strumental in various areas, such as healthcare, finance, and education, where sensitive information must be protected.
Banerjee, S., Bouzefrane. S., and Abane, A. Identity man- agement with hybrid blockchain approach: A deliberate extension with federated sederated-inverse-ree sewvers-reinfforemeee learning. 2021 IEEE 22nd International Conference on High Performance Switching and Routing (HPSR), pp. 1-6. IEEE, 2021.
data. This feature is in-
References
Beikmohammadi, A., Khirirat, S., and Magnússon, S. Com- pressed federated reinforcement learning with genera- tive model. arXiv preprint arXiv:2404. 2222244.06333 10635, 2024.
Agarwal, A., Kakade, S., and Yang, L. F. Model-based rein- forcement learning with generative model is minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020.
Chen, T., Zhang, K., Giannakis, G. B., and Başar, T. Communication-effie policy gradient methods for dis- tributed reinforcement learning. IEEE Transactions on Control of Network Systems, 9())917-929, 2021a.
Agarwal, M., Ganguly, B., and Aggarwal, V. Communi- cation efficient parallel reinforcement learning. In Un- certainty in Artificial Intelligence, pp. 247-256. PMLR, 2021.
Chen, Y., Zhang, X., Zhang, K., Wang, M., and Zhu, X. Byzantine-robust online and offline distributed reinforce- ment learning. In International Conference on Artificial Intelligence and Statistics, pp. 3230-3269. PMLR, 2023.
Agrawal, S. and Jia, R. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Ad- vances in Neural Information Processing Systems, 30, 2017.
Chen, Z., Zhou, Y., and Chen, R. Multi-agent off off-policy tde with near-optimal sample and communication complexity. In 2021 55th Asilomar Conference on Signals, Systems, and Computers, pp. 504-508. IEEE, 2021b.
Al Marjani, A., Garivier, A., and Proutiere, A. Navigating to the best policy in markov decision processes. In Advances in Neural Information Processing Systems, pp. 25852- 25864, 2021.
Chen, Z., Zhou, Y., Chen, R.-R., and Zou, S. Sample and communication-effiicenl decentralized actor-critic algo- rithms with finite-time analysis. In International Con- ference Machine Learning, pp. 3734-3834. PMLR, 2022.
Anwar, A. and Raychowdhury, A. Multi-task federated reinforcement learning with adversaries. arXiv preprint arXiv:2103.06473. 2021.
Ashouri, A. H., Killian, W., Cavazos, J., Palermo, G., and Silvano, C. survey on compiler autotuning using ma- chine learning. ACM Computing Surveys (CSUR), 51(5): 1 1-42, 2018
Dann, Li, Wei, W., and Brunskill, E. Policy cer- tificates: Towards accountable reinforcement learning. International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
Assran, M., Romoff, J., Ballas, N., Pineau, J., and Rabbat, M. Gossip-based basiep actor-learner architectures for deep reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Dann, C., Marinov, T. V., Mohri, M., and Zimmert, J. Be- yond
gaps: Improved restance-epennee regret bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1-12, 2021.
Auer, P. and Ortner, R. Logarithmic online regret bounds for undiscounted reinforcement learning. In Advances in Neural Information Processing Systems, pp. 49-56. MIT Press, 2007.
10

---

Cap-Dependent Bounds for Federated Q-Learning
multi-agent reinforcement learning. In International Con- ference on Machine Learning, pp. 1626-1635. PMLR, 2019.
He, J., Zhou, D., and Gu, Q. Logarithmic regret for rein- forcement learning with linear function approximation. In International Conference Machine Learning, pp. 4171 4110. PMLR, 2021.
Doan, T. T., Maguluri, S. T., and Romberg. J. Finite-time performance of distributed temporal-dine -effereldifferrenee learning with linear function approximation. SIAM Journal on Mathematics of Data Science, 3(1):298-320, 2021.
He, J., Wang, T., Min, Y., and Gu, Q. A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. Advances in neural information processing systems, 35:4762 4775, 2022.
Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 578-598. PMLR, 2021.
Hsu, H.-L., Wang, W. Pajic, M., and Xu, P. Random- ized exploration in cooperative multi-agent reinforcement learning. arXiv preprint arXiv:2404. 100022444.0778, 2024.
Dubey, A. and Pentland, A. Provably efficient cooperative multi-agent reinforcement learning with function approx- imation. arXiv preprint arXiv:2103.0499 2021.
Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dunning, I. al. Impala: Scalable distributed deep-rl with im- portance weighted actor-learner architectures. In Interna- tional Conference on Machine Learning, pp. 1407-1416. PMLR, 2018.
Jin, C., Allen-Zhu Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? Advances in Neural Infor- mation Processing Systems, 31, 2018.
Jin, C., Yang. Z., Wang. Z., and Jordan, M. Provably effi- cient reinforcement learning with linear function approxi- mation. In Conference learning theory, pp. 2137-2143. PMLR, 2020.
Fan, F. X., Ma, Y., Dai, Z., Jing, W., Tan, C., and Low, B. K. H. Fault-tolerant federated reinforcement learning with theoretical guarantee. Advances in Neural Informa- tion Processing Systems, 14:1007110 2021.
Jin, H., Peng, Y., Yang, W., Wang, S., and Zhang, Z. Feder- ated reinforcement learning with environment heterogene- ity. In International Conference on Artificial Intelligence and Statistics, pp. 18-37. PMLR, 2022.
Fan, F. X., Ma, Y., Dai, Z., Tan, C., and Low, B. K. H. Fed- hql: Federated heterogeneous q-learning. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 2810-2812, 2023.
Jonsson, A. Kaufmann, E., Ménard, P., Dar- wiche Domingues, O., Leurent, E., and Valko, M. Planning in markov decision processes with gap- dependent sample complexity. In Advances in Neural Information Processing Systems, pp. 1253-1263, 2020.
Ganesh, S., Chen, J., Thoppe, G., and Aggarwal, V. Global convergence guarantees for federated policy gradient methods with adversaries. arXiv preprint mrXiv:2403.099400 2024.
Kakade, S., Wang, M., and Yang, L. Variance reduc- tion methods for sublinear reinforcement learning. arXiv preprint 102.v91802.09188 2018.
Gao, Z., Han, Y., Ren, Z., and Zhou, Z. Batched multi- armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Khodadadian, S., Sharma, P., Joshi, G., and Maguluri, S. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference Machine Learning, pp. 10997-11057, PMLR, 2022.
Gong, W. Cao, L., Zhu, Y., Zuo, F., He, X., and Zhou, H. Federated inverse reinforcement learning for smart icus with differential privacy. IEEE Internet of Things Journal, 101211:19117-11122 2023.
Krishnan, S., Yang, Z., Goldberg, K., Hellerstein, J., and Stoica, I. Learning to optimize join queries with deep reinforcement learning, arXiv preprint 1rXiv:1808.03/99 2018.
Guo, Z. and Brunskill, E. Concurrent pac rl. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 29, pp. 2624-2630, 2015.
Labbi, S., Tiapkin, D., Mancini, L., Mangold, P., and Moulines, E. Federated ucbvi: Communication--ffiiienn federated regret minimization with heterogeneous agents. arXiv preprint arXiv:2410. 22908, 2024.
Hanzely, F. and Richtárik, Federated learning of a mixture of global and local models. arXiv preprint arXiv:2002.055// 2020.

---

Gap-Dependent Bounds for Federated Q-Learning
Lan, G., Wang, H., Anderson, J., Brinton, C., and Aggarwal, V. Improved communication efficiency in federated natu- ral policy gradient via admm-based gradient updates. In Proceedings of the 37th International Conference on Neu- ral Information Processing Systems, pp- 59873-59885, 2023.
Ménard, P., Domingues, O. D., Shang. X., and Valko, M. Uch momentum q-learning: Correcting the bias with- out forgetting. In International Conference Machine Learning, pp. 7609-7618 PMLR, 2021.
Min, Y., He, J., Wang, T., and Gu, Q. Cooperative multi- agent reinforcement learning: Asynchronous commu- nication and linear function approximation. In Inter- national Conference on Machine Learning, pp. 24785- 24811. PMLR, 2023.
Lan, G., Han, D.-J.. Hashemi, A., Aggarwal, V., and Brin- ton, C. G. Asynchronous federated reinforcement learn- ing with policy gradient updates: Algorithm design and convergence analysis. arXiv preprint arXiv:2404.080003 2024.
Mirhoseini, A., Pham, H., Le, Q. V., Steiner, B., Larsen, R., Zhou, Y., Kumar, N., Norouzi, M., Bengio, S., and Dean, J. Device placement optimization with reinforce- ment learning. In International Conference on Machine Learning, pp. 2430-2439, PMLR, 2017.
Li, G., Shi, L.., Chen, Y., Gu, Y., and Chi, Y. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34: 14:11772-17776 2021.
Mnih. V., Badia, A. P., Mirza, M.. Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K. Asyn- chronous methods for deep reinforcement learning. In International Conference on Machine Learning, pp. 1928- 1937. PMLR, 2016.
Li, G., Cai, C., Chen, Y., Wei, Y., and Chi, Y. Is q-learning minimax optimal? tight sample complexity analysis. Operations Research, 72(1):22,- 2024.
Li, T., Song, L., and Fragouli, C. Federated recommen- dation system via differential privacy. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2592-2597. IEEE, 2020.
Nguyen, P., Tran, T., Gupta, S., Rana, S., Barnett, M., and Venkatesh, S. Incomplete conditional density estimation for fast materials discovery. In Proceedings of the 2019 SIAM International Conference on Data Mining, pp. 549
Liu, R. and Olshevsky, A. Distributed td (0) with almost communication. IEEE Control Systems Letters, 2023.
557. SIAM, 2019.
Liu, S. and Zhu, M. Distributed inverse constrained rein- forcement learning for multi-agent systems. Advances in Neural Information Processing Systems, 35:33444- 33456, 2022.
Nguyen-Tane Tang, T., Yin. M., Gupta, S., Venkatesh, S., and Arora, R. On instance-dependene bounds for offline re- inforcement learning with linear function approximation. In Proceedings of the AAAI Conference on Artificial In- telligence, pp. 9310-9315 2023.
Liu, S. and Zhu, M. Meta inverse constrained reinforce- ment learning: Convergence guarantee and generaliza- tion analysis. In The Twelfth International Conference Learning Representations, 2023.
Ok, J., Proutiere, A., and Tranos, D. Exploration in struc- tured reinforcement learning. Advances in Neural Infor- mation Processing Systems, 31, 2018.
Liu, S. and Zhu, M. Learning multi-agent behaviors from distributed and streaming demonstrations. Advances in Neural Information Processing Systems, 36, 2024.
Perchet, V., Rigollet, P., Chassang, S., and Snowberg, Batched bandit problems. The Annals of Statistics, 44(2): 660 681, 2016.
Liu, S. and Zhu, M. In-trajectory inverse reinforcement learning: Learn incrementally before an ongoing trajec- tory terminates. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2025.
Qiao, D., Yin, M., Min, M., and Wang. Y.-.. Sample- efficient reinforcement learning with loglog (t) switching cost. In International Conference Machine Learning, pp. 18031 18061.. PMLR, 2022.
Marjani, A. and Proutiere, A. Best policy identification in discounted mdps: Problem-specific sample complexity. arXiv preprint arXiv:2009. 13405, 2020.
Salgia, S. and Chi, Y. The sample-communication com- plexity trade-off in federated q-learning. In Advances in Neural Information Processing Systems, 2024.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and Arcas, B. A. Communication-cftiiii learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 1273-1282, PMLR, 2017.
Shen, H., Zhang, K., Hong, M., and Chen, T. Towards un- derstanding asynchronous advantage actor-critic: Conver- gence and linear speedup. IEEE Transactions on Signal Processing, 2023.
12

---

Gap-Dependent Bounds for Federated Q-Learning
Simchowitz, M. and Jamieson, K. G. Non-asymptotic gap- dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, 2019.
Wang, T., Zhou, D., and Gu, Q. Provably efficient reinforce- ment learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems, 34: 13521-13536,,0 2021.
Smith, V., Chiang, C.-K., Sanjabi, M., and Talwalkar, A. S. Federated multi-task learning. Advances in neural infor- mation processing systems, 30, 2017.
Wang, X., Cui, Q. and Du, S. S. On gap-dependent bounds for offline reinforcement learning. Advances in Neural Information Processing Systems, 35:14865-14877 2022.
Sun, J., Wang, G., Giannakis, G. B., Yang, Q., and Yang. Z. tinite-time analysis of decentralized capporal-diffrenne learning with linear function approximation. In Interna- tional Conference on Artificial Infelligence and Statistics, pp. 4485-4495. PMLR, 2020.
Watkins, J. C. H. Learning from Delayed Rewards. PhD thesis, King's College, Oxford, 1989.
Woo, J., Joshi, G., and Chi, Y. The blessing of heterogene- ity in federated q-learning: Linear speedup and beyond. International Conference on Machine Learning, pp. 37157-37216, 2023.
Sutton, R. and Barto, A. Reinforcement Learning: An Introduction. MIT Press, 2018.
Tewari, A. and Bartlett, P. Optimistie linear programming gives logarithmic regret for irreducible mdps. In Ad- vances in Neural Information Processing Systems, pp. 1505-1512, 2008.
Woo, J., Shi, L., Joshi, G., and Chi, Y. Federated offline reinforcement learning: Collaborative single-policy cov- erage suffices. In International Conference on Machine 2024.
Learning, pp.
Tirinzoni, A., Al Marjani, A., and Kaufmann, E. Near instance-optimal pac reinforcement learning for determin- istic mdps. In Advances in Neural Information Processing Systems, pp. 8785-8798, 2022.
Wu, Z., Shen, H., Chen, T., and Ling, Q. Byzantine- decentralized policy evaluation with linear function ap- proximation. IEEE Transactions on Signal Processing, 69:3839-3853, 2021.
Tirinzoni, A., Al-Marjani, A., and Kaufmann, E. Optimistic pac reinforcement learning: the instance-dependen view. In International Conference on Algorithmic Learning Theory, pp. 1460-1480. PMLR, 2023.
Xu, H., Ma. T., and Du, S. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step boot- strap. In Conference on Learning Theory, pp. 4438-4472. PMLR, 2021.
Wagenmaker, A. and Jamieson, K. G. Instance-dependent near-optimal policy identification in linear mdps via on- line experiment design. Advances in Neural Information Processing Systems, 35:5968-5988 2022.
Xu, T., Wang, Z., Zhou, Y., and Liang, Y. Reanalysis of variance reduced temporal difference learning. In International Conference on Learning Representations, 2020.
Wagenmaker, A. J., Chen, Y., Simchowitz, M.. Du, S., and Jamieson, K. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learn- ing, pp. 22384-22429. PMLR, 2022a.
Yang, K., Yang, L., and Du, S. Q-learning with logarithmic regret. In International Conference on Artificial Intelli- gence and Statistics, pp. 1576-1584. PMLR, 2021.
Yang, T., Cen, S., Wei, Y., Chen, Y., and Chi, Y. Fed- erated natural policy gradient and actor critic methods for multi-task reinforcement learning. Advances in Neu- ral Information Processing Systems, 17:121304-121377 2024.
Wagenmaker, A. J., Simchowitz, M., and Jamieson, K. Be- yond no regret: mnstance-dependee pac reinforcement learning. In Conference on Learning Theory, pp. 358- 418. PMLR, 2022b.
Yu, X., He, Z., Sun, Y., Xue, L., and Li, R. The effect of personalization fedprox: fine-grained analysis on statistical accuracy and communication efficiency. arXiv preprint arXiv:2410.08934 2024.
Wai, H.-T. On the convergence of consensus algorithms with markovian noise and gradient bias. In 2020 59th IEEE Conference Decision and Control (CDC), pp. 4897-4902. IEEE, 2020.
Zanette, A. and Brunskill, E. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Interna- tional Conference on Machine Learning, pp. 7304-7312. 7312. PMLR, 2019.
Wang, G., Lu, S., Giannakis, G., Tesauro, G., and Sun, J. Decentralized td tracking with linear function approxi- mation and its finite time analysis. Advances in Neural Information Processing Systems, 33:13762-13772 2020.
13

---

Gap-Dependent Bounds for Federated Q-Learning
Zeng, S., Doan, T. T., and Romberg, Finite-time analysis of decentralized stochastic approximation with applica- tions in multi-agent and multi-task learning. In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 2641-2646 IEEE, 2021.
in stochastic and deterministic environments. In Inter- national Conference Machine Learning, pp. 42878 42914. PMLR, 2023.
Zhang, C., Wang, H., Mitra, A., and Anderson, J. Finite- time analysis of on-policy heterogeneous federated rein- forcement learning. In ICLR, 2024a.
Zhang. Z., Zhou, Y., and Ji, X. Almost optimal model-free reinforcement learning via reference-ad reference-advantage decom- position. Advances in Neural Information Processing Systems, 33:15198 13:15118-15207,, 2020.
Zhang, Z., Ji, X., and Du, Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference Learning Theory, pp. 4528 4531. PMLR, 2021.
Zhang, Z., Ji, X., and Du, S. Horizon-fiee reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory, pp. 3858- 3904. PMLR, 2022a.
Zhang, Z., Jiang, Y., Zhou, Y., and Ji, X. Near-optimal regret bounds for multi-batch reinforcement learning. Advances in Neural Information Processing Systems, 35:24586- 24596, 2022b.
Zhang, Z., Chen, Y., Lee, J. D., and Du, S. S. Settling the sample complexity online reinforcement learning. In Conference Learning Theory, pp. 5213-5219. PMLR, 2024b.
Zhao, F., Ren, X., Yang, S., Zhao, P., Zhang, R., and Xu, X. Federated multi-objective reinforcement learning. Infor- mation Sciences, 624:811-833 2023.
Zheng, Z. Gao, F,, Xue, L., and Yang. J. Federated q- learning: Linear regret speedup with low communication cost. In The Twelfth International Conference Learn- ing Representations, 2024.
Zheng, Z., Zhang, H., and Xue, L. Federated q-learning with reference-advantain decomposition: Almost opti- mal regret and logarithmic communication cost. In The Thirteenth International Conference on Learning Repre- sentations, 2025a.
Zheng, Z., Zhang, H., and Xue, L. Sap-dependent bounds for gelaarning using reference-advantage decomposition. In The Thirteenth International Conference on Learning Representations, 2025b.
Zhou, R., Zihan, Z., and Du, S. S. Sharp variance-dependent bounds in reinforcement learning: Best of both worlds
14

---

Cap-Dependent Bounds for Federated Q-Learning
Organization of the appendix. In the appendix, Appendix A reviews related works. Appendix B presents the results of our numerical experiments, demonstrating log 7type regret and showing that the log 7 term of the communication cost is independent of M, S, and A. Appendix C provides algorithmic details for both the FedQ-Hooffding and Feen--Brnsteen algorithms. Appendix D and Appendix E include some useful lemmas. Appendix F contains the proof of the gap-dependent regret bound (Theorem 3. l). Appendix G presents the proof of the gap-dependent communication cost bound (Theorem 3.3).
A. Related Work
online RL for Single Agent RL with Worst-Case Regret. There are mainly two types of algorithms for reinforcement learning: model-based and model-free learning. Model-based algorithms learn model from past experience and make decisions based on this model, while model-free algorithms only maintain a group of value functions and take the induced optimal actions. Due to these differences, model-free algorithms are usually more space-efficient and time-efficient compared to model- based algorithms. However, model- based algorithms may achieve better learning performance by leveraging the learned model.
Next, we discuss the literature on model-based and model-free algorithms for finite-horizon tabular MDPs with worst-case regret. Auer et al. (2008), Agrawal & Jia (2017), Azar al. (2017), Kakade al. (2018), Agarwal et al. (2020), Dann et al. (2019), Zanette& & Brunskill (2019). Zhang et al. (2021), Zhou et al. (2023) and Zhang et al. (2024b) worked on model-based algorithms. Notably, Zhang et al. (2024b) provided an algorithm that achieves a regret of (min V S/SAA AAH2T, T)), which matches the information lower bound. Jin et al. (2018), Yang et al. (2021), Zhang et al. (2020), Li et al. (2021) and Ménard et al. (2021) work on model-free algorithms. The latter three works achieved the minimax regret of O(VSAH?T)
Suboptimality Gap. When there is strictly positive suboptimality gap, it possible to achieve logarithmic regret bounds. In RL, earlier work obtained asymptotic logarithmic regret bounds (Auer & Ortner, 2007; Tewari & Bartlett, 2008). Recently, non-asymptotic logarithmic regret bounds were obtained (Jaksch et al., 2010; Ok et al., 2018; 8; Simchowitz & Jamieson, 2019; He et al., 2021). Specifically, Jaksch et al. (2010) developed model-based algorithm, and their bound depends on the policy gap instead of the action gap studied in this paper. Ok et al. (2018) derived problem-specific logarithmic type lower bounds for both structured and unstructured MDPs. Simchowitz & Jamieson (2019) extended the model-based algorithm in Zanette& & Brunskill (2019) and obtained logarithmic regret bounds. Logarithmic regret bounds are also derived in linear function approximation settings He et al. (2021). Additionally, Nguyen-Tang et al. (2023) provides a gap-dependent regret bounds for offline RL with linear funciton upproximation.
Specifically, for model free algorithm, Yang et al. (2021) showed that the optimistic Q-learning algorithm by Jin al. (2018) enjoyed a logarithmic regret O " which was subsequently refined by Xu et al. (2021). In their work, Xu et al. (2021) introduced the Adaptive Multi-step Bootstrap (AMB) algorithm. Zheng et al. (2025b) further improved the logarithmic regret bound by leveraging the analysis of the UCB-Advantage algorithm (Zhang et al., 2020) and SaarlySetteed-Advaaeee
algorithm (Li et al., 2021).
There are also some other works focusing on gap-dependent sample complexity bounds (Jonsson et al., 2020; Marjani & Proutiere, 2020; Al Marjani et al., 2021; Tirinzoni et al., 2022; Wagenmaker et al., 2022b; Wagenmaker & Jamieson, 2022; Wang et al., 2022; Tirinzoni et al., 2023).
RL with Low Switching Cost and Batched RL. Research in RL with low-switching cost aims minimize the number of policy switches while maintaining comparable regret bounds to fully adaptive counterparts, and it can be applied to federated RL. In batched RL (Perchet et al., 2016; Gao et al., 2019), the agent sets the number of batches and the length of each batch upfront, implementing an unchanged policy in a batch and aiming for fewer batches and lower regret. Bai et al. (2019) first introduced the problem of RL with low-switching cost and proposed a Q-learning algorithm with lazy updates, achieving O TT) switching cost. This work was advanced by Zhang et al. (2020), which improved the regret upper bound and the switching cost. Additionally, Wang et al. (2021) studied RL under the adaptivity constraint. Recently, Qiao et al. (2022) proposed a model- based algorithm with Ólog log T) switching cost. Zhang et al. (2022b) proposed a batched RL algorithm that is well-suited for the federated setting.
Multi-Agent RL (MARL) with Event-Triggerrd Communications. We review a few recent works for online MARL with linear function approximations. Dubey& & Pentland (2021) introduced Coop-LSVI for cooperative MARL. Min et al. (2023) proposed an asynchronous version of L.SV--UB that originates from Jin et al. (2020), matching the same regret bound with improved communication complexity compared to Dubey & Pentland (2021). Hsu et al. (2024) developed two algorithms that incorporate randomized exploration, achieving the same regret and communication complexity as Min et al. (2023).
15

---

Gap-Dependent Bounds for Federated Q-Learning
Dubey & Pentland (2021), Min et al. (2023) and Hsu al. (2024) employed event-triggered communication conditions based on determinants of certain quantities. Different from our federated algorithm, during the synchronization in Dubey & Pentland (2021) and Min et al. (2023), local agents share original rewards or trajectories with the server. On the other hand, Hsu et al. (2024) reduces communication cost by sharing compressed statistics in the non-tabular setting with linear function approximation.
Federated and Distributed RL. Existing literature on federated and distributed RL algorithms highlights various aspects, For value-based algorithms, Guo & Brunskill (2015), Zheng et al. (2024). and Woo et al. (2023) focused on linear speed up. Agarwal al. (2021) proposed a parallel RL algorithm with low communication cost. Woo et al. (2023) and Woo et al. (2024) discussed the improved covering power of heterogeneity. Wu et al. (2021) and Chen et al. (2023) worked on robustness. Particularly, Chen et al. (2023) proposed algorithms in both offline and online settings, obtaining near-optimal sample complexities and achieving superior robustness guarantees. In addition, several works have investigated value-based algorithms such as Q-learning in different settings, including Beikmohammadi et al. (2024), Jin et al. (2022), Khodadadian et al. (2022), Fan et al. (2023), Woo et al. (2023), Woo et al. (2024); Anwar & Raychowdhury (2021) Zhao et al. (2023), He et al. (2022), Yang et al. (2024) and Zhang et al. (2024a). The convergence of decentralized temporal difference algorithms has been analyzed by Doan al. (2019), Doan al. (2021), Chen et al. (2021b), Sun al. (2020), Wai (2020), Wang et al. (2020). Zeng et al. (2021), and Liu & Olshevsky (2023).
Some other works focus on policy madieent-based algorithms. Communication-efiicii policy gradient algorithms have been studied by Chen et al. (2021a) and Fan et al. (2021). Lan et al. (2023) further reduces the communication complexity and also demonstrates a linear speedup in the synchronous setting. Optimal sample complexity for global convergence in federated RL, even in the presence of adversaries, is studied in Ganesh et al. (2024). Lan et al. (2024) proposes an algorithm to address the challenge of lagged policies in asynchronous settings.
The convergence of distributed actor-critic algorithms has been analyzed by Shen et al. (2023) and Chen et al. (2022). Federated actor-learner architectures have been explored by Assran et al. (2019), Espeholt et al. (2018) and Mnih et al. (2016). Distributed inverse reinforcement learning has been examined by Banerjee et al. (2021), Gong et al. (2023), and Liu & Zhu (2022; 2023; 2024; 2025). Personalized federated learning has been discussed in (Hanzely & Richtárik, 2020; Li ct al., 2020; Smith et al., 2017; Yu et al., 2024)
B. Numerical Experiments
In this section, we conduct experiments All the experiments are conducted in a synthetic environment to demonstrate the log T -tyype regret and reduced communication cost bound with the coefficient of the main term O(log 7') being independent of M, A in environment to evaluate the proposed algorithms on a tabular episodic MDP. After setting H, A, the reward (8, a) for each (s, a, h) is generated independently and uniformly at random from [o, 1]. (. | s, a) is generated on the S-dimensional simplex independently and uniformly at random for (s, a, h). We also set the constant in the bonus term by to be 2 and c == 1. We will first demonstrate the log T -typ regret of heQQ-Hoeffding algorithm.
algorithm (Zheng et al., 2024). We follow Zheng et al. (2024) and generate a synthetic
B. Logarithmic Regret and Speedup
In this section, we show that the regret for any given MDP follows a log T pattern. We consider two different values for the triple (H, A): 2, and (5,3, 3,,),, 2). For FedQ-Hoeffding algorithm, we set the agent number M 10 and generate T/H 10" episodes for each agent, resulting in a total of 10s episodes. Additionally, to show the linear speedup effect, we conduct experiments with its single-agent version, the UCB- JCB-Hoeffding algorithm (Jin et al., 2018), where all the conditions except M = remain the same. To show error bars, we also collect 10 sample paths for each algorithm under the same MDP environment.
The regret results are shown in Figure and Figure 2. Both figures display performance metrics through two visualization panels: the left showing raw regret Regret(T) versus the normalized horizon T/H. and the right plotting adjusted regret (Tgr / (T/TH++1 versus THH. All solid lines represent median values across 10 trials, with shaded areas indicating the 10th-90th percentile ranges. Specifically: the yellow lines show the regret results of FedQ- Hoeffding, the red lines represent the regret results UCB- HoB--feef, and the blue line displays the FedQ-Hoeffding regret scaled by 1/v M to
AAll the experiments are run on server with Intel Xeon E5- 25-2650v4 (2.2GHz) and 100 cores. Each replication is limited to a single core and 50GB RAM. The code for the numerical experiments is included in the supplementary materials along with the submission.
16

---

Gap-Dependent Bounds for Federated Q-Learning
demonstrate its regret error reduction speedup pattern.
8
FeeQ-Hoeffding
UCB Hoeffding
7
TedQ--ooefdiing--ejjsteee
6-
Regret(
UCB- HoefHHofg Hedd-+ooefllinng-Adjusted
FedO-Hoeffiing
Regret(T)//og((/))
5-
4-
20
3
2:
10
1
0.4
1e7 0.0
0.2
0.4
0.6
0.8
1.0
Total number episodes TIH
Total number of episodes TIH
1e7
Figure Regret results for = 2, S 2, and = 2. The left panel directly shows the plot of Regret(T) versus T/H, while right Iog(T/H + 1) and T/H. In both plots, the yellow line represents the regret results FedQ-Hooefldng algorithm, while the red line represents results denotes the adjusted regret of the naQQ-Hocffding algorithm, which is obtained by dividing the regret results of the yellow line by v M..
panel illustrates the relationship between Regret(T)/ (TannTT/T/////L
UCB-Hoeflding algorithm. The blue line in each plot
14000
12000
800
10000
FedQ Hoefiding
nae--Hoefiding
UCB Hoeffding
Regret(7/leg(///t
UCB- UCe-Hoeffdling
Regret(T)
8000
FedQ Hoeffding Adjusted
Fed0-Hooeffiing-Ayyusteed
6000
400
200
2000
0.0
0.2
0.4
0.6
0.8
1.0
1.0
Total number episodes T/H
Total number of episodes TIH
1e7
Figure 2. Regret results for H = 5, S = 3, and A = 2. The left panel directly shows the plot of Regret(T') versus T/H, while the right panel illustrates the relationship between Regret(T)) log(T/H + 1) and T/H. In both plots, yellow represents the regret results of the FedQ-Ioeeffdig algorithm, while the red line represents the results of the UCB-Heeffding algorithm. The blue line in each plot denotes the adjusted regret of the BedQ-Hocffidhe algorithm, which is obtained by dividing the regret results of the yellow line by M.
From the two groups of plots, we observe that the two yellow lines in the plots on the right side of Figure and Figure 2 tend to approach horizontal lines as T/H becomes sufficiently large. Since the y-axis represents Regret(T)) log ( / + 1) these two plots, we can conclude that the regret of the FedQ- Hoeffdigg algorithm follows log -type pattern for any given MDP, rather than the /MT pattern shown in the Theorem 4.1 of Zheng et (2024). This consistent with the logarithmic regret result presented in Theorem 3.1. Furthermore, as T H1 becomes sufficiently large, we observe that the adjusted regret of RedQ-Hoeffding (represented by the blue lines) for both groups of (H, A) is significantly lower than the corresponding regret of the single-agent version, UCB-Hoeffding (represented by the red lines). This further supports the conclusion that the regret of FedQ-Hoeffddin does not follow a VMT pattern, or else the blue lines and the red lines would be close to each other. Finally, as T/H grows larger, we notice that the yellow lines and the red lines become close, confirming that the regret of FedQ- Hoeffding approaches that of UCB Hoeffding as T becomes sufficiently large. This also supports the error reduction rate (1/M) for the gap-dependent regret.
17

---

Gap-Dependent Bounds for Federated Q-Learning
B.2. Dependency of Communication Cost M, S, and A
In this section, we will demonstrate that the coefficient of the log I' term in the communication cost independent of M, and A. To eliminate the influence of terms with lower orders of log T, such log(log T) and vlog T in Theorem 3.3, will focus exclusively the communication cost for sufficiently large values of T'
B.2.1. DEPENDENCY ON M
To explore the dependency of communication cost on M, we set (H,S, A) = 22, and let take values in {2,4, 6, 8). We generate 10" episodes for each agent and only consider the communication cost after x 10 episodes. The Figure shows the communication cost results for each M after 5 x 10s episodes.
M-2
M-2 (slopa-6.52)
(slopa-6.50)
Me6
160
M-6 (slopa-6.51)
M-8 (slopa-6.40)
af communication
120
Log Log-numbar cpisodes log(71H)
Figure Number of communication rounds vs Log-number of Episodes for different Values with H 2, S = and Each solid line represents the number of communication rounds for each value of M (2,4, 4, 6) after 5 10 episodes, while the dashed line represents the fitted line for each M.
In Figure 3, each solid line represents the communication cost for each value M E (2, 2,,4,6,5 6, 8} after x 10y episodes, while the dashed line represents the corresponding fitted line. Since the x-axis represents the log-number of episodes, l))(T/H), the slope of the fitted line very close to the coefficient of the log T'term in the communication cost when log T is sufficently large. We observe that the slopes of these fitted lines are very similar, which indicates that for any given MDP, the coefficient of the log -tterm in the communication cost is independent of M. If the coefficient were linearly dependent on M, as shown in Zheng et al. (2024), then for M = 8, the slope of the fitted line should be nearly four times the value of the slope of the fitted line for M = 2.
B.2.2. DEPENDENCY ON S
To explore the dependency of communication cost on S, we set (H, A, M) = 22, and S take values in (2, 4, 6, 8}. We generate 107 episodes for each agent and only consider the communication cost after 10a episodes. The Figure shows the communication
results for each S after 5 10 episodes.
In Figure 4, each solid line represents the communication cost for each value of S E (2, 4, 6, after 5 x 10a episodes, while the dashed line represents the corresponding fitted line. Since the x-axis represents the log-number of episodes, H))(T/H), the slope of the fitted line very close to the coefficient of the log T-term in the communication cost when log T sufficently large. We observe that the slopes of these fitted lines are very similar, which indicates that for any given MDP, the coefficient of the log T-term in the communication cost independent of S.
18

---

Gap-Dependent Bounds for Federated Q-Learning
000
5m2
5-2 [sinpem6.51)
5md
300
5-6
---
5-6 (slope-8.15 1.15)
Sm8
400
Sounds of communccaiion
200
100
13.0
13.5
14.0
14.5
15.0
15.5
16.0
of episodes logiTMM)
Figure 4. Number of communication rounds Log-number of Episodes for different S Values with H 2, A = and M Each solid line represents the number of communication rounds for each value of S E (2, 4, 6, 8) after 5 10 episodes, while the dashed line represents the fitted line for each S.
B.2.3. DEPENDENCY ON A
400
350
A-2
(slopemb.51)
Bourds of communication
Islope=6.000
A:6
300
A=6 (slope-7.37)
A=8 1slope=8.30)
250
200
150
13.0
135
24.0
14.5
15.0
15.5
16.0
Log number of spisodes lop(7W)
Figure 5. Number of communication rounds vs Log-number of Episodes for different Values with H = 2 M Each solid line represents the number of communication rounds for each value of A E {2, 4, 6, 8) after 5 10s episodes. while the dashed line represents the fitted line each
To explore the dependency of communication cost on A, we set (H, M) = (2,2,2) and let A take values in {2, 4, 6, 8). We generate 107 episodes for each agent and only consider the communication cost after x 10th episodes. The Figure shows the communication cost results for each after 5 10 episodes.
19

---

Cap-Dependent Bounds for Federated Q-Learning
In Figure S, each solid line represents the communication cost for each value of A E (2, 6,8) after 10 episodes, while the dashed line represents the corresponding fitted line. Since the x-axis represents the log-number of episodes, log(T/H), the slope of the fitted line is very close to the coefficient of the log T'termm in the communication cost when log I is sufficently large. We observe that the slopes of these fitted lines are very similar, which indicates that for any given MDP, the coefficient of the log T-term in the communication cost is independent of A.
C. Algorithm Review
C.1. FedO-Hooffding Algorithm
In this section, present more details for Section 3.1. Denote 1/:
H+1 o 1, nb 0 for / 2 1, and 1// H+1
Ti= (1 - V V < S I. We also denote (41,))) lit , mh) for any positive integers i < 12. After receiving the information from each agent m, for each triple (s, a, h)) visited by the agents, the server sets ///.A.
1 1 1f (N + 1, N (x, a)) and B $s.a. = -i vf b. where the confidence bound is given by b, cv 11% for some sufficiently large constant > Then the server updates the Qeestimate according the following two cases.
Case 1: (s) < (M + + =: ig. This case implies that each client can visit each (s, a) pair at step h at most once. Then, we denote S m < + +1... < <,x S M as the agent indices with ni updates the global estimate of action values sequentially as follows:
"m. (s. > The server then
(s, a) + bo).t= ( +1, +,,...,, 2 + (s.a) (1-m))h(sso) + ne (rx(2,)) (s.
(11)
Case 2: No (s, a) 2 in. In this case, the central server calculates ( = -Em u (s) a) and updates
mak
(s. (1 1/ ) (%,, a) + v/,a (1)(8, + k (s, + 3
A.
(12)
After finishing updating the estimated Q function, the server updates the estimated value function and the policy as follows:
(*)+ min H, max Qh ( }. Th (s) arg max Qi+t1 (s,d.) V(s,h) ESX [H] a'EA
(13)
d'EA
The details of the FedQ- algorithm are presented below.
Algorithm FedQ-Hoofiiing (Central Server)
1: Input: To E N
2: Initialization: i = 1, (x, a) = o,
= H, as) e SxAAx and n : :S + A)ne(m)
is arbitrary deterministic policy.
3: while E E.e N < To do
4: Broadcast -² [N, ( (s))) and (s)) k.h to all clients.
5: Wait until receiving an abortion signal and send the signal to all agents.
6: Receive (ra(s, (s)) ba,b, {n Inm (s)) and {o/+1 (s, . (s))) from clients.
7: Calculate Aok+1 (s, a), (s a), oh (s, v(s, h) E x [ with a = (s).
8: for (8, a, h) E Ax do
then 9: if # (s) or n (s)
10:
Out (s.
11:
else if (/, a) < io then
Update Q k++1 1 (8.a) according to Equation (11).
12:
13:
else
14:
Update Q (s, a) according to Equation (12).
end if
end for
Update V and n k+1 by Equation (13).
18:
k+ le +1
19: end while
20

---

Gap-Dependent Bounds for Federated Q-Learning
Algorithm 2 FedQ--ooffdding (Agent m in round k)
1: Initialize ( (8, a) = Wh+ (s, = TA (s, , a) O, 0,V E E A [H].
2: Receive n², (NN (s, " (s)) sn, and (x)) from the central server.
3: while no abortion signal from the central server do
n 4: while nh ($h, an) < max {I, LM (sk, ] v(s,a,
A [M] do
5: Collect a new trajectory ((sh, On, ra) with an = (sn).
6: Th
" (5n, an) f nh (sh, an) + 1, 1/4 (8h, an) f uht (oh, an) + Vi+ (8h+1), and rn (sh, an) + The Vh E [H].
7: end while
8: Send an abortion signal the central server.
9: end while
10: "h m.. (s, a) + nx (8, a), o (8,a) a) < uhtt (8, Vss E ES [H] with (6))
11: Send (ri(s, (s)), mi (s, (s)))a and fulth mikk
(s, (+))) a, to the central server.
C.2. FedQ-Bernstein Algorithm
The Bernstein-type algorithm differs from the Hoeffding-tyre algorithm Algorithms 1 and 2, in that it selects the upper confidence bound based on a variance estimator, akin the approach used in the Bernstein-type algorithm in Jin al. (2018). In this subsection, we first review the algorithm design in Zheng al. (2024).
To facilitate understanding, introduce additional notations exclusive to Bernstei-ttype algorithms, supplementing the already provided notations for the Hoeffding-type algorithm.
pp k (s, a)
Vi+z
k.d. 8/41
]]
[1(())
k.im
an R.J.m = (s, (s)a)].
(s,
1=1
M
(s, a)
Σ
m.kk 1h
(s, am a).
N (8, No. (s,a)
mi Here, Pı (s, a) the sample mean of [V/++ (5 (#
k. ) for all the visits of (s, a, h)) for the m-th agent during the k-th round and 1 (s, a) corresponds to the mean for all the visits during the k-th round. We define (s a, h) to denote the sample
variance all the visits before the k-th round, i.e.
2
N (s,a) Σ
Vis Vitalss
Vall sfmm V h41
Wa(s,a, as)
Σ
(s,
Here, (K',j", m²) ) is the (round, episode, agent) index for the i-th visit to (s, as,a,h) defined in Appendix E. Using the expressions of uh and uht1, further find that
a (s) a)
Σ w as (s,
Σ o (s, (s, (s,a)
(
Therefore, the quantity Wa(s, a h) can be calculated efficiently the following way. Define
k-1
k-1
Wi,(s,a,h) = Σ
u (s. a)nk (s, W2) = a)n
(14)
then we have
W W Wi,e(s, (s (s) (a.t((s, W2n(8, a, + (8,
(15)
and
W (1,
W2.4 h))
W (s, a,
(16)
N
(s,a)
N (s,
21

---

Gap-Dependent Bounds for Federated Q-Learning
This indicates that the central server, by actively maintaining and updating the quantities Wi. and W2.4. and systematically m. m.kks 's and ya.k S, is able to compute WK+1-
collecting / S. Ph
Next, we define
8 (8, =d (min) min {V Hi
H) VHTSA+ MSAH
H
(17)
in which > positive constant. With this, the upper confidence bound be(s, a, h) for single visit is determined by (s, a, h) -i be a, h), which can be calculated as follows:
(1. a, h) = (s,,a, as, (s, a, h) - ne) (8.,,,))
2
2Tp
When there no ambiguity, we use the simplified notation b, (1 a, ht. In the FedQ-Bernstein algorithm, let Pt (s, a, h) - (t 1- ) (s, a, h). Then similar the FedQ- RedQ--oofffdin, we can updates the global estimate of the value functions according to the following
cases.
Case 1: (s, a) < io. This case implies that each client can visit each (s, a) pair at step ht at most once. Then, we denote S mi < mg.... ma+-et
M as the agent indices with n (s, a) O. The server then updates the global
estimate of action values as follows:
(
= (1-mm)0h(ss mh (ra(1,,)) a) + min ( + by) : : 1k-1 1....
(18)
Case 2: N a) 2 io. In this case, the central server calculates u (s, = =Em= l (s, a) / a) and updates
mikk
the Q-estimate as
t (s, = (1 - n/ 1 a) 1 m.k (ra(s, a) + (s, + B/2.
(19)
Then we can present the FedQ-Bernstein Algorithm in Zheng al. (2024).
Algorithm 3 RedQ-Bernstein (Central Server)
1: Input: To E N4.
2: Initialization: & = 1, (s a) = (s,, = (2, a) = o, (s.,a) = Vy((s) = H,Y(s, e
S x Ax [H]] and x² = [m] S A} he(H] is an arbitrary deterministic policy.
3: while EHL E. N (s. < To do
4: Broadcast A (s, (()))s)))))))))))))))))))))))) (s))) and (s) A all clients.
5: Wait until receiving an abortion signal and send the signal to all agents.
6: Receive (rx (s, (*)))) (nh m.kk (s, mx)))) a. (" (s, (*))) and m. (1m1""s, (s, (+)))) k,hmm from clients.
7: Calculate N*++1 (s,a), a), (8 a), i (8, (),u (s, V(s, h) E x [H] with a = (s).
8: Calculate (s(s, a, h), (s+ a, h), WI.++(Ss is, a, h), (s, (s),,))) V(s,h) E x [H] with a = *)(s)) based
on Equation (14), Equation (15) and Equation (16).
9: for (8, a, h) E A x [H] do
if # (s) or n (s, a) then as)
11:
1 (s.
12:
else if (s, a) < in then
13:
Update Q
k++1 (8.a) according to Equation (18).
14:
else
15:
Update Q (s, a) according to Equation (19).
end if
end for
Update V and n k+1 by Equation (13).
19:
+- 1: +
20: end while
22

---

Gap-Dependent Bounds for Federated Q-Learning
Algorithm 4 FedQ-Bernstein (Agent in round k)
1: (s, a) Uh++1 (s, a) (5, a) 14 (s, a) - O, V(s, a, E x [H].
2: Receive n², (NN (s, "x (8)) and (Vi from the central server.
3: while no abortion signal from the central server do
n 4: while nh (sh, an) < max {I, [1,LMH( LI N [nd a(s,,, E x X [H] do
5: Collect a new trajectory ((sh, On, rh)] with au = TH(())
6: nh (5p, an) + n/ (#h, an) + 1, 1h4 (8h, an) + uht (8h, an) + Vhtt (3p+1), uh (8h, an) + 16 (sh, an) +
[V h+1 (s)+1)) and rn (sp: ap)) + rhy vh E [H].
7: end while
8:
Send an abortion signal the central server.
9: end while
10: h m.k
V(s.)) e S x [H] with m..k(sss (s, t (s, a), mikk (s, a) + (8, a) and ph mik (s, a) + 1% (s.aa)/n a).a)// (s. (s.
(s).
11: Send (ri(s, (s)),,,, mikk (s, (s)))a tur mn (s, (s))) and (u)41(s, (s, ( e. to the central server.
D. Technical Lemmas
Lemma D.1. (Freedman's inequality, Theorem EC.1 of al. (2024)) Consider a filtration Fo C. Fi C F2 C .., and let Eg stand for the expectation conditioned on Fk. Suppose that
Y
X ER,
k=1
where {X&} is a real-valued scalar sequence obeying
1xxl S R and
Ex- [Kk] = 0 for all k: 2
for some quantity R We also define
n
W
Σ R3 [x].
In addition, suppose that W,, o² holds deterministically for some given quantity 0² < cc. Then for any positive integer m 2 1, with probability at least 1 - 8, one has
0² 2m
2m 5
4
2m 8
Yal s 8 max
W
log + R Rlog
Lemma D.2. (Lemma 10 Zhang et al. (2022a)) Let X1, X2.... be a sequence of random variables taking value in [0, 1].
Define F& = o (X2, Xe...., X3-1) and Y₁ 1 Fx) for k 2 1. For any d >> O, we have that
3n,
Yv + log(110) Xx 2
<d
k=1
1=1
and
n
P
3n,
V2 2
Σ
Xx + 1og(11))
58.
1=1
1=1
E. Key Lemmas
In this section, we introduce some useful lemmas which will be used in the proofs. Before starting, we define (' a, h). j (s, a, h), and ms a, h) as the round, episode, and agent indices, respectively, for the i-th visit the state-action-step triple (s, a, h) in chronological order. Under the full synchronization assumption, these indices can be constructed as:
ke (8, a, ht) sup N4 NY a) < <i}.
23

---

(f) & T H Gap-Dependent Bounds for Federated Q-Learning
J-1 M
(l) - sup JEN, Σ>>>>>>
Σ
T
(v,00= = (8% h
5'm K'S m)) < i - -N N2 (3,
3'=1m=1
m-
a) sup m E
Σ
I (s, (5t
s'mm
Oh
K
7-1 E (s,a) (8% m==1==1
<i- (s,
J'm oh
m.dt of m
When there is no ambiguity, we use k", m' and j' for short. Next, we begin to introduce the lemmas. First, Lemma E. establishes some relationships between some quantities used Algorithm and Algorithm 2.
Lemma E.1. (Paraphrased from Lemma B.1 in Zheng et al. (2024)). The following relationships hold for both algorithms.
(a) To T.
(b) (x, S En, (s, S To/H.
(c) For any (s,a, E xx [I] [K], we have
a) max (1, (s, M +1] | vm E [M],
n (s, *
(s. a) < io
m.k (s, S 1, (s a) s M.
n
(s, a) 2 in.
MH[H +1) n (s, < (s,a)) HIII +1)
(s,
T (s.a)
m.k
(d) For any (s,u, h) ES A [H].
To
No kK (8, (s, a) S Σ Nk+ (s,
a) S 1
+ MSA.
H(H +1)
H
5,a
(e) Let
1
1+
To MHSA
H(H + 1)
then we have f ST < 2T + MHSA
Proof of Lemma I. (a), (b), (c) can be directly proved given and Algorithm and Algorithm 2.
(d) By property (b) and (c), it holds that
Σ No -s, < Σ NK (s, + Σ n (s. <
Σ 3.a
M +
N (s.a) H(H
1 < (1+ H(H + 1)
To
MSA.
H
H
3.6
5;a
3.6
(e) With conclusion (d), we have T= =Esaa N $ Ti. The second inequality is because of (a).
is because K TH/H < T./H.
24

---

Cap-Dependent Bounds for Federated Q-Learning
Next, define new weights T/. For any (s, a,,a,,,h k) E Ax [M] [K], we let = (1, a) and i E U(0). Let t' = Nht (s. a) and t" = - (s, a), we denote
(f + +1,1) a) - =f < inl + 1" - 1'
a,
of (t + 1, 2 io}.
and we will use the simplified notation jj when there is no ambiguity. In Lemma E.2, we will present some properties of the new weights and their relationship with the original weights r/f.
Lemma E.2. The following properties holds:
(a) For all t E N+. Ei= Tíe = 11H
(b) For any k, k, E N4 such that t = NK (s, a) and k < K, we have
N
No
(s,a,)) h) =
Σ
T
N
NA
which further indicates that
17 = Ilt > 0j.
(c) For any 1 4 and any E [1] we have that
h/ S cxp(1/H).
(d) For any t E N+ and any (s,a, E Ax [I. ift < as, and (5, a) 2 io. we have that
Ti No m S ex)(L/H).
(e) 1/t < Ei th /// 2/t
Proof. Here (a), (b) and (c) are from Lemma B.2 and B.3 in Zheng et al. (2024) and (e) is from Lemma 1 of Li et al. (2021), so here we only prove the property (d). Note that
N M
i II (1-mg)) (1-m))= N=1
(1) -1 _ (1-7Nx 117
-(6-NAI NAI (IT)
(1 +1
wi I.
(1 1
H 1
xx H.
S exp(1/H).
N
Here (I) is because my is monotonically decreasing. (II) is because i - S n by (c) of Lemma E.
S
(..)
for N
(8, a) 2 in
H(H+1
Lemma E.3. For any non-negative weight sequence {wh Jmm and a E (0, 1), it holds for any h (H) that:
R.j.m
Σ
k.j.m Wh (t.ii
Σ w/ k.j.m
T T
( Kis. a
R.S. M
2
(SAllWlloo.h ) 1WWl
ah
(1 k.j.m. aa J.yaa
1-a a
k.j.m
2
< 22MS @2MS/|W[loo,t
+
(SA (wllwoloo,))) || 1-a
Here, ||o]oo,k max max(w (.i.imm and ||wl En.gm k.j.m
w/ k....
25

---

Cap-Dependent Bounds for Federated Q-Learning
Proof. We can decompose the summation into two terms
J.J.m
Σ
N E.J.
0
wh
(I[0< No (5) jm a b. < M) +I ( k. .0 : .). 2 21)
No. (5
kJ.m
wh p-
= EE
(s) [[(s
, on ) = (s, (T < (s, < M] (() 2 21)).
8,0 k.
Let ())s,a) = maxfk k 11 K. N (s) < M). Then for the first term, it holds that
1/0- < (7 k.m an - < <M
k.jm
Wh
(5 km L.
k.j.m
k.j.
ΣΣ (N)
Wh
I[(5 ,0 (lbimm) (s. a) < (s) < <]]
k.j.m
$ || loch Σ
Σ
16s o b... = (8, [0 < ax) < M]
,
s.0 k.j.
ka
||
Σ
I1 (s, < M]
6,0 k=1 j.m
1oolloo
No.
Noot+ (s) < 2M5A||
(20)
8,0
The last inequality is because No 1 =N (s, a) + n (s, S 2M by (s, a) < M. For the second term, let
(
K
c)) = Σ
wh A.
k.s.m on k. = a)] (s) a) 2 M] = Σ
Σ W
,0 _ k. = (s, a)l.
ked.m
A= A= +1 J,
Then we have
En,a (3, a) S Enii w/ h.s. = ||w.11. Given the term
w..diim I[(s
R.i. ,hh k.d.m = (s, ()) (M M)
(N)(s
k.j.
k.j. concentrates on smallest round indices with largest values of (N)(a.) we can obtain the largest when the weights wh
value. Let ku(s, a) k1 < k22 ... k4 S K be all round indices that satisfy n (s, a) > 0 and let k441 K 1. Then we have:
K
cb (8) S 1oo
Σ
Σ
aa B.J.m)) = (s, = |wlloa Σ mh a).
k= 1 J.m
Let
Σ t=1
n (s, a) S sca(s.a))
q == max
q
and
9
d= c=, a) |wlloo
Σ
n (s,
Then for g S t, we have the following inequality:
ky (s. a) +
d
(N 11(s
[|(s
kij.m J. = (N -
o0,1
(N (s, a) (N (sx (21)
k.j.
26

---

Cap-Dependent Bounds for Federated Q-Learning
Note that for any 0 y < x and a E [0, 1), have:
y 1 (x1-a - -y²
S x
(22)
Then, for any i e [8], let (s, a) and y = Noh
(s, a), -
holds that:
n ()) (N (s,
(s,
(N h (s,
(5, a))
2 (Nr (s,u))a (s,
n
2a
(23)
1-a
Here the first inequality is because No (8, = N Equation (23) from I to g, we know
ki (8. S 2 (s, a) by (c) of Lemma E. Summing up a) + n
n (s
(N (8. a))
-a (N (s. a))
(N a))a
1-a a
1=1
(N (s, (8,8))==00 - (N (s, a))
S 2a
- a
(N hatt (8, a))a h
(N (s,a))==a
2a
1
Ki Ei=1
n (8,
1-a
S 2n
(24)
1-a
The second inequality is because k + 1 S k4+1 and thus >>> 1 and 0 S < 1, we have the following inequality
N (s, N (s) The last inequality is because for any
21-a < (z 1) + +1,
and we can let N (s, ()..)///((( a). Applying Equation (24) Equation (21), for q < t, we have
wh kjjm
Σ
Iis5 oh
k. = (s, a)) [N M]
(N% (s, aa)
k.J.m
1-a
ki (8, ES
mh
d
< <2"||W||bo..
1-a a
(N (s,a))a
1-0
Ei ki (s.
d
5 2a
|| ||iloo,
1-a
(N ())
(Iwlloo, Eie
ki ())
1-a
Th
d
= =22]Wlloo,
+ (N ( (s,a)]llloc,n)
1-a
(Iwlloonh Σí ki (0, (3,
1-a
d
< <21|
+
1-a a
(cn(s,
$ <21| (c)(s,a))=-a 1-a
(25)
Here the second inequality is because No. N (s, S (xf a) for g < L. the second last inequality is because (s,s, a) I No. N (s, a)lal)lllooo by the definition of g. The last inequality is by Equation (22) with cs a) and y = ||ا|| Σi= n (s.
27

---

Gap-Dependent Bounds for Federated Q-Learning
We also prove the Equation (25) for g with d 0. In this case, by applying Equation (24) to Equation (21), it holds that
1-a
J. Wh (s)
ks (5,a) Σ "
1 a -...) (.))))[((((s,))) 2 M] s 2d 1olloooc,
1-a a
(ch (3,
(2] )
1
Therefore, with Equation (25), conclude that
J.ja Wh
2a
|| [wllo
lo,
ΣE
k.jan k... (8,
()) [N) M] 5
((en(8,a))
(s)
8,0 k.j.m
8,8
2a
(SA)
(26)
The last inequality by Hölder's inequality, as Σr,o ca(s,))=-a S (SA))| and Equation (26), we prove the following conclusion:
1-0 Combining the results of Equation (20)
R.jm Wh
2"
Σ
S 2MMA||wWloo.t
1-a [[ ||,||,,,
(5 ,0
R.im J.ii
N
F. Proofs of Theorem 3.1
F1. Auxillary Lemmas
In this section, we provide the proof of the gap-dependent regret bound (Theorem 3.1) for both FedQ- Hoeffding and Fed-Bernstein algorithms together. We first provide several lemmas describing the key properties Q-estimates Q a).
Lemma F.I. (Lemma C.1 of Zheng et al. (2024)). Using V(s a, h, k) as the simplified notation for V(s, a, h k) S A x [M] [K]. Then given any 8 E (0, 1), with probability at least 8, for FedQ-Hoefffing algorithm (Algorithm I and Algorithm 2), the following event holds:
G G 6
0z (o) 12h (s)
(0)) < 1h
H
N 1/
(V k+1
(5 (N, a,),,,)), V(s,ah,,))
i=1
Here, for some sufficiently large constant c 0,
No
34
(s,a, = Σ No
No
H3,
Th
Lemma F2. (Lemma E. of Zheng et al. (2024)). Given any (0, 1), with probability at least 1 5. for TedQ-Bernstein algorithm (Algorithm 3 and Algorithm 4), the following event holds:
(s) G2 1 0 (2h (1)ss) < 1 4 H
Σ
NE (V
Vi (s smm > (s,,,,, V(s,ah,,k)
th
Here, 38 (s, a, It) is the cumulative bonus defined Equation (17).
Let X = H, K,T, The notation f(X) S g(x) means that there exists a universal constant C₁ > 0 such that
f(X) S (.) Then we have the following lemma.
28

---

Gap-Dependent Bounds for Federated Q-Learning
Lemma F.3. For FedQ-Hooe Hoooffding algorithm (Algorithm and Algorithm 2), under the event 91 in Lemma F.I, for any non-negative weight sequence (wh (. J. it holds for any h E [H] that:
R.J.m
Σ
k.j.m Wh
(2hh Q%) (sh .0
b.j. S A/lllbL +
Σ
Wh J.jan (h)
Rig.
Winh R.J.m
where for any h S S H 1
wh M. (h) = w/h k.j.m
N
(. wh't1
E
wh H' (h)I N (
(s m'
:0p'
2
1/
NWW
II (Ik",",,m) (k...m))
with
ykj. = -lo" NW. H + HT (0- (oW ==..m
demm R.j.m
< in
H N
,0 aag. < M
The same conclusion also holds for FedQ-Beree Bernstein (Algorithm and Algorithm 4) under the event G2 in Lemma F.2.
Proof. By Lemma F.I. under the event G1, we have the following relationship
k.j.
(oth - -Qh) (0%
Wh
an
k.j.m
No.
Wh
k.jm
7o
No
+
Wp
k.j.m
1/s
No
(v
Kfmt ) Σ
Wh
kim gll
NN.
(27)
A.jio
k.j.m
For the third term of Equation (27), by (e) of Lemma E.2, we have
No
S NNK
(s, a. ht)
7
No
C
H3,
i
S 201
H3,
N
1=1
Then by Lemma E.3, it holds that
Wh
Risi g
No
(s).
kddm k.mm h))
dg
k.j.m
HH,
Wh
k.j.
V
(1
kis.m ,ah
k.J.m)
k.j.m
H3 N
Wh
Ridim
1
[o
No < M] + / !! | ||,||
(28)
k.j.m
Next, we will bound the second term of Equation (27). We can decompose the term into two parts as
No
(V
(s im
Wh
k.j.m
No
Σ
J.m.
(V/41
mm) (I[0= N kum a A. < io] + (s kidi a (...m)))
2 i0l)
Wh
f7/
k.j.m
1=1
29

---

Cap-Dependent Bounds for Federated Q-Learning
For the first part of the second term in Equation (27), have
Σ
(v No T
- V/ m
m [1
(o
(s
-a c.l 60
N
H
wh
< No (6%
km k.d.
10
111
k.m
i=1
H
wh
0 < (5) j.
< i0
(29)
Here, the second inequality is because ΣE 7i S 1 by (b) of Lemma E.2.
For the second part of the second term Equation (27), we group the summations in a different way.
No
k.j.m Wh
No
(Vh+1
Vi ( "mm
mm y (o an m. 2 i0}
kid.
No
k.j.m
No (V/+ V kt 3f .nt y (s -ah -i
こ éo}
Σ W W'
[[Kt (K,5' [K),
Wh
1ml
k' J' Wh
(Vit Vieti) (5th-i" m'mdmmm)
(30)
k
where
Nº
W s'm mn
Σ
E1
[ .a A.J.m 2 in
w/t k.
No n
(("t,"',m)) = (K.j'm')
R.sio
Let ||0|, following property:
No max (1 Jim and | Saniimattiii Since R.J.
Di
T/e
No by (b) of Lemma E.2, have the
<
- = Σ
K's' m'
Riim -h . k.s.m 2 in
w/th k.s.
$ [Wll1
(31)
10 Womm '
R.j.o
If we have proved that:
| S
(32)
then combining the results of Equation (28), Equation (29) and Equation (30) together with Equation (27), we reach
Σ
J.s.
(Qh -hh) (5 k... Og k)).m
wh
k.j.m
Σ K'd' mm
H''m (V Vntt) (5
(5/+11 (m + H3S (
Σ k...m
wh n1
m No
H
Σ k.j.m
k.j. HT NN (ohi wh
< 80 +
Σ
kij.
H T
Io <
k.jm , (s
decii < M
wh
No
k.j.m
Σ mm mm
K. m' (Qh Qh+11) (
(5p-1
K'''m'' K'
H3S H3SAlllllso. /|wp:///loo/////lleece
+ knd.on
w/ A.d.myyh..so
(33)
with | < ||ll and looo S exp(3/H))lwlllo.// Here the last inequality is because
K f.mm S oh (5k ,441
m'm &. and ViL (8/ 2 2h (5
k J'm
V (5/ h+l
30

---

Cap-Dependent Bounds for Federated Q-Learning
With Equation (33), we develop a recursive relationship for the weighted sum of Q% - Q between step / and step / + 1. By recursions with regard to h, h + 1, ,....; H, we finish the proof for Algorithm 1 and Algorithm 2.
For Algorithm 3 and Algorithm 4, the only difference lies in the bonus term in Equation (27) and Equation (28). According to Lemma F.2, under the event G2, we have the same relationship for redQ-Bernstein algorithm as in Equation (27). Moreover, note that NN (5, a, hi) X H by Equation (17), it is easy to prove the same conclusion as Equation (28). Then the N
following part remains the same. Now we only need to prove Equation (32).
Proof of Equation (32): Now we have
N
J'm w
Σ k.J.m
k.j. , M. 2 i0
k.m
I [(kt , "" m²) (K','', m')]
wh
N
$ ololo R.J.
Σ I [
kaam k.j.m
2
10
f/1
No
11 [(kt m²') - (m))
1=1
We only need to prove for any triple (M,'' m') and any E (H).
N
Σ I [
k.)) 2 in
f I [(t', ,,,m') = (4'..''m')) s exp(3/H) H)
(34)
For i E 1, by definition of k',"" and m', for any given triple (K' m'm
I [(K' m'm = (K' J m²)] =
if and only if
(o 0 d.J.m) (5 ml o0h W &' 3'')), K' < k and i = i''(K' j', m').
where ('KK,, J', m²) is the global visiting number for (5% (5 mmmm # & mn at (K, (W''', j')). When there is no ambiguity, we will use i' for short. Therefore
No
Σ T [o k.J.m
oz k.
2 i0
Σ
1
Nh T [(, f',,m,,) = (44.H,m²)
1=1
Nh I
(o
K'
K K'
z io, (m .ap 1.sii (8) I' W
No a sl.mi))
Tie
(35)
k=k++1
j.m
he S K be all the round index such that ny By H m' 2 in for any a E [t] then we can simplify Equation (35):
k is' mm))
Let K' < kn
< k2
0 and
N
3/ 3 m²
5' mm'
(h
hhp
N
Σ 1
N km an
k.j.m
N i0
m/s 1 [(K' ,"" m²) (K W. j'mm
k.j.m
1=1
(0h .ah -a Mansimy = (s '' 'm'
Hariim
Ms I' mmm]]] , .u
N
9=1
3.m
V s' mm N mm
n
(sh
.bp
(36)
9=1
For any g [t] and
11 by (d) of Lemma E.2, the following relationship holds
n
S
exp(11HH)
(37)
No. +m
31

---

Gap-Dependent Bounds for Federated Q-Learning
Combining Equation (37) with the property (c) of Lemma E.2, for any p [n [ we have
& exp(2/ H H No" Sexp(1/H)pp
n2 S
and thus
Ki k I'm h (sp
o J'm'n
Mr
No
S cxp(2/H)
t. n
n/5
No
+n ( I exp(2/H)
Σ nhe S cxp(3/H).
20
1=1
g=
k S and N Applying this inequality Equation (36), we complete the proof of Equation (34), and consequently, Equation (32).
Here (T) because k' < ki < h2 <
>
No 2 1.. The last inequality by (a) of Lemma E.2.
F.2. Proof of Lemma 4.1
Proof. The following proof holds for both FedQ-Hoofi algorithm and FedQ- algorithm.
Let N [oog((H()] For any N, k [K] and given h [H]. let:
k.j. Wh,
= T (
k.j.m)) E 12 2¹)) k.j. kidm ,a (... Q7 (6 , ,
and
k.j.m K.N
I (2 [ (s ohh m) Q (s . J..m E 12N-1e, c, H
Then
|| Gwllse max wht
hng k.
S 1, ||
Σ
k.j.m
Whit
k.j.m
Now for any é E [N], we have the following relationship:
Whis
k.j.
(oh Q%) (mm ,an d. 2 te|le((Wll
(38)
Combining the results of Lemma E.3 and Equation (38), have:
2 3--e|lwllo 2 / Σ
Whit (1))
(39)
h'=h k.j.m
where
k.mm == Whi
R.j.m
Wha
N
k.j.a (h) wh'41,((h)
E
WHz
5'm.m' (b)I NWW (6
mm a
m²
M. mm
> 1o
f
NV
I
[(Kt
,4 ".,"","m)) = (k, , S S H 1,
iml
Therefore, for any triple (k, m) and h 5 S H- 1, we have
N k.j. (h) (h)
N K
Σ
mn (h)
N St an
K. mn
2 i0
No.
[(kt = (k, m)]
Wh'
Then by mathematical induction on h E [b, H), it is straightforward to prove that for any j E [K].
N
k.) < (exp(3/H)) -h -h < 27,
k.j.
(40)
given Equation (34) and the base case 5
k.j. A...
N
k.j.m < 1.
;=
h,i
whis
32

---

Cap-Dependent Bounds for Federated Q-Learning
Solving Equation (39), can derive the following relationship:
S 4'e2
En Ensm Whis (h)
J.j.
||
1.h
(1)
+
2¹
(41)
We claim that which will be proved later. Therefore, by
Σ
Ak 2 SMH MVHSSAVi,
(42)
M== Ag..m
N
I [[ -Q7) (s J. .0 b
2 E
= Σ
k.j.m h2
i=1
we have
H T
H
N
H
N
ΣΣ
2% (5) a...mmm
k.j. 0
S 2
2
k.j. h2
Σ
|
|
(43)
1= k.d.
h=1 lid.m 1=1
h=1
t=1
By Equation (41), it holds that
N
SA
J.m. (4))"()))).m Ei=hh Exs,m
H
Wh
4'62
2'c
1=1
1=1
SA
Σ
Ekjm
2'E
SAA MH*SA+ M MVHSAAL
(44)
Here, the second inequality is because 0 S WHis of Equation (42). Combing the results of Equation (43) and Equation (44), we reach
k.j. (M) < 27 by Equation (40) and Y 2 0. The last inequality is because
H
H.SAL 2
MH MUISSMM
Σ Σ
T
k.J.m k.m. ke.i. _a a...m - Q7 (8h , a
k.j.
2 2 S
1= R.s.i
Now we finish the proof of the first conclusion. Further, we can prove the second conclusion by noting that
Σ (oh
(m , 1. 1 [10h Q7)
(3t...mm j.j. k.j.m
A=1 k.j.m
H
N
[ellwll(1 111,1
h= 1=1
H
Σ
Σ
(.... Whic (h)
2'c
h=1 Mi kij.m
SA
H H
m hr
1=1 k'=h k.j.m
SAA + MH MVH.SAVL
Here, the second incquality is by Equation (41). The second last inequality is because ΣN and the last inequality is because of Equation (42). Next, we only need to prove Equation (42).
wh., A.i.'' (h) < 27 by Equation (40)
33

---

Cap-Dependent Bounds for Federated Q-Learning
Proof of Equation (42): By definition of h
Y. we have the following equation
Σ
%
NW H + H
Σ
T
[
(sh
.46 (... < i0
+
Σ
N
H
T [0= (sW ,a aagg.mm < M
R.m.J
k.j.m
k.m..
k.
(45)
For the first term of Equation (45), we have
Σ
N
IN (s,a) = 0, (sh
. oh a = (s, - MHSA
(46)
R.
6,0 R.g.m
The inequality here is because if we let ko a) be the round index such that N (s, a) = and N > 0, then ko , a = (s, a)] m (s, a) S.
Σ (s O, (s
4h m) = (s, a)] =
Σ
J.m.
j.m
Let (1) = max(k| 13 K, (s, < io) Then for the second term of Equation (45), it holds that
Σ HT N (s
k.j. k.j.m
< i0
= H Σ
Σ
To
< (s, a) < in, (s k.j.
,0 k.j.m)) = (8, a))
k.
8,0 J.j.m
h
Σ
1
(s
J.g.m au
" k.j. = (s,
8,0
m,m
H Σ Ns,+
8,0
H1
NW a) En
8,0
< HSA + MHSA S SA.
(47)
Here, the first inequality is because NoW (s, a) < in and then my k1 (s, a) & M by (c) of Lemma E. Finally, for the last term of Equation (45), by Equation (20) with 1/2 and wh
k.j. 1, we have
Σ
H&,
T
(aim "...") NO. (s
M] S2MVHSSAVT.
(48)
N
k.m.j
Applying Equation (46), Equation (47) and Equation (48) to Equation (45), we know
H
H
Σ
kkmm
= MH MVHSAM/.
M
J.m.
M
F.3. Proof of Lemma 4.2
Proof. The following proof holds for both FedQ-Hoeffding algorithm and FedQ-Bernstein algorithm. To begin, note that
Vi- VF") (8) = Vi* (5...))) - (s k.j.m ae.. + (Qi- -oT") (8f "a
As k.mm a M.s.imm +E [v5 - (V- -Vzrt) (sH..img s kuim ~ Pi I K.s.m alddmm))
= E A1(s) k.mm (.s.m + A2 k.j.
.2 k..i ) | 1 k.s. ~ Pi I sisii a cp.smm)))
B [Q0 QF (2 , a k.j.m
k.mm Pi(. 8 k.j. a (.s.mm))
82
=... E
Σ An (8h k.j...m k.s.
an
8ht1
kjmm
Pr sp.
kjj. a ). h E 11] - 1]
34

---

Gap-Dependent Bounds for Federated Q-Learning
Here the second equation is by Bellman equation and Bellman optimality equation Equation (3). Therefore, can get another expression of the regret
E (Regret(T)) E
Σ (vi V/(") (sfadm)
E
Σ Σ
kiam Redimn An
.4h
A..i.m Famm
By event 9j in Lemma F.1 (or 22 in Lemma F.2 for FedQ-Bernstein algorithm),
(shimm 2% knjan 0h (hs"")) = max(Qx (s "ah)", 2 max (s% ,a)} = Vi (s
Thus, for any episode-step pair (k. h)
R... R.j. k.).m) (s
clip Vi2 (sp (.3.
k.jm Q7 (5%
(s , a.. Amin] S clip [ Qh) (sh.d.m. an (. A Amin
0h
which further implies
E (Regret(T)) S E
Σ Σ
clip [ - Q%) (6h...m _0h a. Amin)
k.j.
1=1 k.j.a
F.4 Bounding the Gap-Dependent Regret
The following proof holds for both redQ-Hoeffding algorithm and FedQ-Bernstee algorithm (substituting G1 by G2).
Let 1/Ti, we have:
H
E (Regret(T))
$ E
Σ clip [ Qi) (sh...m aa
k.jm))
Amin
91 P(G))
H
+
Σ clip (0h - Qi) (s k.j.m an
k...m
Amin
9 P(G))
h=1 k.j.m
H SAc
0
MV MH SA
+ -/--- Ti
HT
A Amin
SA MV MI
=0
Amin
The last inequality is because under the event G1 we have
Σ Σ
H
clip [10x
Qi) (s k.d. R.j.m
A min 5
S
MH MVHTSAVI)
Amin
1=1 Am
by Lemma 4.1 with Amin and under the event gj,
Σ
clip (()) Qi) (s km.. a k.i.m
Amin
S HT,.
1= Rij.m
Since , = log( 25ART 1og(2SAHTT)) by (e) Lemma E. we have
5 2log(2SAHT)) < 2og ASSAH(2T+ 0o (180(SAAH))) log(MHHA)) = - (1B((AAT)) (49)
35

---

Gap-Dependent Bounds for Federated Q-Learning
The last inequality is because M, H < <T. Therefore, applying Equation (49), we have
H MVH MH
E (Regret(T))
0
min
H (MSAAT)
Mv MVH'TAA/lgMMMAAA MH
0
Amin
G. Proofs of Theorem 3.3
G.1. Probability Events
Lemma G.1. Let L' = log( (2MSAHT) with E (0, 1). Then we have the following conclusion:
(a) With probability at least - 6, the following event holds:
H & =
Σ
(s).s an k.m.s)
2 Amin
S Cmin
R.j.m
(b) For any given deterministic optimal policy n², with probability at least 6, the following event holds:
k'
&g
P
k.j.
+ f ())
mT))
33>>
a
k.j.n
# ( +2,, vh [H] W. [K]
j.m
R=
(c) For any k [K], let R2 Ik=1 E 1, which is the total number of episodes in the first k' rounds. Then with probability at least 1 8, the following event holds:
(5/ kmmm = -/77))
E3
8/
J.m
Σ
k.j.
s/(r) + 91, AA E S, E [H] E [K]
J.m
(d) With probability least 5, the following event holds:
Sh
k.j.m
8
P (8h
k.j.
= 1 }
Ju
kijaa = slat) 96' Vs E S, e [l] e [K]. e [M] 8h
<
24
j=1
Here, under the full synchronization assumption, we can assume in k-th round, each agent will generate Js episodes. Note that given the round ls and the policy x² the probability k.j.m. =s(7*) independent of the index m. j. Let k.j.m
Pko = (s = =) then Es can be written as s.h
Jk
E
k.j.m
- J.lpk s.h
22.Japh + + Vs E S,h e A [K], [M]
36

---

Cap-Dependent Bounds for Federated Q-Learning
Proof. (a) It is proved by Lemma 4.1.
(b) We order all the episodes in the sequence following the rule: first by round index, second by episode index, and third by agent index. Let n(k, J. m) denote the position of the j-th episode of the m-th agent in the k-th round of the sequence. The filtration F fm) is the o-ficed generated by all the random variables until the first n(k, j. m) - 1 episodes. When there is no ambiguity, we will abbreviate n(ki,, j. m) as n and Fn(t.s.m) as Fn. Then we have:
P ( bi # क. ( ())) m+/) ) = ( # the ( Fr).
According to Lemma D.2, with probability least 1 - 8/T2, the following inequality holds for any given h 1/ [H].
k' = k/g
# and Bxg""
k/ x m.m 1 E [Ti]:
P
k.j. an
k.j. s 31 (hh # Th. (s/..-m) m+t))
# the (sh.).m) + 21, Vk's [K].
Considering all the possible values of h = h1 E [H]. k' = kóg E 17 and REy = k/ j.m 1 1e [Ti), with probability at =kee
least 1 - 5, it holds simultancously for all h E [H], k E | and Rg = Ek=1 Ei. 1 E [Ti] that
K''
P ax k.jm
m
S 3
a kjim * mm(shh.mm) + 21. k= J.m
II
(c) According to Lemma D.1, with probability at least 1188/ -8/ST?, the following inequality holds for any given s' E S, h N'' [H, k' K/6 E [7]] and RE -
-==12 s.m 1 [Ti]
A/
= 50 s/|7Th) )
k.j.m = 80| - P 5/
-P.st.. s..... = s' s/|7*)
S
24
5/1"
k.j..
c + 9c.
1= j.
k= 1 J.m
Here, we let 0² = Ti, m 1ogg(Ti)) in Lemma D.1 and
A/ Wn
Ai
P
5/
k.j. = s(1 (1- P (5/ sam==s' =s((x)))
PP
(s s' 3/|xt)
k.j.m
1=
A= j.
Considering all the possible values of = E S, h = 1/' E [H]. /'' = Ky E 11, T E [Ti], with probability at least
1 1- 8, it holds simultancously for all s E S, e [H], ke e [7)] and Í e [Ti] that
M
W'
k.j.
-
k.j.a = s/att) S (P (5
24
Σ
8/
J.jaa = sla+) =slat)
+ 9c.
J.m
k=1 j.m
(d) The proof is similar (c) by considering all the combinations of (s, m, RR) E [1] x [M] H [Ti].
G.2. Proof of Lemma 5.1
Proof. The event G1 E n &2 holds with probability at least 1 - 35. Next will prove Lemma 5.1 under the event Gi &, n &2. (For FedQ-Berntein algorithm, we will prove Lemma 5.1 under the event G2 & n &2)) For any h E [H], let set Dr be all triples of (s, ft) such that & AAt that is:
Da ((s, a, la < & Ah (s))
37

---

Gap-Dependent Bounds for Federated Q-Learning
We also let the set D Uh=1 D and the set
Dopt = E (s))
Then we have [D] Dopul = SAH.
If for given (h, j, m), (skmm ah k.m.j. h)) Da. have An A Oh m. 2 A By event 91 in Lemma F.I (or G2 in Lemma F.2 for FedQ- -errssten algorithm),
R. a ). max ( (..... .a)3 2 (h k. Q
"a)) .a)) (5% (.
Therefore, holds that
Q (sh ,0 a k.m.s) - 1% (s) .
k.m.
k.m. k. 2 (s ,0
fo k.mm 2 Amin-
Then we have
a kimm
& (.h...m))))
(6) (ol)mad
k.m. h) Du an
(oh
Riim .a a.
k.m.
(5) a
( b.m.d) 2 A min
and thus by the event E in Lemma G.1, it holds that
H
H
Σ
a
k.jm
& A5
}
Σ
1hish
kmm. a a.h. b.m.))
R.m.j. k.m.) R. (3h
2 A Ain
S (50)
Cmin-
A=1 Reg.m
A=1 Aug.m
Next we prove the second conclusion. Let 5% = {s P = OJ. For any given deterministic optimal policy x², we have
k.im
* (5 (.
k.mm
+ TT](( (5)
h.im), sh
k.im $ sh + [ k.im
* (
s kam sh)
(51)
For 8h &.mm the only element in Aã (6
$ Sh have IPx k. and (% (.3im)) 1 by condition (b) of Definition 3.2. This means n (s).mm)) is kimm), Therefore, we have
I ah
kjm + t (s
& st] I k.s. & Aj, (7 (st.mmm))
(52)
For the second term in Equation (51), if because of the randomness of the selection of s k..m we have P(s1 81 k.jm| (x*) = [S( = si R.d.m)) > 0 and then
II aaat k.jmm * (s j.jm sq] = 0.
(53)
To bound the second term in Equation (51) for h > 1, we first prove lemma.
k.i. kijm k.."")) ) in j-th episode of agent m round if Lemma G.2. For any [H] and the trajectory {s .ah
Th
Ptt fim > 0 and dg k.jan is the unique optimal action for state 8h
J.jja at step h, then P. k.j. h+ > 0
Proof. For any given optimal policy n², it holds that
P
A++1
IP
Sh+1
k.j. 8h41
P
8h+1
8h+1
k.j.m
8h.
8/
k.j.m
(hh.
0n
k.j.m TT*
P
19h
J.j.
aa
ax
A.j.m
J.j.m $1+1
k.j.
jm
8h+1 =
8h
On
x 2.... n
>
The equation (1) is by Markov property and IP(sn = 88
j.j.m
Oh
On
k.j.m
TT* =
P((h
8/
k.j.m
|Tr) = P
A s.m
38

---

Gap-Dependent Bounds for Federated Q-Learning
For every initial state 81 R..m know P "1 " 0. Therefore, if for h > 1, Fr p. and 8% s E Sh. by
"
k.m.d at step I', otherwise Lemma G.2, we know there exists h < f such that at at is not optimal action for state 8/ have P k.a. $h
> O. Therefore, for the second term in Equation (51), we have
R. I k.d.m + n (1 8h
[
ss]
S
b.d.
Σ N==1
I
& (h
(54)
By combining the results of Equation (52), Equation (53) and Equation (54), we can bound the Equation (51) as follows:
H
* (5)
Σ h/=l
I
an &
k.
(sh.
I
$ Air (sh...mm)
h'=1
Therefore, using the first conclusion, Equation (50), we reach
H
Σ
T
k.j.
* (8 (.)im)))
<
I
On
R.jm
A
S Cmin
k.J.a
k.j.m 1/=1
By combining this inequality with the event &g in Lemma G.I, we can conclude that for any h [H] and k' E [K].
k.mm TP
(n + 16(6 (.)")) mh)) S 4Cmin.
1=
G.3. Proof of Lemma 5.2
Proof. The event G1 n (ni E, holds with probability at least 1 - 56. Next we will prove Lemma 5.1 under the event G1 n (n &.) (For FedQ-Bernstein algorithm, will prove Lemma 5.1 under the event G2 (n E.).)
Under the event 91 n (N f E.) (or G2 n (n &,),, we have already proved the Lemma 5.1 in Appendix G.2. Because V/ (5o, dn) i1 + i2 > Cmins by Lemma 5.1, we know ao AA Next we prove the second conelusion.
Using the law of total probability, for any 0 < h < H 1. E S and any given deterministic optimal policy n², we have the following relationship
k.j. F(
F(5
IP Σ
k.jm 8h41
/. 8', a,
J.j.m (T)(s)) sq. J.J. = s', a,
k.j.m (h('s) x*)
k.jam
k.j.m
+ (8 k.j., ,T4))
htl
8, 0h
pkj.m
IP sp.
k... 5 an k.j. = (h(ss) 174) + (P(ss
k.j. sh+1
= s, an
k.j.
# (o | mT/)
(55)
where
jpk..mm a = IP k.m. k.j.
s|s
s.aa k.j. Ti((s)) xt))
= =P(s
k.j. = s|s/
s a, k.j.m = T,. (s')
(st+1
The last equality is because of Markov property. We also have
IP
A.j. - = Σ 6h+l1
P
k.j. = 56, m²" IP
8/
k.j. s'(xx*)
Σ pplisii
P
8
k.j. = 5 =11x²) (56)
where the last equation is because
PP
k.j.m h+1
21 = =,,,"" n² =P
k.j.m
k.j.m
= 21
k.j. = 5 s',a
k.j.m
= 7h((s))
= s,s',h"
p.....m
39

---

Gap-Dependent Bounds for Federated Q-Learning
Combining the results of Equation (55) and Equation (56), then it holds
IP
k.j. h+l
s/(rh) IP
kmj. sh+11
s [T²))
Σ p.e.s.i
%/ IP
s ah J. a (5 P = (s/ + IP shtt1 8, Oh fi o u ( (1
&.j.m
Σ
p a,
IP
s...iim = ss ) - (s Shchim s' s((xT)
Σ
($$ P.aiii = s', an
+ (h's') x²))
R.j.n h+1
8, 0n
k.j. # (8h (m m
Therefore for any h H 1 and E S, by the triangle inequality, it holds that
PP
k.j.m sh+1
=s xt)
IP
k.j.m s/m² Σ p
P 5h
k.ji
= 1T/) IP (sh.d.m 5 (/(x))
Σ pp..iom
IP
5h A. 5', On
k.jm + (s)) Tt) + P
k.j.m
8, an
k.j.m
* m (s xt))
(57)
Summing Equation (57) for all S, since E, P. Ps 1, then we can derive the following recursive relationship:
Σ 1P
sh+1
k.m
=s ltt)
PP
(sht1
k.j.
=s|x²))
Σ
IP 5% Blsiim =s' x+))
P 8/
k.j.m kijm 5617T) + 2IP ahp
+ T (
(...imm m+t)
Since P(s = s ) - IP(s (. = =/
O. by recursion, for any h' E [H] we can get the following conclusion
Σ
P sh
Pp (s = 8/7x*
2 2
a
kjjm
* ( (.3.m))
| xxt)
h=1
H
< 2
P
Og
# * ( m. | mτt) j.j.m
(58)
h=1
Applying Equation (10) in Lemma 5.1 to Equation (58), then for any h E [H] and k' E [K], it holds that:
k'
ΣΣΣ
T
%/2
J.j.
TP
8/
k.j. = =s/TT)
P
ah
k.jm
+ (
| S 8HH
k= j.
h=1 k= j.m
Based on the property (b) of Definition 3.2, we have ki also have
π )}
F then for any E S, h e [M]] and k [K].
P
1/
k.j.m
RA-
S.A
PP
k.j. 8/
s mx IP (P(st...m 8/7²* < 8HH
(59)
k=1 J.m
k=1
and thus by the triangle inequality
W p
ΣΣ
= m+)) < R + SH
(60)
1=
Applying Equation (60) to &g Lemma G.I, for any & E S, [H] and k' E [K], we have
K
Σ
kjjm
s)
kkjm 8k P
= s| =slat) < 21 (RwIPI,, 8HH 1 9t
5 RR.PP s 23H
(61)
40

---

Gap-Dependent Bounds for Federated Q-Learning
Combining the results of Equation (59) and Equation (61), by triangle inequality, derive the following relationship for any E E. [H] and k' E [K]
ΣΣ
A/
k.j.m
Ry P. S Re.Pa.n a,n 31HC
(62)
A== J.m
Then by triangle inequality, it holds for any 8 E S, h E [H] and k' E [K] that
hb
R.j.
8,
E An(o) - Ry Pz.n
J.m
II
k.jm
RR.
%/
k.jm
8, 8,a,
k.j.
Ai(s))
N=
J.m
Rm J.m
/
Pa x,
+ 32HCmin
Here, the last inequality is by Equation (62) and also the fact that
K
K
8, $ An(0)
kJ.
Σ
k.jm
& (b((she)im)) < Cmin
1cm J.m
1oml
j.
due to Equation (9) Lemma 5.1.
G.4. Proof of Lemma 5.3
Proof. The event & holds with probability at least 1 - 8. Next we will prove Lemma 5.3 under the event Eg.
the trigger condition is met by the triple (s, a, h) in round k then we have a = (s). For such (s, a, h), by Es in Lemma G.I, holds for any E,S, h E [H]. At E [K] and m E [M] that
kjm h
s, an
k.j.m
I
k.j. $ E JJPPt / /2J S, 9d' JaPk 24J.Pk S, + 96 sh
(63)
Since (s, a, h) satisfies the trigger condition in round k, there exists an agent mo such that ni k.mo (s (s, a). Then we reach
J&P + //4./. s.A + 9r' ! (s 1 é CN 199.'.
MH(H 11)
The last inequality is because / (s, > is. Solving the inequality (I), we can get the following relationship
V J.P s.h 2 VCN -3'" Vol.
Then by Equation (63), for any other agent m,
k.j. 8
8, s,a,
k.j.
2 J& " - 24 Pht s. - -9'' -t'== -(V Jr Pb
Vb(l
15v
2 15v
Cn +1
ON 33
3r' 2v66)
3
The last inequality is because CN > 199('. Therefore, we have
M (s,))) a) Σ
Jz Σ
M(CN + 1)
M
n (8,a)
k.j.m h
8, a
k.j.m
>
3H + +1)
m=1
1=1

---

Gap-Dependent Bounds for Federated Q-Learning
and thus
1 No (s, = (s) + +n)(s,)) (1+ 31 + +1) ())
G.5. Proof of Lemma 5.4
Proof. The event 91 n (N E,) holds with probability least 56. Next will prove Lemma 5.4 under the event Gi n (N= E.). (For FedQ-Bernstein algorithm, we will prove Lemma 5.4 under the event G2 n (Ni= Ei).)
Under the event 91 n (N-= E.) (or G2 n (N E,), we have already proved the Lemma 5.1, Lemma 5.2 and Lemma 5.3.
For PA,. > O, the optimal action is unique. Then for any (s, a, h) such that =-t (s)(s) and P >> 0, we can simplify the results of Lemma 5.2 to the following equation
Rx h /v Rx
R a, 32HCOin S No Myk+1(6 (s,a) S Re + 5 Ru 32HC
(64)
By Equation (64), for any sf S and h' e [H] such that P O, have
RRP s/ -5, // R& Pr s 32HCmin
No (s', (s)( (s' T (s'))
R P + / / + 32HCmin
To prove the second conclusion, we only need to prove that, for any s' E S and h E [H] such that P > 0.
RAP W 5 R Ad 32HC
(65)
Rk PP P / Rk-IPP; ne + 32HCmin
GH(H+1)
Next, we will prove the Equation (65). For the triple (su, ao ho), by Equation (64), we know that
6500HHCmmn
N (So, ao) I Rk- P+ so 5 RK- T so 323H2
Cst
Solving the inequality, we have
6500H3 Cmnn
25t 5v
Rs
I+ h0
32HHCmin +
Cst
6468H3CCm..
H3Cmin
Cat
V
C.t
H3Cmin
V
79, H/33mmn
(66)
Cst
and then
R so
RR--1P
IF su. 79 H3C min.
(67)
Here, the inequality (T) is because such that P we have
25c < H3Cmi for H2 2 and < Cst S 1. Therefore, for any & E S and N/ E [H]
Pr Po
RE- IIPs IP oN / RR- Bo
PE- 80.10 V 79 H3Cming
(68)
ho
V
Pa $s
42

---

Gap-Dependent Bounds for Federated Q-Learning
and thus
v Balp's >
V Rx RK- P3 RR- S > H9VH3Cmin
(69)
For X 6241///Cmmn 792 H min- note that
[Cinn X H + 32HCmin min 56H²
X
5vX++ 32HC $ V
(70)
Here, the first inequality is because 5/i < /gr for H 2 2. Therefore, based on Equation (66), Equation (67),
Equation (68) and Equation (69), we can apply Equation (70) for RB-14% So and R P sot R&-1 respectively:
1 H and RgP
Rk-1 No.ho 5 56H²
RglP so.
// Rx-1 Pp s0 + 32HC
RePP so. 32HC
(71)
56H²
and
Rk-1Paa 56H²
RgP
5y R p 32HCmin
5 R y 32HC S
(72)
56H²
Since No. (80: 0o) > in and the trigger condition is satisfied by (s, a, h) in round k. by Lemma 5.3, we have:
N (8o, ao) No
1+ 3H( +1)
N Ag (50: a0)
Together with Equation (64), it holds that
RgP so + + RgIP= so. + 32HH
No+1 (so. au)
2 +
(73)
R P ho -5 R 1P 80.000 32HCmin
N (so, ao)
3H(H +
Applying Equation (71) to Equation (73), have
ho +
Ra so, + +23HHmm min
(1+ + 56H2 RRs
1 3H +1)
I
RE- IP so
5, Rse Tpo so,no' 32HCmiin
56/12 RR
Therefore, we know
Rs
1 56
1 3H(H +1)
(74)
RE-1
1 56H
Using Equation (72), we have
R&P W ///RAPR P Ael 32HCmin
(1 56/7" Rc
3H1(H +1) )
(1-
1+
56/2
(75)
Rk-1P% P. + 5, 1P- PP M + 32HCmin
56H
R
56H7
The last inequality is by Equation (74). Let
6H2-6H+1
6H7-6H+2
+
6H2-6H+1
6112-
6ff
Then we have
2
6H2 + 6H +2
11
6H"46H+1 462
4 - 6H + 2)
56H²
43

---

Gap-Dependent Bounds for Federated Q-Learning
and thus
6H(H+1)
6H 6H +1 6H + 6H +2
2 -1+c)
S
56
1
3H(H+1)
56
Applying this inequality to Equation (75) completes the proof of Equation (65), thereby proving the second conclusion.
G.6. Details of Final Discussion
The event 91 n (N & (or 92 n (N= &,) holds with probability at least 1 - 56. Under the event & n (n & (or S2 (N E.), we have proved Lemma 5.3 and Lemma 5.4. Next, we will discuss the number of communication rounds and consider four different situations:
1. In round k, the trigger condition is satisfied by (s,a, a,,a h) when (s, in. We will refer to this Type-I trigger. For each time the trigger condition met for (s, a, h) the number of visits (s, a, h) increases by at least 1/(2M 1)) times. Specifically, when the trigger condition first satisfied, the visit number increases from 0 to at least 1. Therefore, the maximum number of Type-I triggers for each triple (s, a, h), denoted tz a, h), satisfies
(s,0,,))-
11+ 2MH +1)
S i1.
Therefore, we have
log(in)
( h) 5
+ =
log 2MH(H+1)
and thus the number of rounds with Type-I triggers is bounded by
Σ 8,0,
SOMMHSSA (i1))
(76)
2. In round k, the triple (s, a, satisfies the trigger condition when i < ( a) < + ig. We will refer to this as Type-II trigger if & (s) E (s) and a,, O, and Type-Ill trigger if (s) and P a, 0. By Lemma 5.3, for each time the trigger condition is satisfied by (s, a, h) the number of visits (s, a, h) increases by at least 1/3H + 1) times.
For (s, a, h) satisfying the type-Il trigger, by Equation (9) in Lemma 5.1 and Lemma 5.2, know that the maximum visit number to (s, a, h) is 32HCmin. Therefore, the maximum number of Type-Il triggers for each triple (s, (s),
denoted (2(s, a, h), satisfies
1 3H(H+1)
S 00
32HCmin
MH MH2/A2
=
H A min
min
Therefore, we have
log
HASA A-
H
12 a
+1 O
222 log
A min
log
3H(H+I)
and thus the number of rounds with Type-Il triggers is bounded by
HSSA A min
Σ (2(8, so (H s,a.h
(77)
3. By condition (b) of Definition 3.2, we know a = (s) for a Type-Ill trigger. Therefore, the maximum number of Type-Ill triggers for each triple (s, (s),)), h), denoted ts(s, (s). 1). satisfies
(s,
1
i + is < 12.
1 3H +1)
44

---

Gap-Dependent Bounds for Federated Q-Learning
Therefore, we have
log(12)
(a (8),,
+ 1 = 0
log (H(H+I)
Because we only have H.S triples (s)), h), the number of rounds with Type-Ill triggers is bounded by
Σ 20
s S (12))
(78)
4. The trigger condition is satisfied by (s, a, h) in round & when (5, a) > i
By Lemma 5.3, in this case, for each time the trigger condition is satisfied by (s, a, h) we have E (T)... we will first prove the trigger condition cannot be satisfied by (s, (5,a,h) h) in round when Aj(s), P 0 and N (s, a) > i1 + iz. Let Su {(, a, h) AÑ(s,, Fa, = 0}. By Lemma 5.2, we know for (s, a, h) E So. N M a) S 322H min à i2. However, when the trigger condition satisfied by (s, a, h)) in round k, we have (s, i ig, which is contradicts the fact that N (s, < in i2. Therefore the triple (s, a, satisfies that P 2,6 Then by Lemma 5.4, for any 8' E S and h' E [M] such that P2 > O, it holds that
N (s))
1 (H(H+1)
indicating that the number of visits (s', n (8'), 1(') with P times. We refer this type of trigger Type-IV trigger. Therefore, the maximum number of Type-IV triggers, denoted 44, satisfies
Av' > simultaneously increases by at least 1/6H
1+ (H(H+1))
T
11 12
HSA
The last inequality is because i2 > MHSA. Therefore, the number of rounds with Type-Ill triggers bounded by
log( HSA
O (11 log
T
)
log
(79)
HSA
log
1 (H[
By Equation (76), Equation (77), Equation (78) and Equation (79), the number of rounds is no more than
Σ a, + Σ t2(
Σ
(f), t
s,a.h
H$SA
T
MH (11) S
+ Slog (12) (0)++H21,, H2log log
A
50 SHHSSAlog (MH2() + HA
H
+ S1 +
(MH
A2 Cat )
H² log
HSA ))
T
2 min
The last incquality is because i2 S SH A Cst
By (c) Lemma E.I, we have
2MSAHT,
2MSAHT
log 2MSAH
))=0
SAT
= log
log
log
(80)
8
8
Let = 5/5 and 60 = log
MSAT
Since < d' < O(n) by Equation (80), then with probability at least 1 - p, the
number of rounds of communication no more than
o MHHSSAlog (MH²))) + SA
SAAA
+ H
SHO A
+ H² log
T
min Ca.
HSA
min
45


Reviews:
[{"review_id": "WnVhe1TWEB", "reviewer": "Reviewer_dRFT", "summary": "In the last few years, there has been an increase of interest in the topic of federated reinforcement learning (FRL), where agents interacting with similar (or exactly identical) MDPs communicate to achieve some speedup in performance. The authors consider such a formulation in the context of episodic finite-horizon problems, involving $M$ agents, each interacting with the same MDP. While this problem has been explored in the past, the authors improve upon prior results in the following ways:\n\n- They achieve gap-dependent regret bounds in FRL, i.e., regret bounds that scale with $\\log(T)$ and the inherent difficulty of the problem-instance, as opposed to the gap-independent $\\sqrt{T}$ bounds. \n\n- They manage to shave off from the $log(T)$ term some factors that depend on the number of states and actions. \n\n- The dependence on the communication rounds is also improved from prior work.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We provide point-by-point responses to your thoughtful comments.\n\n**W1: A direct extension.** We respectfully disagree that extending to FRL is trivial. FRL introduces unique challenges and requires new techniques beyond those used in single-agent RL, especially in controlling the estimation error of value functions due to its algorithm design and communication constraints.\n\nConcurrent RL assumes full raw data sharing and coordination via visit count thresholds. Existing works provide only worst-case regret, and even with full communication, bounding the extra regret caused by this delayed policy update is non-trivial.\n\nFRL, in contrast, imposes privacy and communication constraints, making the setting more complex. Due to on-policy learning and policy switching, stationary visitation distributions are unavailable, and the central server cannot track visit counts directly. FedQ-Hoeffding addresses this challenge with a trigger condition (Eq. (4)) and future-dependent weights (line 1269), but breaks the martingale structure typically used in concentration inequalities.\n\nAlso, FRL introduces a multi-agent burn-in cost $C_f$ in the regret. Directly applying single-agent techniques (e.g., Yang et al., 2021) would incur undesired dependency on $\\Delta_{\\min}$, which we avoid through delayed integration (see Lemma F.3).\n\n**W2, W4 pt.1: Comments on the log factor.** We respectfully believe that our improvement is significant, as this is the first gap-dependent communication cost bound for FRL, marking meaningful progress toward tight communication complexity with both theoretical and practical relevance.\n\nFirst, removing $M,S,A$ from the $\\log T$ term is significant, especially in large-scale applications like recommender systems (Covington et al., RecSys, 2016) or text-based games (Bellemare et al. JAIR, 2013), where $S,A$ can be enormous.\n\nSecond, the dependency of $M,S,A$ improves from $MSA\\log T$ to $MSA\\log\\log T$. Since the policy-switching cost lower-bounds communication rounds under synchronized policies, our improvement matches key advances in Qiao et al. (2022) and Zhang et al. (2022b) on policy-switching cost, highlighting the improvement from $\\log T$ to $\\log\\log T$ is both theoretically important and practically beneficial.\n\nFinally, the linear dependence on $S,A$ in the $\\log\\log T$ term is provably necessary, as Qiao et al. (2022) proves a lower bound of $O(HSA \\log \\log T)$ for policy switching cost. Compared to recent bounds scaling with $SA\\log T$ for FRL (e.g., Zheng et al., 2024, 2025a; Labbi et al., 2024), our result marks meaningful progress toward this lower bound.\n\n**W3: Regret speedup.** Yes, our regret bound does reflect a speedup w.r.t. $M$. In our paper, the average regret per episode is $O(\\frac{H^7SA\\log(MSAT)}{MT\\Delta_{\\min}})$ for sufficiently large $T$. This indicates a nearly $1/M$ rate of improvement under gap-dependent analysis, compared to the single-agent case that has an average regret of $O(\\frac{H^7SA\\log(SAT)}{T\\Delta_{\\min}})$. Our result achieves a faster rate of improvement than the commonly observed $\\sqrt{1/M}$ speedup in worst-case MDPs.\n\n**W4 pt.2: A non-trivial regime.** We respectfully argue that such regimes do exist. When $T>\\tilde{\\Theta}(\\textnormal{Poly}(\\frac{MH^2SA}{\\Delta_{\\min} C_{st}}))$ that is common in prior RL works (e.g., Zhang et al., 2020; Li et al., 2021), our gap-dependent result is strictly better than the prior bound $O(MH^3SA\\log T)$. Moreover, for any $X\\in\\{M,S,A\\}$, when $\\log T>\\Theta(X\\log(\\frac{X\\log(MSAT)}{\\Delta_{\\min}C_{st}})) $ that is used in other RL contexts (e.g., Weisz et al., ALT, 2021), our bound is independent of $X$, in contrast to prior bounds that scale linearly with it.\n\n**W5: Lower bounds.** Finding lower bounds in FRL is an important open problem. However, due to the inherent trade-off between regret and communication, establishing meaningful joint lower bounds is challenging. At one extreme, no communication among agents results in zero communication cost but no speedup in regret; at the other, full communication achieves linear regret speedup at a communication cost that scales with $T$. Both deviate from FRL’s goal of balancing these two objectives.\n\nStill, existing results support the structure of our results. The regret lower bound of $O\\left(\\frac{HSA}{\\Delta_{\\min}}\\log\\left( \\frac{T}{H}\\right)\\right)$ for single-agent RL in Xu et al. (2021) justifies the linear dependence on $S,A,\\Delta_{\\min}^{-1}$ and $\\log T$ in our result. Linear dependence in $H$ remains an open question in the literature.\n    \nAs for communication cost, although no gap-dependent or even worst-case lower bounds exist in FRL, the linear dependency on $S$, $A$, and $\\log\\log T$ is provably necessary, as noted in our response to W2.\n\n**Questions on two cases.** These two cases were proposed in Zheng et al. (2024) to reduce the estimation error of value functions. This design does not contribute to our improvement in communication cost.", "claims_and_evidence": "The claims are well-supported by rigorous proofs.", "methods_and_evaluation_criteria": "Since this is a theoretical paper, there is no evaluation criteria as such. This is not a limitation of the paper.", "theoretical_claims": "I skimmed through the proofs of the main claims and they appear correct to me.", "experimental_designs_or_analyses": "There are no experimental designs since the main contributions of the paper are theoretical.", "relation_to_broader_scientific_literature": "The paper refines the understanding of the emerging FRL literature by sharpening prior regret and communication bounds.", "essential_references_not_discussed": "All relevant references are discussed in adequate detail.", "other_strengths_and_weaknesses": "Strengths\n---------------\n- This paper appears to be the first to establish gap-dependent regret and communication-complexity bounds in FRL. \n- The ideas behind the design of the coordinated exploration scheme in FedQ-Hoeffding might apply more generally to similar episodic, finite-horizon problems. \n- The authors provide a fairly detailed exposition of their technical analysis in the main body of the paper. This was very helpful to get a quick sense of the main proof ideas. \n\nWeaknesses\n-------------------\n- My main concern with the paper is the following. Gap-dependent regret bounds are quite well known in the bandits and RL literature for the single-agent setting. This paper considers the homogeneous FRL setting where all agents interact with the *same* MDP. So essentially, this is a direct extension of the single-agent setting in a simplified tabular case with no function approximation. At least in the case where the agents communicate all the time, the gap-dependent bound analysis in the homogeneous FRL case seems a trivial extension of the single-agent counterpart. I am not sure if the extension to the case where agents communicate sporadically presents any major technical bottleneck. \n\n- The removal of dependencies on $M$, $S$, and $A$ from $\\log(T)$ is a nice contribution, but in the end, it is an improvement to a log-factor term. I do not necessarily consider this to be a significant contribution. \n\n- Given that all agents interact with the same MDP, I was hoping that the final regret bounds would show some sort of a speedup w.r.t. the number of agents $M$, relative to when the agents don't communicate. Whether such an improvement is indeed reflected in the final regret bound was not apparent to me looking at Eq.~(1). Could the authors comment on this aspect?\n\n- In terms of the improvement in communication claimed in Eq.~(2), I am not sure if this as significant as claimed. If I understand correctly, earlier communication bounds were on the order of $O(MSA \\log(T))$, while the refined bound has dependencies of the form of $MSA \\log(\\log(T))$. Thus, *communication still depends linearly on the number of states and actions*; the improvement is simply in terms of a logarithmic factor multiplying the number of states and actions. Furthermore, there are additional terms governing the communication complexity that continue to depend on $|S|$ and $|A|$ through higher-order dependencies on the horizon length $H$, and logarithmic dependencies on the gap $\\Delta_{min}$. As such, overall, it is unclear to me whether there is a non-trivial regime of the parameters $M, S, A, H, T, \\Delta_{min}$, where the gains in communication complexity are a significant improvement over prior results. \n\n- Since the paper is theoretical in nature, and the main contributions pertain to a refinement of prior bounds, I was hoping to see some lower bounds on the best achievable gap-dependent regret and the minimal number of communication rounds needed to achieve such a regret bound. Characterizing such lower bounds would shed light on the tightness of the guarantees presented in this paper. However, no such lower bounds are derived in this paper.", "other_comments_or_suggestions": "In the description of the FedQ-Hoeffding algorithm from Section 3, I would urge the authors to provide more intuition behind the rationale for the update strategies of the Q-table under Cases 1 and 2. At a high-level, why are these cases treated separately? Is it this separate treatment that leads to the final improvements in the communication-complexity?", "questions_for_authors": "I have no further comments or questions beyond those above.", "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": "gilIEx6Rln", "reviewer": "Reviewer_vCHq", "summary": "This paper studies the gap-dependent bounds for online federated Q-learning where multiple agents collaboratively explore and learn a global Q-function under tabular MDP setting. The authors provide analysis of both performance regret and communication cost of the online federated Q-learning algorithm (FedQ-Hoeffding), proposed in the previous work, in terms of gap-dependent parameters.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your careful reading and thoughtful comments. Below are our point-by-point responses, and we hope our responses address your concerns.\n\n**Weakness**: Contribution of the work\n\n**Response**: We respectfully disagree that our main result is merely an application of existing gap-dependent regret analyses [2, 3] that only focus on the single-agent setting. Our contributions go beyond adapting known techniques: we establish the first gap-dependent bounds on both regret and communication cost for federated RL (FRL) in the literature, and we develop new theoretical tools that are broadly applicable to other on-policy RL and FRL methods. \n\nBelow, we clarify our contributions in two parts.\n\nFirst, we explain new challenges and techniques in controlling the estimation error of value functions to prove **the first gap-dependent regret bound in FRL**. In contrast to the single-agent setting, FRL introduces additional regret due to delayed policy switching, which is necessary to reduce communication frequency. To overcome this challenge, we develop new recursions (see Eq. (35)) for bounding the additional regret in the weighted sum of value estimation errors across steps. \n\nAdditionally, our regret bound includes a multi-agent burn-in cost $C_f$. Applying the techniques of [2, 3] directly, this term would incur the undesired dependence on the gap $\\Delta_{\\min}$. We remove this dependency through a new delayed integration argument that carefully analyzes error recursion between adjacent steps (see Eq. (35) and Eq. (41)), which is not found in prior works.\n\nSecond, we also establish **the first gap-dependent communication cost in FRL**. Our result (Eq. (2)) improves upon [1] by removing the dependency on $M,S,A$ from the $\\log T$ term, which presents a substantial advance for the on-policy RL literature. This improvement is enabled by new technical insights. In FRL, synchronization is triggered when one triple meets the termination condition (Eq. (4)). Unlike [1], our analysis carefully controls synchronization triggered by optimal triples in late rounds, which is crucial for tightening the $\\log T$ dependence.\n\nSpecifically, our Lemmas 5.3 and 5.4 show that, when an optimal triple triggers synchronization in late rounds, the number of visits to all optimal triples across all agents grows exponentially. This simultaneous increase allows us to eliminate the dependency of $M,S,A$ from the $\\log T$-term in the count of trigger events and therefore in the number of communication rounds as well. Technically, this relies on a novel concentration result (Lemma 5.2) using error recursions from visits to suboptimal triples without assuming any stationary visitation distribution for the implemented policies. To our knowledge, this approach is novel in the RL literature.\n\n**Question 1**: the algorithm in Section 3.1\n\n**Response**: Yes, the algorithm we analyze is identical to the one in [1]. We only give a brief overview in the main paper, and the details are provided in Appendix C.1. Our contribution lies in the new analysis that yields the first gap-dependent bounds for FRL. \n\nAs for prior knowledge of the suboptimality gap, we agree this is an interesting direction. Incorporating such knowledge could potentially lead to more communication-efficient algorithms and may offer insights into reward design and its impact on learning efficiency. However, existing literature typically assumes the gap is unknown, and we follow that convention. \n\n**Question 2**: Speedup\n\n**Response**: The linear dependence on $M$ in the burn-in cost $C_f$ arises from the high estimation error in early rounds. This burn-in phase is necessary for coordinating policy updates and is common in FRL (e.g., [1, 4, 5]). Since the optimal value functions satisfy $V_h^*(s)\\leq H$ for any $(s,h)$, the minimum gap $\\Delta_{\\min}$ is upper bounded by $H$. When the total number of steps $T$ for each agent is sufficiently large, our gap-dependent bound becomes $O\\left(\\frac{H^6SA\\log(MSAT)}{\\Delta_{\\min}}\\right)$, which can enjoy a near-linear multi-agent speedup in the average regret for each episode.\n\n[4] Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Federated Q-learning with reference-advantage decomposition: almost optimal regret and logarithmic communication cost. ICLR, 2025.\n\n[5] Safwan Labbi, Daniil Tiapkin, Lorenzo Mancini, Paul Mangold, and Eric Moulines. Federated UCBVI: communication-efficient federated regret minimization with heterogeneous agents. AISTATS, 2025.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The key contribution of this paper is providing the gap-dependent regret bound of existing FedQ-Hoeffding, proposed in the previous work [1] with worst-case \\sqrt{T}-type regret bound.  Gap-dependent regret analysis for on-policy Q-learning has been studied in [2,3] for single-agent Q-learning case, and this work extends the gap-dependent analysis for FedQ-Hoeffding in federated settings.\n\n[1] Zheng, Z., Gao, F., Xue, L., and Yang, J. Federated qlearning: Linear regret speedup with low communication cost. In The Twelfth International Conference on Learning Representations, 2024\n\n[2] Yang, K., Yang, L., and Du, S. Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pp. 1576–1584. PMLR, 2021.\n\n[3] Zheng, Z., Zhang, H., and Xue, L. Gap-dependent bounds for q-learning using reference-advantage decomposition. In The Thirteenth International Conference on Learning Representations, 2025b.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths\n- This work offers the first gap-dependent regret bound and communication cost analysis for online Q-learning in federated environments.\n\nWeaknesses\n- The contribution appears somewhat incremental, as the primary result stems from applying existing gap-dependent regret analysis [2,3] to a previously established algorithm [1].", "other_comments_or_suggestions": "See questions below", "questions_for_authors": "1. The algorithm in Section 3.1 appears nearly identical to the one in [1]. I'm curious whether any modifications were made to hyper-parameters or communication triggering mechanisms specifically for the gap-dependent analysis. If changes exist, highlighting the differences between this version of FedQ-Hoeffding and the one in [1] would be valuable. Also, I'm curious whether the algorithm can be more efficient if we have prior knowledge of the suboptimality gap.\n2. Given the other gap-independent terms (C_f in (1)) in the regret bound, it seems that the algorithm can benefit from speedup in terms of number of agents when the suboptimality gap is sufficiently small. Could you provide intuition for why agents cannot enjoy the advantages of collaboration when the gap is large?", "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": "PrKue9Y0gU", "reviewer": "Reviewer_A3ZH", "summary": "The paper presents a gap-dependent analysis of regret and communication cost for on-policy Federated Q-Learning method. It improves prior worst-case regret bounds that scale as $\\sqrt{T}$ by $log⁡T$. The paper introduces a refined communication cost bound that distinguishes between exploration and exploitation, leading to improved efficiency. The results offer a multi-agent speedup pattern and remove the dependence of the communication cost on MSA in the logT term.\n\n## update after rebuttal\nI appreciate the authors' detailed responses. My questions and concerns have been addressed, and I will keep my score as it is.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your careful reading and thoughtful comments. Below are our point-by-point responses, and we hope our responses address your concerns.\n\n**Weakness 1**: Improve readability of technical details\n\n**Response**: Thanks for this helpful advice. To improve readability, we now provide a high-level explanation before diving into technical details.\n\n**Regret (High-Level Intuition)**: \n\nFedQ-Hoeffding is an optimism-based algorithm that guarantees $Q_h^k(s,a)\\geq Q_h^\\star(s,a)$ for all $(s,a,h,k)$. Under MDPs with a nonzero minimum suboptimality gap $\\Delta_{\\min}$, a suboptimal action $a$ is chosen at step $h$ for state $s$ only if the estimated value function satisfies $Q_h^k(s,a) = \\max_{a'} Q_h^k(s,a') \\geq \\max_{a'} Q_h^\\star(s,a')\\geq Q_h^\\star(s,a) + \\Delta_{\\min}$. This implies that only large estimation errors $Q_h^k-Q_h^*$ (at least $\\Delta_{\\min}$) contribute to the regret. Our proof formalizes this intuition. Lemma 4.2 links such estimation errors to the expected regret, and Lemma 4.1 controls the estimation errors via recursions over steps.\n\n**Communication Cost (High-Level Intuition)**: \n\nIn FedQ-Hoeffding, communication rounds are triggered only when a specific termination condition (Eq. (4)) is satisfied for some triple $(s, a, h)$. Thus, the total number of rounds is upper-bounded by the number of times this condition is triggered. The trigger condition ensures an exponential increase in the number of visits to the triple $(s, a, h)$ that triggers the condition.\n\nCompared to worst-case MDPs, the suboptimality gap helps identify the discrepancy between the number of visits to non-optimal and optimal triples: for non-optimal triples, the number of visits scales as $\\log T$ (Lemma 5.1), which is much smaller than the average sample size $T$ and results in $\\log \\log T$ trigger events with linear dependence on $M,S,A$; and for optimal triples, Lemmas 5.3 and 5.4 establish that if a trigger occurs for **one** optimal triple in the later rounds, it guarantees a simultaneous exponential increase in the number of visits to **all** optimal triples across all $M$ agents. This is the key insight that allows us to eliminate the dependency of $M,S,A$ from the $\\log T$-term in the count of trigger events and therefore in the number of communication rounds as well.\n\n**Weakness 2**: Summary of related work\n\n**Response**: Thanks for this helpful suggestion. To improve clarity and facilitate comparison, we now follow your advice to include a structured summary of related works in federated RL in the table below. The table highlights whether each work provides gap-dependent bounds, the corresponding regret bound, and the number of communication rounds. For simplicity, $O^*$ hides lower-order terms compared to $\\log T$, and $f_M \\in \\\\{1,M\\\\}$.\n\n| Algorithm            | Gap-dependent | Regret bound                                         | Number of rounds                  |\n|--------|-------|--------------|-------------|\n| Byzan-UCBVI (Chen et al., 2022)        | ×             | $\\tilde{O}(\\sqrt{MH^3S^2AT})$                        | $O(MHSA\\log T)$                   |\n| FedQ-Hoeffding (Zheng et al., 2024)    | ×             | $\\tilde{O}(\\sqrt{MH^4SAT})$                          | $O(MH^3SA\\log T)$                 |\n| FedQ-Bernstein (Zheng et al., 2024)    | ×             | $\\tilde{O}(\\sqrt{MH^3SAT})$                          | $O(MH^3SA\\log T)$                 |\n| FedQ-Advantage (Zheng et al., 2025a)   | ×             | $\\tilde{O}(\\sqrt{MH^2SAT})$                          | $O(f_MH^2SA(\\log H)\\log T)$       |\n| Fed-UCBVI (Labbi et al., 2025)         | ×             | $\\tilde{O}(\\sqrt{MH^2SAT})$                          | $O^*(HSA\\log T)$                  |\n| Our work                               | ✓             | $O^*\\left(\\frac{H^6SA\\log(MSAT)}{\\Delta_{\\min}}\\right)$ | $O^*(H^2\\log T)$                  |\n\n**Suggestion**: Rewrite the “Technical Novelty and Contributions\" section\n\n**Response**: In the revised version, we will incorporate the high-level intuition from our response to Weakness 1 into the Technical Novelty and Contributions section to make it more accessible to readers less familiar with this area.\n\n**Question**: Near-zero suboptimality gap\n\n**Response**: In finite-horizon tabular episodic MDPs, since the numbers of states, actions, and steps are finite, the minimum gap $\\Delta_{\\min} = \\inf\\\\{\\Delta_h(s,a) \\mid \\Delta_h(s,a)>0,(s,a,h)\\in \\mathcal{S}\\times \\mathcal{A}\\times [H]\\\\}$ is positive as long as at least one suboptimal action exists, that is, $\\\\{\\Delta_h(s,a) \\mid \\Delta_h(s,a)>0,(s,a,h)\\in \\mathcal{S}\\times \\mathcal{A}\\times [H]\\\\} \\neq \\emptyset$. Otherwise, all actions are optimal (i.e., the set above is empty), leading to a degenerate MDP. Therefore, in all non-degenerate tabular MDPs, which are the focus of our setting, $\\Delta_{\\min}>0$, ensuring that our gap-dependent regret bound remains valid and does not degrade, even if some suboptimality gaps are very small.", "claims_and_evidence": "The paper claims to improve the theoretical bounds for FedQ-Hoeffding from prior work (Zheng, 2024), specifically providing gap-dependent bounds for regret and communication cost. Theoretical analysis supports the claims. \nIt also includes numerical experiments in the appendix that illustrate the theoretical dependencies of communication costs on various parameters.", "methods_and_evaluation_criteria": "This is a theoretical study, and the methods used for evaluation rely entirely on mathematical proofs and complexity analysis. Given that the objective of this work is improving theoretical bounds, this approach is appropriate. The numerical experiments presented in the appendix serve to validate theoretical insights.", "theoretical_claims": "While I did not verify the proof steps in detail, the results appear consistent with numerical experiments.", "experimental_designs_or_analyses": "As this is a theoretical study, no extensive experimental validation is expected.", "relation_to_broader_scientific_literature": "The paper fits within the broader context of federated reinforcement learning. It builds on prior work (Zheng, 2024) by introducing improved theoretical guarantees.", "essential_references_not_discussed": "No critical references appear to be missing. However, a more structured comparison with existing methods (e.g., via a table) would improve clarity (see below).", "other_strengths_and_weaknesses": "Strengths:\nProvides a meaningful theoretical advancement in the regret analysis of federated Q-learning.\nAddresses an open problem regarding gap-dependent regret bounds in on-policy FRL.\nWeaknesses (Clarity): \nProviding a more intuitive explanation or a high-level overview before diving into technical details could improve readability.\nThe discussion of related work in the introduction is relatively unstructured; listing prior results in paragraphs makes it difficult to compare methods effectively. A table summarizing related work, regret bounds, and key assumptions would be helpful to compare and categorize the works cited.", "other_comments_or_suggestions": "Technical novelty and contributions section could be rewritten to be more accessible to readers who are not experts in this specific area.", "questions_for_authors": "The paper assumes strictly positive suboptimality gaps. How would the results change if some actions had near-zero gaps? Would the bounds degrade?", "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": "uctfp39wtm", "reviewer": "Reviewer_Cred", "summary": "This work studies instance-dependent regret guarantees in tabular Markov Decision Processes within a federated learning framework, where multiple agents collaborate to learn the environment. Specifically, the author focuses on the minimal sub-optimality gap structure and provides the first logarithmic regret guarantee in federated reinforcement learning. Additionally, compared to the previous communication cost for $\\sqrt{T}$-type regret, the proposed algorithm achieves a lower communication cost by seperating the dependency on the size of the state-action space and the log-dependency on the number of episode $T$.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your careful reading and thoughtful comments. Below are our point-by-point responses to your questions, and we hope our responses address your concerns.\n\n**Theoretical Claim**: Specific factors lead to the continuous improvement\n\n**Response**: Thanks for this insightful comment. We agree that it is important to clarify this improvement. \n\nTo begin with, it is worth pointing out that [1] only removes the dependence on $A$ only for MDPs with unique optimal actions. In contrast, our work removes the dependence on $M,S,A$ from the $\\log T$ term in **general MDPs (G-MDPs)**, which include MDPs with unique optimal actions as a special case. Both [1] and our paper exploit the common discrepancy between the numbers of visits to optimal triples and suboptimal triples. This allows the number of synchronizations (or policy switches) triggered by suboptimal triples to be bounded by the $\\log \\log T$ terms that still depend on $S$ and $A$. \n\nOur **key improvement** is in further removing the dependency on $M, S$ for the $(\\log T)-$term that bounds the number of synchronization triggered by optimal triples in late rounds. This is achieved through new technical insights. In FRL, synchronization is triggered when one triple meets the termination condition (Eq. (4)). Unlike [1], our analysis carefully controls synchronization triggered by optimal triples in late rounds, which is crucial for tightening the $\\log T$ dependence.\n\nSpecifically, our Lemmas 5.3 and 5.4 show that, when an optimal triple triggers synchronization in late rounds, the number of visits to all optimal triples across all agents grows exponentially. This simultaneous increase allows us to eliminate $M,S,A$ from the $\\log T$-term in the count of trigger events and therefore in the number of communication rounds as well. Technically, this relies on a novel concentration result (Lemma 5.2) using error recursions from visits to suboptimal triples without assuming any stationary visitation distribution for the implemented policies. To our knowledge, this approach is novel in the RL literature.\n\nWe also remark that removing the $S$-dependency in [1] is impossible due to its unaligned stage design, which prevents the simultaneous updating of policies for all state-action pairs.\n\n**References Not Discussed**: a relevant work\n\n**Response**: We agree that this is a relevant reference to the federated setting and will add it in our revised version.\n\n**Suggestion**: Provide an explicit algorithm\n\n**Response**: Due to page limits, we give an overview of the algorithm in Section 3.1 of the main paper and then provide the full algorithm in Appendix C.1. For clarity and ease of understanding, we also follow your suggestion to outline each step as follows:\n\n**Step 1: Coordination.** At the beginning of round $k$, the server broadcasts $\\pi^k = \\\\{\\pi_h^k\\\\}\\_{h=1}^H$, $\\\\{N_h^k(s,\\pi_h^k(s))\\\\}\\_{s,h}$ and $\\\\{V_h^k(s)\\\\}_{s,h}$ to all of the agents. When $k=1$, $N_h^1(s,a) = 0,Q_h^1(s,a) = V_h^1(s)=H,\\forall (s,a,h)$ and $\\pi^1$ is an arbitrary deterministic policy. Once receiving such information, the agents will execute policy $\\pi^k$ and start collecting trajectories. \n\n**Step 2: Event-Triggered Termination.** During exploration, every agent $m$ will monitor $n_h^{m,k}(s,a)$, which is the total number of visits for $(s,a,h)$ in round $k$. For any agent $m$, at the end of each episode, if any $(s,a,h)$ has been visited by $\\max\\left\\\\{1,\\lfloor \\frac{1}{MH(H+1)} N_h^k(s,a) \\rfloor \\right\\\\}$ times by agent $m$, the agent will send a signal to the server, which will then request all agents to abort the exploration.\n\n**Step 3: Local Aggregation.** After the exploration is terminated, each agent updates the local estimate of the expected return $v_{h+1}^{m,k}(s,a)$:$$v_{h+1}^{m,k}(s,a)=\\frac{1}{n_h^{m,k}(s,a)}\\sum_{j=1}^{n^{m,k}}V_{h+1}^k\\left(x_{h+1}^{m,k,j}\\right)\\mathbb{I}[\\{(x_h^{m,k,j},a_h^{m,k,j})=(s,a)\\}],\\forall (s,a,h).$$\nNext, each agent $m$ sends $\\\\{r_h(s,\\pi_h^k(s))\\\\}\\_{s,h}$, $\\\\{n_h^{m,k}(s,\\pi_h^k(s))\\\\}\\_{s,h}$ and $\\\\{v_{h+1}^{m,k}(s,\\pi_h^k(s))\\\\}\\_{s,h}$ to the central server. \n\n**Step 4: Server-side Aggregation.** After receiving the information sent by the agents, the central server will update the value functions $Q_h^{k+1}(s,a)$ and $V_h^{k+1}(s)$, as well as the policy $\\pi^{k+1}$, as shown in Appendix C.1.\n\nThe algorithm then proceeds to round $k+1$.", "claims_and_evidence": "The author provides a clear claim of the result in the theorems and includes a proof sketch to outline the key steps of the theoretical analysis.", "methods_and_evaluation_criteria": "The main contribution of this work focuses on the theoretical analysis of regret, with the simulation serving as an auxiliary tool to support its efficiency, which is reasonable and sufficient.", "theoretical_claims": "The theoretical analysis primarily focuses on two aspects: the regret guarantee and the communication complexity.\n\nFor the regret guarantee, the logarithmic regret is achievable under the assumption of a minimal sub-optimality gap, and the proof sketch aligns with previous analyses of logarithmic regret but is adapted to a more complex federated learning framework.\n\nFor the communication complexity, achieving logarithmic communication complexity is reasonable with a predefined trigger criterion in federated Q-learning. However, I have concerns about the claimed improvement that separates the dependency on the size of the state-action space and the log-dependency on the number of episodes $T$. As discussed in the proof sketch, the improvement comes from the assumption of a minimal sub-optimality gap, which ensures that sub-optimal actions are taken only $O(\\log T)$ times. However, a similar motivation was used in [1] to reduce the dependency on the action space size $A$, since each state has a unique optimal action. It is important to clarify what specific factors lead to the continuous improvement that further removes the dependency on the state space size $S$.\n\n[1] Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition", "experimental_designs_or_analyses": "The main contribution of this work focuses on the theoretical analysis of regret, with the simulation serving as an auxiliary tool to support its efficiency, which is reasonable and sufficient. Therefore, there is no need to evaluate the soundness or validity of the experimental designs or analyses.", "relation_to_broader_scientific_literature": "This work mainly focuses on providing an instance-dependent guarantee for federated reinforcement learning, which may be related to other works on federated learning.", "essential_references_not_discussed": "This paper provides a comprehensive discussion of related work in federated reinforcement learning and batch reinforcement learning. However, it would be beneficial to also consider \"A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits,\" which is relevant to the setting of federated learning.", "other_strengths_and_weaknesses": "No other strengths and weaknesses.", "other_comments_or_suggestions": "In the main paper, it would be beneficial to provide an explicit algorithm and clearly outline how it progresses in each step. This would improve readability and help readers better understand the methodology.", "questions_for_authors": "As discussed in Theoretical Claims, it is important to clarify what specific factors lead to the continuous improvement that further removes the dependency on the state space size $S$.", "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:

Meta-review: This paper studies the gap-dependent bounds for online federated Q-learning where multiple agents collaboratively explore and learn a global Q-function under tabular MDP setting. The authors provide analysis of both performance regret and communication cost of the online federated Q-learning algorithm (FedQ-Hoeffding), proposed in the previous work, in terms of gap-dependent parameters.

Reviewers think the results are strong and the techniques are novel. The AC agrees and thus recommends acceptance.
Decision: Accept (poster)