# Minimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2025.

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

- [Learning to Sparsify Stochastic Linear Bandits](https://mlsanity.com/paper/2605.10151/) (2026)

## Abstract (arXiv)

We study the stochastic linear bandit problem with multiple arms over T rounds, where the covariate dimension d may exceed T, but each arm-specific parameter vector is s-sparse. We begin by analyzing the sequential estimation problem in the single-arm setting, focusing on cumulative mean-squared error. We show that Lasso estimators are provably suboptimal in the sequential setting, exhibiting suboptimal dependence on d and T, whereas thresholded Lasso estimators -- obtained by applying least squares to the support selected by thresholding an initial Lasso estimator -- achieve the minimax rate. Building on these insights, we consider the full linear contextual bandit problem and propose a three-stage arm selection algorithm that uses thresholded Lasso as the main estimation method. We derive an upper bound on the cumulative regret of order s(log s)(log d + log T), and establish a matching lower bound up to a log s factor, thereby characterizing the minimax regret rate up to a logarithmic term in s. Moreover, when a short initial period is excluded from the regret, the proposed algorithm achieves exact minimax optimality.