mlsanityData to 14 Oct 2026

Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes

arXiv 2306.07001 ↗First posted 12 Jun 2023cs.LG stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

Constrained Markov Decision Processes (CMDPs) are one of the common ways to model safe reinforcement learning problems, where constraint functions model the safety objectives. Lagrangian-based dual or primal-dual algorithms provide efficient methods for learning in CMDPs. For these algorithms, the currently known regret bounds in the finite-horizon setting allow for a "cancellation of errors"; one can compensate for a constraint violation in one episode with a strict constraint satisfaction in another. However, we do not consider such a behavior safe in practical applications. In this paper, we overcome this weakness by proposing a novel model-based dual algorithm OptAug-CMDP for tabular finite-horizon CMDPs. Our algorithm is motivated by the augmented Lagrangian method and can be performed efficiently. We show that during K episodes of exploring the CMDP, our algorithm obtains a regret of tildeO(√K) for both the objective and the constraint violation. Unlike existing Lagrangian approaches, our algorithm achieves this regret without the need for the cancellation of errors.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 24 of its 54 references that are in the map. First posted on arXiv 12 Jun 2023.

Builds on

24 of 54 references.

References · 24

  1. 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 316
  2. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  4. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  5. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
  6. 2020Exploration-Exploitation in Constrained MDPscited by 149
  7. 2021Reward is enough for convex MDPscited by 84
  8. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  9. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  10. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  11. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 56
  12. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
12 more
  1. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 39
  2. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  3. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 34
  4. 2019Active Exploration in Markov Decision Processescited by 27
  5. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  6. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 23
  7. 2017Iteration complexity of inexact augmented Lagrangian methods for constrained convex programmingcited by 21
  8. 2020Active Model Estimation in Markov Decision Processescited by 20
  9. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 20
  10. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 19
  11. 2022Active Exploration via Experiment Design in Markov Chainscited by 19
  12. 2022A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimizationcited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 3.

7 papers.

  1. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  2. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 6
  3. 2024Operator Splitting for Convex Constrained Markov Decision Processescited by 4
  4. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Marginscited by 1
  5. 2026Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPscited by 1
  6. 2025Context-aware Constrained Reinforcement Learning Based Energy-Efficient Power Scheduling for Non-stationary XR Data Trafficcited by 0
  7. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0