Robust Pareto Set Identification with Contaminated Bandit Feedback
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.