Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents

• URL: http://arxiv.org/abs/2512.17688v1
• Date: Fri, 19 Dec 2025 15:23:44 GMT
• Title: Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents
• Abstract summary: We present a novel theoretical analysis of Federated SARSA (FedSARSA) with linear function approximation and local training.<n>We establish convergence guarantees for FedSARSA in the presence of heterogeneity, both in local transitions and rewards.<n>We show that FedSARSA achieves linear speed-up with respect to the number of agents, up to higher-order terms due to Markovian sampling.
• Score: 25.68297036299815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel theoretical analysis of Federated SARSA (FedSARSA) with linear function approximation and local training. We establish convergence guarantees for FedSARSA in the presence of heterogeneity, both in local transitions and rewards, providing the first sample and communication complexity bounds in this setting. At the core of our analysis is a new, exact multi-step error expansion for single-agent SARSA, which is of independent interest. Our analysis precisely quantifies the impact of heterogeneity, demonstrating the convergence of FedSARSA with multiple local updates. Crucially, we show that FedSARSA achieves linear speed-up with respect to the number of agents, up to higher-order terms due to Markovian sampling. Numerical experiments support our theoretical findings.

Related papers

• From Sparse Features to Trustworthy Proxies: Certifying SAE-Based Interpretability [53.681678236115836]
  We study when can an SAE-based explanation be treated as a faithful view of an underlying frozen LM.<n>Our framework derives an upper bound on the base model's expected risk using four measurable quantities.<n>We show that the bound becomes non-vacuous on GPT-2 Small, Gemma-2B, and Llama-3-8B at practical sample sizes.
  arXiv  Detail & Related papers  (2026-06-16T18:28:23Z)
• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Theoretical Convergence of SMOTE-Generated Samples [47.26889442476884]
  We provide a rigorous theoretical analysis of SMOTE's convergence properties.<n>We prove that the synthetic random variable Z converges in probability to the underlying random variable X.<n>Lower values of the nearest neighbor rank lead to faster convergence.
  arXiv  Detail & Related papers  (2026-01-05T09:19:45Z)
• Stratified GRPO: Handling Structural Heterogeneity in Reinforcement Learning of LLM Search Agents [90.45197506653341]
  Large language model (LLM) agents increasingly rely on external tools such as search engines to solve complex, multi-step problems.<n>The trajectories of search agents are structurally heterogeneous, where variations in the number, placement, and outcomes of search calls lead to fundamentally different answer directions and reward distributions.<n>Standard policy gradient methods, which use a single global baseline, suffer from what we identify and formalize as cross-stratum bias.<n>We propose Stratified GRPO, whose central component, Stratified Advantage Normalization (SAN), partitions trajectories into homogeneous strata based on their structural properties and computes advantages locally within each
  arXiv  Detail & Related papers  (2025-10-07T17:59:13Z)
• Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling [6.549288471493216]
  We study a generic federated approximation problem involving $M$ agents.<n>The goal is for the agents to communicate intermittently via a server to find the root of the average of the agents' local operators.<n>We develop a novel algorithm titled texttFedHSA, and prove that it guarantees convergence to the correct point.
  arXiv  Detail & Related papers  (2025-04-15T22:13:55Z)
• Single-Loop Federated Actor-Critic across Heterogeneous Environments [9.276123988094698]
  We study textitSingle-loop Federated Actor Critic (SFAC) where agents perform actor-critic learning in a two-level federated manner.<n>We show that the convergence error of SFAC converges to a near-stationary point, with the extent proportional to environment.
  arXiv  Detail & Related papers  (2024-12-19T06:13:59Z)
• Broadening Target Distributions for Accelerated Diffusion Models via a Novel Analysis Approach [49.97755400231656]
  We show that a new accelerated DDPM sampler achieves accelerated performance for three broad distribution classes not considered before.<n>Our results show an improved dependency on the data dimension $d$ among accelerated DDPM type samplers.
  arXiv  Detail & Related papers  (2024-02-21T16:11:47Z)
• SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning [14.663513734368628]
  We show that the communication complexity of FedLSA scales with the inverse of the desired accuracy. An important finding is that, compared to the existing results for Scaffnew, the sample complexity scales with the inverse of the number of agents.
  arXiv  Detail & Related papers  (2024-02-06T16:06:59Z)
• Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning [8.632943870358627]
  Federated reinforcement learning (FRL) has emerged as a promising paradigm for reducing the sample complexity of reinforcement learning tasks. We introduce FedSARSA, a novel on-policy reinforcement learning scheme equipped with linear function approximation. We show that FedSARSA converges to a policy that is near-optimal for all agents, with the extent of near-optimality proportional to the level of heterogeneity.
  arXiv  Detail & Related papers  (2024-01-27T02:43:45Z)
• On the Power of Adaptive Weighted Aggregation in Heterogeneous Federated Learning and Beyond [37.894835756324454]
  Federated averaging (FedAvg) is the most fundamental algorithm in Federated learning (FL)<n>Recent empirical results show that FedAvg can perform well in many real-world heterogeneous tasks.<n>We present a simple and effective FedAvg variant termed FedAWARE.
  arXiv  Detail & Related papers  (2023-10-04T10:15:57Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  We consider distributed variational inequalities (VIs) on domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that covers the settings of fully decentralized calculations. We theoretically analyze its convergence rate in the strongly-monotone, monotone, and non-monotone settings.
  arXiv  Detail & Related papers  (2021-06-15T17:45:51Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)
• A Unified Linear Speedup Analysis of Federated Averaging and Nesterov FedAvg [49.76940694847521]
  Federated learning (FL) learns a model jointly from a set of participating devices without sharing each other's privately held data. In this paper, we focus on Federated Averaging (FedAvg), one of the most popular and effective FL algorithms in use today. We show that FedAvg enjoys linear speedup in each case, although with different convergence rates and communication efficiencies.
  arXiv  Detail & Related papers  (2020-07-11T05:59:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.