# Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints

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

## Key facts

- Cited by 1 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 21 of its 41 references that are in the map.
- First posted on arXiv 24 Sep 2025.

## 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, 21 of 21)

- [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)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [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)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising](https://mlsanity.com/paper/1802.08365/) (2018)
- [Safe Reinforcement Learning on Autonomous Vehicles](https://mlsanity.com/paper/1910.00399/) (2019)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [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)
- [No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions](https://mlsanity.com/paper/2305.17380/) (2023)
- [Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization](https://mlsanity.com/paper/2410.02275/) (2024)
- [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024)
- [Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints](https://mlsanity.com/paper/2405.14372/) (2024)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)

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

- [Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints](https://mlsanity.com/paper/2610.12153/) (2026)

## Abstract (arXiv)

We study online episodic Constrained Markov Decision Processes (CMDPs) under both stochastic and adversarial constraints. We provide a novel algorithm whose guarantees greatly improve those of the state-of-the-art best-of-both-worlds algorithm introduced by Stradi et al. (2025). In the stochastic regime, i.e., when the constraints are sampled from fixed but unknown distributions, our method achieves widetildeO(√T) regret and constraint violation without relying on Slater's condition, thereby handling settings where no strictly feasible solution exists. Moreover, we provide guarantees on the stronger notion of positive constraint violation, which does not allow to recover from large violation in the early episodes by playing strictly safe policies. In the adversarial regime, i.e., when the constraints may change arbitrarily between episodes, our algorithm ensures sublinear constraint violation without Slater's condition, and achieves sublinear α-regret with respect to the unconstrained optimum, where α is a suitably defined multiplicative approximation factor. We further validate our results through synthetic experiments, showing the practical effectiveness of our algorithm.