Efficient online recommendation via low-rank ensemble sampling

ABSTRACT

The low-rank structure is one of the most prominent features in modern recommendation problems. In this paper, we consider an online learning problem with a low-rank expected reward matrix where both row features and column features are unknown a priori, and the agent aims to learn to choose the best row-column pair (i.e. the maximum entry) in the matrix. We develop a novel online recommendation algorithm based on ensemble sampling, a recently developed computationally efficient approximation of Thompson sampling. Our computational results show that our algorithm consistently achieves order-of-magnitude improvements over the baselines in both synthetic and real-world experiments.

References

1. S. Agrawal and N. Goyal. 2013. Thompson Sampling for Contextual Bandits with Linear Payoffs. In Proceedings of The 30th International Conference on Machine Learning. 127--135.
2. Samuel Burer and Renato D.C. Monteiro. 2005. Local Minima and Convergence in Low-Rank Semidefinite Programming. Mathematical Programming 103, 3 (01 Jul 2005), 427--444.
3. Emmanuel J. Candès and Benjamin Recht. 2009. Exact Matrix Completion via Convex Optimization. Foundations of Computational Mathematics 9, 6 (03 Apr 2009), 717.
4. Olivier Chapelle and Lihong Li. 2011. An Empirical Evaluation of Thompson Sampling. In Advances in Neural Information Processing Systems 24. 2249--2257.
5. M. A. Davenport and J. Romberg. 2016. An Overview of Low-Rank Matrix Recovery From Incomplete Observations. IEEE Journal of Selected Topics in Signal Processing 10, 4 (June 2016), 608--622.
6. D. Gross. 2011. Recovering Low-Rank Matrices From Few Coefficients in Any Basis. IEEE Trans. Inf. Theor. 57, 3 (March 2011), 1548--1566.
7. F. Maxwell Harper and Joseph A. Konstan. 2015. The Movie Lens Datasets: History and Context. ACM Trans. Interact. Intell. Syst. 5, 4, Article 19 (Dec. 2015), 19 pages.
8. Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. 2013. Low-rank Matrix Completion Using Alternating Minimization. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (STOC '13). ACM, New York, NY, USA, 665--674.
9. Dietmar Jannach, Markus Zanker, Alexander Felfernig, and Gerhard Friedrich. 2010. Recommender Systems: An Introduction (1st ed.). Cambridge University Press, New York, NY, USA.
10. Sumeet Katariya, Branislav Kveton, Csaba Szepesvári, Claire Vernade, and Zheng Wen. 2017. Bernoulli Rank-1 Bandits for Click Feedback. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19--25, 2017. 2001--2007.
11. Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, and Zheng Wen. 2017. Stochastic Rank-1 Bandits. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. PMLR, Fort Lauderdale, FL, USA.
12. Jaya Kawale, Hung H Bui, Branislav Kveton, Long Tran-Thanh, and Sanjay Chawla. 2015. Efficient Thompson Sampling for Online Matrix-Factorization Recommendation. In Advances in Neural Information Processing Systems 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (Eds.). Curran Associates, Inc., 1297--1305.
13. R. H. Keshavan, A. Montanari, and S. Oh. 2010. Matrix Completion From a Few Entries. IEEE Transactions on Information Theory 56, 6 (June 2010), 2980--2998.
14. Branislav Kveton, Csaba Szepesvári, Anup Rao, Zheng Wen, Yasin Abbasi-Yadkori, and S. Muthukrishnan. 2017. Stochastic Low-Rank Bandits. CoRR abs/1712.04644 (2017). http://arxiv.org/abs/1712.04644
15. Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. 2016. Collaborative Filtering Bandits. In Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '16). ACM, New York, NY, USA, 539--548.
16. Xiuyuan Lu and Benjamin Van Roy. 2017. Ensemble Sampling. In Advances in Neural Information Processing Systems 30, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 3258--3266.
17. Andriy Mnih and Ruslan R Salakhutdinov. 2008. Probabilistic Matrix Factorization. In Advances in Neural Information Processing Systems 20, J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis (Eds.). Curran Associates, Inc., 1257--1264.
18. Benjamin Recht and Christopher Ré. 2013. Parallel stochastic gradient algorithms for large-scale matrix completion. Mathematical Programming Computation 5, 2 (01 Jun 2013), 201--226.
19. Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. 2018. A Tutorial on Thompson Sampling. CoRR (2018).
20. D. Russo and B. Van Roy. 2014. Learning to optimize via posterior sampling. Mathematics of Operations Research 39, 4 (2014), 1221--1243.
21. Daniel Russo and Benjamin Van Roy. 2016. An Information-theoretic Analysis of Thompson Sampling. J. Mach. Learn. Res. 17, 1 (Jan. 2016), 2442--2471.
22. Ruslan Salakhutdinov and Andriy Mnih. 2008. Bayesian Probabilistic Matrix Factorization Using Markov Chain Monte Carlo. In Proceedings of the 25th International Conference on Machine Learning (ICML '08). ACM, New York, NY, USA, 880--887.
23. Rajat Sen, Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sanjay Shakkottai. 2016. Latent Contextual Bandits: A Non-Negative Matrix Factorization Approach. CoRR abs/1606.00119 (2016).
24. Xiaoxue Zhao, Weinan Zhang, and Jun Wang. 2013. Interactive Collaborative Filtering. In Proceedings of the 22Nd ACM International Conference on Information & Knowledge Management (CIKM '13). 1411--1420.