# Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence

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

## Key facts

- Cited by 84 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 68 references that are in the map.
- First posted on arXiv 24 May 2021.

## Builds on (most cited first, 30 of 35)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [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)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [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)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Mirror Descent Policy Optimization](https://mlsanity.com/paper/2005.09814/) (2020)
- [Sample Efficient Reinforcement Learning with REINFORCE](https://mlsanity.com/paper/2010.11364/) (2020)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [Convergent Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1910.12156/) (2019)
- [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)
- [Policy Optimization for H2 Linear Control with H_∞ Robustness Guarantee: Implicit Regularization and Global Convergence](https://mlsanity.com/paper/1910.09496/) (2019)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning](https://mlsanity.com/paper/1709.06293/) (2017)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [Path Consistency Learning in Tsallis Entropy Regularized MDPs](https://mlsanity.com/paper/1802.03501/) (2018)

## Built on by (most cited first, 30 of 84)

- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Mirror Learning: A Unifying Framework of Policy Optimisation](https://mlsanity.com/paper/2201.02373/) (2022)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Regressing the Relative Future: Efficient Policy Optimization for Multi-turn RLHF](https://mlsanity.com/paper/2410.04612/) (2024)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01050/) (2022)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [Policy Optimization over General State and Action Spaces](https://mlsanity.com/paper/2211.16715/) (2022)
- [A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spaces](https://mlsanity.com/paper/2310.02951/) (2023)
- [Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2206.00833/) (2022)
- [Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergence](https://mlsanity.com/paper/2412.18164/) (2024)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization](https://mlsanity.com/paper/2209.15382/) (2022)
- [Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2301.13087/) (2023)
- [Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity](https://mlsanity.com/paper/2201.09457/) (2022)
- [Policy Mirror Descent Inherently Explores Action Space](https://mlsanity.com/paper/2303.04386/) (2023)
- [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022)
- [Entropy annealing for policy mirror descent in continuous time and space](https://mlsanity.com/paper/2405.20250/) (2024)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)
- [Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity](https://mlsanity.com/paper/2405.19697/) (2024)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)

## Abstract (arXiv)

Policy optimization, which finds the desired policy by maximizing value functions via optimization techniques, lies at the heart of reinforcement learning (RL). In addition to value maximization, other practical considerations arise as well, including the need of encouraging exploration, and that of ensuring certain structural properties of the learned policy due to safety, resource and operational constraints. These can often be accounted for via regularized RL, which augments the target value function with a structure-promoting regularizer. Focusing on discounted infinite-horizon Markov decision processes, we propose a generalized policy mirror descent (GPMD) algorithm for solving regularized RL. As a generalization of policy mirror descent (arXiv:2102.00135), our algorithm accommodates a general class of convex regularizers and promotes the use of Bregman divergence in cognizant of the regularizer in use. We demonstrate that our algorithm converges linearly to the global solution over an entire range of learning rates, in a dimension-free fashion, even when the regularizer lacks strong convexity and smoothness. In addition, this linear convergence feature is provably stable in the face of inexact policy evaluation and imperfect policy updates. Numerical experiments are provided to corroborate the appealing performance of GPMD.