Bogunovic, Ilija; Li, Zihan; Krause, Andreas; Scarlett, Jonathan; (2022) A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits. In: Koyejo, S and Mohamed, S and Agarwal, A and Belgrave, D and Cho, K and Oh, A, (eds.) Advances In Neural Information Processing Systems 35 (NEURIPS 2022). Neural Information Processing Systems (NIPS)

Preview

PDF 9408_a_robust_phased_elimination_al.pdf - Accepted Version Download (1MB) | Preview

Abstract

We consider the sequential optimization of an unknown, continuous, and expensive to evaluate reward function, from noisy and adversarially corrupted observed rewards. When the corruption attacks are subject to a suitable budget C and the function lives in a Reproducing Kernel Hilbert Space (RKHS), the problem can be posed as corrupted Gaussian process (GP) bandit optimization. We propose a novel robust elimination-type algorithm that runs in epochs, combines exploration with infrequent switching to select a small subset of actions, and plays each action for multiple time instants. Our algorithm, Robust GP Phased Elimination (RGP-PE), successfully balances robustness to corruptions with exploration and exploitation such that its performance degrades minimally in the presence (or absence) of adversarial corruptions. When T is the number of samples and γT is the maximal information gain, the corruption-dependent term in our regret bound is O(CγT3/2), which is significantly tighter than the existing O(CpTγT) for several commonly-considered kernels. We perform the first empirical study of robustness in the corrupted GP bandit setting, and show that our algorithm is robust against a variety of adversarial attacks.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item