mlsanityData to 14 Oct 2026

Nearly-Optimal Algorithm for Adversarial Kernelized Bandits

arXiv 2605.10299 ↗First posted 11 May 2026cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

This paper studies kernelized bandits (also known as Gaussian process bandits) in an adversarial environment, where the reward functions in a known reproducing kernel Hilbert space (RKHS) may be adversarially chosen at each round. We show that the exponential-weight algorithm achieves tildeO(√T γT) adversarial regret, where T and γT denote the number of total rounds and the maximum information gain, respectively. For squared exponential (SE) and nu-Mat'ern kernels, we also show algorithm-independent lower bounds that guarantee the optimality of our algorithm up to polylogarithmic factors. Furthermore, we present a computationally efficient variant of our algorithm using Nystr"om approximation while maintaining nearly optimal regret guarantees.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 51 of its 72 references that are in the map. First posted on arXiv 11 May 2026.

Builds on

51 of 72 references.

References · 51

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2013Learning to Optimize Via Posterior Samplingcited by 256
  3. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
  4. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  5. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  6. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  7. 2014Hilbert Space Methods for Reduced-Rank Gaussian Process Regressioncited by 88
  8. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  9. 2018Adversarially Robust Optimization with Gaussian Processescited by 62
  10. 2020Distributionally Robust Bayesian Optimizationcited by 61
  11. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  12. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
38 more
  1. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  2. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  3. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  4. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  5. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 31
  6. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  7. 2020Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programmingcited by 28
  8. 2017Sparsity, variance and curvature in multi-armed banditscited by 24
  9. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
  10. 2021Value-at-Risk Optimization with Gaussian Processescited by 20
  11. 2021No-Regret Algorithms for Time-Varying Bayesian Optimizationcited by 19
  12. 2019No-Regret Learning in Unknown Games with Correlated Payoffscited by 18
  13. 2020Learning to Play Sequential Games versus Unknown Opponentscited by 18
  14. 2020No-regret Algorithms for Multi-task Bayesian Optimizationcited by 18
  15. 2020Mean-Variance Analysis in Bayesian Optimization under Uncertaintycited by 18
  16. 2021Nearly Optimal Algorithms for Level Set Estimationcited by 17
  17. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  18. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 17
  19. 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16
  20. 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
  21. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  22. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  23. 2018Online learning with kernel lossescited by 12
  24. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
  25. 2020Regret Bounds for Noise-Free Kernel-Based Banditscited by 11
  26. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  27. 2018Distributed Adaptive Sampling for Kernel Matrix Approximationcited by 9
  28. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  29. 2014On the Complexity of Bandit Linear Optimizationcited by 8
  30. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  31. 2019Statistical and Computational Trade-Offs in Kernel K-Meanscited by 7
  32. 2020Approximation Theory Based Methods for RKHS Banditscited by 6
  33. 2023Adversarial Contextual Bandits Go Kernelizedcited by 6
  34. 2021Adversarial Attacks on Gaussian Process Banditscited by 5
  35. 2022Instance-Dependent Regret Analysis of Kernelized Banditscited by 5
  36. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  37. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  38. 2023Robust Bayesian Satisficingcited by 3

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Near-Optimal Regret in Adversarial Kernel Banditscited by 0