Contextual bandits with surrogate losses: Margin bounds and efficient algorithms

Dylan J Foster; Akshay Krishnamurthy

NeurIPS 2018poster19 citations

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 a new margin-based regret bound 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.

BibTeX

@inproceedings{NEURIPS2018_01e9565c,
 author = {Foster, Dylan J and Krishnamurthy, Akshay},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Contextual bandits with surrogate losses: Margin bounds and efficient algorithms},
 url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/01e9565cecc4e989123f9620c1d09c09-Paper.pdf},
 volume = {31},
 year = {2018}
}