# Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis

arXiv: https://arxiv.org/abs/2002.11332 · HTML: https://mlsanity.com/paper/2002.11332/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2020.

## Built on by (most cited first, 15 of 15)

- [PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits](https://mlsanity.com/paper/2210.15345/) (2022)
- [Contextual Information-Directed Sampling](https://mlsanity.com/paper/2205.10895/) (2022)
- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Does Sparsity Help in Learning Misspecified Linear Bandits?](https://mlsanity.com/paper/2303.16998/) (2023)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13791/) (2023)
- [Sparsity-Agnostic Linear Bandits with Adaptive Adversaries](https://mlsanity.com/paper/2406.01192/) (2024)
- [Noisy Truncated SGD: Optimization and Generalization](https://mlsanity.com/paper/2103.00075/) (2021)
- [New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem](https://mlsanity.com/paper/2312.12400/) (2023)
- [Exploiting Concavity Information in Gaussian Process Contextual Bandit Optimization](https://mlsanity.com/paper/2503.10836/) (2025)
- [Infrequent Exploration in Linear Bandits](https://mlsanity.com/paper/2510.26000/) (2025)

## Abstract (arXiv)

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 θ^* 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 θ^* with any assumed structure. The regret bounds are expressed in terms of geometric quantities such as Gaussian widths associated with the structure of θ^*. We also obtain sharper regret bounds compared to earlier work for the unstructured θ^* setting as a consequence of our improved analysis. We show there is implicit exploration in the smoothed setting where a simple greedy algorithm works.