有限时域马尔可夫决策过程中自然策略梯度的有限时间分析

arXiv cs.LG 论文
reinforcement-learning natural-policy-gradient finite-horizon mdps convergence-analysis theoretical-analysis

摘要

本文首次为有限时域马尔可夫决策过程中的自然策略梯度算法提供了有限时间收敛保证，证明了在不同步长策略下的次线性和线性收敛速度。

arXiv:2607.22982v1 公告类型: 新 摘要：自然策略梯度（NPG）是一种成熟的强化学习算法，是信任区域策略优化和近端策略优化等广泛使用的方法的基础，这些方法在实际应用中均表现出色。本文研究了在已知动力学和时域依赖转移核的有限时域马尔可夫决策过程中的精确NPG算法。我们首次为该设置下的算法提供了有限时间收敛保证，考虑了常量和递增步长策略。对于常量步长 $\eta_t=\eta$，我们证明NPG在 $t$ 次迭代后以 $\mathcal{O}(H^{2}/t)$ 的速率次线性收敛，其中 $H$ 为时域长度。我们还将该常量步长分析扩展到线性MDP，在全支持投影分布下的精确总体投影预言机中，恢复了与表格设置相同的次线性速率。此外，对于递增步长，我们证明该算法以 $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_\rho}\right)^t\right)$ 的线性收敛速率收敛，其中 $\vartheta_\rho > 1$ 为问题依赖常数，而仅依赖于时域的鲁棒调度形式 $\eta_t=\eta_0(H/(H-1))^t$（$\eta_0>0$ 且 $H \geq 2$）也能达到相同的几何速率。
查看原文
查看缓存全文

缓存时间: 2026/07/28 06:23 

# 有限时间范围马尔可夫决策过程中自然策略梯度的有限时间分析
来源：https://arxiv.org/abs/2607.22982
查看 PDF (https://arxiv.org/pdf/2607.22982)

> 摘要：自然策略梯度 \(NPG\) 是一种成熟的强化学习算法，是信任区域策略优化和近端策略优化等广泛使用的方法的基础，这两种方法都已展现出强大的实证成功。在本文中，我们研究了已知动态和依赖于时间范围的转移核条件下，有限时间范围马尔可夫决策过程中的精确 NPG。我们首次为该算法在此设置下提供了有限时间收敛保证，并考虑了恒定步长和递增步长两种情形。对于恒定步长 \(\eta\_t=\eta\)，我们证明了经过 \(t\) 次迭代后，NPG 以 \(\mathcal{O}\(H^\{2}/t\)\) 的速率次线性收敛，其中 \(H\) 为时间范围长度。我们还将此恒定步长分析扩展到线性 MDP，在具有全支撑投影分布的确切总体投影预言下，恢复了与表格设置相同的次线性速率。此外，对于递增步长，我们证明了该算法以 \(\mathcal{O}\left(\left(1-\frac{1}{\vartheta_\rho}\right)^t\right)\) 的速率线性收敛，其中 \(\vartheta\_\rho > 1\) 为问题相关常数；而仅依赖于时间范围的鲁棒调度形式 \(\eta\_t=\eta\_0\(H/\(H-1\)\)^t\)（其中 \(\eta\_0>0\) 且 \(H \geq 2\)）达到了相同的几何速率。

## 提交历史

来自：Asha Barua \[查看邮箱 (https://arxiv.org/show-email/53c802de/2607.22982)\] **\[v1\]** 2026年7月25日 星期六 01:37:26 UTC \(47 KB\)

相似文章

用于稳定多智能体策略学习的度量梯度投影

arXiv cs.LG

介绍HPML，一种将多智能体系统的联合更新场投影到度量梯度分量上以稳定和改进多智能体强化学习的方法。它提供了理论保证，并在CTDE基准测试上展示了改进的稳定性和回报。

基于梯度外推的策略优化

arXiv cs.LG

本文介绍了基于梯度外推的策略优化（GXPO），这是一种仅使用三次反向传播即可在大型语言模型（LLM）的强化学习训练中近似多步前瞻的方法。它在保持固定活跃阶段成本的同时，在数学基准测试上展示了优于标准 GRPO 的推理性能。

差分隐私自然梯度下降

arXiv cs.LG

本文介绍了DP-NGD，一个实用框架，通过将曲率估计与私有数据解耦，并协调各向同性DP约束与各向异性二阶优化，将自然梯度下降与差分隐私相结合，在相同隐私预算下实现了最先进的准确率和高达10倍的收敛速度提升。