  We study the stochastic multi-armed bandit problem with the graph-based
feedback structure introduced by Mannor and Shamir. We analyze the performance
of the two most prominent stochastic bandit algorithms, Thompson Sampling and
Upper Confidence Bound (UCB), in the graph-based feedback setting. We show that
these algorithms achieve regret guarantees that combine the graph structure and
the gaps between the means of the arm distributions. Surprisingly this holds
despite the fact that these algorithms do not explicitly use the graph
structure to select arms; they observe the additional feedback but do not
explore based on it. Towards this result we introduce a "layering technique"
highlighting the commonalities in the two algorithms.
