# Contextual Semibandits via Supervised Learning Oracles

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2015.

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

- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Retrieving Black-box Optimal Images from External Databases](https://mlsanity.com/paper/2112.14921/) (2021)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits](https://mlsanity.com/paper/2602.09456/) (2026)
- [An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits](https://mlsanity.com/paper/2310.19025/) (2023)
- [Energy Regularized RNNs for Solving Non-Stationary Bandit Problems](https://mlsanity.com/paper/2303.06552/) (2023)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback](https://mlsanity.com/paper/2606.01081/) (2026)
- [Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation](https://mlsanity.com/paper/2607.13686/) (2026)
- [Sales Channel Optimization via Simulations Based on Observational Data with Delayed Rewards: A Case Study at LinkedIn](https://mlsanity.com/paper/2209.07749/) (2022)

## Abstract (arXiv)

We study an online decision making problem where on each round a learner chooses a list of items based on some side information, receives a scalar feedback value for each individual item, and a reward that is linearly related to this feedback. These problems, known as contextual semibandits, arise in crowdsourcing, recommendation, and many other domains. This paper reduces contextual semibandits to supervised learning, allowing us to leverage powerful supervised learning methods in this partial-feedback setting. Our first reduction applies when the mapping from feedback to reward is known and leads to a computationally efficient algorithm with near-optimal regret. We show that this algorithm outperforms state-of-the-art approaches on real-world learning-to-rank datasets, demonstrating the advantage of oracle-based algorithms. Our second reduction applies to the previously unstudied setting when the linear mapping from feedback to reward is unknown. Our regret guarantees are superior to prior techniques that ignore the feedback.