An Optimal Algorithm for Stochastic and Adversarial Bandits

Julian Zimmert, Yevgeny Seldin

Introduction

The multi-armed bandit (MAB) problem is a fundamental framework for decision-making under uncertainty. Traditionally, researchers have focused on two distinct environments: stochastic, where arm losses follow fixed probability distributions, and adversarial, where losses are chosen by a malicious agent. While algorithms like UCB1 excel in stochastic settings ($O(\log T)$ regret) and EXP3 handles adversarial ones ($O(\sqrt{T})$ regret), they typically fail when placed in the "wrong" environment. Using an adversarial algorithm in a stochastic setting leads to sub-optimal regret, while using a stochastic algorithm against an adversary can result in catastrophic linear regret.

The Best-of-Both-Worlds Challenge

Creating a single algorithm that performs optimally in both regimes—without knowing the environment type in advance—has been a long-standing goal. Previous "best-of-both-worlds" solutions often relied on complex detection mechanisms to switch between modes or required prior knowledge of the time horizon $T$. This paper introduces $\frac{1}{2}$-Tsallis-INF, a simple, anytime algorithm that achieves universal optimality through a unified mathematical framework.

Methods: The Power of Tsallis Entropy

The authors utilize the Online Mirror Descent (OMD) framework, replacing the standard Shannon entropy regularizer with Tsallis entropy. This entropy is parameterized by $\alpha \in [0, 1]$. As shown in the theoretical analysis summarized in the table below, the choice of $\alpha$ is critical for balancing the upper and lower regret bounds.

Table 1: Theoretical regret bounds and learning rates for different values of $\alpha$. Note that $\alpha = 1/2$ provides optimal $\mathcal{O}(1)$ ratios for both regimes.

By setting $\alpha = 1/2$ and employing a simple, time-varying learning rate $\eta_t = 1/\sqrt{t}$, the algorithm naturally balances exploration and exploitation. A key theoretical innovation is the discovery of a "self-bounding" property of the regret, which allows the authors to prove optimal bounds without the cumbersome variance-bounding techniques that hindered previous research. This allows the algorithm to be "anytime," meaning it doesn't need to know the total number of steps in advance.

Empirical Results

The algorithm was tested against classic baselines (UCB1, EXP3, Thompson Sampling) and modern robust algorithms (EXP3++, BROAD) in two primary scenarios: standard stochastic bandits and stochastically constrained adversaries (where optimal arms swap periodically).

Figure 1: Empirical regret comparison in (a) stochastic and (b) stochastically constrained adversarial regimes. The $\frac{1}{2}$-Tsallis-INF algorithm (T-INF, blue circles) maintains competitive performance in both.

As illustrated in Figure 1, $\frac{1}{2}$-Tsallis-INF (labeled T-INF) performs exceptionally well. In the stochastic regime (a), it significantly outperforms adversarial-only algorithms like EXP3 and maintains a logarithmic regret curve. In the adversarial regime (b), it remains robust while popular stochastic algorithms like Thompson Sampling (TS) and UCB1 suffer near-linear regret. Notably, Thompson Sampling, often considered the gold standard for stochastic problems, proves extremely fragile in shifting environments.

Key Insights and Future Work

The primary takeaway is that robustness does not require complexity. $\frac{1}{2}$-Tsallis-INF avoids "if-then" logic or environment testing, adapting fluidly to the data. While the current proof assumes a unique best arm for the stochastic guarantee, empirical evidence suggests the algorithm is more general. Future work aims to refine the constant factors in the bounds and extend the framework to partial monitoring and more complex decision-making games.

Summary updated

Abstract

We derive an algorithm that achieves the optimal (up to constants) pseudo-regret in both adversarial and stochastic multi-armed bandits without prior knowledge of the regime and time horizon. The a...
BibTeX
@inproceedings{zimmert2019optimal,
  author = {Julian Zimmert and Yevgeny Seldin},
  title = {{An Optimal Algorithm for Stochastic and Adversarial Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=IoFlasP2YlV},
}
Figure