# Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 35 references that are in the map.
- First posted on arXiv 10 Nov 2025.

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

- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits](https://mlsanity.com/paper/2002.07258/) (2020)
- [When and why randomised exploration works (in linear bandits)](https://mlsanity.com/paper/2502.08870/) (2025)
- [Linear Bandits on Ellipsoids: Minimax Optimal Algorithms](https://mlsanity.com/paper/2502.17175/) (2025)

## Abstract (arXiv)

We consider the maximization of x^top θ over (x,θ) ∈ X × Theta, with X subset ℝd convex and Theta subset ℝd an ellipsoid. This problem is fundamental in linear bandits, as the learner must solve it at every time step using optimistic algorithms. We first show that for some sets X e.g. ℓp balls with p>2, no efficient algorithms exist unless P = NP. We then provide two novel algorithms solving this problem efficiently when X is a centered ellipsoid. Our findings provide the first known method to implement optimistic algorithms for linear bandits in high dimensions.