{"ID":2844097,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.07504","arxiv_id":"2511.07504","title":"Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids","abstract":"We consider the maximization of $x^\\top θ$ over $(x,θ) \\in \\mathcal{X} \\times Θ$, with $\\mathcal{X} \\subset \\mathbb{R}^d$ convex and $Θ\\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\u003e2$, 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.","short_abstract":"We consider the maximization of $x^\\top θ$ over $(x,θ) \\in \\mathcal{X} \\times Θ$, with $\\mathcal{X} \\subset \\mathbb{R}^d$ convex and $Θ\\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 so...","url_abs":"https://arxiv.org/abs/2511.07504","url_pdf":"https://arxiv.org/pdf/2511.07504v1","authors":"[\"Raymond Zhang\",\"Hédi Hadiji\",\"Richard Combes\"]","published":"2025-11-10T17:22:34Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\"]","methods":"[]","has_code":false}