# Accelerating Primal-dual Methods for Regularized Markov Decision Processes

arXiv: https://arxiv.org/abs/2202.10506 · HTML: https://mlsanity.com/paper/2202.10506/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 42 references that are in the map.
- First posted on arXiv 21 Feb 2022.

## Builds on (most cited first, 22 of 22)

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Understanding the impact of entropy on policy optimization](https://mlsanity.com/paper/1811.11214/) (2018)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Trust-PCL: An Off-Policy Trust Region Method for Continuous Control](https://mlsanity.com/paper/1707.01891/) (2017)
- [Cautious Reinforcement Learning via Distributional Risk in the Dual Domain](https://mlsanity.com/paper/2002.12475/) (2020)
- [Faster saddle-point optimization for solving large-scale Markov decision processes](https://mlsanity.com/paper/1909.10904/) (2019)
- [Stochastic Primal-Dual Q-Learning](https://mlsanity.com/paper/1810.08298/) (2018)
- [A Note on Optimization Formulations of Markov Decision Processes](https://mlsanity.com/paper/2012.09417/) (2020)
- [Deep Primal-Dual Reinforcement Learning: Accelerating Actor-Critic using Bellman Duality](https://mlsanity.com/paper/1712.02467/) (2017)

## Built on by (most cited first, 2 of 2)

- [Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity](https://mlsanity.com/paper/2405.19697/) (2024)
- [A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance](https://mlsanity.com/paper/2505.04494/) (2025)

## Abstract (arXiv)

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.