Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents

2024/10/30 by Labbi, Safwan, Tiapkin, Daniil, Mancini, Lorenzo +2 · 2 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2410.22908

Abstract

In this paper, we present the Federated Upper Confidence Bound Value Iteration algorithm (Fed-UCBVI), a novel extension of the UCBVI algorithm (Azar et al., 2017) tailored for the federated learning framework. We prove that the regret of Fed-UCBVI scales as O(√(H³ |S| |A| T / M)), with a small additional term due to heterogeneity, where |S| is the number of states, |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, 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, Fed-UCBVI's communication complexity only marginally increases with the number of agents.

Cited by

• Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents
• Q-Learning with Fine-Grained Gap-Dependent Regret

Related

• Federated Q-Learning: Linear Regret Speedup with Low Communication Cost
• Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning
• Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost
• Federated Multi-Armed Bandits
• Towards Fast Rates for Federated and Multi-Task Reinforcement Learning