Comparator-adaptive Convex Bandits

arXiv (Cornell University)

Abstract

We study bandit convex optimization methods that adapt to the norm of the comparator, a topic that has only been studied before for its full-information counterpart. Specifically, we develop convex bandit algorithms with regret bounds that are small whenever the norm of the comparator is small. We first use techniques from the full-information setting to develop comparator-adaptive algorithms for linear bandits. Then, we extend the ideas to convex bandits with Lipschitz or smooth loss functions, using a new single-point gradient estimator and carefully designed surrogate losses.

Authors 3

1. Dirk van der Hoeven Aachen

   Leiden University

   Affiliation as printed

   Leiden University

2. Ashok Cutkosky

   Boston University

   Affiliation as printed

   Boston University

3. Haipeng Luo

   University of Southern California

   Affiliation as printed

   University of Southern California