acceptodds
Under review as a conference paper at ICLR 2027

Logarithm-Free Corruption Bounds for Tsallis-INF

Abstract

Tsallis-INF simultaneously attains logarithmic stochastic regret and minimax adversarial regret, but existing corruption-dependent analyses contain a logarithmic factor inside the square-root corruption term. We remove this factor under a conditional gap-shortfall assumption that includes stochastic bandits with adaptive adversarial corruptions. For a unique reference arm with arbitrary positive gaps , write and . We prove that both the importance-weighted and reduced-variance versions of Tsallis-INF satisfy , where is pseudo-regret on the observed losses against the best fixed arm in expectation and is the expected corruption budget. The algorithm requires no knowledge of the gaps, budget, or horizon. Our analysis bounds the integrated trajectory of the sampling probabilities. A common normalization potential handles changes in the ordering of the arms, a favorable drift absorbs normalization noise, and a dyadic activation schedule accounts for heterogeneous gaps using a single shared budget. An equal-gap lower-bound construction shows that the square-root corruption term is necessary in a specified parameter regime under an expected budget.

Primary area:
learning theory
Keywords:
multi-armed bandit, corruption robustness, best of both worlds

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_7cYROpenReview ↗
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 O(CH)O(\sqrt{CH}) 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
  1. 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.
  2. 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.

  1. 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.
  2. 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.
  3. The improved Nash-regret bound follows by substituting the new corruption bound into an existing reduction. Besides, the strongest matching result is restricted to 2×22\times2 games in a small-gap regime, while full matching for K>2K>2 is not established.
  4. 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. I believe the manuscript appears to rely heavily on AI-generated text and has not been sufficiently edited afterward.\textbf{I believe the manuscript appears to rely heavily on AI-generated text and has not been sufficiently edited afterward.}

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 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×22\times2 games.

We would only like to add one remark on point 3. In the game bound, the coefficient of log⁡T\log T improves from O(H/γ)O(H/\gamma) to O(H)O(H), which does not depend on the column gap γ\gamma, 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.

Thank you for your response and your clarifications. I wish you the best with the revision.

Reviewer_r562OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the regret in the corrupted regime, parameterized by CC, which intrapolates between i.i.d. (C=0)(C=0) and fully adversarial regimes C=Θ(T)C = \Theta(T).

For general C>0C>0, the learner pays a so-called "corruption term". In the literature before this work, there is a gap of log term between the best upper and lower bounds.

The main contribution of this work is that, without changing the Tsallis-INF algorithm, it provides new analysis and show that the log term in the upper bound is unnecessary. This can be further applied to improve no-regret game learning.

Critical strengths
  1. The main contribution is a novel and improved analysis for Tsallif-INF regarding the self-bounding term in the corrupted regime. The detailed insights on this part is very informative and helpful.
  2. The improvement is also applied to game (multi-player) setting.
Critical weaknesses
  1. The main weakness is that the improved bound is not proven in the most general corrupted setting (Eq. (9)) in the paper.
Questions for authors
  1. What's the barrier towards the most general SB(2C)SB(2C) class?
  2. Do authors believe it's possible to obtain similar improvement?
1 comment

Thank you very much for reading the paper carefully. We also appreciate your questions on the self-bounding class, which is the main open problem of this work.

From the other reviews, we understand that the presentation needs substantial improvement, and we do not think this can be done properly during the discussion period. We have therefore decided to withdraw the submission and revise the paper carefully. Below we briefly answer your questions.

Q1. Our proof uses the drift of the potential in each round, and this needs the conditional gaps in each round. The class SB(2C)\mathsf{SB}(2C) only gives Eq. (9), which is one inequality on the final regret, where an early excess can cancel a later shortfall (Appendix M). Since it gives no information on each round, our potential argument does not apply.

Q2. We think this is open. The lower bounds on SB(2C)\mathsf{SB}(2C) (ours and the one by Ito (2021)) have no logarithm, so a similar improvement is not ruled out. However, for Tsallis-INF on this class, we have neither an upper bound without the logarithm nor a lower bound with it.

In the revised paper we will explain this limitation and the barrier above more clearly.

Thank you again for your time and for your comments.

Reviewer_dPWjOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper presents a new analysis of the well-known Tsallis-INF algorithm, removing a logarithmic factor from the corruption-dependent regret term for stochastic bandits with adaptive corruption. The analysis covers both importance-weighted and reduced-variance estimators under a per-round conditional-gap assumption. The authors also provide lower bounds and apply the improved guarantee to a previously established reduction for learning in zero-sum games.

The contribution is primarily a refinement of the analysis of a known algorithm. I found the scope of the improvement limited relative to the substantial technical complexity of the paper. Although the authors identify regimes in which the refined bound is tighter, I was not convinced that the manuscript adequately establishes the broader significance of the result or communicates a sufficiently substantial conceptual contribution.

Critical strengths

The paper studies a well-established problem in corruption-robust bandits and addresses a specific gap between existing upper and lower bounds in log factor.

Critical weaknesses
  • Limited contribution. The algorithm is unchanged, and the main improvement removes a logarithmic factor from the corruption-dependent regret term. The game upper bound follows through an existing reduction. I am not convinced that the contribution is sufficiently substantial relative to the technical complexity of the analysis.

  • Unclear broader significance. The motivation focuses on closing the gap between existing bounds, but the broader conceptual value remains unclear. The authors should identify which proof techniques or ideas could improve results in other settings, specify those settings, and explain what improvements these ideas might enable.

  • Dense presentation and difficult proof verification. The abstract and main proof overview are overloaded with notation and technical details, while the central insight remains difficult to extract. I could not fully verify the argument from the main paper. Have the authors explored simplifying the proof for human readability, using fewer auxiliary quantities and a clearer explanation of the purpose of each step?

  • Restricted model generality. The improvement requires per-round conditional-gap structure and does not cover the full self-bounding class addressed by previous analyses. This limits its generality and leaves unclear whether the restriction is inherent or specific to the proof.

  • Incomplete matching for heterogeneous gaps. The upper and lower corruption bounds depend on different gap complexities, HH and H∗H_*, leaving a possible O(log⁡K)O(\sqrt{\log K}) discrepancy. Constant-factor matching is established for equal gaps within the stated parameter regime.

  • Limited regret guarantee. The square-root corruption dependence concerns expected pseudo-regret on observed losses; the implied clean-regret bound still includes an additional 2C2C. Although the currently optimal arm may change, the guarantee uses a fixed-arm comparator and does not establish dynamic regret.

Questions for authors
  1. Beyond closing the logarithmic discrepancy, what is the main conceptual insight that readers should take away from this work? Why is this insight significant for the broader online learning community?

  2. Which technical ideas, proof techniques, or concepts from your analysis do you believe could help improve results in other settings? Which settings specifically, and what improvements might these ideas enable? Please clarify which components of the proof could transfer and which depend essentially on the particular algorithm and assumptions studied here.

  3. What is the main difficulty in extending the result to the full self-bounding class? Do you believe the restriction reflects a limitation of the algorithm or of the present analysis?

  4. Does the remaining difference between the upper-bound complexity HH and the lower-bound complexity H∗H_* arise from the upper-bound analysis or the lower-bound construction?

  5. Have you attempted to simplify the proof to improve its readability for human readers? In particular, could the argument be organized around fewer auxiliary quantities and a clearer sequence of steps, with an explanation of the purpose of each step and how it contributes to the main result?

2 comments

Thank you very much for the careful review and for the constructive comments and questions.

We agree that the presentation needs to be improved substantially and that the proof is hard to verify in its current form. We do not think this can be fixed properly during the discussion period, so we have decided to withdraw the submission and revise the paper carefully. We will use your comments in the revision. Below we briefly answer your questions.

On the significance (W1, W2). We would like to add some background that the paper does not explain. We had been working on this problem for several years. We expected that the logarithmic factor is necessary, and we were trying to prove a matching lower bound. The improved upper bound came out of AI-assisted work (as disclosed in the AI use statement), and it was a surprise to us. We wrote the paper up quickly because we thought that people working on the same problem would want to know the result early. We admit that the presentation suffered from this.

We also think that the application to games is more than the removal of a log factor. The coefficient of log⁡T\log T in the Nash regret improves from O(H/γ)O(H/\gamma) to O(H)O(H), which no longer depends on the column gap γ\gamma, so the asymptotic behavior changes. For two-row games this coefficient is tight up to a constant (Theorem 5).

Q1. The main message is that the cost of learning and the cost of corruption can be separated: the stochastic term needs a logarithm, but the corruption term does not. The logarithm in the previous bounds comes from the proof technique (the self-bounding argument, which uses only one inequality on the final regret with a single multiplier), not from the algorithm itself.

Q2. We think that only a small part transfers directly. Lemma 11 (gap counting) and Lemma 8 (weight schedule) depend only on the gap vector and not on the algorithm, so they can be reused. However, the rest of the analysis depends heavily on the fact that the learning rate depends only on the round, which gives the explicit expression pt,i=at2/ui2p_{t,i}=a_t^2/u_i^2 for the sampling probabilities. FTRL-based algorithms for more general problems beyond multi-armed bandits often use more complicated regularizers or adaptive learning rates, and such an explicit expression is not available there. So we expect the extension to these settings to be difficult.

Q3. Our proof uses the drift of the potential in each round, and this needs the conditional gaps in each round. The self-bounding class only gives one inequality on the final regret, where an early excess can cancel a later shortfall (Appendix M), so our argument does not apply. This is a limitation of our analysis. We do not know whether it is also a limitation of the algorithm: for Tsallis-INF on this class, we have neither a lower bound with the logarithm nor an upper bound without it.

Q4. We do not know which of the two bounds is loose. In the lower bound the adversary uses the budget at a single gap scale, which leads to H∗H_*, while the upper bound adds up the cost over all scales, which leads to HH. The two agree for equal gaps, and in general they differ by at most a factor of 1+log⁡(K−1)1+\log(K-1).

Q5. Yes, and we spent quite a lot of time on this. We tried two natural directions. The first was to derive the result only from the intermediate bound RegT≤O(∑tt−1/2∑i≠i⋆pt,i)\mathrm{Reg}_T\le O\bigl(\sum_t t^{-1/2}\sum_{i\ne i^\star}\sqrt{p_{t,i}}\bigr), as in the self-bounding analysis. We can show that this is impossible, so some additional property of the algorithm has to be used. The second was to use the standard stability–penalty decomposition of FTRL instead of our (nonstandard) potential, but this turned out to make the proof more complicated rather than simpler.

When the reference arm remains optimal in conditional expectation, there is a short proof of about one page (Appendix F), and we plan to start from it in the revised paper. We are not sure whether all of the remaining complexity is really necessary. We also agree that the current proof skips many steps and is hard to read.

On soundness. We have checked every step of all the proofs ourselves. We understand that the current writing makes it hard for readers to do the same, and we will improve this in the revision.

Thank you again for your time and for the detailed comments.

I thank the authors for the response; it seems that you are truly enthusiastic about your results. However, my honest opinion is that in our era, this paper will not contribute to the learning community knowledge, as much of the work presented is technical, and the impact of it to other domains is unclear. I thus keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.