mlsanityData to 14 Oct 2026

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

arXiv 2610.13692 ↗First posted 9 Oct 2026cs.LG cs.AIcited by 0

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

Abstract (arXiv)

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 tildeO(ε-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 Omega(ε-2) sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 23 of its 54 references that are in the map. First posted on arXiv 9 Oct 2026.

Builds on

23 of 54 references.

Closest ancestors · 2

Same direction, newest first

  1. 2026Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds2 Oct
  2. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradients3 May

Other references · 21

  1. 2023GPT-4 Technical Reportcited by 18,396
  2. 2022Training language models to follow instructions with human feedbackcited by 15,971
  3. 2017Proximal Policy Optimization Algorithmscited by 15,215
  4. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  5. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  6. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,720
  7. 2019Fine-Tuning Language Models from Human Preferencescited by 2,150
  8. 2023RRHF: Rank Responses to Align Language Models with Human Feedback without tearscited by 463
  9. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  10. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  11. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  12. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
9 more
  1. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  2. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  3. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 26
  4. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  5. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 24
  6. 2019Smoothing Policies and Safe Policy Gradientscited by 21
  7. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 20
  8. 2022Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequalitycited by 20
  9. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 17

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025A Variance-Reduced Cubic-Regularized Newton for Policy Optimization
  2. 2026Beyond Importance Sampling: Rejection-Gated Policy Optimization
  3. 2024Policy Gradient with Active Importance Sampling
  4. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction
  5. 2025Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Data
  6. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
  7. 2026Beyond Softmax and Entropy: Convergence Rates of Policy Gradients with f-SoftArgmax Parameterization & Coupled Regularization
  8. 2025Reusing Trajectories in Policy Gradients Enables Fast Convergence