Technical Summary: Impatient Bandits: Optimizing for the Long-Term Without Delay

1. Problem Formulation

The paper addresses a critical challenge in large-scale recommender systems: optimizing for long-term user satisfaction (e.g., sustained engagement over 60 days) while mitigating the severe delays inherent in observing such rewards. In standard multi-armed bandit (MAB) settings, algorithms assume immediate feedback. However, in real-world platforms like Spotify, the true reward (long-term engagement) is only observable after a significant delay (e.g., $d_{max} = 60$ days).

Waiting for full rewards to materialize before updating policies leads to a "cold-start" problem where new content cannot be effectively evaluated, and learning rates are prohibitively slow. Conversely, optimizing for short-term proxies (e.g., immediate clicks) often misaligns with long-term goals.

The authors formalize this as a Bandit problem with Progressive Feedback. Unlike standard delayed feedback where no information is available until the delay expires, progressive feedback posits that long-term outcomes become increasingly predictable over time through a sequence of intermediate, correlated outcomes (e.g., daily listening activity). The core challenge is to leverage these intermediate signals to learn effectively before the final long-term reward is observed, without relying on the assumption that short-term signals are perfect surrogates.

2. Methodology

2.1 Model: Bandits with Progressive Feedback

The authors define a setting where:

• Actions: A finite set of items $\mathcal{A}$ are recommended to batches of users $U_t$ at each time step $t$.
• Outcomes: Selecting an item $a$ for user $u$ generates a vector of outcomes $Y_u = (Y_u^{(1)}, \dots, Y_u^{(J)})$, representing engagement metrics revealed progressively over $J$ days.
• Reward: The true reward $R(Y_u)$ is a known function of the full trajectory (e.g., total engagement over 60 days).
• Assumptions:
  • Exchangeability: Users receiving the same item have exchangeable potential outcomes conditional on item features.
  • Gaussian Process: Potential outcomes follow a multivariate Gaussian distribution. The latent parameter $\theta_a$ represents the item's true quality, and observed outcomes are noisy realizations of $\theta_a$.
  • Linear Reward: The reward function $R(\cdot)$ is affine, ensuring the expected reward is Gaussian.

2.2 Algorithm: Impatient Thompson Sampling

The proposed solution integrates Thompson Sampling with an (Empirical) Bayesian Filter.

1. Prior Learning: Using historical data, the system fits a prior distribution over the latent item quality parameters $\theta_a$ (specifically the mean $\mu_{1,z}$ and covariance $\Sigma_{1,z}$ conditioned on item features $z$). This is done via Type II Maximum Likelihood (Empirical Bayes).
2. Posterior Updates: As intermediate outcomes $Y_u^{(j)}$ are revealed, the algorithm updates the posterior distribution of $\theta_a$ using a Gaussian filter. This allows the system to maintain a probabilistic belief about the item's long-term value even when the final reward is unobserved.
3. Decision Making: At each step, the algorithm samples a candidate $\theta'_a$ from the current posterior for each item and selects the item maximizing the expected reward $R(\theta'_a)$.

A "Lower Variance" version of the algorithm is introduced for theoretical analysis, which rounds the sampling probabilities to ensure exact batch sizes, though empirical results show the standard version performs similarly.

2.3 Theoretical Framework: Value of Progressive Feedback (VoPF)

The paper introduces an information-theoretic metric, the Value of Progressive Feedback (VoPF), to quantify the utility of intermediate signals.

• Definition: VoPF is the conditional mutual information between the true long-term reward and the progressive (censored) outcomes, given the delayed outcomes.
• Significance: It measures how much uncertainty about the long-term reward is resolved by observing intermediate signals.
• Regret Bound: The authors derive a regret bound for their algorithm that scales with $\exp(-\text{VoPF})$.
  • If VoPF is zero (intermediate signals are uninformative), the bound reverts to the standard regret bound for delayed rewards.
  • If VoPF is high (signals are highly predictive), the regret decreases significantly, effectively allowing the algorithm to learn as if delays were shorter.

3. Key Contributions

1. Formalization of Progressive Feedback: The paper distinguishes "progressive feedback" (incrementally revealing, predictive signals) from standard "delayed feedback" or "perfect surrogates." It provides a rigorous model for this phenomenon in the context of recommender systems.
2. Novel Algorithm: It proposes an Impatient Bandit algorithm combining Thompson Sampling with Gaussian filtering to handle correlated, progressively revealed outcomes.
3. Theoretical Guarantees: It establishes a novel regret bound controlled by the VoPF metric, proving that the algorithm can achieve low regret in early batches even before long-term rewards are fully observed, provided the intermediate signals are informative.
4. Empirical Validation:
   • Synthetic Experiments: Demonstrated that the algorithm's performance qualitatively matches theoretical predictions across varying levels of signal informativeness.
   • Semi-Synthetic Experiments: Using Spotify podcast data, the algorithm significantly outperformed baselines (delayed-only and short-term proxy) in cumulative regret, particularly in cold-start scenarios.
   • A/B Test: A large-scale deployment on Spotify involving hundreds of millions of users.

4. Results

4.1 Synthetic and Semi-Synthetic Experiments

• Regret Reduction: In synthetic environments, the Impatient Bandit algorithm significantly reduced cumulative regret compared to a standard Thompson Sampling algorithm that ignores intermediate feedback. The improvement correlated directly with the VoPF.
• Cold Start: In semi-synthetic experiments using Spotify podcast data, the algorithm accumulated much less regret during the first 60 days (the delay period) compared to the delayed-reward baseline.
• Prior Importance: Experiments showed that using a learned prior (fitted on historical data) was crucial; an uninformative prior resulted in performance comparable to the delayed-reward baseline.
• Non-Stationarity: In a setting where the set of available items changed frequently (simulating continuous content release), the progressive feedback algorithm maintained low regret, whereas the delayed algorithm failed to adapt quickly.

4.2 A/B Test Results (Spotify)

The method was tested on a "Shows you might like" shelf in the Spotify mobile app, ranking podcast recommendations.

• Treatment vs. Control: The treatment policy used progressive feedback to estimate "stickiness" (long-term engagement) for new shows, while the control policy relied on delayed rewards (waiting 60 days for data).
• Impact on New Content: For recently released shows, the treatment policy increased the discovery rate by nearly 30% and improved 60-day active days per impression by over 50% compared to the control.
• Overall Impact: Across all shows, the treatment led to a 7% increase in 60-day active days and >10% increase in 60-day minutes per impression.
• Trade-offs: These long-term gains came with a slight, statistically significant decrease in short-term discovery rates (fewer immediate clicks), confirming the algorithm successfully shifted focus from short-term proxies to long-term value.
• Deployment: Based on these results, the method was rolled out to power personalized podcast recommendations for hundreds of millions of users.

5. Significance and Claims

The paper claims that its primary contribution is resolving the trade-off between learning speed and long-term alignment in recommender systems. By formalizing "progressive feedback," the authors demonstrate that it is possible to optimize for long-term goals without waiting for the full reward horizon, provided that intermediate signals are predictive.

The authors emphasize that their approach is distinct from existing surrogate outcome literature because:

1. It does not assume intermediate outcomes are perfect surrogates.
2. It handles a large number of continuous, sequentially revealed intermediate signals (e.g., >50 daily metrics) rather than a single binary outcome.
3. It explicitly models the uncertainty reduction over time via Bayesian filtering.

The work validates that leveraging progressive feedback can lead to substantial improvements in industrial-scale systems, specifically solving the cold-start problem for new content where historical long-term data is absent. The authors note that the success of the algorithm relies on the ability to learn an accurate prior from historical data, a practical requirement they address via Empirical Bayes fitting.