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 Thompson sampling for MF (PTS), is based on the general Thompson sampling framework, but augmented with a novel efficient online Bayesian probabilistic matrix factorization method based on the Rao-Blackwellized particle filter. Extensive experiments in collaborative filtering using several real-world datasets demonstrate that PTS significantly outperforms the current state-of-the-arts.
The authors propose an online matrix completion algorithm that employs particle filters to represent the posterior distribution over user/item factors. Thompson sampling is employed to recommend items according to this approximated posterior. Particle are then resampled, but only the vectors of item and user corresponding to the most recently received rating.A theoretical bound on the regret is provided, and the method is analyzed on synthetic data, and compared against various baseline strategies on 5 real datasets. The method outperforms all but one baseline on all the datasets (and the best baseline is considered unrealistic but see question below). The value of this method hinges on the assumption that uncertainty of *both* user and item factors is necessary to make reasonable recommendations in the cold-start scenario, which is illustrated in Figure 4c.Overall, this paper may be a solid contribution but I have some concerns that need to be resolved:1. In 4/5 of the real datasets, the proposed method is either comparable orworse than the strategy of picking the most popular item (restricted to those recommended for that user). This is labelled as an 'unrealistically optimistic baseline' as it is not possible to know global popularity beforehand. However, it certainly seems possible to estimate global popularity on a training set (akin to how ICF estimates item factors on a training set) and evaluate on a test set. This also seems very possible in a real-world setting (collect information on global popularity before deploying your recommendation system). I think a comparison with such a strategy is warranted.2. How were K=2 and 30 particles chosen? How does the algorithm scale and perform for larger K? Do you need many more particles to represent posteriors over larger-dimensional objects for these datasets?3. The authors acknowledge that ICF performance is sensitive to the amount of training data used. A plot showing how ICF performs against PTS/PTS-B as a function of training proportion would be helpful here. Some other minor points:1. It's mentioned that Thompson sampling is used to recommend the item, but in Algorithm 1, the item chosen to be recommended is simply \argmax_j \tilde{U}_i^T\tilde{V}_j. Is the ``sampling'' part simply coming from the sampling of \tilde{U} and \tilde{V} using the particles?2. The method performs slightly worse in an offline setting than standard PMF (0.7925 vs. 0.7718) - is there an explanation for why?3. The following citable work (obtained via google search of 'matrix completion bandit problem') seems very relevant, yet is not cited:Linear Bandits, Matrix Completion, and Recommendation Systems. Madeleine Udell and Reza Takapoui. NIPS Workshop on Large Scale Matrix Analysis and Inference, 2014.