Thresholding Graph Bandits with GrAPL
  In this paper, we introduce a new online decision making paradigm that we
call Thresholding Graph Bandits. The main goal is to efficiently identify a
subset of arms in a multi-armed bandit problem whose means are above a
specified threshold. While traditionally in such problems, the arms are assumed
to be independent, in our paradigm we further suppose that we have access to
the similarity between the arms in the form of a graph, allowing us gain
information about the arm means in fewer samples. Such settings play a key role
in a wide range of modern decision making problems where rapid decisions need
to be made in spite of the large number of options available at each time. We
present GrAPL, a novel algorithm for the thresholding graph bandit problem. We
demonstrate theoretically that this algorithm is effective in taking advantage
of the graph structure when available and the reward function homophily (that
strongly connected arms have similar rewards) when favorable. We confirm these
theoretical findings via experiments on both synthetic and real data.
