Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studied the problem of multi-armed bandits problem with delayed feedback. Most of the traditional algorithms focus on either stochastic or oblivious adversary settings, thus in the case where the setting is unknown, these algorithms can not achieve optimal pseudo-regret bound. In order to overcome this problem, this paper provided a slight modification version of Zimmert and Seldin [2020]'s algorithm (adding a constant term $\eta_0$ and $\gamma_0$ to the learning rate). By doing that, it can achieve near-optimal regret in both stochastic and oblivious adversary settings.
strengths_and_weaknesses: I like the overall idea of the paper to extend the best-of-both-worlds algorithm into a delayed feedback setting. However, I have a few concerns over the contribution of this paper.

As the algorithm is very similar to Zimmert and Seldin [2020]'s algorithm, the first regret bound analysis against oblivious adversary is also very similar to the analysis in Zimmert and Seldin [2020]'s paper. Furthermore, due to the modification, the newly derived regret suffers another term, $d_{max} K^{1/3} \log(K)$ compared to the regret of the original algorithm. 

The second regret bound against stochastic setting is interesting and novel as it provides a new feature for the Zimmert and Seldin [2020]'s algorithm (it also requires a new technique of controlling drift of the playing distribution over arbitrary time intervals). 

The third contribution about adversarial regret lower bound, although novel is in my opinion not well connected to current paper since Algorithm 1 does not consider skipping-based refined regret or achieves any regret bound that matches the new lower bound. 

Therefore, the main contribution of the paper is to provide a regret bound for a modification of Zimmert and Seldin [2020]'s algorithm against a stochastic setting with a small sacrifice in the regret against an oblivious adversary.  Even though I think this is new and novel, I am unsure whether it is significant enough for publication in Neurips. 

minors: There are a few terms mentioned in the paper that I can not find the definition (e.g., uniform delays, minimax regret).



questions: Can the authors comment on the existing lower bound regret in the stochastic setting if they exist one?
limitations: There is no potential negative 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: This paper present an algorithm which achieves the best of both worlds guarantee with delayed feedback between the adversarial world and stochastic world. More specifically, the authors consider two delay settings (fix delay and arbitrary uniform delay) of multi-armed bandit problem, and propose two algorithms that achieve  $\widetilde{O}(log K + K^{1/3} )$ (the ideal stochastic bound should be $\widetilde{O}(log K)$) regret within stochastic setting where the loss are sampled i.i.d from a fixed distribution, while ensuring $\widetilde{O}(\sqrt{K})$ in the worst case. The algorithms applies the FTRL framework with specific hybrid regularizers and careful learning rate scheduling, which is similar to those from previous works. However, with the novel analysis technique (Lemma 4), the authors show that the proposed algorithms actually achieve the best of both worlds. 
strengths_and_weaknesses: Unlike the original multi-arm bandit problem which receives the feedback immediately after playing an arm, the delayed feedback setting is much more complicated as the learner has to maintain sufficient robustness with missing information, which may lead to drastic different strategy. Moreover, it is even harder to achieve best of both worlds results in this setting, which requires the learner to carefully balance the exploration and exploitation. 

To the best of my knowledge, this is the first best of both world results of multi-armed bandit problem with the delayed feedbacks. The analysis is quite different from the approach (and "cheating-regret"-"drift" decomposition) from $Gy\ddot{o}rgy$ and Joulani (2021)  and the other approach of Zimmert and Seldin (2020), with the help of the powerful Lemma 4 which controls the drift of the playing distribution by the time-varying hybrid regularizer to handle the arbitrary delays (arbitrary uniform or fixed). Besides, the proof of Lemma 4 is very interesting and may be applied in many related problems. 

This paper does not have any specific weakness point. Overall, the writing is clean and well-organized. 
questions: 1. Is it able to achieve Lemma 4 with episodic MDPs? 

2. Is it possible to improve the $d_{max} K^{1/3} \log K$ and $d K^{1/3} \log K$  terms in the regret bounds for the stochastic setting? What's the main difficulty in removing such terms from the regret bounds? Is it possible to use SAPO or EXP3++ approaches to avoid these terms? 

3. Is it possible to achieve similar results with arbitrary delays with respect to the total delay $D = \sum_{t=1}^{T} d_t$? 

4. Any corruption result? 
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 study considers the multi-armed bandit problem with delayed feedback.
For this problem, the authors propose a best-of-both-worlds algorithm that achieves minimax optimal regret for adversarial regimes as well as logarithmic regret for stochastic regimes.
This result is achieved by modifying the update rules for learning rates of an existing algorithm proposed by [Zimmert and Seldin, 2020].
The proposed approach works even for problems with arbitrary (round-dependent) delays.
strengths_and_weaknesses: Strengths:

- The paper makes solid contributions to important problems.
- The paper is well structured and easy to read.
- The proposed approach appears simple and practical.

Weaknesses:

- Novelty in algorithms and analysis techniques is somewhat limited.

Comments:

Delayed feedback and best-of-both-worlds algorithms are both topics of practical importance.
I consider this paper to be of high importance because it provides a solid contribution to these two topics.

The proposed algorithm and analysis techniques are based on existing ones and have limited novelty.
However, there are several nontrivial steps in the analysis that require delicate attention, which the authors address in a sophisticated manner.
questions: - Are there any known lower bounds for stochastic settings with delayed feedback?

- Can the proposed algorithm handle stochastic regimes with adversarial corruption or adversarial regimes with self-bounding constraint given in [Zimmert and Seldin, 2021]?
Since the analysis is based on this technique, it appears to be easily extendable.
If not, I would like to know why.
limitations: The limitations are adequately addressed.
review_title: null

Meta-review: metareview: The paper makes a solid technical contribution in the online learning literature, providing the first best-of-both worlds algorithm for online learning with delayed feedback. Despite building heavily on existing algorithmic ideas, the paper involves some critical technical novelties that enable their results.
confidence: Certain
Decision: Accept