From Bandits to Experts: A Tale of Domination and Independence
We consider the partial observability model for multi-armed bandits, introduced by Mannor and Shamir [14]. Our main result is a characterization of regret in the directed observability model in terms of the dominating and independence numbers of the observability graph (which must be accessible before selecting an action). In the undirected case, we show that the learner can achieve optimal regret without even accessing the observability graph before selecting an action. Both results are shown using variants of the Exp3 algorithm operating on the observability graph in a time-efficient manner.
The authors of this paper consider a kind of 
      sequential prediction problem with a side graph information. It is a 
      setting that is intermediary between the expert setting and the bandit 
      setting, and where one observes, after choosing an arm, not only the 
      outcome of the arm but also the outcome of some other arms that are linked 
      to this arm through a graph. They consider two main settings, (i) the 
      informed setting where the graph is made available to the learner before 
      each prediction and (ii) the uniformed setting which they introduce and 
      where the graph is only made available to the learner after his 
      prediction. Their results also depend on whether the graph is directed or 
      not. The results are provided in the adversarial case. The authors 
      provide some results in these two setting (uninformed and informed). They 
      first provide an algorithm in the uniformed setting which I believe are 
      the first ones in this setting, and bound the regret in the undirected and 
      the directed case. In the directed case, there is a gap between the lower 
      and upper bound for the first algorithm they introduced. In the informed 
      setting, they manages, in the directed case, to go closer to the lower 
      bound by building a new algorithm. I find the paper well written 
      and the results interesting. My main comment on it would be that it would 
      gain in clarity if the authors could: - write explicitly in the bandit 
      and expert setting the bound of EXP3-SET, and comment on the fact that it 
      matches the lower bound (up to some log terms in the bandit case) in both 
      cases. The bound in the case of Erdos-Renyi random graphs is nice but 
      gives less insight and you can put it in appendix if you lack space. - 
      To me Theorem 1 is a technical side results, and Corollary 2 is more 
      clear. You should maybe delete Theorem 1 and keep corollary 2. - I 
      think it is very important that you extend a bit the explanation right 
      after Corollary 2 on how to choose the \alpha_t, and of how much is the 
      loss if you do not know them for tuning \beta. What you say makes sense, 
      but it is too concise and have not a clear picture of how much you loose 
      in the regret by doing what you propose. - Maybe even, you could 
      suppress Corollary 2 and just keep Corollary 4. And then, you will have 
      more space to do an extended discussion. - It would really help the 
      reader to discuss the links and differences between Corollary 4 and 
      Corollary 8 (again, to me, you can suppress Theorem 7 and just keep 
      Corollary 8). For instance, provide an example of graph where \alpha(G) is 
      small and mas(G) is large: after all, it is not obvious from your results 
      that the bound in Corollary 8 is sharpen than the bound in Corollary 4 
      (even though the setting in Corollary 8 supposes that the graph 
      information is available to the predictor), since you have an additional 
      ln(K)\sqrt{\log(T)} that appears. Please discuss this in details. 
      As a conclusion I like this paper, and find the results nice. It 
      seems correct but I did not have time to check the proofs in full 
      details.