Reusing Trajectories in Policy Gradients Enables Fast Convergence

2025/06/06 by Alessandro Montenegro, Federico Mansutti, Montenegro, Alessandro +7
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2506.06178

openalex publication_date 2025/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

Policy gradient (PG) methods are a class of effective reinforcement learning algorithms, particularly when dealing with continuous control problems. They rely on fresh on-policy data, making them sample-inefficient and requiring O(ε^-2) trajectories to reach an ε-approximate stationary point. A common strategy to improve efficiency is to reuse information from past iterations, such as previous gradients or trajectories, leading to off-policy PG methods. While gradient reuse has received substantial attention, leading to improved rates up to O(ε^-3/2), the reuse of past trajectories, although intuitive, remains largely unexplored from a theoretical perspective. In this work, we provide the first rigorous theoretical evidence that reusing past off-policy trajectories can significantly accelerate PG convergence. We propose RT-PG (Reusing Trajectories - Policy Gradient), a novel algorithm that leverages a power mean-corrected multiple importance weighting estimator to effectively combine on-policy and off-policy data coming from the most recent ω iterations. Through a novel analysis, we prove that RT-PG achieves a sample complexity of O(ε^-2ω^-1). When reusing all available past trajectories, this leads to a rate of O(ε^-1), the best known one in the literature for PG methods. We further validate our approach empirically, demonstrating its effectiveness against baselines with state-of-the-art rates.

Citations

• Policy Gradient with Active Importance Sampling
• Learning Optimal Deterministic Policies with Stochastic Policy Gradients
• Reusing Historical Trajectories in Natural Policy Gradient via Importance Sampling: Convergence and Convergence Rate
• BioXP-0.5B: Explainable Medical-AI via RL-GRPO
• PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation
• A general sample complexity analysis of vanilla policy gradient
• Bandit Algorithms
• Stochastic Recursive Momentum for Policy Gradient Methods
• Lower Bounds for Non-Convex Stochastic Optimization
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient
• Smoothing Policies and Safe Policy Gradients
• Benchmarking Deep Reinforcement Learning for Continuous Control
• Stochastic Variance Reduction for Nonconvex Optimization
• Variance Reduction for Faster Non-Convex Optimization
• Trust Region Policy Optimization
• Playing Atari with Deep Reinforcement Learning
• Neuronlike adaptive elements that can solve difficult learning control problems
• Reinforcement Learning: An Introduction

Related

• Reusing Historical Trajectories in Natural Policy Gradient via Importance Sampling: Convergence and Convergence Rate
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning
• On the Global Optimum Convergence of Momentum-based Policy Gradient
• An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient