Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization

Abstract

Natural policy gradient (NPG) methods are among the most widely used policy optimization algorithms in contemporary reinforcement learning. This class of methods is often applied in conjunction with entropy regularization -- an algorithmic scheme that encourages exploration -- and is closely related to soft policy iteration and trust region policy optimization. Despite the empirical success, the theoretical underpinnings for NPG methods remain limited even for the tabular setting. This paper develops $\text{non-asymptotic}$ convergence guarantees for entropy-regularized NPG methods under softmax parameterization, focusing on discounted Markov decision processes (MDPs). Assuming access to exact policy evaluation, we demonstrate that the algorithm converges linearly -- or even quadratically once it enters a local region around the optimal policy -- when computing optimal value functions of the regularized MDP. Moreover, the algorithm is provably stable vis-à-vis inexactness of policy evaluation. Our convergence results accommodate a wide range of learning rates, and shed light upon the role of entropy regularization in enabling fast convergence.

arXiv commentv2 adds new proofs and improved results; accepted to Operations Research

References in corpus (19)

• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Trust Region Policy Optimization
• Benchmarking Deep Reinforcement Learning for Continuous Control
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Bridging the Gap Between Value and Policy Based Reinforcement Learning
• Equivalence Between Policy Gradients and Soft Q-Learning
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• A unified view of entropy-regularized Markov decision processes
• A Theory of Regularized Markov Decision Processes
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• Provably Efficient Exploration in Policy Optimization
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge

Cited by in corpus (23)

• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Provable Fictitious Play for General Mean-Field Games
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Leveraging Non-uniformity in First-order Non-convex Optimization
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• Online Robust Reinforcement Learning with Model Uncertainty
• Twice regularized MDPs and the equivalence between robustness and regularization
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process
• Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning
• Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPs
• Approximate Newton policy gradient algorithms
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
• Bregman Gradient Policy Optimization
• Actor-critic is implicitly biased towards high entropy optimal policies
• Deep Predictive Learning of Carotid Stenosis Severity
• Understanding the Effect of Stochasticity in Policy Optimization
• Global optimality of softmax policy gradient with single hidden layer neural networks in the mean-field regime
• On The Convergence of First Order Methods for Quasar-Convex Optimization