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) @
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.
Author Information
Vidyashankar Sivakumar (Walmart Labs)
Steven Wu (University of Minnesota)
Arindam Banerjee (University of Minnesota)

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
-
2020 : Contributed Talk: Incentivizing Bandit Exploration:Recommendations as Instruments »
Dung Ngo · Logan Stapleton · Vasilis Syrgkanis · Steven Wu -
2020 : Contributed Talk: Causal Feature Discovery through Strategic Modification »
Yahav Bechavod · Steven Wu · Juba Ziani -
2022 Poster: Stability Based Generalization Bounds for Exponential Family Langevin Dynamics »
Arindam Banerjee · Tiancong Chen · Xinyan Li · Yingxue Zhou -
2022 Spotlight: Stability Based Generalization Bounds for Exponential Family Langevin Dynamics »
Arindam Banerjee · Tiancong Chen · Xinyan Li · Yingxue Zhou -
2022 Poster: Smoothed Adversarial Linear Contextual Bandits with Knapsacks »
Vidyashankar Sivakumar · Shiliang Zuo · Arindam Banerjee -
2022 Spotlight: Smoothed Adversarial Linear Contextual Bandits with Knapsacks »
Vidyashankar Sivakumar · Shiliang Zuo · Arindam Banerjee -
2020 Poster: New Oracle-Efficient Algorithms for Private Synthetic Data Release »
Giuseppe Vietri · Grace Tian · Mark Bun · Thomas Steinke · Steven Wu -
2020 Poster: Privately Learning Markov Random Fields »
Huanyu Zhang · Gautam Kamath · Janardhan Kulkarni · Steven Wu -
2020 Poster: Private Query Release Assisted by Public Data »
Raef Bassily · Albert Cheu · Shay Moran · Aleksandar Nikolov · Jonathan Ullman · Steven Wu -
2020 Poster: Oracle Efficient Private Non-Convex Optimization »
Seth Neel · Aaron Roth · Giuseppe Vietri · Steven Wu -
2020 Poster: Private Reinforcement Learning with PAC and Regret Guarantees »
Giuseppe Vietri · Borja de Balle Pigem · Akshay Krishnamurthy · Steven Wu -
2019 Poster: Fair Regression: Quantitative Definitions and Reduction-Based Algorithms »
Alekh Agarwal · Miroslav Dudik · Steven Wu -
2019 Oral: Fair Regression: Quantitative Definitions and Reduction-Based Algorithms »
Alekh Agarwal · Miroslav Dudik · Steven Wu -
2019 Poster: Orthogonal Random Forest for Causal Inference »
Miruna Oprescu · Vasilis Syrgkanis · Steven Wu -
2019 Oral: Orthogonal Random Forest for Causal Inference »
Miruna Oprescu · Vasilis Syrgkanis · Steven Wu -
2019 Poster: Locally Private Bayesian Inference for Count Models »
Aaron Schein · Steven Wu · Alexandra Schofield · Mingyuan Zhou · Hanna Wallach -
2019 Oral: Locally Private Bayesian Inference for Count Models »
Aaron Schein · Steven Wu · Alexandra Schofield · Mingyuan Zhou · Hanna Wallach -
2017 Poster: High-Dimensional Structured Quantile Regression »
Vidyashankar Sivakumar · Arindam Banerjee -
2017 Poster: Robust Structured Estimation with Single-Index Models »
Sheng Chen · Arindam Banerjee -
2017 Talk: Robust Structured Estimation with Single-Index Models »
Sheng Chen · Arindam Banerjee -
2017 Talk: High-Dimensional Structured Quantile Regression »
Vidyashankar Sivakumar · Arindam Banerjee