Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids
arXiv:2511.07504v1 Announce Type: new
Abstract: 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.
Abstract: 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.
Raymond Zhang, H’edi Hadiji, Richard Combes
Go to original source