Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost

arXiv:2609.00193 · stat.ML, cs.AI, cs.LG · Submitted 2026-08-31 · Read on arXiv

stat.ML, cs.AI, cs.LG

Submitted: 2026-08-31

Updated: 2026-08-31

Terminology

• Regret — 59× in this paper · explained in 3 episodes
• Reinforcement Learning — 44× in this paper · explained in 4 episodes
• Q-learning — 13× in this paper · explained in 3 episodes
• Sample Complexity — 4× in this paper · explained in 15 episodes
• Communication Overhead — 3× in this paper · explained in 2 episodes
• Federated Learning — 3× in this paper · explained in 15 episodes
• Online Reinforcement Learning — 3× in this paper · explained in 2 episodes
• Regularization — 3× in this paper · explained in 3 episodes
• Action Space — 2× in this paper · explained in 1 episode
• Actor — 2× in this paper · explained in 3 episodes
• Adaptivity — 2× in this paper · explained in 1 episode
• EMMA — 2× in this paper · explained in 2 episodes
• Convergence Guarantees — 1× in this paper · explained in 3 episodes
• Core — 1× in this paper · explained in 2 episodes
• Federated Learning (FL) — 1× in this paper · explained in 7 episodes
• Generative Model — 1× in this paper · explained in 2 episodes
• Markov Decision Process (MDP) — 1× in this paper · explained in 11 episodes
• Minimax Regret — 1× in this paper · explained in 2 episodes
• Mobile Edge Computing — 1× in this paper · explained in 2 episodes
• Multi-Agent Reinforcement Learning (MARL) — 1× in this paper · explained in 4 episodes
• Reinforcement Learning (RL) — 1× in this paper · explained in 25 episodes
• Reward Function — 1× in this paper · explained in 2 episodes
• Sample Efficiency — 1× in this paper · explained in 4 episodes
• Theoretical Guarantees — 1× in this paper · explained in 2 episodes

Sources

• Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Sampling
• Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximation
• Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation

Related papers

• Behavior of prediction performance metrics with rare events
• Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
• A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
• Efficient quadratic entropy with distance sketches
• Embedding-Bias in Conditional Independence Testing
• From Log-Odds to Shapley Values: An Explanatory Geometry for the Weighted Naive Bayes Classifier