# Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 15 references that are in the map.
- First posted on arXiv 24 Feb 2025.

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

- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference](https://mlsanity.com/paper/2207.11597/) (2022)
- [Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization](https://mlsanity.com/paper/2402.07341/) (2024)

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

- [Prior Diffusiveness and Regret in the Linear-Gaussian Bandit](https://mlsanity.com/paper/2601.02022/) (2026)
- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids](https://mlsanity.com/paper/2511.07504/) (2025)
- [Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory](https://mlsanity.com/paper/2610.05659/) (2026)

## Abstract (arXiv)

We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least Omega(min(d σ √T + d |θ|A, |θ|A T)) where d is the dimension, T the time horizon, σ2 the noise variance, A a matrix defining the set of actions and θ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate |θ|, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time O(dT + d2 log(T/d) + d3) and memory O(d2), in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings.