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

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 Õ(√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.