@inproceedings{syrgkanis2016improved,
author = {Syrgkanis, Vasilis and Luo, Haipeng and Krishnamurthy, Akshay and Schapire, Robert E.},
title = {Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits},
booktitle = {Advances in Neural Information Processing Systems},
year = {2016},
month = {December},
abstract = {We give an oracle-based algorithm 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 )^[2/3] (log N)^[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^[3/4])$ barrier that is achieved by recently introduced algorithms. Breaking this barrier was left as a major open problem. Our analysis is based on the recent relaxation based approach of Rakhlin and Sridharan [7].},
url = {http://approjects.co.za/?big=en-us/research/publication/improved-regret-bounds-oracle-based-adversarial-contextual-bandits/},
pages = {3135-3143},
}