Reusing Trajectories in Policy Gradients Enables Fast Convergence

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

TL;DR

Reusing past trajectories (off-policy data) in policy gradient methods has long been intuitively appealing but theoretically opaque. This paper introduces RT-PG (Reusing Trajectories - Policy Gradient), a novel algorithm that leverages a power mean-corrected importance sampling estimator to safely mix past data with fresh samples. Theoretically, RT-PG accelerates convergence to a state-of-the-art sample complexity of $\tilde{O}(\epsilon^{-1})$, significantly outperforming traditional gradient-reuse methods while demonstrating superior empirical performance on continuous control benchmarks.

What Problem Does This Paper Address?

Policy Gradient (PG) methods are a staple of reinforcement learning for continuous control, but they are notoriously data-hungry. Vanilla PG methods (like REINFORCE) are strictly on-policy: they require completely fresh trajectories to estimate the gradient at each policy update, resulting in a slow sample complexity of $O(\epsilon^{-2})$ to find an $\epsilon$-approximate stationary point.

To improve efficiency, researchers often try to reuse past data. While reusing past gradients (variance reduction techniques like SVRPG or STORM-PG) has been heavily studied and optimizes the rate to $O(\epsilon^{-3/2})$, reusing past trajectories remains largely unexplored theoretically.

The core challenge of trajectory reuse is statistical dependence. Because the current policy parameter ($\theta_k$) is computed using the history of past trajectories, evaluating a new gradient on those same trajectories introduces severe statistical biases:

  1. Target Bias: The target policy depends directly on the history of sampled trajectories, leaking information and biasing the estimator.
  2. Cross-time Bias: Using standard data-mixing heuristics (like the Balance Heuristic) introduces dependencies on future policies, breaking time coherence.
Figure 1. Update scheme up to k “ 2. Arrows denote: ( ) tra- jectory sampling, ( ) update dynamics, and ( ) estimator inputs.

The authors address this gap by providing the first rigorous theoretical framework and practical algorithm for fast, stable trajectory reuse.

Methods

The authors propose RT-PG, which replaces vanilla on-policy gradient estimators with a novel Multiple Power Mean (MPM) estimator.

Instead of using standard Multiple Importance Weighting (MIW) or the Balance Heuristic (BH)—which either suffer from exploding variance or high memory overhead—the MPM estimator introduces a Power Mean (PM) correction (specifically a harmonic mean correction). This bounds the importance weights by a deterministic threshold ($1/\lambda_{i,k}$), effectively curtailing the high variance typical of off-policy data mismatch.

Crucially, the MPM estimator uses deterministic coefficients ($\alpha_{i,k}$) based solely on the iteration count, entirely eliminating cross-time bias. Furthermore, unlike the Balance Heuristic, MPM does not require storing old policy parameters in memory; it only requires the current policy and a history buffer of the trajectories themselves.

Comparison of memory requirements and sample complexity across various PG methods.

Datasets

The algorithm was evaluated on standard continuous control environments from the MuJoCo physics engine suite:

  • Continuous Cart Pole (used for window sensitivity and ablation studies)
  • HalfCheetah-v4 (a highly complex observation/action space environment)
  • Swimmer-v4 (noted for exposing difficult local optima)

No new datasets or benchmarks were introduced.

Key Insights and Ideas

  • The Bias Trade-off: Trajectory reuse inherently introduces "PM bias" due to the weight-bounding correction. However, the authors show that this bias is easily controlled by scaling the batch size, whereas the "cross-time bias" of other estimators is mathematically unmanageable.
  • Window-Dependent Acceleration: The sample complexity of RT-PG scales inversely with the reuse window size $\omega$, achieving $\tilde{O}(\epsilon^{-2}\omega^{-1})$.
  • Reaching the Theoretical Limit: When maximizing data reuse across all past iterations ($\omega = K$), the sample complexity drops to $\tilde{O}(\epsilon^{-1})$. This is the fastest known rate for stochastic policy gradients in general policy classes.
  • Memory Efficiency over Policy Storage: Storing past trajectories is often significantly cheaper than storing past policy neural networks when the parameter space ($d_\Theta$) is massive. MPM exploits this by keeping a history of data rather than a history of models.
Comparison of estimators highlighting target, cross-time, and PM biases alongside storage requirements.

Key Results

  • Sample Efficiency Gains: In Cart Pole experiments, RT-PG demonstrated up to a 7x speedup in sample efficiency over the standard on-policy baseline (GPOMDP) when utilizing a window size of $\omega = 8$.
  • Baseline Outperformance: In the challenging HalfCheetah-v4 and Swimmer-v4 environments, RT-PG converged significantly faster and achieved nearly twice the final average return of state-of-the-art variance-reduced methods (such as STORM-PG and SRVRPG).
  • Robustness to Hyperparameters: Ablation studies (Th-RT-PG) revealed that the algorithm is highly robust to the choice of the divergence bound $D$, making it highly viable for practical deployment where true divergence bounds are unknown.

Limitations and Future Work

  • Divergence Assumption: The theoretical analysis relies on a uniform bound ($D$) on the $\chi^2$-divergence between trajectory distributions. While the practical version of RT-PG bypasses this by estimating divergences dynamically, proving convergence without this assumption remains an open challenge.
  • Dimensionality Dependence: The sample complexity bounds contain an explicit dependence on the dimensionality of the policy parameter space ($d_\Theta$), introduced by the covering arguments used to bound the target bias. Future work will focus on deriving dimension-free convergence rates.

Summary updated

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 $\tilde{O}(ε^{-2}ω^{-1})$. When reusing all available past trajectories, this leads to a rate of $\tilde{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.
BibTeX
@inproceedings{montenegro2026reusing,
  author = {Alessandro Montenegro and Federico Mansutti and Marco Mussi and Matteo Papini and Alberto Maria Metelli},
  title = {{Reusing Trajectories in Policy Gradients Enables Fast Convergence}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=gcYvvxTLRA},
}
Figure