Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
We study safe online reinforcement learning in Constrained Markov Decision Processes (CMDPs) under strong regret and violation metrics, which forbid error cancellation over time. Existing primal-dual methods that achieve sublinear strong reward regret inevitably incur growing strong constraint violation or are restricted to average-iterate convergence due to inherent oscillations. To address these limitations, we propose the Flexible safety Domain Optimization via Margin-regularized Exploration (FlexDOME) algorithm, the first to provably achieve near-constant tildeO(1) strong constraint violation alongside sublinear strong regret and non-asymptotic last-iterate convergence. FlexDOME incorporates time-varying safety margins and regularization terms into the primal-dual framework. Our theoretical analysis relies on a novel term-wise asymptotic dominance strategy, where the safety margin is rigorously scheduled to asymptotically majorize the functional decay rates of the optimization and statistical errors, thereby clamping cumulative violations to a near-constant level. Furthermore, we establish non-asymptotic last-iterate convergence guarantees via a policy-dual Lyapunov argument. Experiments corroborate our theoretical findings.
Key facts. Cited by 1 paper 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 20 of its 32 references that are in the map. First posted on arXiv 11 Feb 2026.
Builds on
20 of 32 references.
Closest ancestors · 5
Same direction, newest first
- 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints28 May
- 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization3 Oct
- 2024Learning Adversarial MDPs with Stochastic Hard Constraints6 Mar
- 2024Truly No-Regret Learning in Constrained MDPs24 Feb
- 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees31 Jan
Other references · 15
- 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 316
- 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
- 2020Exploration-Exploitation in Constrained MDPscited by 149
- 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
- 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
- 2018Hierarchical Game-Theoretic Planning for Autonomous Vehiclescited by 48
- 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
- 2024Quantum Circuit Optimization with AlphaTensorcited by 36
- 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 34
- 2024RL-GPT: Integrating Reinforcement Learning and Code-as-policycited by 32
- 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
- 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 20
3 more
- 2024A Review of Safe Reinforcement Learning Methods for Modern Power Systemscited by 11
- 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 7
- 2023Towards Real-World Applications of Personalized Anesthesia Using Policy Constraint Q Learning for Propofol Infusion Controlcited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2026Near-Optimal Sample Complexity for Online Constrained MDPs
- 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraints
- 2026Provably Safe Reinforcement Learning for Stochastic Reach-Avoid Problems with Entropy Regularization
- 2026Robust Peak-cost Constrained Reinforcement Learning
- 2025Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds
- 2025Foundations of Safe Online Reinforcement Learning in the Linear Quadratic Regulator: √T-Regret
- 2024Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time
- 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning