Improved regret bounds for oracle-based adversarial contextual bandits

Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, Robert E. Schapire

Research output: Contribution to journalConference articlepeer-review

24 Scopus citations


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)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(T3/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 [7].

Original languageEnglish (US)
Pages (from-to)3143-3151
Number of pages9
JournalAdvances in Neural Information Processing Systems
StatePublished - 2016
Externally publishedYes
Event30th Annual Conference on Neural Information Processing Systems, NIPS 2016 - Barcelona, Spain
Duration: Dec 5 2016Dec 10 2016

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Improved regret bounds for oracle-based adversarial contextual bandits'. Together they form a unique fingerprint.

Cite this