Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits

We consider the adversarial linear contextual bandit problem, where the loss vectors are selected fully adversarially and the per-round action set (i.e. the context) is drawn from a fixed distribution. Existing methods for this problem either require access to a simulator to generate free i.i.d. contexts, achieve a suboptimal regret no better than O(T 5 /6 ), or are computationally inefficient. We greatly improve these results by achieving a regret of O( √ T ) without a simulator, while maintaining computational efficiency when the action set in each round is small. In the special case of sleeping bandits with adversarial loss and stochastic arm availability, our result answers affirmatively the open question by Saha et al. [2020] on whether there exists a polynomial-time algorithm with poly(d) √ T regret. Our approach naturally handles the case where the loss is linear up to an additive misspecification error, and our regret shows near-optimal dependence on the magnitude of the error. * The authors are listed in alphabetical order. † This work was done when Chen-Yu Wei was at MIT Institute for Data, Systems, and Society. 1 Apparently, the stochastic and adversarial linear contextual bandits defined here are incomparable, and their names do not fully capture their underlying assumptions. However, these are the terms commonly used in the literature (e.g., [Abbasi-Yadkori et al., 2011, Neu and Olkhovskaya, 2020] ).