Robust Pareto Set Identification with Contaminated Bandit Feedback

Kerem Bozgan, Cem Tekin

TL;DR

This paper introduces R-PSI, a robust algorithm for identifying the Pareto optimal set in multi-objective multi-armed bandits when reward observations are "contaminated" by an adversary. By swapping traditional mean estimators for sample medians, the authors provide a solution that remains accurate even under unbounded adversarial attacks, achieving sample complexity bounds that match state-of-the-art non-contaminated settings as the corruption probability vanishes.

What Problem Does This Paper Address?

In many real-world scenarios, we want to find the best "trade-offs" among multiple goals—like maximizing a movie's appeal across different age groups or balancing insulin efficacy against hypoglycemia risk. This is known as Pareto Set Identification (PSI).

However, standard algorithms assume the data we receive is "clean." In reality, feedback can be corrupted: "review bombers" might tank a product's rating, or sensors might malfunction. Most existing bandit algorithms rely on the mean reward, which is notoriously sensitive to outliers. If an adversary can inject even a few wildly incorrect values, they can completely mislead a mean-based algorithm. This paper tackles the challenge of finding the Pareto set when a fraction ($\epsilon$) of the observations are replaced by arbitrary, potentially malicious, values.

Methods

The authors propose the Robust Pareto Set Identification (R-PSI) algorithm. Its core innovations include:

  • Median-based Estimation: Instead of the mean, R-PSI uses the sample median, which is a robust statistic. The median can ignore extreme outliers as long as they don't make up more than half the data.
  • Handling Unavoidable Bias: Contamination introduces a fundamental bias ($D$) that no algorithm can fully overcome. R-PSI is designed to be $(\alpha, \delta)$-PAC, meaning it finds a set that is "close enough" (within $2D + \alpha$) to the true Pareto set with high probability.
  • Adaptive Elimination: The algorithm operates in phases. It maintains an "undecided" set of arms and a "predicted" Pareto set. In each phase, it samples arms to shrink confidence intervals and eliminates arms that are statistically guaranteed to be suboptimal.
  • Robust Confidence Bounds: The authors derive new confidence regions based on the "statistical bias" of the median, tailored to handle three types of adversaries: Oblivious (fixed strategy), Prescient (knows the future), and Malicious (can manipulate when contamination happens).

Datasets

The algorithm was evaluated on three distinct datasets to simulate different adversarial environments:

  1. MovieLens: Used to simulate "review bombing." The goal is to find movies that are Pareto optimal across five different age demographics.
  2. SW-LLVM: A dataset of 1023 compiler settings. The objectives are performance and memory footprint. This was used to test against a "malicious" adversary.
  3. UVA/PADOVA Diabetes Simulator: A high-fidelity simulator for blood glucose levels. The task is to identify optimal insulin dosing strategies despite "oblivious" errors in carbohydrate counting by patients.

Key Insights and Ideas

  • The Median as a Shield: The "aha moment" is the formal proof that the median's robustness properties in single-objective bandits can be mathematically extended to the complex geometry of Pareto fronts in multi-objective spaces.
  • The $2D$ Accuracy Limit: The paper highlights a "no-free-lunch" result: if an adversary can shift a sample by $D$, you can never distinguish arms within a $2D$ range of each other. R-PSI accepts this reality and optimizes for the best possible accuracy given that constraint.
  • Intricate Set Operations: Unlike single-objective bandits where you just keep the "best" arm, PSI requires carefully moving arms between "undecided," "O1" (potentially optimal), and "O2" (confirmed optimal) sets to ensure that no true Pareto arm is accidentally discarded due to noise.

Key Results

  • Theoretical Efficiency: R-PSI achieves a sample complexity of $O\left(\frac{K}{\alpha^2} \log \frac{MK}{\delta \alpha}\right)$. This is significant because it shows that robustness doesn't come with a massive "complexity tax"—the scaling is essentially the same as the best non-robust algorithms.
  • Empirical Superiority: In the MovieLens "review bombing" simulation, R-PSI maintained a 1.0 success rate (RSR) even with 40% contamination. In contrast, the standard mean-based algorithm (Auer-A1) saw its success rate drop to zero with as little as 5% contamination.
  • Reliability in Healthcare: On the Diabetes Simulator, R-PSI identified the correct treatment strategies with orders of magnitude fewer samples than a median-modified version of existing algorithms, proving it is not just robust, but also highly sample-efficient.

Limitations and Future Work

  • Large-Scale Scaling: The current approach might struggle with a very large number of arms or objectives where correlations between arms are significant. The authors suggest that capturing these correlations could further reduce sample complexity.
  • Skewed Distributions: The median and mean are only the same for symmetric distributions (like Gaussians). If the underlying reward distribution is highly skewed, R-PSI will find the "median-optimal" set, which might differ from what a user expecting "mean-optimal" results wants.
  • Future Direction: A promising next step is investigating how to handle "large-scale MO-MAB" problems where arms are not independent, perhaps by using Gaussian Processes or linear structures.

Summary updated

Abstract

We consider the Pareto set identification (PSI) problem in multi-objective multi-armed bandits (MO-MAB) with contaminated reward observations. At each arm pull, with some probability, the true reward samples are replaced with the samples from an arbitrary contamination distribution chosen by the adversary. We propose a median-based MO-MAB algorithm for robust PSI that abides by the accuracy requirements set by the user via an accuracy parameter. We prove that the sample complexity of this algorithm depends on the accuracy parameter inverse squarely. We compare the proposed algorithm with a mean-based method from MO-MAB literature on Gaussian reward distributions. Our numerical results verify our theoretical expectations and show the necessity for robust algorithm design in the adversarial setting.
BibTeX
@misc{bozgan2022robust,
  author = {Kerem Bozgan and Cem Tekin},
  title = {{Robust Pareto Set Identification with Contaminated Bandit Feedback}},
  year = {2022},
  eprint = {2206.02666},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.02666},
}
Figure