# Contextual bandits with surrogate losses: Margin bounds and efficient algorithms

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

## Key facts

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

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

- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning](https://mlsanity.com/paper/2106.01723/) (2021)
- [Bandits with Preference Feedback: A Stackelberg Game Perspective](https://mlsanity.com/paper/2406.16745/) (2024)
- [Universal and data-adaptive algorithms for model selection in linear contextual bandits](https://mlsanity.com/paper/2111.04688/) (2021)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [Differentially Private Nonparametric Regression Under a Growth Condition](https://mlsanity.com/paper/2111.12786/) (2021)
- [Provably Efficient Interactive-Grounded Learning with Personalized Reward](https://mlsanity.com/paper/2405.20677/) (2024)
- [An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces](https://mlsanity.com/paper/2502.02140/) (2025)
- [Fast Best-in-Class Regret for Contextual Bandits](https://mlsanity.com/paper/2510.15483/) (2025)
- [Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback](https://mlsanity.com/paper/2602.08307/) (2026)

## Abstract (arXiv)

We use surrogate losses to obtain several new regret bounds and new algorithms for contextual bandit learning. Using the ramp loss, we derive new margin-based regret bounds in terms of standard sequential complexity measures of a benchmark class of real-valued regression functions. Using the hinge loss, we derive an efficient algorithm with a √dT-type mistake bound against benchmark policies induced by d-dimensional regressors. Under realizability assumptions, our results also yield classical regret bounds.