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) @ None #None
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)
More from the Same Authors
-
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