mlsanityData to 7 Oct 2026

Graph Neural Thompson Sampling

arXiv 2406.10686 ↗First posted 15 Jun 2024cs.LG cs.AI stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

We consider an online decision-making problem with a reward function defined over graph-structured data. We formally formulate the problem as an instance of graph action bandit. We then propose textttGNN-TS, a Graph Neural Network (GNN) powered Thompson Sampling (TS) algorithm which employs a GNN approximator for estimating the mean reward function and the graph neural tangent features for uncertainty estimation. We prove that, under certain boundness assumptions on the reward function, GNN-TS achieves a state-of-the-art regret bound which is (1) sub-linear of order tildeO((tilded T)1/2) in the number of interaction rounds, T, and a notion of effective dimension tilded, and (2) independent of the number of graph nodes. Empirical results validate that our proposed textttGNN-TS exhibits competitive performance and scales well on graph action bandit problems.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 40 of its 58 references that are in the map. First posted on arXiv 15 Jun 2024.

Builds on

40 of 58 references.

References · 40

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Automatic chemical design using a data-driven continuous representation of moleculescited by 762
  3. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 647
  4. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  5. 2017A Tutorial on Thompson Samplingcited by 420
  6. 2017On Kernelized Multi-armed Banditscited by 348
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  8. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  9. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  10. 2018Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Samplingcited by 166
  11. 2020Neural Thompson Samplingcited by 127
  12. 2019ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendationscited by 77
28 more
  1. 2020Neural Contextual Bandits with Deep Representation and Shallow Explorationcited by 71
  2. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  3. 2019A Geometric Perspective on Optimal Representations for Reinforcement Learningcited by 54
  4. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  5. 2021Neural Contextual Bandits without Regretcited by 40
  6. 2019Perturbed-History Exploration in Stochastic Linear Banditscited by 28
  7. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  8. 2022Sample-Then-Optimize Batch Neural Thompson Samplingcited by 25
  9. 2021Batched Neural Banditscited by 22
  10. 2020A Closer Look at Small-loss Bounds for Bandits with Graph Feedbackcited by 21
  11. 2023Graph Neural Banditscited by 20
  12. 2019Feedback graph regret bounds for Thompson Sampling and UCBcited by 17
  13. 2019Laplacian-regularized graph bandits: Algorithms and theoretical analysiscited by 17
  14. 2019Deep Neural Linear Bandits: Overcoming Catastrophic Forgetting through Likelihood Matchingcited by 16
  15. 2019Perturbed-History Exploration in Stochastic Multi-Armed Banditscited by 16
  16. 2021Understanding Bandits with Graph Feedbackcited by 14
  17. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  18. 2019On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problemscited by 10
  19. 2022Graph Neural Network Banditscited by 10
  20. 2017Thompson Sampling For Stochastic Bandits with Graph Feedbackcited by 9
  21. 2022Neural Bandit with Arm Group Graphcited by 8
  22. 2018Analysis of Thompson Sampling for Graphical Bandits Without the Graphscited by 7
  23. 2020Reinforcement Learning with Feedback Graphscited by 7
  24. 2022Residual Bootstrap Exploration for Stochastic Linear Banditcited by 7
  25. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6
  26. 2021Maximizing and Satisficing in Multi-armed Bandits with Graph Informationcited by 5
  27. 2020Graph-based State Representation for Deep Reinforcement Learningcited by 4
  28. 2023Online Network Source Optimization with Graph-Kernel MABcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Laplacian Kernelized Banditcited by 0