## 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)^{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(T^{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 [7].

Original language | English (US) |
---|---|

Pages (from-to) | 3143-3151 |

Number of pages | 9 |

Journal | Advances in Neural Information Processing Systems |

State | Published - Jan 1 2016 |

Externally published | Yes |

Event | 30th Annual Conference on Neural Information Processing Systems, NIPS 2016 - Barcelona, Spain Duration: Dec 5 2016 → Dec 10 2016 |

## All Science Journal Classification (ASJC) codes

- Computer Networks and Communications
- Information Systems
- Signal Processing