Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery
Yassir Jedra William Réveillard Stefan Stojanovic Alexandre Proutiere
We study contextual bandits with low-rank structure where, in each round, if
the (context, arm) pair $(i,j)\in [m]\times [n]$ is selected, the learner
observes a noisy sample of the $(i,j)$-th entry of an unknown low-rank reward
matrix. Successive contexts are generated randomly in an i.i.d. manner and are
revealed to the learner. For such bandits, we present efficient algorithms for
policy evaluation, best policy identification and regret minimization. For
policy evaluation and best policy identification, we show that our algorithms
are nearly minimax optimal. For instance, the number of samples required to
return an $\varepsilon$-optimal policy with probability at least $1-\delta$
typically scales as ${m+n\over \varepsilon^2}\log(1/\delta)$. Our regret
minimization algorithm enjoys minimax guarantees scaling as
$r^{7/4}(m+n)^{3/4}\sqrt{T}$, which improves over existing algorithms. All the
proposed algorithms consist of two phases: they first leverage spectral methods
to estimate the left and right singular subspaces of the low-rank reward
matrix. We show that these estimates enjoy tight error guarantees in the
two-to-infinity norm. This in turn allows us to reformulate our problems as a
misspecified linear bandit problem with dimension roughly $r(m+n)$ and
misspecification controlled by the subspace recovery error, as well as to
design the second phase of our algorithms efficiently.