# Laplacian-regularized graph bandits: Algorithms and theoretical analysis

Source: [Laplacian-regularized graph bandits: Algorithms and theoretical analysis](<https://www.sota2.com/research/paper/68fa67061e209131cea13e11>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T22:04:19.938Z

Authors: Kaige Yang, Xiaowen Dong, Laura Toni

Published: 2019-07-12T08:57:26.000Z

## Abstract

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 $\\tilde{\\mathcal{O}}(\\Psi d \\sqrt{T})$ with time horizon $T$, feature dimensionality $d$, and the scalar parameter $\\Psi \\in (0,1)$ that depends on the graph connectivity. This is an improvement over $\\tilde{\\mathcal{O}}(d \\sqrt{T})$ in \\algo{LinUCB}~\\Ccite{li2010contextual}, 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 $\\tilde{\\mathcal{O}}(\\Psi d\\sqrt{nT})$, which is a significant improvement over $\\tilde{\\mathcal{O}}(nd\\sqrt{T})$ in the state-of-the-art algorithm \\algo{Gob.Lin} \\Ccite{cesa2013gang}. 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Contextual Bandits on ogbn-arxiv](<https://www.sota2.com/research/sota/contextual-bandits-on-ogbn-arxiv.md>): Contextual Bandits; Ogbn-arxiv; Cumulative Regret: 203.2.

- [Contextual Bandits on MIND small](<https://www.sota2.com/research/sota/contextual-bandits-on-mind-small.md>): Contextual Bandits; MIND small; Cumulative Regret: 325.9.

- [Contextual Bandits on Synthetic SBM](<https://www.sota2.com/research/sota/contextual-bandits-on-synthetic-sbm.md>): Contextual Bandits; Synthetic SBM; Cumulative Regret: 462.1.

- [Contextual Bandits on Amazon](<https://www.sota2.com/research/sota/contextual-bandits-on-amazon.md>): Contextual Bandits; AMAZON; Cumulative Regret R(T): 189.4.

- [Contextual Bandits on LastFM](<https://www.sota2.com/research/sota/contextual-bandits-on-lastfm.md>): Contextual Bandits; LastFM; Cumulative Regret: 276.9.

- [Contextual Bandits on MovieLens-1M](<https://www.sota2.com/research/sota/contextual-bandits-on-movielens-1m.md>): Contextual Bandits; MovieLens 1M; Cumulative Regret: 238.

- [Contextual Bandits on MovieLens 100k](<https://www.sota2.com/research/sota/contextual-bandits-on-movielens-100k.md>): Contextual Bandits; MovieLens 100k; Cumulative Regret: 247.2.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1907.05632>)

[PDF](<https://arxiv.org/pdf/1907.05632.pdf>)
