# A Variance-Reduced Cubic-Regularized Newton for Policy Optimization

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

## 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.

## 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, 15 of 15)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [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)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step](https://mlsanity.com/paper/1612.00547/) (2016)
- [Sample Complexity of Policy Gradient Finding Second-Order Stationary Points](https://mlsanity.com/paper/2012.01491/) (2020)
- [PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation](https://mlsanity.com/paper/2202.00308/) (2022)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2304.10951/) (2023)
- [Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction](https://mlsanity.com/paper/2401.01084/) (2024)

## 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.