Contextual Bandits with Delayed Feedback and Semi-supervised Learning (Student Abstract)

Luting Yang, Jianyi Yang, Shaolei Ren

Abstract

In contextual multi-armed bandit (MAB) problems, agents typically expect immediate feedback to refine their decision-making policies. However, real-world applications such as personalized advertising or clinical trials often involve significant delays in reward reporting. This paper proposes a novel framework that treats pending rounds as unlabeled data within a semi-supervised learning (SSL) paradigm. By generating "pseudo-rewards" for these delayed rounds, we introduce two robust algorithms—MinMax and MinAvg—designed to stabilize reward estimation and minimize cumulative regret in delayed-feedback environments.

Introduction

The standard contextual MAB model assumes that the reward for an action is observed before the next context is presented. In practice, delays are common; for instance, a user might click an ad but not complete a purchase for several days. During this interval, the agent must continue to make decisions. Traditional approaches often ignore these pending rounds, relying solely on historical "labeled" data. This neglect leads to inaccurate reward models and increased regret.

To address this, we propose leveraging the contexts of pending rounds. By viewing these as unlabeled data, we can apply semi-supervised learning techniques to improve the agent's underlying reward model even before the true feedback arrives.

Methodology

Our approach utilizes Kernel Ridge Regression to model non-linear reward functions. The core innovation lies in how we handle the uncertainty of pending rewards through the following steps:

  1. Primary Estimation: We construct an initial reward model using the feedback already received.
  2. Uncertainty Bounds: For each pending round, we calculate an "ambiguous range"—a confidence interval representing the likely values of the missing reward.
  3. Semi-supervised Learning (SSL): We generate "pseudo-rewards" within the calculated uncertainty bounds. This allows the model to incorporate the structure of the context space from pending rounds, effectively stabilizing the learning process.
  4. Robust Selection Policies: We integrate these pseudo-rewards into a Contextual Upper Confidence Bound (UCB) framework using two specific policies:
  5. MinMax: A conservative approach that minimizes the maximum possible estimation error, preparing for the worst-case scenario within the uncertainty range.
  6. MinAvg: A balanced approach that minimizes the average estimation error across multiple samples of potential rewards.
Algorithm 1: Contextual Bandit with Delayed Feedback using MinMax and MinAvg policies.

Key Insights

The primary contribution of this work is the conceptual shift of viewing pending contexts as unlabeled data. By borrowing from SSL techniques used in fields like image classification, we can "label" pending rounds with fictitious rewards. This helps maintain a more robust model of the environment. Furthermore, since the MinMax optimization can be computationally intensive, the proposed framework suggests a sampling-based approximation to maintain efficiency as the number of delayed rounds grows.

Conclusion and Future Work

This research provides a theoretical foundation for integrating semi-supervised learning into contextual bandits with delayed feedback. While the current work focuses on the mathematical formulation of the MinMax and MinAvg algorithms, future research will focus on deriving formal regret bounds and conducting empirical evaluations against standard UCB variants. These experiments will be crucial in quantifying the performance gains of SSL-based bandit algorithms in high-delay scenarios.

Summary updated

Abstract

Contextual multi-armed bandit (MAB) is a classic online learning problem, where a learner/agent selects actions (i.e., arms) given contextual information and discovers optimal actions based on reward feedback. Applications of contextual bandit have been increasingly expanding, including advertisement, personalization, resource allocation in wireless networks, among others. Nonetheless, the reward feedback is delayed in many applications (e.g., a user may only provide service ratings after a period of time), creating challenges for contextual bandits. In this paper, we address delayed feedback in contextual bandits by using semi-supervised learning — incorporate estimates of delayed rewards to improve the estimation of future rewards. Concretely, the reward feedback for an arm selected at the beginning of a round is only observed by the agent/learner with some observation noise and provided to the agent after some a priori unknown but bounded delays. Motivated by semi-supervised learning that produces pseudo labels for unlabeled data to further improve the model performance, we generate fictitious estimates of rewards that are delayed and have yet to arrive based on already-learnt reward functions. Thus, by combining semi-supervised learning with online contextual bandit learning, we propose a novel extension and design two algorithms, which estimate the values for currently unavailable reward feedbacks to minimize the maximum estimation error and average estimation error, respectively.
BibTeX
@inproceedings{yang2021contextual,
  author = {Luting Yang and Jianyi Yang and Shaolei Ren},
  title = {{Contextual Bandits with Delayed Feedback and Semi-supervised Learning (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.17968},
}
Figure