Stochastic contextual bandits with graph feedback: from independence
  number to MAS number
Yuxiao Wen Yanjun Han Zhengyuan Zhou
We consider contextual bandits with graph feedback, a class of interactive
learning problems with richer structures than vanilla contextual bandits, where
taking an action reveals the rewards for all neighboring actions in the
feedback graph under all contexts. Unlike the multi-armed bandits setting where
a growing literature has painted a near-complete understanding of graph
feedback, much remains unexplored in the contextual bandits counterpart. In
this paper, we make inroads into this inquiry by establishing a regret lower
bound $\Omega(\sqrt{\beta_M(G) T})$, where $M$ is the number of contexts, $G$
is the feedback graph, and $\beta_M(G)$ is our proposed graph-theoretical
quantity that characterizes the fundamental learning limit for this class of
problems. Interestingly, $\beta_M(G)$ interpolates between $\alpha(G)$ (the
independence number of the graph) and $\mathsf{m}(G)$ (the maximum acyclic
subgraph (MAS) number of the graph) as the number of contexts $M$ varies. We
also provide algorithms that achieve near-optimal regrets for important classes
of context sequences and/or feedback graphs, such as transitively closed graphs
that find applications in auctions and inventory control. In particular, with
many contexts, our results show that the MAS number completely characterizes
the statistical complexity for contextual bandits, as opposed to the
independence number in multi-armed bandits.