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:
- Stochastic (i.i.d.): Rewards are drawn from fixed distributions, where the goal is logarithmic regret $O(\log T)$.
- 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.
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++.
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