SCIENCE@home

Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids

Raymond Zhang,H'edi Hadiji,Richard Combes

Published 2025 in arXiv.org

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-22 of 22 references · Page 1 of 1

CITED BY