PaperlayerView exact revision on arXiv

Source-linked AI summary

Better-than-Demonstrator Imitation Learning via Automatically-Ranked Demonstrations

Daniel S. Brown, Wonjoon Goo, Scott Niekum

arXiv:1907.03976v3cs.LGstat.ML

TL;DR

Imitation learning often cannot exceed the demonstrator, and ranked demonstrations offer a route to improvement but are difficult to obtain and lack established theoretical conditions. The paper provides theory and introduces D-REX, which uses noise in a behaviorally cloned policy to generate ranked demonstrations. On simulated robot and Atari tasks, D-REX outperforms standard imitation learning and exceeds the best demonstration in 8 of 9 tasks.

  • Problem

    Imitation learning typically does not exceed demonstrator performance, while theoretical conditions for improvement from ranked demonstrations and accessible rankings remain limited.

    Source: §1 · pp. 1–2

  • Method

    D-REX adds noise at increasing levels to a behaviorally cloned policy to generate ranked demonstrations for reward learning and policy optimization.

    Source: §1 · p. 2, §7 · p. 8

  • Results

    D-REX outperforms state-of-the-art imitation learning techniques and the best demonstration in 8 out of 9 simulated robot locomotion and Atari tasks.

    Source: §7 · p. 9

  • Takeaways & Limitations

    Automatically generated rankings make ranking- and preference-based learning applicable to imitation-learning settings with only unlabeled demonstrations.

    Source: §7 · p. 9

    The setup assumes demonstrations come from a policy attempting, possibly unsuccessfully, to optimize an unavailable true reward.

    Source: §3 · p. 3

Abstract

from arXiv · show

The performance of imitation learning is typically upper-bounded by the performance of the demonstrator. While recent empirical results demonstrate that ranked demonstrations allow for better-than-demonstrator performance, preferences over demonstrations may be difficult to obtain, and little is known theoretically about when such methods can be expected to successfully extrapolate beyond the performance of the demonstrator. To address these issues, we first contribute a sufficient condition for better-than-demonstrator imitation learning and provide theoretical results showing why preferences over demonstrations can better reduce reward function ambiguity when performing inverse reinforcement learning. Building on this theory, we introduce Disturbance-based Reward Extrapolation (D-REX), a ranking-based imitation learning method that injects noise into a policy learned through behavioral cloning to automatically generate ranked demonstrations. These ranked demonstrations are used to efficiently learn a reward function that can then be optimized using reinforcement learning. We empirically validate our approach on simulated robot and Atari imitation learning benchmarks and show that D-REX outperforms standard imitation learning approaches and can significantly surpass the performance of the demonstrator. D-REX is the first imitation learning approach to achieve significant extrapolation beyond the demonstrator's performance without additional side-information or supervision, such as rewards or human preferences. By generating rankings automatically, we show that preference-based inverse reinforcement learning can be applied in traditional imitation learning settings where only unlabeled demonstrations are available.

1 Introduction

Imitation learning often fails to exceed the demonstrator, and prior better-than-demonstrator approaches require rewards, human supervision, or ranked demonstrations; theoretical conditions for improvement were lacking. The paper develops theory and D-REX, which automatically ranks demonstrations by adding noise to a behaviorally cloned policy, and reports better-than-demonstrator performance without extra supervision or side-information.

1 Introduction

  • The work addresses the difficulty of obtaining demonstration rankings and the lack of theory for predicting when ranked demonstrations can exceed demonstrator performance.Earlier methods either required a hand-crafted reward [2] [3] [4] or a human supervisor [5] [6] [7].Source: §1 · pp. 1–2
  • The paper presents theoretical results on when inverse reinforcement learning can achieve better-than-demonstrator performance and how rankings reduce reward-function error and ambiguity.The IRL setting aims to recover a reward function from demonstrations.Source: §1 · p. 1
  • D-REX injects increasing noise into a behaviorally cloned policy to automatically produce demonstrations ranked by performance, then learns a reward function from those rankings.The approach assumes demonstrations outperform a purely random policy and that added noise progressively worsens performance toward random behavior.Source: §1 · p. 2, Figure 1 · p. 2
  • D-REX significantly outperforms standard imitation learning and the demonstrator on simulated robotics and Atari benchmarks, without extra supervision or side-information.The authors report this as the first such imitation learning approach.Source: §1 · p. 2

2 Related Work

Related work covers reward-based and inverse-reinforcement-learning approaches, preference learning, and methods using noisy trajectories. The paper distinguishes D-REX by automatically generating ranked demonstrations from a cloned policy rather than relying on supplied rankings or repeated perturbed demonstrations.

2 Related Work

  • Reward-based policy improvement can use demonstrations for initialization, but designing rewards for reinforcement learning can be difficult and may produce unintended behavior [20].Inverse reinforcement learning infers a reward that explains demonstrations, while some suboptimal-demonstration methods require manual clustering or labels.Source: §2 · p. 2
  • A feature-based apprenticeship method can outperform the demonstrator when reward-feature signs are known, but requires hand-crafted linear features and repeated MDP solving.Other approaches to better-than-demonstrator performance use active human queries [6, 9, 11] or hand-crafted rewards [18, 2].Source: §2 · p. 3
  • Prior preference-learning approaches use active queries [6] [10] [11] or pre-ranked demonstrations [27] [7]; T-REX [7] can surpass suboptimal demonstrators but lacks theory on when extrapolation is possible.The paper positions its work as providing that theory and applying ranking-based learning when human rankings are unavailable.Source: §2 · p. 3
  • Earlier noisy-trajectory methods estimate a maximum-entropy IRL partition function using random or locally perturbed trajectories, while DART [31] perturbs demonstrations to enrich behavioral-cloning data.D-REX instead clones once from a small number of initial demonstrations, then injects varying noise to create ranked demonstrations without human preference labels.Source: §2 · p. 3

3 Problem Statement

The problem is to learn a policy from demonstrations that earns more under the unknown true reward than the demonstrations do. The setup defines both average demonstration performance and a stricter comparison against the best individual demonstration.

3 Problem Statement

  • The environment is modeled as an MDP with states, actions, transition probabilities, a true reward function, and a discount factor; a policy maps states to action distributions.The expected discounted return of a policy is denoted J(π|R*).Source: §3 · p. 3
  • The true reward is unavailable, and the demonstrations are assumed to come from a demonstrator attempting, possibly unsuccessfully, to optimize it.The target learned policy must achieve higher expected return under the true reward than the demonstrations’ average return.Source: §3 · p. 3
  • A policy extrapolates beyond the demonstrations when its expected return under the true reward exceeds their average return, J(D|R*).The average is taken across the demonstrated trajectories.Source: §3 · p. 3
  • Extrapolating beyond the best demonstration is a stricter criterion: the learned policy’s return must exceed the maximum return among individual demonstrations.Source: §3 · p. 3

4 Extrapolating Beyond a Demonstrator: Theory

The theory gives sufficient conditions for better-than-demonstrator performance in inverse reinforcement learning and shows that trajectory rankings can reduce reward ambiguity. Ranked demonstrations also provide information that observation-only IRL lacks.

4 Extrapolating Beyond a Demonstrator: Theory

  • Extrapolation is guaranteed when the demonstrator is sufficiently suboptimal, reward approximation error is small, and the optimized policy’s state occupancy is sufficiently close to the optimal policy’s.The paper identifies these as the key conditions for the sufficient result.Source: §4 · p. 4

4.1 Extrapolation via ranked demonstrations

  • A reward function that fits demonstrations can still be superficial and overfit suboptimal behavior, limiting generalization.The paper notes that matching demonstrations alone may miss important details of the true reward structure.Source: §4.1 · pp. 4–5
  • A total ranking over policies yields reward ambiguity no greater than inverse reinforcement learning from the optimal policy alone.Pairwise preferences add half-space constraints, and random constraints reduce ambiguity exponentially.Source: §4.1 · p. 5
  • Rankings can reduce reward ambiguity and improve IRL efficiency by turning reward inference into supervised learning without an inner-loop MDP solver.The proposed method uses noise injection to produce automatically ranked demonstrations.Source: §4.1 · p. 5

5 Algorithm

D-REX uses behavioral cloning and noise injection to generate rankings automatically, then applies T-REX to learn a reward function for reinforcement-learning policy optimization. Its ranking assumption is that greater noise corresponds to worse performance.

5.1 Trajectory-ranked Reward Extrapolation (T-REX)

  • T-REX learns a reward function from ranked trajectories using supervised pairwise ranking, then combines that reward with reinforcement learning to optimize a policy.Its ranking loss is based on the Luce-Shephard choice rule.Source: §5.1 · p. 5

5.2 Disturbance-based Reward Extrapolation (D-REX)

  • D-REX clones unranked demonstrations, injects noise at different levels, labels higher-noise trajectories as worse, and uses T-REX before reinforcement-learning optimization.The algorithm returns the policy optimized against the learned reward.Source: §5.1 · p. 6, §5.2 · p. 6
  • With a cloned policy better than random, increasing noise is intended to interpolate toward uniformly random behavior and, with high probability, produce progressively worse policies.The ϵ-greedy policy follows the clone with probability 1−ϵ and selects a uniformly random action otherwise.Source: §5.2 · p. 6
  • Using K rollouts at each of d noise levels produces K × d ranked trajectories, with trajectories from the same noise level treated as equally preferred.The number of generated demonstrations can be increased by generating more rollouts.Source: §5.2 · p. 6

6 Experimental Results

Across the reported tasks, D-REX’s noise injection degrades cloned-policy performance and supports reward extrapolation; policies optimized with D-REX exceed the best demonstration on all tasks except Pong. The reward predictions correlate relatively strongly with true returns across most tasks.

6.1 Automatically generating rankings via noise

  • As noise increases, cloned-policy performance degrades toward the level of a uniformly random policy, supporting the assumption of near-monotonic degradation in expectation.The evaluation used Hopper and Half-Cheetah plus seven Atari games.Source: §6.1 · p. 6, Figure 2 · p. 7

6.2 Reward extrapolation

  • D-REX’s predicted returns correlate relatively strongly with ground-truth returns across most evaluated tasks, including held-out trajectories beyond the demonstration performance.Figure 3 compares normalized predicted returns with ground-truth returns for synthetic, original, and additional trajectories.Source: §6.2 · p. 7, Figure 3 · p. 7

6.3 Extrapolating beyond the demonstrator’s performance

  • D-REX beats the best demonstration on every task except Pong, and beats BC and GAIL on every task except Hopper and Pong.Table 1 compares the methods using best average ground-truth returns over three seeds and 20 trials per seed.Source: Table 1 · p. 8, §6.3 · p. 8
  • D-REX gains 77% on Hopper and 418% on HalfCheetah versus the best demonstration; excluding Q*Bert, Atari gains average 39%.On Q*Bert, D-REX exploits a known loophole that allows nearly infinite points.Source: §6.3 · p. 8

7 Conclusion

The paper develops theory for when imitation learning can exceed a demonstrator and how rankings reduce reward ambiguity, then introduces D-REX to generate ranked demonstrations automatically. Across simulated robot locomotion and Atari tasks, D-REX outperforms state-of-the-art imitation learning and the best demonstration in 8 of 9 tasks.

7 Conclusion

  • The paper gives a sufficient condition for extrapolation and shows theoretically that preferences and rankings reduce uncertainty over the true reward function.The theory addresses when better-than-demonstrator performance is possible and how rankings improve reward learning.Source: §7 · p. 8
  • D-REX automatically generates ranked demonstrations through noise injection and uses them to seek performance beyond a suboptimal demonstrator.The method is proposed for settings with only unlabeled demonstrations.Source: §7 · pp. 8–9
  • D-REX outperforms state-of-the-art imitation learning and the best demonstration in 8 out of 9 simulated robot locomotion and Atari tasks.The paper presents these results as evidence of better-than-demonstrator learning without extra rewards, active supervision, or preference labels.Source: §7 · p. 9

A Theory and Proofs

The theory represents reward as a linear combination of features and gives a sufficient condition for inverse reinforcement learning to produce a policy that beats the demonstrator under the true reward. The stated setting assumes the learner and demonstrator share a state space.

A Theory and Proofs

  • The demonstrator’s reward is approximated by a linear feature combination, and policy return is expressed using expected discounted feature counts.The features may be arbitrarily complex, including activations from a deep neural network’s penultimate layer.Source: A Theory and Proofs · p. 11
  • Theorem 1 guarantees extrapolation when the demonstrator’s true-reward optimality gap δ exceeds ε_Φ − 2||ε||∞.Here ε_Φ is the infinity-norm gap between optimal and learned policy feature counts, and ||ε||∞ is the reward-error bound.Source: A Theory and Proofs · pp. 11–12
  • The theorem assumes the learner and demonstrator operate in the same state space, though their transition dynamics and action spaces need not match.The authors suggest imitation from observation as a possible way to learn an initial cloned policy without demonstrator actions.Source: A Theory and Proofs · p. 12

A.1 Extrapolation via ranked demonstrations

This section explains how ranked demonstrations can reveal reward distinctions that a single expert demonstration may leave ambiguous, and how policy rankings constrain the reward functions consistent with optimal behavior.

A.1 Extrapolation via ranked demonstrations

  • A reward learned from demonstrations can overfit the examples and miss important reward differences, impairing transfer when initial states or transition dynamics change.The paper notes this risk when an action that previously reached a preferred state instead reaches another state after dynamics change.Source: §A.1 · p. 13
  • Ranked demonstrations encode both preferred and rejected behavior, avoiding the degenerate all-zero reward that can arise from an unranked expert demonstration.The example illustrates how a reward matching an expert trace can still reveal little about the underlying reward structure, risking poor generalization when dynamics change.Source: §A.1 · pp. 12–13

A.2 Ranking Theory

  • A total ranking over policies yields reward ambiguity no greater than using only the optimal policy.With linear feature rewards, each ranking adds half-space constraints on feasible reward weights.Source: §A.2 · p. 14

A.3 Uncertainty Reduction for Random Halfspaces

The analysis models pairwise trajectory preferences as half-space constraints on reward hypotheses and argues that random constraints reduce ambiguity exponentially. The section also specifies noise schedules used in MuJoCo and Atari degradation experiments.

A.3 Uncertainty Reduction for Random Halfspaces

  • The analysis’s main result is that random half-space constraints reduce reward ambiguity exponentially, so a logarithmic number can eliminate a large portion of possible reward hypotheses.Each ranked trajectory pair defines a half-space constraint on the true reward feature weights.Source: §A.3 · pp. 14, 17
  • The analysis assumes linear feature rewards with bounded weights and simplifies its derivation using a finite set of reward hypotheses.The random-constraint argument tracks unique hypotheses eliminated as constraints are sampled.Source: §A.3 · pp. 14–15

B Noise Degradation

  • Noise-degradation experiments use 20 evenly spaced noise levels in [0.0, 1.0) with five trajectories per level for MuJoCo, versus five specified noise levels and 20 trajectories per level for Atari.The Atari noise schedule is (0.01, 0.25, 0.5, 0.75, 1.0).Source: B Noise Degradation · p. 17

B.1 Noise Injection Theory

The analysis studies how random-action noise changes the performance of optimal and behaviorally cloned policies. Under simplifying assumptions, increasing noise moves the expected number of suboptimal actions toward the trajectory horizon; compounding errors widen the performance gap in sequential tasks.

B.1 Noise Injection Theory

  • For an optimal policy, the expected number of suboptimal actions is Tε when the action set is large, and the empirical count concentrates around that mean for long trajectories.The derivation assumes one optimal action per state and independent visited states, temporarily ignoring compounding errors.Source: §B.1 · p. 18
  • For a cloned policy with optimal-action probability β, increasing noise moves the empirical suboptimal-action count from (1 − β)T toward T with high probability, for sufficiently large action sets and horizons.The analysis also notes that ε = 1 yields random actions regardless of the cloned policy's optimality.Source: §B.1 · p. 19
  • In sequential tasks, compounding errors make the cloned policy's performance gap from the expert grow as noise increases from 0 to 1.The preceding count analysis abstracts away these accumulated errors.Source: §B.1 · p. 19

C Risk Analysis

The risk analysis reports that D-REX improves worst-case performance over the demonstrator on most Atari games, while a live-long reward alone does not explain its results. The experiments use suboptimal demonstrations, behavioral cloning, and noise-generated synthetic rankings.

C Risk Analysis

  • D-REX achieves safer worst-case policies than the demonstrator on 6 of 7 games; except Pong, it also exceeds the demonstrator, BC, and GAIL in worst-case utility.The comparison to the demonstrator is described as intent extrapolation; results correspond to Table 1's average-performance results.Source: C Risk Analysis · p. 20

D Live-Long Baseline

  • A +1 reward per timestep fails to learn Enduro and Seaquest, and surpasses D-REX only on Pong, indicating that D-REX is not simply rewarding longer episodes.The authors connect D-REX's learned reward to trajectories following demonstrator intent and to observation details correlated with ground-truth reward.Source: D Live-Long Baseline · p. 20

E.1 Demonstrations

  • Demonstrations come from partially trained PPO checkpoints selected to perform significantly above random play but significantly below converged PPO.Checkpoints were recorded every 5 optimization steps for MuJoCo and every 50 for Atari.Source: §E.1 · pp. 20–21

E.2 Behavioral cloning

  • Behavioral cloning uses 1,000-step MuJoCo trajectories with an L2-trained four-layer MLP, while Atari uses an 80/20 train-validation split and a Nature DQN architecture with early stopping.Atari training stops after validation loss fails to improve for six consecutive evaluations.Source: §E.2 · p. 21

E.3 Synthetic rankings

  • Synthetic rankings use 20 MuJoCo noise levels with five trajectories each and five Atari noise levels with 20 trajectories each; Atari also includes least-preferred no-op demonstrations to encourage action and progress.No-op demonstrations address the tendency of learned rewards to favor staying alive or sitting at the start screen, though the authors note that no-op may be optimal in extremely risky domains.Source: §E.3 · p. 21

E.4 Reward function training

The reward-training pipeline learns a reward function from ranked trajectory snippets, then optimizes policies with PPO. The appendix also describes the GAIL baseline and visualizes reward extrapolation and learned attention on Atari observations.

E.4 Reward function training

  • Reward learning compares ranked pairs of trajectory snippets; MuJoCo uses three reward networks, while Atari uses 40,000 augmented pairs with a progress constraint and held-out validation for early stopping.MuJoCo discards synthetic pairs whose noise levels differ by less than 0.3; Atari crops snippets to 50–200 frames and keeps every fourth observation.Source: §E.4 · p. 22

E.5 Policy optimization

  • PPO optimizes policies on the learned reward, using an ensemble of three normalized reward networks for MuJoCo and sigmoid-normalized predictions for Atari.The Atari policy is trained for 50 million frames; MuJoCo training runs for 1 million steps.Source: §E.5 · p. 22

F GAIL

  • The Atari GAIL baseline uses a Nature DQN generator and a discriminator that classifies state-action inputs as demonstrations or generated samples, with one generator update per discriminator update.The discriminator receives four-frame state stacks with the action encoded and concatenated to the observation.Source: F GAIL · p. 23

G Reward Extrapolation and Attention Heatmaps

  • The heatmaps are computed by masking image patches and measuring predicted-reward changes; examples show attention on game-relevant objects, including Seaquest enemies and submarine and Space Invaders aliens and barriers.The Seaquest minimum-reward observation shows the submarine just before an enemy shark destroys it.Source: G Reward Extrapolation and Attention… · p. 23, Figure 11 · p. 30, Figure 12 · p. 31
  • Figure 5 distinguishes noise-generated demonstrations, actual demonstrations, and unseen trajectories, comparing their ground-truth returns with D-REX-predicted returns on a normalized scale.Blue dots denote synthetic demonstrations, red actual demonstrations, and green additional trajectories not seen during training.Source: Figure 5 · p. 24
Loading 1907.03976v3…