Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids

Abstract

We consider the maximization of $x^{\top }\hat{I}¸$ over $(x,\hat{I}¸)\in \mathcal{X}\times \hat{I}˜$, with $\mathcal{X}\subset {\mathbb{R}}^d$ convex and $\hat{I}˜\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. ${\ell }_p$ balls with $p>2$, no efficient algorithms exist unless $\mathcal{P}=\mathcal{NP}$. 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.

27 pages, 8 figures, 4 algos