A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning

Stephane Ross, Geoffrey Gordon, and J. Andrew (Drew) Bagnell
Proceedings of the 14th International Conference on Artifical Intelligence and Statistics (AISTATS), April, 2011.


Download
  • Adobe portable document format (pdf) (448KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Keywords
Imitation Learning, Structured Prediction, Reduction, Online Learning

Notes
Sponsor: ONR MURI grant N00014-09-1-1052 Reasoning in Reduced Information Spaces, National Sciences and Engineering Research Council of Canada (NSERC)
Associated Center(s) / Consortia: National Robotics Engineering Center
Number of pages: 9

Text Reference
Stephane Ross, Geoffrey Gordon, and J. Andrew (Drew) Bagnell, "A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning," Proceedings of the 14th International Conference on Artifical Intelligence and Statistics (AISTATS), April, 2011.

BibTeX Reference
@inproceedings{Ross_2011_6814,
   author = "Stephane Ross and Geoffrey Gordon and J. Andrew (Drew) Bagnell",
   title = "A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning",
   booktitle = "Proceedings of the 14th International Conference on Artifical Intelligence and Statistics (AISTATS)",
   month = "April",
   year = "2011",
}