# Provable Safe Reinforcement Learning with Binary Feedback

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 50 references that are in the map.
- First posted on arXiv 26 Oct 2022.

## Builds on (most cited first, 28 of 28)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (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)
- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [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)
- [End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Tasks](https://mlsanity.com/paper/1903.08792/) (2019)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Lyapunov-based Safe Policy Optimization for Continuous Control](https://mlsanity.com/paper/1901.10031/) (2019)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Learning to be Safe: Deep RL with a Safety Critic](https://mlsanity.com/paper/2010.14603/) (2020)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Trial without Error: Towards Safe Reinforcement Learning via Human Intervention](https://mlsanity.com/paper/1707.05173/) (2017)
- [Safe Exploration in Finite Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/1606.04753/) (2016)
- [Safe Reinforcement Learning by Imagining the Near Future](https://mlsanity.com/paper/2202.07789/) (2022)
- [Safe Reinforcement Learning Using Advantage-Based Intervention](https://mlsanity.com/paper/2106.09110/) (2021)
- [Learning Barrier Certificates: Towards Safe Reinforcement Learning with Zero Training-time Violations](https://mlsanity.com/paper/2108.01846/) (2021)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [Safe Driving via Expert Guided Policy Optimization](https://mlsanity.com/paper/2110.06831/) (2021)
- [SAMBA: Safe Model-Based & Active Reinforcement Learning](https://mlsanity.com/paper/2006.09436/) (2020)
- [Safe Pontryagin Differentiable Programming](https://mlsanity.com/paper/2105.14937/) (2021)
- [Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL](https://mlsanity.com/paper/2206.14057/) (2022)
- [Provably Safe PAC-MDP Exploration Using Analogies](https://mlsanity.com/paper/2007.03574/) (2020)

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

- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Safety through feedback in Constrained RL](https://mlsanity.com/paper/2406.19626/) (2024)
- [Flipping-based Policy for Chance-Constrained Markov Decision Processes](https://mlsanity.com/paper/2410.06474/) (2024)
- [Model-Assisted Probabilistic Safe Adaptive Control With Meta-Bayesian Learning](https://mlsanity.com/paper/2307.00828/) (2023)
- [A Hormetic Approach to the Value-Loading Problem: Preventing the Paperclip Apocalypse?](https://mlsanity.com/paper/2402.07462/) (2024)
- [Approximating Safety Feedback Without a Safety Oracle via Model Predictive Control](https://mlsanity.com/paper/2510.20955/) (2025)
- [Safe Reinforcement Learning with Preference-based Constraint Inference](https://mlsanity.com/paper/2603.23565/) (2026)

## Abstract (arXiv)

Safety is a crucial necessity in many applications of reinforcement learning (RL), whether robotic, automotive, or medical. Many existing approaches to safe RL rely on receiving numeric safety feedback, but in many cases this feedback can only take binary values; that is, whether an action in a given state is safe or unsafe. This is particularly true when feedback comes from human experts. We therefore consider the problem of provable safe RL when given access to an offline oracle providing binary feedback on the safety of state, action pairs. We provide a novel meta algorithm, SABRE, which can be applied to any MDP setting given access to a blackbox PAC RL algorithm for that setting. SABRE applies concepts from active learning to reinforcement learning to provably control the number of queries to the safety oracle. SABRE works by iteratively exploring the state space to find regions where the agent is currently uncertain about safety. Our main theoretical results shows that, under appropriate technical assumptions, SABRE never takes unsafe actions during training, and is guaranteed to return a near-optimal safe policy with high probability. We provide a discussion of how our meta-algorithm may be applied to various settings studied in both theoretical and empirical frameworks.