Efficient Thompson sampling for online matrix-factorization recommendation

Matrix factorization (MF) collaborative filtering is an effective and widely used method in recommendation systems. However, the problem of finding an optimal trade-off between exploration and exploitation (otherwise known as the bandit problem), a crucial problem in collaborative filtering from cold-start, has not been previously addressed. In this paper, we present a novel algorithm for online MF recommendation that automatically combines finding the most relevant items with exploring new or less-recommended items. Our approach, called Particle Thomp-son sampling for MF (PTS), is based on the general Thompson sampling frame-work, but augmented with a novel efficient online Bayesian probabilistic matrix factorization method based on the Rao-Blackwellized particle filter. Extensive ex-periments in collaborative filtering using several real-world datasets demonstrate that PTS significantly outperforms the current state-of-the-arts. 1