Impatient Bandits: Optimizing for the Long-Term Without Delay

• URL: http://arxiv.org/abs/2501.07761v1
• Date: Tue, 14 Jan 2025 00:28:26 GMT
• Title: Impatient Bandits: Optimizing for the Long-Term Without Delay
• Abstract summary: We study a content exploration task, which we formalize as a bandit problem with delayed rewards.<n>We develop a predictive model of delayed rewards that incorporates all information obtained to date.<n>We devise a bandit algorithm that quickly learns to identify content aligned with long-term success.
• Score: 20.753692240620644
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Short-Term Pain for Long-Term Gain: Adaptive Experiment with Post-Commitment Reward Shift [7.0306572851625]
  Decision-makers in learning environments face a dilemma when their short-term optimal actions may not favor their long-term benefits the most.<n>To understand the tradeoff behind the dilemma, we study adaptive experimentation with post-commitment reward shifts.
  arXiv  Detail & Related papers  (2026-07-26T03:03:08Z)
• Long-term User Engagement Optimization through Model-agnostic Downstream Rewards Learning [2.66348673166416]
  We present a unified, model-agnostic downstream reward framework for optimizing long-term user value in large-scale recommendation systems.<n>We propose several model-agnostic downstream rewards signals derived from observed user action patterns across multiple sources.<n>Online A/B experiments demonstrate consistent improvements in engagement and retention-related metrics.
  arXiv  Detail & Related papers  (2026-07-15T16:17:58Z)
• LatSearch: Latent Reward-Guided Search for Faster Inference-Time Scaling in Video Diffusion [87.42285185305813]
  We introduce a novel inference-time search mechanism that performs Reward-Guided Resampling and Pruning.<n>LatSearch consistently improves video generation across multiple evaluation dimensions compared to the baseline Wan2.1 model.
  arXiv  Detail & Related papers  (2026-03-15T18:07:29Z)
• Retentive Relevance: Capturing Long-Term User Value in Recommendation Systems [29.596401271139797]
  We introduce Retentive Relevance, a novel content-level survey-based feedback measure.<n>Retentive Relevance directly assesses users' intent to return to the platform for similar content.<n>We show that Retentive Relevance significantly outperforms both engagement signals and other survey measures in predicting next-day retention.
  arXiv  Detail & Related papers  (2025-10-08T23:38:57Z)
• $\ exttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• Long-term Off-Policy Evaluation and Learning [21.047613223586794]
  Short- and long-term outcomes of an algorithm often differ, with damaging downstream effects. It takes months or even longer to observe the long-term outcomes of interest, making the algorithm selection process unacceptably slow. We propose a new framework called Long-term Off-Policy Evaluation (LOPE), which is based on reward function decomposition.
  arXiv  Detail & Related papers  (2024-04-24T06:59:59Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the instantaneous reward before observing it.
  arXiv  Detail & Related papers  (2024-02-23T06:27:12Z)
• Are We Wasting Time? A Fast, Accurate Performance Evaluation Framework for Knowledge Graph Link Predictors [4.31947784387967]
  In Knowledge Graphs on a larger scale, the ranking process rapidly becomes heavy. Previous approaches used random sampling of entities to assess the quality of links predicted or suggested by a method. We show that this approach has serious limitations since the ranking metrics produced do not properly reflect true outcomes. We propose a framework that uses relational recommenders to guide the selection of candidates for evaluation.
  arXiv  Detail & Related papers  (2024-01-25T15:44:46Z)
• Accelerating Exploration with Unlabeled Prior Data [66.43995032226466]
  We study how prior data without reward labels may be used to guide and accelerate exploration for an agent solving a new sparse reward task. We propose a simple approach that learns a reward model from online experience, labels the unlabeled prior data with optimistic rewards, and then uses it concurrently alongside the online data for downstream policy and critic optimization.
  arXiv  Detail & Related papers  (2023-11-09T00:05:17Z)
• STARC: A General Framework For Quantifying Differences Between Reward Functions [52.69620361363209]
  We provide a class of pseudometrics on the space of all reward functions that we call STARC metrics.<n>We show that STARC metrics induce both an upper and a lower bound on worst-case regret.<n>We also identify a number of issues with reward metrics proposed by earlier works.
  arXiv  Detail & Related papers  (2023-09-26T20:31:19Z)
• Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delay [29.23091752603817]
  We study a content exploration task, which we formalize as a multi-armed bandit problem with delayed rewards. We develop a predictive model of delayed rewards that incorporates all information obtained to date. We apply our approach to a podcast recommendation problem, where we seek to identify shows that users engage with repeatedly over two months.
  arXiv  Detail & Related papers  (2023-07-19T12:35:16Z)
• Optimizing Audio Recommendations for the Long-Term: A Reinforcement Learning Perspective [11.31980071390936]
  We present a novel podcast recommender system deployed at industrial scale. In deviating from the pervasive industry practice of optimizing machine learning algorithms for short-term proxy metrics, the system substantially improves long-term performance in A/B tests.
  arXiv  Detail & Related papers  (2023-02-07T16:17:25Z)
• ZigZag: Universal Sampling-free Uncertainty Estimation Through Two-Step Inference [54.17205151960878]
  We introduce a sampling-free approach that is generic and easy to deploy. We produce reliable uncertainty estimates on par with state-of-the-art methods at a significantly lower computational cost.
  arXiv  Detail & Related papers  (2022-11-21T13:23:09Z)
• SURF: Semi-supervised Reward Learning with Data Augmentation for Feedback-efficient Preference-based Reinforcement Learning [168.89470249446023]
  We present SURF, a semi-supervised reward learning framework that utilizes a large amount of unlabeled samples with data augmentation. In order to leverage unlabeled samples for reward learning, we infer pseudo-labels of the unlabeled samples based on the confidence of the preference predictor. Our experiments demonstrate that our approach significantly improves the feedback-efficiency of the preference-based method on a variety of locomotion and robotic manipulation tasks.
  arXiv  Detail & Related papers  (2022-03-18T16:50:38Z)
• Learning Long-Term Reward Redistribution via Randomized Return Decomposition [18.47810850195995]
  We consider the problem formulation of episodic reinforcement learning with trajectory feedback. It refers to an extreme delay of reward signals, in which the agent can only obtain one reward signal at the end of each trajectory. We propose a novel reward redistribution algorithm, randomized return decomposition (RRD), to learn a proxy reward function for episodic reinforcement learning.
  arXiv  Detail & Related papers  (2021-11-26T13:23:36Z)
• Learning Guidance Rewards with Trajectory-space Smoothing [22.456737935789103]
  Long-term temporal credit assignment is an important challenge in deep reinforcement learning. Existing policy-gradient and Q-learning algorithms rely on dense environmental rewards that provide rich short-term supervision. Recent works have proposed algorithms to learn dense "guidance" rewards that could be used in place of the sparse or delayed environmental rewards.
  arXiv  Detail & Related papers  (2020-10-23T23:55:06Z)
• Sequential Recommender via Time-aware Attentive Memory Network [67.26862011527986]
  We propose a temporal gating methodology to improve attention mechanism and recurrent units. We also propose a Multi-hop Time-aware Attentive Memory network to integrate long-term and short-term preferences. Our approach is scalable for candidate retrieval tasks and can be viewed as a non-linear generalization of latent factorization for dot-product based Top-K recommendation.
  arXiv  Detail & Related papers  (2020-05-18T11:29:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.