Reusing Trajectories in Policy Gradients Enables Fast Convergence

Alessandro Montenegro, Federico Mansutti, Marco Mussi, Matteo Papini, Alberto Maria Metelli
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:90041-90082, 2026.

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 $\mathcal{O}(\epsilon^{-2})$ trajectories to reach an $\epsilon$-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 $\mathcal{O}(\epsilon^{-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 $\omega$ iterations. Through a novel analysis, we prove that RT-PG achieves a sample complexity of $\widetilde{\mathcal{O}}(\epsilon^{-2}\omega^{-1})$. When reusing all available past trajectories, this leads to a rate of $\widetilde{\mathcal{O}}(\epsilon^{-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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-montenegro26a, title = {Reusing Trajectories in Policy Gradients Enables Fast Convergence}, author = {Montenegro, Alessandro and Mansutti, Federico and Mussi, Marco and Papini, Matteo and Metelli, Alberto Maria}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {90041--90082}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/montenegro26a/montenegro26a.pdf}, url = {https://proceedings.mlr.press/v306/montenegro26a.html}, 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 $\mathcal{O}(\epsilon^{-2})$ trajectories to reach an $\epsilon$-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 $\mathcal{O}(\epsilon^{-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 $\omega$ iterations. Through a novel analysis, we prove that RT-PG achieves a sample complexity of $\widetilde{\mathcal{O}}(\epsilon^{-2}\omega^{-1})$. When reusing all available past trajectories, this leads to a rate of $\widetilde{\mathcal{O}}(\epsilon^{-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.} }
Endnote
%0 Conference Paper %T Reusing Trajectories in Policy Gradients Enables Fast Convergence %A Alessandro Montenegro %A Federico Mansutti %A Marco Mussi %A Matteo Papini %A Alberto Maria Metelli %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-montenegro26a %I PMLR %P 90041--90082 %U https://proceedings.mlr.press/v306/montenegro26a.html %V 306 %X 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 $\mathcal{O}(\epsilon^{-2})$ trajectories to reach an $\epsilon$-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 $\mathcal{O}(\epsilon^{-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 $\omega$ iterations. Through a novel analysis, we prove that RT-PG achieves a sample complexity of $\widetilde{\mathcal{O}}(\epsilon^{-2}\omega^{-1})$. When reusing all available past trajectories, this leads to a rate of $\widetilde{\mathcal{O}}(\epsilon^{-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.
APA
Montenegro, A., Mansutti, F., Mussi, M., Papini, M. & Metelli, A.M.. (2026). Reusing Trajectories in Policy Gradients Enables Fast Convergence. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:90041-90082 Available from https://proceedings.mlr.press/v306/montenegro26a.html.

Related Material