Gap-Dependent Bounds for Federated $Q$-learning
We present the first gap-dependent analysis of regret and communication cost for on-policy federated $Q$-Learning in tabular episodic finite-horizon Markov decision processes (MDPs). Existing FRL methods focus on worst-case scenarios, leading to $\sqrt{T}$-type regret bounds and communication cost bounds with a $\log T$ term scaling with the number of agents $M$, states $S$, and actions $A$, where $T$ is the average total number of steps per agent. In contrast, our novel framework leverages the benign structures of MDPs, such as a strictly positive suboptimality gap, to achieve a $\log T$-type regret bound and a refined communication cost bound that disentangles exploration and exploitation. Our gap-dependent regret bound reveals a distinct multi-agent speedup pattern, and our gap-dependent communication cost bound removes the dependence on $MSA$ from the $\log T$ term. Notably, our gap-dependent communication cost bound also yields a better global switching cost when $M=1$, removing $SA$ from the $\log T$ term.
Code (0)
등록된 구현이 없습니다.
Tasks
Q-LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
On the Necessity of Collaboration for Online Model Selection with Decentralized Data
We consider online model selection with decentralized data over $M$ clients, and study the necessity of collaboration among clients. Previous work proposed various federated algorithms without demonstrating their necessi…
Model SelectionOptimal Federated Learning for Functional Mean Estimation under Heterogeneous Privacy Constraints
Federated learning (FL) is a distributed machine learning technique designed to preserve data privacy and security, and it has gained significant importance due to its broad range of applications. This paper addresses th…
Federated LearningPrivacy PreservingGeneralization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels
Machine learning models trained by different optimization algorithms under different data distributions can exhibit distinct generalization behaviors. In this paper, we analyze the generalization of models trained by noi…
Federated LearningGeneralization BoundsLearning TheoryMinimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles
In this paper, our aim is to analyse the generalization capabilities of first-order methods for statistical learning in multiple, different yet related, scenarios including supervised learning, transfer learning, robust …
Federated Learningparameter estimationQuantizationTransfer LearningImproved Information Theoretic Generalization Bounds for Distributed and Federated Learning
We consider information-theoretic bounds on expected generalization error for statistical learning problems in a networked setting. In this setting, there are $K$ nodes, each with its own independent dataset, and the mod…
Federated LearningGeneralization Bounds