Understanding Bandits with Graph Feedback
  The bandit problem with graph feedback, proposed in [Mannor and Shamir,
NeurIPS 2011], is modeled by a directed graph $G=(V,E)$ where $V$ is the
collection of bandit arms, and once an arm is triggered, all its incident arms
are observed. A fundamental question is how the structure of the graph affects
the min-max regret. We propose the notions of the fractional weak domination
number $\delta^*$ and the $k$-packing independence number capturing upper bound
and lower bound for the regret respectively. We show that the two notions are
inherently connected via aligning them with the linear program of the weakly
dominating set and its dual -- the fractional vertex packing set respectively.
Based on this connection, we utilize the strong duality theorem to prove a
general regret upper bound $O\left(\left( \delta^*\log
|V|\right)^{\frac{1}{3}}T^{\frac{2}{3}}\right)$ and a lower bound
$\Omega\left(\left(\delta^*/\alpha\right)^{\frac{1}{3}}T^{\frac{2}{3}}\right)$
where $\alpha$ is the integrality gap of the dual linear program. Therefore,
our bounds are tight up to a $\left(\log |V|\right)^{\frac{1}{3}}$ factor on
graphs with bounded integrality gap for the vertex packing problem including
trees and graphs with bounded degree. Moreover, we show that for several
special families of graphs, we can get rid of the $\left(\log
|V|\right)^{\frac{1}{3}}$ factor and establish optimal regret.
