mlsanityData to 7 Oct 2026

Truly No-Regret Learning in Constrained MDPs

arXiv 2402.15776 ↗First posted 24 Feb 2024cs.LG stat.MLcited by 23

Not on the map. Why?

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.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 33 of its 51 references that are in the map. First posted on arXiv 24 Feb 2024.

Builds on

33 of 51 references.

References · 33

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  4. 2018Reward Constrained Policy Optimizationcited by 397
  5. 2021Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learningcited by 337
  6. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 320
  7. 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 302
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  9. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2013Bandits with Knapsackscited by 163
  12. 2020Exploration-Exploitation in Constrained MDPscited by 146
21 more
  1. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  2. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  3. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  4. 2015Linear Contextual Bandits with Knapsackscited by 82
  5. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  6. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  7. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
  8. 2020Stochastic Bandits with Linear Constraintscited by 68
  9. 2016Conservative Contextual Linear Banditscited by 56
  10. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  11. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  12. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  13. 2021State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewardscited by 37
  14. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  15. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  16. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  17. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  18. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  19. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 19
  20. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  21. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 9; 2026: 10.

23 papers.

Sort:

By area:

  1. 2024ActSafe: Active Exploration with Safety Constraints for Reinforcement Learningcited by 22
  2. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
  3. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  4. 2024Embedding Safety into RL: A New Take on Trust Region Methodscited by 9
  5. 2025Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spacescited by 5
  6. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  7. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  8. 2025Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approachcited by 5
  9. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  10. 2025Data-Dependent Regret Bounds for Constrained MABscited by 2
  11. 2026Replicable Constrained Banditscited by 2
  12. 2025Safe and Near-Optimal Control with Online Dynamics Learningcited by 1
11 more
  1. 2025Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraintscited by 1
  2. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 1
  3. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
  4. 2025A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Modelscited by 0
  5. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Marginscited by 0
  6. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  7. 2026Price of Fairness in Short-Term and Long-Term Algorithmic Selectionscited by 0
  8. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  9. 2026Sampling-Based Safe Reinforcement Learningcited by 0
  10. 2026Constrained Multi-Objective Reinforcement Learning with Max-Min Criterioncited by 0
  11. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0