  We naturally generalize the on-line graph prediction problem to a version of
stochastic contextual bandit problems where contexts are vertices in a graph
and the structure of the graph provides information on the similarity of
contexts. More specifically, we are given a graph $G=(V,E)$, whose vertex set
$V$ represents contexts with {\em unknown} vertex label $y$. In our stochastic
contextual bandit setting, vertices with the same label share the same reward
distribution. The standard notion of instance difficulties in graph label
prediction is the cutsize $f$ defined to be the number of edges whose end
points having different labels. For line graphs and trees we present an
algorithm with regret bound of $\tilde{O}(T^{2/3}K^{1/3}f^{1/3})$ where $K$ is
the number of arms. Our algorithm relies on the optimal stochastic bandit
algorithm by Zimmert and Seldin~[AISTAT'19, JMLR'21]. When the best arm
outperforms the other arms, the regret improves to $\tilde{O}(\sqrt{KT\cdot
f})$. The regret bound in the later case is comparable to other optimal
contextual bandit results in more general cases, but our algorithm is easy to
analyze, runs very efficiently, and does not require an i.i.d. assumption on
the input context sequence. The algorithm also works with general graphs using
a standard random spanning tree reduction.

Machine Learning;Machine Learning