# Sparsity-Agnostic Linear Bandits with Adaptive Adversaries

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 27 references that are in the map.
- First posted on arXiv 3 Jun 2024.

## Builds on (most cited first, 17 of 17)

- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits](https://mlsanity.com/paper/2006.02612/) (2020)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits](https://mlsanity.com/paper/2210.15345/) (2022)
- [Thresholded Lasso Bandit](https://mlsanity.com/paper/2010.11994/) (2020)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis](https://mlsanity.com/paper/2002.11332/) (2020)
- [Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection](https://mlsanity.com/paper/2009.02003/) (2020)
- [Variance-Aware Sparse Linear Bandits](https://mlsanity.com/paper/2205.13450/) (2022)
- [Best of Both Worlds Model Selection](https://mlsanity.com/paper/2206.14912/) (2022)
- [Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms](https://mlsanity.com/paper/2106.02979/) (2021)
- [Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit](https://mlsanity.com/paper/2109.11612/) (2021)

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

- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Learning to Sparsify Stochastic Linear Bandits](https://mlsanity.com/paper/2605.10151/) (2026)

## Abstract (arXiv)

We study stochastic linear bandits where, in each round, the learner receives a set of actions (i.e., feature vectors), from which it chooses an element and obtains a stochastic reward. The expected reward is a fixed but unknown linear function of the chosen action. We study sparse regret bounds, that depend on the number S of non-zero coefficients in the linear reward function. Previous works focused on the case where S is known, or the action sets satisfy additional assumptions. In this work, we obtain the first sparse regret bounds that hold when S is unknown and the action sets are adversarially generated. Our techniques combine online to confidence set conversions with a novel randomized model selection approach over a hierarchy of nested confidence sets. When S is known, our analysis recovers state-of-the-art bounds for adversarial action sets. We also show that a variant of our approach, using Exp3 to dynamically select the confidence sets, can be used to improve the empirical performance of stochastic linear bandits while enjoying a regret bound with optimal dependence on the time horizon.