# Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization

arXiv: https://arxiv.org/abs/2410.02275 · HTML: https://mlsanity.com/paper/2410.02275/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 17 of 17)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising](https://mlsanity.com/paper/1802.08365/) (2018)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Safe Reinforcement Learning on Autonomous Vehicles](https://mlsanity.com/paper/1910.00399/) (2019)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization](https://mlsanity.com/paper/2003.01303/) (2020)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [Learning Adversarial MDPs with Stochastic Hard Constraints](https://mlsanity.com/paper/2403.03672/) (2024)
- [Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Study](https://mlsanity.com/paper/1709.03465/) (2017)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [Markov Persuasion Processes: Learning to Persuade from Scratch](https://mlsanity.com/paper/2402.03077/) (2024)
- [Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints](https://mlsanity.com/paper/2405.14372/) (2024)

## Built on by (most cited first, 12 of 12)

- [An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints](https://mlsanity.com/paper/2505.21841/) (2025)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Data-Dependent Regret Bounds for Constrained MABs](https://mlsanity.com/paper/2505.20010/) (2025)
- [Replicable Constrained Bandits](https://mlsanity.com/paper/2602.14580/) (2026)
- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2509.20114/) (2025)
- [Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins](https://mlsanity.com/paper/2602.10917/) (2026)
- [A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Models](https://mlsanity.com/paper/2504.04976/) (2025)
- [Truly Adapting to Adversarial Constraints in Constrained MABs](https://mlsanity.com/paper/2602.14543/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## 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.