Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement 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.

Weakness 1: Simple numerical experiments

We have conducted additional experiments to demonstrate the reduced communication cost and low burn-in cost compared to other baselines.

Additional Experiment 1: Comparison of switching cost with UCB-Advantage [1] and the number of communication rounds with FedQ-Advantage [2]

To evaluate the switching/communication cost of different algorithms, we plot the average regret per episode, defined as $\text{Regret}(T)/(MT)$, against the policy switching cost in single-agent RL or the number of rounds in FRL.

Specifically, to show our results, we choose a set of average regret thresholds $\\{0.5,0.3,0.1,0.05,0.03,0.01\\}.$ For each algorithm, we conduct 10 independent trials and report the median policy switching cost for single-agent RL or median number of communication rounds for FRL required for average regret to fall below each threshold. All evaluations are conducted in the two synthetic environments described in Appendix B, denoted by Settings I-II for single-agent RL and III-IV for FRL. The table below summarizes the results (rounded to the nearest integer), where “None” indicates that the algorithm did not reach the target average regret within the allotted number of episodes.

Table 1: Median policy switching cost (settiing I and II) or number of rounds (settiing III and IV) required to reach each average regret.

These results demonstrate that, to achieve any given average regret, our algorithm incurs a lower policy switching cost than UCB-Advantage in single-agent RL, and requires fewer communication rounds than FedQ-Advantage in FRL.

Additional Experiment 2: Burn-in cost comparison

We also conducted additional experiments for burn-in cost under the two synthetic environments described in Appendix B, denoted by Settings I-II for single-agent RL and III-IV for FRL. To evaluate the burn-in cost of different algorithms, we plot the normalized regret curves $\frac{\text{regret}(t)/\log(t+1)}{\text{regret}(N)/\log(N+2)},$ where $N = T/H$ denotes the total number of episodes per agent. By examining these curves, we observe that, our algorithm consistently requires the smaller number of episodes than all baseline methods to achieve the same normalized regret level.

To show the results, we select a set of normalized regret thresholds $\\{0.5,0.8,0.85,0.9,0.95,0.99\\}.$ For each algorithm, we conduct 10 independent trials and report the median number of episodes per agent needed to reach or exceed each threshold. As shown in the following table, our method achieves lower burn-in cost and superior sample efficiency.

Table 2: Median number of episodes per agent required to reach each normalized regret.

Weakness 2: Notation is a bit heavy

Thank you for the suggestion. To improve clarity and ease of reference, we have included two notation summary tables for our algorithms in Appendix D.2 of the original submission.

Weakness 3: A lack of proof sketch in the main text

Thank you for the suggestion. Due to space constraints, we did not include the proof sketch in the main text of the original submission. However, we will incorporate a key proof sketch into the main text using the additional page provided for the revised manuscript.

Question: Extension to general cases with continuous state and action space

Thank you for the insightful question. Extending FedQ-EarlySettled-LowCost to non-tabular settings, such as those involving continuous state/action spaces or linear function approximation, is a promising but nontrivial direction for future work.

Recent works have explored related ideas in the offline RL setting. For example, [3] proposes a federated offline RL algorithm using confidence-bound methods, while [4, 5] apply reference-advantage decomposition techniques in offline RL with linear function approximation. These works demonstrate the feasibility of using confidence bounds and reference-advantage decomposition techniques in non-tabular environments.

However, adapting our event-triggered termination mechanism to non-tabular settings presents significant challenges. For environments with continuous state spaces, it becomes difficult to quantify visitation counts, the design of stopping conditions for exploration becomes ambiguous, and policy updates based on event-triggered signals must be carefully coordinated across agents become complex, especially under communication cost constraints. These challenges in the online RL and online FRL settings require new algorithmic and theoretical tools. We agree with you and view this as an important direction for future work.

[1] Zihan Zhang, Yuan Zhou and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. NeurIPS 2020.

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

[3] Doudou Zhang, Yufeng Zhang, Aaron Sonabend-W, Zhaoran Wang, Junwei Lu and Tianxi Cai. Federated offline reinforcement learning. Journal of the American Statistical Association, 2024.

[4] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang and Tong Zhang. Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game. ICLR, 2023.

[5] Qiwei Di, Heyang Zhao, Jiafan He and Quanquan Gu. Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning. ICLR, 2024

I thank the authors for their effort in writing the detailed rebuttal. They addressed my questions well. I maintain my original scoring for 'accept'.

We appreciate your careful reading and thoughtful comments. Below are our point-by-point responses, and we hope our responses address your concerns.

Weakness 1 and Question: Technical contributions

We respectfully disagree with the view that our method simply combines prior techniques. Instead, we have developed novel analytical tools that go beyond prior work. Appendix C provides a detailed discussion of the challenges and our corresponding contributions. Below, we further clarify why our contributions go beyond incremental advances.

Challenge 1: Non-adaptiveness of weights and reference functions

Previous works only addressed isolated aspects of non-adaptiveness: [1] applies round-wise approximation for non-adaptive weights, and [2] uses the empirical process for settled reference functions. However, no prior work simultaneously resolves both forms of non-adaptiveness, and their direct combination introduces substantial technical difficulties. Notably, the empirical process in [2] incurs an extra $\log T$ factor due to $\epsilon$-net construction over non-adaptive reference function classes. When combined with round-wise approximations, the existence of nonadaptive weights can increase the effective dimension of the $\epsilon$-nets, leading to looser regret bounds. It would require a new proof idea to solve this non-trivial challenge.

Contribution 1: Unified treatment via surrogate reference functions

We address both forms of non-adaptiveness by integrating the surrogate reference function technique from [3], originally developed for gap-dependent analysis, into our worst-case regret framework. This enables a new decomposition that improves both theoretical bounds and generality. Specifically, our framework can be applied to existing reference-advantage-based RL methods [2, 4, 5], tightening their regret bounds. In model-free RL or FRL, worst-case regret is typically bounded by relating regret to the estimation error of the optimal $Q$-function, that is $\sum_{k,j,m}(Q_h^k-Q_h^\star)(s_h^{k,j,m},a_h^{k,j,m}).$ Prior methods upper-bound each term via $Q_h^{\text{R}}-Q_h^\star$ and then bound the sum recursively over $h$. Specifically, based on the reference-advantage update rules (Eq. 11, 15), with high probability, $Q_h^{\text{R},k}-Q_h^\star\leq\mathcal{G}_0$, where $\mathcal{G}_0$ is defined in Appendix C.

Following the structure of the reference-advantage decomposition, and using the surrogate reference function $\hat{V}\_h^{\text{R},k}$, $\mathcal{G}\_0$ can be upper bounded by the summations with respect to $C_B,\hat{\mathcal{G}}\_1,\hat{\mathcal{G}}\_2,\hat{\mathcal{G}}\_3,\hat{\mathcal{G}}\_4$, where $C_B$ collects some constants and the cumulative bonuses, $\hat{\mathcal{G}}\_1$ reflects the estimation error $V_{h+1}^{k}-V_{h+1}^\star$, $\hat{\mathcal{G}}\_3$ reflects the reference settling error $V_{h+1}^{\text{R},k}-\hat{V}\_{h+1}^{\text{R},k}$, and $\hat{\mathcal{G}}\_2,\hat{\mathcal{G}}\_4$ reflect the empirical estimation error for the settled advantage function $V_{h+1}^\star-\hat{V}\_{h+1}^{\text{R},k}$ and surrogate reference function $\hat{V}\_{h+1}^{\text{R},k}$.

In contrast to the original decomposition from [2], where non-adaptive weights and non-adaptive reference functions together result in looser regret bounds, our surrogate reference function is adaptive, mitigating both issues. The adaptive design ensures that non-adaptive weights, which reflect delayed policy switching, is incorporated without introducing additional error via empirical process tools. As a result, we achieve a $\log(SAT/p)$ improvement in the regret bound over Q-EarlySettled-Advantage [2], marking the first application of surrogate reference functions in worst-case RL and significantly expanding the analytical tools for RL that overcome limitations in [2, 4, 5].

Challenge 2: Balancing low switching cost and regret

In online RL, achieving a logarithmic policy switching cost typically relies on delayed policy updates, as in [6, 7]. However, delayed policy updates introduce extra regret, since the same policy is reused across episodes before any state-action-step triple reaches a predefined threshold. This trade-off explains why, the low-switching-cost variants of UCB-Hoeffding and UCB-Bernstein ([6]) underperform their standard counterparts, as shown in Figure 1. How to achieve better regret at a low switching cost with delayed policy updates remains a significant challenge.

Contribution 2: Two-sided confidence bounds for improved bonus design

We introduce a new two-sided variance bound to tighten regret under delayed updates in the proof of the optimism property ($Q_h^k\geq Q_h^\star$, Lemma H.1). Specifically, we derive both upper and lower bounds on the variance estimator (Eq. 33, 37, 38), whereas prior works such as [2] only use the lower bound. This refinement leads to more accurate confidence intervals in parts (b) and (c) of Lemma G.1 and allows us to improve the bonus term $\beta_h^R$ in the reference-advantage decomposition, reducing the cumulative bonus $C_B$ and yielding both tighter regret and better empirical performance.

Additionally, to integrate this with a round-based design, we adapt the variance estimator by using one estimator in early rounds and another in later rounds, as detailed in Eq. 8 and 12. This adaptive approach ensures consistent accuracy of the bonus term across different phases of learning.

Challenge 3: LCB with round-nased design

FedQ-Advantage [5] settles reference functions only after a state-step pair has been visited sufficiently often, which introduces a polynomial dependence on $S,A$ in the bound for $V_h^{\text{R},K}-V_h^K$, resulting in high burn-in cost. This dependence limits the practicality in large-scale environments.

Contribution 3: LCB-triggered reference settling for reduced burn-in cost

We are the first in the literature to apply the LCB technique in FRL. In our design, $V_h^{k}$ and LCB-estimates $V_h^{\text{L},k}$ serves as upper and lower bounds for $V_h^\star$. The reference function is settled once $V_h^k-V_h^{\text{L},k}\leq\beta$, ensuring $V_h^\star\in[V_h^{\text{L},k},V_h^k]$. This allows us to settle the reference earlier and bound the settling error $\hat{\mathcal{G}}_4$ more tightly, reducing dependence on $H,S,A$.

To accommodate the round-based design of FRL, we modify the standard LCB strategy used in single-agent RL: early rounds adopt the same design as in the single-agent setting, while late rounds use an equal-weight estimator (Eq. 14), balancing accuracy with communication efficiency.

Weakness 2: Empirical performance

Notably, the $HSA$ term in the coefficient for both regret and switching/communication cost is unavoidable. In fact, [8] provides a lower bound of $\tilde{\Omega}(HSA/\Delta_{\min})$ for single-agent RL, demonstrating that any algorithm must incur regret with a coefficient that scales linearly with $HSA$. Similarly, [7] proves a lower bound $\tilde{\Omega}(HSA)$ on switching cost for any algorithm with $\tilde{O}(\sqrt{T})$ regret, highlighting that the coefficient of switching/communication costs must also grow linearly with $HSA$.

Importantly, model-free RL algorithms with larger theoretical regret constants and $O(T)$ switching/communication cost are already used in practice. For example, in single-agent RL, [9] proposes Action-Robust Q-learning based on UCB-Hoeffding, which has a regret bound of $\tilde{O}(\sqrt{H^4SAT})$, corresponding to a coefficient larger than 10,000 in our setting (see Figure 1, UCB-Hoeffding), and incurs a switching cost scales as $O(T)$. Nevertheless, the algorithm performs well in Cliff Walking, a text-based environment with $(H,S,A)=(100,48,4)$, and Inverted Pendulum, a control task simulated in MuJoCo with $H=100$. Similarly, [10] extends UCB-Hoeffding to a multi-agent setting for cooperative navigation with $10^4$ states. Despite a regret bound of $O(H^6SA\log(T)/\Delta_{\min})$ with a coefficient over 10,000 (see Figure 3, FedQ-Hoeffding) and a communication cost scales as $O(MHSAT)$ under full communication, the algorithm still achieves strong empirical results.

Therefore, large constants (especially those polynomial in $H,S,A$) do not preclude practical effectiveness. In comparison, our algorithm achieves smaller coefficient than other baselines (Figures 1–4), demonstrating practical utility even in moderate-horizon settings.

[1] Zhong Zheng, Fengyu Gao, Lingzhou Xue and Jing Yang. Federated Q-learning: Linear regret speedup with low communication cost. ICLR 2024.

[2] Gen Li, Laixi Shi, Yuxin Chen and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Information and Inference, 2023.

[3] Zhong Zheng, Haochen Zhang and Lingzhou Xue. Gap-dependent bounds for Q-learning using reference-advantage decomposition. ICLR 2025.

[4] Zihan Zhang, Yuan Zhou and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. NeurIPS 2020.

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

[6] Yu Bai, Tengyang Xie, Nan Jiang and Yu-Xiang Wang. Provably efficient Q-learning with low switching cost. NeurIPS 2019.

[7] Dan Qiao, Ming Yin, Ming Min and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog(t) switching cost. ICML 2022.

[8] Haike Xu, Tengyu Ma and Simon Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. ICML 2021.

[9] Guanlin Liu, Zhihan Zhou, Han Liu and Lifeng Lai. Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty. TMLR 2024.

[10] Justin Lidard, Udari Madhushani and Naomi Leonard. Provably efficient multi-agent reinforcement learning with fully decentralized communication. ACC 2022.

Dear Reviewer a3AW,

Thank you again for your thoughtful review. In our rebuttal, we have further clarified our technical contributions and provided additional explanation regarding the practical performance of our algorithm. We hope our responses have addressed your questions and concerns. Please feel free to let us know if there is anything else we can clarify. We would be happy to provide further information.

Thank you for your time and consideration.

Thank you once again for your response and for sharing your insights. In the second part of our response, we would like to further clarify the contributions and technical novelties of our work.

We respectfully disagree that the contributions are incremental. While our work use some existing theoretical tools, directly combining them is non-trivial and insufficient to achieve our results:

(1) Combining techniques such as the empirical process [5] to address non-adaptive weights and settled reference functions leads to an additional dependence on $T$ and results in looser regret bounds.

(2) Delayed policy updates are a common strategy for achieving low switching cost [4, 10], but they incur extra regret due to outdated policies. Balancing low switching cost with strong regret performance remains non-trivial and requires new techniques.

(3) Round-based designs for reference functions, such as FedQ-Advantage [11], suffer from high burn-in costs due to polynomial dependence on $S, A$.

Beyond synthesizing known ideas, our paper introduces at least three following key technical innovations:

Novel decomposition for worst-case regret: The reference-advantage decomposition, commonly used to achieve optimal regret in online RL, faces key limitations in our round-based setting, particularly under communication constraints, due to its non-adaptiveness in both the weighting scheme and the settled reference functions. To address this issue, we propose a novel decomposition for worst-case regret (detailed in Appendix C and also our initial response), which leverages surrogate reference functions to construct a tighter upper bound on worst-case regret.

While surrogate reference functions were originally introduced in [11], our work is the first to apply them in the worst-case RL setting and within the federated RL framework, using only their core definition and without relying on auxiliary techniques previously developed for gap-dependent analysis. This decomposition represents a new and general contribution to the online RL literature. Furthermore, our decomposition is general and can be used to strengthen the analysis in several existing works [3, 5, 12].

Two-sided variance bound for improved bonuses: Bonus design plays a crucial role in reinforcement learning. For instance, UCB-Bernstein outperforms UCB-Hoeffding by leveraging its tighter bonus derived from the Bernstein inequality [13]. Similarly, [14] achieves the information-theoretic lower bound using the same algorithmic structure as [15], with a single but crucial change: replacing the original bonus with a Bernstein-type bonus that incorporates a more accurate variance estimator. Such improvements rely on nontrivial analytical advances.

In our work, rather than directly combining existing techniques, we develop a novel two-sided variance bound that yields a tighter bonus. This refinement is key to establishing the optimism property (Lemma H.1) and leads to both improved theoretical regret bounds and enhanced empirical performance. Our variance bound is general and can potentially benefit bonus design in prior works such as [3, 5, 11, 12].

Lower confidence bound (LCB) with round-based design: To our knowledge, we are the first in the literature to deploy the LCB technique in the online FRL setting. Unlike its traditional use in single-agent scenarios, we adapt the classical LCB framework to a round-based paradigm that emphasizes low switching and communication costs.

Our method introduces a novel hybrid design that adjusts strategies between early and late rounds, effectively combining LCB-based exploration with round-based synchronization. This adaptive mechanism enables more efficient learning under communication constraints and may serve as a blueprint for using LCB in similar federated settings.

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 part 1: Exact bounds in Tables

We follow this helpful suggestion and provide updated tables with explicit bounds to facilitate clearer comparisons.

We first define the following notations: $\iota=\log(SAT /p)$, where $p\in (0,1)$ is the failure probability; $C_g=SA\log(T)/\Delta_{\min}$; $\mathbb{Q}^\star:=\max_{s,a,h}\{\mathbb{V}\_{s,a,h}(V_{h+1}^\star)\}\in[0,H^2]$; $\beta\in (0,H]$ is an arbitrarily predefined hyper-parameter; and $O^\star$ only captures the main $\log T$ term. The following tables show that our algorithm achieves state-of-the-art performance in both regret and switching/communication costs (Our detailed switching/communication cost results can be found in Theorems 4.6 and 4.8).

Table 1: Comparison of model-free online single-agent RL algorithms.

Table 2: Comparison of model-free online FRL algorithms.

Weakness 1 part 2 and Question 2: Additional comparison with FedQ-Advantage

Theoretically, for sufficiently large $T$, our algorithm achieves a switching/communication cost of $O(H^2\log T)$, which improves upon the $O(H^2S\log T)$ cost of UCB-Advantage [106] and the $O(MH^2SA\log T)$ cost of FedQ-Advantage [109].

Empirically, to evaluate the switching/communication cost of different algorithms, we plot the average regret per episode, defined as $\text{Regret}(T)/(MT)$, against the policy switching cost in single-agent RL or the number of rounds in FRL.

Specifically, to show our results, we choose a set of average regret thresholds $\\{0.5,0.3,0.1,0.05,0.03,0.01\\}.$ For each algorithm, we conduct 10 independent trials and report the median policy switching cost for single-agent RL or median number of communication rounds for FRL required for average regret to fall below each threshold. All evaluations are conducted in the two synthetic environments described in Appendix B, denoted by Settings I-II for single-agent RL and III-IV for FRL. The table below summarizes the results (rounded to the nearest integer), where “None” indicates that the algorithm did not reach the target average regret within the allotted number of episodes.

Table 3: Median policy switching cost (settiing I and II) or number of rounds (settiing III and IV) required to reach each average regret.

These results demonstrate that, to achieve any given average regret, our algorithm incurs a lower policy switching cost than UCB-Advantage in single-agent RL, and requires fewer communication rounds than FedQ-Advantage in FRL.

Weakness 2: Technical novelty

We appreciate the opportunity to clarify our novelty. Our work does not simply combine prior techniques. Instead, we have developed novel analytical tools that go beyond prior work. Appendix C provides a detailed discussion of the challenges and our corresponding contributions. Our novelty and contribution lie in addressing non-trivial theoretical and algorithmic challenges that arise when combining their respective strengths.

The reference-advantage decomposition, suffers from non-adaptiveness in both weights and reference functions when applied in a round-based setting, especially under communication constraints. We propose a new decomposition that uses surrogate reference functions, enabling tighter worst-case regret bounds while avoiding reliance on empirical process techniques that result in an additional factor of $\log T$.

We also introduce a new two-sided variance bound to tighten regret under delayed updates in the proof of the optimism property ($Q_h^k\geq Q_h^\star$, Lemma H.1). Specifically, we derive both upper and lower bounds on the variance estimator (Eq. 33, 37, 38), whereas prior works (such as [48]) only use the lower bound. This refinement leads to more accurate confidence intervals in parts (b) and (c) of Lemma G.1 and allows us to improve the bonus term $\beta_h^R$ in the reference-advantage decomposition, reducing the cumulative bonus and yielding both tighter regret and better empirical performance.

Further, we leverage the Lower confidence bound to trigger early reference settling. Unlike the single-agent setting, our method adopts a different design in the early and late rounds to integrate the LCB-based strategy with round-based synchronization, ensuring low switching and communication costs. This approach is formalized in Equations (10) and (14), which help bound the reference settling error in Lemma H.4 and contribute to reducing the burn-in cost—a benefit that prior FRL methods (e.g., FedQ-Advantage) cannot achieve.

Finally, in the FRL setting, integrating these techniques involves new challenges in synchronizing learning progress across agents, managing reference settling in a distributed and delayed-update setting, and maintaining both low communication cost and low switching cost.

Question 1: Notation

Thank you for the advice! We will correct this notation accordingly in the revised manuscript.

Question 3: Key to reduce burn-in cost

Our work improves upon FedQ-Advantage by addressing key sources of estimation error that contribute to the burn-in cost. Specifically:

LCB-Based Reference Settling. Our algorithm introduces an LCB-type estimate $Q_h^{\text{L},k}$ to control the reference settling error more tightly in Lemma H.4. This reduces dependence on $H,S,A$, leading to a lower burn-in cost.

Two-Sided Inequality for Tighter Bonuses. As discussed in our response to Weakness 1 part 2, we use a new two-sided inequality to refine the reference-advantage bonus, yielding tighter confidence bounds and more accurate $Q$-estimates, which directly contribute to improved regret and reduced burn-in cost.

Surrogate Reference Functions. We further reduce the burn-in by introducing surrogate reference functions, which address the non-adaptiveness of both the weights and the reference functions in the regret decomposition. This innovation improves the tightness of the analysis and avoids the inefficiencies associated with empirical process techniques used in earlier works.

Together, these contributions enable our algorithm to achieve lower burn-in costs while maintaining strong regret and cost guarantees, marking a significant improvement over FedQ-Advantage.

Question 4: Visualizing the burn-in costs

Thank you for the helpful suggestion. We conducted additional experiments under the two synthetic environments described in Appendix B, denoted by Settings I-II for single-agent RL and III-IV for FRL. To evaluate the burn-in cost of different algorithms, we plot the normalized regret curves $\frac{\text{regret}(t)/\log(t+1)}{\text{regret}(N)/\log(N+2)},$where $N = T/H$ denotes the total number of episodes per agent. By examining these curves, we observe that, our algorithm consistently requires the smaller number of episodes than all baseline methods to achieve the same normalized regret level.

To show the results, we select a set of normalized regret thresholds $\\{0.5,0.8,0.85,0.9,0.95,0.99\\}.$ For each algorithm, we conduct 10 independent trials and report the median number of episodes per agent needed to reach or exceed each threshold. As shown in the following table, our method achieves lower burn-in cost and superior sample efficiency.

Table 4: Median number of episodes per agent required to reach each normalized regret.

(All reference numbers are from our paper.)

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 part 1 and Question 1: The linear dependency on $M$ in the number of communications

Thank you for raising this important point. We also appreciate your mention of the reference [1, Labbi], which we will cite in the revised manuscript.

[1] proposes a model-based online FRL algorithm, Fed-UCBVI, and analyzes its communication cost. For comparison: in worst-case setting, our work provides the bound $O(M\log T)$, and both [1] and our gap-dependent analysis provide the bound $O(M\log\log T)$ under a homogeneous exploration speed assumption. Notably, we can refine our worst-case bound to match this improved communication rate under the same assumption. However, no existing method eliminates the linear dependence on $M$ in general, and the techniques in [1], which share similarities with our gap-dependent analysis, do not overcome this either. We elaborate below.

The linear $M-$dependence in our method arises from the event-triggered termination condition (Eq. 3), where the threshold $c_h^k$ is scaled by $1/M$ to ensure that the total number of visits to a state-action-step triple across all agents is controlled in each round. In our worst-case analysis, we do not assume that the agents explore the environment at the same speed, so that each agent can generate different numbers of episodes in a given round. As such, the uniform threshold $c_h^k$ ensures robustness to heterogeneous agent exploration speeds, but results in a communication bound of $O(M\log T)$.

In contrast, under the homogeneous exploration speed assumption used in both [1] and our gap-dependent analysis, all agents generate the same number of episodes per round. Since they share a common policy, the visits are i.i.d., and the law of large numbers implies that once one agent meets the threshold for a triple, the others are likely close to meeting it as well. In Lemma L.4, we have shown that when the visit count exceeds $i_1=\tilde{\Theta}(M)$, this concentration effect enables a global synchronization that helps remove the $M-$dependency of the number of communication rounds in the late stage with high probability. This reduces the overall $M-$dependency to $O(M\log\log T)$, which is caused by the early stage and remains unavoidable even under this assumption.

In summary, although our method inherits a linear $M$-dependence in communication cost, this is a fundamental limitation shared by most existing FRL algorithms aiming for optimal regret guarantees. We can refine the bound in our worst-case analysis if we assume a homogeneous exploration speed as in [1] and our gap-dependent analysis. However, such an idea cannot remove the linear dependency on $M$ due to the early stage. We also remark that the bound $O(M\log T)$ holds deterministically, but the bound $O(M\log \log T)$ holds with high probability, due to the concentration arguments.

Weakness 1 part 2: The large-scale FRL scenarios

While removing the linear $M$-dependence remains an open problem in general FRL, we note that, in large-scale FRL scenarios (i.e., when $M$ is large), it is possible to remove the $M-$dependency by allowing waiting time, similar to the strategy used in FedQ-Advantage [109].

Specifically, we can modify our algorithms so that each local agent terminates exploration in a round only when it independently triggers the synchronization condition, without relying on signals from other agents. In this situation, each agent, rather than just one in our current algorithm, ensures it collects a sufficient number of new visits in a round for at least one triple before proceeding. This modified design removes the need to coordinate exploration speeds across agents.

We formalize this in the following result that will be added to the revised manuscript:

A New Theorem. For the modified FedQ-EarlySettled-LowCost (Algorithms 1 and 2 with $\beta\in(0,H]$ and the modified synchronization condition), define $\tilde{C} = H^2(H+1)SA$. Then, the number of rounds $K$ is bounded by $4\tilde{C}+ 8\tilde{C} \max\\{\log(T/\tilde{C}),1\\}.$

This new bound eliminates the linear dependence on $M$. This improvement comes at the cost of waiting time, as agents who complete exploration early must wait until slower agents also reach the synchronization condition. For more general scenarios, especially under heterogeneous agent behaviors, further research is required into new synchronization strategies and regret-communication trade-offs.

Weakness 2: The non-homogeneous case

We appreciate the reviewer’s suggestions for possible extensions to the non-homogeneous case. The literature on online FRL discusses two key forms of heterogeneity: (a) Heterogeneous exploration speed, where agents generate different numbers of episodes per round, as discussed in [108, 109] and this paper, and (b) Heterogeneous reward functions and transition kernels across agents, as discussed in Fed-UCBVI. While our current paper addresses (a), we agree that (b) is an important and challenging direction, and we elaborate on it below.

Fed-UCBVI provides theoretical guarantees under heterogeneity (b) by leveraging centralized value functions and Bellman equations. In principle, a similar analysis could be extended to model-free FRL algorithms, including ours. However, the resulting regret bounds for both Fed-UCBVI and hypothetical model-free extensions inevitably lead to the linear dependence on $T$, highlighting a key limitation: none of these methods fully mitigates the bias introduced by heterogeneity (b).

The main technical challenge arises from heterogeneous visiting probabilities for any given $(s,a,h)$ across agents. Even when agents share the same policy, heterogeneous environments result in different numbers of visits across agents. This causes an imbalance in sample contributions across agents, making the standard equal-weight aggregation used for the Q-update in all existing online FRL algorithms inherently biased.

To overcome this issue, a promising direction may involve weighted aggregation schemes based on agent-specific visitation counts, as explored in some offline FRL papers [88, 89]. Adapting such techniques to the online setting could help address the bias introduced by heterogeneity, though doing so would require a careful redesign of both the algorithm and its theoretical analysis. We view this as an important direction for future work.

Question 2: Comparison with model-based method

Thank you for your suggestion and we will include these experiments to the main text.

To address the comparison with model-based methods, we include an evaluation against Fed-UCBVI, the only known online model-based FRL algorithm with near-optimal regret guarantees. We conduct experiments on the same two environments described in Appendix B, with $(H,S,A) = (5,3,2)$ and $(7,10,5)$, using $M=10$ agents. For each method, we report both regret and communication round performance over 10 independent runs, using the same hyperparameter settings for Fed-UCBVI as specified in [1]. The results show that our algorithm achieves consistently lower regret than Fed-UCBVI, while Fed-UCBVI demonstrates lower communication rounds due to its use of transition kernel estimations. In terms of memory, Fed-UCBVI requires $\Theta(S^2)$, while our method requires only $\Theta(S)$, offering a substantial advantage in scalability. We summarize the regret results (rounded to the nearest integer) in two tables below.

Table 1: Median regret at different episode number for $(H,S,A)=(5,3,2)$.

Table 2: Median regret at different episode number for $(H,S,A)=(7,10,5)$.

Question 3: The burn-in cost

Thank you for raising this important point. Theorem 4.3 with $\beta=\Theta(1)$ provides the worst-case regret guarantee of FedQ-EarlySettled-LowCost as $\tilde{O}(\sqrt{MH^2SAT}+H^6SA+MH^5SA)$, where the additional terms $\tilde{O}(H^6SA + MH^5SA)$ lead to the burn-in cost of $\tilde{O}(MSAH^{10})$. Next, we discuss below the nature of the dependencies on $M,S,A,H$.

The linear dependence on $M$ is unavoidable in online FRL because each local agent must explore the environment using suboptimal policies. Such dependency also appears in [1, 108, 109].

The linear dependence on $SA$ is also unavoidable in online RL because the agent must explore the entire environment using suboptimal policies. Our method enjoys a lower burn-in cost than FedQ-Advantage and Fed-UCBVI, both of which show super-linear dependence on $SA$. In fact, this linear dependence is supported by the information lower bound in [102], which shows that even single-agent RL incurs a burn-in cost of $\Theta(H^2SA)$.

The super-linear dependence on $H$ is better than that of FedQ-Advantage, while model-based methods such as Fed-UCBVI exhibit better dependence on $H$ by estimating the transition kernels, but at the cost of higher memory requirements $\Theta(S^2)$ vs. our $\Theta(S)$. Notably, there is room for improving our $H$-dependence by possibly enhancing the Hoeffding-type Q-update (Eq.9 and 13) using more advanced techniques, such as Q-learning with momentum ([2]), which may accelerate reference settling and improve convergence. We view it as a promising direction for future work.

[2] Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. "Ucb momentum q-learning: Correcting the bias without forgetting." ICLR 2021.

(All reference numbers in this response, except for [1] and [2], are from our paper.)

I thank the authors for taking the time to answer my concerns. After the authors' response, I remain positive about this paper.

I appreciate that the authors considered adding additional experiments with model-based methods.

The term "exploration speed" remains quite confusing, and is not defined neither in the authors' manuscript nor in [1]; I would appreciate if the author can give more details on what they mean by this, especially since I don't believe [1] makes any assumption on such type of "exploration speed". In particular, [1] uses a local estimate of the global exploration to decide when communication should happen: based on this local counter and on an adequate "doubling trick", number of communication can be reduced by a factor $M$. Isn't the same idea possible to apply here?

Regarding the non-homogeneous case, I agree that all existing results exhibit a regret that scales linearly in T when agents are not homogeneous. Nonetheless, these results prove that the method works in slightly heterogeneous settings, up to a small additional error: in the results presented in the current manuscript, no such analysis is proposed, and this is an important limitation in the paper, since heterogeneity is one of the key factors of federated learning.

Thank you again for the thoughtful follow-up. Below, we provide the second part of our response.

On the "Doubling Trick"

For definitions that are shared between [1] and our work, we adopt our notation instead of that used in [1], in order to maintain consistency with the submission. Let $n_h^{m,k}(s,a)$ denote the number of visits to the state-action-step triple $(s, a, h)$ by agent $m$ in round $k$, and define the global visit count to $(s, a, h)$ prior to round $k$ as $N_h^k(s,a) = \sum_{r=1}^{k-1} \sum_{m=1}^{M} n_h^{m,r}(s,a).$

In [1], for agent $m$, a local estimate $\hat{N}\_{(k,t),h}^m(s,a)$ of the global visit count is maintained during the $t$-th episode of round $k$. A synchronization signal is sent when this local estimate exceeds twice the global count prior to round $k$, i.e., $\hat{N}\_{(k,t),h}^m(s,a) > 2 N_h^k(s,a).\quad(1)$ According to the design in Algorithm 1 of [1], when agent $m$ sends the synchronization signal in the $t$-th episode of round $k$, it holds that $\hat{N}\_{(k,t),h}^m(s,a)=N_h^k(s,a) + Mn_h^{m,k}(s,a).$ Substituting this into the synchronization condition (1) yields: $N_h^k(s,a)+Mn_h^{m,k}(s,a)>2N_h^k(s,a),$ which is equivalent to $n_h^{m,k}(s,a)>\frac{1}{M}N_h^k(s,a).$ This means in [1], agent $m$ send the synchronization signal if $n_h^{m,k}(s,a)>\frac{1}{M}N_h^k(s,a).$ Our method adopts a similar idea but uses a more conservative threshold. Specifically, in round $k$, agent $m$ sends a synchronization signal if $n_h^{m,k}(s,a)\geq\frac{1}{MH(H+1)}N_h^k(s,a).\quad(2)$ While the doubling trick is commonly used in model-based settings like [1,6], model-free approaches, including ours and [2,3,7], must use a more conservative rate of $\frac{1}{MH(H+1)}$ due to the lack of transition kernel estimates under the model-free framework.

Furthermore, under the homogeneous exploration speed assumption (used in both [1] and our gap-dependent analysis), our worst-case analysis can also eliminate the $M \log T$ dependency. Since all agents share a common policy in each round, their visits to each state-action-step triple are i.i.d.. By the law of large numbers, once one agent meets the synchronization threshold for a given triple, the others are likely to be close as well. This phenomenon is theoretically established in Lemma L.4 (line 1396), where we show that for any triple satisfying the synchronization condition (Equation (2)) in round $k$, once the visit count prior to round $k$ exceeds $i_1 \tilde{\Theta}(M)$, the total number of visits will subsequently grow at a rate of $\Omega\left(\frac{1}{H(H+1)}\right)$—a rate that is independent of $M$. As a result, the overall $M$-dependency is reduced to $O(M\log\log T)$, which arises from the early stage when the visit count is still below $i_1$ and remains unavoidable even under this assumption. We will include these discussions in the revised manuscript.

On the Non-Homogeneous Case

Our work focuses on addressing system heterogeneity, a core challenge in federated learning highlighted in [5]. As discussed in [5], this type of heterogeneity arises from variations in system characteristics across the network. Devices can differ widely in terms of hardware capabilities, network connectivity, and energy constraints, which often leads to issues such as stragglers and partial participation. Our algorithm is designed to handle such heterogeneity without incurring any additional error that grows linearly with $T$, ensuring robustness in real-world federated environments.

In contrast, [1] focuses primarily on statistical heterogeneity, which refers to highly non-identically distributed data across agents (as also noted in [5]). We agree this is an important challenge. While our current analysis does not cover this form of heterogeneity, extending our framework to such settings is a key direction for future work. We will add this discussion to the revised manuscript.

[1] Labbi, S., Tiapkin, D., Mancini, L., Mangold, P., and Moulines, E. (2024). Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents. arXiv preprint arXiv:2410.22908.

[2] Zheng, Z., Gao, F., Xue, L., and Yang, J. Federated Q-learning: Linear regret speedup with low communication cost. ICLR, 2024.

[3] Zheng, Z., Zhang, H., and Xue, L. Federated Q-learning with reference advantage decomposition: Almost optimal regret and logarithmic communication cost. ICLR, 2025.

[4] Zhang, H., Zheng, Z., and Xue, L. Gap-Dependent Bounds for Federated Q-Learning. ICML, 2025

[5] Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine 37, no. 3 (2020): 50-60.

[6] Zhang, H., Chen, Y., Lee, J. D., and Du, S. S. Settling the sample complexity of online reinforcement learning. COLT, 2024.

[7] Bai, Y., Xie, T., Jiang, N., and Wang, Y.-X. Provably efficient q-learning with low switching cost. NeurIPS, 2019.

Thank you for the thoughtful follow-up. We provide the first part of our responses to each point below.

Clarifying “Exploration Speed"

In our initial response, exploration speed refers to the number of episodes generated by each agent per round, which may vary across agents.

In our worst-case analysis, we denote the number of episodes generated by agent $m$ in round $k$ as $n^{m,k}$, and $n^{m,k}$ can vary across agents. Our algorithm proceeds in rounds, and each round terminates when the synchronization condition (Equation (3) in our work) is met for one agent. This setup eliminates waiting time for each agent and imposes no constraints on the number of episodes generated per agent, thereby allowing heterogeneous exploration speeds across agents.

Accordingly, our regret is defined as:

where $s_1^{m,k,t}$ denotes the initial state of agent $m$ in $t$-th episode of round $k$, and $\pi_{k,t}$ is the policy executed in that episode. This formulation naturally accommodates heterogeneous exploration speeds.

In contrast, [1] assumes that all agents generate the same number of episodes in each round—an assumption that, although not explicitly stated, is reflected in both the algorithm design and the regret formulation. [1] uses a global episode index $t \in [T]$ in the Algorithm 1, which implicitly assumes that, without any waiting time, all agents are synchronized at the same episode and generate the same number of episodes in each round. The assumption is also implied by its regret definition (see Eq. 4 of [1]):

$\text{Regret}(T) = \sum_{m=1}^{M} \sum_{t=1}^{T} \left(V_1^{\star}(s_1^{m,t}) - V_1^{\pi_t}(s_1^{m,t})\right),$

with homogeneous transition kernels and reward functions, where $s_1^{m,t}$ is the initial state of agent $m$ in episode $t$, and $\pi_t$ is the policy executed in episode $t$. This expression further implies that each agent generates $T$ episodes during the learning process, whereas our work does not make such an assumption and is closer to the spirit of first two online FRL works [2,3].

We will revise the manuscript to distinguish between homogeneous and heterogeneous exploration speed settings more clearly, relate it to existing literature: [2, 3] and our work allow heterogeneous exploration speeds, while [1, 4] focus on the homogeneous exploration speed setting to improve communication efficiency.

Moreover, in our work, the homogeneous exploration speed assumption is only used in the gap-dependent analysis and implies that all agents generate the same number of episodes per round. We formally refer to this as the full synchronization assumption, which is described in detail in Appendix L (line 1335) of the original submission. Specifically, under this assumption, the number of episodes generated by agent $m$ in round $k$ satisfies $n^{m,k} = n^k$, meaning the episode count is independent of the agent index $m$. Both [1] and our gap-dependent analysis leverage this assumption to eliminate the $O(M \log T)$ communication overhead, reducing it to an $O(M \log\log T)$ term and matching the optimal rate.

Thank you for your response and for sharing your perspective. We will revise the manuscript to include a more explicit discussion to help readers better understand the setting related to exploration speed.

We would also like to take this opportunity to clarify several key points regarding your concerns. Our response is structured into three parts.

Regarding the rescaling approach

Our work indeed adopts a similar idea, where the central server aggregates local means to update the $Q$-function. However, as noted in our initial response to Weakness 1, without the assumption of homogeneous exploration speed, applying such rescaling leads to a communication cost with an $O(M\log T)$ dependence. This highlights a trade-off between exploration heterogeneity and communication efficiency.

Regarding the heterogeneity

Our main focus is on addressing two central challenges in online federated RL: achieving low policy switching cost and low burn-in cost. These challenges are critical for improving learning efficiency and scalability and represent an important and underexplored gap in current research.

We fully agree that statistical heterogeneity is another meaningful and realistic challenge in federated learning. Extending our framework to handle both statistical and system-level heterogeneity is a promising direction for future work, and we appreciate this valuable suggestion.