Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies
Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies
复制标题
DOI：
10.48550/arxiv.2210.01400
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Rui Yuan;S. Du;Robert Mansel Gower;A. Lazaric;Lin Xiao
中科院分区：
文献类型：
--
作者：
Rui Yuan;S. Du;Robert Mansel Gower;A. Lazaric;Lin Xiao
考虑无限视界折现马尔可夫决策过程，研究了自然策略梯度（NPG）的收敛速度和对数线性策略类的Q-NPG方法。使用兼容函数近似框架，具有对数线性策略的两种方法都可以写成策略镜像下降（PMD）方法的不精确版本。我们表明，这两种方法都使用简单的、非自适应的几何增长步长来获得线性收敛率和$\tilde{\mathcal{O}}(1/\epsilon^2)$样本复杂性，而无需诉诸熵或其他强凸正则化。最后，作为一个副产品，我们得到了两种方法在任意恒定步长下的亚线性收敛速率。
We consider infinite-horizon discounted Markov decision processes and study the convergence rates of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear policy class. Using the compatible function approximation framework, both methods with log-linear policies can be written as inexact versions of the policy mirror descent (PMD) method. We show that both methods attain linear convergence rates and $\tilde{\mathcal{O}}(1/\epsilon^2)$ sample complexities using a simple, non-adaptive geometrically increasing step size, without resorting to entropy or other strongly convex regularization. Lastly, as a byproduct, we obtain sublinear convergence rates for both methods with arbitrary constant step size.