Online Learning with Feedback Graphs Without the Graphs
This work addresses the challenge of learning with hidden feedback structures for online learning systems, with incremental theoretical contributions to understanding feedback graph models.
The paper tackles the problem of online learning with feedback graphs that vary per round and are never fully revealed, showing a stark contrast between adversarial and stochastic settings: in adversarial cases, no improvement over ignoring extra feedback is possible, while in stochastic cases, an algorithm achieves $\widetilde{\Theta}(\sqrt{\alpha T})$ regret over $T$ rounds when independence numbers are at most $\alpha$.
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 Θ(\sqrt{αT})$ regret over $T$ rounds, provided that the independence numbers of the hidden feedback graphs are at most $α$. 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.