mlsanityData to 14 Oct 2026

Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization

arXiv 2410.02275 ↗First posted 3 Oct 2024cs.LGcited by 12

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study online learning in constrained MDPs (CMDPs), focusing on the goal of attaining sublinear strong regret and strong cumulative constraint violation. Differently from their standard (weak) counterparts, these metrics do not allow negative terms to compensate positive ones, raising considerable additional challenges. Efroni et al. (2020) were the first to propose an algorithm with sublinear strong regret and strong violation, by exploiting linear programming. Thus, their algorithm is highly inefficient, leaving as an open problem achieving sublinear bounds by means of policy optimization methods, which are much more efficient in practice. Very recently, Muller et al. (2024) have partially addressed this problem by proposing a policy optimization method that allows to attain widetildeO(T0.93) strong regret/violation. This still leaves open the question of whether optimal bounds are achievable by using an approach of this kind. We answer such a question affirmatively, by providing an efficient policy optimization algorithm with widetildeO(√T) strong regret/violation. Our algorithm implements a primal-dual scheme that employs a state-of-the-art policy optimization approach for adversarial (unconstrained) MDPs as primal algorithm, and a UCB-like update for dual variables.

Key facts. Cited by 12 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 17 of its 29 references that are in the map. First posted on arXiv 3 Oct 2024.

Builds on

17 of 29 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints23 May
  2. 2024Learning Adversarial MDPs with Stochastic Hard Constraints6 Mar
  3. 2024Truly No-Regret Learning in Constrained MDPs24 Feb

Other references · 14

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  3. 2020Exploration-Exploitation in Constrained MDPscited by 149
  4. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  5. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  6. 2018Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertisingcited by 61
  7. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  8. 2019Safe Reinforcement Learning on Autonomous Vehiclescited by 50
  9. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  10. 2020Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimizationcited by 35
  11. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  12. 2017Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Studycited by 14
2 more
  1. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  2. 2024Markov Persuasion Processes: Learning to Persuade from Scratchcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 7.

12 papers.

  1. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 6
  2. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  3. 2025Data-Dependent Regret Bounds for Constrained MABscited by 2
  4. 2026Replicable Constrained Banditscited by 2
  5. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 2
  6. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  7. 2025Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraintscited by 1
  8. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Marginscited by 1
  9. 2025A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Modelscited by 0
  10. 2026Truly Adapting to Adversarial Constraints in Constrained MABscited by 0
  11. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  12. 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraintscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Near-Optimal Sample Complexity for Online Constrained MDPs
  2. 2024Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback
  3. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
  4. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
  5. 2026Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
  6. 2025Provably Efficient Sample Complexity for Robust CMDP
  7. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process
  8. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation