  Pure exploration in multi-armed bandits has emerged as an important framework
for modeling decision-making and search under uncertainty. In modern
applications, however, one is often faced with a tremendously large number of
options. Even obtaining one observation per option may be too costly rendering
traditional pure exploration algorithms ineffective. Fortunately, one often has
access to similar relationships amongst the options that can be leveraged. In
this paper, we consider the pure exploration problem in stochastic multi-armed
bandits where the similarities between the arms are captured by a graph and the
rewards may be represented as a smooth signal on this graph. In particular, we
consider the problem of finding the arm with the maximum reward (i.e., the
maximizing problem) or one with a sufficiently high reward (i.e., the
satisficing problem) under this model. We propose novel algorithms
\textbf{\algoname{}} (GRaph-based UcB) and $\zeta$-\textbf{\algoname{}} for
these problems and provide a theoretical characterization of their performance
which specifically elicits the benefit of the graph side information. We also
prove a lower bound on the data requirement, showing a large class of problems
where these algorithms are near-optimal. We complement our theory with
experimental results that show the benefit of capitalizing on such side
information.
