Best Arm Identification in Graphical Bilinear Bandits
This work addresses the problem of best arm identification in a novel graphical bandit setting, which could be relevant for resource allocation in networked systems.
This paper introduces a new graphical bilinear bandit problem where a central entity allocates arms to graph nodes and observes noisy bilinear rewards on edges. The goal is to identify the arm allocation that maximizes the sum of bilinear rewards, for which they propose a decentralized random sampling strategy with theoretical guarantees.
We introduce a new graphical bilinear bandit problem where a learner (or a \emph{central entity}) allocates arms to the nodes of a graph and observes for each edge a noisy bilinear reward representing the interaction between the two end nodes. We study the best arm identification problem in which the learner wants to find the graph allocation maximizing the sum of the bilinear rewards. By efficiently exploiting the geometry of this bandit problem, we propose a \emph{decentralized} allocation strategy based on random sampling with theoretical guarantees. In particular, we characterize the influence of the graph structure (e.g. star, complete or circle) on the convergence rate and propose empirical experiments that confirm this dependency.