mlsanityData to 7 Oct 2026

A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits

arXiv 2202.01850 ↗First posted 3 Feb 2022stat.ML cs.AI cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

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(C √T γ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.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 40 of its 58 references that are in the map. First posted on arXiv 3 Feb 2022.

Builds on

40 of 58 references.

References · 40

  1. 2017On Kernelized Multi-armed Banditscited by 348
  2. 2017Max-value Entropy Search for Efficient Bayesian Optimizationcited by 202
  3. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 188
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  5. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  6. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  7. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  8. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  9. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  10. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  11. 2018Adversarially Robust Optimization with Gaussian Processescited by 61
  12. 2020Distributionally Robust Bayesian Optimizationcited by 60
28 more
  1. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  2. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  3. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  4. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  5. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  6. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  7. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  8. 2020Bayesian Optimization of Risk Measurescited by 35
  9. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  10. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 29
  11. 2020Prediction with Corrupted Expert Advicecited by 26
  12. 2017Practical Bayesian optimization in the presence of outlierscited by 25
  13. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 23
  14. 2019Bayesian Optimization under Heavy-tailed Payoffscited by 21
  15. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  16. 2021Defense Against Reward Poisoning Attacks in Reinforcement Learningcited by 20
  17. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  18. 2018Semiparametric Contextual Banditscited by 19
  19. 2021Value-at-Risk Optimization with Gaussian Processescited by 19
  20. 2016Unscented Bayesian Optimization for Safe Robot Graspingcited by 18
  21. 2021Risk-averse Heteroscedastic Bayesian Optimizationcited by 17
  22. 2017Streaming kernel regression with provably adaptive mean, variance, and regularizationcited by 15
  23. 2022Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Timescited by 12
  24. 2021Bias-Robust Bayesian Optimization via Dueling Banditscited by 11
  25. 2020Approximation Theory Based Methods for RKHS Banditscited by 6
  26. 2021Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptionscited by 5
  27. 2021Adversarial Attacks on Gaussian Process Banditscited by 5
  28. 2021Corruption Robust Active Learningcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 5; 2025: 3; 2026: 1.

11 papers.

  1. 2022Graph Neural Network Banditscited by 10
  2. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  3. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  4. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  5. 2024Sample-efficient Bayesian Optimisation Using Known Invariancescited by 4
  6. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  7. 2024Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Duelingcited by 2
  8. 2024Stochastic Bandits Robust to Adversarial Attackscited by 1
  9. 2025Robust Satisficing Gaussian Process Bandits Under Adversarial Attackscited by 1
  10. 2025Robust Bayesian Optimisation with Unbounded Corruptionscited by 1
  11. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1