Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits
Abstract
We propose a new oracle-based algorithm, BISTRO+, for the adversarial contextual bandit problem, where either contexts are drawn i.i.d. or the sequence of contexts is known a priori, but where the losses are picked adversarially. Our algorithm is computationally efficient, assuming access to an offline optimization oracle, and enjoys a regret of order $O((KT)^{\frac{2}{3}}(\log N)^{\frac{1}{3}})$, where $K$ is the number of actions, $T$ is the number of iterations, and $N$ is the number of baseline policies. Our result is the first to break the $O(T^{\frac{3}{4}})$ barrier achieved by recent algorithms, which was left as a major open problem. Our analysis employs the recent relaxation framework of (Rakhlin and Sridharan, ICML'16).
Cite
Text
Syrgkanis et al. "Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits." Neural Information Processing Systems, 2016.Markdown
[Syrgkanis et al. "Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits." Neural Information Processing Systems, 2016.](https://mlanthology.org/neurips/2016/syrgkanis2016neurips-improved/)BibTeX
@inproceedings{syrgkanis2016neurips-improved,
title = {{Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits}},
author = {Syrgkanis, Vasilis and Luo, Haipeng and Krishnamurthy, Akshay and Schapire, Robert E.},
booktitle = {Neural Information Processing Systems},
year = {2016},
pages = {3135-3143},
url = {https://mlanthology.org/neurips/2016/syrgkanis2016neurips-improved/}
}