Learning to Search Better Than Your Teacher

Abstract

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.

In ICML 2015

References in corpus (1)

• Reinforcement and Imitation Learning via Interactive No-Regret Learning

Cited by in corpus (32)

• Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning
• An Algorithmic Perspective on Imitation Learning
• Evaluating the State-of-the-Art of End-to-End Natural Language Generation: The E2E NLG Challenge
• Structured Prediction Theory Based on Factor Graph Complexity
• Hierarchical Imitation and Reinforcement Learning
• Provably Efficient Imitation Learning from Observation Alone
• Error Bounds of Imitating Policies and Environments
• Real-Time Web Scale Event Summarization Using Sequential Decision Making
• Learning to Search via Retrospective Imitation
• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• Learning to design without prior data: Discovering generalizable design strategies using deep learning and tree search
• Learning Dexterous Manipulation from Suboptimal Experts
• Meta-Learning for Contextual Bandit Exploration
• Imitation Learning: Progress, Taxonomies and Challenges
• A Credit Assignment Compiler for Joint Prediction
• Active Information Acquisition
• Imitation-Projected Programmatic Reinforcement Learning
• Think Too Fast Nor Too Slow: The Computational Trade-off Between Planning And Reinforcement Learning
• Optimal Completion Distillation for Sequence Learning
• Latent Programmer: Discrete Latent Codes for Program Synthesis
• Help, Anna! Visual Navigation with Natural Multimodal Assistance via Retrospective Curiosity-Encouraging Imitation Learning
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration
• Provable Representation Learning for Imitation Learning via Bi-level Optimization
• Detecting and Exorcising Statistical Demons from Language Models with Anti-Models of Negative Data
• Co-training for Policy Learning
• Bridging the Imitation Gap by Adaptive Insubordination
• Computational Morphology with Neural Network Approaches
• Learning Constraints for Structured Prediction Using Rectifier Networks
• Cost-Sensitive Training for Autoregressive Models
• Autoregressive Knowledge Distillation through Imitation Learning
• Search-Guided, Lightly-supervised Training of Structured Prediction Energy Networks
• Exploration in Action Space