Efficient Optimal Learning for Contextual Bandits

Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:197-216, 2011.

Abstract

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-dudik11a, title = {Efficient Optimal Learning for Contextual Bandits}, author = {Dudik, Miroslav and Hsu, Daniel and Kale, Satyen and Karampatziakis, Nikos and Langford, John and Reyzin, Lev and Zhang, Tong}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {197--216}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/dudik11a/dudik11a.pdf}, url = {https://proceedings.mlr.press/r9/dudik11a.html}, abstract = {We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient Optimal Learning for Contextual Bandits %A Miroslav Dudik %A Daniel Hsu %A Satyen Kale %A Nikos Karampatziakis %A John Langford %A Lev Reyzin %A Tong Zhang %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-dudik11a %I PMLR %P 197--216 %U https://proceedings.mlr.press/r9/dudik11a.html %V R9 %X We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work. %Z Reissued by PMLR on 04 October 2026.
APA
Dudik, M., Hsu, D., Kale, S., Karampatziakis, N., Langford, J., Reyzin, L. & Zhang, T.. (2011). Efficient Optimal Learning for Contextual Bandits. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:197-216 Available from https://proceedings.mlr.press/r9/dudik11a.html. Reissued by PMLR on 04 October 2026.

Related Material