Achieving Tighter Finite-time Rates For Heterogeneous Federated Stochastic Approximation Under Markovian Sampling

Abstract

Motivated by collaborative reinforcement learning (RL) and optimization with time-correlated data, we study a generic federated stochastic approximation problem involving \(M\) agents, where each agent is characterized by an agent-specific (potentially nonlinear) local operator. The goal is for the agents to communicate intermittently via a server to find the root of the average of the agents' local operators. The generality of our setting stems from allowing for (i) Markovian data at each agent and (ii) heterogeneity in the roots of the agents' local operators. The limited recent work that has accounted for both these features in a federated setting fails to guarantee convergence to the desired point or to show any benefit of collaboration; furthermore, they rely on projection steps in their algorithms to guarantee bounded iterates. Our work overcomes each of these limitations. We develop a novel algorithm titled \texttt\{FedHSA\}, and prove that it guarantees convergence to the corre

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzhu2025achieving

Related papers

• Federated Stochastic Approximation Under Markov Noise And Heterogeneity: Applications In Reinforcement Learning (2022)0.00
• Local Stochastic Approximation: A Unified View Of Federated Learning And Distributed Multi-task Reinforcement Learning Algorithms (2020)0.00
• Finite-time Analysis Of On-policy Heterogeneous Federated Reinforcement Learning (2024)0.00
• Stochastic Approximation With Delayed Updates: Finite-time Rates Under Markovian Sampling (2024)0.00
• The Blessing Of Heterogeneity In Federated Q-learning: Linear Speedup And Beyond (2023)0.00
• Momentum For The Win: Collaborative Federated Reinforcement Learning Across Heterogeneous Environments (2024)0.00
• Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis (2025)0.00
• Federated TD Learning Over Finite-rate Erasure Channels: Linear Speedup Under Markovian Sampling (2023)0.00