# Learning to Act Safely with Limited Exposure and Almost Sure Certainty

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 84 references that are in the map.
- First posted on arXiv 18 May 2021.

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

- [Speech Recognition with Deep Recurrent Neural Networks](https://mlsanity.com/paper/1303.5778/) (2013)
- [Control Barrier Functions: Theory and Applications](https://mlsanity.com/paper/1903.11199/) (2019)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [StarCraft II: A New Challenge for Reinforcement Learning](https://mlsanity.com/paper/1708.04782/) (2017)
- [Safe Exploration in Continuous Action Spaces](https://mlsanity.com/paper/1801.08757/) (2018)
- [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)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees](https://mlsanity.com/paper/1909.05304/) (2019)
- [Safe Exploration in Finite Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/1606.04753/) (2016)
- [Learning for Safety-Critical Control with Control Barrier Functions](https://mlsanity.com/paper/1912.10099/) (2019)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/1801.08099/) (2018)
- [Enforcing robust control guarantees within neural network policies](https://mlsanity.com/paper/2011.08105/) (2020)
- [Certified Reinforcement Learning with Logic Guidance](https://mlsanity.com/paper/1902.00778/) (2019)
- [Imitation Learning with Stability and Safety Guarantees](https://mlsanity.com/paper/2012.09293/) (2020)
- [Safety-Constrained Reinforcement Learning for MDPs](https://mlsanity.com/paper/1510.05880/) (2015)
- [Learning Stabilizable Nonlinear Dynamics with Contraction-Based Regularization](https://mlsanity.com/paper/1907.13122/) (2019)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [Stability-certified reinforcement learning: A control-theoretic perspective](https://mlsanity.com/paper/1810.11505/) (2018)
- [Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2010.00081/) (2020)
- [Policy Gradients for CVaR-Constrained MDPs](https://mlsanity.com/paper/1405.2690/) (2014)
- [Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning](https://mlsanity.com/paper/1612.02516/) (2016)
- [Formal Controller Synthesis for Continuous-Space MDPs via Model-Free Reinforcement Learning](https://mlsanity.com/paper/2003.00712/) (2020)
- [Regret Bounds for Safe Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2005.01936/) (2020)
- [Learning to be safe, in finite time](https://mlsanity.com/paper/2010.00417/) (2020)

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

- [Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2112.05198/) (2021)
- [Learning safety critics via a non-contractive binary bellman operator](https://mlsanity.com/paper/2401.12849/) (2024)

## Abstract (arXiv)

This paper puts forward the concept that learning to take safe actions in unknown environments, even with probability one guarantees, can be achieved without the need for an unbounded number of exploratory trials. This is indeed possible, provided that one is willing to navigate trade-offs between optimality, level of exposure to unsafe events, and the maximum detection time of unsafe actions. We illustrate this concept in two complementary settings. We first focus on the canonical multi-armed bandit problem and study the intrinsic trade-offs of learning safety in the presence of uncertainty. Under mild assumptions on sufficient exploration, we provide an algorithm that provably detects all unsafe machines in an (expected) finite number of rounds. The analysis also unveils a trade-off between the number of rounds needed to secure the environment and the probability of discarding safe machines. We then consider the problem of finding optimal policies for a Markov Decision Process (MDP) with almost sure constraints. We show that the action-value function satisfies a barrier-based decomposition which allows for the identification of feasible policies independently of the reward process. Using this decomposition, we develop a Barrier-learning algorithm, that identifies such unsafe state-action pairs in a finite expected number of steps. Our analysis further highlights a trade-off between the time lag for the underlying MDP necessary to detect unsafe actions, and the level of exposure to unsafe events. Simulations corroborate our theoretical findings, further illustrating the aforementioned trade-offs, and suggesting that safety constraints can speed up the learning process.