Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids

We consider the maximization of $x^{\mathrm{\top }}\theta$ over $(x,\theta )\in \mathcal{X}\times \mathrm{\Theta }$, with $\mathcal{X}\subset {\mathbb{R}}^d$ convex and $\mathrm{\Theta }\subset {\mathbb{R}}^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 $\mathcal{X}$ e.g. ${\mathrm{\ell }}_p$ balls with $p>2$, no efficient algorithms exist unless $\mathcal{P}=\mathcal{N}\mathcal{P}$. We then provide two novel algorithms solving this problem efficiently when $\mathcal{X}$ is a centered ellipsoid. Our findings provide the first known method to implement optimistic algorithms for linear bandits in high dimensions.