# Optimal Rates of Convergence for Entropy Regularization in Discounted Markov Decision Processes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 29 of its 52 references that are in the map.
- First posted on arXiv 6 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [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)
- [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)
- [Gradient descent follows the regularization path for general losses](https://mlsanity.com/paper/2006.11226/) (2020)
- [Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank](https://mlsanity.com/paper/2011.13772/) (2020)
- [Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning](https://mlsanity.com/paper/1709.06293/) (2017)
- [Hessian Riemannian gradient flows in convex programming](https://mlsanity.com/paper/1811.10331/) (2018)
- [A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spaces](https://mlsanity.com/paper/2310.02951/) (2023)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024)
- [Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation](https://mlsanity.com/paper/2106.04096/) (2021)
- [Implicit Bias of Gradient Descent for Mean Squared Error Regression with Two-Layer Wide Neural Networks](https://mlsanity.com/paper/2006.07356/) (2020)
- [Actor-critic is implicitly biased towards high entropy optimal policies](https://mlsanity.com/paper/2110.11280/) (2021)
- [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)
- [The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs](https://mlsanity.com/paper/2110.07409/) (2021)
- [Implicit Bias of MSE Gradient Optimization in Underparameterized Neural Networks](https://mlsanity.com/paper/2201.04738/) (2022)
- [Deep Linear Networks for Matrix Completion -- An Infinite Depth Limit](https://mlsanity.com/paper/2210.12497/) (2022)
- [A Geometric Embedding Approach to Multiple Games and Multiple Populations](https://mlsanity.com/paper/2401.05918/) (2024)
- [Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients](https://mlsanity.com/paper/2403.19448/) (2024)

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

- [Central Path Proximal Policy Optimization](https://mlsanity.com/paper/2506.00700/) (2025)

## Abstract (arXiv)

We study the error introduced by entropy regularization in infinite-horizon discrete discounted Markov decision processes. We show that this error decreases exponentially in the inverse regularization strength, both in a weighted KL-divergence and in value with a problem-specific exponent. This is in contrast to previously known estimates, of the order O(τ), where τ is the regularization strength. We provide a lower bound that matches our upper bound up to a polynomial term, thereby characterizing the exponential convergence rate for entropy regularization. Our proof relies on the observation that the solutions of entropy-regularized Markov decision processes solve a gradient flow of the unregularized reward with respect to a Riemannian metric common in natural policy gradient methods. This correspondence allows us to identify the limit of this gradient flow as the generalized maximum entropy optimal policy, thereby characterizing the implicit bias of this gradient flow, which corresponds to a time-continuous version of the natural policy gradient method. We use our improved error estimates to show that for entropy-regularized natural policy gradient methods, the overall error decays exponentially in the square root of the number of iterations, improving over existing sublinear guarantees. Finally, we extend our analysis to settings beyond the entropy. In particular, we characterize the implicit bias regarding general convex potentials and their resulting generalized natural policy gradients.