Corrupted Contextual Bandits: Online Learning with Corrupted Context

Djallel BouneffoufICASSP 2021 · OpenReview

Introduction

In real-world machine learning applications, data reliability is rarely guaranteed. While standard Contextual Multi-Armed Bandit (CMAB) algorithms excel in environments with clean side-information, they often falter when faced with "corrupted" context—instances where the provided features are disconnected from the underlying state. This paper addresses the challenge of "useless context," where side-information intermittently becomes complete noise, potentially leading standard models to "unlearn" optimal strategies.

The Corrupted Contextual Bandit (CBCC) Problem

The core issue is the reliability of the context vector. In a standard contextual bandit setting, an agent observes a context, selects an action, and receives a reward, learning a mapping between the two. However, if the context is corrupted—meaning it holds no relationship to the actual environment—the agent's model becomes biased.

Unlike previous work focusing on "noisy" context (small random perturbations) or corrupted rewards, this research investigates a binary state: context is either "ground truth" or "useless noise." The agent must make decisions without knowing the current state of context validity.

Methods: The TSCC Algorithm

The authors propose Contextual Thompson Sampling with Corrupted Context (TSCC). The algorithm employs a hierarchical architecture designed to dynamically balance contextual and non-contextual learning:

  1. Meta-Bandit Layer: Maintains a belief about a parameter $\alpha$, which determines whether to prioritize the contextual model or a fallback strategy.
  2. Contextual Model: Utilizes standard Contextual Thompson Sampling (CTS) to model linear relationships between features and rewards.
  3. Fallback Model: A classic Multi-Armed Bandit (MAB) that ignores context, tracking the average performance of arms.
  4. Integration: At each step, the algorithm samples from both models. If the contextual model's performance degrades due to corruption, the meta-bandit shifts weight to the fallback model. Crucially, both models are updated after every interaction, ensuring the agent learns general arm performance even when specific context is unreliable.

Experimental Setup

The researchers evaluated TSCC using four diverse datasets from the UCI Machine Learning Repository, adapted into bandit problems.

Table 1: Summary of UCI datasets used in the study.

To simulate corrupted environments, context features were replaced with random values at frequencies ranging from 5% to 95%.

Key Results

The proposed TSCC algorithm consistently outperformed standard baselines across all datasets and corruption levels.

Figure 1: Performance comparison of TSCC against baselines at 25%, 50%, and 95% corruption levels.
  • Robustness: In the Covertype dataset, TSCC achieved a misclassification error rate of 63.44%, compared to 65.54% for standard CMAB.
  • Adaptability: Analysis shows that TSCC effectively pivots its strategy based on corruption levels. At 25% corruption, it leverages context heavily; at 95% corruption, it successfully mimics a simpler, more reliable MAB strategy.
  • Theoretical Performance: The authors proved that TSCC's regret bound effectively bridges the gap between contextual and non-contextual bandits, matching the efficiency of the optimal strategy for the given noise level.

Conclusion

The TSCC algorithm provides a robust framework for sequential decision-making in unreliable environments. By maintaining parallel contextual and non-contextual models, it avoids the pitfalls of "unlearning" during periods of high data corruption. Future work may explore non-stationary corruption probabilities and methods for detecting anomalous context vectors directly.

Summary updated

Abstract

We consider a novel variant of the contextual bandit problem (i.e., the multi-armed bandit with side-information, or context, available to a decision-maker) where the context used at each decision may be corrupted ("useless context"). This new problem is motivated by certain on-line settings including clinical trial and ad recommendation applications. In order to address the corrupted-context setting, we propose to combine the standard contextual bandit approach with a classical multi-armed bandit mechanism. Unlike standard contextual bandit methods, we are able to learn from all iteration, even those with corrupted context, by improving the computing of the expectation for each arm. Promising empirical results are obtained on several real-life datasets.
BibTeX
@inproceedings{bouneffouf2021corrupted,
  author = {Djallel Bouneffouf},
  title = {{Corrupted Contextual Bandits: Online Learning with Corrupted Context}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=nT7ohp6BRTt},
}

Loading related content...

Figure