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
in Tuesday Posters »
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).
Keywords: Bandit Algorithms · Online Learning
[ PDF] 

Author Information

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

More from the Same Authors