Corruption-Tolerant Gaussian Process Bandit Optimization

Abstract

We consider the problem of optimizing an unknown (typically non-convex) function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS), based on noisy bandit feedback. We consider a novel variant of this problem in which the point evaluations are not only corrupted by random noise, but also adversarial corruptions. We introduce an algorithm Fast-Slow GP-UCB based on Gaussian process methods, randomized selection between two instances labeled "fast" (but non-robust) and "slow" (but robust), enlarged confidence bounds, and the principle of optimism under uncertainty. We present a novel theoretical analysis upper bounding the cumulative regret in terms of the corruption level, the time horizon, and the underlying kernel, and we argue that certain dependencies cannot be improved. We observe that distinct algorithmic ideas are required depending on whether one is required to perform well in both the corrupted and non-corrupted settings, and whether the corruption level is known or not.

Accepted to AISTATS 2020

References in corpus (13)

• Practical Bayesian Optimization of Machine Learning Algorithms
• Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
• Max-value Entropy Search for Efficient Bayesian Optimization
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Finite-Time Analysis of Kernelised Contextual Bandits
• A General Framework for Multi-fidelity Bayesian Optimization with Gaussian Processes
• Adversarially Robust Optimization with Gaussian Processes
• Time-Varying Gaussian Process Bandit Optimization
• Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
• High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Fast Information-theoretic Bayesian Optimisation
• Stochastic Linear Optimization with Adversarial Corruption

Cited by in corpus (10)

• Corruption-robust exploration in episodic reinforcement learning
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Stochastic Linear Bandits Robust to Adversarial Attacks
• High-Dimensional Experimental Design and Kernel Bandits
• Optimal Order Simple Regret for Gaussian Process Bandits
• Uncertainty quantification using martingales for misspecified Gaussian processes
• Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Adversarial Attacks on Gaussian Process Bandits
• Neural Contextual Bandits without Regret