# Learning to Sparsify Stochastic Linear Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 11 May 2026.

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [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)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Sparsity-Agnostic Linear Bandits with Adaptive Adversaries](https://mlsanity.com/paper/2406.01192/) (2024)
- [Joint Continuous and Discrete Model Selection via Submodularity](https://mlsanity.com/paper/2102.09029/) (2021)
- [Online Mixed Discrete and Continuous Optimization: Algorithms, Regret Analysis and Applications](https://mlsanity.com/paper/2309.07630/) (2023)
- [New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem](https://mlsanity.com/paper/2312.12400/) (2023)
- [Minimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits](https://mlsanity.com/paper/2505.17400/) (2025)

## Abstract (arXiv)

This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a tildeO(d√T) regret, where d is the dimension of the action vector and T is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a tildeO(d √T) α-regret; for general compact sets lacking strong convexity, we establish a tildeO(d T2/3) α-regret, where α pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments including an application to recommendation system.