# Simple Regret Minimization for Contextual Bandits

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2018.

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

- [Modern Bayesian Experimental Design](https://mlsanity.com/paper/2302.14545/) (2023)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [Concentrated Differential Privacy for Bandits](https://mlsanity.com/paper/2309.00557/) (2023)
- [The Role of Contextual Information in Best Arm Identification](https://mlsanity.com/paper/2106.14077/) (2021)
- [Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learning](https://mlsanity.com/paper/2211.12004/) (2022)
- [Best Arm Identification with Contextual Information under a Small Gap](https://mlsanity.com/paper/2209.07330/) (2022)
- [Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds](https://mlsanity.com/paper/2302.02988/) (2023)
- [Adaptive Experimentation at Scale: A Computational Framework for Flexible Batches](https://mlsanity.com/paper/2303.11582/) (2023)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Offline RL With Resource Constrained Online Deployment](https://mlsanity.com/paper/2110.03165/) (2021)
- [Active Learning for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2605.24803/) (2026)
- [Demystifying the unreasonable effectiveness of online alignment methods](https://mlsanity.com/paper/2604.17207/) (2026)
- [Active Context Selection Improves Simple Regret in Contextual Bandits](https://mlsanity.com/paper/2605.20040/) (2026)
- [CurveRL: Principled Distribution-Aware Context Reweighting for LLM Reasoning](https://mlsanity.com/paper/2605.24331/) (2026)

## Abstract (arXiv)

There are two variants of the classical multi-armed bandit (MAB) problem that have received considerable attention from machine learning researchers in recent years: contextual bandits and simple regret minimization. Contextual bandits are a sub-class of MABs where, at every time step, the learner has access to side information that is predictive of the best arm. Simple regret minimization assumes that the learner only incurs regret after a pure exploration phase. In this work, we study simple regret minimization for contextual bandits. Motivated by applications where the learner has separate training and autonomous modes, we assume that the learner experiences a pure exploration phase, where feedback is received after every action but no regret is incurred, followed by a pure exploitation phase in which regret is incurred but there is no feedback. We present the Contextual-Gap algorithm and establish performance guarantees on the simple regret, i.e., the regret during the pure exploitation phase. Our experiments examine a novel application to adaptive sensor selection for magnetic field estimation in interplanetary spacecraft, and demonstrate considerable improvement over algorithms designed to minimize the cumulative regret.