Summary
This paper investigates the sample and communication complexities of federated Q-learning with intermittent central aggregation of the Q-value function.
The authors demonstrate that to achieve any speedup in sample complexity through federated collaboration, the communication complexity must be at least $\Omega(1 /(1-\gamma ))$.
Additionally, the paper introduces a novel federated Q-learning algorithm incorporating variance reduction and minibatching techniques, achieving order-optimal sample and communication complexities.
Strengths
- This paper considers the important trade-off problem between sample complexity speedup and communication cost in federated reinforcement learning. It provides a complete characterization of this trade-off in federated Q-learning, including the communication cost in bits.
- Not only do the authors provide a complete characterization of the sample-communication trade-off and design a novel federated Q-learning algorithm that achieves order-optimal sample and communication complexities, but they also provide insights and intuitions into how infrequent communication fails to speed up sample complexity, and how their algorithm balances this trade-off.
Weaknesses
- Several papers report that a _one-shot_ average is sufficient to achieve linear speedups in federated reinforcement learning (FedRL) [1,2]. This seems to contrast starkly with the authors' claim that infrequent communication does not speed up sample complexity. Could the authors clarify this discrepancy and discuss how their work relates to these results?
- The related work section on Distributed RL is generally comprehensive; however, it omits some recent works on heterogeneous FedRL [3,4].
- There is a lack of discussion on the technical difficulties and novelties of the proposed approach. The authors mentioned that Theorem 1 is inspired **by** the analysis of single-agent Q-learning [5] and Theorem 2 is based on the analysis of variance-reduced Q-learning [6]. The authors should elaborate on how their analysis differs from the single-agent case, what new challenges arise in the federated setting, and what novel techniques are employed to overcome these challenges. Additionally, can these techniques be generalized to other settings?
- In Eq. (7), should $\widehat{\mathcal{T}}$ be $\mathcal{T}$? Otherwise it is not defined.
Overall, I am satisfied with the paper, with the first point being my primary concern. I would be happy to raise my score if the authors provide satisfactory clarifications on the above points.
### References
[1] Liu, R., & Olshevsky, A. (2023). Distributed TD (0) with almost no communication. _IEEE Control Systems Letters_, _7_, 2892-2897.
[2] Tian, H., Paschalidis, I. C., & Olshevsky, A. (2024). One-Shot Averaging for Distributed TD (λ) Under Markov Sampling. _IEEE Control Systems Letters_.
[3] Xie, Z., & Song, S. (2023). FedKL: Tackling data heterogeneity in federated reinforcement learning by penalizing KL divergence. _IEEE Journal on Selected Areas in Communications_, _41_(4), 1227-1242.
[4] Zhang, C., Wang, H., Mitra, A., & Anderson, J. (2024). Finite-time analysis of on-policy heterogeneous federated reinforcement learning. In _International Conference on Learning Representations_. PMLR.
[5] Li, G., Cai, C., Chen, Y., Wei, Y., & Chi, Y. (2024). Is Q-learning minimax optimal? a tight sample complexity analysis. _Operations Research_, _72_(1), 222-236.
[6] Wainwright, M. J. (2019). Variance-reduced $ Q $-learning is minimax optimal. _arXiv preprint arXiv:1906.04697_.
Questions
- While I understand that the authors focus on homogeneous i.i.d. data to highlight the main ideas, could the authors comment on the difficulty of generalizing their results to the asynchronous sampling setting? Specifically, the authors mention that the lower bound applies to the asynchronous setting. A similar remark on Theorem 2 would be helpful.
Please see Section Weaknesses for other questions.