Gap-Dependent Regret for Federated Q-Learning

open_access
Open Access
Author:
Zhang, Haochen
Graduate Program:
Statistics
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
July 07, 2025
Committee Members:
Lingzhou Xue, Thesis Advisor/Co-Advisor
Bing Li, Committee Member
Runze Li, Professor in Charge/Director of Graduate Studies
Keywords:
Reinforcement Learning
Federated Learning
Regret
Abstract:
Federated Reinforcement Learning (FRL) is a distributed learning paradigm where multiple agents collaboratively learn a shared policy while keeping their raw data locally, thus preserving privacy and reducing communication cost. This framework is particularly relevant in real-world applications such as autonomous driving and healthcare, where distributed agents operate in similar or the same environments but face privacy and bandwidth constraints. Regret analysis is a crucial topic in FRL because it quantifies the cumulative performance gap between the learning policy and the optimal policy, serving as a key measure of learning efficiency. In federated settings, where agents interact with different instances of the same environment, minimizing regret ensures that the collaborative learning process does not sacrifice individual agent performance. Existing FRL methods focus on worst-case scenarios, leading to $\sqrt{T}$-type regret bounds, where T is the average total number of steps per agent. However, in practice, FRL algorithms often perform better than their worst-case guarantees, as they can be significantly improved under Markov decision processes (MDPs) with benign structures, such as strictly positive suboptimality gaps. This motivates the problem-dependent analysis exploiting benign MDPs. In this work, we present the first gap-dependent analysis of regret for on-policy federated Q-Learning in tabular episodic finite-horizon MDPs. By explicitly incorporating the positive suboptimality gaps of MDPs into our theoretical framework, we establish a significantly improved regret bound of order $\log T$. Our gap-dependent regret bound also reveals a distinct multi-agent speedup pattern in terms of the average regret, which will be shown in the numerical experiments chapter.