# Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 4 of its 53 references that are in the map.
- First posted on arXiv 8 Oct 2026.

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

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Replicable Constrained Bandits](https://mlsanity.com/paper/2602.14580/) (2026)
- [Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2509.20114/) (2025)

## Abstract (arXiv)

We study episodic constrained Markov decision processes with adversarial losses under stochastic hard constraints. Specifically, starting from a known strictly feasible policy with margin d, we seek to obtain optimal regret while satisfying the expected cost constraints in every episode. In this setting, Stradi et al. (2025) show that a carefully designed mixing rule attains regret of order widetildeO(√T/mind,d2). Interestingly, they also provide a lower bound of order Omega(√T/ρ) for the same setting, where ρ is the Slater margin of the offline problem and can be much larger than d. In this work, we build on their approach to obtain optimal regret dependence on these margins. Specifically, we propose MA-OPS, an algorithm that combines an optimistic search for the Slater margin with a pessimistic evaluation of the selected policies to safely learn a policy with a large feasibility margin. This policy is then used to minimize regret while satisfying the constraints at every episode. In particular, we show that MA-OPS attains regret widetildeO(√T/ρ + 1/(dρ)). Finally, we provide a matching lower bound, showing that the dependence on T, d, ρ in the regret bound is optimal up to logarithmic factors.