# Stochastic Structured Prediction under Bandit Feedback

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2016.

## Built on by (most cited first, 12 of 12)

- [Reinforcement Learning for Bandit Neural Machine Translation with Simulated Human Feedback](https://mlsanity.com/paper/1707.07402/) (2017)
- [Reliability and Learnability of Human Bandit Feedback for Sequence-to-Sequence Reinforcement Learning](https://mlsanity.com/paper/1805.10627/) (2018)
- [Revisiting the Weaknesses of Reinforcement Learning for Neural Machine Translation](https://mlsanity.com/paper/2106.08942/) (2021)
- [Improving Machine Translation with Human Feedback: An Exploration of Quality Estimation as a Reward Model](https://mlsanity.com/paper/2401.12873/) (2024)
- [Bandits Don't Follow Rules: Balancing Multi-Facet Machine Translation with Multi-Armed Bandits](https://mlsanity.com/paper/2110.06997/) (2021)
- [Offline Reinforcement Learning from Human Feedback in Real-World Sequence-to-Sequence Tasks](https://mlsanity.com/paper/2011.02511/) (2020)
- [Teacher Forcing Recovers Reward Functions for Text Generation](https://mlsanity.com/paper/2210.08708/) (2022)
- [RIVAL: Reinforcement Learning with Iterative and Adversarial Optimization for Machine Translation](https://mlsanity.com/paper/2506.05070/) (2025)
- [LLMR: Knowledge Distillation with a Large Language Model-Induced Reward](https://mlsanity.com/paper/2409.12500/) (2024)
- [An Efficient Algorithm for Deep Stochastic Contextual Bandits](https://mlsanity.com/paper/2104.05613/) (2021)
- [Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback](https://mlsanity.com/paper/2606.01081/) (2026)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)

## Abstract (arXiv)

Stochastic structured prediction under bandit feedback follows a learning protocol where on each of a sequence of iterations, the learner receives an input, predicts an output structure, and receives partial feedback in form of a task loss evaluation of the predicted structure. We present applications of this learning scenario to convex and non-convex objectives for structured prediction and analyze them as stochastic first-order methods. We present an experimental evaluation on problems of natural language processing over exponential output spaces, and compare convergence speed across different objectives under the practical criterion of optimal task performance on development data and the optimization-theoretic criterion of minimal squared gradient norm. Best results under both criteria are obtained for a non-convex objective for pairwise preference learning under bandit feedback.