Safe Exploration in Markov Decision Processes

By Teodor Mihai Moldovan, Pieter Abbeel. 2012

333 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Reinforcement Learning

Citations in the corpus

Constrained Policy Optimization (2017, background): “In domains like this, safe exploration for RL agents is important (Moldovan & Abbeel, 2012; Amodei et al., 2016).”
Concrete Problems in AI Safety (2016, background): “Safety can be defined as remaining within an ergodic region of the state space such that actions are reversible [104, 159], or as limiting the probability of huge negative reward to some small value [156].”
Reinforcement Learning in Healthcare: A Survey (2019, methodology): “Other fundamental issues in RL research include but are not limited to the credit assignment problem [14], [27], the sampel/space/time complexity [28], [29], function approximation [30], [31], safety [32], [33], robustness [34], [35], and”
Verifiable Reinforcement Learning via Policy Extraction (2018, background): “Speciﬁc to reinforcement learning, there has been substantial interest in safe exploration [23, 36, 33]; see [14] for a survey.”
Reinforcement learning in robotics: A survey (2013, positive): “To apply reinforcement learning in robotics, safe exploration becomes a key issue of the learning process (Schneider, 1996; Bagnell, 2004; Deisenroth and Rasmussen, 2011; Moldovan and Abbeel, 2012), a problem often neglected in the general reinforcement learning community.”
Uncertainty-Aware Reinforcement Learning for Collision Avoidance (2017, methodology): “Uncertainty estimates have been used to perform both risk-averse and risk-seeking, optimistic exploration [19].”
Leave no Trace: Learning to Reset for Safe and Autonomous Reinforcement Learning (2017, background): “Previous work has examined safe exploration in small MDPs. Moldovan & Abbeel (2012a) examine risk-sensitive objectives for MDPs, and propose a new objective of which minmax and expectation optimization are both special cases.”
Safe Model-based Reinforcement Learning with Stability Guarantees (2017, background): “Both [11] and [12] introduce algorithms to safely explore MDPs so that the agent never gets stuck without safe actions.”
AI Safety Gridworlds (2017, background): “There are several possible formulations for safe exploration: being able to return to the starting state or some other safe state with high probability (Moldovan and Abbeel, 2012), achieving a minimum reward (Hans et al.”
Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics (2016, positive): “2017) or the system never leaves a safe subset of the state space (Ostafew et al. 2016; Aswani et al. 2013; Akametalu et al. 2014; Moldovan and Abbeel 2012; Turchetta et al. 2016).”
Dead-ends and Secure Exploration in Reinforcement Learning (2019, background): “…to assert an optimization criterion, such as worst case scenario (Heger, 1994), risk-sensitive criterion by transforming the TD error (Mihatsch & Neuneier, 2002), and call-time criterion by defining the safety in terms the probability of returning to the initial state (Moldovan & Abbeel, 2012).”
Combating Reinforcement Learning's Sisyphean Curse with Intrinsic Fear (2016, background): “[19] gives a deﬁnition of safety based on ergodicity.”
A comprehensive survey on safe reinforcement learning (2015, methodology): “These conclusions can also be obtained for Safe RL from Table 2 where most of the approaches address finite MDPs (Heger, 1994a; Gaskett, 2003; Moldovan and Abbeel, 2012a) and problems with continuous or large state spaces (Mihatsch and Neuneier, 2002; Geibel and Wysotzki, 2005; Thomaz and Breazeal,…”
Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning (2021, methodology): “1 Nonlinear (69, 79, 82), GP (78, 79, 80, 81) NN (70, 75, 85, 86, 87), Tabular (73) Input & state (69, 70, 73, 75, 78, 79, 80, 81, 82) Trajectory (87) Input & state (69, 70, 73, 75, 78, 79, 80, 81, 82) Trajectory (85, 86, 87) Stabilization (81), Tracking (79), Navigation (69, 70, 73, 82, 85, 86), Lo”
Probabilistically safe policy transfer (2017, background): “Typical constraints involve ensuring that either the expectation of the return exceeds a threshold [9], [13], [23], the variance of the return remains below a threshold [4], or that any state is reachable from any other state (ergodicity) [15], [19].”
Safe Exploration in Finite Markov Decision Processes with Gaussian Processes (2016, background): “This lemma follows directly from the definitions of ut(s), lt(s), wt(s) and Ct(s).”
Autonomous Reinforcement Learning via Subgoal Curricula (2021, background): “For an environment to be considered reversible, we assume that the MDP M E is ergodic, as deﬁned in [31].”