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

arXiv: https://arxiv.org/abs/2610.03165 · HTML: https://mlsanity.com/paper/2610.03165/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 30 of its 54 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 30)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Learning to Walk in Minutes Using Massively Parallel Deep Reinforcement Learning](https://mlsanity.com/paper/2109.11978/) (2021)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Momentum-Based Policy Gradient Methods](https://mlsanity.com/paper/2007.06680/) (2020)
- [Stochastic Recursive Momentum for Policy Gradient Methods](https://mlsanity.com/paper/2003.04302/) (2020)
- [Smoothing Policies and Safe Policy Gradients](https://mlsanity.com/paper/1905.03231/) (2019)
- [Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method](https://mlsanity.com/paper/1609.03261/) (2016)
- [Policy Optimization with Stochastic Mirror Descent](https://mlsanity.com/paper/1906.10462/) (2019)
- [A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2003.00430/) (2020)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation](https://mlsanity.com/paper/2202.00308/) (2022)
- [Momentum-Based Policy Gradient with Second-Order Information](https://mlsanity.com/paper/2205.08253/) (2022)
- [Stochastic Variance Reduction for Policy Gradient Estimation](https://mlsanity.com/paper/1710.06034/) (2017)

## Built on by (most cited first, 1 of 1)

- [Variance-Reduced Policy Gradient is Nearly Minimax-Optimal](https://mlsanity.com/paper/2610.13692/) (2026)

## Abstract (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 Theta(ε-4) with bounded-variance one-policy feedback and Theta(ε-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.