The Trajectory Count Is Not the Training Bill

TL;DR for operators

Generating fresh training trajectories can be expensive. Reusing gradient information from previous policy updates may reduce that expense, but changes in the policy make earlier estimates increasingly difficult to trust.

In Variance-Reduced Policy Gradient is Nearly Minimax-Optimal, Leonardo Cesani, Matteo Papini, and Marcello Restelli¹ establish that a class of first-order, actor-only policy-gradient algorithms can achieve an expected final-policy suboptimality gap of at most $\psi+\epsilon$ using $\widetilde{\mathcal O}(\epsilon^{-2})$ trajectories, under specified assumptions. A matching lower bound establishes the optimality of the target-accuracy exponent, up to logarithmic factors.

The mechanism combines defensive importance sampling, which controls the weights used to correct for policy changes, with recursive gradient estimation that limits accumulated estimation error.

For reinforcement-learning engineers, this makes defensive recursive optimization a credible benchmarking candidate when trajectory collection dominates training cost. It does not establish cheaper training overall: the algorithm adds likelihood evaluations and parameter-storage overhead, its guarantees depend on restrictive conditions, and its experiments do not include language models.

A previous gradient is only useful if it remains relevant

A policy-gradient optimizer estimates how changes to policy parameters affect expected reward. Conventional Monte Carlo estimates can be noisy, requiring many trajectories to obtain a dependable update.

One alternative is to carry forward gradient information rather than reconstruct every estimate independently. The difficulty is that a trajectory sampled under one policy does not necessarily represent the trajectory distribution under its successor.

Off-policy importance sampling corrects this mismatch through likelihood ratios. However, ordinary ratios can become extremely large when a trajectory is much more probable under the target policy than under the sampling policy. Recursive estimation then risks propagating noisy corrections across updates.

The paper addresses this problem through defensive importance sampling.

Instead of sampling exclusively from one policy distribution, it constructs a mixture of two adjacent trajectory distributions:

When $0<\xi<1$, importance weights for the new policy are bounded by $1/\xi$, while those for the previous policy are bounded by $1/(1-\xi)$. At the theorem’s choice of $\xi=1/2$, both bounds equal 2.

This removes the need to assume uniformly bounded variance for conventional importance weights. It does not eliminate importance weighting or guarantee that arbitrary stored trajectories can be reused safely. The analyzed method samples from the mixture and evaluates likelihoods under the relevant policies.

That distinction matters for implementation: controlling statistical instability introduces additional sampling and likelihood-evaluation requirements.

The accuracy exponent matches a statistical limit

The paper’s main contribution is a conditional global-convergence result, rather than simply another variance-reduction heuristic.

Under bounded policy-score norms, mean-squared score smoothness, and weak gradient domination, Theorem 5.1 establishes:

with trajectory complexity

suppressing other problem-dependent constants.

Here, $\epsilon$ is the desired accuracy beyond the permitted bias, $\gamma$ is the discount factor, and $\chi$ is a gradient-domination coefficient.

The guarantee concerns the last policy iterate, not an average over intermediate policies. It also requires neither Hessian-vector products nor Fisher preconditioning nor an auxiliary learned critic.

The crucial qualification lies in weak gradient domination:

This assumption connects the size of the projected policy gradient to global suboptimality. When $\psi>0$, the theorem permits a persistent gap from the optimum. The result therefore does not imply that arbitrary neural-network objectives can be optimized globally to any desired accuracy.

The authors also establish an information-theoretic lower bound in Theorem 3.1:

Using two difficult-to-distinguish MDPs with different optimal actions, they show that sufficiently accurate policy optimization can require this many trajectories in the worst case, for $\gamma\in[2/3,1)$ and sufficiently small $\epsilon$.

The upper and lower bounds agree on the $\epsilon^{-2}$ exponent. Their discount-horizon factors differ: the upper bound contains $(1-\gamma)^{-4}$, while the lower bound contains $(1-\gamma)^{-2}$.

Thus, nearly minimax-optimal describes the dependence on target accuracy, not a complete match in every parameter governing sample complexity.

Refreshes and momentum control accumulated estimation error

Defensive sampling addresses unstable off-policy corrections, but recursive gradient estimates introduce another problem: estimation errors can persist across successive updates.

LVR-PG combines two established approaches within one framework.

PAGE-style updates occasionally replace the recursive estimate with a larger-batch estimate. STORM-style updates instead use momentum to discount the influence of accumulated estimation error.

The common analysis summarizes their combined effect through

where $p$ is the refresh probability and $\alpha$ controls recursive momentum.

Setting $\alpha=0$ gives defensive PAGE-PG; setting $p=0$ gives defensive STORM-PG. The framework also permits hybrid configurations.

The importance of this unification is mathematical as well as architectural. Both defensive variants can attain the stated $\widetilde{\mathcal O}(\epsilon^{-2})$ rate under suitable parameter choices.

Theorem 5.1 specifies a sufficient parameter region: refresh probability and momentum each scale as $\mathcal O(B\epsilon^2)$, their sum is $\Omega(B\epsilon^2)$, initialization and refresh batches scale with $\epsilon^{-2}$, and the learning rate scales with $B\epsilon$.

This identifies how sampling, momentum, refreshes, and step size must be balanced for the proof. It does not prescribe universally optimal finite-budget hyperparameters.

Defensive STORM performs well in the tested control tasks

The experimental results provide a separate, narrower form of evidence.

The authors compare GPOMDP, N-PG-IGT, defensive PAGE, defensive STORM, and a selected hybrid LVR-PG configuration across CartPole-v1 and three MuJoCo locomotion environments.

Appendix I, Table 4 reports mean normalized area under the learning curve (AUC), with estimated standard errors from five independent runs:

Higher AUC indicates better learning-curve performance over the observed trajectory budget, within each environment.

Defensive STORM records the highest reported mean AUC on Swimmer, HalfCheetah, and Hopper. The hybrid configuration narrowly leads CartPole, where both approaches approach the maximum episodic return of 500 after approximately 1,000 training trajectories in the reported curves.

These are favorable finite-budget comparisons, but the large standard errors in several environments and absence of formal significance tests limit claims of superiority.

Two additional experimental components clarify interpretation.

The CartPole gradient diagnostic finds lower variability in individual trajectory gradient contributions for defensive STORM and hybrid LVR-PG over much of training. This is supporting mechanism evidence, not a direct measurement of the full recursive estimator’s variance.

The CartPole parameter ablations show sensitivity to configuration: larger tested momentum values improve defensive STORM performance, while more frequent refreshes improve the tested defensive PAGE configurations. These tests concern hyperparameter sensitivity, not an independent demonstration of the asymptotic theorem.

Fewer trajectories may still require more computation

For an RL engineering team, the business question is whether improved trajectory efficiency compensates for the computation needed to obtain it.

The paper’s theoretical unit is a sampled environment trajectory. That is not interchangeable with an environment transition, generated token, gradient-update step, or second of training time.

Defensive recursive estimation also requires access to current and previous policy parameters and trajectory likelihoods. These calculations and retained states contribute to computational and memory overhead.

Cognaptus inference: When trajectory generation is materially more expensive than the additional gradient-estimation work, defensive STORM is a reasonable candidate for controlled experimentation. When likelihood evaluation, policy-state storage, or optimizer computation dominates, the same algorithm may offer little total-cost advantage.

A decision-grade benchmark would compare the candidate against the existing estimator at matched training budgets and target returns, recording trajectories collected, environment steps, likelihood-evaluation time, memory consumption, wall-clock duration, and final policy quality.

The engineering team could then determine whether a lower trajectory requirement actually improves the workload’s cost-performance relationship. The theoretical rate alone cannot answer that question.

The gap between the theorem and deployed optimizers remains open

Three boundaries determine how far the result can be generalized.

First, the mathematical guarantee requires specific landscape and policy-score regularity conditions. The Fisher-non-degenerate specialization in Corollary 5.1 provides another route under additional assumptions, but retains a compatible-approximation and concentrability-related bias term. Uniform Fisher non-degeneracy can also fail as softmax policies approach determinism.

Second, the experiments use Adam and fixed trajectory horizons, whereas the main proof analyzes projected gradient ascent with accuracy-dependent step sizes and geometrically stopped trajectories. Empirical success under the former settings does not establish the theorem for those implementations.

Third, the evaluation covers small control-policy networks and four simulated tasks. No PPO, GRPO, RLHF, RLVR, transformer-policy, or language-model reasoning experiment is reported.

For language-model post-training researchers, the contribution therefore identifies an actor-only optimization direction worth investigating, especially where critic maintenance is costly. Whether it improves generated-token efficiency, training stability, memory use, or model quality remains untested.

The statistical result is a benchmark invitation

LVR-PG advances the theoretical understanding of actor-only policy optimization by combining bounded defensive corrections with recursive estimator-error control and establishing a near-minimax target-accuracy rate.

Its strongest result is conditional mathematical efficiency. The control experiments provide encouraging but limited evidence that defensive STORM can translate some of that efficiency into better learning curves.

For training-infrastructure teams, the next step is comparative measurement rather than immediate replacement. A defensible adoption decision requires establishing that trajectory savings survive the additional likelihood computations, retained policy state, and optimizer overhead on the workload that actually matters.

Cognaptus: Automate the Present, Incubate the Future.