# Laplacian-regularized graph bandits: Algorithms and theoretical analysis

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2019.

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

- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [Maximizing and Satisficing in Multi-armed Bandits with Graph Information](https://mlsanity.com/paper/2108.01152/) (2021)
- [RoME: A Robust Mixed-Effects Bandit Algorithm for Optimizing Mobile Health Interventions](https://mlsanity.com/paper/2312.06403/) (2023)
- [Semi-Parametric Contextual Bandits with Graph-Laplacian Regularization](https://mlsanity.com/paper/2205.08295/) (2022)
- [Meta Learning in Bandits within Shared Affine Subspaces](https://mlsanity.com/paper/2404.00688/) (2024)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2306.05998/) (2023)
- [Online Network Source Optimization with Graph-Kernel MAB](https://mlsanity.com/paper/2307.03641/) (2023)
- [Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.14138/) (2023)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [Laplacian Kernelized Bandit](https://mlsanity.com/paper/2601.00461/) (2026)
- [When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution](https://mlsanity.com/paper/2104.07150/) (2021)
- [Recommending with Recommendations](https://mlsanity.com/paper/2112.00979/) (2021)
- [Anomaly Detection in Networked Bandits](https://mlsanity.com/paper/2508.20076/) (2025)
- [Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces](https://mlsanity.com/paper/2606.27917/) (2026)

## Abstract (arXiv)

We consider a stochastic linear bandit problem with multiple users, where the relationship between users is captured by an underlying graph and user preferences are represented as smooth signals on the graph. We introduce a novel bandit algorithm where the smoothness prior is imposed via the random-walk graph Laplacian, which leads to a single-user cumulative regret scaling as tildeO(Psi d √T) with time horizon T, feature dimensionality d, and the scalar parameter Psi ∈ (0,1) that depends on the graph connectivity. This is an improvement over tildeO(d √T) in algoLinUCB~Cciteli2010contextual, where user relationship is not taken into account. In terms of network regret (sum of cumulative regret over n users), the proposed algorithm leads to a scaling as tildeO(Psi d√nT), which is a significant improvement over tildeO(nd√T) in the state-of-the-art algorithm algoGob.Lin Ccitecesa2013gang. To improve scalability, we further propose a simplified algorithm with a linear computational complexity with respect to the number of users, while maintaining the same regret. Finally, we present a finite-time analysis on the proposed algorithms, and demonstrate their advantage in comparison with state-of-the-art graph-based bandit algorithms on both synthetic and real-world data.