- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This work studies best-of-both-worlds multi-armed bandits (MABs) with delayed feedback. The main contribution is that the authors develop a purely follow-the-regularized-leader (FTRL)-based algorithm to obtain a BOBW guarantee with regret in the stochastic regime. The significance of this regret is that it eliminates the term, which is suffered by all the previous FTRL-based approaches for BOBW delayed MAB and is only eliminated by the more complicated detect-and-switch-based method in [1]. That said, the downside of the main result is that a term remains in the regret for stochastic and adversarial regimes. This term can be much larger than the term in the previous FTRL-based BOBW result for delayed MAB in [2]. Further, the previous detect-and-switch-based BOBW result for delayed MAB in [1] doesn't have any such remainder. Besides, the tuning of the learning rate for this algorithm requires the knowledge of , which is not required by the previous FTRL-based BOBW algorithm in [2].
Critical strengths
- Result: The proposed FTRL-based BOBW algorithm for delayed MAB eliminates the term in the regret for the stochastic regime of previous FTRL-based approaches. Prior to this work, such refinement was only known to be achievable for the detect-and-switch-based BOBW algorithm for delayed MAB in [1], yet this kind of method is less adaptive compared to the FTRL-based approach, as it requires explicit environment detection and switching, and its analysis is often more complicated than the FTRL-based ones.
Critical weaknesses
-
Result: Though a remainder of in the regret for stochastic regime is eliminated. Several other concerns arise. Specifically,
- Such a kind of improvement has already been shown to be achieved by the method in [1], though it is a detect-and-switch-based one. In light of this, the significance of the result is somewhat limited.
- More importantly, an additional remainder of appears in both the regret for stochastic and adversarial regimes. The downside of this term is that it might be much worse than the corresponding remainder in the previous FTRL-based BOBW algorithm in [2], and there is not even any such kind of term in the result of the detect-and-switch-based algorithm in [1]. Given this, this somewhat makes people feel that the improvement comes at the cost of introducing a dependence on a worse remainder, which thus again limits the significance of the result.
-
Position and Presentation: Overall, this work is well written. Nevertheless, I personally feel that the title doesn't seem to be very appropriate. In particular, at first glance, this title makes people feel that this work attains the SOTA result. However, as discussed above, the regret in the stochastic regime in this work is inferior to the result of [1]. In the adversarial regime, the leading term in the regret of this work indeed shaves off a multiplicative factor compared to that in [1], yet it additionally has a remainder of . Therefore, it is also hard to say that the regret in the adversarial regime in this work truly improves upon that in [1]. Collectively, the title doesn't seem to really reflect the position of this work against existing work. In other words, if the result in this work is 'nearly optimal' as claimed in the title, then [1] can also be called 'nearly optimal'. Thus, I think this title is not so informative, and it is actually a bit misleading.
In the BOBW literature, it is rather challenging to obtain regret upper bounds that fully match the lower bounds, and thus it is kind of a convention in the literature to call such results 'nearly optimal', which I think is understandable and acceptable. However, this still doesn't contradict what I said above, since if there are already some papers on BOBW delayed MABs and yet the latest paper claims to be 'nearly optimal', there is an implication in the title that the result in this latest paper truly improves on the results in previous works. However, this is not the case, given the results in [1].
-
Knowledge of : The proposed algorithm requires the knowledge of , which is not required by some FTRL-based approaches (say, [2]) and the detect-and-switch-based approach in [1].
[1] Schlisselberg et al. Improved best-of- both-worlds regret for bandits with delayed feedback. NeurIPS, 25.
[2] Masoudian et al. A best-of-both-worlds algorithm for bandits with delayed feedback with robustness to excessive delays. NeurIPS, 24.
Questions for authors
Please see the weakness part above.
3 comments
I thank the authors for their responses, and I would like to maintain my rating for this paper. Also, I'm sorry for the missing references in my original review; I have now added them.
Thank you for the quick response. No problem for the missing references, we could guess from the context what you were referring to.
Just to learn: do you consider the new title and positioning an improvement?
We address some of your concerns in a general comment. In short: Schlisselberg et. al. (2026) require knowledge of T. Without this knowledge their bound is of order ∑i=i⋆(Δ(i)log(T)2+KσmaxΔ(i)) in the stochastic setting and consequently their result is asymptotically suboptimal in both the adversarial and stochastic setting. We have added a standard idea to improve the dependence on dmax.
About the title. We indeed adopted the convention that is standard in the literature. For the new version we opted for a more descriptive title: Tracking the Drift: Improved Best-of-Both-Worlds FTRL for Delayed Bandits.