# A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 40 references that are in the map.
- First posted on arXiv 21 Apr 2023.

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

- [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)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [Improved Image Captioning via Policy Gradient optimization of SPIDEr](https://mlsanity.com/paper/1612.00370/) (2016)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Policy Gradient for Coherent Risk Measures](https://mlsanity.com/paper/1502.03919/) (2015)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Accelerated Methods for Non-Convex Optimization](https://mlsanity.com/paper/1611.00756/) (2016)
- [Sample Complexity of Policy Gradient Finding Second-Order Stationary Points](https://mlsanity.com/paper/2012.01491/) (2020)
- [A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points](https://mlsanity.com/paper/1707.08028/) (2017)
- [Batch Policy Gradient Methods for Improving Neural Conversation Models](https://mlsanity.com/paper/1702.03334/) (2017)
- [Reinforcement Learning of Speech Recognition System Based on Policy Gradient and Hypothesis Selection](https://mlsanity.com/paper/1711.03689/) (2017)
- [Smoothed functional-based gradient algorithms for off-policy reinforcement learning: A non-asymptotic viewpoint](https://mlsanity.com/paper/2101.02137/) (2021)
- [A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization](https://mlsanity.com/paper/2208.00290/) (2022)

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

- [Policy Newton Algorithm in Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2506.01597/) (2025)
- [Efficiently Escaping Saddle Points for Policy Optimization](https://mlsanity.com/paper/2311.08914/) (2023)
- [A Variance-Reduced Cubic-Regularized Newton for Policy Optimization](https://mlsanity.com/paper/2507.10120/) (2025)
- [Policy Newton methods for Distortion Riskmetrics](https://mlsanity.com/paper/2508.07249/) (2025)
- [Generalized Random Direction Newton Algorithms for Stochastic Optimization](https://mlsanity.com/paper/2602.19893/) (2026)
- [Second-Order Actor-Critic Methods for Discounted MDPs via Policy Hessian Decomposition](https://mlsanity.com/paper/2605.14982/) (2026)
- [Bellman-Certified Rounding for Sparse Policy Deployment in MDPs](https://mlsanity.com/paper/2610.00325/) (2026)

## Abstract (arXiv)

We consider the problem of control in the setting of reinforcement learning (RL), where model information is not available. Policy gradient algorithms are a popular solution approach for this problem and are usually shown to converge to a stationary point of the value function. In this paper, we propose two policy Newton algorithms that incorporate cubic regularization. Both algorithms employ the likelihood ratio method to form estimates of the gradient and Hessian of the value function using sample trajectories. The first algorithm requires an exact solution of the cubic regularized problem in each iteration, while the second algorithm employs an efficient gradient descent-based approximation to the cubic regularized problem. We establish convergence of our proposed algorithms to a second-order stationary point (SOSP) of the value function, which results in the avoidance of traps in the form of saddle points. In particular, the sample complexity of our algorithms to find an ε-SOSP is O(ε-3.5), which is an improvement over the state-of-the-art sample complexity of O(ε-4.5).