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