Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles

Jung-Hun Kim, Se-Young Yun, Minchan Jeong, Junhyun Nam, Jinwoo Shin, Richard CombesAISTATS 2023 · OpenReview

Abstract: We study contextual linear bandit problems under feature uncertainty; they are noisy with missing entries. To address the challenges of the noise, we analyze Bayesian oracles given observed noisy features and propose a novel algorithm, CLBBF (Contextual Linear Bandits on Bayesian Features). Our approach estimates underlying feature distributions to approximate a Bayesian Oracle, achieving near-optimal regret and significantly outperforming standard methods in noisy real-world scenarios.

Introduction

In the standard contextual linear bandit problem, an agent chooses an "arm" (e.g., a product recommendation) based on a set of features or context. Most existing research assumes these features are perfectly accurate. However, real-world data is often corrupted by measurement noise, missing entries due to communication failures, or intentional noise added for privacy (e.g., differential privacy).

When features are noisy, the fundamental assumption of "realizability"—that the reward is a simple linear function of the observed features—breaks down. Standard algorithms like LinUCB or OFUL assume observed data is ground truth, leading to sub-optimal decisions and poor regret (the performance gap between the agent and the best possible strategy).

Methodology: The Bayesian Oracle Approach

The authors bridge the gap between noisy observations and optimal decision-making by defining a Bayesian Oracle. This oracle knows the true latent parameters but only observes noisy features. The optimal strategy for this oracle is to act based on the conditional expectation of the true feature given the noisy observation.

Geometric interpretation of the Bayesian Oracle and feature noise.

The proposed CLBBF algorithm implements this by:

  1. Parameter Estimation: Estimating the mean, covariance, and missingness probability of features on the fly using all observed arms.
  2. Bayesian Feature Mapping: Transforming noisy, incomplete vectors into "Bayesian features"—the best statistical estimate of the true feature.
  3. Optimism in the Face of Uncertainty: Applying a modified OFUL strategy to these transformed features to manage the exploration-exploitation trade-off.

To address computational costs, the authors also introduced E-CLBBF, which utilizes an explicit exploration phase to reduce the frequency of feature estimate updates.

Experimental Evaluation

The approach was evaluated on both synthetic and real-world datasets:

  • Synthetic Datasets: Controlled environments with Gaussian noise and up to 40% missing data.
  • Real-World Datasets: Avazu CTR (mobile ads), Taobao.com (e-commerce logs), and MovieLens 100K. For these, autoencoders were used to compress features before introducing artificial noise and missingness to simulate difficult conditions.

Key Results and Insights

A critical discovery of this work is that the optimal hypothesis in a noisy setting can be significantly different from the underlying "true" linear function. While the relationship between noisy features and rewards is non-linear, the reward remains linear with respect to the Bayesian-estimated features. This allows the use of powerful linear bandit tools in what initially appears to be a non-linear problem.

Performance comparison between CLBBF (Algorithm 1) and OFUL across synthetic and real-world datasets.

As shown in the experimental results, CLBBF consistently outperforms standard OFUL:

  • Theoretical Guarantees: CLBBF achieves a regret bound of $\tilde{O}(d\sqrt{T})$ when the number of arms is large, matching the performance of standard algorithms in noiseless settings.
  • Robustness: While OFUL's performance degrades rapidly as missing data increases, CLBBF remains stable.
  • The Power of Many Arms: Interestingly, a large number of arms ($K$) helps the agent estimate global noise and feature distributions faster than it learns reward parameters.

Conclusion and Future Work

While CLBBF demonstrates significant improvements, it currently relies on Gaussian assumptions for features and noise, which may not cover categorical or heavy-tailed data. Future work includes exploring non-Gaussian frameworks and establishing theoretical regret lower bounds for this specific noisy Bayesian setting. Despite these limitations, CLBBF provides a robust framework for deploying bandit algorithms in messy, real-world data environments.

Summary updated

Abstract

We study contextual linear bandit problems under feature uncertainty; they are noisy with missing entries. To address the challenges of the noise, we analyze Bayesian oracles given observed noisy f...
BibTeX
@inproceedings{kim2023contextual,
  author = {Jung-Hun Kim and Se-Young Yun and Minchan Jeong and Junhyun Nam and Jinwoo Shin and Richard Combes},
  title = {{Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=7htkyGlFy2},
}
Figure