Contextual bandits with surrogate losses: Margin bounds and efficient algorithms
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsregressionSimilar Papers 제목 키워드 기반
A Universal Growth Rate for Learning with Smooth Surrogate Losses
This paper presents a comprehensive analysis of the growth rate of $H$-consistency bounds (and excess error bounds) for various surrogate losses used in classification. We prove a square-root growth rate near zero for sm…
Binary ClassificationClassificationMulti-class ClassificationFast Best-in-Class Regret for Contextual Bandits
We study the problem of stochastic contextual bandits in the agnostic setting, where the goal is to compete with the best policy in a given class without assuming realizability or imposing model restrictions on losses or…
Comparator-adaptive Convex Bandits
We study bandit convex optimization methods that adapt to the norm of the comparator, a topic that has only been studied before for its full-information counterpart. Specifically, we develop convex bandit algorithms with…
Generalized Translation and Scale Invariant Online Algorithm for Adversarial Multi-Armed Bandits
We study the adversarial multi-armed bandit problem and create a completely online algorithmic framework that is invariant under arbitrary translations and scales of the arm losses. We study the expected performance of o…
Multi-Armed BanditsTranslationFundamental Novel Consistency Theory: $H$-Consistency Bounds
In machine learning, the loss functions optimized during training often differ from the target loss that defines task performance due to computational intractability or lack of differentiability. We present an in-depth s…
Multi-class ClassificationBinary Classification