Collaborative Filtering Bandits

ABSTRACT

Classical collaborative filtering, and content-based filtering methods try to learn a static recommendation model given training data. These approaches are far from ideal in highly dynamic recommendation domains such as news recommendation and computational advertisement, where the set of items and users is very fluid. In this work, we investigate an adaptive clustering technique for content recommendation based on exploration-exploitation strategies in contextual multi-armed bandit settings. Our algorithm takes into account the collaborative effects that arise due to the interaction of the users with the items, by dynamically grouping users based on the items under consideration and, at the same time, grouping items based on the similarity of the clusterings induced over the users. The resulting algorithm thus takes advantage of preference patterns in the data in a way akin to collaborative filtering methods. We provide an empirical analysis on medium-size real-world datasets, showing scalability and increased prediction performance (as measured by click-through rate) over state-of-the-art methods for clustering bandits. We also provide a regret analysis within a standard linear stochastic noise setting.

References

1. C. Gentile, S. Li, and G. Zappella. Online clustering of bandits. In ICML, 2014.
2. N. Korda, B. Szorenyi, and S. Li, Distributed Clustering of Linear Bandits in Peer to Peer Networks. In ICML, 2016.
3. Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. 2011.
4. J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration-exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876--1902, 2009.
5. P. Auer. Using confidence bounds for exploration-exploitation trade-offs. Journal of Machine Learning Research, 3:397--422, 2002.
6. P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 2001.
7. M. G. Azar, A. Lazaric, and E. Brunskill. Sequential transfer in multi-armed bandit with finite set of models. In NIPS, pages 2220--2228, 2013.
8. G. Bresler, G. Chen, and S. D. A latent source model for online collaborative filtering. In NIPS. MIT Press, 2014.
9. E. Brunskill and L. Li. Sample complexity of multi-task reinforcement learning. In UAI, 2013.
10. W. Cao, J. Li, Y. Tao, and Z. Li. On top-k selection in multi-armed bandits and hidden bipartite graphs. In NIPS, 2015.
11. G. Cavallanti, N. Cesa-Bianchi, and C. Gentile. Tracking the best hyperplane with a simple budget perceptron. Machine Learning, 69/2:143--167, 2007.
12. W. Chu, L. Li, L. Reyzin, and R. E. Schapire. Contextual bandits with linear payoff functions. In AISTATS, 2011.
13. K. Crammer and C. Gentile. Multiclass classification with bandit feedback using adaptive regularization. In ICML, 2011.
14. I. S. Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In 7th KDD, pages 269--274. ACM, 2001.
15. I. S. Dhillon, S. Mallela, and D. S. Modha. Information-theoretic co-clustering. In 9th KDD, pages 89--98, New York, NY, USA, 2003. ACM.
16. J. Djolonga, A. Krause, and V. Cevher. High-dimensional gaussian process bandits. In NIPS, pages 1025--1033, 2013.
17. M. Dudik, D. Erhan, J. Langford, and L. Li. Sample-efficient nonstationary-policy evaluation for contextual bandits. In UAI, 2012.
18. T. George and S. Merugu. A scalable collaborative filtering framework based on co-clustering. In 5th ICDM, pages 625--628. IEEE Computer Society, 2005.
19. F. Hao, S. Li, G. Min, H. Kim, S. Yau, and L. Yang,An Efficient Approach to Generating Location-Sensitive Recommendations in Ad-hoc Social Network Environments. IEEE Transactions on Services Computing, 8:3, pp. 520--533, 2015.
20. J. Kawale, H. Bui, B. Kveton, L. Thanh, and S. Chawla. Efficient thompson sampling for online matrix-factorization recommendation. In NIPS, 2015.
21. A. Krause and C. Ong. Contextual gaussian process bandit optimization. In 25th NIPS, 2011.
22. B. Kveton, C. Szepesvari, Z. Wen, and A. Ashkan. Cascading bandits: Learning to rank in the cascade model. In ICML, 2015.
23. L. Li, W. Chu, J. Langford, and R. Schapire. A contextual-bandit approach to personalized news article recommendation. In WWW, pages 661--670, 2010.
24. S. Li, F. Hao, M. Li, and H.C. Kim.Medicine Rating Prediction and Recommendation in Mobile Social Networks.In International Conference on Green, Pervasive and Cloud Computing, 2013.
25. L. Tang, Y. Jiang, L. Li, and T. Li. Ensemble contextual bandits for personalized recommendation. In RecSys, 2014.
26. S. Li, C. Gentile, and A. Karatzoglou. Graph clustering bandits for recommendation. arXiv:1605.00596.
27. O. Maillard and S. Mannor. Latent bandits. In ICML, 2014.
28. E. Moroshko, N. Vaits, and K. Crammer. Second-order non-stationary online learning for regression. Journal of Machine Learning Research, 16:1481--1517, 2015.
29. T. T. Nguyen and H. W. Lauw. Dynamic clustering of contextual multi-armed bandits. In 23rd CIKM, pages 1959--1962. ACM, 2014.
30. Y. Seldin, P. Auer, F. Laviolette, J. Shawe-Taylor, and R. Ortner. Pac-bayesian analysis of contextual bandits. In NIPS, pages 1683--1691, 2011.
31. I. Sutskever, R. Salakhutdinov, and J. Tenenbaum. Modelling relational data using bayesian clustered tensor factorization. In NIPS, pages 1821--1828. MIT Press, 2009.
32. L. Tang, Y. Jiang, L. Li, C. Zeng, and T. Li. Personalized recommendation via parameter-free contextual bandits. In SIGIR. ACM, 2015.
33. K. Verstrepen and B. Goethals. Unifying nearest neighbors collaborative filtering. In RecSys, 2014.
34. Y. Yue, S. A. Hong, and C. Guestrin. Hierarchical exploration for accelerating contextual bandits. In ICML, 2012.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning settings

      • Learning from implicit feedback

    • Machine learning approaches

      • Learning linear models

• Human-centered computing

  • Collaborative and social computing

    • Collaborative and social computing theory, concepts and paradigms

      • Collaborative filtering

      • Social recommendation

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Recommender systems

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

      • Online learning algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Online learning theory

      • Regret bounds

      • Unsupervised learning and clustering