mlsanityData to 14 Oct 2026

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints

arXiv 2505.21841 ↗First posted 28 May 2025cs.LG cs.AIcited by 6

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

Abstract (arXiv)

Online safe reinforcement learning (RL) plays a key role in dynamic environments, with applications in autonomous driving, robotics, and cybersecurity. The objective is to learn optimal policies that maximize rewards while satisfying safety constraints modeled by constrained Markov decision processes (CMDPs). Existing methods achieve sublinear regret under stochastic constraints but often fail in adversarial settings, where constraints are unknown, time-varying, and potentially adversarially designed. In this paper, we propose the Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm, the first to address online CMDPs with anytime adversarial constraints. OMDPD achieves optimal regret O(sqrt(K)) and strong constraint violation O(sqrt(K)) without relying on Slater's condition or the existence of a strictly known safe policy. We further show that access to accurate estimates of rewards and transitions can further improve these bounds. Our results offer practical guarantees for safe decision-making in adversarial environments.

Key facts. Cited by 6 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 27 of its 36 references that are in the map. First posted on arXiv 28 May 2025.

Builds on

27 of 36 references.

Closest ancestors · 4

Same direction, newest first

  1. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization3 Oct
  2. 2024Learning Adversarial MDPs with Stochastic Hard Constraints6 Mar
  3. 2024Truly No-Regret Learning in Constrained MDPs24 Feb
  4. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees31 Jan

Other references · 23

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 337
  4. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  6. 2020Exploration-Exploitation in Constrained MDPscited by 149
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  8. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  9. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  10. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  11. 2019Safe Reinforcement Learning on Autonomous Vehiclescited by 50
  12. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
11 more
  1. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  2. 2023Optimal Algorithms for Online Convex Optimization with Adversarial Constraintscited by 34
  3. 2020Asymptotically Optimal Information-Directed Samplingcited by 33
  4. 2019Online Primal-Dual Mirror Descent under Stochastic Constraintscited by 31
  5. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  6. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  7. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  8. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  9. 2024An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraintscited by 11
  10. 2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
  11. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 6.

6 papers.

  1. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 2
  2. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  3. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Marginscited by 1
  4. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  5. 2026Boundary-Seeking Policy Gradient for Safe Reinforcement Learningcited by 0
  6. 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraintscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints
  2. 2024Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback
  3. 2026Near-Optimal Sample Complexity for Online Constrained MDPs
  4. 2026Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
  5. 2025Mirror Descent Policy Optimisation for Robust Constrained Markov Decision Processes
  6. 2024Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time
  7. 2025Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds
  8. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints