A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays

Summary

This paper studies the best-of-both-worlds (BOBW) algorithms for MAB with delayed feedback. Compared to previous results, it eliminates the need for prior knowledge on maximum delay $d_{\text{max}}$, and the regret scales with the number of “outstanding observations” ($\sigma_{\text{max}}$) rather than with the delay length as in the previous works. Technique-wise, this is achieved through a new round skipping rule, a new implicit exploration loss estimator, and advanced analysis.

Strengths

The regret guarantee is significant in the sense that it scales with the number of missing information, rather than how much it is delayed as in previous work. In the latter case, even if there’s only one single delay, it incurs linear regret if this delay is $T$, which however is safeguarded by the regret guarantee in this paper. Such phenomenon has been achieved soly in either stochastic or adversarial regime before, but not in BOBW. To achieve this, the authors propose new techniques in both algorithm design and regret analysis.

Weaknesses

1. I feel that the words "distribution drift/shift" comes from nowhere in the introduction. Its meaning is not clear to me in the context of delayed bandits, but no sufficient explanation is provided. A reader may not figure it out until the Analysis Section. 2. The authors use both “multiarm” and “multi-arm” inconsistently. The latter is commonly used. 3. The contribution summary may need polishing. Points 2-4 (Line 118) seems too detailed. Currently they are not informative, they could be merged, or not even necessarily included in the contribution summary in my opinion. 4. The author may consider elaborating more on Line 181-183, i.e., why the additional $K^{1/3}$ factor is a price for BOBW guarantee (in the analysis). This could be an interesting point to BOBW researchers. 5. When introducing Lemma 2 for the first time (around Line 202), it would be good to briefly talk about what are the key elements to achieve it, rather than let the readers figure it out in the long proof later. Is it due to the analysis (virtual rearrangement) only, or also the skipping rule and/or implicit exploration? 6. These two works on feedback-delayed bandits should be relevant, but they are not discussed in this paper. One in stochastic regime [1] and the other in adversarial regime [2]. References: [1] Yang, Yunchang, Han Zhong, Tianhao Wu, Bin Liu, Liwei Wang, and Simon Shaolei Du. "A Reduction-based Framework for Sequential Decision Making with Delayed Feedback." In Thirty-seventh Conference on Neural Information Processing Systems. 2023. [2] van der Hoeven, Dirk, Lukas Zierahn, Tal Lancewicki, Aviv Rosenberg, and Nicoló Cesa-Bianchi. "A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs." In The Thirty Sixth Annual Conference on Learning Theory, pp. 1285-1321. PMLR, 2023.

Questions

1. Why do some citations have no year? E.g., “analysis of Zimmert and Seldin” in Line 58 2. Is the word “outstanding observations” existing in the delayed-feedback literature or named for the first time by the authors? It is just the number of missing observations, right? If so, I personally just feel that the wording is not very informative/natural. 3. Is the idea of “skipping” reflected only through the regret analysis, or both the algorithm design and analysis? From Algorithm 1, I think it is the latter, but Line 86-89 seems to mean the former. 4. Since the BOBW guarantee is obtained through the self-bounding trick, can we directly obtain a regret bound for the intermediate $C$-corrupted regime?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes

Summary

This paper proposes a new best-of-both-world algorithm for bandits with a delayed feedback model. The results simultaneously achieve the latest upper bounds for delayed feedback in stochastic and adversarial (up to a factor). The algorithm design utilizes an implicit exploration estimator and the skipping set. The analysis contains new technical methods for handling the relationship between drifted and standard regrets.

Strengths

The reviewer thinks this paper is a nice piece of theoretical work. It has several strengths as follows, 1. This paper's introduction concisely and clearly discusses this work and its relation (both result and theoretical tool aspects) to previous work. This is very helpful for readers to understand the research background and new contribution. 2. The best-of-both-world theoretical results of this paper combine the known best stochastic and adversarial upper bounds (with a $K^{1/3}$) factor for bandits with delay and improve upon the latest results on the same topic.

Weaknesses

The reviewer is uncertain whether this paper reaches the NeurIPS bar for the following weaknesses reasons: 1. The algorithm design itself needs to be more novel. The only new component the reviewer notices is the implicit exploration estimator, which was also related to prior works in adversarial bandits. 2. The algorithm design is not optimized. For example, the skipping set $\mathcal{S_{t}}$ is always expanding, which is counterintuitive: (1) As the threshold $d^t_{\text{max}}$ is non-decreasing, there should exist observations, previous belongs to the skipping set, with delay less than the increased new threshold. Why does the algorithm design not add these skipped observations to the non-skipped set? (2) Even for observations belonging to the skipping set, when their observations are finally revealed, why does the algorithm not consider the kind of observations? If considered by the decision-making, both types of observations can help improve the algorithm's performance. Even if this modification cannot reduce the regret upper bound, it should be able to improve the algorithm's empirical performance.

Questions

1. The reviewer needs clarification on some proof steps. For example, by the definition of the drift regret, the benchmark is the estimated loss $\hat \ell_{i^*}$, but when it comes to the stability-penalty decomposition at the beginning of Appendix A, the benchmark becomes the actual loss $\ell_{i^*}$, which looks inconsistent.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Summary

This paper studied the best of both world algorithms for arbitrary delayed feedback. The proposed algorithm does not require prior knowledge of maximum delay $d_{\max}$ and avoids its linear dependence in the regret bound. To this end, they proposed the implicit exploration that works for the best-of-both-worlds guarantees. The key idea is to relate the number of outstanding observations $\sigma_{\max}$ so as not to rely on the boundness of delays.

Strengths

- The first proposal of implicit exploration for BoBW settings. The algorithm is based on FTRL with a hybrid regularizer where a skipping technique is employed, which becomes crucial for the BoBW guarantee. - When the maximal number of outstanding observations $\sigma_{\max}$ is smaller than maximum delay $d_{\max}$, the proposed method provided a much better bound than [Masoudian et al. 2022].

Weaknesses

I only see it for writing. The current main paper more focus on the explanation of the result comparison with [Masoudian et al. 2022]. Although the authors detailed a summary of technical proof in the main text, a more intuitive, and higher-level explanation of algorithmic parts would be appreciated when introducing the proposed technical scheme. For example, the paper does not provide a detailed explanation of the selection of regularizers or learning rates intuitively. For example, what makes analysis challenging due to aiming BoBW bounds could be more highlighted. I guess the additional challenge for dealing with stochastic cases, from [Zimmer and Seldin, 2020] that already uses the FTRL algorithm with a hybrid regularizer, has already been addressed by [Masoudian et al. 2022], but by missing these explanations, it would be hard for readers to see the clear picture of inherently technical challenges of BoBW algorithm for delayed feedback.

Questions

How can we interpret implicit exploration term $\lambda_{s,t}$? (Is this inspired by controlling the bias term due to an implicit exploration scheme in order to make it applicable to a best-of-both-worlds setting?)

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

n.a

Summary

The authors consider the multi-armed bandit problem with delayed feedback, where the loss of a chosen arm is observed several rounds later. In this setting, nearly optimal algorithms have been developed for both stochastic and adversarial environments, as well as best-of-both-worlds (BOBW) algorithms that perform well in both regimes. However, the regret upper bounds of existing BOBW algorithm by Masoudian et al. (2022) has gaps compared to the regret upper bounds of algorithms designed specifically for adversarial environments (Zimmert and Seldin, 2020) and stochastic environments (Joulani et al., 2013) and in particular the algorithm by Masoudian et al. require the prior knowledge of the maximal delay before the game starts. To address this issue, the authors propose an algorithm that achieves a regret upper bound without knowing the maximal delay in advance. To achieve this, the authors introduce a new framework of implicit exploration, demonstrating that this framework can be effectively combined with techniques that skip observations associated with excessive delays.

Strengths

The differences from existing research are thoroughly discussed. Technically, the introduction of the implicit exploration framework to achieve BOBW regret bounds without using the maximal delay is novel. Fine-tuned adjustments are made to achieve BOBW while employing implicit exploration. Additionally, how the parameter $\lambda$ is utilized in the proof is clearly explained and discussed throughout the proof.

Weaknesses

One concern is that the differences between this paper and existing research might not be sufficient. While the authors propose an algorithm that works in both adversarial and stochastic environments, the foundation for handling excessive delays seems to have been largely established by Zimmert and Seldin (2020) (and Masoudian (2022)). I was unable to check all the proofs in detail, but they appear to be generally correct. However, there seems to be large room for improvement in the overall explanation. Many explanations are not contextualized, making the proofs difficult to read. For instance, Lemmas 11 to 13 are directly taken from Masoudian et al. (2022). However, the algorithm in Masoudian et al. (2022) differs from the one proposed by the authors, so it is unclear whether these results are directly applicable.

Questions

The authors are expected to discuss to what extent the results from Zimmert and Seldin (2020) and Masoudian et al. (2022) can be used in their study.

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

not applicable

Response

I appreciate the authors' response. Since the authors addressed my concerns, I will raise the score from 5 to 6. However, as with bmXx, I expect improvements in the overall writing, particularly in the appendix.