  In environments with uncertain dynamics exploration is necessary to learn how
to perform well. Existing reinforcement learning algorithms provide strong
exploration guarantees, but they tend to rely on an ergodicity assumption. The
essence of ergodicity is that any state is eventually reachable from any other
state by following a suitable policy. This assumption allows for exploration
algorithms that operate by simply favoring states that have rarely been visited
before. For most physical systems this assumption is impractical as the systems
would break before any reasonable exploration has taken place, i.e., most
physical systems don't satisfy the ergodicity assumption. In this paper we
address the need for safe exploration methods in Markov decision processes. We
first propose a general formulation of safety through ergodicity. We show that
imposing safety by restricting attention to the resulting set of guaranteed
safe policies is NP-hard. We then present an efficient algorithm for guaranteed
safe, but potentially suboptimal, exploration. At the core is an optimization
formulation in which the constraints restrict attention to a subset of the
guaranteed safe policies and the objective favors exploration policies. Our
framework is compatible with the majority of previously proposed exploration
methods, which rely on an exploration bonus. Our experiments, which include a
Martian terrain exploration problem, show that our method is able to explore
better than classical exploration methods.
