The Sample-Communication Complexity Trade-off in Federated Q-Learning

Autor:	Salgia, Sudeep, Chi, Yuejie
Rok vydání:	2024
Předmět:	Computer Science - Machine Learning Mathematics - Optimization and Control Statistics - Machine Learning
Druh dokumentu:	Working Paper
Popis:	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. Comment: Accepted to NeurIPS 2024
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2408.16981 Zobrazit plný text záznamu View this record from Arxiv