Impatient Bandits: Optimizing for the Long-Term Without Delay
This work addresses the problem of balancing short-term and long-term rewards in recommender systems for large-scale applications like podcast recommendations, representing an incremental improvement over existing methods.
The paper tackles the challenge of optimizing for long-term user satisfaction in recommender systems by formalizing it as a bandit problem with delayed rewards, and it introduces a predictive model and algorithm that significantly outperform short-term proxy or delayed-only methods in a podcast recommendation A/B test serving hundreds of millions of users.
Increasingly, recommender systems are tasked with improving users' long-term satisfaction. In this context, we study a content exploration task, which we formalize as a bandit problem with delayed rewards. There is an apparent trade-off in choosing the learning signal: waiting for the full reward to become available might take several weeks, slowing the rate of learning, whereas using short-term proxy rewards reflects the actual long-term goal only imperfectly. First, we develop a predictive model of delayed rewards that incorporates all information obtained to date. Rewards as well as shorter-term surrogate outcomes are combined through a Bayesian filter to obtain a probabilistic belief. Second, we devise a bandit algorithm that quickly learns to identify content aligned with long-term success using this new predictive model. We prove a regret bound for our algorithm that depends on the \textit{Value of Progressive Feedback}, an information theoretic metric that captures the quality of short-term leading indicators that are observed prior to the long-term reward. We apply our approach to a podcast recommendation problem, where we seek to recommend shows that users engage with repeatedly over two months. We empirically validate that our approach significantly outperforms methods that optimize for short-term proxies or rely solely on delayed rewards, as demonstrated by an A/B test in a recommendation system that serves hundreds of millions of users.