Stochastic Low-Rank Bandits

12/13/2017
by   Branislav Kveton, et al.
0

Many problems in computer vision and recommender systems involve low-rank matrices. In this work, we study the problem of finding the maximum entry of a stochastic low-rank matrix from sequential observations. At each step, a learning agent chooses pairs of row and column arms, and receives the noisy product of their latent values as a reward. The main challenge is that the latent values are unobserved. We identify a class of non-negative matrices whose maximum entry can be found statistically efficiently and propose an algorithm for finding them, which we call LowRankElim. We derive a O((K + L) (d) Δ^-1 n) upper bound on its n-step regret, where K is the number of rows, L is the number of columns, d is the rank of the matrix, and Δ is the minimum gap. The bound depends on other problem-specific constants that clearly do not depend K L. To the best of our knowledge, this is the first such result in the literature.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset