  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.
