- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies corruption-robust stochastic bandits and improves the regret analysis of Tsallis-INF. The main result removes a log term from the corruption-dependent regret term, obtaining an dependence under a conditional gap-shortfall model without changing the algorithm. The paper also provides near-matching lower bounds and applies the result to improve regret guarantees for bandit learning in zero-sum games.
Critical strengths
- The paper addresses a gap in the analysis of Tsallis-INF. It removes a log term in the corruption-dependent regret term without modifying the algorithm.
- The paper provides a relatively complete theoretical treatment around the main result. It gives lower bounds and applies the new analysis to obtain improved regret guarantees for zero-sum games.
Critical weaknesses
As acknowledged in the AI use statement section, this paper relies heavily on generative AI throughout both the research and writing process. My main concerns with the paper are as follows.
- The results are incremental. The central result is essentially an improved analysis of the existing Tsallis-INF algorithm that removes a log term from the original regret term. The algorithm (Tsallis-INF) itself is unchanged.
- The log-free result relies on a per-round conditional gap-shortfall condition, which is strictly stronger than the terminal self-bounding condition. Thus, the paper does not resolve whether the log term can be removed in the full self-bounding class.
- The improved Nash-regret bound follows by substituting the new corruption bound into an existing reduction. Besides, the strongest matching result is restricted to games in a small-gap regime, while full matching for is not established.
- The presentation is unnecessarily dense and fragmented. The focus of the paper is relatively simple—showing that a log term in the regret bound of Tsallis-INF can be removed. But the paper presents this result in a much more complicated way than necessary. For example, the abstract is dominated by regret rates, lower-bound regimes, and game-theoretic consequences, with very little high-level intuition. Similarly, Eq. (1) introduces 6 notations all at once, although some of these quantities only become relevant later in the lower-bound discussion. The main text also repeatedly interleaves model comparisons, upper and lower bounds, game applications, and proof intuition before the central story is fully established.
Overall, I find the technical contribution limited, the main improvement relies on a more restrictive setting, and the paper is poorly presented. I therefore recommend rejection.
Questions for authors
See above
2 comments
Thank you for your response and your clarifications. I wish you the best with the revision.
Thank you very much for the review, and for pointing out concretely where the presentation is problematic (the abstract, Eq. (1), and the mixing of model comparisons, bounds, game applications, and proof intuition in the main text). These comments are very helpful for the revision.
On the presentation. We agree with the criticism. The manuscript was not edited enough, and it is dense and fragmented as you point out. This needs a major rewrite, which cannot be done properly during the discussion period, so we have decided to withdraw the submission and revise the paper carefully.
On the use of generative AI. As disclosed in the AI use statement, we used generative AI, including for the central step: the improved upper bound came out of AI-assisted work. We had been working on this problem for several years. We expected that the logarithm is necessary, and we were trying to prove a matching lower bound. So the result was a surprise to us, and we wrote it up quickly because we thought that people working on the same problem would want to know it early. We have checked every step of all the proofs ourselves, and we take full responsibility for the content.
On the technical points (1–3). We agree with the facts in these points. The algorithm is unchanged and the contribution is an improved analysis. The result needs the per-round conditional-gap condition, and the full self-bounding class remains open. The game upper bound is obtained by plugging our bound into an existing reduction, and full matching is shown only for 2×2 games.
We would only like to add one remark on point 3. In the game bound, the coefficient of logT improves from O(H/γ) to O(H), which does not depend on the column gap γ, so the asymptotic behavior changes. This coefficient is tight up to a constant for two-row games (Theorem 5). In the revised paper we will make the scope of the results clear from the beginning.
Thank you again for your time and for the detailed feedback.