# A Theory of Regularized Markov Decision Processes

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

## Key facts

- Cited by 286 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2019.

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

- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [RLAIF vs. RLHF: Scaling Reinforcement Learning from Human Feedback with AI Feedback](https://mlsanity.com/paper/2309.00267/) (2023)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Maximum Entropy RL (Provably) Solves Some Robust RL Problems](https://mlsanity.com/paper/2103.06257/) (2021)
- [WARM: On the Benefits of Weight Averaged Reward Models](https://mlsanity.com/paper/2401.12187/) (2024)
- [Derivative-Free Guidance in Continuous and Discrete Diffusion Models with Soft Value-Based Decoding](https://mlsanity.com/paper/2408.08252/) (2024)
- [Offline RL with No OOD Actions: In-Sample Learning via Implicit Value Regularization](https://mlsanity.com/paper/2303.15810/) (2023)
- [Adversarially Trained Actor Critic for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02446/) (2022)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Understanding Reinforcement Learning-Based Fine-Tuning of Diffusion Models: A Tutorial and Review](https://mlsanity.com/paper/2407.13734/) (2024)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Provably Good Batch Reinforcement Learning Without Great Exploration](https://mlsanity.com/paper/2007.08202/) (2020)
- [BOND: Aligning LLMs with Best-of-N Distillation](https://mlsanity.com/paper/2407.14622/) (2024)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Factually Consistent Summarization via Reinforcement Learning with Textual Entailment Feedback](https://mlsanity.com/paper/2306.00186/) (2023)
- [Multi-turn Reinforcement Learning from Preference Human Feedback](https://mlsanity.com/paper/2405.14655/) (2024)
- [Generative Flow Networks as Entropy-Regularized RL](https://mlsanity.com/paper/2310.12934/) (2023)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Feedback Efficient Online Fine-Tuning of Diffusion Models](https://mlsanity.com/paper/2402.16359/) (2024)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Adversarially Guided Actor-Critic](https://mlsanity.com/paper/2102.04376/) (2021)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [WARP: On the Benefits of Weight Averaged Rewarded Policies](https://mlsanity.com/paper/2406.16768/) (2024)
- [Offline Reinforcement Learning as Anti-Exploration](https://mlsanity.com/paper/2106.06431/) (2021)

## Abstract (arXiv)

Many recent successful (deep) reinforcement learning algorithms make use of regularization, generally based on entropy or Kullback-Leibler divergence. We propose a general theory of regularized Markov Decision Processes that generalizes these approaches in two directions: we consider a larger class of regularizers, and we consider the general modified policy iteration approach, encompassing both policy iteration and value iteration. The core building blocks of this theory are a notion of regularized Bellman operator and the Legendre-Fenchel transform, a classical tool of convex optimization. This approach allows for error propagation analyses of general algorithmic schemes of which (possibly variants of) classical algorithms such as Trust Region Policy Optimization, Soft Q-learning, Stochastic Actor Critic or Dynamic Policy Programming are special cases. This also draws connections to proximal convex optimization, especially to Mirror Descent.