Technical Summary: Reusing Trajectories in Policy Gradients Enables Fast Convergence

Problem Statement

Policy Gradient (PG) methods are effective for continuous control problems but suffer from poor sample efficiency. Standard "vanilla" PG algorithms (e.g., REINFORCE, GPOMDP) rely exclusively on fresh on-policy data, requiring $O(\epsilon^{-2})$ trajectories to reach an $\epsilon$-approximate stationary point. This inefficiency stems from the high variance of gradient estimates, which does not vanish because gradients are always estimated from new samples.

While reusing past data (off-policy trajectories or gradients) is a common strategy to improve efficiency, existing theoretical work has largely focused on gradient reuse (e.g., SVRPG, SRVRPG, STORM-PG), achieving rates up to $O(\epsilon^{-3/2})$. The reuse of past trajectories, though intuitive, has remained largely unexplored from a rigorous theoretical perspective. Previous attempts to reuse trajectories either lacked convergence guarantees or relied on strong assumptions and complex estimators (e.g., requiring storage of all past policies or suffering from high variance due to naive importance weighting).

The central question addressed is: Can the reuse of past off-policy trajectories lead to provable improvements in the sample complexity of PG methods?

Methodology

The RT-PG Algorithm

The authors propose RT-PG (Reusing Trajectories – Policy Gradient), a novel algorithm that estimates the policy gradient by leveraging trajectories collected from the most recent $\omega$ iterations. The core innovation is the Multiple Power Mean (MPM) estimator, which combines on-policy and off-policy data using a corrected Multiple Importance Weighting (MIW) scheme.

The MPM Estimator

To address the statistical challenges of reusing data (specifically bias introduced by the dependency between the current policy parameters and past trajectories), the MPM estimator employs two key mechanisms:

1. Deterministic Coefficients: Unlike the Balance Heuristic (BH) which uses coefficients dependent on all past policies (introducing "cross-time bias"), RT-PG uses deterministic coefficients $\alpha_{i,k}$ that depend only on the iteration count and window index. This eliminates cross-time bias.
2. Power Mean (PM) Correction: To ensure the importance weights remain bounded (a "defensive" property) and to control the bias introduced by the deterministic coefficients, the estimator applies a PM correction to the vanilla importance weights. The corrected weight for a trajectory $\tau$ collected under policy $\pi_{\theta_i}$ and evaluated under $\pi_{\theta_k}$ is:
   $$\left( (1 - \lambda_{i,k}) \frac{p_{\theta_i}(\tau)}{p_{\theta_k}(\tau)} + \lambda_{i,k} \right)^{-1}$$
   where $\lambda_{i,k} \in [0, 1]$ is a correction parameter. This term represents a harmonic mean between the vanilla weight and 1, ensuring the weight is bounded by $1/\lambda_{i,k}$.

Theoretical Analysis

The authors provide a rigorous finite-time analysis of the MPM estimator:

• Concentration Bounds: They derive high-probability concentration bounds for the estimator using Freedman's inequality for martingales and a covering argument to handle the vector-valued nature of the gradient.
• Bias Control: The analysis explicitly separates and controls two sources of bias:
  • Target Bias: Arising because the target parameter $\theta_k$ depends on the history of trajectories. This is controlled via a covering argument over a subset of the parameter space containing the history-dependent target.
  • PM Bias: Arising from the PM correction term. This is managed by carefully selecting $\lambda_{i,k}$ based on the batch size and the $\chi^2$-divergence bound between trajectory distributions.

Key Contributions

1. First Rigorous Evidence: The paper provides the first theoretical proof that reusing past off-policy trajectories can significantly accelerate PG convergence.
2. Novel Estimator (MPM): Introduction of the MPM estimator, which effectively mixes fresh on-policy data with off-policy trajectories from the last $\omega$ iterations while maintaining bounded importance weights and eliminating cross-time bias.
3. Improved Sample Complexity:
   • Partial Reuse: When reusing trajectories from the most recent $\omega$ iterations (where $\omega < K$), RT-PG achieves a sample complexity of $\tilde{O}(\epsilon^{-2}\omega^{-1})$.
   • Full Reuse: When reusing all available past trajectories (where $\omega \ge K$), the algorithm achieves a sample complexity of $\tilde{O}(\epsilon^{-1})$. This matches the best-known rates in the literature for PG methods and represents a significant improvement over the standard $O(\epsilon^{-2})$ rate.
4. Practical Implementation: A practical variant of RT-PG is proposed that adaptively weights off-policy data based on empirical estimates of policy dissimilarity (divergence), removing the need for the theoretical global bound $D$ in practice.

Results

Theoretical Results

Under standard assumptions (bounded $\chi^2$-divergence between trajectory distributions and regularity of the policy class), the authors prove that RT-PG finds an $\epsilon$-approximate stationary point with:

• $\tilde{O}(\epsilon^{-1})$ sample complexity in the full reuse regime.
• $\tilde{O}(\epsilon^{-2}\omega^{-1})$ sample complexity in the partial reuse regime.

These results hold without requiring the storage of past policies (unlike BH-based methods), only requiring the storage of past trajectories.

Empirical Results

Experiments were conducted on continuous control tasks (Cart Pole, Half Cheetah, Swimmer) using both linear Gaussian and deep Gaussian policies.

• Sample Efficiency: RT-PG consistently outperforms standard on-policy baselines (GPOMDP) and state-of-the-art variance-reduced methods (SVRPG, SRVRPG, STORM-PG, DEF-PG) in terms of sample efficiency. In the Half Cheetah environment, RT-PG achieved nearly twice the final performance of most baselines.
• Trajectory Reuse Impact: Experiments varying the window size $\omega$ demonstrated that increasing the reuse window accelerates convergence. RT-PG showed diminishing returns for very large windows but significantly outperformed baselines even with moderate reuse.
• Comparison with Naive Reuse: RT-PG significantly outperformed MIW-PG (which uses uniform weighting), validating the effectiveness of the PM correction and adaptive weighting scheme in controlling variance.
• Memory Efficiency: Unlike BH-based methods that require storing all past policy parameters to compute weights, RT-PG only requires storing past trajectories, making it more scalable for high-dimensional policy spaces.

Significance and Claims

The paper claims to provide the first rigorous theoretical evidence that trajectory reuse is a viable and powerful mechanism for accelerating Policy Gradient convergence. By introducing the RT-PG algorithm and the MPM estimator, the authors bridge the gap between the intuitive idea of reusing past data and provable convergence guarantees.

The significance lies in:

1. Theoretical Advancement: Establishing that trajectory reuse can achieve the $\tilde{O}(\epsilon^{-1})$ rate, previously thought difficult for PG methods without strong assumptions or gradient reuse.
2. Practical Utility: Demonstrating that reusing trajectories reduces the sampling cost without compromising learning stability, offering a practical alternative to gradient-reuse methods that may require larger batch sizes or complex variance reduction techniques.
3. Memory Efficiency: Achieving improved rates without the memory overhead of storing past policy parameterizations, a limitation of other trajectory-reuse approaches like the Balance Heuristic.

The authors remain modest regarding the limitations, noting that their results rely on the assumption of bounded $\chi^2$-divergence between trajectory distributions and that the sample complexity depends on the parameter dimensionality $d_\Theta$. They identify removing this assumption and eliminating the dimension dependency as future work.