PaperlayerView exact revision on arXiv

Source-linked AI summary

Safe Exploration in Markov Decision Processes

Teodor Mihai Moldovan, Pieter Abbeel

arXiv:1205.4810v3cs.LG

TL;DR

Exploration methods often rely on ergodicity, which is impractical for many physical systems because unsafe exploration can cause them to break. This paper defines safety through ergodicity, develops a tractable guaranteed-safe approximation, and finds that it explores better than classical methods in experiments.

  • Problem

    Existing exploration algorithms provide strong guarantees under ergodicity, but that assumption rarely holds for physical systems where unsafe exploration can cause breakage.

  • Method

    The paper defines safety through policies that preserve ergodicity with controlled probability and replaces the NP-hard constraint with a stricter tractable constraint using expected transition measures and reward correction.

  • Results

    The method achieves safe exploration in contrast to plain exploration methods and supports exploration-bonus methods, including adapted R-max.

  • Takeaways & Limitations

    The framework can safely adapt exploration methods based on exploration bonuses and explores Martian terrain better than regular unsafe exploration at safety level .98.

  • Takeaways & Limitations

    Safety depends on policies rather than only safe states or state-actions, and the guaranteed-safe approximation may produce suboptimal exploration.

Abstract

from arXiv · show

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.

1. Introduction

Existing exploration methods often assume ergodicity, an assumption that can fail in physical systems because unsafe exploration may cause them to break. The paper defines safety through ergodicity, develops an efficient guaranteed-safe approximation, and reports safe exploration in experiments.

  • Motivation: Most existing exploration algorithms assume ergodicity, meaning any state is reachable from any other through a suitable policy.This assumption supports exploration guarantees based on favoring rarely visited states.
  • Motivation: Physical exploration examples can break during unsafe exploration, violating the ergodicity assumption.The paper notes that the assumption rarely holds for the physical systems motivating safe exploration.
  • Contributions: Safety is defined by restricting attention to policies that preserve ergodicity with a controlled probability.The resulting safety constraint is NP-hard to impose in general.
  • Contributions: The paper introduces an approximation scheme for guaranteed-safe exploration that may be suboptimal.It also incorporates uncertainty correlated across states, which can support learning about state-action pairs before visiting them.
  • Experiments: Experiments show safe exploration contrasting with plain exploration, with the method supporting exploration-bonus algorithms and grid worlds up to 50 100.The approach is reported as almost as computationally efficient as planning in a known MDP, although computation is repeated after every step.

2. Notation and Assumptions

The paper represents policies and initial-state distributions as probability measures and models uncertain dynamics with Bayesian beliefs over transition measures and rewards. These beliefs may allow arbitrary correlations between transitions and rewards, including correlations useful for safe exploration.

  • MDP notation: Policies and initial-state distributions are represented by probability measures, with δ(s) denoting a distribution concentrated on state s.The total reward is defined through a value expression, and the usual value recursion assumes a known transition measure.
  • Transition measures: Transition measures may sum to less than one, with missing mass assigned to an absorbing end state.This representation can model γ discounting by using γp as a transition measure.
  • Bayesian dynamics: Ambiguous dynamics are modeled Bayesianly by treating the transition measure as random and using a belief β over possible dynamics governing transitions and rewards.The expected return is taken under both the belief and policy.
  • Bayesian dynamics: The belief may permit arbitrary correlations between transition measures and rewards, which the paper states are usually necessary for safe exploration.The expected transition and reward quantities are denoted p := Eβ[P] and r := Eβ[R].

3. Problem formulation

The paper frames safe exploration as optimizing exploration policies subject to probabilistic ergodicity constraints. It shows why safety must be policy- and belief-dependent, while noting that exact enforcement is NP-hard.

  • 3.1. Exploration Objective: Exploration methods optimize constructed MDPs with exploration bonuses, and safety constraints can be added to this formulation.The framework applies to exploration methods that favor insufficiently known transitions with bonuses.
  • 3.2. Safety Constraint: Ergodicity requires that any state be reachable from any other state through some policy.The paper treats ergodicity as the basis for existing exploration guarantees.
  • 3.2. Safety Constraint: A policy is δ-safe when it preserves ergodicity with a user-specified probability δ.This restricts eligible policies while allowing a small probability of failure in non-ergodic environments.
  • 3.2. Safety Constraint: 25 wordsThe set of δ-safe policies is NP-hard to express or decide in general for a specified home state, belief, and stopping time.
  • 3.3. Safety Counter-Examples: Safety cannot generally be characterized by merely labeling states or state-actions as safe, because the same state-action may appear in safe and unsafe policies.The relevant distinction depends on policy behavior, including how often states or actions are visited.
  • 3.3. Safety Counter-Examples: Having a return policy for every possible MDP is insufficient when the return policy can differ across dynamics samples.The paper gives a belief over two MDPs where this condition holds but all policies remain naturally unsafe.
  • 3.3. Safety Counter-Examples: Safety cannot be defined using only the mean transition measure, because a policy can be unsafe under the belief but safe under the averaged MDP.Figure 3 uses two equally likely MDPs to demonstrate this mismatch.

4. Guaranteed Safe, Potentially Sub-optimal Exploration

The method replaces an NP-hard safety constraint with a stricter tractable constraint, then solves standard and constrained MDP problems to obtain guaranteed-safe exploration that may be suboptimal.

  • Optimization: The exploration objective uses an exploration bonus, while the optimization imposes a lower-bound safety constraint at level δ.Algorithm 1 takes a prior belief, discount γ, safety level δ, and an exploration-bonus function ξ.
  • Safety formulation: The safety constraint is converted into two MDP formulations, using a modified transition measure for first visits and a discounted MDP for the outer term.The inner term counts only the first time a state is reached; the outer term is represented through a γ-discounted MDP with a terminal reward converted to a step-wise reward.
  • Safety formulation: Replacing random transition measures with belief-expected measures and a reward correction yields a lower bound on expected value under the belief.The replacement makes the safety constraint more stringent but tractable.
  • Optimization: The resulting optimization replaces the NP-hard safety constraint with a stricter tractable constraint, producing guaranteed-safe but potentially suboptimal exploration.Suboptimality arises because optimization occurs over a restricted policy set.
  • Optimization: The procedure solves a standard MDP for the return policy and a constrained MDP for the exploration policy, both efficiently via linear programming or value iteration.The experiments use a linear-programming formulation with state-action occupation measures.
  • Experiments: The safe explorer uncovers the entire grid-world map by avoiding irreversible actions, whereas adapted R-max can get stuck before observing it.After more observations, the safe explorer may reclassify an initially unsafe transition as safe.

5. Experiments

The experiments evaluate adapted R-max safe exploration in grid worlds and a simulated Martian terrain task. Safety constraints improve exploration when ergodicity fails, while the Mars experiment demonstrates safer coverage than unsafe exploration.

  • Grid World: The grid-world task models height-limited movement with local sensing, where steep uphill moves fail and previously unseen neighboring heights are revealed on entry.The agent can descend cliffs but cannot climb slopes exceeding one height level.
  • Grid World: Adapted R-max makes exploration bonuses proportional to neighboring unknown states uncovered by each move and adds safety costs derived from the safety theorem.The practical safety correction was found to be twice as large as needed for a tight bound.
  • Grid World: Adding safety constraints improves the fraction of squares explored in randomly generated grid worlds because plain exploration loses its efficiency guarantees when ergodicity is violated.Figure 6 summarizes median and quartile coverage across grid sizes and levels of non-ergodicity.
  • Martian Terrain: The Mars model uses 20-by-20-meter states, allows slopes from -45 to 5 degrees, and represents terrain heights as independent Gaussian variables informed by HiRISE data.Remote sensing is modeled as Gaussian noise whose variance increases with measurement distance.
  • Martian Terrain: At safety level .98, the method covers more Martian terrain than unsafe exploration, which becomes stuck in a crater; safe exploration at level 1.0 is impossible.Naively constraining the expected transition measure performs as poorly as unsafe exploration at .98.
  • Martian Terrain: Table 1 reports per-step planning times for the 50×100 Mars grid world, while implementation details include repeated planning after each knowledge update.The experiments used γ = .999 for Mars exploration and restricted numerical precision to 10^-6 to avoid LP-solver instability.

6. Discussion

The framework supports multiple safety criteria beyond preserving ergodicity. These criteria can be combined and imposed at different confidence levels.

  • Alternative safety criteria: The framework supports stricter finite-horizon ergodicity, bounded probability of leaving a predefined safe set, and minimum expected total reward.These alternatives extend safety beyond eventual reachability alone.
  • Combining constraints: Any number and combination of the supported safety constraints can be imposed simultaneously at different δ-levels.This allows multiple safety requirements to be enforced within one constrained formulation.

Appendix

The appendix provides the NP-hardness reduction, supporting proof material, and an exploration-efficiency comparison. The reduction connects deciding safe policies to 3SAT satisfiability.

  • NP-hardness reduction: The NP-hardness proof reduces 3SAT to deciding whether a p-safe policy exists for a constructed belief over MDPs.The construction uses boolean assignments to determine whether transitions succeed.
  • NP-hardness reduction: The reduction represents clauses and variable assignments through state transitions whose success depends on the truth values associated with origin states.States S and D are assigned variables that are always true, while the belief is uniform over the remaining variables.
  • NP-hardness reduction: In the constructed MDP, a policy going from D to S and remaining in S is p-safe exactly when some boolean assignment makes D accessible from S.This accessibility condition is equivalent to satisfiability of the 3SAT formula.
  • Proof material: The appendix proof material includes the theorem statements and a lemma showing that a policy-dependent reward correction preserves expected total return in an averaged MDP.The proof concludes that the relevant value difference is identically zero.
  • Exploration-efficiency comparison: Figure 6 compares median and quartile fractions of uncovered grid worlds across explorers, grid sizes, and randomly introduced inaccessible squares.The comparison includes adapted R-max, original R-max, and Near-Bayesian exploration; the latter two behave identically in this environment.
Loading 1205.4810v3…