mlsanityData to 14 Oct 2026

A Variance-Reduced Cubic-Regularized Newton for Policy Optimization

arXiv 2507.10120 ↗First posted 14 Jul 2025cs.LG cs.AIcited by 0

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

Abstract (arXiv)

In this paper, we study a second-order approach to policy optimization in reinforcement learning. Existing second-order methods often suffer from suboptimal sample complexity or rely on unrealistic assumptions about importance sampling. To overcome these limitations, we propose VR-CR-PN, a variance-reduced cubic-regularized policy Newton algorithm. To the best of our knowledge, this is the first algorithm that integrates Hessian-aided variance reduction with second-order policy optimization, effectively addressing the distribution shift problem and achieving best-known sample complexity under general nonconvex conditions but without the need for importance sampling. We theoretically establish that VR-CR-PN achieves a sample complexity of tildeO(ε-3) to reach an ε-second-order stationary point, significantly improving upon the previous best result of tildeO(ε-3.5) under comparable assumptions. As an additional contribution, we introduce a novel Hessian estimator for the expected return function, which admits a uniform upper bound independent of the horizon length H, allowing the algorithm to achieve horizon-independent sample complexity.

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 15 of its 26 references that are in the map. First posted on arXiv 14 Jul 2025.

Builds on

15 of 26 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction2 Jan

Other references · 14

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  4. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  6. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  7. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  8. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  9. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 20
  10. 2016Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Stepcited by 18
  11. 2020Sample Complexity of Policy Gradient Finding Second-Order Stationary Pointscited by 17
  12. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 17
2 more
  1. 2022Second-order optimization with lazy Hessianscited by 15
  2. 2023A Cubic-regularized Policy Newton Algorithm for Reinforcement Learningcited by 7

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Policy Gradient with Second Order Momentum
  2. 2026Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
  3. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
  4. 2026Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
  5. 2024Revisiting Scalable Hessian Diagonal Approximations for Applications in Reinforcement Learning
  6. 2025Second-Order Policy Gradient Methods for the Linear Quadratic Regulator
  7. 2026Second-Order Actor-Critic Methods for Discounted MDPs via Policy Hessian Decomposition
  8. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework