# PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 34 references that are in the map.
- First posted on arXiv 1 Feb 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Don't Decay the Learning Rate, Increase the Batch Size](https://mlsanity.com/paper/1711.00489/) (2017)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Understanding the impact of entropy on policy optimization](https://mlsanity.com/paper/1811.11214/) (2018)
- [Adding Gradient Noise Improves Learning for Very Deep Networks](https://mlsanity.com/paper/1511.06807/) (2015)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [On Linear Convergence of Policy Gradient Methods for Finite MDPs](https://mlsanity.com/paper/2007.11120/) (2020)
- [Beyond variance reduction: Understanding the true impact of baselines on policy optimization](https://mlsanity.com/paper/2008.13773/) (2020)
- [Momentum-Based Policy Gradient Methods](https://mlsanity.com/paper/2007.06680/) (2020)
- [Stochastic Recursive Momentum for Policy Gradient Methods](https://mlsanity.com/paper/2003.04302/) (2020)
- [On the Promise of the Stochastic Generalized Gauss-Newton Method for Training DNNs](https://mlsanity.com/paper/2006.02409/) (2020)
- [Towards Understanding the Importance of Noise in Training Neural Networks](https://mlsanity.com/paper/1909.03172/) (2019)

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

- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Momentum-Based Policy Gradient with Second-Order Information](https://mlsanity.com/paper/2205.08253/) (2022)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [Policy Gradient with Active Importance Sampling](https://mlsanity.com/paper/2405.05630/) (2024)
- [Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments](https://mlsanity.com/paper/2405.19499/) (2024)
- [Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction](https://mlsanity.com/paper/2401.01084/) (2024)
- [Decentralized Federated Policy Gradient with Byzantine Fault-Tolerance and Provably Fast Convergence](https://mlsanity.com/paper/2401.03489/) (2024)
- [Non-Asymptotic Global Convergence of PPO-Clip](https://mlsanity.com/paper/2512.16565/) (2025)
- [Efficiently Escaping Saddle Points for Policy Optimization](https://mlsanity.com/paper/2311.08914/) (2023)
- [On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization](https://mlsanity.com/paper/2401.12508/) (2024)
- [Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs](https://mlsanity.com/paper/2408.11513/) (2024)
- [Reusing Trajectories in Policy Gradients Enables Fast Convergence](https://mlsanity.com/paper/2506.06178/) (2025)
- [Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds](https://mlsanity.com/paper/2610.03165/) (2026)
- [A Variance-Reduced Cubic-Regularized Newton for Policy Optimization](https://mlsanity.com/paper/2507.10120/) (2025)
- [Variance-Reduced Policy Gradient is Nearly Minimax-Optimal](https://mlsanity.com/paper/2610.13692/) (2026)

## Abstract (arXiv)

Despite their success, policy gradient methods suffer from high variance of the gradient estimate, which can result in unsatisfactory sample complexity. Recently, numerous variance-reduced extensions of policy gradient methods with provably better sample complexity and competitive numerical performance have been proposed. After a compact survey on some of the main variance-reduced REINFORCE-type methods, we propose ProbAbilistic Gradient Estimation for Policy Gradient (PAGE-PG), a novel loopless variance-reduced policy gradient method based on a probabilistic switch between two types of updates. Our method is inspired by the PAGE estimator for supervised learning and leverages importance sampling to obtain an unbiased gradient estimator. We show that PAGE-PG enjoys a Oleft( ε-3 right) average sample complexity to reach an ε-stationary solution, which matches the sample complexity of its most competitive counterparts under the same setting. A numerical evaluation confirms the competitive performance of our method on classical control tasks.