Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
cs.LG, cs.AI
Submitted: 2026-10-09
Updated: 2026-10-09
License: http://creativecommons.org/licenses/by/4.0/
The gist: Standard Policy Gradient (PG) algorithms suffer from high estimation variance because they rely on Monte Carlo updates.
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 (ε-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.
Sources
- GPT-4 Technical Report
- Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback
- DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Sharp First-Order Lower Bounds under $\alpha$-Polyak-Lojasiewicz Conditions
- Learning Optimal Deterministic Policies with Stochastic Policy Gradients
- Proximal Policy Optimization Algorithms
- DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models
- Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
- Stochastic Recursive Momentum for Policy Gradient Methods
- RRHF: Rank Responses to Align Language Models with Human Feedback without tears
- Fine-Tuning Language Models from Human Preferences
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks