mlsanityData to 7 Oct 2026

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

arXiv 2302.04375 ↗First posted 8 Feb 2023cs.LG cs.AIcited by 15

Not on the map. Why?

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.

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

Builds on

32 of 44 references.

References · 32

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2018Reward Constrained Policy Optimizationcited by 397
  6. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  7. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  9. 2020Projection-Based Constrained Policy Optimizationcited by 195
  10. 2020Exploration-Exploitation in Constrained MDPscited by 146
  11. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  12. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
20 more
  1. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  2. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  3. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  4. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
  5. 2016Safe Exploration in Finite Markov Decision Processes with Gaussian Processescited by 72
  6. 2020Stochastic Bandits with Linear Constraintscited by 68
  7. 2018Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertisingcited by 60
  8. 2016Conservative Banditscited by 58
  9. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  10. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  11. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  12. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  13. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
  14. 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
  15. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  16. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  17. 2018Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limitcited by 27
  18. 2020Learning in Markov Decision Processes under Constraintscited by 20
  19. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  20. 2021Stability Constrained Reinforcement Learning for Real-Time Voltage Controlcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 5; 2025: 2; 2026: 6.

15 papers.

Sort:

By area:

  1. 2024A Survey of Constraint Formulations in Safe Reinforcement Learningcited by 42
  2. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  3. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  4. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spacescited by 6
  5. 2024Enhancing Safety in Reinforcement Learning with Human Feedback via Rectified Policy Optimizationcited by 5
  6. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  7. 2024Flipping-based Policy for Chance-Constrained Markov Decision Processescited by 3
  8. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferencescited by 1
  9. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 1
  10. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  11. 2024Absolute State-wise Constrained Policy Optimization: High-Probability State-wise Constraints Satisfactioncited by 0
  12. 2026Bi-Level Online Provisioning and Scheduling with Switching Costs and Cross-Level Constraintscited by 0
3 more
  1. 2026Escaping Offline Pessimism: Vector-Field Reward Shaping for Safe Frontier Explorationcited by 0
  2. 2026A Queueing-Theoretic Framework for Dynamic Attack Surfaces: Data-Integrated Risk Analysis and Adaptive Defensecited by 0
  3. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0