Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation
This provides theoretical guarantees for a widely used method in reinforcement learning, addressing a gap in understanding its convergence properties, though it is incremental as it builds on existing NPG frameworks.
The paper tackles the convergence analysis of entropy-regularized natural policy gradient methods with linear function approximation in reinforcement learning, proving a fast convergence rate of O(1/T) and linear convergence under mild conditions, up to a function approximation error.
Natural policy gradient (NPG) methods with entropy regularization achieve impressive empirical success in reinforcement learning problems with large state-action spaces. However, their convergence properties and the impact of entropy regularization remain elusive in the function approximation regime. In this paper, we establish finite-time convergence analyses of entropy-regularized NPG with linear function approximation under softmax parameterization. In particular, we prove that entropy-regularized NPG with averaging satisfies the \emph{persistence of excitation} condition, and achieves a fast convergence rate of $\tilde{O}(1/T)$ up to a function approximation error in regularized Markov decision processes. This convergence result does not require any a priori assumptions on the policies. Furthermore, under mild regularity conditions on the concentrability coefficient and basis vectors, we prove that entropy-regularized NPG exhibits \emph{linear convergence} up to a function approximation error.