Venue: NeurIPS 2022 Conference

Reviews:

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 studies the multi-armed bandit problem with graph feedbacks where the learner would receive the loss information of all the arms $j$ that $e(i,j) \in G$ after selecting arm $i$, where $G$ here is the feedback graph. The proposed algorithm aims at achieving the best of both worlds guarantee, that is, achieving $\widetilde{O}(\log T)$ regret with stochastic losses while ensuring worst-case robustness $\widetilde{O}(\sqrt{\alpha T})$ where $\alpha$ here is s the independence number of the feedback graph. 

The idea of the proposed algorithm originates from the EXP3++ algorithm for stochastic and adversarial bandits, which achieves the near-optimal best of both worlds result for normal multi-armed bandits. To extend the EXP3++ algorithm to the graph feedback setting, the learner takes the idea of EXP3.G which was designed only for adversarial graph feedback, and build up a novel exploration scheme to carefully estimate the gaps, in order to control the magnitude of exploitation and exploration. 


strengths_and_weaknesses: The paper shows that the best of both worlds guarantee can be achieved by EXP3++ approach for weakly observable feedback graphs. Moreover, it seems that the algorithm can achieve $O(\sqrt{\alpha T})$ regret for adversarial losses while having more logarithmic terms for the stochastic setting. The specific contribution is the new exploration scheme and may be applied in other questions. 

This paper does not have any specific weakness. The writing is clean and well-organized. 
questions: 1. Though the $\frac{1}{\Delta^2}$ term in Theorem 3 seems inevitable (as it also appears in EXP3++), is it possible to drop this term as the some best of both worlds results of MAB (including BROAD of Wei and Luo (2018) and Tsallis-INF of Zimmert and Seldin (2019)) do not have this term. 

2. Is it possible that SAPO approach could achieve better regret bounds? 
limitations: None.
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 studies online learning in a new setting of directed graph feedback. By combining the ideas of EXP3++ and EXP3.G, they suggest an algorithm, EXP3.G++ that can achieve near-optimal regret bound in both stochastic and oblivious adversarial settings.
strengths_and_weaknesses: I enjoyed reading the paper and all the results are sound and well presented. The regret bound for both adversary and stochastic settings improves the previous results (Erez and Koren (2021)) by log(T) factors and achieves a near lower bound guarantee. Further, the authors also provide an extension for changing the feedback graphs and provide a regret bound for EXP3.G++ in this case.
questions: Can the authors commend on the performance of EXP3.G++ in extreme cases of bandit and full information? 

Can the authors commend the applications of graph feedback (especially directed graph feedback) in real-world situations?

limitations: There is no 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 considers the problem of achieving best-of-both-worlds guarantees in the bandits with graph feedback. Specifically, the authors propose an algorithm based on a combination of EXP3.G [Alon et al., 2015] designed for classic bandits with graph feedback problem and EXP3++ [Seldin et al., 2017] designed for getting best-of-both-worlds for MAB. In the adversarial environment, they achieves $\tilde{O}(\sqrt{\alpha T})$ near optimal regret and $O(\max_I \sum_{i\in I}(\frac{\ln^2 T}{\Delta_i}))$ regret bound. The algorithm can also be extended to the time-varying feedback graph setting and achieve the corresponding regret bounds in both the adversarial and the stochastic setting.
strengths_and_weaknesses: Strength:
- The paper is very well written and the designed algorithm is intuitive and well explained.
- This paper improves upon the previous work by [Erez and Koren 2021] in both the adversarial regret bound and stochastic regret bound. Specifically, in the adversarial environment, the obtained regret bound is optimal ignoring logarithmic factors.
- From the algorithm perspective, the algorithm generalizes the EXP3++ algorithm, which works for MAB problem, to graph bandits with a new specific exploration set, which is a maximal independent and dominating set constructed according to the empirical gap.
- I checked the proofs for each theorem in the main text and the appendix and they look correct to me.


Weakness:
- One issue is about the optimality of the regret bound in the stochastic environment. I thought that the instance-optimal regret bound in the stochastic graph bandits is O(c\ln T) with c defined by an optimization problem with respect to the graph structure. I wonder how large the gap is between the instance-optimal regret bound and the bound derived in this paper?

- One minor issue concerns me is the novelty of this paper as the algorithm generalizes the EXP3++ algorithm with a new but intuitive exploration over the nodes. Based on the exploration, it can be shown that each node can be explored with probability $1/t\hat{\Delta}_i^2$ as some node with smaller gap will be chosen in the exploration set according to the construction. For the other derivations, they seem similar to the analysis in [Alon et al., 2015] and [Seldin et al., 2017].

- Another minor issue I do not understand is that why the results presented by the author for the fixed graph setting has $\tilde{\alpha}$ dependence in the adversarial regret bound while this can indeed be improved to $\alpha$ as shown in the appendix with an additional $\ln T$ factor. I think here the improvement from $\tilde{\alpha}$ to $\alpha$ is more important as this could be an improvement of a factor of $K$ for some specific graph.

Typos:
- line 483: $\alpha_s$ -> $a_s$
- line 575-576: The first inequality should be $\leq\frac{1}{2}n\lambda$ instead of $\geq n\lambda$.
- line 632: $1+\ell_{s,i^*}$ -> $1+\tilde{\ell}_{s,i^*}$
questions: - Could the authors explain more about the relationship between the obtained regret bound in the stochastic environment and the instance optimal regret bound in this environment?
limitations: Yes, the authors addressed the limitations of the 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 online learning with feedback graphs and present an algorithm achieving (almost) best-of-both-world regret bounds in stochastic and adversarial environments. The core idea is a combination of the EXP3++ algorithm (providing adaptivity between regime) and the EXP3.G algorithm (exploiting feedback graphs) and a novel exploration scheme which exploits the structure of the graph. The results are extended to the time-varying feedback graphs.

strengths_and_weaknesses: Strengths: The paper is well written and easy to follow. The results are interesting and in my opinion, contribute significantly to the community. While the proposed algorithm is built upon previously known algorithms, the presented exploration scheme is, as far as I know, novel and provides interesting insight. 

Weakness: No significant weaknesses. Two minor comments/suggestions: 1) It seems that there is still room to improve the complexity of Algorithm 2; 2) some numerical experiments comparing the proposed algorithm with non-adaptive benchmarks (showing the trade-off of adaptivity and performance) could be interesting. 




questions: - Pseudo codes Algorithms 1 and 2 are not clear when standing alone: it might be better if it is indicated clearer where Algorithm 2 (and Equations (2)-(3)) is injected to Algorithm 1.

- It is a little bit confusing that in Line 216, the observability probability is said to be lower bounded by  $(\beta \log t) / (t \hat{\Delta}^2 )$ in the stochastic case but then in Equation (4), it suggests that this might not be the case in general. My understanding for this is that in stochastic case, we can tune the parameters such that $(\beta \log t) / (t \hat{\Delta}^2 )$ is indeed the minimum of the 3 terms of (4), is this correct? 

- The wording in Theorem 2 makes it seem unnecessarily limited: from proofs in Appendix B, results of Theorem 2 should work with any gamma and beta such that epsilon = 1/2 $\sqrt(\lambda \log K/ (t K^2))$, right? The specific choice of gamma and beta is for the purpose of achieving the bounds in Theorem 3, right? Personal opinion: one theorem covering 2 cases (such as Theorem 4) would be preferable. 

- The statement that the complexity of Algorithm 2 is O(K^3) seems a little bit overkilled, should it be O(K^2) instead (given an efficient sorting algorithm O(KlogK)? It seems that this is related to the "minimum weight cover set problem" so it might be interesting to look into the literature to reduce the complexity further. 

- A small speculation: Section 6 deals with the time-varying feedback graphs in an informed setting. I wonder if this can be extended even further to the case of uninformed setting, e.g., by bounding with MAS number similarly to Alon, Noga, et al. "Nonstochastic multi-armed bandits with graph-structured feedback."  (2017) or at least in some special cases where the precise graphs are unknown when making decisions but we know that they belong to a certain class such as in Vu et al. Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek (2020) (note that these references are not cited in the current version). 


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

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