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