Timezone: »

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

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ 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).