Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

arXiv:2610.13692v1 Announce Type: cross 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 ilde{O}(epsilon^{-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 Omega(epsilon^{-2}) sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms.

Related

• Softmax gradient policy for variance minimization and risk-averse multi armed bandits
• On the Approximation and Convergence of Distributional Policy Gradient Algorithms for Risk-Sensitive Reinforcement Learning
• ProRL: Effective Reinforcement Learning for Proactive Recommendation via Rectified Policy Gradient Estimation

Source: arXiv cs.AI | 2026-10-12