### Poster

## Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits

### Vasilis Syrgkanis · Haipeng Luo · Akshay Krishnamurthy · Robert Schapire

##### Area 5+6+7+8 #43

Keywords: [ Online Learning ] [ Bandit Algorithms ]

[
Abstract
]

Abstract:
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).

Live content is unavailable. Log in and register to view live content