Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies regret-bounds for semi-bandits in the feedback graph model for weakly observable feedback graphs, and (sometimes) improves both the upper and lower bounds on the regret in the adversarial setting (though in general the bounds are incomparable). In particular, they characterize the regret more precisely than existing work by going beyond weak domination number regret bounds in this setting; they use the notion of the fractional weak domination number (previously used for the case of strongly observable feedback graphs) and the k-packing independence number and show bounds in terms of these parameters. Since the gap between the upper and lower bounds on the regret depends on the integrality gap for a linear program related to the feedback graph (corresponding to the fractional weakly dominating sets problem on the graph), they then provide some natural concrete instances (e.g. bounded degree graphs) where the lower bound is now tight up to a factor of $\log^{1/3}(n)$. 
main_review: This work follows an interesting line of work in proving regret bounds for the adversarial semi-bandit problem in terms of parameters of the feedback graph. The results are novel and interesting, and are definitely worth of acceptance. The paper is well-written and clearly contextualizes their results compared to the prior work. Moreover, some new techniques are introduced to get the lower bound -- the proof initially follows the same outline as in the original semi-bandit feedback paper lower bound, but is able to conduct a smarter analysis by reducing to the problem of best arm identification (e.g. Thm.2, which I found interesting and useful).  They also give a novel rounding procedure on the aforementioned LP to connect the integrality gap to k-packing independence number ( which shows up in Thm 2), thus completing the connection to the upper bound results. The upper bound result is almost standard; the only novelty here is the choice of exploration distribution, which depends on rounding the LP (the analysis is standard and the dependence on the integrality gap falls out by definition).

Overall, I found the results of section D.2 and D.3 the most interesting and useful technical part of the paper, in addition to the actual result (identification of graph parameters that better characterize the regret in the weakly observable setting, and even more tightly in a few natural concrete instances).  I would encourage some re-writing of lines 741-750 -- the logical flow of the argument is a bit disjointed, and could read more smoothly given that the argument is very simple. Overall, I recommend acceptance.
limitations_and_societal_impact: Yes, as this is a theory paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider bandits with graph feedback and show improved lower and upper regret bounds involving a new quantity: fractional weak domination number. This leads to some logarithmic dependence improvement on the number of nodes. 
main_review: - The paper is well written and well organized, which provides sufficient background knowledge to reach the results. The table is also helpful.
- For the upper bounds, I think it is interesting to see the improvement, but overall the the algorithm is not very novel, which seems to be still Exp3.G but with the fractional exploration probability. Related to this, I think the authors should compare their algorithm with Exp3.G or other bandit with graph feedback algorithms. The unbiased estimator and the negative entropy function are both standard in this field I think. The only difference as I mentioned should be the construction of u. The current presentation may give readers an impression that the algorithm is all new in these parts. 
- Moreover, the improvement from \delta to \delta* seems a little bit incremental to me. One thing I think is more interesting but the authors didn't even mention is about the computational efficiency. I think in the original Exp.G algorithm, we need to have a weak domination set to achieve such bounds, but the set is NP-hard to get in general. However, the exploration probability the authors propose can be efficiently computed via a linear program. Maybe the authors can verify whether this is the case, and it is nice to discuss this in the future revision. 
- As for the lower bounds, although the authors say "we can not find an instance such that our lower bound is worse than the previous one", this claim looks a little bit weak to me and I may still think the bounds are in general incomparable and the improvement in some special instances seems not very significant. 
- What is BESTARMID around Line 351? I couldn't find it in the main text. 
- Around Line 118 the authors mention [35] and say [35] gives another way to achieve the optimal regret bound. But what theorem or algorithm are the authors referring to? I thought the paper is mainly about adaptive bounds and many results in the paper have logarithmic terms in T, which may not be considered "optimal" here. 

Overall, I think the authors have an interesting observation on this problem, but the results are not a very significant improvement compared to the previous works. Also, there is not much algorithmic contribution. Therefore, I give the marginally below the acceptance threshold rating to this paper.

===========

I thank the authors for the valuable discussions and I increase my score based on this. 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the min-max regret bounds of the adversarial bandit with graph feedback. The graph feedback means that when pulling an arm, the learner can also get feedback from the arms that are adjacent to this arm in a specific graph $G$. The authors made non-trivial improvements on the upper bound and lower bound on the regret, especially for the “weakly observable” graphs. For some special cases such as complete
bipartite graphs and orthogonal relation on $\mathbb{F}^k_2$, the regret upper and lower bounds are optimal up to constant factors. 

main_review: In summary, the problem is significant for the subarea of graphical bandits, and the authors made non-trivial contributions to this problem, though there are still rooms for further improvements.

Originality: The techniques and methods used in this paper are novel. By making a deeper analysis on the problem and introducing the parameter $\delta^*(\cdot)$ of a graph $G$, the authors were able to show a better bound compared to $\delta(\cdot)$ that are commonly adopted in previous works (note $\delta^*(G) \leq \delta(G)$ for any graph $G$). 

Quality: Overall, this paper made non-trivial contributions to this problem and the introduction of $\delta^*(\cdot)$ can inspire future studies. In my opinion, it may be hard to make further improvements without using new techniques. Thus, although in general, there is still a $\frac{\log{n}}{\log\log{n}}$ gap, I think the results in this paper are good enough, especially for some special cases where the upper bound matches the lower bound (ignoring constant factors).

Clarity: The paper is well written overall but has some typos and formatting issues. For instance, Table 1 is surpassing the margin and needs to be restructured, and the reference in Line 63 is ??. 

Significance: The problem is significant, but this paper only makes significant contributions to some special cases. For General cases, the improvements are limited. 

In conclusion, my score lies between 6 and 7. I tend to give a score 6 for now due to the lack of practical motivations and numerical results. A typical motivation can be utilizing the information or data of the queried user's friends or connections, but this application may have potential privacy issues. It may help the readers if the authors can add more practical motivations and applications.

-----------------------------------------------------------------
After reading the response, the score is increased from 6 to 7.
limitations_and_societal_impact: Limitation: The improvements made by the authors do not cover most of the general cases, which has been discussed in the box Main Review. 

I do not find negative societal impact of this work as this work is pure-theory and focuses on a fundamental abstract problem.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper connects notions of the fractional weak domination number and the k-packing independence number with the graph bandits problem. Under these notions, the authors propose a new algorithm that achieves a fractional weak domination number dependent upper bound and also constructs lower bounds, including the main meta-lower bounds and other lower bounds in terms of different classical graph parameters. Therefore, tighten the gap between the upper and lower bound compared to the previous works. 
main_review: --Originality:
For the lower bound analysis, the technique to construct lower bound for regret via best-arm-identification problems is standard. One innovation here is that the authors use k-packing independence numbers to adopt these lower bound construction techniques into a graph structure.  Then by showing the relationship between the 1-packing independent set and the solution of the integral program defined in the paper, the author gets a fractional weak domination number dependent bound (Thm 3). The technique used in Thm3 seems purely related to graph theories. It looks interesting to me but I am not sure how novel it is in the graph theory area.

For the upper bound analysis, the choice of OMD framework, regularization functions, the estimator, and the exploration parameters are all standard techniques. One small innovation is that the exploration parameter u comes from the solution of a linear program, instead of simply a uniform distribution over some representative set.

Overall, I think this paper combines some well-known techniques from online learning and graph theory (or linear programming). The combination techniques themselves have some novelty. 

--Quality: 
All claims are well supported

--Clarity:
This paper is well written

--Significance:
This paper closes the upper bound and lower bound gaps for graph bandits and also discusses their results in several classical graph structures. So I think from a theoretical perspective, this contribution is meaningful.  

The technique's novelty here is nontrivial but somehow limited. 

--Questions: I wonder if this algorithm can directly extend to more adaptive settings [21, 5,19...] by combining with those existing techniques listed in the related work? If so that would be attractive.

limitations_and_societal_impact: The authors have adequately addressed the limitations
review_title: null

Meta-review: Several reviewers raised their scores after discussing with the authors.
Overall, we agree that the contribution of this paper is significant enough for better understanding the
minimax regret of bandits with graph feedback.
Please do incorporate all the suggestions from the reviewers into the final version.
Decision: Accept (Poster)