# Laplacian Kernelized Bandit

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 53 references that are in the map.
- First posted on arXiv 1 Jan 2026.

## Builds on (most cited first, 30 of 34)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Information Directed Sampling for Stochastic Bandits with Graph Feedback](https://mlsanity.com/paper/1711.03198/) (2017)
- [Gaussian Processes on Graphs via Spectral Kernel Learning](https://mlsanity.com/paper/2006.07361/) (2020)
- [BlendSQL: A Scalable Dialect for Unifying Hybrid Question Answering in Relational Algebra](https://mlsanity.com/paper/2402.17882/) (2024)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Kernel Methods for Cooperative Multi-Agent Contextual Bandits](https://mlsanity.com/paper/2008.06220/) (2020)
- [Laplacian-regularized graph bandits: Algorithms and theoretical analysis](https://mlsanity.com/paper/1907.05632/) (2019)
- [Bandits with Feedback Graphs and Switching Costs](https://mlsanity.com/paper/1907.12189/) (2019)
- [Communication Efficient Distributed Learning for Kernelized Contextual Bandits](https://mlsanity.com/paper/2206.04835/) (2022)
- [Gaussian Processes Over Graphs](https://mlsanity.com/paper/1803.05776/) (2018)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Practical Contextual Bandits with Feedback Graphs](https://mlsanity.com/paper/2302.08631/) (2023)
- [Residual Bootstrap Exploration for Stochastic Linear Bandit](https://mlsanity.com/paper/2202.11474/) (2022)
- [Analysis of Thompson Sampling for Graphical Bandits Without the Graphs](https://mlsanity.com/paper/1805.08930/) (2018)
- [Horde of Bandits using Gaussian Markov Random Fields](https://mlsanity.com/paper/1703.02626/) (2017)
- [Deviance Matrix Factorization](https://mlsanity.com/paper/2110.05674/) (2021)
- [Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits](https://mlsanity.com/paper/2305.18784/) (2023)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)

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

- [Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback](https://mlsanity.com/paper/2610.17760/) (2026)

## Abstract (arXiv)

We study multi-user contextual bandits where users are related by a graph and their reward functions exhibit both non-linear behavior and graph homophily. We introduce a principled joint penalty for the collection of user reward functions fu, combining a graph smoothness term based on RKHS distances with an individual roughness penalty. Our central contribution is proving that this penalty is equivalent to the squared norm within a single, unified multi-user RKHS. We explicitly derive its reproducing kernel, which elegantly fuses the graph Laplacian with the base arm kernel. This unification allows us to reframe the problem as learning a single ''lifted'' function, enabling the design of principled algorithms, textttLK-GP-UCB and textttLK-GP-TS, that leverage Gaussian Process posteriors over this new kernel for exploration. We provide high-probability regret bounds that scale with an effective dimension of the multi-user kernel, replacing dependencies on user count or ambient dimension. Empirically, our methods outperform strong linear and non-graph-aware baselines in non-linear settings and remain competitive even when the true rewards are linear. Our work delivers a unified, theoretically grounded, and practical framework that bridges Laplacian regularization with kernelized bandits for structured exploration.