A Markov Decision Process Analysis of the Cold Start Problem in Bayesian Information Filtering
This work addresses the cold-start challenge for users in information filtering systems, offering incremental improvements in exploration-exploitation trade-offs.
The paper tackles the cold-start problem in personalized information filtering by developing a Bayesian Markov decision process approach to efficiently compute optimal forwarding algorithms, achieving a 15% improvement in relevant items shown compared to baseline methods in simulations using arXiv.org data.
We consider the information filtering problem, in which we face a stream of items, and must decide which ones to forward to a user to maximize the number of relevant items shown, minus a penalty for each irrelevant item shown. Forwarding decisions are made separately in a personalized way for each user. We focus on the cold-start setting for this problem, in which we have limited historical data on the user's preferences, and must rely on feedback from forwarded articles to learn which the fraction of items relevant to the user in each of several item categories. Performing well in this setting requires trading exploration vs. exploitation, forwarding items that are likely to be irrelevant, to allow learning that will improve later performance. In a Bayesian setting, and using Markov decision processes, we show how the Bayes-optimal forwarding algorithm can be computed efficiently when the user will examine each forwarded article, and how an upper bound on the Bayes-optimal procedure and a heuristic index policy can be obtained for the setting when the user will examine only a limited number of forwarded items. We present results from simulation experiments using parameters estimated using historical data from arXiv.org.