# Truly No-Regret Learning in Constrained MDPs

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

## Key facts

- Cited by 23 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 33 of its 51 references that are in the map.
- First posted on arXiv 24 Feb 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, 30 of 33)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Responsive Safety in Reinforcement Learning by PID Lagrangian Methods](https://mlsanity.com/paper/2007.03964/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewards](https://mlsanity.com/paper/2102.11941/) (2021)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization](https://mlsanity.com/paper/2110.08923/) (2021)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [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)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)

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

- [ActSafe: Active Exploration with Safety Constraints for Reinforcement Learning](https://mlsanity.com/paper/2410.09486/) (2024)
- [Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization](https://mlsanity.com/paper/2410.02275/) (2024)
- [Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form](https://mlsanity.com/paper/2408.16286/) (2024)
- [Embedding Safety into RL: A New Take on Trust Region Methods](https://mlsanity.com/paper/2411.02957/) (2024)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints](https://mlsanity.com/paper/2505.21841/) (2025)
- [Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces](https://mlsanity.com/paper/2502.11828/) (2025)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach](https://mlsanity.com/paper/2510.20235/) (2025)
- [Data-Dependent Regret Bounds for Constrained MABs](https://mlsanity.com/paper/2505.20010/) (2025)
- [Replicable Constrained Bandits](https://mlsanity.com/paper/2602.14580/) (2026)
- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Safe and Near-Optimal Control with Online Dynamics Learning](https://mlsanity.com/paper/2509.16650/) (2025)
- [Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2509.20114/) (2025)
- [Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins](https://mlsanity.com/paper/2602.10917/) (2026)
- [A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Models](https://mlsanity.com/paper/2504.04976/) (2025)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [Price of Fairness in Short-Term and Long-Term Algorithmic Selections](https://mlsanity.com/paper/2605.06227/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)
- [Sampling-Based Safe Reinforcement Learning](https://mlsanity.com/paper/2605.19469/) (2026)
- [Constrained Multi-Objective Reinforcement Learning with Max-Min Criterion](https://mlsanity.com/paper/2605.31388/) (2026)
- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)

## Abstract (arXiv)

Constrained Markov decision processes (CMDPs) are a common way to model safety constraints in reinforcement learning. State-of-the-art methods for efficiently solving CMDPs are based on primal-dual algorithms. For these algorithms, all currently known regret bounds allow for error cancellations -- one can compensate for a constraint violation in one round with a strict constraint satisfaction in another. This makes the online learning process unsafe since it only guarantees safety for the final (mixture) policy but not during learning. As Efroni et al. (2020) pointed out, it is an open question whether primal-dual algorithms can provably achieve sublinear regret if we do not allow error cancellations. In this paper, we give the first affirmative answer. We first generalize a result on last-iterate convergence of regularized primal-dual schemes to CMDPs with multiple constraints. Building upon this insight, we propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.