# Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds

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

## 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 6 of its 39 references that are in the map.
- First posted on arXiv 7 Apr 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, 6 of 6)

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [You Only Look Once: Unified, Real-Time Object Detection](https://mlsanity.com/paper/1506.02640/) (2015)
- [Towards Robust Monocular Depth Estimation: Mixing Datasets for Zero-shot Cross-dataset Transfer](https://mlsanity.com/paper/1907.01341/) (2019)
- [Hearing Touch: Audio-Visual Pretraining for Contact-Rich Manipulation](https://mlsanity.com/paper/2405.08576/) (2024)
- [F1 Hand: A Versatile Fixed-Finger Gripper for Delicate Teleoperation and Autonomous Grasping](https://mlsanity.com/paper/2205.07066/) (2022)
- [A Modular Bio-inspired Robotic Hand with High Sensitivity](https://mlsanity.com/paper/2309.16081/) (2023)

## Abstract (arXiv)

This paper studies constrained Markov decision processes (CMDPs) with constraints against stochastic thresholds, aiming at safety of reinforcement learning in unknown and uncertain environments. We leverage a Growing-Window estimator sampling from interactions with the uncertain environment to estimate the thresholds, based on which we design Stochastic Pessimistic-Optimistic Thresholding (SPOT), a novel model-based primal-dual algorithm for multiple constraints against stochastic thresholds. SPOT enables reinforcement learning under both pessimistic and optimistic threshold settings. We prove that our algorithm achieves sublinear regret and constraint violation; i.e., a reward regret of tildeO(√T) while allowing an tildeO(√T) constraint violation over T episodes. The theoretical guarantees show that our algorithm achieves performance comparable to that of an approach relying on fixed and clear thresholds. To the best of our knowledge, SPOT is the first reinforcement learning algorithm that realises theoretical guaranteed performance in an uncertain environment where even thresholds are unknown.