Reduction of Imitation Learning to No-Regret Online Learning
Sep 12, 2026
This episode examines "A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning" (Ross, Gordon, and Bagnell, AISTATS 2011), unpacking why naively training a policy via supervised learning on expert demonstrations produces errors that compound quadratically with task horizon rather than linearly. It traces this compounding-error problem through concrete analogues — a self-driving policy drifting off the expert's trajectory into unseen states, and the exposure bias later rediscovered in sequence-to-sequence language models trained with teacher forcing — showing the same closed-loop failure mode recurring across robotics, structured prediction (like part-of-speech tagging), and NLP. It also revisits the authors' own earlier fix, SMILe (2010), explaining why its stochastic mixture-of-policies approach required an impractically large number of iterations to approach linear regret. Listeners interested in the theoretical foundations connecting imitation learning, sequence generation, and online learning reductions will find this a clear walkthrough of a foundational result that anticipated problems later rediscovered independently in deep learning.
Interactive Visualization: Reduction of Imitation Learning to No-Regret Online Learning
Sources:
1. A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning — Stephane Ross, Geoffrey J. Gordon, J. Andrew Bagnell, 2010
http://arxiv.org/abs/1011.0686
2. Efficient Reductions for Imitation Learning — Stéphane Ross, J. Andrew Bagnell, 2010
https://scholar.google.com/scholar?q=Efficient+Reductions+for+Imitation+Learning
3. Search-based Structured Prediction (SEARN) — Hal Daumé III, John Langford, Daniel Marcu, 2009
https://scholar.google.com/scholar?q=Search-based+Structured+Prediction+%28SEARN%29
4. Apprenticeship Learning via Inverse Reinforcement Learning — Pieter Abbeel, Andrew Y. Ng, 2004
https://scholar.google.com/scholar?q=Apprenticeship+Learning+via+Inverse+Reinforcement+Learning
5. Generative Adversarial Imitation Learning — Jonathan Ho, Stefano Ermon, 2016
https://scholar.google.com/scholar?q=Generative+Adversarial+Imitation+Learning
6. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data — John Lafferty, Andrew McCallum, Fernando Pereira, 2001
https://scholar.google.com/scholar?q=Conditional+Random+Fields%3A+Probabilistic+Models+for+Segmenting+and+Labeling+Sequence+Data
7. Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks — Samy Bengio, Oriol Vinyals, Navdeep Jaitly, Noam Shazeer, 2015
https://scholar.google.com/scholar?q=Scheduled+Sampling+for+Sequence+Prediction+with+Recurrent+Neural+Networks
8. Approximately Optimal Approximate Reinforcement Learning — Sham Kakade, John Langford, 2002
https://scholar.google.com/scholar?q=Approximately+Optimal+Approximate+Reinforcement+Learning
9. Error-Correcting Tournaments / Error Limiting Reductions — Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford, Bianca Zadrozny (various papers in this line, ~2005), 2005
https://scholar.google.com/scholar?q=Error-Correcting+Tournaments+%2F+Error+Limiting+Reductions
10. Relating Reinforcement Learning Performance to Classification Performance — John Langford, Bianca Zadrozny, 2005
https://scholar.google.com/scholar?q=Relating+Reinforcement+Learning+Performance+to+Classification+Performance
11. Efficient Reductions for Imitation Learning (SMILe, Forward Training) — Stéphane Ross, J. Andrew Bagnell, 2010
https://scholar.google.com/scholar?q=Efficient+Reductions+for+Imitation+Learning+%28SMILe%2C+Forward+Training%29
12. Approximately Optimal Approximate Reinforcement Learning (CPI) — Sham Kakade, John Langford, 2002
https://scholar.google.com/scholar?q=Approximately+Optimal+Approximate+Reinforcement+Learning+%28CPI%29
13. Error Limiting Reductions Between Classification Tasks — Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford, Bianca Zadrozny, 2005
https://scholar.google.com/scholar?q=Error+Limiting+Reductions+Between+Classification+Tasks
14. Max-Margin Markov Networks — Ben Taskar, Carlos Guestrin, Daphne Koller, 2003
https://scholar.google.com/scholar?q=Max-Margin+Markov+Networks
15. On the Generalization Ability of Online Strongly Convex Programming Algorithms — Sham Kakade, Ambuj Tewari, 2009
https://scholar.google.com/scholar?q=On+the+Generalization+Ability+of+Online+Strongly+Convex+Programming+Algorithms
Interactive Visualization: Reduction of Imitation Learning to No-Regret Online Learning
1. A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning — Stephane Ross, Geoffrey J. Gordon, J. Andrew Bagnell, 2010
http://arxiv.org/abs/1011.0686
2. Efficient Reductions for Imitation Learning — Stéphane Ross, J. Andrew Bagnell, 2010
https://scholar.google.com/scholar?q=Efficient+Reductions+for+Imitation+Learning
3. Search-based Structured Prediction (SEARN) — Hal Daumé III, John Langford, Daniel Marcu, 2009
https://scholar.google.com/scholar?q=Search-based+Structured+Prediction+%28SEARN%29
4. Apprenticeship Learning via Inverse Reinforcement Learning — Pieter Abbeel, Andrew Y. Ng, 2004
https://scholar.google.com/scholar?q=Apprenticeship+Learning+via+Inverse+Reinforcement+Learning
5. Generative Adversarial Imitation Learning — Jonathan Ho, Stefano Ermon, 2016
https://scholar.google.com/scholar?q=Generative+Adversarial+Imitation+Learning
6. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data — John Lafferty, Andrew McCallum, Fernando Pereira, 2001
https://scholar.google.com/scholar?q=Conditional+Random+Fields%3A+Probabilistic+Models+for+Segmenting+and+Labeling+Sequence+Data
7. Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks — Samy Bengio, Oriol Vinyals, Navdeep Jaitly, Noam Shazeer, 2015
https://scholar.google.com/scholar?q=Scheduled+Sampling+for+Sequence+Prediction+with+Recurrent+Neural+Networks
8. Approximately Optimal Approximate Reinforcement Learning — Sham Kakade, John Langford, 2002
https://scholar.google.com/scholar?q=Approximately+Optimal+Approximate+Reinforcement+Learning
9. Error-Correcting Tournaments / Error Limiting Reductions — Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford, Bianca Zadrozny (various papers in this line, ~2005), 2005
https://scholar.google.com/scholar?q=Error-Correcting+Tournaments+%2F+Error+Limiting+Reductions
10. Relating Reinforcement Learning Performance to Classification Performance — John Langford, Bianca Zadrozny, 2005
https://scholar.google.com/scholar?q=Relating+Reinforcement+Learning+Performance+to+Classification+Performance
11. Efficient Reductions for Imitation Learning (SMILe, Forward Training) — Stéphane Ross, J. Andrew Bagnell, 2010
https://scholar.google.com/scholar?q=Efficient+Reductions+for+Imitation+Learning+%28SMILe%2C+Forward+Training%29
12. Approximately Optimal Approximate Reinforcement Learning (CPI) — Sham Kakade, John Langford, 2002
https://scholar.google.com/scholar?q=Approximately+Optimal+Approximate+Reinforcement+Learning+%28CPI%29
13. Error Limiting Reductions Between Classification Tasks — Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford, Bianca Zadrozny, 2005
https://scholar.google.com/scholar?q=Error+Limiting+Reductions+Between+Classification+Tasks
14. Max-Margin Markov Networks — Ben Taskar, Carlos Guestrin, Daphne Koller, 2003
https://scholar.google.com/scholar?q=Max-Margin+Markov+Networks
15. On the Generalization Ability of Online Strongly Convex Programming Algorithms — Sham Kakade, Ambuj Tewari, 2009
https://scholar.google.com/scholar?q=On+the+Generalization+Ability+of+Online+Strongly+Convex+Programming+Algorithms
Interactive Visualization: Reduction of Imitation Learning to No-Regret Online Learning