Reusing Trajectories in Policy Gradients Enables Fast Convergence

Alessandro Montenegro, Federico Mansutti, Marco Mussi, Matteo Papini, Alberto Maria Metelli · 2025

Read Reusing Trajectories in Policy Gradients Enables Fast Convergence by Alessandro Montenegro, Federico Mansutti, Marco Mussi, Matteo Papini, Alberto Maria Metelli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06178.txt.

Introduction

Policy gradient methods teach software agents by trial and error, but they usually throw away each run of experience after one use. Alessandro Montenegro, Federico Mansutti, Marco Mussi, Matteo Papini, and Alberto Maria Metelli ask whether reusing old runs can speed up learning. Their algorithm, RT-PG, mixes fresh runs with recent past ones and corrects for the mismatch with a special weighting.

The team proves that this reuse cuts the number of runs needed to reach a given accuracy. When all past runs are recycled, the rate they prove is the best known for this family of methods. Experiments back the theory, with RT-PG beating rivals that hold the previous best rates. The work gives a firm base for a trick practitioners already suspected was sound.

Catalog record

CREATORAlessandro Montenegro, Federico Mansutti, Marco Mussi, Matteo Papini, Alberto Maria Metelli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE135 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06178

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Reusing Trajectories in Policy Gradients Enables Fast Convergence Alessandro Montenegro, Federico Mansutti, Marco Mussi, Matteo Papini, Alberto Maria Metelli Abstract Policy gradient (PG) methods are a class of effective reinforcement learning algorithms, particularly when dealing with continuous control problems. These methods learn the parameters of parametric policies via stochastic gradient ascent, typically using on-policy trajectory data to estimate the policy gradient. However, such reliance on fresh data makes them sample-inefficient. Indeed, vanilla PG methods require 𝒪 ⁡ ( ϵ − 2 ) \mathcal{O}(\epsilon^{-2}) trajectories to reach an ϵ \epsilon -approximate stationary point. A common strategy to improve efficiency is to reuse off-policy information from past iterations, such as previous gradients or trajectories . While gradient reuse has received substantial theoretical attention, leading to improved rates of 𝒪 ( ϵ − 3 / 2 ) \mathcal{O}(\epsilon^{-3/2}) , the reuse of past trajectories remains largely unexplored from a theoretical perspective. In this work, we provide the first rigorous theoretical evidence that extensive reuse of past off-policy trajectories can significantly accelerate convergence in PG methods. We introduce a power mean correction to the multiple importance weighting estimator and propose RPG (Retrospective Policy Gradient), a PG algorithm that combines old and new trajectories for policy updates. Through a novel analysis, we show that, under established assumptions, RPG achieves a sample complexity of 𝒪 ~ ​ ( ϵ − 1 ) \widetilde{\mathcal{O}}(\epsilon^{-1}) , the best known rate in the literature. We further validate empirically our approach against PG methods with state-of-the-art rates. 1 Introduction Among reinforcement learning ( Sutton and Barto 2018 , RL,) approaches, policy gradient ( Deisenroth et al. 2013 , PG,) methods have demonstrated notable success in tackling real-world problems, due to their capacity to operate in continuous state and action spaces ( Peters and Schaal 2006 ) , robustness to sensor and actuator noise ( Gravell et al. 2020 ) , and effectiveness in managing partially observable environments ( Azizzadenesheli et al. 2018 ) . Moreover, PG methods allow for the integration of expert prior knowledge into policy design ( Ghavamzadeh and Engel 2006 ) , thereby enhancing the safety, interpretability, and performance of the learned policy ( Peters and Schaal 2008 ) . PG methods operate by directly optimizing the parameters \bm{\theta}\in\mathbb{R}^{d_{\Theta}} of parametric policies to maximize a performance objective J(\bm{\theta}) , typically the expected return. In practice, the parameter vector \bm{\theta} is updated via gradient ascent, based on an estimate of the gradient \nabla J(\bm{\theta}) w.r.t. the policy parameters. The goal is to identify an optimal parameterization \bm{\theta}^{*} that maximizes the objective. In most cases J(\bm{\theta}) is a non-convex objective, thus this notion of optimality is often relaxed to that of finding a first-order stationary point , defined by the condition \|\nabla J(\bm{\theta}^{*})\|_{2}=0 ( Papini et al. 2018 ) . Despite their practical success, PG methods remain notoriously data-hungry, as each update requires several interactions with the environment to gather fresh data for gradient estimation. This limitation is reflected in their theoretical convergence guarantees, which have become a central focus in the PG literature. Vanilla PGs such as REINFORCE ( Williams 1992 ) , PGT ( Sutton et al. 1999 ) , and GPOMDP ( Baxter and Bartlett 2001 ) aim to learn \bm{\theta}^{*} via stochastic gradient ascent, using only on-policy trajectories, i.e., those generated by the current policy. These methods require order of \mathcal{O}(\epsilon^{-2}) total trajectories to reach an \epsilon -approximate stationary point, i.e., a parameter \bm{\theta} such that \|\nabla J(\bm{\theta})\|_{2}^{2}\leq\epsilon . These unsatisfactory theoretical guarantees of vanilla PG methods are primarily due to the high variance of the gradient estimates, which are computed using only on-policy trajectories. To mitigate this variance, one can reuse off-policy data collected during the learning process, such as past gradients or past trajectories originating from different policy parameterizations. These data are typically incorporated into the gradient estimation through importance weighting ( Owen and Zhou 2000 ) . A central challenge in this setting arises from the use of importance weights (IWs), which may inject high variance in the gradient estimate ( Mandel et al. 2014 ) . While reusing trajectories is the most natural choice for improving PGs’ sample efficiency, the literature extensively focused instead on reusing gradients, proposing various update schemes. Among these methods, Papini et al. 2018 introduced SVRPG, which incorporates ideas from stochastic variance-reduced gradient methods ( Johnson and Zhang 2013 ; Allen-Zhu and Hazan 2016 ; Reddi et al. 2016 ) . Specifically, SVRPG employs a semi-stochastic gradient that combines the stochastic gradient at the current iterate with that of a past “snapshot” parameterization. This method achieves a sample complexity of \mathcal{O}(\epsilon^{-5/3}) ( Xu et al. 2020 ) . An improvement over this result was proposed by Xu et al. 2019 , who introduced SRVRPG. Unlike SVRPG, SRVRPG employs a recursive semi-stochastic gradient , which integrates the current stochastic gradient with those accumulated throughout the entire learning process. This recursive structure reduces the sample complexity to \mathcal{O}(\epsilon^{-3/2}) under the same convergence criterion. Furthermore, Yuan et al. 2020 proposed STORM-PG, which, instead of alternating between small and large batch updates as in SRVRPG, maintains a moving average of past stochastic gradients. This approach enables adaptive step sizes and eliminates the need for large batches of trajectories, while still ensuring a sample complexity of \mathcal{O}(\epsilon^{-3/2}) . More recently, Paczolay et al. 2024 introduced a variant of STORM-PG that stochastically decides whether or not to reuse past gradients at each iteration. This method retains the same sample complexity of \mathcal{O}(\epsilon^{-3/2}) , while relaxing the standard assumption of bounded IW variance. Beyond gradient reuse, variance reduction can also be achieved by reusing off-policy trajectories collected with previous policies. While this approach is conceptually more natural, it has received relatively little theoretical attention. For instance, Metelli et al. 2018 propose reusing trajectories to compute multiple successive stochastic gradient estimates, but with no formal convergence guarantees. Similarly, Papini et al. 2024 leverage past trajectories collected under multiple policy parameterizations, achieving a sample complexity of \mathcal{O}(\epsilon^{-5/3}) , under strong technical assumptions. Table 1 summarizes the key assumptions, data reuse strategies, and sample complexities of related PG methods. Algorithm Data Reused Assumptions Sample Complexity a Regular a Policies § a IW Bounded a Variance REINFORCE ( Williams 1992 ) — ✓ ✗ \mathcal{O}\left(\epsilon^{-2}\right) PGT ( Sutton et al. 1999 ) — ✓ ✗ \mathcal{O}\left(\epsilon^{-2}\right) GPOMDP ( Baxter and Bartlett 2001 ) — ✓ ✗ \mathcal{O}\left(\epsilon^{-2}\right) BPO ( Papini et al. 2024 ) Trajectories \text{\color[rgb]{1,0,0} ✓ {} }^{\dagger} \text{\color[rgb]{1,0,0} ✓ {} }^{\dagger} \mathcal{O}\left(\epsilon^{-5/3}\right) SVRPG ( Papini et al. 2018 ; Xu et al. 2020 ) Gradients ✓ ✓ \mathcal{O}\left(\epsilon^{-5/3}\right) SRVRPG ( Xu et al. 2019 ) Gradients ✓ ✓ \mathcal{O}\left(\epsilon^{-3/2}\right) STORM-PG ( Yuan et al. 2020 ) Gradients ✓ ✓ \mathcal{O}\left(\epsilon^{-3/2}\right) DEF-PG ( Paczolay et al. 2024 ) Gradients ✓ ✗ \mathcal{O}\left(\epsilon^{-3/2}\right) RPG (this work) Trajectories ✓ ✓ \widetilde{\mathcal{O}}\left(\epsilon^{-1}\right) # \dagger Stricter assumptions implying the ones matched. # \widetilde{\mathcal{O}}(\cdot) hides logarithmic factors. § See Assumption 4.4 . Table 1 : Comparison of the sample complexities of methods achieving \|\nabla J(\bm{\theta})\|_{2}^{2}\leq\epsilon . Original Contribution. Despite significant progress in reducing sample complexity, state-of-the-art methods still require \mathcal{O}(\epsilon^{-3/2}) trajectories to reach an \epsilon -approximate stationary point. Most of these improvements rely on gradient reuse, a theoretically convenient but arguably less

Read the complete text