The Sample-Communication Complexity Trade-off in Federated Q-Learning
<|reference_start|>The Sample-Communication Complexity Trade-off in Federated Q-Learning: We consider the problem of federated Q-learning, where $M$ agents aim to collaboratively learn the optimal Q-function of an unknown infinite-horizon Markov decision process with finite state and action spaces. We investigate the trade-off between sample and communication complexities for the widely used class of intermittent communication algorithms. We first establish the converse result, where it is shown that a federated Q-learning algorithm that offers any speedup with respect to the number of agents in the per-agent sample complexity needs to incur a communication cost of at least an order of $\frac{1}{1-\gamma}$ up to logarithmic factors, where $\gamma$ is the discount factor. We also propose a new algorithm, called Fed-DVR-Q, which is the first federated Q-learning algorithm to simultaneously achieve order-optimal sample and communication complexities. Thus, together these results provide a complete characterization of the sample-communication complexity trade-off in federated Q-learning.<|reference_end|>
@article{salgia2024the,
    title={The Sample-Communication Complexity Trade-off in Federated Q-Learning},
    author={Sudeep Salgia and Yuejie Chi},
    journal={arXiv preprint arXiv:2408.16981},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.16981},
    primaryClass={cs.LG math.OC stat.ML}
}