+ I liked the simplicity of the solution to divide the problem into star graphs. The domination number introduced seems to be a natural quantity for this problem. +/- To my opinion, the setting seems somewhat contrived combining feedback graphs and switching costs. The application to policy regret with counterfactual however provides a convincing example that the analysis can be useful and inspire future work. +/- The main part of the paper is rather clear and well written. Yet, I found the proofs in the appendices sometimes a bit hard to follow with sequences of unexplained equations. I would suggest to had some details. - There is a gap between the lower bound and the upper-bound (\sqrt(\beta) instead of \beta^{1/3}). In particular, for some graphs, the existing bound with the independence number may be better. This is also true for the results on the adaptive adversary and the counterfactual feedback. Other remarks: - Was the domination number already introduced for feedback graphs without switching costs? If yes, existing results for this problem should be cited. If not, it would be interesting to state what kind of results your analysis would provide without using the mini-batches. - Note that the length of the mini-batches tau_t may be non-integers. This should be clarified to be sure there are no side effects. For instance, what happens if $\tau_t << 1$? I am not sure if the analysis is still valid. - A better (more formal) definition of the independence and the domination numbers should be provided. It took me some time to understand their meaning. - Alg 1 and Thm 3.1: Since only upper-bounds on the pseudo-regret are provided, the exploration parameter gamma seems to be useless, isn't it? The choice gamma=0 seems to be optimal. A remark on high-probability upper-bounds and the role of gamma might be interesting. In particular, do you think your analysis (which is heavily based on expectations) can be extended to high-probability bounds on the regret? - I understand that this does not suit the analysis (which uses the equivalence in expectation btw Alg1 and Alg6) but it seems to be suboptimal (at least in practice) to discard all the feedbacks obtained while playing non-revealing actions. It would be nice to have practical experiments to understand better if we lose something here. It would be also nice to compare it with existing algorithms. Typos: - p2, l86: too many )) - Thm 3.1: A constant 2 in the number of switches is missing. - p13, l457: some notations seem to be undefined (w_t, W_t). - p14, you may add a remark - p15, l458: the number of switches can be upper-bounded by **twice** the number of times the revealing action is played - p16, l514: I did not understand why Thm 3.1 implies the condition of Thm C.5 with alpha=1/2 and not 1. By the way, (rho_t) should be non-decreasing for this condition to hold.
- There is a gap between the lower bound and the upper-bound (\sqrt(\beta) instead of \beta^{1/3}). In particular, for some graphs, the existing bound with the independence number may be better. This is also true for the results on the adaptive adversary and the counterfactual feedback. Other remarks: