An Optimal Algorithm for Stochastic and Adversarial Bandits

Julian Zimmert, Yevgeny Seldin

Abstract

We derive an algorithm that achieves the optimal (within constants) pseudo-regret in both adversarial and stochastic multi-armed bandits without prior knowledge of the regime and time horizon. The algorithm is based on online mirror descent (OMD) with Tsallis entropy regularization with power $\alpha=1/2$ and reduced-variance loss estimators. More generally, we define an adversarial regime with a self-bounding constraint, which includes stochastic regime, stochastically constrained adversarial regime, and stochastic regime with adversarial corruptions as special cases, and show that the algorithm achieves logarithmic regret guarantee in this regime and all of its special cases simultaneously with the adversarial regret guarantee. The algorithm also achieves adversarial and stochastic optimality in the utility-based dueling bandit setting. We provide empirical evaluation of the algorithm demonstrating that it significantly outperforms UCB1 and EXP3 in stochastic environments.

Introduction

In the Multi-Armed Bandit (MAB) problem, an agent must choose between $K$ actions to maximize rewards over time. Historically, research has been bifurcated into two distinct regimes:

  1. Stochastic (i.i.d.): Rewards are drawn from fixed distributions, where the goal is logarithmic regret $O(\log T)$.
  2. Adversarial: Rewards are chosen by an opponent, where the goal is square-root regret $O(\sqrt{T})$.

The "Best of Both Worlds" (BoBW) challenge involves creating a single algorithm that performs optimally in both settings without knowing the environment type in advance. Previous solutions often relied on complex switching mechanisms or required prior knowledge of the time horizon. This paper introduces Tsallis-INF, an algorithm that naturally bridges this gap through a unified mathematical framework.

The Tsallis-INF Algorithm

The core of Tsallis-INF is the Online Mirror Descent (OMD) framework. The algorithm's performance hinges on two critical design choices: the choice of regularizer and the loss estimator.

Tsallis Entropy Regularization

The authors employ Tsallis entropy with a power of $\alpha = 1/2$ as the regularizer. This specific value serves as a "Goldilocks" zone:

  • $\alpha = 1$ (Shannon entropy, as in Exp3) is optimal for adversarial settings but sub-optimal for stochastic ones.
  • $\alpha = 0$ (Log-barrier) is optimal for stochastic settings but sub-optimal for adversarial ones.
  • $\alpha = 1/2$ provides the necessary curvature to handle both regimes simultaneously.

Reduced-Variance (RV) Estimators

To match the best-known theoretical constants, the algorithm incorporates Reduced-Variance loss estimators. Unlike standard importance weighting, RV estimators mitigate the variance of reward estimates, which is crucial for achieving tight regret bounds in the stochastic case.

Algorithm 1: Online Mirror Descent for bandits

Theoretical and Empirical Results

The primary theoretical contribution is the introduction of the self-bounding property. The authors demonstrate that in "nice" (stochastic-like) environments, the algorithm's regret is bounded by a function of itself. This recursion allows the $O(\sqrt{T})$ adversarial bound to naturally collapse into an $O(\log T)$ stochastic bound.

Performance Comparison

Tsallis-INF achieves minimax optimality in adversarial settings ($O(\sqrt{KT})$) and asymptotic optimality in stochastic settings ($O(\sum \frac{\log T}{\Delta_i})$). As shown in the comparison table below, the $\alpha=1/2$ approach provides a constant ratio between upper and lower bounds across both regimes, a feat not matched by previous state-of-the-art algorithms like BROAD or EXP3++.

Comparison of Tsallis-INF (alpha=1/2) with other algorithms

Empirical Findings

Empirical evaluations using Bernoulli rewards and stochastically constrained adversarial environments show that Tsallis-INF significantly outperforms UCB1 and Exp3. Notably, the paper reveals a vulnerability in Thompson Sampling: while it excels in pure i.i.d. settings, it can suffer nearly linear regret in adversarial environments where Tsallis-INF remains robust.

Conclusion

Tsallis-INF represents a significant milestone in bandit theory, providing a simple, anytime algorithm that is optimal in both stochastic and adversarial worlds. While the current proof for stochastic optimality assumes a unique best arm, empirical evidence suggests the algorithm is robust even when this assumption is violated. Future work aims to extend this BoBW framework to more complex scenarios, such as partial monitoring and combinatorial bandits.

Summary updated

Abstract

We derive an algorithm that achieves the optimal (within constants) pseudo-regret in both adversarial and stochastic multi-armed bandits without prior knowledge of the regime and time horizon. The algorithm is based on online mirror descent (OMD) with Tsallis entropy regularization with power $\alpha=1/2$ and reduced-variance loss estimators. More generally, we define an adversarial regime with a self-bounding constraint, which includes stochastic regime, stochastically constrained adversarial regime (Wei and Luo), and stochastic regime with adversarial corruptions (Lykouris et al.) as special cases, and show that the algorithm achieves logarithmic regret guarantee in this regime and all of its special cases simultaneously with the adversarial regret guarantee.} The algorithm also achieves adversarial and stochastic optimality in the utility-based dueling bandit setting. We provide empirical evaluation of the algorithm demonstrating that it significantly outperforms UCB1 and EXP3 in stochastic environments. We also provide examples of adversarial environments, where UCB1 and Thompson Sampling exhibit almost linear regret, whereas our algorithm suffers only logarithmic regret. To the best of our knowledge, this is the first example demonstrating vulnerability of Thompson Sampling in adversarial environments. Last, but not least, we present a general stochastic analysis and a general adversarial analysis of OMD algorithms with Tsallis entropy regularization for $\alpha\in[0,1]$ and explain the reason why $\alpha=1/2$ works best.
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