  We consider a bandit problem over a graph where the rewards are not directly
observed. Instead, the decision maker can compare two nodes and receive
(stochastic) information pertaining to the difference in their value. The graph
structure describes the set of possible comparisons. Consequently, comparing
between two nodes that are relatively far requires estimating the difference
between every pair of nodes on the path between them. We analyze this problem
from the perspective of sample complexity: How many queries are needed to find
an approximately optimal node with probability more than $1-\delta$ in the PAC
setup? We show that the topology of the graph plays a crucial in defining the
sample complexity: graphs with a low diameter have a much better sample
complexity.
