Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation

SIAM Journal on Optimization, vol. 34, pp. 2729–2755

Abstract

Abstract. Natural policy gradient (NPG) methods, equipped with function approximation and 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 persistence of excitation condition, and achieves a fast convergence rate of [Formula: see text] 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 linear convergence up to the compatible function approximation error. Finally, we provide sample complexity results for sample-based NPG with entropy regularization.

Authors 3

1. Semih Çaycı Aachen Chair for Mathematics of Information Processing

   RWTH Aachen University

   Affiliation as printed

   Chair for Mathematics of Information Processing, RWTH Aachen University, 52062 Aachen, Germany

2. Niao He

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zurich, 8092 Zurich, Switzerland

3. R. Srikant

   University of Illinois Urbana-Champaign

   Affiliation as printed

   Department of Electrical and Computer Engineering, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA