  We study the problem of {\em online} low-rank matrix completion with
$\mathsf{M}$ users, $\mathsf{N}$ items and $\mathsf{T}$ 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 $\mathsf{T}$) and nearly optimal dependence
on $\mathsf{M}$ and $\mathsf{N}$. 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(\mathsf{polylog}
(\mathsf{M}+\mathsf{N}) \mathsf{T}^{2/3})$. That is, roughly only
$\mathsf{polylog} (\mathsf{M}+\mathsf{N})$ 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 \textsc{OCTAL} (Online Collaborative filTering
using iterAtive user cLustering) that guarantees nearly optimal regret of
$O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{1/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.
