Adaptive Momentum-Based Policy Gradient with Second-Order Information

Saber Salehkaleybar, Sadegh Khorasani, Negar Kiyavash, Niao He, Patrick ThiranarXiv 2022 · OpenReview

Abstract

Policy Gradient (PG) methods are fundamental to Reinforcement Learning (RL) but are frequently hindered by high variance and sample inefficiency. Traditional variance reduction techniques often rely on Importance Sampling (IS) to handle non-stationary data distributions, which introduces instability and requires large batch sizes. We present SHARP (Stochastic Hessian Aided Recursive Policy gradient), a novel algorithm that utilizes second-order information to achieve optimal convergence rates without the need for IS or large batches.

Introduction

In the landscape of Reinforcement Learning, Policy Gradient (PG) methods have become the standard for solving complex continuous control tasks. However, their practical application is often hindered by the high variance of gradient estimates. Because these gradients are derived from stochastic trajectories, the resulting noise can lead to slow convergence or catastrophic instability during training.

To mitigate this, variance reduction techniques have been adapted from supervised learning. However, RL presents a unique challenge: non-stationarity. As an agent learns, its policy changes, which in turn alters the distribution of trajectories it experiences. Standard methods attempt to correct this shift using Importance Sampling (IS), but IS is notorious for "weight explosion," where small differences in policies lead to massive variance in the re-weighted gradients.

The SHARP Algorithm

The Stochastic Hessian Aided Recursive Policy gradient (SHARP) algorithm introduces a paradigm shift by replacing Importance Sampling with second-order information.

Second-Order Correction

Instead of re-weighting historical data, SHARP employs an unbiased estimate of a Hessian-vector product. This term acts as a predictive correction, estimating how the gradient would have evolved as the policy parameters moved from the previous iteration to the current one. By incorporating this curvature information, the algorithm can update its gradient estimate recursively without looking back at old data distributions through the lens of IS.

Momentum and Normalization

SHARP integrates this second-order correction into a momentum-based framework inspired by STORM (Stochastic Recursive Momentum). It maintains a running gradient estimate that combines the current stochastic gradient with a corrected version of the previous estimate. To further stabilize training in the non-convex landscapes typical of deep RL, SHARP utilizes normalized gradients for its parameter updates.

Theoretical Complexity and Comparison

A primary advantage of SHARP is its theoretical efficiency. It achieves a sample complexity of $O(\epsilon^{-3})$ to reach an $\epsilon$-approximate first-order stationary point, which is the optimal rate for stochastic optimization under standard smoothness assumptions.

Comparison of SHARP with state-of-the-art variance-reduced policy gradient methods.

As shown in the comparison table above, SHARP stands out by requiring a batch size of only $O(1)$ per iteration. Unlike many competing methods that require "checkpoints" with massive batch sizes (often $O(1/\epsilon)$ or $O(1/\epsilon^2)$) to reset the variance, SHARP maintains its efficiency throughout the training process. Furthermore, it eliminates the need for the restrictive assumptions often required to bound the variance of Importance Sampling weights.

Experimental Results

The effectiveness of SHARP was validated using the MuJoCo simulator across several benchmarks, including Reacher, Walker, Swimmer, and the high-dimensional Humanoid task.

In these environments, SHARP consistently outperformed established baselines such as HAPG, IS-MBPG, and PAGE-PG. Notably, on the Humanoid task—which features a 376-dimensional state space—SHARP demonstrated significantly faster convergence and higher final returns. The algorithm also exhibited superior stability; while IS-based methods often show "spiky" performance due to weight instability, SHARP’s training curves remained smooth with tight confidence intervals. In all tested environments, SHARP achieved the highest Performance-Robustness (PR) metric, balancing average return with stability across random seeds.

Conclusion

SHARP represents a significant advancement in variance-reduced policy gradients. By leveraging Hessian-vector products, it bypasses the inherent instabilities of Importance Sampling while maintaining optimal theoretical complexity and practical sample efficiency. Future work may explore the application of these second-order momentum techniques to global optimization and the relaxation of current regularity assumptions.

Summary updated

BibTeX
@misc{salehkaleybar2022adaptive,
  author = {Saber Salehkaleybar and Sadegh Khorasani and Negar Kiyavash and Niao He and Patrick Thiran},
  title = {{Adaptive Momentum-Based Policy Gradient with Second-Order Information}},
  year = {2022},
  url = {https://openreview.net/forum?id=N_AugVmeloE},
}
Figure