# Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 28 references that are in the map.
- First posted on arXiv 23 Sep 2021.

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

- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)

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

- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)
- [Sparsity-Agnostic Linear Bandits with Adaptive Adversaries](https://mlsanity.com/paper/2406.01192/) (2024)
- [FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2405.14038/) (2024)
- [On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-balls](https://mlsanity.com/paper/2506.19752/) (2025)
- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Learning with Incomplete Context: Linear Contextual Bandits with Pretrained Imputation](https://mlsanity.com/paper/2510.09908/) (2025)

## Abstract (arXiv)

In this paper, we consider the multi-armed bandit problem with high-dimensional features. First, we prove a minimax lower bound, Obig((log d)^fracα+12T^frac1-α2+log Tbig), for the cumulative regret, in terms of horizon T, dimension d and a margin parameter α∈[0,1], which controls the separation between the optimal and the sub-optimal arms. This new lower bound unifies existing regret bound results that have different dependencies on T due to the use of different values of margin parameter α explicitly implied by their assumptions. Second, we propose a simple and computationally efficient algorithm inspired by the general Upper Confidence Bound (UCB) strategy that achieves a regret upper bound matching the lower bound. The proposed algorithm uses a properly centered ℓ1-ball as the confidence set in contrast to the commonly used ellipsoid confidence set. In addition, the algorithm does not require any forced sampling step and is thereby adaptive to the practically unknown margin parameter. Simulations and a real data analysis are conducted to compare the proposed method with existing ones in the literature.