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

We consider an online model for recommendation systems, with each user being\nrecommended an item at each time-step and providing 'like' or 'dislike'\nfeedback. Each user may be recommended a given item at most once. A latent\nvariable model specifies the user preferences: both users and items are\nclustered into types. All users of a given type have identical preferences for\nthe items, and similarly, items of a given type are either all liked or all\ndisliked by a given user. We assume that the matrix encoding the preferences of\neach user type for each item type is randomly generated; in this way, the model\ncaptures structure in both the item and user spaces, the amount of structure\ndepending on the number of each of the types. The measure of performance of the\nrecommendation system is the expected number of disliked recommendations per\nuser, defined as expected regret. We propose two algorithms inspired by\nuser-user and item-item collaborative filtering (CF), modified to explicitly\nmake exploratory recommendations, and prove performance guarantees in terms of\ntheir expected regret. For two regimes of model parameters, with structure only\nin item space or only in user space, we prove information-theoretic lower\nbounds on regret that match our upper bounds up to logarithmic factors. Our\nanalysis elucidates system operating regimes in which existing CF algorithms\nare nearly optimal.\n