Learning to Search Better than Your Teacher

By Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé Iii, J. Langford. 2015

238 citations recorded by the source corpus.

Methods for learning to search for structured prediction typically imitate a reference policy, with existing theoretical guarantees demonstrating low regret compared to that reference. This is unsatisfactory in many applications where the reference policy is suboptimal and the goal of learning is to improve upon it. Can learning to search work even when the reference is poor? We provide a new learning to search algorithm, LOLS, which does well relative to the reference policy, but additionally guarantees low regret compared to deviations from the learned policy: a local-optimality guarantee. Consequently, LOLS can improve upon the reference policy, unlike previous algorithms. This enables us to develop structured contextual bandits, a partial information structured prediction setting with many potential applications.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

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

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Thinking Fast and Slow with Deep Learning and Tree Search (2017, methodology): “Kai-Wei, et al. [15] use an iterative scheme with some similarity to ExIt.”
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”
Value Iteration Networks (2016, background): “The success of reactive policies in sequential problems is due to the learning algorithm , which essentially trains a reactive policy to select actions that have good long-term consequences in its training domain.”
Evaluating the State-of-the-Art of End-to-End Natural Language Generation: The E2E NLG Challenge (2019, methodology): “are trained using the Locally Optimal Learning to Search (LOLS) imitation learning framework (Chang et al. 2015), optimising for BLEU, ROUGE-L, and slot error (cf.”
Learning Algorithms for Active Learning (2017, methodology): “Related approaches have been explored in previous work on imitation learning and learning to search (Ross & Bagnell, 2014; Chang et al., 2015).”
An Algorithmic Perspective on Imitation Learning (2018, methodology): “Modern, high performance, implementations of such search based structured prediction use online learning methods of DAGGER [Ross et al., 2011, 2013], AggreVaTe [Ross and Bagnell, 2014, Sun et al., 2017], or LOLS [Chang et al., 2015, Daumé III and Langford, 2015].”
Reinforcement Learning for Bandit Neural Machine Translation with Simulated Human Feedback (2017, background): “, translation) and then the world reveals a score that measures how good or bad that output is, but provides neither a “correct” output nor feedback on any other possible output (Chang et al., 2015; Sokolov et al., 2015).”
Linguistically-Informed Self-Attention for Semantic Role Labeling (2018, background): “The question of training on gold versus predicted labels is closely related to learning to search (Daum´e III et al., 2009; Ross et al., 2011; Chang et al., 2015) and scheduled sampling (Bengio et al., 2015), with applications in NLP to sequence labeling and transition-based parsing (Choi and…”
Optimal Completion Distillation for Sequence Learning (2018, background): “The learning to search (L2S) literature (Daumé III and Marcu, 2005; Chang et al., 2015; Goodman et al., 2016; Leblond et al., 2018) also attempts at estimating the cost of each action by examining multiple roll-outs of a generated prefix.”
Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction (2017, methodology): “Since the sizes of stack, buffer and arcs change during parsing, a common approach is to featurize the state s by taking the features of the latest three symbols from stack, buffer and arcs (e.g., (Chang et al., 2015a)).”
Truncated Horizon Policy Search: Combining Reinforcement Learning & Imitation Learning (2018, methodology): “6 for k > 1 and the policy that induced by the oracle, which is missing in previous work (e.g., (Chang et al., 2015)).”
Query-Efficient Imitation Learning for End-to-End Simulated Driving (2017, methodology): “, (Daumé Iii, Langford, and Marcu 2009; Ross, Gordon, and Bagnell 2010; Chang et al. 2015)), we introduce a concept of cost to a policy.”
Help, Anna! Visual Navigation with Natural Multimodal Assistance via Retrospective Curiosity-Encouraging Imitation Learning (2019, background): “In general, imitation learning (Daum´e III et al., 2009; Ross et al., 2011; Ross and Bagnell, 2014; Chang et al., 2015; Sun et al., 2017) ﬁnds a policy ˆ π that minimizes the expected imitation loss L with respect to a teacher policy π (cid:63) under the agent-induced state distribution D ˆ π : We…”
Learning to Search with MCTSnets (2018, background): “The learning-to-search framework (Chang et al., 2015) learns an evaluation function that is effective in the context of beam search.”
Query-Efficient Imitation Learning for End-to-End Autonomous Driving (2016, methodology): “However, it is certainly possible to incorporate an explicit reward with other imitation learning algorithms, such as SEARN [7], AggreVaTe [15] and LOLS [5].”
Hierarchical Imitation and Reinforcement Learning (2018, background): “The latter setting (Daumé et al., 2009; Ross et al., 2011; Ross & Bagnell, 2014; Chang et al., 2015; Sun et al., 2017) assumes an interactive expert that provides demonstrations in response to actions taken by the current policy.”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “The oracle-based approach has produced practically effective algorithms for active learning [18], contextual bandits [19], structured prediction [20, 21], and multi-class classification [22], and here, we consider oracle-based algorithms for challenging RL settings.”
Stochastic Structured Prediction under Bandit Feedback (2016, background): “Most closely related are recent applications of policy gradient methods to exponential output spaces in NLP problems [22, 3, 15].”
Imitation learning for language generation from unaligned data (2016, methodology): “There are X-count-1 X-type-1 if you don’t care if dogs are allowed. framework (Chang et al., 2015).”
Non-Monotonic Sequential Text Generation (2019, methodology): “Therefore, despite the fact that this can lead to inconsistency in the learned model (Chang et al., 2015), all experiments are with oracle roll-ins.”