A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning
By Stéphane Ross, Geoffrey J. Gordon, J. Bagnell. 2010
4,272 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Optimization & Training
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Yoshua Bengio
- Mohit Bansal
- Pieter Abbeel
- Jianfeng Gao
- Ruslan Salakhutdinov
- Percy Liang
- Quoc V. Le
In Management Science and Operations Research
- Sergey Levine
- Pieter Abbeel
- Ofir Nachum
- Chelsea Finn
- Shimon Whiteson
- Nan Jiang
- R´emi Munos
- Lihong Li
In Reinforcement Learning
- Sergey Levine
- Pieter Abbeel
- Chelsea Finn
- Ofir Nachum
- Shimon Whiteson
- Shixiang Shane Gu
- Yuxi Li
- Abhishek Gupta
In Optimization & Training
- Yoshua Bengio
- Sergey Levine
- Pieter Abbeel
- Quoc V. Le
- Chelsea Finn
- Ruslan Salakhutdinov
- Razvan Pascanu
- Kyunghyun Cho
Citations in the corpus
- Sequence-Level Knowledge Distillation (2016, background): “, 2009), DAgger (Ross et al., 2011), and minimum risk training (Och, 2003; Shen et al.”
- Learning to summarize from human feedback (2020, background): “are incentivized to place probability mass on all human demonstrations, including those that are low-quality; and distributional shift during sampling can degrade performance [56, 52].”
- Coarse-to-Fine Question Answering for Long Documents (2016, methodology): “To reduce variance, we use curriculum learning, start training with distant supervision and gently transition to reinforcement learning, similar to DA GGER (Ross et al., 2011).”
- Learning with Latent Language (2017, positive): “4 The learner is trained from task-specific expert policies using DAgger (Ross et al., 2011) during the language-learning phase, and adapts to individual environments using “vanilla” policy gradient (Williams, 1992) during the concept learning phase.”
- End-to-End Training of Deep Visuomotor Policies (2015, background): “To avoid this problem, the training data must come from the policy’s own state distribution [35].”
- One-Shot Imitation Learning (2017, methodology): “In this paper, we focus on imitation learning algorithms such as behavioral cloning and DAGGER (Ross et al., 2011), which only require demon- strations rather than reward functions to be specified.1 This has the potential to be more scalable, since it is often easier to demonstrate a task than…”
- Thinking Fast and Slow with Deep Learning and Tree Search (2017, methodology): “Such dataset aggregation is similar to the DAgger algorithm [5].”
- An Actor-Critic Algorithm for Sequence Prediction (2016, methodology): “Methods of this type include the S EARN (Daum ´ e Iii et al., 2009) and DA GGER (Ross et al., 2010) algorithms.”
- Is Reinforcement Learning (Not) for Natural Language Processing?: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization (2022, methodology): “Imitation learning for NLP. Algorithms such as Schedule Sampling (SS) (Bengio et al., 2015), Parallel SS (Duckworth et al., 2019), SS for Transformers (Mihaylova & Martins, 2019), Diffential SS (Goyal et al., 2017), LOLS (Lampouras & Vlachos, 2016; Chang et al., 2015), TextGAIL (Wu et al., 2021b), a”
- Neural Text Generation with Unlikelihood Training (2019, background): “The resulting distribution mismatch between training sequences and generated sequences is a known issue with maximum-likelihood training, motivating objectives that operate on model-generated sequences (Daum´e et al., 2009; Ross et al., 2011; Ranzato et al., 2015; Yu et al., 2016).”
- LILA: Language-Informed Latent Actions (2021, neutral): “…appropriate SDC, learning an effective policy (note this is just discrete node navigation – not continuous manipulation) required running DAgger [54] for 25 iterations on top of their existing data, collecting an order of magnitude more demonstration data (or demonstration edits/corrections as…”
- Language Models are Few-Shot Butlers (2021, methodology): “We compare our models with the ones developed by Shridhar et al. (2021): • BUTLER: trained with Dagger (Ross et al., 2011) for 50k episodes and handling failed actions with beam search.”
- Imitating Interactive Intelligence (2020, background): “Theoretical analysis of behavioural cloning (Ross et al., 2011) suggests that errors of the imitator agent in predicting the demonstrator’s actions lead to a performance gap that compounds.3 The root problem is that each mistake of the imitator changes the distribution of future states so that…”
- ALFWorld: Aligning Text and Embodied Environments for Interactive Learning (2020, methodology): “After concluding that current reinforcement learning approaches were not successful on our set of training tasks, we turned to DAgger (Ross et al., 2011) assisted by a rule-based expert (detailed in Appendix E).”
- ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks (2019, neutral): “We note that a DAgger-style [43] student-forcing paradigm in ALFRED is non-trivial, even disregarding language alignment.”
- Shaking the foundations: delusions in sequence models for interaction and control (2021, neutral): “The requirement of soliciting an expert’s action online from a trajectory generated by an agent for counterfactual teaching is similar to the Dagger algorithm [20] where”
- Vision-and-Language Navigation: Interpreting Visually-Grounded Navigation Instructions in Real Environments (2017, methodology): “However, this limits exploration to only states that are in ground-truth shortest-path trajectory, resulting in a changing input distribution between training and testing [45, 32].”
- Value Iteration Networks (2016, methodology): “We demonstrate that VINs can be effectively used within standard RL and IL algorithms in various problems, among which require visual perception, continuous control, and also natural language based decision making in the WebNav challenge [20].”
- Offline Reinforcement Learning as One Big Sequence Modeling Problem (2021, methodology): “…et al., 2019; Kumar et al., 2019a; Ghasemipour et al., 2021); imitation learning, where it is used to fit an expert’s actions to obtain a policy (Ross & Bagnell, 2010; Ross et al., 2011); and other areas such as hierarchical RL (Peng et al., 2017; Co-Reyes et al., 2018; Jiang et al., 2019).”