Variance-reduced policy gradient methods reach optimal sample complexity limits
Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
Machine LearningArtificial Intelligence
Summary
Policy Gradient methods are used in AI to teach computers how to make decisions, but they often need lots of trial runs because their estimates can be very noisy. The authors developed a new way to reduce this noise using clever updates that avoid complicated calculations, making learning more efficient. They proved that their approach is almost the best possible in terms of how many samples it needs to learn well, even under broad conditions. This means computers can learn good policies faster without relying on restrictive assumptions.
What this means in practice
- •For reinforcement learning engineers: Build more sample-efficient policy gradient algorithms that require fewer environment interactions to converge reliably.
- •For robotics system designers: Improve robot decision-making systems by applying variance-reduced policy gradients that learn effective policies with less data.
A theory result. No direct application yet.
Authors
Leonardo Cesani, Matteo Papini, Marcello Restelli
Abstract
Standard Policy Gradient (PG) algorithms suffer from high estimation variance because they rely on Monte Carlo updates. While off-policy variance reduction mitigates this problem, establishing optimal sample complexity currently requires either restrictive assumptions, such as uniformly bounded importance weights, or impractical second-order operations. In this work, we introduce Loopless Variance-Reduced PG (LVR-PG), a unified theoretical framework that abstracts a class of first-order estimators that integrate recursive updates with defensive importance sampling, including known estimators such as PAGE-PG and STORM-PG. We prove that this algorithmic class achieves $\tilde{\mathcal{O}}(ε^{-2})$ last-iterate global convergence under weak gradient domination for general parametric policies. We establish this guarantee using purely first-order updates, with minimal assumptions and without gradient preconditioners. By extending state-of-the-art lower bounds to continuous parametric policies, we establish an $Ω(ε^{-2})$ sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms.