2023/05/01 by Julia Olkhovskaya, Olkhovskaya, Julia, Jack Mayo +7 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2305.00832
openalex publication_date 2023/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the adversarial linear contextual bandit setting, which allows for the loss functions associated with each of K arms to change over time without restriction. Assuming the d-dimensional contexts are drawn from a fixed known distribution, the worst-case expected regret over the course of T rounds is known to scale as O(√(Kd T)). Under the additional assumption that the density of the contexts is log-concave, we obtain a second-order bound of order O(K√(d VT)) in terms of the cumulative second moment of the learner's losses VT, and a closely related first-order bound of order O(K√(d LT^*)) in terms of the cumulative loss of the best policy LT^*. Since VT or LT^* may be significantly smaller than T, these improve over the worst-case regret whenever the environment is relatively benign. Our results are obtained using a truncated version of the continuous exponential weights algorithm over the probability simplex, which we analyse by exploiting a novel connection to the linear bandit setting without contexts.