arXiv cs.AI· Leonardo Cesani, Matteo Papini, Marcello Restelli·· 6 天前AI 评分22
LVR-PG：方差缩减策略梯度被证明近乎极小极大最优
Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
AI 导读
研究者提出 Loopless Variance-Reduced PG（LVR-PG）统一理论框架，抽象出结合递归更新与防御性重要性采样的一阶估计器类，涵盖 PAGE-PG 和 STORM-PG。
正文 · 原文
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}}(\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.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.13692 [cs.LG] |
| (or arXiv:2610.13692v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.13692 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Leonardo Cesani [view email]
[v1]
Fri, 9 Oct 2026 14:54:26 UTC (1,285 KB)
来源：arXiv cs.AI · arxiv.org