  Recommendation systems often use online collaborative filtering (CF)
algorithms to identify items a given user likes over time, based on ratings
that this user and a large number of other users have provided in the past.
This problem has been studied extensively when users' preferences do not change
over time (static case); an assumption that is often violated in practical
settings. In this paper, we introduce a novel model for online non-stationary
recommendation systems which allows for temporal uncertainties in the users'
preferences. For this model, we propose a user-based CF algorithm, and provide
a theoretical analysis of its achievable reward. Compared to related
non-stationary multi-armed bandit literature, the main fundamental difficulty
in our model lies in the fact that variations in the preferences of a certain
user may affect the recommendations for other users severely. We also test our
algorithm over real-world datasets, showing its effectiveness in real-world
applications. One of the main surprising observations in our experiments is the
fact our algorithm outperforms other static algorithms even when preferences do
not change over time. This hints toward the general conclusion that in
practice, dynamic algorithms, such as the one we propose, might be beneficial
even in stationary environments.
