A Variance-Reduced Cubic-Regularized Newton for Policy Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915388599566336 |
|---|---|
| author | Sun, Cheng Zhang, Zhen Yang, Shaofu |
| author_facet | Sun, Cheng Zhang, Zhen Yang, Shaofu |
| contents | 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 $\tilde{\mathcal{O}}(ε^{-3})$ to reach an $ε$-second-order stationary point, significantly improving upon the previous best result of $\tilde{\mathcal{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10120 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Variance-Reduced Cubic-Regularized Newton for Policy Optimization Sun, Cheng Zhang, Zhen Yang, Shaofu Machine Learning Artificial Intelligence 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 $\tilde{\mathcal{O}}(ε^{-3})$ to reach an $ε$-second-order stationary point, significantly improving upon the previous best result of $\tilde{\mathcal{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. |
| title | A Variance-Reduced Cubic-Regularized Newton for Policy Optimization |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2507.10120 |