Online Learning with Feedback Graphs Without the Graphs
  We study an online learning framework introduced by Mannor and Shamir (2011)
in which the feedback is specified by a graph, in a setting where the graph may
vary from round to round and is \emph{never fully revealed} to the learner. We
show a large gap between the adversarial and the stochastic cases. In the
adversarial case, we prove that even for dense feedback graphs, the learner
cannot improve upon a trivial regret bound obtained by ignoring any additional
feedback besides her own loss. In contrast, in the stochastic case we give an
algorithm that achieves $\widetilde \Theta(\sqrt{\alpha T})$ regret over $T$
rounds, provided that the independence numbers of the hidden feedback graphs
are at most $\alpha$. We also extend our results to a more general feedback
model, in which the learner does not necessarily observe her own loss, and show
that, even in simple cases, concealing the feedback graphs might render a
learnable problem unlearnable.
