mlsanityData to 7 Oct 2026

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

arXiv 2103.12487 ↗First posted 23 Mar 2021cs.LG stat.MLcited by 15

Not on the map. Why?

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.

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

Builds on

10 of 28 references.

References · 10

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  5. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  6. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  7. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  8. 2015Fighting Bandits with a New Kind of Smoothnesscited by 45
  9. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  10. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 5; 2023: 2; 2024: 5; 2025: 1.

15 papers.

Sort:

  1. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  2. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  3. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  4. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  5. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  6. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  7. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  8. 2021When Are Linear Stochastic Bandits Attackable?cited by 10
  9. 2022Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimizationcited by 4
  10. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  11. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  12. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
3 more
  1. 2025Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stabilitycited by 2
  2. 2024Adaptive Experimental Design for Policy Learningcited by 1
  3. 2024Stochastic Bandits Robust to Adversarial Attackscited by 1