# Sparse Linear Bandits with Blocking Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 51 references that are in the map.
- First posted on arXiv 26 Oct 2024.

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

- [Beyond neural scaling laws: beating power law scaling via data pruning](https://mlsanity.com/paper/2206.14486/) (2022)
- [Visual Transformers: Token-based Image Representation and Processing for Computer Vision](https://mlsanity.com/paper/2006.03677/) (2020)
- [Understanding Dataset Difficulty with V-Usable Information](https://mlsanity.com/paper/2110.08420/) (2021)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Prioritized Training on Points that are Learnable, Worth Learning, and Not Yet Learnt](https://mlsanity.com/paper/2206.07137/) (2022)
- [A Survey on Data Selection for Language Models](https://mlsanity.com/paper/2402.16827/) (2024)
- [DeepCore: A Comprehensive Library for Coreset Selection in Deep Learning](https://mlsanity.com/paper/2204.08499/) (2022)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [D2 Pruning: Message Passing for Balancing Diversity and Difficulty in Data Pruning](https://mlsanity.com/paper/2310.07931/) (2023)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [An Empirical Exploration of Curriculum Learning for Neural Machine Translation](https://mlsanity.com/paper/1811.00739/) (2018)
- [A Survey on Deep Active Learning: Recent Advances and New Frontiers](https://mlsanity.com/paper/2405.00334/) (2024)
- [How hard can it be? Estimating the difficulty of visual search in an image](https://mlsanity.com/paper/1705.08280/) (2017)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Let's Learn Step by Step: Enhancing In-Context Learning Ability with Curriculum Learning](https://mlsanity.com/paper/2402.10738/) (2024)
- [Which Examples to Annotate for In-Context Learning? Towards Effective and Efficient Selection](https://mlsanity.com/paper/2310.20046/) (2023)
- [Similarity Search for Efficient Active Learning and Search of Rare Concepts](https://mlsanity.com/paper/2007.00077/) (2020)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach](https://mlsanity.com/paper/1711.05174/) (2017)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [Regret Guarantees for Item-Item Collaborative Filtering](https://mlsanity.com/paper/1507.05371/) (2015)
- [LLM Chain Ensembles for Scalable and Accurate Data Annotation](https://mlsanity.com/paper/2410.13006/) (2024)
- [A Latent Source Model for Online Collaborative Filtering](https://mlsanity.com/paper/1411.6591/) (2014)
- [Learning User Preferences in Non-Stationary Environments](https://mlsanity.com/paper/2101.12506/) (2021)
- [The Sample Complexity of Online One-Class Collaborative Filtering](https://mlsanity.com/paper/1706.00061/) (2017)
- [High-dimensional Contextual Bandit Problem without Sparsity](https://mlsanity.com/paper/2306.11017/) (2023)
- [AnchorAL: Computationally Efficient Active Learning for Large and Imbalanced Datasets](https://mlsanity.com/paper/2404.05623/) (2024)
- [Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints](https://mlsanity.com/paper/2311.03376/) (2023)
- [Maximizing the Minimum Eigenvalue in Constant Dimension](https://mlsanity.com/paper/2401.14317/) (2024)
- [Investigating the Impact of Hard Samples on Accuracy Reveals In-class Data Imbalance](https://mlsanity.com/paper/2409.14401/) (2024)

## Abstract (arXiv)

We investigate the high-dimensional sparse linear bandits problem in a data-poor regime where the time horizon is much smaller than the ambient dimension and number of arms. We study the setting under the additional blocking constraint where each unique arm can be pulled only once. The blocking constraint is motivated by practical applications in personalized content recommendation and identification of data points to improve annotation efficiency for complex learning tasks. With mild assumptions on the arms, our proposed online algorithm (BSLB) achieves a regret guarantee of widetildemathsfO((1+βk)2k^frac23 mathsfT^frac23) where the parameter vector has an (unknown) relative tail βk -- the ratio of ℓ1 norm of the top-k and remaining entries of the parameter vector. To this end, we show novel offline statistical guarantees of the lasso estimator for the linear model that is robust to the sparsity modeling assumption. Finally, we propose a meta-algorithm (C-BSLB) based on corralling that does not need knowledge of optimal sparsity parameter k at minimal cost to regret. Our experiments on multiple real-world datasets demonstrate the validity of our algorithms and theoretical framework.