# Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces

Source: [Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces](<https://www.sota2.com/research/paper/6a41fbe6206542251d7cc9e4>)

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

Data updated: 2026-06-30T05:00:05.202Z

Authors: Joyanta Jyoti Mondal, Ibne Farabi Shihab, Anuj Sharma

Published: 2026-06-26T10:07:10.000Z

## Abstract

Contextual bandits with graph-structured arms arise in recommendation, citation retrieval, and social advertising, where arms connected on a graph tend to share reward signal. Standard dimensionality reduction ignores this structure, inflating exploration cost by a factor of $d/k$. We propose GraphDR-LinUCB, which projects arm features onto the graph's low-frequency spectral subspace and runs linear UCB in the resulting $k$-dimensional space. We prove the first $\\wtO(k\\sqrt{T})$ regret bound for spectral-projection-based contextual bandits, reducing dimension dependence from $d$ to $k$; a perturbation argument extends this to noisy graphs, with an explicit penalty for reward-smoothness mismatch and graph-estimation error. Our central theoretical finding is that the high-frequency reward component need not incur a worst-case linear-in-$T$ penalty: its actual cost depends on its realized impact along the played path, not on its total energy. A simple spectral comparison between subspaces ($\\Gamma\_k$) predicts which reducer wins on a given dataset, correctly calling five of six real-dataset outcomes without any fitted threshold. Across a synthetic benchmark and six real datasets (MovieLens, Amazon, LastFM, ogbn-arxiv, MIND), GraphDR-LinUCB reduces cumulative regret by $15\\times$ over full-dimensional LinUCB and outperforms competing graph-aware methods on five of six; the single failure is precisely where the graph's spectral subspace is misaligned with the reward.

## 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 MovieLens 100k](<https://www.sota2.com/research/sota/contextual-bandits-on-movielens-100k.md>): Contextual Bandits; MovieLens 100k; Cumulative Regret: 122.7.

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

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

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

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

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

- [Contextual Bandits on Amazon Dig. Music](<https://www.sota2.com/research/sota/contextual-bandits-on-amazon-dig-music.md>): Contextual Bandits; Amazon Dig. Music; Cumulative Regret: 309.9.

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

- [Bandit Recommendation on MovieLens 1M (top-1500 subset)](<https://www.sota2.com/research/sota/bandit-recommendation-on-movielens-1m-top-1500-subset.md>): Bandit Recommendation; MovieLens 1M top-1500 most-rated items; Cumulative Regret R(T): 273.3.

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

## Original sources and implementation

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

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