A Variance-Reduced Cubic-Regularized Newton for Policy Optimization

2025/07/14 by Cheng Sun, Zhen Zhang, Sun, Cheng +3
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Advanced Control Systems Optimization #Advanced Multi-Objective Optimization Algorithms #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2507.10120

openalex publication_date 2025/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 O(ε^-3) to reach an ε-second-order stationary point, significantly improving upon the previous best result of O(ε^-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.

Citations

• Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction
• A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning
• Second-order optimization with lazy Hessians
• Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function
• PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation
• Sample Complexity of Policy Gradient Finding Second-Order Stationary Points
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Momentum-Based Variance Reduction in Non-Convex SGD
• Proximal Policy Optimization Algorithms
• Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step
• Trust Region Policy Optimization
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

Related

• A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning
• Efficiently Escaping Saddle Points for Policy Optimization
• Variance-Reduced Conservative Policy Iteration
• Variance-Reduced Off-Policy Memory-Efficient Policy Search
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction