Accelerating Primal-Dual Methods for Regularized Markov Decision Processes

DOI10.1137/21M1468851arXiv2202.10506MaRDI QIDQ6202767FDOQ6202767

Lexing Ying, Inderjit S. Dhillon, Haoya Li, Hsiang-Fu Yu

Publication date: 27 February 2024

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: Entropy regularized Markov decision processes have been widely used in reinforcement learning. This paper is concerned with the primal-dual formulation of the entropy regularized problems. Standard first-order methods suffer from slow convergence due to the lack of strict convexity and concavity. To address this issue, we first introduce a new quadratically convexified primal-dual formulation. The natural gradient ascent descent of the new formulation enjoys global convergence guarantee and exponential convergence rate. We also propose a new interpolating metric that further accelerates the convergence significantly. Numerical results are provided to demonstrate the performance of the proposed methods under multiple settings.

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

zbMATH Keywords

Markov decision processreinforcement learningprimal-dual methodentropy regularization

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Learning and adaptive systems in artificial intelligence (68T05) Minimax problems in mathematical programming (90C47) Markov and semi-Markov decision processes (90C40) Lyapunov and storage functions (93D30) Acceleration of convergence in numerical analysis (65B99)

Cites Work

• Title not available (Why is that?)
• Simple statistical gradient-following algorithms for connectionist reinforcement learning
• Title not available (Why is that?)
• 10.1162/jmlr.2003.3.4-5.803
• A note on optimization formulations of Markov decision processes
• Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes
• Approximate Newton Policy Gradient Algorithms
• Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time

This page was built for publication: Accelerating Primal-Dual Methods for Regularized Markov Decision Processes

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