mlsanityData to 14 Oct 2026

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

arXiv 2606.27917 ↗First posted 26 Jun 2026cs.LGcited by 0

Not on the map. Why?

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.

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

23 of 38 references.

References · 23

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Inductive Representation Learning on Large Graphscited by 6,320
  3. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  4. 2017A Tutorial on Thompson Samplingcited by 433
  5. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  6. 2014Online Clustering of Banditscited by 102
  7. 2016Corralling a Band of Bandit Algorithmscited by 100
  8. 2021Adapting to Misspecification in Contextual Banditscited by 81
  9. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
  10. 2019Bilinear Bandits with Low-rank Structurecited by 55
  11. 2013A Gang of Banditscited by 49
  12. 2019Laplacian-regularized graph bandits: Algorithms and theoretical analysiscited by 17
11 more
  1. 2021Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Surveycited by 8
  2. 2024Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recoverycited by 6
  3. 2026Spectral bandits for smooth graph functions with applications in recommender systemscited by 6
  4. 2025Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interferencecited by 5
  5. 2024Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketchingcited by 4
  6. 2025Generalized Low-Rank Matrix Contextual Bandits with Graph Informationcited by 4
  7. 2025Graph Feedback Bandits on Similar Arms: With and Without Graph Structurescited by 3
  8. 2019Contextual Bandits with Random Projectioncited by 1
  9. 2025Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedbackcited by 1
  10. 2026Catching a Moving Subspace: Low-Rank Bandits Beyond Stationaritycited by 1
  11. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1

Built on by

Not cited yet.