Optimal Sequential Recommendations: Exploiting User and Item Structure
This addresses the challenge of improving recommendation accuracy in systems with user feedback, though it appears incremental by combining existing structures.
The paper tackles the problem of online sequential recommendations by developing an algorithm that exploits both user and item clustering structures, proving it to be near-optimal with information-theoretic lower bounds, and highlighting the sub-optimality of using only one structure as in most collaborative filtering methods.
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. A latent variable model specifies the user preferences: both users and items are clustered into types. The model captures structure in both the item and user spaces, as used by item-item and user-user collaborative filtering algorithms. We study the situation in which the type preference matrix has i.i.d. entries. Our main contribution is an algorithm that simultaneously uses both item and user structures, proved to be near-optimal via corresponding information-theoretic lower bounds. In particular, our analysis highlights the sub-optimality of using only one of item or user structure (as is done in most collaborative filtering algorithms).