# Linear bandits with polylogarithmic minimax regret

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 13 references that are in the map.
- First posted on arXiv 19 Feb 2024.

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

- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference](https://mlsanity.com/paper/2207.11597/) (2022)
- [On the Complexity of Bandit Linear Optimization](https://mlsanity.com/paper/1408.2368/) (2014)

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

- [Learning pure quantum states (almost) without regret](https://mlsanity.com/paper/2406.18370/) (2024)
- [Quantum state-agnostic work extraction (almost) without dissipation](https://mlsanity.com/paper/2505.09456/) (2025)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)
- [Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds](https://mlsanity.com/paper/2411.12154/) (2024)
- [A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noise](https://mlsanity.com/paper/2501.11127/) (2025)
- [Learning Pure Quantum States in Any Dimension (Almost) Without Regret](https://mlsanity.com/paper/2605.09019/) (2026)
- [Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms](https://mlsanity.com/paper/2608.14319/) (2026)
- [A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets](https://mlsanity.com/paper/2609.32149/) (2026)

## Abstract (arXiv)

We study a noise model for linear stochastic bandits for which the subgaussian noise parameter vanishes linearly as we select actions on the unit sphere closer and closer to the unknown vector. We introduce an algorithm for this problem that exhibits a minimax regret scaling as log3(T) in the time horizon T, in stark contrast the square root scaling of this regret for typical bandit algorithms. Our strategy, based on weighted least-squares estimation, achieves the eigenvalue relation λmin ( Vt ) = Omega (√λmax(Vt ) ) for the design matrix Vt at each time step t through geometrical arguments that are independent of the noise model and might be of independent interest. This allows us to tightly control the expected regret in each time step to be of the order O(frac1t), leading to the logarithmic scaling of the cumulative regret.