# Pure Exploration in Kernel and Neural Bandits

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 52 references that are in the map.
- First posted on arXiv 22 Jun 2021.

## Builds on (most cited first, 22 of 22)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Misspecified Linear Bandits](https://mlsanity.com/paper/1704.06880/) (2017)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach](https://mlsanity.com/paper/1711.05174/) (2017)
- [Best Arm Identification in Generalized Linear Bandits](https://mlsanity.com/paper/1905.08224/) (2019)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)

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

- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Federated Neural Bandits](https://mlsanity.com/paper/2205.14309/) (2022)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Multi-task Representation Learning for Pure Exploration in Bilinear Bandits](https://mlsanity.com/paper/2311.00327/) (2023)
- [Near Instance Optimal Model Selection for Pure Exploration Linear Bandits](https://mlsanity.com/paper/2109.05131/) (2021)
- [(Private) Kernelized Bandits with Distributed Biased Feedback](https://mlsanity.com/paper/2301.12061/) (2023)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Reward-Biased Maximum Likelihood Estimation for Neural Contextual Bandits](https://mlsanity.com/paper/2203.04192/) (2022)
- [Neural Bandits for Data Mining: Searching for Dangerous Polypharmacy](https://mlsanity.com/paper/2212.05190/) (2022)
- [Kernel ε-Greedy for Multi-Armed Bandits with Covariates](https://mlsanity.com/paper/2306.17329/) (2023)

## Abstract (arXiv)

We study pure exploration in bandits, where the dimension of the feature representation can be much larger than the number of arms. To overcome the curse of dimensionality, we propose to adaptively embed the feature representation of each arm into a lower-dimensional space and carefully deal with the induced model misspecification. Our approach is conceptually very different from existing works that can either only handle low-dimensional linear bandits or passively deal with model misspecification. We showcase the application of our approach to two pure exploration settings that were previously under-studied: (1) the reward function belongs to a possibly infinite-dimensional Reproducing Kernel Hilbert Space, and (2) the reward function is nonlinear and can be approximated by neural networks. Our main results provide sample complexity guarantees that only depend on the effective dimension of the feature spaces in the kernel or neural representations. Extensive experiments conducted on both synthetic and real-world datasets demonstrate the efficacy of our methods.