Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers the online learning problem with adversarial rewards and a stochastic feedback graph. There has been a line of research on this problem, most of them need some assumptions on the graph structure and knowledge about the parameter of the graph. The main contribution of the paper is a minimax optimal algorithm with a less stringent assumption on the graph structure and needs no knowledge about the graph parameter. The main idea of the algorithm is to estimate the graph structure properly and feed the estimated graph to the Exp3.G algorithm (cf. https://arxiv.org/abs/1502.07617). Furthermore, the paper shows that if we observe not only the realized reward but also the realized graph, we can achieve better regret in some problem instances.
strengths_and_weaknesses: The contribution of the paper is solid. It generalizes existing research in an interesting way. The algorithm only assumes that all edges in the stochastic graph are independent, and needs no more knowledge about the graph structure. 
Strength:
1. The paper is well written. The idea is clearly presented.
2. The paper generalizes existing research by relaxing the assumption significantly.
3. The upper bound has a matching minimax lower bound.
4. The author reduces the stochastic feedback graph problem to the deterministic feedback graph problem in a nontrivial way.
Weakness:
1. The main algorithm is a reduction to the well-known Exp3.G algorithm, thus the novelty is not significant.

questions: The related work section could be improved. This section looks like a simple enumeration of existing research, with little discussion about the relationship between this paper and prior work. For example, it says that “Following Mannor and Shamir [2011], we can consider a more general scenario where the feedback graph is not fixed but changes over time, resulting in a sequence G1, . . . , GT of feedback graphs [Alon et al., 2013, 2017, Kocák et al., 2014, 2016b, Cohen et al., 2016].” If the author could elaborate on the similarity and differences between the scenario of their paper and the scenario of this line of work, the related work section will be more informative.
limitations: I don't see potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper provides online learning with stochastic feedback graphs, which is a generalization of vanilla online learning with feedback graphs in the sense that the feedback is stochastic.
The authors provide regret upper bound, which is a natural extension of the regret bound in the vanilla setting under milder conditions than the one in many existing works.
A more efficient algorithm is provided under the assumption that the learner can observe the realization of the entire graph.
Their algorithm is based on the idea of reducing the considering problem to the vanilla one by introducing threshold $\epsilon$.
strengths_and_weaknesses: Strengths:
- Assumptions on the underlying graph are largely relaxed.
- The limitations of existing are well described.
- The paper is well organized and written.

Weaknesses: 

(minor)
- The notation $\Delta$ around Eq.(3) is a bit confusing.
- The definition of $\Phi$ is given in page 7 while it is used in Algorithm 1 (page 5). I would like to see the definition or reference in page 5.
questions: - Is it in most cases that the $\sqrt{(\alpha_\epsilon/\epsilon) T}$ is much smaller than the other $(\delta_\epsilon/\epsilon)^{1/3} T^{2/3} \$?
- The considered setting can also be regarded as online learning with time-varying feedback graphs. Could the authors point out the relation between that setting?
limitations: Not applicable
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the online learning framework with stochastic feedback graphs. Unlike previous works, no assumptions are made on the feedback graphs. A regret-minimization algorithm, namely EdgeCatcher, is proposed and its regret bounds are analyzed in 3 cases where the feedback graphs are either strongly observable, observable or not observable. A lower bound is derived matching the upper-bounds guarantees of EdgeCatcher. Tighter bounds are also derived in the case where the entire feedback graph is observed at the end of each round. 
strengths_and_weaknesses: Strengths: the paper is well-written and easy to follow. The presented results are interesting and relevant to the community. Although the proposed algorithms are based on previously known ideas, the combination of such elements in building up EdgeCatcher is quite elegant and interesting. 

Weaknesses: certain parts in the main text requires more discussions (see below). Concrete examples and/or numerical experiments to show the performance of the proposed algorithms will be appreciated. 

After the rebuttal phase: the authors answer the raised concerns. I am willing to increase the score to 7.
questions: What is the complexity of computing $\varepsilon_s^*$ and $\varepsilon_w^*$ in (1) and (2)? Is there any better way to compute them  than considering each possible value of epsilon  in a brute-force manner? Similar question for the terms defined in Section 5.

The stopping criterion $\Phi$ defined in (5) depends on the constants $C_s, C_w$; so it also depends on the choice of algorithm A (so it should be written as $\Phi(\mathcal{G}, T, \mathcal{A})$. By (1) and (2), in the non-observable case, this $\Phi$ becomes infinite and then the RoundRobin will be played until $T/K$; then Blockreduction is called upon the remaining rounds. Will this lead to a linear regret?

The condition on $\varepsilon$ in Corollary 1 is rather counter-intuitive: as I understand, the smaller epsilon, the better approximation we have from RoundRobin, why do we need to have a lower-bound of $\varepsilon$ here, i.e., even if one can somehow obtain a better approximation, we cannot use it?

Any motivational examples for the cases considered in Section 5, or is this purely a theoretical question whether one can gets better guarantees? I might be mistaken but the notation $\hat{H}_t$  (Equation (6)) does not seem to be introduced anywhere. 





limitations:  the authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of bandits with stochastic graph feedback. Specifically, each edge of the feedback graph is realized with a fixed probability at each round instead of the deterministic setting. The authors propose a novel algorithm which achieves $O\left(\min\{\sqrt{\alpha T/\epsilon_1}, (\delta/\epsilon_2)^{1/3}T^{2/3}\}\right)$ regret bound where $\alpha$ is the independent number of the graph clipped on $\epsilon_1$ and $\delta$ is the weak domination number clipped on $\epsilon_2$. The algorithm contains three components, including one part exploring the structure of the graph,  one part exploiting the graph by picking one action over a period of rounds and one part that decides when to switch from the exploration part to the exploitation part. The authors also show the almost matching lower bound of this problem. Finally, based on a stronger assumption on the observations, the authors derive an algorithm with tighter regret bound.
strengths_and_weaknesses: Strength:
- The problem considered in this paper is well motivated and interesting.
- The paper is well written. The algorithms are intuitive and nicely explained.
- The proposed algorithm is novel to me and the authors show that the algorithm achieves the near-optimal regret bound. Although the first exploration part and the second exploitation (block-wise strategy) are very intuitive and classic in the stochastic graph feedback problem, the transition condition between the two parts require some novelty and the authors address this issue by carefully balancing the regret in the exploration phase and the exploitation phase. I checked the proofs for sec 3 and sec 4 and briefly checked the proofs in sec 5 and based on what I have checked, the proofs make sense to me.

Weakness:
- Overall I do not find any major weaknesses with the current work. There are some minor typos and issues:
-- line 206 and 208: I think here $\Delta=O((1/\epsilon)\ln(KT))$ should be $\Delta=\Omega((1/\epsilon)\ln(KT))$ or at least $\Delta=\Theta((1/\epsilon)\ln(KT))$
-- Algorithm 4 looks very dense to me. It would be better if there are more explanations in the some lines of the algorithm.
questions: See suggestions in "Strengths And Weaknesses".
limitations: Yes, the authors addressed the limitations of their work.
review_title: null

Meta-review: metareview: The reviewers came to consensus that this paper makes a good progress on online learning with stochastic feedback graphs. I agree with these opinions and please polish the manuscript by addressing the raised minor concerns such as the presentation issues in the final version.
confidence: Certain
Decision: Accept