A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning
TL;DR DAgger trains an imitation policy by running the current policy, having the expert label the states it visits, and retraining on all data collected so far. In Super Tux Kart its steering policy never falls off the track after 15 iterations, while SMILe still falls about twice per lap.
What they do
Supervised imitation trains only on states the expert visits; once the learned policy errs it reaches states the expert never showed, and mistakes compound to as much as T²ε extra cost over T steps for per-step error ε. Earlier fixes (forward training, SMILe, SEARN) learn non-stationary or stochastic mixture policies. DAgger (Dataset Aggregation) learns one stationary deterministic policy and is analyzed as no-regret online learning.
How it works
- Iteration 1 trains on expert trajectories. Each later iteration runs the current policy (optionally mixed with the expert with probability β_i), has the expert label the visited states, and retrains on the aggregate of all data so far.
- Retraining on everything seen so far is Follow-The-Leader, a no-regret online learner. The guarantees hold for any no-regret algorithm used this way.
- With a strongly convex loss and Õ(T) iterations, some policy in the sequence reaches loss ε_N + O(1/T) under its own state distribution, so total cost grows linearly in T and ε instead of quadratically.
- The simplest version uses the expert only in the first iteration and has no parameters beyond the supervised learner.
Results
- Super Tux Kart (linear steering on image features, human expert): DAgger almost never falls off the track after 5 iterations and never after 15. After 20 iterations SMILe still falls about twice per lap; supervised learning does not improve with more data.
- Super Mario Bros. (linear SVMs, planner expert, stages about 4200-4300 long): DAgger beats SMILe, supervised learning and SEARN for every α tried, reaching an average distance of 3030 with β_i = 0.5^(i-1) and 2980 parameter-free.
- Handwriting recognition (greedy left-to-right SVM): character accuracy rises from 82% without structure and 83.6% supervised to 85.5% with DAgger; SEARN with α = 0.8 or 1 performs similarly.
Limitations
The expert must label every state the learner visits during training (a human for Super Tux Kart, a full-state planner for Mario). The guarantees need a no-regret learner or strongly convex loss, which the authors call stronger than the classification-only assumptions of earlier reductions. Experiments use linear learners on two games and an OCR benchmark, not a physical robot.
Figures
Abstract
Sequential prediction problems such as imitation learning, where future observations depend on previous predictions (actions), violate the common i.i.d. assumptions made in statistical learning. This leads to poor performance in theory and often in practice. Some recent approaches provide stronger guarantees in this setting, but remain somewhat unsatisfactory as they train either non-stationary or stochastic policies and require a large number of iterations. In this paper, we propose a new iterative algorithm, which trains a stationary deterministic policy, that can be seen as a no regret algorithm in an online learning setting. We show that any such no regret algorithm, combined with additional reduction assumptions, must find a policy with good performance under the distribution of observations it induces in such sequential settings. We demonstrate that this new approach outperforms previous approaches on two challenging imitation learning problems and a benchmark sequence labeling problem.
Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.