Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

• Actor-only policy gradients avoid a separate critic, whose approximation error can introduce bias and whose maintenance adds memory and computational costs.This motivates improving trajectory efficiency without introducing a learned critic.Source: §1 · p. 1
• Existing actor-only guarantees fall short of the Ω(ϵ−2) lower bound and require assumptions on log-policy Hessians or importance-weight variance.The section identifies whether purely first-order methods can reach that bound as a central question.Source: §1 · p. 1
• The paper adapts a hard-instance construction to continuously parameterized policies satisfying WGD, proving an Ω(ϵ−2) worst-case trajectory requirement.The lower bound applies to any algorithm guaranteeing expected ϵ-optimality.Source: §1 · p. 2
• LVR-PG unifies gradient-only policy-gradient estimators with defensive importance sampling, including PAGE-PG and STORM-PG variants.Defensive sampling avoids assuming uniformly bounded importance-weight variance.Source: §1 · p. 2
• LVR-PG achieves last-iterate global convergence with sample complexity matching the lower bound up to logarithmic factors, without uniform importance-weight variance bounds or second-order regularity.The paper also reports that defensive STORM-PG has superior sample efficiency among the benchmarked configurations.Source: §1 · p. 3

• The agent interacts with an MDP using a differentiable parametric stochastic policy, and policy performance is its expected discounted return.The performance function is generally non-convex and bounded when per-step rewards are bounded.Source: §2 · p. 3
• Policy-gradient updates use projected stochastic gradient ascent over a closed convex parameter set, based on trajectory-derived gradient estimates.The generalized gradient mapping recovers the ordinary gradient in the unconstrained setting.Source: §2 · p. 3
• Geometric stopping yields unbiased estimates of the infinite-horizon discounted objective, with expected trajectory length (1 − γ)^−1.The empirical evaluation instead uses a fixed horizon.Source: §2 · p. 3
• Off-policy gradient estimation reuses trajectories collected under a different policy and applies importance sampling to preserve an unbiased estimate.Its variance scales with the χ2-divergence between trajectory distributions, which can be unbounded even for Gaussian policies.Source: §2 · pp. 3–4

• WGD permits local maxima whose performance is within ψ of the global optimum; zero bias recovers the stricter gradient-domination condition.In unconstrained settings, the projected gradient mapping reduces to the true gradient.Source: §3 · p. 4
• Theorem 3.1 establishes an Ω(ϵ−2) worst-case trajectory lower bound for expected ϵ-optimality under the stated regularity and WGD assumptions.The result extends the statistical barrier to policy optimization in the paper's setting.Source: §3 · p. 4
• Even when WGD has zero bias and excludes suboptimal stationary points, stochastic transition dynamics preserve irreducible estimation variance.The section relates this variance to the continuing Ω(ϵ−2) barrier.Source: §3 · p. 5
• The lower bound adapts to policy optimization because MDP interactions reveal states, actions, and rewards, while the tabular bound does not automatically survive restrictions enforcing gradient domination.Theorem 3.1 addresses both gaps under its stated assumptions.Source: §3 · p. 5
• The lower bound is independent of the update rule and does not imply that Hessian or Fisher information is necessary to attain the statistical limit.The section therefore motivates testing whether first-order recursive methods can match the bound.Source: §3 · p. 5

4 THE LVR-PG FRAMEWORK

• LVR-PG provides a unified framework for loopless, gradient-only estimators, recovering defensive STORM-PG and PAGE-PG with suitable parameter choices.The framework targets last-iterate global convergence at a rate matching the lower bound up to logarithmic factors and horizon terms.Source: §4 · p. 5
• Defensive importance sampling draws trajectories from a mixture of current and previous policies, bounding target-policy importance weights and preserving unbiased gradient estimates.The bound follows because each target trajectory density contributes positively to the mixture distribution.Source: §4 · p. 5

Algorithm 1: LVR-PG

• A refresh probability governs randomized full-batch versus mini-batch updates, while the momentum parameter controls how past gradient errors are discounted.Setting α = 0 recovers PAGE-PG; setting α > 0 yields the STORM-PG momentum update.Source: §4 · p. 5

11 Return θK

• A refresh samples N trajectories from the target policy for a full-batch gradient; otherwise, a mini-batch is drawn from a mixture behavior distribution to evaluate both policies.The mixture enables computation of the Defensive IS operator for the recursive update.Source: §11 · p. 6
• The momentum parameter α controls how past gradient errors are discounted, with α = 0 recovering DEF-PAGE-PG and α > 0 yielding DEF-STORM-PG.The framework uses the defensive versions of PAGE-PG and STORM-PG.Source: §11 · p. 6
• After computing the variance-reduced estimator, LVR-PG updates policy parameters by projected stochastic gradient ascent to maximize performance subject to the parameter constraint.Source: §11 · p. 6

5 CONVERGENCE AND OPTIMALITY

• The proof couples suboptimality descent with the estimator-variance recurrence, using a potential that combines the suboptimality gap and estimation error.The recurrence contracts for large potential values and gives a WGD-induced quadratic decrease at smaller values; stochastic estimation error contributes an additive term.Source: §5 · pp. 6–7
• LVR-PG achieves minimax-optimal sample complexity up to logarithmic factors and horizon terms, with a last-iterate guarantee using first-order updates and hyperparameters satisfying p, α = O(Bϵ^2) and p + α = Ω(Bϵ^2).The proof uses N, N0 = Θ(ϵ^-2) and η = Θ(Bϵ); Figure 1 depicts the nearly optimal hyperparameter region.Source: §5 · pp. 6–7, Figure 1 · p. 7

5.1 On Fisher-Non-Degeneracy

• For unconstrained policies, uniformly non-degenerate Fisher information and bounded compatible approximation error imply WGD; under finite concentrability, the corollary preserves the theorem’s minimax-optimal sample complexity.The compatible approximation error is evaluated under the current policy’s state-action distribution, with the concentrability coefficient entering the irreducible bias.Source: §5.1 · pp. 7–8

6 EXPERIMENTAL RESULTS

• The evaluation uses CartPole-v1 and Swimmer-v4, representing classic control and MuJoCo locomotion tasks.Source: §6 · p. 8
• DEF-STORM-PG uses momentum-based recursive gradient estimates with defensive importance sampling and no full-batch refreshes.The comparisons include GPOMDP, N-PG-IGT, and DEF-PAGE-PG.Source: §6 · p. 8
• Across both environments, DEF-STORM-PG reaches high returns with fewer trajectories than GPOMDP and DEF-PAGE-PG; on CartPole-v1 it has fewer oscillations than N-PG-IGT.In Swimmer-v4, N-PG-IGT converges quickly to a local optimum.Source: §6 · p. 8

7 CONCLUSIONS

• Purely first-order policy-gradient methods achieve minimax-optimal sample complexity up to logarithmic factors and horizon terms, without second-order assumptions.Source: §7 · p. 8
• Defensive importance sampling requires mixture-distribution trajectory evaluation and storage of both current and previous policy parameters, motivating variance reduction without explicit double sampling.The paper also identifies extending the framework to adaptive gradient methods as future work.Source: §7 · p. 8

AI use statement

• The authors report using generative AI for text polishing, proof assistance, and code generation, while stating that research ideas and the literature review were not AI-generated.Source: AI use statement · p. 9

CHECKLIST

• The paper reports that assumptions are defined in Section 3 and proofs are provided in the appendix.It also says the framework is described in Sections 2–4 and its complexity properties are proved.Source: CHECKLIST · p. 11
• Code and experimental training details are provided in the supplementary material and Appendix I, respectively.The checklist also reports that plots describe their measures and Appendix I covers the computing infrastructure.Source: CHECKLIST · p. 11
• The checklist marks human-subject materials and participant-risk, wage, and compensation information as not applicable.It reports that the code is in the supplementary materials and identifies no applicable asset-license information.Source: CHECKLIST · p. 11

19 Return θK

• Geometric stopping terminates each trajectory with probability 1 − γ, giving expected trajectory length (1 − γ)^−1 without arbitrary truncation.The stated purpose is to keep gradient estimates unbiased for the infinite-horizon objective.Source: A LOOPLESS VARIANCE-REDUCED POLICY… · p. 12

A LOOPLESS VARIANCE-REDUCED POLICY GRADIENT (LVR-PG)

• Bernoulli refresh decisions switch LVR-PG between full-batch gradient refreshes and recursive mini-batch updates using historical information.The generic template tracks a recursive gradient estimator at each iteration.Source: A LOOPLESS VARIANCE-REDUCED POLICY… · p. 12

B MEAN-SQUARED SMOOTHNESS

• The defensive mixture qξ combines the consecutive policies’ trajectory distributions to control importance-weight variance in the recursive gradient difference.The supplied lemma states that the unified mean-squared smoothness constant is strictly bounded for ξ in (0, 1).Source: B MEAN-SQUARED SMOOTHNESS · p. 13
• Defensive importance sampling strictly bounds mean-squared smoothness under mean-square score continuity, without uniform variance or arbitrary Hessian-limit assumptions.DEF-PAGE-PG and DEF-STORM-PG share the same consecutive-estimation bound because they use the same gradient estimator and defensive mixture.Source: B MEAN-SQUARED SMOOTHNESS · pp. 13, 15

C ON FISHER-NON-DEGENERACY

• The Fisher-non-degeneracy condition requires the Fisher information matrix to remain uniformly positive definite, excluding redundant or flat parameter directions.The text describes the matrix as a well-behaved preconditioner in the natural policy-gradient update.Source: C ON FISHER-NON-DEGENERACY · p. 15
• For Gaussian policies with fixed covariance and a linearly parameterized mean, Fisher non-degeneracy holds globally exactly when feature covariance is positive definite.This requires linearly independent basis functions and sufficiently rich state-distribution coverage.Source: C ON FISHER-NON-DEGENERACY · p. 16
• Softmax policies approaching determinism can lose global Fisher non-degeneracy as Fisher entries vanish for actions whose probabilities approach zero.The text says architectural constraints or regularization are needed for strict global non-degeneracy in this case.Source: C ON FISHER-NON-DEGENERACY · p. 16
• The approximation-error condition is evaluated under the current policy’s state-action distribution, unlike STORM-PG-S’s condition under the unknown optimal policy distribution.The text motivates this choice by noting that the current policy’s state-action distribution is observable through the policy being optimized.Source: C ON FISHER-NON-DEGENERACY · p. 16
• The Fisher-induced gradient-domination lemma is stated for Fisher-non-degenerate policies under the listed regularity and approximation assumptions, with an additional bounded distribution-ratio condition.The lemma’s displayed conclusion is not included in the supplied passage.Source: C ON FISHER-NON-DEGENERACY · p. 16
• The formulation isolates approximation error under the current-policy distribution, while the later gradient-domination lemma accounts for mismatch in state-action visitation through a concentrability coefficient.The text identifies the representational penalty as ε_bias and the visitation penalty as κ.Source: C ON FISHER-NON-DEGENERACY · pp. 16–17

D INTERMEDIATE RESULTS

• For γ sufficiently close to 1, the geometrically stopped GPOMDP estimator has the stated standard O((1 − γ)^−3) variance bound.The bound follows under the stated assumption on policy scores.Source: D INTERMEDIATE RESULTS · pp. 17–18
• The appendix gives a smoothness result for expected return under bounded rewards, convex parameters, and the stated policy-score assumptions.The supplied passages show the lemma heading and a bound proportional to parameter distance, but not the complete expression.Source: D INTERMEDIATE RESULTS · p. 18
• The LVR-PG estimation error is analyzed through a recurrence that depends on the refresh probability, momentum parameter, batch sizes, and defensive-weight bound.The proof separates full-batch refresh and recursive momentum-update cases.Source: D INTERMEDIATE RESULTS · pp. 20–21

E CONVERGENCE

• The convergence section presents sample-complexity results for LVR-PG, DEF-PAGE-PG, and DEF-STORM-PG, plus a Fisher-non-degenerate-policy corollary.The supplied passage identifies these results but does not include their quantitative bounds.Source: E CONVERGENCE · p. 22

E.1 Proof of Theorem 5.1

• The proof couples suboptimality and estimator-variance recurrences in a potential, then establishes a last-iterate descent recurrence to obtain the convergence bound.The potential is Φk := rk + c∆k, which upper-bounds suboptimality; the proof analyzes the nonnegative sequence max{0, Φk} to ensure descent after entering the target region.Source: §E.1 · pp. 22, 24, 25
• For fixed B, LVR-PG achieves n = Õ(ϵ^-2) as ϵ → 0, with minimax-optimal dependence on accuracy up to logarithmic factors and explicit dependence on the effective horizon.Theorem 5.1 guarantees J* − E[J(θK)] ≤ ψ + ϵ under Assumptions 3.1–3.2; the stated scaling treats policy-regularity and defensive-mixture constants as fixed.Source: §E.1 · pp. 22, 23, 27
• The theorem uses N = N0 = Θ(ϵ^-2), η = Θ(Bϵ), and hyperparameters p, α = O(Bϵ^2) with p + α = Ω(Bϵ^2).It also specifies fixed mini-batch size B ≥ 1 and ξ = 1/2.Source: §E.1 · pp. 22, 26

E.2 Corollaries of Theorem 5.1

• DEF-PAGE-PG is the α = 0 specialization of the variance recurrence, with refresh probability p = 1/N and expected per-iteration cost 1 + (1 − 1/N)B.The corollary states a sample-complexity guarantee under Assumptions 3.1–3.2 for fixed B and sufficiently small ϵ; its displayed bound is not legible in the supplied passage.Source: §E.2 · pp. 28–29
• With p = 0 and ξ = 1/2, DEF-STORM-PG guarantees a gap of at most ψ + ϵ; for fixed batch size and constants, the complexity bound is dominated by ϵ^-2 terms.The guarantee holds for a suitable choice of momentum, initial batch size, and learning rate.Source: §E.2 · pp. 29–30

F SAMPLE COMPLEXITY UNDER FISHER-NON-DEGENERACY

• Under Fisher non-degeneracy with κ finite and Θ = R^d, LVR-PG inherits weak gradient domination with χ = C1/µF and ψ = √(ϵbiasκ)/(1 − γ).Substituting these constants into Theorem 5.1 gives the stated suboptimality and sample-complexity guarantees.Source: F SAMPLE COMPLEXITY UNDER… · p. 30

G LOWER-BOUND

• The lower-bound construction uses two hard MDPs and a constrained continuous policy class satisfying Assumptions 3.1–3.2 with χ = 4/3 and ψ = 0.The instances differ by a small transition perturbation, making them difficult to distinguish while requiring mutually exclusive optimal policies.Source: G LOWER-BOUND · pp. 30–31
• The two-instance testing argument establishes a trajectory-complexity lower bound for adaptive algorithms, including those with random trajectory counts.Le Cam’s and Pinsker’s inequalities yield an information requirement; the transcript KL bound depends only on transition dynamics, with active-state visits controlling information per trajectory.Source: G LOWER-BOUND · pp. 36–38

H TECHNICAL LEMMAS

• Under the stated noise bounds, a recurrence with effective contraction rate min{aϵ, b} reaches x_k ≤ ϵ within a sufficient iteration count and stays there.The target neighborhood is invariant once reached.Source: H TECHNICAL LEMMAS · p. 39

I EXPERIMENTAL DETAILS; Policies and Implementation; Algorithms; Performance Measures

• The experiments compare defensive-IS STORM, PAGE, and hybrid configurations with GPOMDP and N-PG-IGT, using normalized AUC to summarize returns across four environments.LVR-PG denotes the best-performing hybrid configuration; the reported AUC comparison says its momentum-only configuration performs consistently better than competitors in almost all environments.Source: I EXPERIMENTAL DETAILS · p. 40, Algorithms · p. 41, Performance Measures · p. 41

I.1 CartPole-v1

• On CartPole-v1, DEF-STORM-PG and LVR-PG approach the maximum return of 500 after approximately 103 trajectories, while N-PG-IGT shows greater training variance.Both improve faster than GPOMDP and DEF-PAGE-PG.Source: §I.1 · p. 41, Figure 5 · p. 42

I.2 Swimmer-v4; I.3 HalfCheetah-v4; I.4 Hopper-v4

• On Swimmer-v4, DEF-STORM-PG has the highest returns; on HalfCheetah-v4 it reaches the best return, while Hopper-v4 favors DEF-STORM-PG and N-PG-IGT.N-PG-IGT saturates at a lower reward than DEF-STORM-PG on HalfCheetah; on Hopper, DEF-PAGE-PG and GPOMDP learn more slowly than momentum-based algorithms.Source: §I.2 · p. 42, Figure 6 · p. 42, §I.3 · p. 43

I.5 Gradient-Estimator Variability on CartPole-v1

• The CartPole-v1 gradient-variability diagnostic examines the trace of the sample covariance of per-trajectory, unweighted, baseline-free GPOMDP contributions.The supplied passages describe the diagnostic but do not report its findings.Source: §I.5 · pp. 43–44
• The statistic summarizes variability in per-trajectory gradient contributions evaluated at current policy parameters using each algorithm’s collected batches.GPOMDP and N-PG-IGT use on-policy batches, while LVR-PG configurations use defensive-mixture batches.Source: §I.5 · p. 44
• DEF-STORM-PG and the hybrid LVR-PG configuration show lower per-trajectory gradient variability than the baselines over much of training.The diagnostic covers 5 × 10^3 training trajectories, averages over five independent runs, and uses a base-10 logarithmic scale.Source: Figure 9 · p. 44, §I.5 · p. 44
• DEF-PAGE-PG achieves lower per-trajectory gradient variability than GPOMDP, while N-PG-IGT values increase over the observed budget.Source: §I.5 · p. 44

I.6 Hyperparameter Ablations on CartPole-v1

• Returns near 500 for p = 0.5 and p = 0.9, versus near 400 for p = 0.1, show that more frequent refreshes improve DEF-PAGE-PG's final performance.The results are consistent with using larger on-policy batches to control gradient-estimation variance.Source: §I.6 · pp. 44–45, Figure 10 · p. 44
• α = 0.9 rapidly reaches returns close to 500; α = 0.5 takes substantially more trajectories, while α = 0.1 fluctuates and does not solve CartPole-v1.The best-performing setting uses a smaller historical correction because that correction is weighted by 1 − α.Source: Figure 10 · p. 44, §I.6 · p. 45

I.7 Hyperparameter Grid Search for LVR-PG on CartPole-v1

• 453.5±7.2 mean AUC at (α, p) = (0.9, 0.5) is the grid's largest, while three configurations reach mean terminal return 500 at displayed precision.The other two configurations are (0.5, 0.3) and (0.01, 0.5); their mean AUC values differ.Source: §I.7 · p. 45, Figure 11 · p. 45

I.8 Computational Resources

• Experiments ran on a 2023 14-inch MacBook Pro with an Apple M2 Pro chip and 16 GB of RAM.Source: §I.8 · p. 46