Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides an algorithm for the combinatorial semi-bandits that achieves regret bound with three well known notions of data dependence regret in adversary regime. Besides that the provided algorithms attains best of both worlds result (Zimmert et al., 2019) up to a logarithmic factor in adversary setting. Their algorithm in stochastic regime with adversarial corruption achieves $O(\log T + \sqrt{C\log T})$ regret with respect to $T$ as the time horizon and $C$ as the corruption budget. Furthermore, they improved existing regret bounds for adversarial linear bandits to achieve path-length regret bound which in worst case is tight up to a logarithmic factor.
main_review: ## Semi-bandit Part of the Paper
 As it is mentioned in the paper, the key idea of provided algorithm for combinatorial semi-bandits is to combine the zero powered of Tsallis algorithm provided by Zimmert et al. (2019, 2021)  to _optimistic prediction for the losses_ in order to get the best of both world result from the former and data dependent from the later approach. 

__Significance and Originality:__

This idea seems interesting and elegant to me. Also circumventing the challenges for the analysis is also a good contribution. However, I have one important issue with the mentioned claims about improvements over Zimmert et al. (2019).
 - Result of the paper for stochastic with adversarial corruption is $O(\log T + \sqrt{C\log T})$  whereas the authors claim Zimmert et al., (2019) , with some straightforward modification of their proof, achieve $O(\log T + C)$. By contrast with the same self-bounding analysis provided by Tsallis-INF paper (Zimmert and Seldin, 2021) , where this paper uses the same analysis approach, it is quite easy to show that  Zimmert et al., (2019) algorithm in this intermediate regime obtains $O(\log T + \sqrt{C\log T})$. The authors need to be more transparent about this point since they are also using the same self-bounding technique for obtaining $O(\log T + \sqrt{C\log T})$ bound. In general there is a work by Masoudian and Seldin (2021)  titled: "Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits" that achieves even better regret for the self-bounding analysis which is $O(\log T + \sqrt{C\log T/C} )$.

Taking this point to account, Zimmert et al. (2019) algorithm in stochastic and stochastic with adversarial corruption regimes has the same performance as Algorithm 1 in the paper. On the other hand their algorithm in adversarial setting has tight regret bound while Algorithm 1 has additional multiplicative factor $\sqrt{\log T}$ in the regret. Moreover the results on size-invariant is almost the same as Zimmert et al. (2019). So the only improvement is the data dependent bound for the adversary regime. 


Still I consider this improvement as a good contribution as long as I can be convinced that the Zimmert et al. (2019)  is __not__ able to attain such a bound in _easy_ environments. To be more precise I would like to see a good discussion and also experimental results to support the inferior performance of Zimmert et al. (2019) algorithm in  _easy_ environments and obviously the superior performance of proposed algorithm.



__Quality:__
The proof generally follows self-bounding analysis by Zimmert and Seldin (2021) and optimistic predictors analysis by Wei and Luo (2018) and seems sound, however I did not track the full calculations in the supplementary materials.


## Linear Bandit Part of the Paper
The last section of the paper regarding the linear bandit seems incoherent to me since the major part of the paper is about how to obtain and analysis new algorithm by combing Zimmert et al., (2019) and optimistic loss predictors. I see that the authors aims obtain data dependent bound for linear bandit similar to semi-bandit, however, for the non-expert reader it is hard to follow this short section since no background and intuition about provided algorithms and regret bounds analysis is provided.

__Significance and Originality:__

The analysis of regret idea has no novelty since it is straightforward by just combining two existing bounds for regret. Achieving path-length regret bound for linear bandit is not significant since as the authors mentioned there are already two data dependent bounds for this problem based on _total quadratic variation of losses_ and _cumulative loss for optimal actions_ achieved by an algorithm provided by Ito et al., (2020). The worst case of these bounds are same as the path length regret bound, besides that there are rare cases that path length regret would benefit us over two former ones. So I consider this as a minor contribution.



__Clarity of the Paper:__
- Generally the paper is well written and easy to read. But the last section on Linear bandits seems irrelevant and so vague since there is no provided background, intuition, discussion and … about the subject. Theorem 3 in this section is vague and there is undefined variable in it and need to revised.


limitations_and_societal_impact: __Limitations:__


- The paper in stochastic and stochastic with adversarial corruption regimes implicitly uses the uniqueness of the best action. This is needed for the self-bounding analysis and must be mentioned as a clear assumption. 

- There is a small issue about using “best of three worlds” term. The best of one world result implies there is no better result than that and in other words there must be a matching lower bound for the result. However, obviously the stated result for stochastic with adversarial corruption is not minimax optimal (consider $C \geq T/ \log T$) so in this world the achieved bound seems a rather  good bound but is not the best.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an optimistic FTRL-based algorithm that achieves the near-optimal regret for semi-bandits simultaneously in terms of a variety of path-length(variation) instance in adversarial setting, gap in stochastic setting and corruption in the intermediate setting. It also achieves the near-optimal regret for linear-bandits simultaneously in terms of path-length(variation) in adversarial setting,
main_review: --Originality:
This work is based on the classical optimistic FTRL framework with a hybrid self-bounding regularizer. Unlike the previous works which mostly use doubling tricks or simply time-varying learning rate, It proposes more adaptive, entry-wise, learning-rate type parameters with rigorous analysis to achieve the best of many worlds. I think such modifications are novel.

But the main limitation of novelty is that most initial-stage proof steps (Lemma 1, Lemma 2) are using the standard optimistic FTRL techniques.  And given [Zimmert et al. 2019], [Wei and Luo, 2018], this hybrid log-barrier idea is not very surprising to me.

--Quality:
This submission is technically sound, all the claims are supported.

But one concern to me is that it seems by using a log-barrier type regularizer instead of Tsallis entropy with power 1/2 regularizer, the authors are unable to get a finer regret. (In [Zimmert et al. 2019], they have $\sum_i 1/\Delta_i$ for the full-combinatorial set and fixed-size set, where here it seems to be $m/\Delta_{min}$. If I am correct, I think the author should mention this difference.

--Clarity:
The paper is overall well-written. There are several suggestions:1\ In line 271, it says $\gamma_{ti}$ which I believe should be $\beta_{ti}$ 2\It would be better if you could give some intuitive explanations on $\beta_{ti}$, something like how the two terms in $\alpha_{ti}$ directly connect to equation (7) (8).

--Significance:
I think the best-of-many worlds results are important and the entry-wise adaptive learning rate idea is inspiring.
limitations_and_societal_impact: As I wrote above, I would like authors to discuss more on the influence if not choosing Tsallis entropy with power 1/2.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an algorithm that obtains multiple data-dependent regret bounds for semi-bandits simultaneously with optimal regret bounds in the stochastic and intermediate regimes.

Additionally they propose an adversarial linear bandit algorithm that obtains several problem dependent regret bounds simultaneously such as optimal path length bounds.
main_review: This paper extends recent results for the K-armed bandit setting derived in the COLT2021 submission:
"Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds", to combinatorial semi-bandits.
It combines the same base regularizer (log-barrier) with optimistic FTRL as in Ito 2021, together with the hybrid regularization as in Zimmert et al for semi-bandits.
The paper is well written and the results seem fine.
It recovers the optimal stochastic and adversarial guarantees, as well as a multitude of improved problem dependent regret bounds.

While I think the results are useful and especially the linear bandit results are novel, I am missing a discussion about the relationship to the paper mentioned above. It is unclear to me how much genuine novelty the adaptation to semi-bandit brings compared to previous work. 
The paper also lacks a justification for the hybrid regularization. In Zimmert et al., this was introduced mainly to deal with the $m\gg d/2$ case, which the authors do not explicitly care about here. Since the hybrid part adds some extra computational complexity, especially in more general action sets, there should be a strong technical necessity to keeping it.

Minor:
The authors claim that it is unknown if Zimmert et al. also obtains $\sqrt{C}$ bounds. Since they use the same self-bounding regret technique as this paper here and previous papers, it is quite obvious that they do. (The paper is simply older than when the $\sqrt{C}$ bounds first appeared.)
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the hybrid regret bounds for combinatorial semi-bandits (in stochastic, stochastic with corruption and adversarial settings simultaneously) and linear bandits (w.r.t. three different parameters). The paper improves the previous results by combining optimistic predictors with FTRL and the alg. of tracking the best linear predictor.
main_review: Originality: The task has been studied before and this work proposes a new method to improve the previous results. It might seem that the proposed method is a direct combination of known results. The contribution of this work highly depends on how difficult it is to combine the known methods. It would be important to address the main challenges of combining these methods and characterize the novelty.

Quality: All claims are well supported.

Clarity: The submission lacks discussion and explanation.  In section 4 and 5, it seems that the paper just lists the algorithms and the quantities without much explanation. For example, when comparing the proposed algorithm with the existing one, the paper does not explain why these changes improve the results. When discussing the reason for using a log-barrier regularizer instead of Tsallis entropy (Line 273-278), it is hard to understand it without checking other works.

Significance: The significance of this work is not obvious to me.

-------------------------------------------------------------------------------------
The authors addressed my concerns about the technical novelty of this submission. I am happy to raise my score. I hope the authors could add more discussion in Sec 4 and 5 and address the difference between the algorithms in this work and those in previous work.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The reviewers agree that this is an interesting and significant contribution.
Decision: Accept (Poster)