联邦强化学习新算法，通信少、收敛快，适配不同设备。
Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents
- 基于上置信界值迭代，设计可跨设备协同的联邦强化学习算法。
- 理论证明其累积损失随智能体数线性下降，且在单智能体时逼近最优上限。
- 通信开销几乎不随智能体增加而上升，适合资源受限的分布式场景。
本文提出联邦上置信界值迭代算法（Fed-UCBVI），是针对联邦学习框架对UCBVI算法的新扩展。我们证明了该算法的累积遗憾上界为$ ilde{ ext{O}}( oot{3}{H^3 | ext{S}| | ext{A}| T / M})$，其中包含由异构性带来的微小额外项。当仅有一个智能体时，该上界与最小最大下界仅差多对数因子；在多智能体情形下，算法实现线性加速。为分析该结果，我们引入一种新的异构性度量，可能具有独立理论价值。此外，与现有联邦强化学习方法不同，Fed-UCBVI的通信复杂度随智能体数量增长极为缓慢。
原文摘要 · Abstract (English)
In this paper, we present the Federated Upper Confidence Bound Value Iteration algorithm ($\texttt{Fed-UCBVI}$), a novel extension of the $\texttt{UCBVI}$ algorithm (Azar et al., 2017) tailored for the federated learning framework. We prove that the regret of $\texttt{Fed-UCBVI}$ scales as $\tilde{\mathcal{O}}(\sqrt{H^3 |\mathcal{S}| |\mathcal{A}| T / M})$, with a small additional term due to heterogeneity, where $|\mathcal{S}|$ is the number of states, $|\mathcal{A}|$ is the number of actions, $H$ is the episode length, $M$ is the number of agents, and $T$ is the number of episodes. Notably, in the single-agent setting, this upper bound matches the minimax lower bound up to polylogarithmic factors, while in the multi-agent scenario, $\texttt{Fed-UCBVI}$ has linear speed-up. To conduct our analysis, we introduce a new measure of heterogeneity, which may hold independent theoretical interest. Furthermore, we show that, unlike existing federated reinforcement learning approaches, $\texttt{Fed-UCBVI}$'s communication complexity only marginally increases with the number of agents.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。