mlsanityData to 14 Oct 2026

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

arXiv 2504.04973 ↗First posted 7 Apr 2025cs.LG cs.AI stat.MLcited by 0

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

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.

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.

Builds on

6 of 39 references.

References · 6

  1. 2014Microsoft COCO: Common Objects in Contextcited by 17,608
  2. 2015You Only Look Once: Unified, Real-Time Object Detectioncited by 4,852
  3. 2019Towards Robust Monocular Depth Estimation: Mixing Datasets for Zero-shot Cross-dataset Transfercited by 1,495
  4. 2024Hearing Touch: Audio-Visual Pretraining for Contact-Rich Manipulationcited by 14
  5. 2022F1 Hand: A Versatile Fixed-Finger Gripper for Delicate Teleoperation and Autonomous Graspingcited by 1
  6. 2023A Modular Bio-inspired Robotic Hand with High Sensitivitycited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Near-Optimal Sample Complexity for Online Constrained MDPs
  2. 2024Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time
  3. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
  4. 2024Truly No-Regret Learning in Constrained MDPs
  5. 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraints
  6. 2025Provably Efficient Sample Complexity for Robust CMDP
  7. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning
  8. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling