# Provably Safe Reinforcement Learning with Step-wise Violation Constraints

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 45 references that are in the map.
- First posted on arXiv 13 Feb 2023.

## Builds on (most cited first, 30 of 35)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Survey](https://mlsanity.com/paper/2009.13303/) (2020)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [Responsive Safety in Reinforcement Learning by PID Lagrangian Methods](https://mlsanity.com/paper/2007.03964/) (2020)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Safe Exploration in Continuous Action Spaces](https://mlsanity.com/paper/1801.08757/) (2018)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [IPO: Interior-point Policy Optimization under Constraints](https://mlsanity.com/paper/1910.09615/) (2019)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Safe Reinforcement Learning via Curriculum Induction](https://mlsanity.com/paper/2006.12136/) (2020)
- [Safe Reinforcement Learning by Imagining the Near Future](https://mlsanity.com/paper/2202.07789/) (2022)
- [Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environments](https://mlsanity.com/paper/2209.15090/) (2022)
- [Reachability Constrained Reinforcement Learning](https://mlsanity.com/paper/2205.07536/) (2022)
- [Convergent Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1910.12156/) (2019)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)

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

- [Iterative Reachability Estimation for Safe Reinforcement Learning](https://mlsanity.com/paper/2309.13528/) (2023)
- [Dynamic Model Predictive Shielding for Provably Safe Reinforcement Learning](https://mlsanity.com/paper/2405.13863/) (2024)
- [State-Wise Safe Reinforcement Learning With Pixel Observations](https://mlsanity.com/paper/2311.02227/) (2023)
- [One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2508.01561/) (2025)
- [Verified Safe Reinforcement Learning for Neural Network Dynamic Models](https://mlsanity.com/paper/2405.15994/) (2024)
- [Leveraging Approximate Model-based Shielding for Probabilistic Safety Guarantees in Continuous Environments](https://mlsanity.com/paper/2402.00816/) (2024)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [Flipping-based Policy for Chance-Constrained Markov Decision Processes](https://mlsanity.com/paper/2410.06474/) (2024)
- [Guardian: Decoupling Exploration from Safety in Reinforcement Learning](https://mlsanity.com/paper/2510.22859/) (2025)
- [WINFlowNets: Warm-up Integrated Networks Training of Generative Flow Networks for Robotics and Machine Fault Adaptation](https://mlsanity.com/paper/2603.17301/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## Abstract (arXiv)

In this paper, we investigate a novel safe reinforcement learning problem with step-wise violation constraints. Our problem differs from existing works in that we consider stricter step-wise violation constraints and do not assume the existence of safe actions, making our formulation more suitable for safety-critical applications which need to ensure safety in all decision steps and may not always possess safe actions, e.g., robot control and autonomous driving. We propose a novel algorithm SUCBVI, which guarantees widetildeO(√ST) step-wise violation and widetildeO(√H3SAT) regret. Lower bounds are provided to validate the optimality in both violation and regret performance with respect to S and T. Moreover, we further study a novel safe reward-free exploration problem with step-wise violation constraints. For this problem, we design an (varepsilon,δ)-PAC algorithm SRF-UCRL, which achieves nearly state-of-the-art sample complexity widetildeO((fracS2AH2varepsilon+fracH4SAvarepsilon2)(log(frac1δ)+S)), and guarantees widetildeO(√ST) violation during the exploration. The experimental results demonstrate the superiority of our algorithms in safety performance, and corroborate our theoretical results.