"Federated Reinforcement Learning: Statistical and Communication Trade-offs
summary
Analyzes federated Q-learning with rigorous sample and communication bounds: single-agent Q-learning needs roughly |S||A|(1/(1−γ))^4 / ε^2 samples; running K agents with periodic averaging yields near linear speedup with sample complexity ~|S||A|(1/(1−γ))^5 /(K ε^2) under a generative model and tuned learning/communication schedules. Proves a communication lower bound of about Ω(1/(1−γ)) rounds to gain any speedup, gives variance-reduced + compressed algorithms that match sample and communication rates, and shows importance-weighted averaging recovers centralized rates under heterogeneous behavior policies.
AI-written summary · about
chapters (8)
- 0:00Introduction and motivation
- 0:35Federated RL foundations
- 7:20MDP and Q-learning basics
- 17:25Federated Q-learning speedups
- 21:15Communication complexities
- 26:15Optimal algorithm design
- 27:04Handling data heterogeneity
- 39:19Summary and future outlook
related talks
15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control
45mTutorial: Incentives for Collaborative Learning and Data Sharing, Part I
11mData Efficient Methods for Reinforcement Learning
31mQ-learning with Uniformly Bounded Variance
56mA Tutorial on Reinforcement Learning II
31mOn the Complexity of Learning Good Policies With and Without Rewards
42mReinforcement Learning using Generative Models for Continuous State and Action Space Systems
33mDistributed Learning, Communication Complexity, and Privacy