Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling

• URL: http://arxiv.org/abs/2504.11645v1
• Date: Tue, 15 Apr 2025 22:13:55 GMT
• Title: Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling
• Authors: Feng Zhu, Aritra Mitra, Robert W. Heath,
• Abstract summary: 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.
• Score: 6.549288471493216
• License: http://creativecommons.org/licenses/by/4.0/
• 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 correct point, while enjoying an $M$-fold linear speedup in sample-complexity due to collaboration. To our knowledge, \emph{this is the first finite-time result of its kind}, and establishing it (without relying on a projection step) entails a fairly intricate argument that accounts for the interplay between complex temporal correlations due to Markovian sampling, multiple local steps to save communication, and the drift-effects induced by heterogeneous local operators. Our results have implications for a broad class of heterogeneous federated RL problems (e.g., policy evaluation and control) with function approximation, where the agents' Markov decision processes can differ in their probability transition kernels and reward functions.

Related papers

• Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis [55.13545823385091]
  Federated reinforcement learning (FedRL) enables collaborative learning while preserving data privacy by preventing direct data exchange between agents. In real-world applications, each agent may experience slightly different transition dynamics, leading to inherent model mismatches. We show that even moderate levels of information sharing can significantly mitigate environment-specific errors.
  arXiv  Detail & Related papers  (2025-03-21T18:06:28Z)
• Federated Sinkhorn [2.589644824000165]
  We investigate the potential of solving the discrete Optimal Transport problem with entropy regularization in a federated learning setting. We consider both synchronous and asynchronous variants as well as all-to-all and server-client communication protocols. We empirically demonstrate the algorithms performance on synthetic datasets and a real-world financial risk assessment application.
  arXiv  Detail & Related papers  (2025-02-10T20:29:57Z)
• Towards Fast Rates for Federated and Multi-Task Reinforcement Learning [34.34798425737858]
  We propose Fast-FedPG, a novel federated policy algorithm with a carefully designed bias-correction mechanism. Under a gradient-domination condition, we prove that our algorithm guarantees (i) fast linear convergence with exact gradients, and (ii) sub-linear rates that enjoy a linear speedup w.r.t. the number of agents with noisy, truncated policy gradients.
  arXiv  Detail & Related papers  (2024-09-09T02:59:17Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users [95.77678166036561]
  We propose a UCB-type algorithm with delicate communication protocols. We give sub-linear regret bounds on par with those achieved in the synchronous framework. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.
  arXiv  Detail & Related papers  (2024-02-26T05:31:14Z)
• The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond [44.43850105124659]
  We consider federated Q-learning, which aims to learn an optimal Q-function by periodically aggregating local Q-estimates trained on local data alone. We provide sample complexity guarantees for both the synchronous and asynchronous variants of federated Q-learning. We propose a novel federated Q-learning algorithm with importance averaging, giving larger weights to more frequently visited state-action pairs.
  arXiv  Detail & Related papers  (2023-05-18T04:18:59Z)
• Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity [44.2308932471393]
  We show that exchanging model estimates leads to linear convergence speedups in the number of agents. In a low-heterogeneity regime, exchanging model estimates leads to linear convergence speedups in the number of agents.
  arXiv  Detail & Related papers  (2023-02-04T17:53:55Z)
• Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning [24.567125948995834]
  Federated reinforcement learning is a framework in which $N$ agents collaboratively learn a global model. We show that by careful collaboration of the agents in solving this joint fixed point problem, we can find the global model $N$ times faster.
  arXiv  Detail & Related papers  (2022-06-21T08:39:12Z)
• Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
  This work examines adaptive distributed learning strategies designed to operate under communication constraints. We consider a network of agents that must solve an online optimization problem from continual observation of streaming data.
  arXiv  Detail & Related papers  (2021-12-03T19:23:48Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• UneVEn: Universal Value Exploration for Multi-Agent Reinforcement Learning [53.73686229912562]
  We propose a novel MARL approach called Universal Value Exploration (UneVEn) UneVEn learns a set of related tasks simultaneously with a linear decomposition of universal successor features. Empirical results on a set of exploration games, challenging cooperative predator-prey tasks requiring significant coordination among agents, and StarCraft II micromanagement benchmarks show that UneVEn can solve tasks where other state-of-the-art MARL methods fail.
  arXiv  Detail & Related papers  (2020-10-06T19:08:47Z)

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.