Approximate Newton Policy Gradient Algorithms

DOI10.1137/22M1492088zbMATH Open1523.90313arXiv2110.02398MaRDI QIDQ6074547FDOQ6074547

Authors: Haoya Li, Samarth Gupta, Hsiang-Fu Yu, Lexing Ying, Inderjit S. Dhillon 

Publication date: 12 October 2023

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: Policy gradient algorithms have been widely applied to Markov decision processes and reinforcement learning problems in recent years. Regularization with various entropy functions is often used to encourage exploration and improve stability. This paper proposes an approximate Newton method for the policy gradient algorithm with entropy regularization. In the case of Shannon entropy, the resulting algorithm reproduces the natural policy gradient algorithm. For other entropy functions, this method results in brand-new policy gradient algorithms. We prove that all these algorithms enjoy Newton-type quadratic convergence and that the corresponding gradient flow converges globally to the optimal solution. We use synthetic and industrial-scale examples to demonstrate that the proposed approximate Newton method typically converges in single-digit iterations, often orders of magnitude faster than other state-of-the-art algorithms.

Full work available at URL: https://arxiv.org/abs/2110.02398

Recommendations

• Approximate Newton methods for policy search in Markov decision processes
• Fast global convergence of natural policy gradient methods with entropy regularization
• On linear and super-linear convergence of natural policy gradient algorithm
• Entropy Regularization for Mean Field Games with Learning
• Natural actor-critic algorithms

zbMATH Keywords

Markov decision processquadratic convergencereinforcement learningpolicy gradient algorithmentropy regularizationapproximate Newton method

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Artificial neural networks and deep learning (68T07) Large-scale problems in mathematical programming (90C06) Methods of quasi-Newton type (90C53) Newton-type methods (49M15) Markov and semi-Markov decision processes (90C40)

Cites Work

• Title not available (Why is that?)
• Primal-dual subgradient methods for convex problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Simple statistical gradient-following algorithms for connectionist reinforcement learning
• OnActor-Critic Algorithms
• Reinforcement learning. An introduction
• Title not available (Why is that?)
• A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods
• A comparison of iterative methods for solving nonsymmetric linear systems
• The Information Geometry of Mirror Descent
• New results on superlinear convergence of classical quasi-Newton methods
• Mirror descent algorithms for minimizing interacting free energy
• Title not available (Why is that?)
• Rates of superlinear convergence for classical quasi-Newton methods
• Hessian informed mirror descent
• Fast global convergence of natural policy gradient methods with entropy regularization
• Softmax policy gradient methods can take exponential time to converge
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence

Cited In (14)

• Geometry and convergence of natural policy gradient methods
• Hessian matrix distribution for Bayesian policy gradient reinforcement learning
• Approximate Newton methods for policy search in Markov decision processes
• A stochastic trust-region framework for policy optimization
• A Class of Decision Processes Showing Policy-Improvement/Newton–Raphson Equivalence
• Entropy Regularization for Mean Field Games with Learning
• Fast global convergence of natural policy gradient methods with entropy regularization
• Global convergence of natural policy gradient with Hessian-aided momentum variance reduction
• On linear and super-linear convergence of natural policy gradient algorithm
• Accelerating Primal-Dual Methods for Regularized Markov Decision Processes
• Block Policy Mirror Descent
• Entropy regularization methods for parameter space exploration
• Compatible natural gradient policy search
• Global convergence of policy gradient methods to (almost) locally optimal policies

This page was built for publication: Approximate Newton Policy Gradient Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074547)