首次给出自然策略梯度在有限时域下的收敛性分析，为强化学习提供理论支撑。
Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
- 采用精确自然策略梯度算法，结合已知动态与时变转移核。
- 常数步长下收敛速率达O(H²/t)，递增步长可实现线性收敛。
- 适用于需理论保障的RL研究者，尤其关注策略优化收敛性者。
自然策略梯度（NPG）是强化学习中广泛应用的算法，其基础方法如信任区域策略优化（TRPO）和近端策略优化（PPO）已展现出优异的实证性能。本文研究了在已知动态与时域依赖转移核的有限时域马尔可夫决策过程中的精确NPG算法。我们首次提供了该算法在此设定下的有限时间收敛保证，分别考虑常数步长与递增步长两种情形。当步长恒定（η_t=η）时，证明了迭代t次后以速率O(H²/t)子线性收敛，其中H为时域长度。此外，在满足全支持投影分布的线性MDP精确群体投影预言机下，恢复了与表格型设置相同的子线性速率。对于递增步长，我们证明算法可达到几何收敛率O((1−1/ϑ_ρ)^t)，其中ϑ_ρ>1为问题相关常数；同时，形式为η_t=η₀(H/(H−1))^t（η₀>0，H≥2）的仅依赖时域的鲁棒步长调度亦能实现相同几何速率。
原文摘要 · Abstract (English)
Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size $η_t=η$, we prove that NPG converges sublinearly with a rate of $\mathcal{O}(H^{2}/t)$ after $t$ iterations, where $H$ is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)$ for a problem-dependent constant $\vartheta_ρ> 1$, and the horizon-only robust schedule of the form $η_t=η_0(H/(H-1))^t$ where $η_0>0$ and $H \geq 2$, attains this same geometric rate.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。