Timezone: »

 
Poster
Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis
Vidyashankar Sivakumar · Steven Wu · Arindam Banerjee

Wed Jul 15 08:00 AM -- 08:45 AM & Wed Jul 15 09:00 PM -- 09:45 PM (PDT) @
in Poster Session 22 »
Bandit learning algorithms typically involve the balance of exploration and exploitation. However, in many practical applications, worst-case scenarios needing systematic exploration are seldom encountered. In this work, we consider a smoothed setting for structured linear contextual bandits where the adversarial contexts are perturbed by Gaussian noise and the unknown parameter $\theta^*$ has structure, e.g., sparsity, group sparsity, low rank, etc. We propose simple greedy algorithms for both the single- and multi-parameter (i.e., different parameter for each context) settings and provide a unified regret analysis for $\theta^*$ with any assumed structure. The regret bounds are expressed in terms of geometric quantities such as Gaussian widths associated with the structure of $\theta^*$. We also obtain sharper regret bounds compared to earlier work for the unstructured $\theta^*$ setting as a consequence of our improved analysis. We show there is implicit exploration in the smoothed setting where a simple greedy algorithm works.
Keywords: Sparsity and Compressed Sensing · Online Learning / Bandits · Online Learning, Active Learning, and Bandits

Author Information

Vidyashankar Sivakumar (Walmart Labs)
Steven Wu (University of Minnesota)
Arindam Banerjee (University of Minnesota)
Arindam Banerjee

Arindam Banerjee is a Founder Professor at the Department of Computer Science, University of Illinois Urbana-Champaign. His research interests are in machine learning. His current research focuses on computational and statistical aspects of over-parameterized models including deep learning, spatial and temporal data analysis, generative models, and sequential decision making problems. His work also focuses on applications of machine learning in complex real-world and scientific domains including problems in climate science and ecology. He has won several awards, including the NSF CAREER award, the IBM Faculty Award, and six best paper awards in top-tier venues.

More from the Same Authors