We consider the maximization of $x^\top \theta$ over $(x,\theta) \in \mathcal{ X} \times \Theta$, with $\mathcal{ X} \subset \mathbb{ R}^d$ convex and $\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. $\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.
Categories: stat.ML cs.LG