Structured Prediction via Learning to Search under Bandit Feedback

Amr Sharaf, Hal Daumé Iii

Abstract

Traditional structured prediction models, such as those used for dependency parsing or part-of-speech tagging, typically rely on expensive, full ground-truth labels for training. This paper introduces Bandit Learning to Search (BLS), an algorithm designed to learn from limited "bandit" feedback. By requiring only simple binary (right/wrong) signals for individual actions in a sequence, BLS employs a doubly robust estimation strategy to mitigate the high variance typically associated with bandit learning. Our evaluation across three NLP tasks shows that BLS significantly improves out-of-domain models, achieving performance levels that approach fully supervised benchmarks.

Introduction: The Challenge of Structured Prediction

In tasks like machine translation or syntactic parsing, obtaining perfect ground-truth outputs is often prohibitively expensive. A more scalable alternative is bandit feedback, where a system receives a score for its prediction without knowing how alternative outputs would have performed. However, this setting introduces massive variance, making it difficult for models to identify which specific actions led to success or failure. This research addresses the gap between "cheap but noisy" bandit feedback and "expensive but perfect" full supervision.

Methodology: Bandit Learning to Search (BLS)

The BLS algorithm builds upon the Learning to Search (L2S) framework, which decomposes complex structured tasks into a sequence of discrete actions.

The Learning to Search (L2S) framework illustrating roll-in, roll-out, and one-step deviation.

The core innovations of BLS include:

  • Fine-grained Bandit Feedback: Instead of a single scalar for an entire sequence, the model receives binary feedback for each action. This "per-step" signal is significantly easier for humans to provide than full labels.
  • Doubly Robust (DR) Cost Estimation: To address the "road not taken" problem, BLS utilizes regressors to estimate the potential costs of unchosen actions. Combining these estimates with observed feedback stabilizes the learning process.
  • Exploration Strategies: The authors explored various mechanisms for action selection, finding that Boltzmann (softmax) exploration effectively avoids low-value regions of the search space compared to standard $\epsilon$-greedy methods.

Key Insights: Overcoming the Variance Trap

A critical finding of this work is the "Variance Trap." Standard bandit adaptations of existing algorithms, such as LOLS, often perform worse than their initial reference models because the feedback is too noisy. Without effective variance reduction, models tend to "unlearn" correct behaviors.

Variance comparison between BLS and the bandit version of LOLS over increasing sequences.

BLS avoids this trap through its Doubly Robust estimator. Furthermore, the research highlights that while pure bandit feedback is often insufficient for complex tasks, per-action binary feedback provides a "sweet spot"—offering enough signal for stable updates without the overhead of full supervision.

Experimental Evaluation

The authors evaluated BLS on three standard NLP tasks: Part-Of-Speech (POS) Tagging (simulating domain adaptation from Twitter to WSJ), Noun Phrase Chunking (CoNLL-2000), and Dependency Parsing (Penn Treebank).

Results

The results demonstrate that BLS can effectively refine "out-of-domain" models using only bandit feedback:

Task Reference (Initial) BLS (Best Variant) Full Supervision
POS Tagging (Acc) 47.24% 89.62% 96.51%
Dep. Parsing (UAS) 44.15% 57.20% 90.64%
Chunking (F-Score) 74.73% 90.91% 95.29%

Notably, in POS tagging, BLS recovered nearly 90% accuracy from a failing baseline, whereas the previous state-of-the-art bandit approach (LOLS) collapsed to near-random performance. BLS also significantly outperformed standard Reinforcement Learning techniques like Policy Gradient in tasks with large action spaces.

Limitations and Future Directions

While BLS reduces the cost of supervision, it still requires human intervention for every action in a sequence. Future work may integrate active learning to identify the most informative sequences, further reducing human effort. Additionally, the reliance on regressor accuracy for the Doubly Robust strategy suggests that performance is sensitive to the quality of cost estimation. Finally, extending this to tasks where credit assignment is ambiguous remains an open challenge.

Summary updated

BibTeX
@inproceedings{sharaf2017structured,
  author = {Amr Sharaf and Hal Daumé III},
  title = {{Structured Prediction via Learning to Search under Bandit Feedback}},
  booktitle = {SPNLP @ EMNLP},
  year = {2017},
  doi = {10.18653/v1/w17-4304},
}
Figure