arXiv：cs.LG· Gabor Paczolay, Matteo Papini, Alberto Maria Metelli, Istvan Harmati, Marcello Restelli·· 3 小时前AI 评分35
方差缩减策略梯度算法的样本复杂度：更弱假设与下界
Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
AI 导读
论文提出 Defensive Policy Gradient（DPG）算法，基于防御性重要性采样，在不对普通重要性权重方差做任何假设的前提下，达到与已有方差缩减 REINFORCE 方法相同的 O(ε⁻³) 样本复杂度。作者还在隐藏状态与动作、允许参数依赖奖励的广义黑盒策略优化模型中建立下界：单策略有界方差反馈的最优速率为 Θ(ε⁻⁴)，均方平滑耦合双策略反馈为 Θ(ε⁻³)。
正文
Abstract:Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved $O(\epsilon^{-3})$ sample complexity to find an $\epsilon$-stationary point, under an unrealistic assumption on the variance of the importance weights. In this paper, we propose the \algo (Defensive Policy Gradient) algorithm, based on defensive importance sampling, which achieves the same rate without any assumption on the variance of ordinary importance weights. We also establish lower bounds in a generalized black-box policy-optimization model that hides states and actions and permits parameter-dependent rewards. In this model, the optimal rates are $\Theta(\epsilon^{-4})$ with bounded-variance one-policy feedback and $\Theta(\epsilon^{-3})$ with mean-square-smooth coupled two-policy feedback. Under standard policy-regularity conditions, REINFORCE and \algo realize the corresponding oracle conditions and attain the $O(\epsilon^{-4})$ and $O(\epsilon^{-3})$ upper bounds, respectively. Although the lower bounds do not apply directly to the classical MDP interaction model in which these algorithms operate, this correspondence provides oracle-level evidence that the faster rate of \algo is optimal and genuinely separated from that of vanilla policy gradient.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.03165 [cs.LG] |
| (or arXiv:2610.03165v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.03165 arXiv-issued DOI via DataCite (pending registration) |
|
| Journal reference: | Paczolay, G., Papini, M., Metelli, A.M. et al. Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds. Mach Learn 113, 6475-6510 (2024) |
| Related DOI: | https://doi.org/10.1007/s10994-024-06573-4
DOI(s) linking to related resources |
Submission history
From: Matteo Papini [view email]
[v1]
Fri, 2 Oct 2026 11:43:52 UTC (58 KB)
来源：arXiv：cs.LG · arxiv.org