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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 38 references that are in the map.
- First posted on arXiv 26 Jun 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Laplacian-regularized graph bandits: Algorithms and theoretical analysis](https://mlsanity.com/paper/1907.05632/) (2019)
- [Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey](https://mlsanity.com/paper/2106.02154/) (2021)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [Spectral bandits for smooth graph functions with applications in recommender systems](https://mlsanity.com/paper/2605.20552/) (2026)
- [Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2503.07555/) (2025)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Graph Feedback Bandits on Similar Arms: With and Without Graph Structures](https://mlsanity.com/paper/2501.14314/) (2025)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Contextual Bandits with Random Projection](https://mlsanity.com/paper/1903.08600/) (2019)
- [Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback](https://mlsanity.com/paper/2502.04678/) (2025)
- [Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity](https://mlsanity.com/paper/2605.20269/) (2026)

## Abstract (arXiv)

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√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 (Gammak) 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× 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.