Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning

• URL: http://arxiv.org/abs/2509.24305v1
• Date: Mon, 29 Sep 2025 05:38:42 GMT
• Title: Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning
• Authors: Alexander Tyurin, Andrei Spiridonov, Varvara Rudenko,
• Abstract summary: We introduce two new algorithms, Rennala NIGT and Malenia NIGT, which implement asynchronous policy gradient aggregation.<n>In the homogeneous setting, Rennala NIGT provably improves the total computational and communication complexity while supporting the AllReduce operation.<n>In the heterogeneous setting, Malenia NIGT simultaneously handles asynchronous computations and heterogeneous environments with strictly better theoretical guarantees.
• Score: 55.50683337004406
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study distributed reinforcement learning (RL) with policy gradient methods under asynchronous and parallel computations and communications. While non-distributed methods are well understood theoretically and have achieved remarkable empirical success, their distributed counterparts remain less explored, particularly in the presence of heterogeneous asynchronous computations and communication bottlenecks. We introduce two new algorithms, Rennala NIGT and Malenia NIGT, which implement asynchronous policy gradient aggregation and achieve state-of-the-art efficiency. In the homogeneous setting, Rennala NIGT provably improves the total computational and communication complexity while supporting the AllReduce operation. In the heterogeneous setting, Malenia NIGT simultaneously handles asynchronous computations and heterogeneous environments with strictly better theoretical guarantees. Our results are further corroborated by experiments, showing that our methods significantly outperform prior approaches.

Related papers

• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  We introduce Ringleader ASGD, the first asynchronous algorithm that attains the theoretical lower bounds for parallel computation.<n>Our analysis further establishes that Ringleader ASGD remains optimal under arbitrary gradient and even time-varying speeds.
  arXiv  Detail & Related papers  (2025-09-26T19:19:15Z)
• Preference-Based Multi-Agent Reinforcement Learning: Data Coverage and Algorithmic Techniques [65.55451717632317]
  We study Preference-Based Multi-Agent Reinforcement Learning (PbMARL)<n>We identify the Nash equilibrium from a preference-only offline dataset in general-sum games.<n>Our findings underscore the multifaceted approach required for PbMARL.
  arXiv  Detail & Related papers  (2024-09-01T13:14:41Z)
• Neural Conditional Probability for Uncertainty Quantification [22.951644463554352]
  We introduce Neural Conditional Probability (NCP), an operator-theoretic approach to learning conditional distributions.<n>By leveraging the approximation capabilities of neural networks, NCP efficiently handles a wide variety of com- plex probability distributions.<n>In experiments, we show that NCP with a 2-hidden-layer network matches or outperforms leading methods.
  arXiv  Detail & Related papers  (2024-07-01T10:44:29Z)
• Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments [17.995517050546244]
  We explore a Federated Reinforcement Learning (FRL) problem where $N$ agents collaboratively learn a common policy without sharing their trajectory data. We propose two algorithms: FedSVRPG-M and FedHAPG-M, which converge to a stationary point of the average performance function. Our algorithms enjoy linear convergence speedups with respect to the number of agents, highlighting the benefit of collaboration among agents in finding a common policy.
  arXiv  Detail & Related papers  (2024-05-29T20:24:42Z)
• On the Communication Complexity of Decentralized Bilevel Optimization [40.45379954138305]
  We propose two novel decentralized bilevel gradient descent algorithms based on simultaneous and alternating update strategies. Our algorithms can achieve faster convergence rates and lower communication costs than existing methods. This is the first time such favorable theoretical results have been achieved with mild assumptions in the heterogeneous setting.
  arXiv  Detail & Related papers  (2023-11-19T14:56:26Z)
• AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
  We analyze asynchronous-type algorithms for distributed SGD in the heterogeneous setting. As a by-product of our analysis, we also demonstrate guarantees for gradient-type algorithms such as SGD with random tightness.
  arXiv  Detail & Related papers  (2023-10-31T13:44:53Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  Three major challenges in reinforcement learning are the complex dynamical systems with large state spaces, the costly data acquisition processes, and the deviation of real-world dynamics from the training environment deployment. We study distributionally robust Markov decision processes with continuous state spaces under the widely used Kullback-Leibler, chi-square, and total variation uncertainty sets. We propose a model-based approach that utilizes Gaussian Processes and the maximum variance reduction algorithm to efficiently learn multi-output nominal transition dynamics.
  arXiv  Detail & Related papers  (2023-09-05T13:42:11Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees [10.984101749941471]
  We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. Results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates.
  arXiv  Detail & Related papers  (2021-09-09T19:08:56Z)
• An Efficient Asynchronous Method for Integrating Evolutionary and Gradient-based Policy Search [76.73477450555046]
  We introduce an Asynchronous Evolution Strategy-Reinforcement Learning (AES-RL) that maximizes the parallel efficiency of ES and integrates it with policy gradient methods. Specifically, we propose 1) a novel framework to merge ES and DRL asynchronously and 2) various asynchronous update methods that can take all advantages of asynchronism, ES, and DRL.
  arXiv  Detail & Related papers  (2020-12-10T02:30:48Z)
• Learning Fast Approximations of Sparse Nonlinear Regression [50.00693981886832]
  In this work, we bridge the gap by introducing the Threshold Learned Iterative Shrinkage Algorithming (NLISTA) Experiments on synthetic data corroborate our theoretical results and show our method outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-10-26T11:31:08Z)
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees [39.092596142018195]
  Communication cost is often a critical bottleneck to scale up distributed optimization algorithms to collaboratively learn a model from millions of devices. Two notable trends to deal with the communication overhead of federated compression and computation are unreliable compression and heterogeneous communication. We analyze their convergence in both homogeneous and heterogeneous data distribution settings.
  arXiv  Detail & Related papers  (2020-07-02T14:44:07Z)

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.