mlsanityData to 14 Oct 2026

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

arXiv 2610.03165 ↗First posted 2 Oct 2026cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

Key facts. Cited by 1 paper 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.

Builds on

30 of 54 references.

References · 30

  1. 2023GPT-4 Technical Reportcited by 18,396
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  4. 2021Learning to Walk in Minutes Using Massively Parallel Deep Reinforcement Learningcited by 512
  5. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  6. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  7. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  8. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  9. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  10. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  11. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  12. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
18 more
  1. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  2. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  3. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  4. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  5. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  6. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  7. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  8. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 40
  9. 2020Momentum-Based Policy Gradient Methodscited by 30
  10. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 24
  11. 2019Smoothing Policies and Safe Policy Gradientscited by 21
  12. 2016Less than a Single Pass: Stochastically Controlled Stochastic Gradient Methodcited by 18
  13. 2019Policy Optimization with Stochastic Mirror Descentcited by 18
  14. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 18
  15. 2021Bregman Gradient Policy Optimizationcited by 17
  16. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 17
  17. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 13
  18. 2017Stochastic Variance Reduction for Policy Gradient Estimationcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Variance-Reduced Policy Gradient is Nearly Minimax-Optimalcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Policy Gradient with Active Importance Sampling
  2. 2026Beyond Importance Sampling: Rejection-Gated Policy Optimization
  3. 2024Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysis
  4. 2024Reusing Historical Trajectories in Natural Policy Gradient via Importance Sampling: Convergence and Convergence Rate
  5. 2025A Variance-Reduced Cubic-Regularized Newton for Policy Optimization
  6. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
  7. 2026Rethinking Importance Sampling in LLM Policy Optimization: A Cumulative Token Perspective
  8. 2026Achieving ε-2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions