mlsanityData to 7 Oct 2026

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

arXiv 2410.22908 ↗First posted 30 Oct 2024cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

In this paper, we present the Federated Upper Confidence Bound Value Iteration algorithm (textttFed-UCBVI), a novel extension of the textttUCBVI algorithm (Azar et al., 2017) tailored for the federated learning framework. We prove that the regret of textttFed-UCBVI scales as tildeO(√H3 |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, textttFed-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, textttFed-UCBVI's communication complexity only marginally increases with the number of agents.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 20 of its 25 references that are in the map. First posted on arXiv 30 Oct 2024.

Builds on

20 of 25 references.

References · 20

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  6. 2021Federated Reinforcement Learning: Techniques, Applications, and Open Challengescited by 79
  7. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  8. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 61
  9. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  10. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  11. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  12. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
8 more
  1. 2019Federated Deep Reinforcement Learningcited by 34
  2. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  3. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  4. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  5. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
  6. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  7. 2024Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Costcited by 9
  8. 2024On the Convergence Rates of Federated Q-Learning across Heterogeneous Environmentscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 1.

5 papers.

  1. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  2. 2025Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agentscited by 2
  3. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  4. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  5. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0