Graph Neural Thompson Sampling

我们考虑一个在线决策问题，其中奖励函数定义在图结构数据上。我们正式将问题公式化为图动作强盗的实例。然后，我们提出了GNN-TS，一种使用图神经网络（GNN）估计平均奖励函数和图神经切线特征用于不确定性估计的Thompson Sampling（TS）算法。我们证明，在奖励函数的某些有限假设下，GNN-TS实现了一个最先进的遗憾界，它（1）在交互轮数T和有效维度$\tilde{d}$的数量级上是亚线性的，即$\tilde{\mathcal{O}}((\tilde{d} T)^{1/2})$，（2）与图节点数量无关。实证结果验证了我们提出的GNN-TS在图动作强盗问题上表现出了竞争性能并且具有良好的可扩展性。

本论文致力于解决基于图结构数据的在线决策问题，通过定义奖励函数并将其建模为图动作赌博机问题，提出了一种名为GNN-TS的图神经网络Thompson采样算法，用于评估平均奖励函数和不确定性估计。

GNN-TS算法利用图神经网络来估计奖励函数的平均值和不确定性，证明在奖励函数的某些边界条件下，该算法可以实现最先进的后悔度上限，这个上限与图节点的数量无关。

本文提出的GNN-TS算法在图动作赌博机问题上取得了有竞争力的性能，并且具有良好的可扩展性。实验结果表明，该算法可以在有效降低后悔度的同时，大大减少了计算时间。此外，本文还提供了相关数据集和开源代码，便于其他研究者进行复现和扩展。

在这个领域中，近期还有一些相关的研究，例如《Graph Bandit Convolutional Neural Networks》、《Graph Convolutional Bandit》等。