Budgeted Recommendation with Delayed Feedback

Kweiguu Liu, Setareh Maghsudi, Makoto YokooWorldCIST 2024

Abstract

This paper introduces DORAL (Delay-Oriented Resource Allocation with Learning), a novel framework for contextual multi-armed bandits (MAB) that addresses the simultaneous challenges of limited budgets and delayed feedback. In many real-world applications, such as medical resource distribution or digital advertising, rewards are not immediate, and every action incurs a cost against a finite budget. Traditional bandit algorithms often suffer from over-exploration in these settings, wasting resources on suboptimal arms before their performance is fully realized. DORAL mitigates this through a two-stage approach: first identifying "responsive" arms using a robust median-of-means estimator, and then optimizing resource allocation via a delay-aware linear program. Experimental results on synthetic datasets with heavy-tailed delays demonstrate that DORAL significantly outperforms existing benchmarks in long-term regret and resource efficiency.

Introduction

In the standard contextual multi-armed bandit (MAB) paradigm, an agent observes a context, selects an action (an arm), and receives an immediate reward. However, practical deployments frequently encounter two significant hurdles: delayed feedback and limited resources. For instance, in clinical trials, the efficacy of a treatment may not be known for weeks, yet the supply of medication is finite.

When these factors coincide, they create a "double whammy" effect. Delayed feedback leads to over-exploration, as the agent continues to pull arms without knowing their true utility. Under a strict budget, this over-exploration is catastrophic; precious resources are exhausted on slow-to-respond or suboptimal arms before the agent can adapt its strategy. This paper proposes DORAL to navigate this trade-off by prioritizing "responsiveness" alongside reward.

Methodology

The DORAL framework operates in two distinct stages to ensure that the learning process does not deplete the budget prematurely.

Stage 1: Identifying Responsive Arms (PR-SAR)

The first stage utilizes a fraction of the budget to filter the available arms. The authors introduce Patient-Racing Successive Acceptance and Rejection (PR-SAR). To handle the challenges of "heavy-tailed" delays—where most feedback is quick but some observations take an exceptionally long time—DORAL employs a Median-of-Means Estimator. Instead of a simple average, observations are divided into subsets; the mean of each subset is calculated, and the median of these means is used as the robust estimate. This prevents outliers from skewing the agent's understanding of an arm's delay profile. This stage effectively prunes arms that are too slow to provide actionable data within the required timeframe.

Stage 2: Delay-Oriented Resource Allocation

Once a set of responsive arms is identified, the agent enters the exploitation phase. This stage introduces two critical components:

  1. Cut-off Parameter ($m$): The agent establishes a time window $m$. Feedback that arrives after this window is ignored. This prevents the system from incurring infinite storage overhead and allows for more predictable updates.
  2. Delay-Oriented Linear Programming ($LP_m$): At each step, the agent solves a linear program to determine the optimal arm to pull. Unlike standard LPs that only maximize expected reward, $LP_m$ weights rewards by the probability that feedback will return within the budget and time horizon. This ensures that the agent favors arms that are likely to contribute to the learning objective before the budget is exhausted.

Experimental Evaluation

Dataset and Configuration

Due to the scarcity of public datasets containing both contextual features and specific arm-dependent delay distributions, the authors evaluated DORAL using a synthetic environment. The simulation featured 10 context classes, 10 arms with unit costs, and 5 features per arm/context. To simulate realistic delay scenarios, the authors utilized Geometric and Pareto distributions. Pareto distributions are particularly relevant as they model heavy-tailed scenarios common in real-world systems. The simulations were conducted over 50,000 rounds with a total budget of 85,000.

Results

DORAL was compared against several benchmarks, including Delayed-LinUCB and Delayed Adaptive Linear Programming (D-ALP).

  • Long-term Regret: While DORAL initially shows higher regret due to the exploration-heavy nature of the PR-SAR stage, it eventually overtakes all benchmarks. By the end of the time horizon, its cumulative reward is significantly higher because it avoids the "exploration trap" of slow arms.
  • Robustness: In scenarios with heavy-tailed Pareto delays, DORAL's median-of-means approach proved superior to D-ALP, which struggled to filter out unreliable, slow-responding arms.
  • Efficiency: When arms exhibited diverse delay characteristics, DORAL’s ability to prioritize responsiveness allowed it to optimize the budget more effectively than greedy methods that ignore the temporal cost of feedback.

Discussion and Insights

The core contribution of this work is the conceptualization of responsiveness as a metric. In a budgeted environment, an arm's value is not merely its expected reward, but its "reward-per-unit-of-time-to-learn." An arm with a high reward that takes a year to report back may be less valuable than a medium-reward arm that reports back instantly, as the latter allows the model to update and improve its future decisions more quickly.

Furthermore, the paper demonstrates that the "waiting" strategy—holding out indefinitely for feedback—is often inferior to a "cut-off" strategy when resources are limited. Cutting off late feedback allows the agent to maintain a higher velocity of learning, which is critical when the budget is ticking away.

Conclusion and Future Work

DORAL provides a robust solution for recommendation problems where time and resources are both at a premium. By separating the identification of responsive arms from the allocation process, it prevents the premature exhaustion of budgets.

Future research directions include moving beyond arm-dependent delays to context-dependent delays, where the feedback time might vary based on the specific user profile. Additionally, the authors suggest exploring dynamic cut-off parameters that can adjust on the fly as the agent learns more about the environment, rather than relying on a fixed parameter determined after the first stage.

Summary updated

BibTeX
@inproceedings{liu2024budgeted,
  author = {Kweiguu Liu and Setareh Maghsudi and Makoto Yokoo},
  title = {{Budgeted Recommendation with Delayed Feedback}},
  booktitle = {WorldCIST},
  year = {2024},
}
Figure