# On Kernelized Multi-armed Bandits

arXiv: https://arxiv.org/abs/1704.00445 · HTML: https://mlsanity.com/paper/1704.00445/

## Key facts

- Cited by 352 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2017.

## Built on by (most cited first, 30 of 352)

- [Towards Stable Test-Time Adaptation in Dynamic Wild World](https://mlsanity.com/paper/2302.12400/) (2023)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimism](https://mlsanity.com/paper/2305.18438/) (2023)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [State-wise Safe Reinforcement Learning: A Survey](https://mlsanity.com/paper/2302.03122/) (2023)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Practical and Rigorous Uncertainty Bounds for Gaussian Process Regression](https://mlsanity.com/paper/2105.02796/) (2021)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning](https://mlsanity.com/paper/2107.04050/) (2021)
- [Robust Multi-Objective Bayesian Optimization Under Input Noise](https://mlsanity.com/paper/2202.07549/) (2022)
- [Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?](https://mlsanity.com/paper/2301.12844/) (2023)
- [Differentially Private Federated Bayesian Optimization with Distributed Exploration](https://mlsanity.com/paper/2110.14153/) (2021)
- [Optimistic Active Exploration of Dynamical Systems](https://mlsanity.com/paper/2306.12371/) (2023)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximization](https://mlsanity.com/paper/2412.12098/) (2024)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Safe Exploration in Reinforcement Learning: A Generalized Formulation and Algorithms](https://mlsanity.com/paper/2310.03225/) (2023)
- [GoSafe: Globally Optimal Safe Robot Learning](https://mlsanity.com/paper/2105.13281/) (2021)
- [Checkpoint Merging via Bayesian Optimization in LLM Pretraining](https://mlsanity.com/paper/2403.19390/) (2024)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2103.04972/) (2021)
- [Reinforced Few-Shot Acquisition Function Learning for Bayesian Optimization](https://mlsanity.com/paper/2106.04335/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (2021)
- [Surrogate modeling for Bayesian optimization beyond a single Gaussian process](https://mlsanity.com/paper/2205.14090/) (2022)
- [Efficient Exploration in Continuous-time Model-based Reinforcement Learning](https://mlsanity.com/paper/2310.19848/) (2023)
- [Value-at-Risk Optimization with Gaussian Processes](https://mlsanity.com/paper/2105.06126/) (2021)
- [On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2110.09771/) (2021)

## Abstract (arXiv)

We consider the stochastic bandit problem with a continuous set of arms, with the expected reward function over the arms assumed to be fixed but unknown. We provide two new Gaussian process-based algorithms for continuous bandit optimization-Improved GP-UCB (IGP-UCB) and GP-Thomson sampling (GP-TS), and derive corresponding regret bounds. Specifically, the bounds hold when the expected reward function belongs to the reproducing kernel Hilbert space (RKHS) that naturally corresponds to a Gaussian process kernel used as input by the algorithms. Along the way, we derive a new self-normalized concentration inequality for vector- valued martingales of arbitrary, possibly infinite, dimension. Finally, experimental evaluation and comparisons to existing algorithms on synthetic and real-world environments are carried out that highlight the favorable gains of the proposed strategies in many cases.