# Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions

arXiv: https://arxiv.org/abs/2103.12487 · HTML: https://mlsanity.com/paper/2103.12487/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 28 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Builds on (most cited first, 10 of 10)

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition](https://mlsanity.com/paper/2006.05606/) (2020)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [An Algorithm for Stochastic and Adversarial Bandits with Switching Costs](https://mlsanity.com/paper/2102.09864/) (2021)

## Built on by (most cited first, 15 of 15)

- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Better Best of Both Worlds Bounds for Bandits with Switching Costs](https://mlsanity.com/paper/2206.03098/) (2022)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [When Are Linear Stochastic Bandits Attackable?](https://mlsanity.com/paper/2110.09008/) (2021)
- [Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization](https://mlsanity.com/paper/2206.07528/) (2022)
- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability](https://mlsanity.com/paper/2512.20368/) (2025)
- [Stochastic Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2408.08859/) (2024)

## Abstract (arXiv)

We derive improved regret bounds for the Tsallis-INF algorithm of Zimmert and Seldin (2021). We show that in adversarial regimes with a (Delta,C,T) self-bounding constraint the algorithm achieves Oleft(left(sumineq i^* frac1Deltairight)log_+left(frac(K-1)Tleft(sumineq i^* frac1Deltairight)2right)+√Cleft(sumineq i^*frac1Deltairight)log_+left(frac(K-1)TCsumineq i^*frac1Deltairight)right) regret bound, where T is the time horizon, K is the number of arms, Deltai are the suboptimality gaps, i^* is the best arm, C is the corruption magnitude, and log_+(x) = maxleft(1,log xright). The regime includes stochastic bandits, stochastically constrained adversarial bandits, and stochastic bandits with adversarial corruptions as special cases. Additionally, we provide a general analysis, which allows to achieve the same kind of improvement for generalizations of Tsallis-INF to other settings beyond multiarmed bandits.