Practical Contextual Bandits with Regression Oracles

Dylan Foster, Alekh Agarwal, Miroslav Dudik, Haipeng Luo, Robert Schapire
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1539-1548, 2018.

Abstract

A major challenge in contextual bandits is to design general-purpose algorithms that are both practically useful and theoretically well-founded. We present a new technique that has the empirical and computational advantages of realizability-based approaches combined with the flexibility of agnostic methods. Our algorithms leverage the availability of a regression oracle for the value-function class, a more realistic and reasonable oracle than the classification oracles over policies typically assumed by agnostic methods. Our approach generalizes both UCB and LinUCB to far more expressive possible model classes and achieves low regret under certain distributional assumptions. In an extensive empirical evaluation, we find that our approach typically matches or outperforms both realizability-based and agnostic baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-foster18a, title = {Practical Contextual Bandits with Regression Oracles}, author = {Foster, Dylan and Agarwal, Alekh and Dudik, Miroslav and Luo, Haipeng and Schapire, Robert}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1539--1548}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/foster18a/foster18a.pdf}, url = {https://proceedings.mlr.press/v80/foster18a.html}, abstract = {A major challenge in contextual bandits is to design general-purpose algorithms that are both practically useful and theoretically well-founded. We present a new technique that has the empirical and computational advantages of realizability-based approaches combined with the flexibility of agnostic methods. Our algorithms leverage the availability of a regression oracle for the value-function class, a more realistic and reasonable oracle than the classification oracles over policies typically assumed by agnostic methods. Our approach generalizes both UCB and LinUCB to far more expressive possible model classes and achieves low regret under certain distributional assumptions. In an extensive empirical evaluation, we find that our approach typically matches or outperforms both realizability-based and agnostic baselines.} }
Endnote
%0 Conference Paper %T Practical Contextual Bandits with Regression Oracles %A Dylan Foster %A Alekh Agarwal %A Miroslav Dudik %A Haipeng Luo %A Robert Schapire %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-foster18a %I PMLR %P 1539--1548 %U https://proceedings.mlr.press/v80/foster18a.html %V 80 %X A major challenge in contextual bandits is to design general-purpose algorithms that are both practically useful and theoretically well-founded. We present a new technique that has the empirical and computational advantages of realizability-based approaches combined with the flexibility of agnostic methods. Our algorithms leverage the availability of a regression oracle for the value-function class, a more realistic and reasonable oracle than the classification oracles over policies typically assumed by agnostic methods. Our approach generalizes both UCB and LinUCB to far more expressive possible model classes and achieves low regret under certain distributional assumptions. In an extensive empirical evaluation, we find that our approach typically matches or outperforms both realizability-based and agnostic baselines.
APA
Foster, D., Agarwal, A., Dudik, M., Luo, H. & Schapire, R.. (2018). Practical Contextual Bandits with Regression Oracles. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1539-1548 Available from https://proceedings.mlr.press/v80/foster18a.html.

Related Material