# High-dimensional Contextual Bandit Problem without Sparsity

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 19 Jun 2023.

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

- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (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)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [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)

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

- [Leveraging semantic similarity for experimentation with AI-generated treatments](https://mlsanity.com/paper/2510.21119/) (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)
- [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)

In this research, we investigate the high-dimensional linear contextual bandit problem where the number of features p is greater than the budget T, or it may even be infinite. Differing from the majority of previous works in this field, we do not impose sparsity on the regression coefficients. Instead, we rely on recent findings on overparameterized models, which enables us to analyze the performance of the minimum-norm interpolating estimator when data distributions have small effective ranks. We propose an explore-then-commit (EtC) algorithm to address this problem and examine its performance. Through our analysis, we derive the optimal rate of the ETC algorithm in terms of T and show that this rate can be achieved by balancing exploration and exploitation. Moreover, we introduce an adaptive explore-then-commit (AEtC) algorithm that adaptively finds the optimal balance. We assess the performance of the proposed algorithms through a series of simulations.