Poster
Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits
Vasilis Syrgkanis · Haipeng Luo · Akshay Krishnamurthy · Robert Schapire

Tue Dec 6th 06:00 -- 09:30 PM @ Area 5+6+7+8 #43 #None
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).

Author Information

Vasilis Syrgkanis (Microsoft Research)
Haipeng Luo (Princeton University)
Akshay Krishnamurthy (UMass Amherst)
Robert Schapire (MIcrosoft Research)

More from the Same Authors