# A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 44 references that are in the map.
- First posted on arXiv 8 Feb 2023.

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

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Projection-Based Constrained Policy Optimization](https://mlsanity.com/paper/2010.03152/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (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)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [Safe Exploration in Finite Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/1606.04753/) (2016)
- [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)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2102.08940/) (2021)
- [Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit](https://mlsanity.com/paper/1801.07780/) (2018)
- [Learning in Markov Decision Processes under Constraints](https://mlsanity.com/paper/2002.12435/) (2020)

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

- [A Survey of Constraint Formulations in Safe Reinforcement Learning](https://mlsanity.com/paper/2402.02025/) (2024)
- [Learning Adversarial MDPs with Stochastic Hard Constraints](https://mlsanity.com/paper/2403.03672/) (2024)
- [Provably Safe Reinforcement Learning with Step-wise Violation Constraints](https://mlsanity.com/paper/2302.06064/) (2023)
- [Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces](https://mlsanity.com/paper/2502.18655/) (2025)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Enhancing Safety in Reinforcement Learning with Human Feedback via Rectified Policy Optimization](https://mlsanity.com/paper/2410.19933/) (2024)
- [Flipping-based Policy for Chance-Constrained Markov Decision Processes](https://mlsanity.com/paper/2410.06474/) (2024)
- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences](https://mlsanity.com/paper/2603.20453/) (2026)
- [Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Information](https://mlsanity.com/paper/2306.08762/) (2023)
- [Absolute State-wise Constrained Policy Optimization: High-Probability State-wise Constraints Satisfaction](https://mlsanity.com/paper/2410.01212/) (2024)
- [Bi-Level Online Provisioning and Scheduling with Switching Costs and Cross-Level Constraints](https://mlsanity.com/paper/2601.18936/) (2026)
- [Escaping Offline Pessimism: Vector-Field Reward Shaping for Safe Frontier Exploration](https://mlsanity.com/paper/2603.18326/) (2026)
- [Data-Driven Synthesis of Probabilistic Controlled Invariant Sets for Linear MDPs](https://mlsanity.com/paper/2604.02727/) (2026)
- [A Queueing-Theoretic Framework for Dynamic Attack Surfaces: Data-Integrated Risk Analysis and Adaptive Defense](https://mlsanity.com/paper/2604.10427/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## Abstract (arXiv)

In many applications of Reinforcement Learning (RL), it is critically important that the algorithm performs safely, such that instantaneous hard constraints are satisfied at each step, and unsafe states and actions are avoided. However, existing algorithms for ''safe'' RL are often designed under constraints that either require expected cumulative costs to be bounded or assume all states are safe. Thus, such algorithms could violate instantaneous hard constraints and traverse unsafe states (and actions) in practice. Therefore, in this paper, we develop the first near-optimal safe RL algorithm for episodic Markov Decision Processes with unsafe states and actions under instantaneous hard constraints and the linear mixture model. It not only achieves a regret tildeO(fracd H3 √dKDeltac) that tightly matches the state-of-the-art regret in the setting with only unsafe actions and nearly matches that in the unconstrained setting, but is also safe at each step, where d is the feature-mapping dimension, K is the number of episodes, H is the number of steps in each episode, and Deltac is a safety-related parameter. We also provide a lower bound tildeOmega(maxdH √K, fracHDeltac2), which indicates that the dependency on Deltac is necessary. Further, both our algorithm design and regret analysis involve several novel ideas, which may be of independent interest.