Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids

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.