Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits
This work addresses a core challenge in online learning for bandit problems, providing near-optimal and efficient solutions that could impact applications like recommendation systems, though it is incremental in advancing existing theoretical bounds.
The paper tackles the adversarial linear contextual bandit problem by developing a computationally efficient algorithm that achieves a regret of $\widetilde{O}(\sqrt{T})$ without requiring a simulator, improving upon prior sub-optimal or inefficient methods, and it affirmatively answers an open question about polynomial-time algorithms with $poly(d)\sqrt{T}$ regret for sleeping 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 sub-optimal regret no better than $\widetilde{O}(T^{\frac{5}{6}})$, or are computationally inefficient. We greatly improve these results by achieving a regret of $\widetilde{O}(\sqrt{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)\sqrt{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.