  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.
