Learning Beam Search Policies via Imitation Learning

Renato Negrinho, Matthew R. Gormley, Geoffrey J. Gordon

This paper provides a rigorous theoretical framework for a problem every NLP researcher knows well: the "train-test mismatch" in structured prediction. By treating beam search as an integral part of a model's policy rather than just a test-time heuristic, the authors apply imitation learning to develop a unifying meta-algorithm. This approach not only captures existing beam-aware methods but also provides the first no-regret theoretical guarantees for learning beam search policies.

The Problem: Train-Test Mismatch

In structured prediction tasks like machine translation or parsing, models are typically trained using Maximum Likelihood Estimation (MLE). However, at test time, we use beam search to find the most likely sequence. This discrepancy creates two major issues:

  1. The Beam Gap: The model never learns how to use the beam during training. It doesn't know that its goal is to keep the "correct" answer anywhere within the top $k$ candidates, rather than strictly at the very top at all times.
  2. Exposure Bias: During standard training, the model only sees ground-truth prefixes ("oracle trajectories"). At test time, if it makes one small mistake, it enters a state it has never seen before. Lacking the knowledge of how to recover, it often spirals into further errors.

While "beam-aware" heuristics like LaSO (Learning as Search Optimization) and "early update" exist, they historically lack strong theoretical foundations and often stop or reset training as soon as a mistake is made, limiting the model's exposure to its own errors.

A New Framework: Beam Search as an MDP

The authors frame beam search as a Markov Decision Process (MDP) where each "state" is actually an entire beam (a set of $k$ hypotheses). By defining the state as the beam itself, they can mathematically define what it means for a "policy" to be good at beam search.

The Meta-Algorithm

They propose a meta-algorithm that iterates through three core steps:

  1. Roll-in: Use the current model (or a mixture of the model and an oracle) to generate a trajectory of beams.
  2. Oracle Feedback: For every neighbor of every element in the beam, calculate the "oracle completion cost" (how good the final result would be if we started from here).
  3. Update: Update the model's scoring function to ensure that the "best" neighbors (those leading to low-cost completions) are ranked high enough to stay in the beam.
Algorithm 2: The proposed Meta-algorithm for learning beam search policies.

Key Innovations

  • The "Continue" Strategy: Unlike prior methods that stop or reset when the correct answer falls out of the beam, the authors suggest continuing the trajectory. This forces the model to learn how to produce the best possible output even after a mistake.
  • Surrogate Losses: They define several loss functions, including a novel convex upper bound on the expected beam transition cost. This makes the combinatorial problem of "staying in the beam" differentiable and optimizable.

Unification of Prior Work

A major highlight of the paper is its theoretical unification. The authors demonstrate that 20 years of disparate "beam-aware" heuristics—such as LaSO, BSO, and Early Update—are actually just specific instantiations of their meta-algorithm with different choices for data collection and loss functions.

Table 1: How existing beam-aware algorithms map to specific choices within the proposed meta-algorithm framework.

Theoretical Guarantees

The "holy grail" of this paper is its theoretical backing. The authors prove that if you use their "Continue" strategy with a no-regret online learner, the model's performance will converge to the best possible beam search policy in hindsight. These are the first formal guarantees for beam-aware learning, covering both explicit expectations and finite sample analysis.

Limitations and Future Work

While theoretically profound, the framework has practical limitations:

  • Computational Cost: Running beam search during training (roll-in) is significantly more expensive than standard MLE training.
  • Oracle Dependency: The framework requires an oracle that can evaluate partial, non-optimal states. For some complex reward functions (like BLEU score in translation), creating a perfect oracle for a partial sentence is non-trivial.
  • Empirical Validation: As a theory-heavy paper, it focuses on mathematical foundations and leaves large-scale empirical testing (e.g., benchmarking against state-of-the-art Transformers on WMT) to future work.

Summary updated

Abstract

Beam search is widely used for approximate decoding in structured prediction problems. Models often use a beam at test time but ignore its existence at train time, and therefore do not explicitly learn how to use the beam. We develop an unifying meta-algorithm for learning beam search policies using imitation learning. In our setting, the beam is part of the model and not just an artifact of approximate decoding. Our meta-algorithm captures existing learning algorithms and suggests new ones. It also lets us show novel no-regret guarantees for learning beam search policies.
BibTeX
@inproceedings{negrinho2018learning,
  author = {Renato Negrinho and Matthew R. Gormley and Geoffrey J. Gordon},
  title = {{Learning Beam Search Policies via Imitation Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HkbjIwWdWH},
}
Figure