# Approximation Theory Based Methods for RKHS Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2020.

## Built on by (most cited first, 6 of 6)

- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport](https://mlsanity.com/paper/2502.07397/) (2025)
- [Near-Optimal Regret in Adversarial Kernel Bandits](https://mlsanity.com/paper/2605.26585/) (2026)
- [Trajectory-Aware Best-Arm Identification for Local Search Allocation in Bayesian Optimization and Beyond](https://mlsanity.com/paper/2605.31050/) (2026)
- [Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization](https://mlsanity.com/paper/2607.01080/) (2026)

## Abstract (arXiv)

The RKHS bandit problem (also called kernelized multi-armed bandit problem) is an online optimization problem of non-linear functions with noisy feedback. Although the problem has been extensively studied, there are unsatisfactory results for some problems compared to the well-studied linear bandit case. Specifically, there is no general algorithm for the adversarial RKHS bandit problem. In addition, high computational complexity of existing algorithms hinders practical application. We address these issues by considering a novel amalgamation of approximation theory and the misspecified linear bandit problem. Using an approximation method, we propose efficient algorithms for the stochastic RKHS bandit problem and the first general algorithm for the adversarial RKHS bandit problem. Furthermore, we empirically show that one of our proposed methods has comparable cumulative regret to IGP-UCB and its running time is much shorter.