REVIEW 3 major objections 6 minor 3 references
Reusing Trajectories in Policy Gradients Enables Fast Convergence
T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proves that reusing past trajectories, not just past gradients, cuts the sample complexity of policy-gradient methods to $\widetilde{O}(\epsilon^{-1})$ trajectories—the best rate known for this method class.
desk verdict Solid conditional theory with a new O~(1/eps) trajectory-reuse rate, but the key chi^2 bound is infinite for the Gaussian policies used in the experiments. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the Multiple Power Mean (MPM) estimator, a multiple-importance-weighting estimator that pools $N$ fresh trajectories from the current policy $\pi_{\theta_k}$ with $N$ trajectories from each of the previous $\omega_k$ policies. For every reused trajectory it replaces the raw importance weight $p_{\theta_k}(\tau)/p_{\theta_i}(\tau)$ with the power-mean-corrected weight $\big((1-\lambda_{i,k})p_{\theta_i}(\tau)/p_{\theta_k}(\tau)+\lambda_{i,k}\big)^{-1}$, a harmonic mean of the inverse weight and the constant $1$, so every weight is bounded by $1/\lambda_{i,k}$; the deterministic coefficients $\alpha_{i,k}$ avoid the cross-time bias that afflicts history-dependent balance-heuristic weights. The concentration proof combines Freedman's inequality for martingales with an $\epsilon$-net covering of a ball that almost surely contains the history-dependent iterate $\theta_k$, turning a pointwise estimator bound into a uniform one, with $D$ entering through the weight variance and $d_\theta$ through the covering size.
What would settle it
Run RT-PG in the full-reuse regime on a continuous-control task with deep Gaussian policies and measure, across a range of target accuracies $\epsilon$, the number of collected trajectories needed to reach $\mathbb{E}[\|\nabla J(\theta_{\mathrm{OUT}})\|_2^2] \le \epsilon$; the theorem predicts at most $\widetilde{O}(\epsilon^{-1})$ scaling (times $D d_\theta$), so an empirical scaling close to the on-policy $\epsilon^{-2}$ would falsify the claimed improvement in that setting. As a check on the premise, estimate the $\chi^2$-divergence between trajectory distributions of the iterates visited in those runs: if the estimated supremum grows without bound as training proceeds, Assumption 5.2 is violated and the theorem's bound is vacuous.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that reusing past off-policy trajectories yields a provable, order-level improvement in the sample complexity of policy gradients. The central result (Theorem 6.1) asserts that RT-PG, run with a constant step size $\zeta \le 1/L_{2,J}$ and the MPM estimator, guarantees $\mathbb{E}[\|\nabla J(\theta_{\mathrm{OUT}})\|_2^2] \le \epsilon$ with $\widetilde{O}(G_1^2 D d_\theta \epsilon^{-1})$ trajectories under full reuse ($\omega \ge K$) and $\widetilde{O}(G_1^2 D d_\theta \epsilon^{-2} \omega^{-1})$ trajectories under partial reuse, under standard regularity of the policy's log-density (Assumption 5.1) and a uniform bound on the $\chi^2$-divergence between trajectory distributions (Assumption 5.2). The $\widetilde{O}(\epsilon^{-1})$ rate is the best known for policy-gradient methods with stochastic gradients over general policy classes and continuous state-action spaces. The analysis also isolates two failure modes of naive reuse—target bias, because the parameter being estimated is itself a function of the reused data, and cross-time bias, which corrupts balance-heuristic importance weights—and shows that deterministic coefficient choices together with a covering argument keep both under control.
Load-bearing premise
The load-bearing premise is Assumption 5.2: there must exist a finite constant $D \ge 1$ uniformly bounding the $\chi^2$-divergence between the trajectory distributions of any two policies in the parameter space, and for the linear or deep Gaussian policies used in the experiments this supremum is generally infinite unless the parameter iterates are confined to a bounded set.
Editorial extensions
If this is right
- In the full-reuse regime ($\omega \ge K$), RT-PG reaches an $\epsilon$-approximate stationary point with $\widetilde{O}(\epsilon^{-1})$ trajectories, improving on the on-policy $\widetilde{O}(\epsilon^{-2})$ rate and on the $\widetilde{O}(\epsilon^{-3/2})$ rates of gradient-reuse methods.
- The step size is constant and independent of $\epsilon$; the iteration complexity is $O((J^* - J(\theta_1))/(\zeta \epsilon))$, so the gain in sample complexity does not come from a shrinking learning rate.
- RT-PG stores trajectories but not old policies, giving a memory peak of $\widetilde{O}(\epsilon^{-1})$ trajectories in both reuse regimes; for large policies this can outweigh the memory of gradient-reuse schemes that retain past parameters.
- The $\widetilde{O}(\epsilon^{-1})$ upper bound is consistent with the known $\Omega(\epsilon^{-3/2})$ lower bound for actor-only policy gradients without bounded importance-weight variance, since the lower-bound construction has $d_\theta = \widetilde{O}(\epsilon^{-1})$ parameters.
- Under partial reuse the rate is adaptive in the window size, and choosing $\omega = \widetilde{O}(\epsilon^{-1})$ recovers the full-reuse rate even though the window is smaller than the number of iterations.
Reading between the lines
- The theory prescribes a tuning rule the experiments only partially probe: with a fixed budget of fresh data per iteration, the sample-complexity gain should grow with the window $\omega$ up to $\omega \sim 1/\epsilon$, so measuring the empirical rate at larger windows than the tested $\omega \le 8$ is a direct, low-cost test of whether the promised $\epsilon^{-1}$ regime is operative.
- The MPM correction is a generic device for reweighting history-dependent off-policy data, so the same bounded-weight recipe could apply to natural policy gradients, off-policy evaluation, or replay-buffer actor-critic updates; the appendix's extension to parameter-exploring policies suggests the mechanism does not depend on the score function's form.
- If the $\epsilon^{-1}$ rate holds up, the practical bottleneck shifts from sampling to memory and distribution shift: the finite-$D$ assumption and the $\widetilde{O}(1/\epsilon)$ stored trajectories suggest pairing trajectory reuse with explicit proximity constraints on the policy so that reused data stay inside the $\chi^2$-bounded region—a combination the paper does not analyze.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces RT-PG, a policy gradient algorithm that reuses trajectories from the previous ω iterations through a power-mean-corrected multiple importance weighting estimator. The main theoretical results are high-probability concentration bounds for the estimator (Theorems 5.2 and 5.3) and a sample-complexity guarantee (Theorem 6.1): order O~(ε^{-2}ω^{-1}) trajectories under partial reuse and order O~(ε^{-1}) under full reuse, assuming bounded χ² divergence between trajectory distributions (Assumption 5.2) and regularity of the policy class (Assumption 5.1). The analysis combines Freedman's inequality, bias and variance bounds for the power-mean correction, a Lipschitz argument, and a covering argument. The paper also presents experiments in Cart Pole and Half Cheetah, comparing RT-PG against on-policy and variance-reduced baselines.
Significance. If the theoretical result is correct, it is the first finite-time sample-complexity improvement from trajectory reuse in policy gradients, improving on the O(ε^{-3/2}) rate of gradient-reuse methods and on the O(ε^{-5/3}) rate of the trajectory-reuse method BPO, in the considered setting. The proof structure is coherent and detailed in the appendices, the estimator construction is novel, and the paper ships reproducible code. The main caveat is that the central O~(ε^{-1}) claim is conditional on Assumption 5.2, which is violated by the Gaussian policies used in the experimental section; in addition, the experiments use an adaptive-coefficient heuristic rather than the algorithm actually analyzed. These issues narrow the scope of the contribution substantially and need to be addressed in revision.
major comments (3)
- [Section 5, Assumption 5.2; Appendix E.1, Proposition E.1] Assumption 5.2 requires a finite constant D ≥ 1 with sup_{θ1,θ2∈Θ} χ²(p_{θ1}‖p_{θ2}) ≤ D−1. For the linear Gaussian policies used in the Cart Pole experiments and the deep Gaussian policies used in Half Cheetah (Section 7; Appendix F.1), the parameter space Θ is R^{d_Θ}. Proposition E.1 gives d_2(p_{θ1}‖p_{θ2}) = exp( (1/σ²) Σ_{t=1}^T ‖(θ1−θ2)^T s_t‖² ), so χ²(p_{θ1}‖p_{θ2}) = d_2 − 1, and the supremum over θ1, θ2 ∈ R^{d_Θ} is +∞ for any state sequence with nonzero projection on θ1−θ2. Hence D is infinite for the policy class used to validate the method. Since the coefficients λ_{i,k} in Theorem 5.3 and the batch-size lower bounds in Theorem 6.1 depend on D, an infinite D makes the power-mean correction vanish (λ_{i,k} = 0) and the stated bounds vacuous. The Limitations paragraph in Section 6 acknowledges the reliance on D but does not flag that Assumption 5.2 is not satisfied by the Gaussian policies in the experiments. The paper should either restrict Θ to a compact set and track how D depends on the radius, the horizon T, and the number of iterations, or clearly state that the experimental validation does not fall under the theoretical guarantees.
- [Section 6, Theorem 6.1] The headline full-reuse rate rO(d_Θ ε^{-1} max{G_1² D, Δ/(D ζ)}) is not a finite sample-complexity bound for the experimental policy class, because D is infinite and the batch-size condition N ≥ rO(d_Θ/D) cannot be satisfied in a meaningful way. The partial-reuse batch-size condition N ≥ rO(G_1² D d_Θ / (ε ω)) is likewise not satisfiable when D = ∞. The abstract and Table 1 present 'the best known rate' without this caveat. Please qualify the claim as holding only when Assumption 5.2 is satisfied, or introduce a compact parameter-space restriction and make the dependence of D on the problem parameters explicit.
- [Section 7 and Appendix E] The practical version of RT-PG used in the experiments (Algorithm 2) differs from the analyzed algorithm (Algorithm 1) in three ways: it uses adaptive coefficients λ_{i,k} and α_{i,k} based on empirical divergences pD_i, an Adam learning-rate schedule, and best-iterate output. The theoretical guarantees in Theorems 5.2–6.1 apply to Algorithm 1, not to Algorithm 2. The experiments therefore illustrate the potential of the approach but do not verify the sample-complexity bound. The first paragraph of Section 7 states that the experiments 'validate' the approach; this should be softened and the theory-practice gap acknowledged explicitly. Appendix F.7 goes partway by studying Th-RT-PG, but the ablation still uses ad hoc values of D and does not close the gap.
minor comments (6)
- [Abstract] The phrase 'the best known one in the literature for PG methods' should be qualified as 'under Assumptions 5.1 and 5.2' and should be contrasted with the O(ε^{-5/3}) rate of BPO, which holds under different assumptions.
- [Section 5, after Assumption 5.2] The statement that Assumption 5.2 'holds, for instance, with univariate Gaussian policies with σ1 < √2 σ2' is misleading: that pairwise condition applies to a fixed pair of policies, not to the supremum over the entire parameter space Θ, which is infinite for unbounded Θ even when the per-pair condition holds.
- [Appendix F.7] The ablation in Figures 9–11 varies D over arbitrary values that are not tied to any actual χ² bound; these plots should be labeled as heuristic sensitivity analyses rather than as evidence about the theoretical guarantees.
- [Appendix B, proof of Fact 3.1] In the final line of the proof, 'dτ1θ1' should be 'dτ1 dθ1'.
- [Table 1, footnote] The notation rO for soft-O is used throughout the main text but is defined only in a table footnote; please define it in Section 1 or 2 and state which logarithmic factors are hidden.
- [Section 6, Considerations on Memory Requirements] The statement that RT-PG stores rO(ε^{-1}) trajectories should be made more precise by specifying the dependence on the batch size N and the dimensionality d_Θ, since N itself may depend on D and d_Θ.
Circularity Check
No significant circularity: the Õ(ε^{-1}) rate is a theorem consequence of Assumptions 5.1–5.2, not an assumption or fit.
full rationale
I walked the full derivation chain. The MPM estimator is a design choice; Theorem 5.2 proves its concentration at a history-independent target using two external lemmas from Metelli et al. (2021) for the PM bias and variance. Those lemmas are published results whose stated assumptions do not include the claimed rate, so under the review rules they count as independent support even though one author overlaps. Theorem 5.3 extends the bound to the history-dependent parameter θ_k via a covering argument and Lipschitz continuity of the estimation error, with all logarithmic factors derived rather than assumed. Theorem 6.1 combines the expectation bound (Lemma D.1) with the smoothness descent inequality; the partial-reuse rate Õ(G₁²D d_Θ ε^{-2} ω^{-1}) and the full-reuse rate Õ(G₁²D d_Θ ε^{-1}) are obtained by algebraically trading batch size and iteration complexity. No equation in the paper defines the convergence rate into itself: the ε^{-1} target is not an input to Assumption 5.2, to the PM correction, or to the coefficient choices. The practical variant estimates local χ² divergences to set α and λ, but the estimated object is the policy gradient, not the convergence rate, so this is not a fitted parameter renamed as a prediction. The serious concern that Assumption 5.2 may be violated for the Gaussian policies used in the experiments is a correctness and assumption-satisfaction issue, not a circularity; the theorems are conditional on that assumption rather than equivalent to it. I therefore find no significant circularity and assign score 0.
Assumptions & free parameters
assumptions (6)
- domain assumption Assumption 5.1: sup_{theta in Theta, a in A, s in S} ||nabla log pi_theta(a|s)||_2 <= L_{1,Theta} and ||nabla^2 log pi_theta(a|s)||_2 <= L_{2,Theta}.
- domain assumption Assumption 5.2: there exists D >= 1 such that sup_{theta1,theta2 in Theta} chi^2(p_{theta1} || p_{theta2}) <= D-1.
- domain assumption Bounded rewards |r| <= R_max and finite horizon T or discounted infinite horizon.
- standard math Freedman's inequality for martingale difference sequences.
- standard math Power-mean correction bias and variance bounds from Metelli et al. (2021, Lemma 5.1).
- standard math Covering-number bound for the unit ball in R^{d_theta} (Lattimore and Szepesvari, 2020, Lemma 20.1).
Cite this review
Pith. "Pith review of Reusing Trajectories in Policy Gradients Enables Fast Convergence." pith.science (2026). https://pith.science/paper/3O2NW6MU
@misc{pith2026250606178,
author = {Pith},
title = {Pith review of: Reusing Trajectories in Policy Gradients Enables Fast Convergence},
year = {2026},
howpublished = {\url{https://pith.science/paper/3O2NW6MU}},
note = {Machine review of arXiv:2506.06178}
}
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(\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 $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 $\tilde{O}(\epsilon^{-2}\omega^{-1})$. When reusing all available past trajectories, this leads to a rate of $\tilde{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.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[2]
We start by imposingBď ϵ 2, which allows us to retrieve a requirement on the iteration complexity ofRT-PGfor ensuring the convergence to anϵ-approximate stationary point: B“ 2pJ˚´Jpθ 1qq ζK ď ϵ 2 ùñKě 4pJ˚´Jpθ 1qq ζϵ .(168) Thus, the iteration complexity is of orderKěOppJ ˚´Jpθ 1qqζ´1ϵ´1q. Next, we imposeAď ϵ 2 as well, from which we will recover a condit...
-
[3]
RegardingAandB, we already derived the sufficient conditions for Case I, with just a different fraction ofϵ, leading to: Kě 6pJ˚´Jpθ 1qq ζϵ , (175) N Kě 3510G2 1DdΘ ϵ log ¨ ˝eΨ ˜ 14040G2 1DdΘ ? Ψ ϵ ¸2˛ ‚ 2 “ 14040G2 1DdΘ ϵ log ˆ 14040?eG2 1DdΘΨ ϵ ˙2 .(176) Let us now consider termCand enforce the corresponding condition: C“ 1170G2 1DdΘ logpΨN ωq N ω ď ϵ 3...
work page 2021
-
[551]
Stochastic Recursive Momentum for Policy Gradient Methods
PMLR, 2019. Xu, P., Gao, F., and Gu, Q. Sample efficient policy gradient methods with recursive variance reduction. InInterna- tional Conference on Learning Representations (ICLR), 2020. Yuan, H., Lian, X., Liu, J., and Zhou, Y . Stochastic re- cursive momentum for policy gradient methods.arXiv preprint arXiv:2003.04302, 2020. Yuan, R., Gower, R. M., and ...
work page Pith review arXiv 2020
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.