Why training a policy via plain supervised learning on expert demonstrations produces errors that compound quadratically with task horizon — and how Dataset Aggregation (DAgger) reduces the problem to ordinary no-regret online learning to recover linear error growth.
Toggle between the naive open-loop training setup and DAgger's closed aggregation loop. Same building blocks, different data flow.
Supervised learning assumes train and test states come from the same fixed distribution. In imitation learning, the policy's own predictions choose which states it sees next — so a slightly-off policy visits states the expert never demonstrated, with no training signal for what to do there.
Self-driving: drift off the expert's line → unseen state → worse move → more drift.
Sequence generation: teacher forcing looks great, free-running (own tokens fed back) drifts into degenerate loops — exposure bias, rediscovered ~4 years later.
Structured prediction: tag word 5 using your own tags 1–4, one early mistake reshapes everything downstream.
Theorem 2.1: a per-step classifier error ε under the expert's distribution can incur total task error that scales as T²·ε over horizon T — versus T·ε for ordinary supervised learning. Hover the chart.
Expert trajectory (green) stays on-distribution. One misstep at step 3 pushes the learner into a state the expert never visited (orange), and every subsequent choice compounds off that unfamiliar state (red).
Each iteration i: roll out policy πi-1 (mixed with the expert per βi), label the visited states with the expert's action, add to the growing dataset, retrain (Follow-The-Leader) on everything collected so far.
βi is the fraction of actions from the expert during iteration i's rollout. The only formal requirement: the average βi → 0 as N grows.
DAgger's guarantee rides entirely on Follow-The-Leader being no-regret under strongly convex losses (Kakade & Tewari, 2009), plus the assumption that some policy in the class achieves low surrogate loss under any induced distribution.
Nearly perfect by iteration 5, effectively zero falls per lap by iteration 15 — versus SMILe's stochastic-mixture plateau around 2 falls/lap.
Full interactive companion visualization: Reduction of Imitation Learning to No-Regret Online Learning