Contextual bandits with surrogate losses: Margin bounds and efficient algorithms

Abstract

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 $\sqrt{dT}$-type mistake bound against benchmark policies induced by $d$-dimensional regressors. Under realizability assumptions, our results also yield classical regret bounds.

Cited by in corpus (7)

• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• Exploiting the Surrogate Gap in Online Multiclass Classification
• Online Pricing with Reserve Price Constraint for Personal Data Markets
• Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case
• Universal and data-adaptive algorithms for model selection in linear contextual bandits