Learning to Act Safely with Limited Exposure and Almost Sure Certainty
Not on the map. Why?
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.
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
30 of 84 references.
References · 30
- 2013Speech Recognition with Deep Recurrent Neural Networkscited by 669
- 2019Control Barrier Functions: Theory and Applicationscited by 372
- 2017Safe Model-based Reinforcement Learning with Stability Guaranteescited by 366
- 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 297
- 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 274
- 2018Safe Exploration in Continuous Action Spacescited by 247
- 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
- 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
- 2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 115
- 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
- 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
- 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 79
18 more
- 2019Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guaranteescited by 77
- 2016Safe Exploration in Finite Markov Decision Processes with Gaussian Processescited by 75
- 2019Learning for Safety-Critical Control with Control Barrier Functionscited by 69
- 2020Stochastic Bandits with Linear Constraintscited by 68
- 2018Logically-Constrained Reinforcement Learningcited by 51
- 2020Enforcing robust control guarantees within neural network policiescited by 40
- 2019Certified Reinforcement Learning with Logic Guidancecited by 36
- 2020Imitation Learning with Stability and Safety Guaranteescited by 34
- 2015Safety-Constrained Reinforcement Learning for MDPscited by 33
- 2019Learning Stabilizable Nonlinear Dynamics with Contraction-Based Regularizationcited by 32
- 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
- 2018Stability-certified reinforcement learning: A control-theoretic perspectivecited by 31
- 2020Stage-wise Conservative Linear Banditscited by 28
- 2014Policy Gradients for CVaR-Constrained MDPscited by 21
- 2016Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learningcited by 15
- 2020Formal Controller Synthesis for Continuous-Space MDPs via Model-Free Reinforcement Learningcited by 15
- 2020Regret Bounds for Safe Gaussian Process Bandit Optimizationcited by 4
- 2020Learning to be safe, in finite timecited by 1
Built on by
Citing papers per year: 2021: 1; 2022: 0; 2023: 0; 2024: 1.
2 papers.