Graph Neural Thompson Sampling

2024/06/15 by Wu, Shuang, Amini, Arash A.
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2406.10686

Abstract

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 GNN-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 O((d T)^1/2) in the number of interaction rounds, T, and a notion of effective dimension d, and (2) independent of the number of graph nodes. Empirical results validate that our proposed GNN-TS exhibits competitive performance and scales well on graph action bandit problems.

Related

• Neural Thompson Sampling
• Graph Neural Network Bandits
• A Biased Graph Neural Network Sampler with Near-Optimal Regret
• Combinatorial Neural Bandits
• Thompson Sampling For Stochastic Bandits with Graph Feedback