  While contextual bandit has a mature theory, effectively leveraging different
feedback patterns to enhance the pace of learning remains unclear. Bandits with
feedback graphs, which interpolates between the full information and bandit
regimes, provides a promising framework to mitigate the statistical complexity
of learning. In this paper, we propose and analyze an approach to contextual
bandits with feedback graphs based upon reduction to regression. The resulting
algorithms are computationally practical and achieve established minimax rates,
thereby reducing the statistical complexity in real-world applications.
