Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider the Best-of-Both-Worlds setting in Online Learning with Feedback Graph: the rewards of arms can be stochastic or adversarial and the feedback of them is described by a directed graph of arms. The authors show for strongly observable graphs, FTRL with the negative entropy regularizer and adaptive learning rates has optimal regret bounds up to logarithmic factors in both stochastic and adversarial settings. For weakly observable graphs, a more sophisticated regularizer give similar results.
strengths_and_weaknesses: - This is a great paper. The problem is important and challenging, but the authors give pretty simple and clear solutions. For strongly observable graphs, it is not surprising that entropy can be used for this setting, but how to properly tune the learning rates seems highly nontrivial. I roughly checked the proof and didn't find any issues. Overall the analysis is quite concise. For weakly observable graphs, the choice of the regularizer is more mysterious to me. Maybe the authors can comment more about this, for example, the intuition to add $(1-x)\ln(1-x)$ and $\sqrt{1-x}$ terms.   
- Besides suboptimal orders of logarithmic terms, one weakness is that the gap-dependent constants are still not optimal. For example, consider standard bandit feedback. The bound in this case is $\frac{\alpha(\ln T)^3}{\Delta_{\min}}$, which is not ideal once K is very large and there is only one small gap. I think it would be great to comment this somewhere or show some bounds of optimal stochastic algorithms in the table. 
questions: Can authors talk about whether it is possible to get bounds scaling with $\sum_{i\in S}\frac{1}{\Delta_i}$ for strongly observable graphs under this approach?
limitations: N/A
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 the best-of-both-world problem for bandits with feedback graphs.
It derives an algorithm which is up to log factors optimal in the adversarial regime and obtains reasonable regret guarantees in the stochastic regime.
The stochastic bound is sub-optimal with regard to log factors and instance dependent complexity, but it is still outperforming the best-known bound for best-of-both-worlds algorithms.
Additionally, it proposes best-of-both worlds algorithms in the weakly observable aka T^2/3 regime.
strengths_and_weaknesses: The math is sound and the presentation is clear.
There are technical novelties over the vanilla self-bounding regret analysis due to the fact that Shannon entropy is required for optimal regret in the adversarial regime.
An important limitation of this work is the existence of a very similar work (even up to the title): "A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs". 
The other work explicitly estimates the gaps in the stochastic regime and obtains a better stochastic bound. This work on the other side is purely using the self-bounding technique which simplifies the algorithm and allows for a straightforward bound for the corrupted stochastic setting. The analysis for weakly observable graphs is also unique to this paper here.
Overall, both paper build on the same literature and use very similar algorithmic techniques to obtain almost identical results.

questions: Are you aware of the extremely similar paper:
"A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs" ?
Given that you seem to have obtained almost identical results with very similar techniques in concurrent work, it might make sense to combine the two papers?

limitations: Theoretical work, no societal impact.
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 authors consider the online learning with directed feedback graphs problem and present algorithms based on the follow-the-regularized-leader approach, which achieve best-of-both worlds regret guarantees in both the fully observable and the weakly observable settings. 

The regret bounds presented in the paper are optimal up to polylog factors i advnersarial settings, and are polylogarithmic in $T$ in stochastic settings. The authors also prove regret bounds for the more general adversarial regime with a self-bounding constraint. 

In the fully observable case, the authors employ FTRL with a negative entropy regularization and an adaptive learning rate and exploration scheme to obtain regret bounds that scale with the feedback graph's independence number $\alpha$. In the weakly observable setting, the authors use a regularization which depends on a weakly dominating set, while employing a negative entropy regularization on vertices without self-loops, and Tsallis entropy on the vertices with self loops. In turn, the regret bounds obtained in the weakly observable case scales with the feedback graph's weak domination number $\delta$.
strengths_and_weaknesses: Strengths:
* The results presented in the paper improve upon currently known best-of-both-worlds regret bounds in the online learning with feedback graphs framework, and they are relevant in a very general setting of directed feedback graphs, as well as weakly observable graphs.
* In the fully observable setting, the authors show that FTRL with negative entropy regularization suffices in order to obtain nearly optimal regret bounds, by implementing a novel adaptive step size scheme. This shows that highly complex regularizers are not essential in order to obtain such regret bounds for feedback graphs, and consequently the technical analysis in the paper is very clean and concise.
* The authors present the first best-of-both-worlds regret bounds which hold for weakly observable graphs. while in the stochastic setting their bounds are sub-optimal, this result is highly non-trivial and is achieved with a simple algorithm which is an instantiation of FTRL with a regularizer that combines negative entropy and Tsallis entropy.

Weaknesses:
* The stochastic bounds presented in the paper are suboptimal in the following sense: For strongly observable graphs, the stochastic bound scales with $O(\frac{\alpha}{\Delta})$ which in some cases could be worse than the optimal bound which scales with $O(\sum_{i \in A} \frac{1}{\Delta_i})$ where the sum is over a maximum independent set, and $\Delta_i$ is the suboptimality gap of arm $i$. For weakly observable graphs, the stochastic bound includes an additive term which scales like $\frac{K'}{\Delta}$ where $K'$ is the number of arms with self-loops. In the worst case, this could scale linearly with $K$ which is known to be suboptimal.
* In the strongly observable setting, the algorithm requires the independence number of the feedback graph in order to appropriately tune the step sizes. Since computing the independence number of a graph is computationally hard, this presents a certain limitation of the algorithm. While this limitation also appears in previous works, I think the authors should mention the algorithm's dependence on $\alpha$.
* A few typos: In the abstract "follow-the-perturbed-leader" is mentioned instead of "follow-the-regularized-leader", in the statement of Lemma 1 the first appearance of $\psi_t(q_{t+1})$ should be replaced by $\psi_{t+1}(q_{t+1})$.
questions: * The definition of a weakly dominating set appearing in this paper seems to differ from the definition in previous works, such as Alon et al. [2015]. In their paper, a weakly dominating set is one which dominates the weakly observable vertices. i.e. those without a self loop which also don't have incoming edges from every other vertex. However, the authors define a weakly dominating set by one that dominates all the vertices with no self loops. This makes the weak domination number - according to the authors' definition - larger in the worst case than in the definition from previous works, and in turns makes the regret bounds the authors obtain for weakly observable graphs sub-optimal in another sense. I suggest the authors either match their definition of a weakly dominating set with the definitions from previous works and modify their analysis accordingly, or alternatively, discuss the discrepancy between the two definitions and the relation between the regret bounds obtained with each one.
* It is a bit unclear to me why the extra $\frac{K'}{\Delta}$ is necessary in the stochastic bound in the weakly observable setting. Since the set $V_2$ contains vertices with self-loops, i.e. fully observable vertices, instead of using Tsallis entropy on those vertices which seems to be what contributes this additive factor, why not just use the approach from the fully observable case? I.e, use negative entropy regularizer with the step size scheme described in Section 5. I'm not sure where the analysis breaks given this approach, as it seems that by Lemma 5 the regret breaks into a term which only depends on $V_1$ and a term which depends only on $V_2$ so both terms can presumably be handled separately. I would appreciate it if the authors could explain their choice of Tsallis on $V_2$ and why the approach I suggested wouldn't work.
limitations: The authors properly address most aspects regarding the limitations of their results, specifically the suboptimality of their regret bounds in stochastic regimes.
See the main review for remarks on other limitations which I believe were not properly addressed, such as the discrepancy between their definition of a weakly dominating set and previous definitions, and the required knowledge of the independence number in the fully observable setting.
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 design of best-of-both-worlds algorithms for the problem of online learning with feedback graphs. Online learning is a sequential setting which proceeds in rounds $t = 1, \ldots, T$, where in each round the learner issues a prediction, suffers a loss that corresponds to this prediction, and then obtains some feedback on the prediction. The goal is to control the regret, which is the difference between the cumulative loss of the learner and the cumulative loss of the best fixed prediction in hindsight. This version of online learning considers possibly partial feedback scenarios modelled by directed graphs where nodes are the available actions. In this setting, the feedback received by the learner after choosing an action is given by the loss of actions in the out-neighbourhood of the currently selected action. Best-of-both-worlds algorithms try to achieve optimal regret in both adversarial and stochastic scenarios simultaneously, where losses may or may not follow an underlying distribution. The authors extend previous work to more general feedback structures. They manage to design best-of-both-worlds algorithms for any strongly observable or weakly observable feedback graph, respectively, and prove near-optimal regret bounds for them. In particular, for strongly observable graphs with independence number $\alpha$, the bounds are of order $\sqrt{\alpha T}$ for adversarial losses and $\alpha \ln(T)^3/\Delta$ for stochastic losses, where $\Delta$ is the difference between the expected loss of the best arm and the second best arm. For weakly observable feedback graphs with domination number $\delta$, the bounds are of order $\delta^{1/3}T^{2/3}$ for adversarial losses and $\delta \ln(T)^2/\Delta^2$ for stochastic losses. 
strengths_and_weaknesses: Overall, the paper is well written and the results are new. However, the authors should take some care in addressing the typo’s in the paper, of which some are listed below. The authors provide sufficient motivations for studying the problem at hand. Not only do the results improve upon previous work in terms of regret, they are also more general  as the feedback graphs in this paper are arbitrary feedback graphs rather than restricted feedback graphs considered in previous work. For stochastic losses, compared to the previously best known result the improvement in the strongly observable case is a factor ln(T)^2 and an improvement in the leading factor, which changes from the clique covering number to the independence number. For the weakly observable case there were no previous best of both world results. The near-optimality of the regret bound for the proposed algorithms required an improved analysis on the performance of follow-the-regularized-leader (FTRL) with the Shannon entropy regularizer, while using a novel definition for the update rule of the learning rate at the same time. The above results are indeed not immediate to achieve. As the authors themselves state, this might be useful for different applications of FTRL with a Shannon entropy regularizer too.

Relevance:
Best-of-both-worlds algorithms have been of recent interest in online learning settings. Therefore, the submitted work is sufficiently relevant since it provides significant advances addressing the online learning problem with feedback graphs.

Clarity:
The results are presented in a clear manner and are well contextualised in the literature.

Weaknesses:
In both the weakly and strongly observable case the upper bounds for stochastic losses may be a factor $\ln(T)^2$ away from being optimal. However, the upper bounds improve greatly on previous work, and the lower bound in the weakly observable case probably can be improved. 

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

Meta-review: metareview: The paper received four reviews from experts in online learning, who all strongly support acceptance.  As summarized very well in the reviews, this is a well-written paper that makes a solid and elegant contribution to the line of work on best-of-both-worlds online learning.  The authors have effectively addressed the (relatively minor) concerns indicated in the reviews.  I wholeheartedly recommend the paper is accepted.

One issue brought in the reviews is the non-trivial overlap with a different paper entitled “A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs”.  While this situation did not affect the decision in any way, I urge the authors to properly cite this paper in their final version and discuss how it related to their contribution.
confidence: Certain
Decision: Accept