# Learning to Search Better Than Your Teacher

arXiv: https://arxiv.org/abs/1502.02206 · HTML: https://mlsanity.com/paper/1502.02206/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2015.

## Built on by (most cited first, 30 of 50)

- [An Algorithmic Perspective on Imitation Learning](https://mlsanity.com/paper/1811.06711/) (2018)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [Is Reinforcement Learning (Not) for Natural Language Processing: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization](https://mlsanity.com/paper/2210.01241/) (2022)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Help, Anna! Visual Navigation with Natural Multimodal Assistance via Retrospective Curiosity-Encouraging Imitation Learning](https://mlsanity.com/paper/1909.01871/) (2019)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [Vision-based Navigation with Language-based Assistance via Imitation Learning with Indirect Intervention](https://mlsanity.com/paper/1812.04155/) (2018)
- [Autoregressive Knowledge Distillation through Imitation Learning](https://mlsanity.com/paper/2009.07253/) (2020)
- [Reinforcement Learning for Bandit Neural Machine Translation with Simulated Human Feedback](https://mlsanity.com/paper/1707.07402/) (2017)
- [Policy Decorator: Model-Agnostic Online Refinement for Large Policy Model](https://mlsanity.com/paper/2412.13630/) (2024)
- [Reincarnating Reinforcement Learning: Reusing Prior Computation to Accelerate Progress](https://mlsanity.com/paper/2206.01626/) (2022)
- [Embodied Multi-Modal Agent trained by an LLM from a Parallel TextWorld](https://mlsanity.com/paper/2311.16714/) (2023)
- [Imitation Learning: Progress, Taxonomies and Challenges](https://mlsanity.com/paper/2106.12177/) (2021)
- [Learning to Generate Better Than Your LLM](https://mlsanity.com/paper/2306.11816/) (2023)
- [Autoregressive Structured Prediction with Language Models](https://mlsanity.com/paper/2210.14698/) (2022)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [Truncated Horizon Policy Search: Combining Reinforcement Learning & Imitation Learning](https://mlsanity.com/paper/1805.11240/) (2018)
- [Inverse Reinforcement Learning without Reinforcement Learning](https://mlsanity.com/paper/2303.14623/) (2023)
- [CCIL: Continuity-based Data Augmentation for Corrective Imitation Learning](https://mlsanity.com/paper/2310.12972/) (2023)
- [An Imitation Learning Curriculum for Text Editing with Non-Autoregressive Models](https://mlsanity.com/paper/2203.09486/) (2022)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [A Smooth Sea Never Made a Skilled SAILOR: Robust Imitation via Learning to Search](https://mlsanity.com/paper/2506.05294/) (2025)
- [OIL: Observational Imitation Learning](https://mlsanity.com/paper/1803.01129/) (2018)
- [An Empirical Comparison on Imitation Learning and Reinforcement Learning for Paraphrase Generation](https://mlsanity.com/paper/1908.10835/) (2019)
- [Iterative Document-level Information Extraction via Imitation Learning](https://mlsanity.com/paper/2210.06600/) (2022)
- [Teacher Forcing Recovers Reward Functions for Text Generation](https://mlsanity.com/paper/2210.08708/) (2022)
- [Learning Beam Search Policies via Imitation Learning](https://mlsanity.com/paper/1811.00512/) (2018)
- [Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends](https://mlsanity.com/paper/2111.06257/) (2021)
- [Learning Graph Search Heuristics](https://mlsanity.com/paper/2212.03978/) (2022)

## Abstract (arXiv)

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.