Gap-Dependent Bounds for Federated $Q$-Learning

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.

Theoretical Claim: Specific factors lead to the continuous improvement

Response: Thanks for this insightful comment. We agree that it is important to clarify this improvement.

To 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$.

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

Specifically, 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.

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

References Not Discussed: a relevant work

Response: We agree that this is a relevant reference to the federated setting and will add it in our revised version.

Suggestion: Provide an explicit algorithm

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:

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.

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.

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).$ Next, 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.

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.

The algorithm then proceeds to round $k+1$.

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.

Weakness 1: Improve readability of technical details

Response: Thanks for this helpful advice. To improve readability, we now provide a high-level explanation before diving into technical details.

Regret (High-Level Intuition):

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

Communication Cost (High-Level Intuition):

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

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

Weakness 2: Summary of related work

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\\}$.

Suggestion: Rewrite the “Technical Novelty and Contributions" section

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.

Question: Near-zero suboptimality gap

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.

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.

Weakness: Contribution of the work

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.

Below, we clarify our contributions in two parts.

First, 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.

Additionally, 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.

Second, 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.

Specifically, 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.

Question 1: the algorithm in Section 3.1

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.

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

Question 2: Speedup

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.

[4] Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Federated Q-learning with reference-advantage decomposition: almost optimal regret and logarithmic communication cost. ICLR, 2025.

[5] Safwan Labbi, Daniil Tiapkin, Lorenzo Mancini, Paul Mangold, and Eric Moulines. Federated UCBVI: communication-efficient federated regret minimization with heterogeneous agents. AISTATS, 2025.

We provide point-by-point responses to your thoughtful comments.

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.

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

FRL, 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.

Also, 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).

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.

First, 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.

Second, 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.

Finally, 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.

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.

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.

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.

Still, 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.

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

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.