Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost

2024-05-29 · Zhong Zheng, Haochen Zhang, Lingzhou Xue

In this paper, we consider model-free federated reinforcement learning for tabular episodic Markov decision processes. Under the coordination of a central server, multiple agents collaboratively explore the environment and learn an optimal policy without sharing their raw data. Despite recent advances in federated Q-learning algorithms achieving near-linear regret speedup with low communication cost, existing algorithms only attain suboptimal regrets compared to the information bound. We propose a novel model-free federated Q-learning algorithm, termed FedQ-Advantage. Our algorithm leverages reference-advantage decomposition for variance reduction and operates under two distinct mechanisms: synchronization between the agents and the server, and policy update, both triggered by events. We prove that our algorithm not only requires a lower logarithmic communication cost but also achieves an almost optimal regret, reaching the information bound up to a logarithmic factor and near-linear regret speedup compared to its single-agent counterpart when the time horizon is sufficiently large.

📄 PDF Abstract BibTeX arXiv:2405.18795

Code (0)

등록된 구현이 없습니다.

Tasks

Q-Learning

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition

2024-10-10 · Zhong Zheng, Haochen Zhang, Lingzhou Xue

We study the gap-dependent bounds of two important algorithms for on-policy Q-learning for finite-horizon episodic tabular Markov Decision Processes (MDPs): UCB-Advantage (Zhang et al. 2020) and Q-EarlySettled-Advantage …

Q-Learning

Almost Optimal Model-Free Reinforcement Learningvia Reference-Advantage Decomposition

2020-12-01 · NeurIPS 2020 12 · Zihan Zhang, Yuan Zhou, Xiangyang Ji

We study the reinforcement learning problem in the setting of finite-horizon1episodic Markov Decision Processes (MDPs) with S states, A actions, and episode length H. We propose a model-free algorithm UCB-ADVAN…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition

2020-04-21 · Zihan Zhang, Yuan Zhou, Xiangyang Ji

We study the reinforcement learning problem in the setting of finite-horizon episodic Markov Decision Processes (MDPs) with $S$ states, $A$ actions, and episode length $H$. We propose a model-free algorithm UCB-Advantage…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Federated Best Arm Identification with Heterogeneous Clients

2022-10-14 · Zhirui Chen, P. N. Karthik, Vincent Y. F. Tan, Yeow Meng Chee

We study best arm identification in a federated multi-armed bandit setting with a central server and multiple clients, when each client has access to a {\em subset} of arms and each arm yields independent Gaussian observ…

Comparative assessment of federated and centralized machine learning

2022-02-03 · Ibrahim Abdul Majeed, Sagar Kaushik, Aniruddha Bardhan, Venkata Siva Kumar Tadi 외

Federated Learning (FL) is a privacy preserving machine learning scheme, where training happens with data federated across devices and not leaving them to sustain user privacy. This is ensured by making the untrained or …

BIG-bench Machine Learning Federated Learning Privacy Preserving