Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering

There are two main approaches taken in recommendation systems: content filtering and collaborative filtering. Content filtering makes use of features associated with items and users (e.g., age, location, gender of users and genre, director of movies). In contrast, collaborative filtering is based on observed user preferences. Thus, two users are thought of as similar if they have revealed similar preferences irrespective of their profile. Likewise, two items are thought of as similar if most users have similar preferences for them. More generally, collaborative filtering (CF) makes use of structure in the matrix of preferences, as in low-rank matrix formulations [1, 4, 8, 13, 14, 19, 20, 25]. An important aspect of most recommendation systems is that each recommendation influences what is learned about the users and items, which in turn determines the possible accuracy of future recommendations. This introduces a tension between exploring to obtain information and exploiting existing knowledge to make good recommendations. The tension between exploring and exploiting is exactly the phenomenon of interest in the substantial literature on the multi-armed bandit (MAB) problem and its variants [7, 16, 21].