Online Low Rank Matrix Completion

We study the problem of em online low-rank matrix completion with mathsfM users, mathsfN items and mathsfT rounds. In each round, the algorithm recommends one item per user, for which it gets a (noisy) reward sampled from a low-rank user-item preference matrix. The goal is to design a method with sub-linear regret (in mathsfT) and nearly optimal dependence on mathsfM and mathsfN. The problem can be easily mapped to the standard multi-armed bandit problem where each item is an em independent arm, but that leads to poor regret as the correlation between arms and users is not exploited. On the other hand, exploiting the low-rank structure of reward matrix is challenging due to non-convexity of the low-rank manifold. We first demonstrate that the low-rank structure can be exploited using a simple explore-then-commit (ETC) approach that ensures a regret of O(mathsfpolylog (mathsfM+mathsfN) mathsfT2/3). That is, roughly only mathsfpolylog (mathsfM+mathsfN) item recommendations are required per user to get a non-trivial solution. We then improve our result for the rank-1 setting which in itself is quite challenging and encapsulates some of the key issues. Here, we propose textscOCTAL (Online Collaborative filTering using iterAtive user cLustering) that guarantees nearly optimal regret of O(mathsfpolylog (mathsfM+mathsfN) mathsfT1/2). OCTAL is based on a novel technique of clustering users that allows iterative elimination of items and leads to a nearly optimal minimax rate.