Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Leonardo Cesani; Matteo Papini; Marcello Restelli

cs.LGOct 9, 2026

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Authors: Leonardo Cesani, Matteo Papini, Marcello Restelli

Organizations: Politecnico di Milano · Universit`a degli Studi di Milano

Abstract

Standard Policy Gradient (PG) algorithms suffer from high estimation variance because they rely on Monte Carlo updates. While off-policy variance reduction mitigates this problem, establishing optimal sample complexity currently requires either restrictive assumptions, such as uniformly bounded importance weights, or impractical second-order operations. In this work, we introduce Loopless Variance-Reduced PG (LVR-PG), a unified theoretical framework that abstracts a class of first-order estimators that integrate recursive updates with defensive importance sampling, including known estimators such as PAGE-PG and STORM-PG. We prove that this algorithmic class achieves $\tilde{\mathcal{O}}(ε^{-2})$ last-iterate global convergence under weak gradient domination for general parametric policies. We establish this guarantee using purely first-order updates, with minimal assumptions and without gradient preconditioners. By extending state-of-the-art lower bounds to continuous parametric policies, we establish an $Ω(ε^{-2})$ sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms.

Figures & tables

Algorithm	Complexity †	Convergence Type	Gradient Only	No 2nd-Order Asm.	No Bounded IW Asm.
GPOMDP ( Montenegro et al., 2024 )	$\tilde{\mathcal{O}}(\epsilon^{-3})$	Last-iterate	✓	✗	✓
SRVR-PG ( Liu et al., 2020 )	$\mathcal{O}(\epsilon^{-3})$	Average-iterate	✓	✗	✗
STORM-PG-S ( Ding et al., 2022 )	$\mathcal{O}(\epsilon^{-3})$	Average-iterate	✓	✗	✗
N-PG-IGT ‡ ( Fatkhullin et al., 2023 )	$\tilde{\mathcal{O}}(\epsilon^{-2.5})$	Last-iterate	✓	✗	✓
HARPG ‡ ( Fatkhullin et al., 2023 )	$\tilde{\mathcal{O}}(\epsilon^{-2})$	Last-iterate	✗	✗	✓
ANPG ( Mondal and Aggarwal, 2024 )	$\mathcal{O}(\epsilon^{-2})$	Average-iterate	✗	✗	✓

Table 1: Comparison of sample complexities and theoretical assumptions used for variance-reduced PG algorithms. Complexity denotes the number of trajectories required to reach the global optimal policy. Convergence Type , last-iterate or average-iterate guarantees, denotes the necessary number of trajectories for any algorithm to return an

\epsilon

-optimal policy. Gradient Only denotes an algorithm that does not use second-order or Fisher information. No 2nd-Order Asm. denotes algorithms which do not require assumptions on the Hessian matrix of the log-policy. No Bounded IW Asm. indicates algorithms not requiring an assumption on the boundedness of the variance of the importance weights. † The

\mathcal{O}(\cdot)

hides dependencies on

\gamma,C_{1},L_{S},\chi

and

\psi

\widetilde{\mathcal{O}}(\cdot)

hides logarithmic factors. ‡ Requires an additional second-order smoothness assumption.

Panel of Figure 1 — Figure 1: The continuous algorithmic design space of LVR-PG in normalized coordinates. The shaded region delineates the manifold of hyperparameter configurations $(p,\alpha)$ that satisfy the stability thresholds derived in Theorem 5.1 . In this region, a configuration of LVR-PG is nearly optimal. GPOMDP falls out of this region, since $p=1$ .

Panel of Figure 2 — Figure 2: Comparison of DEF-STORM-PG , DEF-PAGE-PG , N-PG-IGT , and GPOMDP . Shaded regions indicate the estimated standard error of the mean.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Algorithm	Refresh Prob. $p$	Momentum $\alpha$	Defensive Parameter $\xi$
PAGE-PG Gargiani et al. (2022)	$p\in(0,1)$	$\alpha=0$	$\xi=0$
STORM-PG Yuan et al. (2020)	$p=0$	$\alpha\in(0,1)$	$\xi=0$
DEF-PAGE-PG Paczolay et al. (2024)	$p\in(0,1)$	$\alpha=0$	$\xi\in[0,1]$
DEF-STORM-PG Paczolay et al. (2024)	$p=0$	$\alpha\in(0,1)$	$\xi\in[0,1]$

Appendix

Table 2: Instantiations of the LVR-PG Framework

Instance	$J^{(i)}(\theta)$	$J^{*,(i)}$	$\big\\|\nabla_{\theta}J^{(i)}(\theta)\big\\|_{2}$
$\mathcal{M}_{1}$	$\frac{R_{\max}}{1-\gamma(p+\theta\delta)}$	$\frac{R_{\max}}{1-\gamma(p+(1-\alpha)\delta)}$	$\frac{\gamma\delta R_{\max}}{(1-\gamma(p+\theta\delta))^{2}}$
$\mathcal{M}_{2}$	$\frac{R_{\max}}{1-\gamma(p+(1-\theta)\delta)}$	$\frac{R_{\max}}{1-\gamma(p+(1-\alpha)\delta)}$	$\frac{\gamma\delta R_{\max}}{(1-\gamma(p+(1-\theta)\delta))^{2}}$

Appendix

Table 3: Values for

J^{(i)}(\theta)

J^{*,(i)}

, and

\big\|\nabla_{\theta}J^{(i)}(\theta)\big\|_{2}

for the

\mathcal{M}

instances.

Environment	GPOMDP	DEF-STORM-PG	DEF-PAGE-PG	LVR-PG	N-PG-IGT
Cart-Pole	$396.05\pm 34.56$	$481.90\pm 7.85$	$417.34\pm 37.96$	$\mathbf{482.39\pm 5.49}$	$380.03\pm 39.46$
Swimmer	$24.19\pm 6.15$	$\mathbf{40.86\pm 7.94}$	$26.39\pm 5.46$	$33.90\pm 13.28$	$26.22\pm 1.01$
Half-Cheetah	$13.49\pm 30.16$	$\mathbf{105.76\pm 51.57}$	$24.08\pm 32.67$	$55.82\pm 41.76$	$87.67\pm 23.31$
Hopper	$201.90\pm 21.68$	$\mathbf{369.94\pm 89.62}$	$233.65\pm 28.36$	$309.13\pm 44.92$	$368.81\pm 23.97$

Appendix

Table 4: Mean normalized area under the learning curve (AUC) across the four environments; the

\pm

indicate the estimated standard error of the mean. Bold entries indicate the largest mean AUC in each environment.

Environment	Horizon $T$	Batch $N$	Mini-batch $B$	Learning rate $\eta$	Initial std $\sigma$
CartPole-v1	$500$	$50$	$5$	$10^{-2}$	–
Swimmer-v4	$500$	$100$	$10$	$10^{-3}$	$1$
HalfCheetah-v4	$100$	$256$	$16$	$10^{-4}$	$\sqrt{0.3}$
Hopper-v4	$100$	$256$	$16$	$10^{-4}$	$0.3$

Appendix

Table 5: Environment-specific hyperparameter choices for the experiments.

Hyperparameter	GPOMDP	DEF-STORM-PG	DEF-PAGE-PG	LVR-PG	N-PG-IGT
Refresh probability $p$	–	$0$	$0.5$	$0.1^{*}$	–
Recursive parameter $\alpha$	–	$0.9$	$0$	$0.9$	$0.9$
Defensive parameter $\xi$	–	$0.5$	$0.5$	$0.5$	–

Appendix

Table 6: Algorithmic settings for the return comparisons. ( ∗ The hybrid uses

p=0.5

on CartPole-v1.) For N-PG-IGT ,

\alpha

denotes its gradient-transport momentum parameter.

Figure 5: Learning curves on CartPole-v1. Curves show mean evaluation returns over five runs; shaded regions indicate the estimated standard error of the mean.

Figure 6: Learning curves on Swimmer-v4. Curves show mean evaluation returns over five runs; shaded regions indicate the estimated standard error of the mean.

Figure 7: Learning curves on HalfCheetah-v4. Curves show mean evaluation returns over five runs; shaded regions indicate the estimated standard error of the mean.

Figure 8: Learning curves on Hopper-v4. Curves show mean evaluation returns over five runs; shaded regions indicate the estimated standard error of the mean.

Figure 9: Per-trajectory gradient-variability diagnostic on CartPole-v1 over

5\times 10^{3}

training trajectories. Values are shown on a base-

10

logarithmic scale and averaged over five independent runs; shaded regions indicate the estimated standard error of the mean.

Figure 10: Hyperparameter ablations on CartPole-v1 over

10^{4}

training trajectories. Left: Refresh probability

p\in\{0.1,0.5,0.9\}

for DEF-PAGE-PG . Right: Recursive-update parameter

\alpha\in\{0.1,0.5,0.9\}

for DEF-STORM-PG . Curves show mean evaluation returns over five runs, shaded regions indicate the estimated standard error of the mean.

Panel of Figure 11 — Figure 11: Hybrid hyperparameter grid on CartPole-v1. Left: Mean normalized AUC. Right: Mean terminal return, averaged over the last three evaluations in each run. Entries summarize five independent runs; shaded regions indicate the estimated standard error of the mean.

Policy Gradient

Policy gradient methods improve a decision-making policy by estimating how its actions affect expected reward.

See all 68 papers

Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
Oct 2, 2026Gabor Paczolay, Matteo Papini, Alberto Maria Metelli +2Policy Gradient Policy Gradient Methods
Politecnico di Milano. · Budapest University of Technology and Economics. · University of Milan.
Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions
May 13, 2026Ishaq Hamza, Zaiwei ChenPolicy Gradient Last-Iterate Convergence
IISc · Edwardson School of Industrial Engineering, Purdue University · Purdue IE
Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards
Oct 11, 2026Yibo Wang, Yuanxin Liu, Zhaoran WangReinforcement Learning with Verifiable Rewards Policy Gradient Methods

Oct 2, 2026J/K move · Enter open · S save

Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds

Gabor Paczolay, Matteo Papini, Alberto Maria Metelli, Istvan Harmati+1

Politecnico di Milano. · Budapest University of Technology and Economics. · University of Milan.

Policy Gradient Policy Gradient Methods Policy Optimization Sample-Efficient RL Importance Sampling for RL Importance Sampling

Open paper AskPDF arXiv

Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved

O(ε^{-3})

sample complexity to find an

ε

-stationary point, under an unrealistic assumption on the variance of the importance weights. In this paper, we propose the \algo (Defensive Policy Gradient) algorithm, based on defensive importance sampling, which achieves the same rate without any assumption on the variance of ordinary importance weights. We also establish lower bounds in a generalized black-box policy-optimization model that hides states and actions and permits parameter-dependent rewards. In this model, the optimal rates are

Θ(ε^{-4})

with bounded-variance one-policy feedback and

Θ(ε^{-3})

with mean-square-smooth coupled two-policy feedback. Under standard policy-regularity conditions, REINFORCE and \algo realize the corresponding oracle conditions and attain the

O(ε^{-4})

and

O(ε^{-3})

upper bounds, respectively. Although the lower bounds do not apply directly to the classical MDP interaction model in which these algorithms operate, this correspondence provides oracle-level evidence that the faster rate of \algo is optimal and genuinely separated from that of vanilla policy gradient.

Abstract

Policy Gradient

Explore similar work

Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds

Achieving ε−2ε^{-2}ε−2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions