首次给出联邦Q学习的间隙依赖分析，显著降低通信开销。
Gap-Dependent Bounds for Federated $Q$-learning
- 基于马尔可夫决策过程的间隙结构设计新算法
- 实现对数型后悔上界，通信成本不再依赖状态动作数积
- 适合多智能体强化学习中关注效率的场景
我们首次对表格式、分段有限时域马尔可夫决策过程中的在线联邦Q学习，给出了间隙依赖的后悔与通信代价分析。现有联邦强化学习方法聚焦最坏情况，导致后悔与通信代价均含√T与log T项，且受智能体数M、状态数S、动作数A影响。本文新框架利用MDP的良性结构（如严格正的次优性间隙），获得对数型后悔上界，并解耦探索与利用的通信成本。间隙依赖的后悔上界揭示了多智能体特有的加速模式；通信代价上界中，log T项不再依赖MSA。尤其当M=1时，全局切换代价的log T项也移除了SA因子。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。