Neural Bandit with Arm Group Graph
Neural Bandit with Arm Group Graph
复制标题
DOI：
10.1145/3534678.3539312
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Yunzhe Qi;Yikun Ban;Jingrui He
中科院分区：
文献类型：
--
作者：
Yunzhe Qi;Yikun Ban;Jingrui He
上下文强盗旨在根据上下文信息在一组武器中识别出具有最高奖励的最佳武器。由于手臂通常表现出群体行为并且群体之间存在相互影响，我们引入了一种新模型，Arm Group Graph（AGG），其中节点代表手臂组，加权边表示组之间的相关性。为了利用 AGG 中的丰富信息，我们提出了一种老虎机算法 AGG-UCB，其中神经网络旨在估计奖励，并且我们建议利用图神经网络（GNN）来学习具有相关性的臂组的表示。为了解决强盗中的利用-探索困境，我们推导了一个基于神经网络（利用）的新置信上限（UCB）以进行探索。此外，我们证明 AGG-UCB 可以通过超参数化神经网络实现接近最优的遗憾界限，并提供可能具有独立兴趣的全连接层 GNN 的收敛分析。最后，我们在多个公共数据集上针对最先进的基线进行了广泛的实验，显示了所提出算法的有效性。
Contextual bandits aim to identify among a set of arms the optimal one with the highest reward based on their contextual information. Motivated by the fact that the arms usually exhibit group behaviors and the mutual impacts exist among groups, we introduce a new model, Arm Group Graph (AGG), where the nodes represent the groups of arms and the weighted edges formulate the correlations among groups. To leverage the rich information in AGG, we propose a bandit algorithm, AGG-UCB, where the neural networks are designed to estimate rewards, and we propose to utilize graph neural networks (GNN) to learn the representations of arm groups with correlations. To solve the exploitation-exploration dilemma in bandits, we derive a new upper confidence bound (UCB) built on neural networks (exploitation) for exploration. Furthermore, we prove that AGG-UCB can achieve a near-optimal regret bound with over-parameterized neural networks, and provide the convergence analysis of GNN with fully-connected layers which may be of independent interest. In the end, we conduct extensive experiments against state-of-the-art baselines on multiple public data sets, showing the effectiveness of the proposed algorithm.