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:
- Target Bias: The target policy depends directly on the history of sampled trajectories, leaking information and biasing the estimator.
- Cross-time Bias: Using standard data-mixing heuristics (like the Balance Heuristic) introduces dependencies on future policies, breaking time coherence.
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.
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.
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