mlsanityData to 14 Oct 2026

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

arXiv 2406.04163 ↗First posted 6 Jun 2024math.OC cs.LG cs.SYcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

Key facts. Cited by 1 paper 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.

Builds on

29 of 52 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Elementary Analysis of Policy Gradient Methods4 Apr
  2. 2024Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients28 Mar

Other references · 27

  1. 2021Convex optimizationcited by 2,515
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  3. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  4. 2019A Theory of Regularized Markov Decision Processescited by 286
  5. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  6. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  8. 2017A unified view of entropy-regularized Markov decision processescited by 182
  9. 2018Understanding the impact of entropy on policy optimizationcited by 176
  10. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  11. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  12. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
15 more
  1. 2020Gradient descent follows the regularization path for general lossescited by 59
  2. 2020Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rankcited by 42
  3. 2017Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learningcited by 37
  4. 2018Hessian Riemannian gradient flows in convex programmingcited by 26
  5. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 23
  6. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  7. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 16
  8. 2020Implicit Bias of Gradient Descent for Mean Squared Error Regression with Two-Layer Wide Neural Networkscited by 15
  9. 2021Actor-critic is implicitly biased towards high entropy optimal policiescited by 13
  10. 2022Geometry and convergence of natural policy gradient methodscited by 12
  11. 2024Entropy annealing for policy mirror descent in continuous time and spacecited by 12
  12. 2021The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPscited by 9
  13. 2022Implicit Bias of MSE Gradient Optimization in Underparameterized Neural Networkscited by 9
  14. 2022Deep Linear Networks for Matrix Completion -- An Infinite Depth Limitcited by 8
  15. 2024A Geometric Embedding Approach to Multiple Games and Multiple Populationscited by 6

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Central Path Proximal Policy Optimizationcited by 3

Similar, not cited

Close in wording, no citation either way

  1. 2026Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs
  2. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  3. 2026Entropy Regularization Improves Policy Robustness in Continuous-Time Reinforcement Learning
  4. 2026Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic
  5. 2025Convergence of an actor-critic gradient flow for entropy regularised MDPs in general spaces
  6. 2025Convergence Theorems for Entropy-Regularized and Distributional Reinforcement Learning
  7. 2026Reinforcement Learning in Real Option Models
  8. 2025Complexity-Regularized Proximal Policy Optimization