Learning Beam Search Policies via Imitation Learning
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.
This paper develops a unifying formalism (a meta-algorithm) for imitation learning in the context of beam search; that is, learning in a beam-search-aware manner with access to an oracle that will tell you the minimum completion cost for any partial state. This formalism exposes a subtle but important corner of the space that has not yet been explored: algorithms that are beam aware, but which do not reset or stop after the gold-standard falls out of the beam, but instead continue along the best possible remaining path. Using this formalism, they are able to develop regret guarantees for this new case, alongside novel guarantees for existing cases where the algorithm stops or resets. They show the case where the algorithm continues to have better regret guarantees.  This paper is a masterwork of notation. No symbol is wasted, no symbol is under-explained. Everything is crisp and precise. The paper is demanding, but with some patience, its clarity is remarkable. Its unifying framework builds an effective bridge between the worlds of beam-search aware structured prediction and imitation learning, and for this reviewer, that bridge is very valuable. The only thing I would have liked to see, which was missing from both the main paper and the appendices, is the inclusion of a table matching existing papers to specific loss-strategy combinations in the meta-algorithm.   As implied in my summary above, the unexplored corner of imitation learning that they’ve uncovered with this formalism (that is, beam + continue with oracle costs), is novel and interesting. Even ignoring the regret guarantees, from an intuitive standpoint, it is likely to be useful for practitioners down the road, once we have some experiments supporting this choice (this paper has no experiments, which I assume is okay for NIPS).   Some nit-picky concerns:  The two points laid out in the first paragraph: (1) learning ignores the beam and (2) learning uses only oracle trajectories, are a good way to spell out the standard maximum likelihood training process. However, to say that your method is the only method the address both issues simultaneously is too strong. Any beam-aware method naturally addresses (1) and (2), as by definition it does not use *only* oracle trajectories. You need a better way of phrasing number (2) to emphasize that you are the proposing the first method to both use a beam and oracle costs to avoid stopping or resetting when the gold-standard falls out of the beam - which is a fair amount more subtle than being the first to use both a beam and non-oracle trajectories. This becomes clear two paragraphs later, but it is misleading for the first paragraph of the paper.  The main text mentions Thm 4 without mentioning that it can only be found in the appendix.  --  Dropping in to thank the authors for their response, and for including the table I requested.