# A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 17 Oct 2021.

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Bridging the Gap Between Value and Policy Based Reinforcement Learning](https://mlsanity.com/paper/1702.08892/) (2017)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [A General Safety Framework for Learning-Based Control in Uncertain Robotic Systems](https://mlsanity.com/paper/1705.01292/) (2017)
- [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)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [Complexity of first order inexact Lagrangian and penalty methods for conic convex programming](https://mlsanity.com/paper/1506.05320/) (2015)
- [Non-Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1911.04220/) (2019)

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

- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [On the Global Optimum Convergence of Momentum-based Policy Gradient](https://mlsanity.com/paper/2110.10116/) (2021)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2205.13746/) (2022)
- [Identifiability and Generalizability in Constrained Inverse Reinforcement Learning](https://mlsanity.com/paper/2306.00629/) (2023)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [Robust Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.06866/) (2022)
- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form](https://mlsanity.com/paper/2408.16286/) (2024)
- [Constrained Reinforcement Learning Under Model Mismatch](https://mlsanity.com/paper/2405.01327/) (2024)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees](https://mlsanity.com/paper/2505.19238/) (2025)
- [Algorithm for Constrained Markov Decision Process with Linear Convergence](https://mlsanity.com/paper/2206.01666/) (2022)
- [Finite-Time Error Analysis of Soft Q-Learning: Switching System Approach](https://mlsanity.com/paper/2403.06366/) (2024)
- [Flipping-based Policy for Chance-Constrained Markov Decision Processes](https://mlsanity.com/paper/2410.06474/) (2024)
- [Convergence of a model-free entropy-regularized inverse reinforcement learning algorithm](https://mlsanity.com/paper/2403.16829/) (2024)
- [Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning](https://mlsanity.com/paper/2407.10775/) (2024)
- [The Feasibility Theory of Constrained Reinforcement Learning: A Tutorial Study](https://mlsanity.com/paper/2404.10064/) (2024)
- [Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs](https://mlsanity.com/paper/2408.11513/) (2024)
- [Provably Efficient Sample Complexity for Robust CMDP](https://mlsanity.com/paper/2511.07486/) (2025)
- [Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins](https://mlsanity.com/paper/2602.10917/) (2026)
- [Offline Constrained RLHF with Multiple Preference Oracles](https://mlsanity.com/paper/2604.00200/) (2026)
- [Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2405.02456/) (2024)

## Abstract (arXiv)

We study entropy-regularized constrained Markov decision processes (CMDPs) under the soft-max parameterization, in which an agent aims to maximize the entropy-regularized value function while satisfying constraints on the expected total utility. By leveraging the entropy regularization, our theoretical analysis shows that its Lagrangian dual function is smooth and the Lagrangian duality gap can be decomposed into the primal optimality gap and the constraint violation. Furthermore, we propose an accelerated dual-descent method for entropy-regularized CMDPs. We prove that our method achieves the global convergence rate widetildeO(1/T) for both the optimality gap and the constraint violation for entropy-regularized CMDPs. A discussion about a linear convergence rate for CMDPs with a single constraint is also provided.