PaperlayerView exact revision on arXiv

Source-linked AI summary

Mo' States Mo' Problems: Emergency Stop Mechanisms from Observation

Samuel Ainsworth, Matt Barnes, Siddhartha Srinivasa

arXiv:1912.01649v1cs.LGstat.ML

TL;DR

The paper asks when environmental feedback is no longer beneficial and an e-stop reset is warranted. It uses support sets to terminate episodes outside expert-supported states, reporting faster convergence with a small asymptotic sub-optimality gap.

  • Problem

    The paper studies when along a training roll-out environmental feedback is no longer beneficial and an intervention such as resetting the agent is warranted.

    Source: §1 · p. 1

  • Method

    The method uses support sets and e-stop interventions, with triggers provided by an expert supervisor or learned from state-only observations.

    Source: §1 · pp. 1–2, §4.1 · p. 4

  • Results

    Empirical results on discrete and continuous environments show significantly faster convergence on a variety of problems with only a small asymptotic sub-optimality gap, if any.

    Source: §8 · p. 9

  • Takeaways & Limitations

    The trade-off may benefit problems with expensive environment interactions, finite-sample performance priorities, initial experimentation, or policy bootstrapping in larger state spaces.

    Source: §8 · p. 9

    The bounds upper-bound trajectory reward by H and avoid assumptions linking state visitation to value, leaving tighter bounds as an open direction.

    Source: §4.3 · p. 5

Abstract

from arXiv · show

In many environments, only a relatively small subset of the complete state space is necessary in order to accomplish a given task. We develop a simple technique using emergency stops (e-stops) to exploit this phenomenon. Using e-stops significantly improves sample complexity by reducing the amount of required exploration, while retaining a performance bound that efficiently trades off the rate of convergence with a small asymptotic sub-optimality gap. We analyze the regret behavior of e-stops and present empirical results in discrete and continuous settings demonstrating that our reset mechanism can provide order-of-magnitude speedups on top of existing reinforcement learning methods.

1 Introduction

The paper asks when environmental feedback ceases to help and an e-stop intervention is warranted, using expert-triggered or observation-learned resets. Its support-set framework restricts exploration and trades a small asymptotic sub-optimality gap for faster convergence.

1 Introduction

  • Prior examples include heuristic resets that terminate episodes when the pole exceeds a fixed angle and reset rules hard-coded into popular OpenAI Gym environments.The paper motivates learning e-stop interventions as a way to use resets beyond manually designed rules.Source: §1 · p. 1
  • A support set based on expert state visitation terminates episodes with a large penalty when the agent leaves the set, restricting exploration to a smaller state space.The set can be implicit, through a supervisor, or constructed from expert observation-only roll-outs.Source: §1 · pp. 1–2
  • The paper provides a framework for incorporating arbitrary supervisor-triggered e-stop interventions into any reinforcement learning algorithm.The framework uses support sets.Source: §1 · p. 2
  • The paper presents methods and analysis for constructing support sets from observations to create automatic e-stop devices.The introduction identifies state-only demonstrations as one source of observations.Source: §1 · pp. 1–2
  • Empirical results show significantly improved convergence rates with any reinforcement learning method while trading off a small asymptotic sub-optimality gap.The paper reports this pattern on benchmark discrete and continuous domains.Source: §1 · p. 2
  • The paper generalizes support sets to a spectrum of types and discusses their respective trade-offs.Source: §1 · p. 2

2 Related Work

Prior intervention methods include anomaly detection, safe-policy fallback, feedback reduction, and manually specified safety constraints. The paper positions its reset framework alongside these approaches and as complementary to methods using state-action demonstrations.

2 Related Work

  • Prior intervention approaches include anomaly detection with safe-policy fallback, requests for expert feedback, risk estimation, and shielding with manually specified safety constraints.Eysenbach et al. trade off hard resets for soft resets, whereas this paper learns when to perform hard resets.Source: §2 · p. 2
  • Learning-from-demonstration methods include learning reward functions from state-only trajectories, imitation learning with action feedback, and GAIL’s policy-distribution matching.The cited methods are Abbeel and Ng, Ross et al. [21], and GAIL [13], respectively.Source: §2 · p. 2
  • RLED methods use state-action demonstrations to initialize or bootstrap reinforcement learning, and the paper says its support-set approach can complement them.For example, DQfD [12] can pre-train a policy while this method reduces exploration during on-policy learning.Source: §2 · p. 3
  • The paper identifies limitations of existing bootstrapping techniques: they may require state-action data, online feedback, solving in the original state space, or offer no tabular guarantees.Because its method modifies the MDP once, it can be used with existing reinforcement learning algorithms and combined with other bootstrapping methods.Source: §2 · p. 3

3 Problem setup

The setup studies finite-horizon episodic Markov decision processes with a learner, an expert policy, and rewards. It frames the goal as minimizing external regret while using expert information to reduce the effective state space and required exploration.

3 Problem setup

  • The MDP is finite-horizon and episodic, with states, actions, transition probabilities, rewards, horizon H, and initial-state distribution; the learner and expert are policies in this setting.The expert may be sub-optimal, and the initial setup assumes it is realizable in the learner’s policy class.Source: §3 · p. 3
  • The problem is learning a policy that minimizes external regret over K episodes, with T = KH total time steps and cumulative reward tracked across those steps.Regret is compared with the expert policy.Source: §3 · p. 3
  • The setup assumes a reinforcement learning algorithm with regret bounds polynomial in the relevant discrete quantities, and considers either e-stop feedback or expert demonstration roll-outs.The demonstrations are of an expert policy in the MDP.Source: §3 · p. 3
  • The objective is to use expert demonstrations to decrease the effective state-space size and reduce the exploration required to learn in the MDP.Source: §3 · p. 3

4 Incorporating e-stop interventions

The section models e-stops as interventions that restrict learning to a support set, trading possible asymptotic sub-optimality for reduced exploration. It analyzes this trade-off for ideal and imperfect support sets.

4 Incorporating e-stop interventions

  • An e-stop terminates an episode when the agent leaves the support set, with no further reward; the learner then runs on the modified MDP.A supervisor can trigger stops online when the agent visits states outside the set.Source: §4 · pp. 3–4, §4.1 · p. 4

4.1 The sample complexity and asymptotic sub-optimality trade-off

  • The performance trade-off combines approximation error from the support-set choice with the modified MDP’s reinforcement-learning regret.The approximation error depends on the chosen set, while the learning complexity depends on its size rather than the full state space.Source: §4.1 · p. 4

4.2 Perfect e-stops

  • With perfect e-stops retaining every state the expert can visit, the modified MDP’s optimal policy achieves at least the expert policy’s reward in the true MDP.States the expert never visits can be removed without penalty under this condition.Source: §4.2 · p. 4

4.3 Imperfect e-stops

  • Removing states with nonzero expert hitting probability introduces policy error according to their visitation probabilities.The bound’s primary slack comes from upper-bounding a state trajectory’s cumulative reward by H; the analysis makes no assumption linking hitting probability to value.Source: §4.3 · p. 5

5 Learning from observation

This section builds learned e-stop triggers from expert state observations, including settings where action observations are unavailable. It estimates which states the expert visits, removes low-probability states subject to an allowance, and analyzes the resulting performance trade-off.

5 Learning from observation

  • The method builds an e-stop trigger from expert state-only roll-outs, a useful setting when action observations are unavailable, such as video.The authors estimate state hitting probabilities from demonstrations, then remove low-probability states while respecting a state-removal allowance.Source: §5 · p. 5
  • The state-removal allowance, number of expert trajectories, and asymptotic sub-optimality gap trade off against one another.The authors report performance is fairly robust to the number of trajectories and expert quality in their experiments.Source: §5 · p. 6
  • The discrete analysis extends to continuous domains by estimating and thresholding the expert’s state distribution instead of hitting probabilities.The corresponding appendix bound retains a dependence on |S|.Source: §5 · p. 6

6 Empirical study

Across discrete and continuous experiments, e-stops improved sample efficiency and convergence, with results also depending on pruning aggressiveness and the expert-state support used. The experiments report robustness to imperfect experts and limited demonstrations, alongside faster continuous-control learning.

6.1 Discrete environments

  • Across planning and reinforcement learning, tabular and policy-gradient methods, e-stops were more sample-efficient; continuous runs also showed faster, more robust training.In continuous control, e-stop agents converged faster and with lower variance than their full-environment counterparts.Source: §6.1 · p. 6, §6.2 · p. 8, Figure 4 · p. 8
  • More aggressive pruning speeds convergence but can remove states crucial to reaching the goal, worsening the sub-optimality gap.The value-iteration experiments varied the support-set size by progressively pruning states according to expert hitting probability.Source: §6.1 · pp. 6–7
  • Removing half the states with the lowest hitting probabilities had a minor effect on Q-learning’s asymptotic performance but dramatically improved convergence.The authors also report drastic speedups for one-step actor-critic relative to training in the full environment.Source: §6.1 · p. 7
  • E-stop performance was robust to poor expert policies, and in this experiment as few as 10 expert roll-outs produced very good e-stop MDPs.These findings suggest the method needs a “good enough” set of states rather than a fully optimal expert or many demonstrations.Source: §6.1 · p. 7, Figure 3 · p. 7

6.2 Continuous environments

  • On pendulum and HalfCheetah, e-stop agents converged faster and more reliably; on HalfCheetah they consistently outperformed full-environment DDPG policies.The authors attribute the HalfCheetah result in part to e-stops eliminating states associated with local-minimum behaviors.Source: Figure 4 · p. 8, §6.2 · p. 8
  • Continuous experiments used simple min/max state-value bounds based on roll-outs of the best full-environment policy; this improved sample complexity and stabilized learning.The experiments covered inverted pendulum control and HalfCheetah-v3.Source: §6.2 · pp. 7–8

7 Types of support sets and their tradeoffs

This section compares time-dependent support sets with visitation-count support sets as alternatives to a single support set. They address over-support in different ways, with memory and demonstration trade-offs.

7 Types of support sets and their tradeoffs

  • Time-dependent sets increase memory complexity from O(|S|) to O(|S|H).When state distributions across time are similar, using their union effectively increases the number of demonstrations by a factor of H.Source: §7 · p. 9
  • Time-dependent support sets can trigger an intervention when the agent remains in a state that is supported at the start but not at later time steps.In the example, a single union support set would allow the agent to remain at the start state for the episode.Source: §7 · p. 9
  • The section presents visitation counts as an alternative support-set construction balancing trade-offs of the earlier constructions.The authors leave exploration of this and other potential e-stop constructions to future work.Source: §7 · p. 9
  • Visitation-count support terminates an episode without further reward when the agent visits a state more often than the demonstrator.It uses an auxiliary state to track the number of visits to each state.Source: §7 · p. 9
  • The visitation-count mechanism has memory requirements independent of H and fixes some over-support issues in the single-set construction.The optimal policy in this modified MDP achieves at least as much cumulative reward as the expert policy.Source: §7 · p. 9

8 Conclusions

The paper presents e-stops and learned triggers as a way to restrict learning to a smaller support set, trading some asymptotic performance for faster convergence. Its reported results show that this trade-off can yield faster learning, while the bounds and suggested extensions have scope limits.

8 Conclusions

  • E-stops trade a small asymptotic sub-optimality gap for significantly lower sample complexity by restricting learning to a support set.The support-set size can be tuned to adjust this trade-off.Source: §8 · p. 9
  • Discrete and continuous experiments show significantly faster convergence with only a small asymptotic sub-optimality gap, if any.The authors identify this trade-off as useful when environment interactions are expensive and finite-sample performance matters.Source: §8 · p. 9
  • The bounds capture exploration reduction from shrinking the state space; the authors suggest high-dimensional anomaly detectors and tighter bounds using termination knowledge.They identify one-class SVMs and auto-encoders as possible detectors.Source: §8 · p. 9

A Proof of Eq. (5)

The appendix proofs develop regret and performance guarantees for e-stop MDPs. They include an ideal support-set result and a bound framed in terms of expert state-hitting probabilities and an allowance.

A Proof of Eq. (5)

  • The Eq. (5) proof bounds regret after running a reinforcement-learning algorithm in an e-stop MDP.The passage sets this result in a finite-horizon episodic MDP and begins from the external-regret definition.Source: A Proof of Eq. (5) · p. 12

B Proof of Theorem 4.1

  • With the support set equal to states the expert can hit, the optimal policy in the e-stop MDP achieves at least the expert policy’s reward in the original MDP.The theorem assumes the expert policy is realizable in the learner’s policy class.Source: B Proof of Theorem 4.1 · p. 12

C Proof of Theorem 4.2

  • Theorem 4.2 frames the e-stop performance bound using expert-policy state-hitting probabilities and an allowance ξ for removed-state mass.The proof analyzes trajectory probabilities and rewards in the original and e-stop MDPs.Source: C Proof of Theorem 4.2 · pp. 12–13

D Proof of Corollary 4.2.1

The corollary follows from Theorem 4.2 using a union bound over time steps. It uses the expert policy’s average state distribution.

D Proof of Corollary 4.2.1

  • The corollary uses the expert policy’s average state distribution and a union bound over time steps as a consequence of Theorem 4.2.The supplied passage identifies the distribution as ρπe(s).Source: D Proof of Corollary 4.2.1 · p. 13

E Proof of Theorem 5.1

The appendix gives guarantees for approximate e-stops based on hitting probabilities and average state distributions, then records experimental procedures for discrete and continuous settings. The average-distribution approach has additional scope constraints.

E Proof of Theorem 5.1

  • Theorem 5.1 gives an asymptotic sub-optimality result for approximate e-stops, with confidence at least 1 − |S|e^(−2ϵ²n/|S|²).The removed-state allowance ξ bounds the estimated hitting-probability mass outside the constructed support set.Source: E Proof of Theorem 5.1 · p. 13

F Imperfect e-stops in terms of ˆρπe(s)

  • The ρπe-based result requires complete expert roll-outs with no terminal states and retains a dependence on |S|.This approach is presented because hitting-probability analysis does not extend readily to continuous domains.Source: F Imperfect e-stops in terms of ˆρπe(s) · p. 14
  • Theorem F.1 gives an asymptotic sub-optimality result with confidence at least 1 − δ when the estimated removed-state ρ-mass is at most ξ.The proof uses an empirical Bernstein bound; Vn denotes the sample variance.Source: F Imperfect e-stops in terms of ˆρπe(s) · p. 14

G Experimental details

  • The experimental details report Numpy and JAX implementations, AWS runs, and public code and results.The code and results are hosted on GitHub.Source: G Experimental details · p. 15

G.1 Value iteration

  • Value iteration establishes the optimal policy; in the discrete setup, state hitting probabilities were calculated exactly using an absorbing-Markov-chain interpretation.States were removed in ranked order until no feasible path to the goal remained.Source: §G.1 · p. 15

G.2 Policy gradient methods

  • After value iteration on the full environment converged (tolerance 1e−6), 1,000 roll-outs estimated optimal-policy state hitting probabilities, and least-visited 50% of states were replaced with e-stops; Q-learning and Actor-Critic ran across 96 trials (seeds 0-95).Median performance was plotted per states seen; error bars show one standard deviation around the mean, clipped to maximum and minimum values.Source: §G.2 · p. 15

G.3 DDPG

  • Continuous experiments used DDPG with γ = 0.99, τ = 0.0001, learning rate 0.001, and batch size 128.The setup also used normally distributed action noise with standard deviation 0.1.Source: §G.3 · p. 16
Loading 1912.01649v1…