Research map / Reinforcement learning / MDPs and planning
Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces FedSARSA, a federated on-policy SARSA with linear function approximation for heterogeneous agent MDPs, and gives finite-time analysis showing near-optimality proportional to heterogeneity and linear speedup in the number of agents.
Problem
Federated reinforcement learning with heterogeneous environments (differing rewards and transitions) under on-policy, Markovian sampling, linear function approximation, and local updates; lacks non-asymptotic guarantees.
Approach
Federated SARSA with linear function approximation and periodic averaging, analyzed via a central MDP, perturbation bounds on nonlinear projected Bellman fixed points, and virtual backtracking to handle nonstationary on-policy trajectories; yields linear speedup in number of agents and a convergence region radius O(epsilon_p + epsilon_r).
Key results
- Under decaying step-size, the finite-time error scales as O(1/(NT)) plus Lambda^2/(1-gamma)^2 heterogeneity term, giving linear speedup in number of agents N.
- With constant step-size, FedSARSA converges exponentially to a ball whose radius is O(epsilon_p + epsilon_r) around each agent's optimal parameter.
- Simulations show MSE increases with heterogeneity levels and decreases with more agents, consistent with theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| federate SARSA updates across N agents instead of using single-agent SARSA | FedSARSA in homogeneous environments · heterogeneous federated reinforcement learning | finite-time mean squared error: O(1/T) -> O(1/(NT)) | Helped |
Surprising findings
- Simulations suggest the algorithm is more sensitive to reward heterogeneity than kernel heterogeneity.
Limitations
- Requires Lipschitz continuous policy improvement operator with small constant L, excluding greedy policies used in Q-learning.
- Convergence region radius O(epsilon_p + epsilon_r) cannot be eliminated under heterogeneity.
- Experiments are limited to small synthetic MDPs.
Experimental setup
Datasets: synthetic MDPs (100 states, 100 actions, d=25)
Benchmarks: synthetic heterogeneous MDP simulations
Metrics: mean squared error to reference parameter
Baselines: federated TD(0) federated Q-learning single-agent linear SARSA
Builds on: SARSA FedAvg TD(0) finite-time analysis federated TD learning
Closest papers by meaning
- Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis (ICLR 2025 · similarity 0.93)
- Single-Loop Federated Actor-Critic across Heterogeneous Environments (AAAI 2025 · similarity 0.92)
- Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments (ICML 2024 · similarity 0.92)
- Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices (ICML 2024 · similarity 0.91)
- Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning (NeurIPS 2024 · similarity 0.91)
- Federated Q-Learning: Linear Regret Speedup with Low Communication Cost (ICLR 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.