# Variance-Aware Sparse Linear Bandits

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 58 references that are in the map.
- First posted on arXiv 26 May 2022.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2008.11918/) (2020)
- [Online Sparse Reinforcement Learning](https://mlsanity.com/paper/2011.04018/) (2020)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Tight Regret Bounds for Infinite-armed Linear Contextual Bandits](https://mlsanity.com/paper/1905.01435/) (2019)
- [Thresholded Lasso Bandit](https://mlsanity.com/paper/2010.11994/) (2020)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection](https://mlsanity.com/paper/2009.02003/) (2020)

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

- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [How Does Variance Shape the Regret in Contextual Bandits?](https://mlsanity.com/paper/2410.12713/) (2024)
- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [Variance-Dependent Regret Lower Bounds for Contextual Bandits](https://mlsanity.com/paper/2503.12020/) (2025)
- [Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/2506.06521/) (2025)
- [Why Keep Your Doubts to Yourself? Trading Visual Uncertainties in Multi-Agent Bandit Systems](https://mlsanity.com/paper/2601.18735/) (2026)
- [Variance-Dependent Regret Bounds for Non-stationary Linear Bandits](https://mlsanity.com/paper/2403.10732/) (2024)
- [Sparsity-Agnostic Linear Bandits with Adaptive Adversaries](https://mlsanity.com/paper/2406.01192/) (2024)
- [Is Offline Decision Making Possible with Only Few Samples? Reliable Decisions in Data-Starved Bandits via Trust Region Enhancement](https://mlsanity.com/paper/2402.15703/) (2024)
- [Learning to Sparsify Stochastic Linear Bandits](https://mlsanity.com/paper/2605.10151/) (2026)

## Abstract (arXiv)

It is well-known that for sparse linear bandits, when ignoring the dependency on sparsity which is much smaller than the ambient dimension, the worst-case minimax regret is widetildeThetaleft(√dTright) where d is the ambient dimension and T is the number of rounds. On the other hand, in the benign setting where there is no noise and the action set is the unit sphere, one can use divide-and-conquer to achieve widetildemathcal O(1) regret, which is (nearly) independent of d and T. In this paper, we present the first variance-aware regret guarantee for sparse linear bandits: widetildemathcal Oleft(√dsumt=1T σt2 + 1right), where σt2 is the variance of the noise at the t-th round. This bound naturally interpolates the regret bounds for the worst-case constant-variance regime (i.e., σt equiv Omega(1)) and the benign deterministic regimes (i.e., σt equiv 0). To achieve this variance-aware regret guarantee, we develop a general framework that converts any variance-aware linear bandit algorithm to a variance-aware algorithm for sparse linear bandits in a "black-box" manner. Specifically, we take two recent algorithms as black boxes to illustrate that the claimed bounds indeed hold, where the first algorithm can handle unknown-variance cases and the second one is more efficient.