We investigate the low rank matrix completion problem in an online setting with ${ M}$ users, ${ N}$ items, ${ T}$ rounds, and an unknown rank-$r$ reward matrix ${ R}\in \mathbb{ R}^{ { M}\times { N}}$. This problem has been well-studied in the literature and has several applications in practice. In each round, we recommend ${ S}$ carefully chosen distinct items to every user and observe noisy rewards. In the regime where ${ M},{ N} >> { T}$, we propose two distinct computationally efficient algorithms for recommending items to users and analyze them under the benign \emph{ hott items} assumption.1) First, for ${ S}=1$, under additional incoherence/smoothness assumptions on ${ R}$, we propose the phased algorithm \textsc{ PhasedClusterElim}. Our algorithm obtains a near-optimal per-user regret of $\tilde{ O}({ N}{ M}^{ -1}(\Delta^{ -1}+\Delta_{ { hott}}^{ -2}))$ where $\Delta_{ { hott}},\Delta$ are problem-dependent gap parameters with $\Delta_{ { hott}} >> \Delta$ almost always. 2) Second, we consider a simplified setting with ${ S}=r$ where we make significantly milder assumptions on ${ R}$. Here, we introduce another phased algorithm, \textsc{ DeterminantElim}, to derive a regret guarantee of $\widetilde{ O}({ N}{ M}^{ -1/r}\Delta_{ det}^{ -1}))$ where $\Delta_{ { det}}$ is another problem-dependent gap. Both algorithms crucially use collaboration among users to jointly eliminate sub-optimal items for groups of users successively in phases, but with distinctive and novel approaches.
Categories: cs.LG cs.IR stat.ML