# A Simple Unified Framework for High Dimensional Bandit Problems

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 39 references that are in the map.
- First posted on arXiv 18 Feb 2021.

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

- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Stochastic Low-Rank Bandits](https://mlsanity.com/paper/1712.04644/) (2017)
- [Stochastic Rank-1 Bandits](https://mlsanity.com/paper/1608.03023/) (2016)
- [Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling](https://mlsanity.com/paper/1912.03074/) (2019)
- [Bernoulli Rank-1 Bandits for Click Feedback](https://mlsanity.com/paper/1703.06513/) (2017)
- [Structured Stochastic Linear Bandits](https://mlsanity.com/paper/1606.05693/) (2016)

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

- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Anytime Model Selection in Linear Bandits](https://mlsanity.com/paper/2307.12897/) (2023)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [High-dimensional Contextual Bandit Problem without Sparsity](https://mlsanity.com/paper/2306.11017/) (2023)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Federated Online Sparse Decision Making](https://mlsanity.com/paper/2202.13448/) (2022)
- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)
- [Sparsity-Agnostic Linear Bandits with Adaptive Adversaries](https://mlsanity.com/paper/2406.01192/) (2024)
- [Advertising Media and Target Audience Optimization via High-dimensional Bandits](https://mlsanity.com/paper/2209.08403/) (2022)
- [Fixed-Budget Best-Arm Identification in Sparse Linear Bandits](https://mlsanity.com/paper/2311.00481/) (2023)
- [Efficient Generalized Low-Rank Tensor Contextual Bandits](https://mlsanity.com/paper/2311.01771/) (2023)
- [A Unified Regularization Approach to High-Dimensional Generalized Tensor Bandits](https://mlsanity.com/paper/2501.10722/) (2025)
- [High-dimensional Nonparametric Contextual Bandit Problem](https://mlsanity.com/paper/2505.14102/) (2025)
- [On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-balls](https://mlsanity.com/paper/2506.19752/) (2025)
- [Differentially Private High Dimensional Bandits](https://mlsanity.com/paper/2402.03737/) (2024)
- [Sparse Linear Bandits with Blocking Constraints](https://mlsanity.com/paper/2410.20041/) (2024)
- [Navigating Sparsities in High-Dimensional Linear Contextual Bandits](https://mlsanity.com/paper/2510.08435/) (2025)

## Abstract (arXiv)

Stochastic high dimensional bandit problems with low dimensional structures are useful in different applications such as online advertising and drug discovery. In this work, we propose a simple unified algorithm for such problems and present a general analysis framework for the regret upper bound of our algorithm. We show that under some mild unified assumptions, our algorithm can be applied to different high dimensional bandit problems. Our framework utilizes the low dimensional structure to guide the parameter estimation in the problem, therefore our algorithm achieves the comparable regret bounds in the LASSO bandit, as well as novel bounds in the low-rank matrix bandit, the group sparse matrix bandit, and in a new problem: the multi-agent LASSO bandit.