Neural Bandit with Arm Group Graph
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.