On linear and super-linear convergence of natural policy gradient algorithm
From MaRDI portal
Publication:2670744
Abstract: Markov Decision Processes are classically solved using Value Iteration and Policy Iteration algorithms. Recent interest in Reinforcement Learning has motivated the study of methods inspired by optimization, such as gradient ascent. Among these, a popular algorithm is the Natural Policy Gradient, which is a mirror descent variant for MDPs. This algorithm forms the basis of several popular Reinforcement Learning algorithms such as Natural actor-critic, TRPO, PPO, etc, and so is being studied with growing interest. It has been shown that Natural Policy Gradient with constant step size converges with a sublinear rate of O(1/k) to the global optimal. In this paper, we present improved finite time convergence bounds, and show that this algorithm has geometric (also known as linear) asymptotic convergence rate. We further improve this convergence result by introducing a variant of Natural Policy Gradient with adaptive step sizes. Finally, we compare different variants of policy gradient methods experimentally.
Recommendations
- Fast global convergence of natural policy gradient methods with entropy regularization
- Approximate Newton Policy Gradient Algorithms
- Natural actor-critic algorithms
- A constrained optimization perspective on actor-critic algorithms and application to network routing
- Policy gradient in Lipschitz Markov decision processes
Cites work
- Dynamic policy programming
- First-order methods in optimization
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3090562 (Why is no real title available?)
- Improved and generalized upper bounds on the complexity of policy iteration
- Natural actor-critic algorithms
- On the Convergence of Policy Iteration in Stationary Dynamic Programming
- On the theory of policy gradient methods: optimality, approximation, and distribution shift
- The Information Geometry of Mirror Descent
Cited in
(16)- Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes
- Approximate Newton methods for policy search in Markov decision processes
- Fast global convergence of natural policy gradient methods with entropy regularization
- Approximate Newton Policy Gradient Algorithms
- Block Policy Mirror Descent
- Softmax policy gradient methods can take exponential time to converge
- Geometry and convergence of natural policy gradient methods
- Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
- Homotopic policy mirror descent: policy convergence, algorithmic regularization, and improved sample complexity
- Global convergence of natural policy gradient with Hessian-aided momentum variance reduction
- An approximate policy iteration viewpoint of actor-critic algorithms
- Fisher-Rao gradient flows of linear programs and state-action natural policy gradients
- Optimal rates of convergence for entropy regularization in discounted Markov decision processes
- Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs
- A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spaces
- Policy gradient in Lipschitz Markov decision processes
This page was built for publication: On linear and super-linear convergence of natural policy gradient algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670744)
