Logarithm-Free Corruption Bounds for Tsallis-INF

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 ${\Delta }_i$, write $H={\sum }_{i\ne i^{\star }}{\Delta }_i^{-1}$ and $B_T={\sum }_{i\ne i^{\star }}{\Delta }_i^{-1}{\log }_{+}({\Delta }_i^{2}T)$. We prove that both the importance-weighted and reduced-variance versions of Tsallis-INF satisfy ${\mathrm{Reg}}_T\le O(\min \{\sqrt{KT},B_T+\sqrt{CH}\})$, where ${\mathrm{Reg}}_T$ is pseudo-regret on the observed losses against the best fixed arm in expectation and $C$ 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.