Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits

Saeed Masoudian, Yevgeny SeldinarXiv 2021 · arXiv · OpenReview

Abstract

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 $\mathcal{O}\left(\left(\sum_{i\neq i^*} \frac{1}{\Delta_i}\right)\log_+\left(\frac{(K-1)T}{\left(\sum_{i\neq i^*} \frac{1}{\Delta_i}\right)^2}\right)+\sqrt{C\left(\sum_{i\neq i^*}\frac{1}{\Delta_i}\right)\log_+\left(\frac{(K-1)T}{C\sum_{i\neq i^*}\frac{1}{\Delta_i}}\right)}\right)$ regret bound, where $T$ is the time horizon, $K$ is the number of arms, $\Delta_i$ are the suboptimality gaps, $i^*$ is the best arm, $C$ is the corruption magnitude, and $\log_+(x) = \max\left(1,\log x\right)$. 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.

Introduction

In Multi-Armed Bandit (MAB) problems, researchers typically distinguish between stochastic environments (where rewards follow fixed distributions) and adversarial environments (where rewards are chosen arbitrarily). While optimal algorithms exist for both extremes, real-world scenarios are often "mostly stochastic" with occasional adversarial "corruptions."

The Tsallis-INF algorithm is a leading "best-of-both-worlds" approach, performing near-optimally in both regimes without prior knowledge of the environment. However, previous analyses for intermediate regimes—specifically the stochastically constrained adversarial regime—left a gap in performance scaling relative to time ($T$) and corruption magnitude ($C$). This paper provides a significantly tighter theoretical analysis of Tsallis-INF, refining the "self-bounding" proof technique to achieve improved regret bounds.

Methodology

The authors do not modify the Tsallis-INF algorithm itself; rather, they provide a refined mathematical analysis within the "Follow the Regularized Leader" (FTRL) framework using Tsallis entropy (power 1/2) as a regularizer. The core innovation lies in two technical improvements to the self-bounding property:

  1. Joint Optimization: Unlike previous proofs that optimized algorithm probabilities and regime-switching parameters separately, this work performs a joint optimization. This approach is more complex but yields tighter bounds.
  2. Constraint Preservation: The analysis maintains the constraint that arm probabilities must sum to one throughout the optimization, avoiding the relaxations used in prior work.

To handle the resulting optimization complexity, the authors utilize the Lambert W function (specifically the -1 branch), enabling a more precise determination of the transition threshold between stochastic and adversarial behavior.

Key Insights

  • Unified Theory: The standard adversarial regret bound ($O(\sqrt{KT})$) now emerges as a natural limit case of the self-bounding analysis as corruption increases, unifying the theory across regimes.
  • Logarithmic Improvements: In stochastic settings, the dependence on time is refined. Instead of a simple $\log T$, the bound now accounts for the gaps between arms ($\Delta_i$), leading to a tighter fit for how much reward is lost over time.
  • Enhanced Robustness: Tsallis-INF is shown to be more robust to corruptions than previously understood. For large $C$, the regret bound is improved by a factor of approximately $\sqrt{\log T / \log(T/C)}$.
  • Generalizability: The authors provide a "meta-theorem" (Theorem 4), allowing this improved analysis to be applied to more complex structures, such as episodic Markov Decision Processes (MDPs).

Results

The primary contribution is the derivation of tighter regret bounds across different levels of corruption. As shown in Figure 1, the new analysis provides a more refined logarithmic term for small $C$ and a significant improvement for large $C$.

Comparison of regret bounds between Zimmert and Seldin (2021) and the improved bounds presented in this paper.

Specifically:

  • Small Corruption ($C$): The leading term is improved from $O(\sum \frac{1}{\Delta_i} \log T)$ to a version sensitive to the squared sum of inverse gaps.
  • Large Corruption ($C$): The bound is improved by a factor of $O(\sqrt{\log T / \log(T/C)})$.
  • Unified Proof: The analysis reduces two separate optimization problems into a single, more powerful one.

Limitations and Future Work

Despite these improvements, some limitations remain:

  • Unique Best Arm: The current proof technique still requires the assumption of a unique best arm, although empirical evidence suggests the algorithm handles multiple best arms effectively.
  • Algorithmic Scope: The analysis is specific to the FTRL framework. Extending these joint optimization insights to other families, such as Mirror Descent, remains an open challenge.

Note: As a theoretical study, this work is validated through mathematical proofs; no empirical datasets were utilized.

Summary updated

Abstract

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 $\mathcal{O}\left(\left(\sum_{i\neq i^*} \frac{1}{\Delta_i}\right)\log_+\left(\frac{(K-1)T}{\left(\sum_{i\neq i^*} \frac{1}{\Delta_i}\right)^2}\right)+\sqrt{C\left(\sum_{i\neq i^*}\frac{1}{\Delta_i}\right)\log_+\left(\frac{(K-1)T}{C\sum_{i\neq i^*}\frac{1}{\Delta_i}}\right)}\right)$ regret bound, where $T$ is the time horizon, $K$ is the number of arms, $\Delta_i$ are the suboptimality gaps, $i^*$ is the best arm, $C$ is the corruption magnitude, and $\log_+(x) = \max\left(1,\log x\right)$. 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.
BibTeX
@misc{masoudian2021improved,
  author = {Saeed Masoudian and Yevgeny Seldin},
  title = {{Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits}},
  year = {2021},
  eprint = {2103.12487},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.12487},
}
Figure