# Safe Exploration in Finite Markov Decision Processes with Gaussian Processes

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

## Key facts

- Cited by 75 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2016.

## Built on by (most cited first, 30 of 75)

- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Exploration in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2205.00824/) (2022)
- [Saute RL: Almost Surely Safe Reinforcement Learning Using State Augmentation](https://mlsanity.com/paper/2202.06558/) (2022)
- [Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environments](https://mlsanity.com/paper/2209.15090/) (2022)
- [Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain](https://mlsanity.com/paper/2109.06668/) (2021)
- [A Survey of Constraint Formulations in Safe Reinforcement Learning](https://mlsanity.com/paper/2402.02025/) (2024)
- [How to Certify Machine Learning Based Safety-critical Systems? A Systematic Literature Review](https://mlsanity.com/paper/2107.12045/) (2021)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [Provably Safe Reinforcement Learning: Conceptual Analysis, Survey, and Benchmarking](https://mlsanity.com/paper/2205.06750/) (2022)
- [Enforcing Policy Feasibility Constraints through Differentiable Projection for Energy Optimization](https://mlsanity.com/paper/2105.08881/) (2021)
- [Sustainable Online Reinforcement Learning for Auto-bidding](https://mlsanity.com/paper/2210.07006/) (2022)
- [GoSafe: Globally Optimal Safe Robot Learning](https://mlsanity.com/paper/2105.13281/) (2021)
- [Safe Pontryagin Differentiable Programming](https://mlsanity.com/paper/2105.14937/) (2021)
- [ActSafe: Active Exploration with Safety Constraints for Reinforcement Learning](https://mlsanity.com/paper/2410.09486/) (2024)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Safe Learning and Optimization Techniques: Towards a Survey of the State of the Art](https://mlsanity.com/paper/2101.09505/) (2021)
- [Safe Learning of Lifted Action Models](https://mlsanity.com/paper/2107.04169/) (2021)
- [A Human-Centered Safe Robot Reinforcement Learning Framework with Interactive Behaviors](https://mlsanity.com/paper/2302.13137/) (2023)
- [On Safety in Safe Bayesian Optimization](https://mlsanity.com/paper/2403.12948/) (2024)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [On Almost Surely Safe Alignment of Large Language Models at Inference-Time](https://mlsanity.com/paper/2502.01208/) (2025)
- [Reinforcement Learning for Safe Robot Control using Control Lyapunov Barrier Functions](https://mlsanity.com/paper/2305.09793/) (2023)
- [Risk-averse autonomous systems: A brief history and recent developments from the perspective of optimal control](https://mlsanity.com/paper/2109.08947/) (2021)
- [Near-Optimal Multi-Agent Learning for Safe Coverage Control](https://mlsanity.com/paper/2210.06380/) (2022)
- [A Review of Safe Reinforcement Learning Methods for Modern Power Systems](https://mlsanity.com/paper/2407.00304/) (2024)
- [Active learning for distributionally robust level-set estimation](https://mlsanity.com/paper/2102.04000/) (2021)
- [Safe Distributional Reinforcement Learning](https://mlsanity.com/paper/2102.13446/) (2021)
- [Safe Policy Optimization with Local Generalized Linear Function Approximations](https://mlsanity.com/paper/2111.04894/) (2021)
- [Online Learning of Non-Markovian Reward Models](https://mlsanity.com/paper/2009.12600/) (2020)

## Abstract (arXiv)

In classical reinforcement learning, when exploring an environment, agents accept arbitrary short term loss for long term gain. This is infeasible for safety critical applications, such as robotics, where even a single unsafe action may cause system failure. In this paper, we address the problem of safely exploring finite Markov decision processes (MDP). We define safety in terms of an, a priori unknown, safety constraint that depends on states and actions. We aim to explore the MDP under this constraint, assuming that the unknown function satisfies regularity conditions expressed via a Gaussian process prior. We develop a novel algorithm for this task and prove that it is able to completely explore the safely reachable part of the MDP without violating the safety constraint. To achieve this, it cautiously explores safe states and actions in order to gain statistical confidence about the safety of unvisited state-action pairs from noisy observations collected while navigating the environment. Moreover, the algorithm explicitly considers reachability when exploring the MDP, ensuring that it does not get stuck in any state with no safe way out. We demonstrate our method on digital terrain models for the task of exploring an unknown map with a rover.